neural network - NeuQuant.js (JavaScript color quantization) hidden bug in JS conversion -
neuquant.js works when image width , height multiple of 100:
300x300
otherwise, there bug:
299x300
(these made this web app.)
i'm 90% sure bug in neuquant.js. have made tests using jsgif , omggif, , both encoders have same bug. obvious photographic images (quantize 256 colors) when image size other multiple of 100.
if understand neural networks, color quantization, and/or issues porting as3 js, please take look. original porter has abandoned project, , close working!
here my code implements in worker omggif:
importscripts('omggif.js', 'neuquant.js'); var rgba2rgb = function (data) { var pixels = []; var count = 0; var len = data.length; ( var i=0; i<len; i+=4 ) { pixels[count++] = data[i]; pixels[count++] = data[i+1]; pixels[count++] = data[i+2]; } return pixels; } var rgb2num = function(palette) { var colors = []; var count = 0; var len = palette.length; ( var i=0; i<len; i+=3 ) { colors[count++] = palette[i+2] | (palette[i+1] << 8) | (palette[i] << 16); } return colors; } self.onmessage = function(event) { var frames = event.data.frames; var frameslength = frames.length; var delay = event.data.delay / 10; var starttime = date.now(); var buffer = new uint8array( frames[0].width * frames[0].height * frameslength * 5 ); var gif = new gifwriter( buffer, frames[0].width, frames[0].height, { loop: 0 } ); // var pixels = new uint8array( frames[0].width * frames[0].height ); var addframe = function (frame) { var data = frame.data; // make palette neuquant.js var nqinpixels = rgba2rgb(data); var len = nqinpixels.length; var npix = len / 3; var map = []; var nq = new neuquant(nqinpixels, len, 10); // initialize quantizer var palettergb = nq.process(); // create reduced palette var palette = rgb2num(palettergb); // map image pixels new palette var k = 0; (var j = 0; j < npix; j++) { var index = nq.map(nqinpixels[k++] & 0xff, nqinpixels[k++] & 0xff, nqinpixels[k++] & 0xff); // usedentry[index] = true; map[j] = index; } gif.addframe( 0, 0, frame.width, frame.height, new uint8array( map ), { palette: new uint32array( palette ), delay: delay } ); } // add frames (var = 0; i<frameslength; i++) { addframe( frames[i] ); self.postmessage({ type: "progress", data: math.round( (i+1)/frameslength*100 ) }); } // finish var string = ''; ( var = 0, l = gif.end(); < l; ++ ) { string += string.fromcharcode( buffer[ ] ); } self.postmessage({ type: "gif", data: string, framecount: frameslength, encodetime: math.round( (date.now()-starttime)/10 ) / 100 }); }; and of neuquant.js:
/* * neuquant neural-net quantization algorithm * ------------------------------------------ * * copyright (c) 1994 anthony dekker * * neuquant neural-net quantization algorithm anthony dekker, 1994. see * "kohonen neural networks optimal colour quantization" in "network: * computation in neural systems" vol. 5 (1994) pp 351-367. discussion of * algorithm. * * party obtaining copy of these files author, directly or * indirectly, granted, free of charge, full , unrestricted irrevocable, * world-wide, paid up, royalty-free, nonexclusive right , license deal in * software , documentation files (the "software"), including without * limitation rights use, copy, modify, merge, publish, distribute, * sublicense, and/or sell copies of software, , permit persons * receive copies such party so, requirement being * copyright notice remain intact. */ /* * class handles neural-net quantization algorithm * @author kevin weiner (original java version - kweiner@fmsware.com) * @author thibault imbert (as3 version - bytearray.org) * @version 0.1 as3 implementation */ //import flash.utils.bytearray; neuquant = function() { var exports = {}; /*private_static*/ var netsize/*int*/ = 256; /* number of colours used */ /* 4 primes near 500 - assume no image has length large */ /* divisible 4 primes */ /*private_static*/ var prime1/*int*/ = 499; /*private_static*/ var prime2/*int*/ = 491; /*private_static*/ var prime3/*int*/ = 487; /*private_static*/ var prime4/*int*/ = 503; /*private_static*/ var minpicturebytes/*int*/ = (3 * prime4); /* minimum size input image */ /* * program skeleton ---------------- [select samplefac in range 1..30] [read * image input file] pic = (unsigned char*) malloc(3*width*height); * initnet(pic,3*width*height,samplefac); learn(); unbiasnet(); [write output * image header, using writecolourmap(f)] inxbuild(); write output image using * inxsearch(b,g,r) */ /* * network definitions ------------------- */ /*private_static*/ var maxnetpos/*int*/ = (netsize - 1); /*private_static*/ var netbiasshift/*int*/ = 4; /* bias colour values */ /*private_static*/ var ncycles/*int*/ = 100; /* no. of learning cycles */ /* defs freq , bias */ /*private_static*/ var intbiasshift/*int*/ = 16; /* bias fractions */ /*private_static*/ var intbias/*int*/ = (1 << intbiasshift); /*private_static*/ var gammashift/*int*/ = 10; /* gamma = 1024 */ /*private_static*/ var gamma/*int*/ = (1 << gammashift); /*private_static*/ var betashift/*int*/ = 10; /*private_static*/ var beta/*int*/ = (intbias >> betashift); /* beta = 1/1024 */ /*private_static*/ var betagamma/*int*/ = (intbias << (gammashift - betashift)); /* defs decreasing radius factor */ /*private_static*/ var initrad/*int*/ = (netsize >> 3); /* * 256 cols, radius * starts */ /*private_static*/ var radiusbiasshift/*int*/ = 6; /* @ 32.0 biased 6 bits */ /*private_static*/ var radiusbias/*int*/ = (1 << radiusbiasshift); /*private_static*/ var initradius/*int*/ = (initrad * radiusbias); /* * , * decreases * */ /*private_static*/ var radiusdec/*int*/ = 30; /* factor of 1/30 each cycle */ /* defs decreasing alpha factor */ /*private_static*/ var alphabiasshift/*int*/ = 10; /* alpha starts @ 1.0 */ /*private_static*/ var initalpha/*int*/ = (1 << alphabiasshift); /*private*/ var alphadec/*int*/ /* biased 10 bits */ /* radbias , alpharadbias used radpower calculation */ /*private_static*/ var radbiasshift/*int*/ = 8; /*private_static*/ var radbias/*int*/ = (1 << radbiasshift); /*private_static*/ var alpharadbshift/*int*/ = (alphabiasshift + radbiasshift); /*private_static*/ var alpharadbias/*int*/ = (1 << alpharadbshift); /* * types , global variables -------------------------- */ /*private*/ var thepicture/*bytearray*//* input image */ /*private*/ var lengthcount/*int*/; /* lengthcount = h*w*3 */ /*private*/ var samplefac/*int*/; /* sampling factor 1..30 */ // typedef int pixel[4]; /* bgrc */ /*private*/ var network/*array*/; /* network - [netsize][4] */ /*protected*/ var netindex/*array*/ = new array(); /* network lookup - 256 */ /*private*/ var bias/*array*/ = new array(); /* bias , freq arrays learning */ /*private*/ var freq/*array*/ = new array(); /*private*/ var radpower/*array*/ = new array(); var neuquant = exports.neuquant = function neuquant(thepic/*bytearray*/, len/*int*/, sample/*int*/) { var i/*int*/; var p/*array*/; thepicture = thepic; lengthcount = len; samplefac = sample; network = new array(netsize); (i = 0; < netsize; i++) { network[i] = new array(4); p = network[i]; p[0] = p[1] = p[2] = (i << (netbiasshift + 8)) / netsize; freq[i] = intbias / netsize; /* 1/netsize */ bias[i] = 0; } } var colormap = function colormap()/*bytearray*/ { var map/*bytearray*/ = []; var index/*array*/ = new array(netsize); (var i/*int*/ = 0; < netsize; i++) index[network[i][3]] = i; var k/*int*/ = 0; (var l/*int*/ = 0; l < netsize; l++) { var j/*int*/ = index[l]; map[k++] = (network[j][0]); map[k++] = (network[j][1]); map[k++] = (network[j][2]); } return map; } /* * insertion sort of network , building of netindex[0..255] (to after * unbias) * ------------------------------------------------------------------------------- */ var inxbuild = function inxbuild()/*void*/ { var i/*int*/; var j/*int*/; var smallpos/*int*/; var smallval/*int*/; var p/*array*/; var q/*array*/; var previouscol/*int*/ var startpos/*int*/ previouscol = 0; startpos = 0; (i = 0; < netsize; i++) { p = network[i]; smallpos = i; smallval = p[1]; /* index on g */ /* find smallest in i..netsize-1 */ (j = + 1; j < netsize; j++) { q = network[j]; if (q[1] < smallval) { /* index on g */ smallpos = j; smallval = q[1]; /* index on g */ } } q = network[smallpos]; /* swap p (i) , q (smallpos) entries */ if (i != smallpos) { j = q[0]; q[0] = p[0]; p[0] = j; j = q[1]; q[1] = p[1]; p[1] = j; j = q[2]; q[2] = p[2]; p[2] = j; j = q[3]; q[3] = p[3]; p[3] = j; } /* smallval entry in position */ if (smallval != previouscol) { netindex[previouscol] = (startpos + i) >> 1; (j = previouscol + 1; j < smallval; j++) netindex[j] = i; previouscol = smallval; startpos = i; } } netindex[previouscol] = (startpos + maxnetpos) >> 1; (j = previouscol + 1; j < 256; j++) netindex[j] = maxnetpos; /* 256 */ } /* * main learning loop ------------------ */ var learn = function learn()/*void*/ { var i/*int*/; var j/*int*/; var b/*int*/; var g/*int*/ var r/*int*/; var radius/*int*/; var rad/*int*/; var alpha/*int*/; var step/*int*/; var delta/*int*/; var samplepixels/*int*/; var p/*bytearray*/; var pix/*int*/; var lim/*int*/; if (lengthcount < minpicturebytes) samplefac = 1; alphadec = 30 + ((samplefac - 1) / 3); p = thepicture; pix = 0; lim = lengthcount; samplepixels = lengthcount / (3 * samplefac); delta = samplepixels / ncycles; alpha = initalpha; radius = initradius; rad = radius >> radiusbiasshift; if (rad <= 1) rad = 0; (i = 0; < rad; i++) radpower[i] = alpha * (((rad * rad - * i) * radbias) / (rad * rad)); if (lengthcount < minpicturebytes) step = 3; else if ((lengthcount % prime1) != 0) step = 3 * prime1; else { if ((lengthcount % prime2) != 0) step = 3 * prime2; else { if ((lengthcount % prime3) != 0) step = 3 * prime3; else step = 3 * prime4; } } = 0; while (i < samplepixels) { b = (p[pix + 0] & 0xff) << netbiasshift; g = (p[pix + 1] & 0xff) << netbiasshift; r = (p[pix + 2] & 0xff) << netbiasshift; j = contest(b, g, r); altersingle(alpha, j, b, g, r); if (rad != 0) alterneigh(rad, j, b, g, r); /* alter neighbours */ pix += step; if (pix >= lim) pix -= lengthcount; i++; if (delta == 0) delta = 1; if (i % delta == 0) { alpha -= alpha / alphadec; radius -= radius / radiusdec; rad = radius >> radiusbiasshift; if (rad <= 1) rad = 0; (j = 0; j < rad; j++) radpower[j] = alpha * (((rad * rad - j * j) * radbias) / (rad * rad)); } } } /* ** search bgr values 0..255 (after net unbiased) , return colour * index * ---------------------------------------------------------------------------- */ var map = exports.map = function map(b/*int*/, g/*int*/, r/*int*/)/*int*/ { var i/*int*/; var j/*int*/; var dist/*int*/ var a/*int*/; var bestd/*int*/; var p/*array*/; var best/*int*/; bestd = 1000; /* biggest possible dist 256*3 */ best = -1; = netindex[g]; /* index on g */ j = - 1; /* start @ netindex[g] , work outwards */ while ((i < netsize) || (j >= 0)) { if (i < netsize) { p = network[i]; dist = p[1] - g; /* inx key */ if (dist >= bestd) = netsize; /* stop iter */ else { i++; if (dist < 0) dist = -dist; = p[0] - b; if (a < 0) = -a; dist += a; if (dist < bestd) { = p[2] - r; if (a < 0) = -a; dist += a; if (dist < bestd) { bestd = dist; best = p[3]; } } } } if (j >= 0) { p = network[j]; dist = g - p[1]; /* inx key - reverse dif */ if (dist >= bestd) j = -1; /* stop iter */ else { j--; if (dist < 0) dist = -dist; = p[0] - b; if (a < 0) = -a; dist += a; if (dist < bestd) { = p[2] - r; if (a < 0)a = -a; dist += a; if (dist < bestd) { bestd = dist; best = p[3]; } } } } } return (best); } var process = exports.process = function process()/*bytearray*/ { learn(); unbiasnet(); inxbuild(); return colormap(); } /* * unbias network give byte values 0..255 , record position prepare * sort * ----------------------------------------------------------------------------------- */ var unbiasnet = function unbiasnet()/*void*/ { var i/*int*/; var j/*int*/; (i = 0; < netsize; i++) { network[i][0] >>= netbiasshift; network[i][1] >>= netbiasshift; network[i][2] >>= netbiasshift; network[i][3] = i; /* record colour no */ } } /* * move adjacent neurons precomputed alpha*(1-((i-j)^2/[r]^2)) in * radpower[|i-j|] * --------------------------------------------------------------------------------- */ var alterneigh = function alterneigh(rad/*int*/, i/*int*/, b/*int*/, g/*int*/, r/*int*/)/*void*/ { var j/*int*/; var k/*int*/; var lo/*int*/; var hi/*int*/; var a/*int*/; var m/*int*/; var p/*array*/; lo = - rad; if (lo < -1) lo = -1; hi = + rad; if (hi > netsize) hi = netsize; j = + 1; k = - 1; m = 1; while ((j < hi) || (k > lo)) { = radpower[m++]; if (j < hi) { p = network[j++]; try { p[0] -= (a * (p[0] - b)) / alpharadbias; p[1] -= (a * (p[1] - g)) / alpharadbias; p[2] -= (a * (p[2] - r)) / alpharadbias; } catch (e/*error*/) {} // prevents 1.3 miscompilation } if (k > lo) { p = network[k--]; try { p[0] -= (a * (p[0] - b)) / alpharadbias; p[1] -= (a * (p[1] - g)) / alpharadbias; p[2] -= (a * (p[2] - r)) / alpharadbias; } catch (e/*error*/) {} } } } /* * move neuron towards biased (b,g,r) factor alpha * ---------------------------------------------------- */ var altersingle = function altersingle(alpha/*int*/, i/*int*/, b/*int*/, g/*int*/, r/*int*/)/*void*/ { /* alter hit neuron */ var n/*array*/ = network[i]; n[0] -= (alpha * (n[0] - b)) / initalpha; n[1] -= (alpha * (n[1] - g)) / initalpha; n[2] -= (alpha * (n[2] - r)) / initalpha; } /* * search biased bgr values ---------------------------- */ var contest = function contest(b/*int*/, g/*int*/, r/*int*/)/*int*/ { /* finds closest neuron (min dist) , updates freq */ /* finds best neuron (min dist-bias) , returns position */ /* chosen neurons, freq[i] high , bias[i] negative */ /* bias[i] = gamma*((1/netsize)-freq[i]) */ var i/*int*/; var dist/*int*/; var a/*int*/; var biasdist/*int*/; var betafreq/*int*/; var bestpos/*int*/; var bestbiaspos/*int*/; var bestd/*int*/; var bestbiasd/*int*/; var n/*array*/; bestd = ~(1 << 31); bestbiasd = bestd; bestpos = -1; bestbiaspos = bestpos; (i = 0; < netsize; i++) { n = network[i]; dist = n[0] - b; if (dist < 0) dist = -dist; = n[1] - g; if (a < 0) = -a; dist += a; = n[2] - r; if (a < 0) = -a; dist += a; if (dist < bestd) { bestd = dist; bestpos = i; } biasdist = dist - ((bias[i]) >> (intbiasshift - netbiasshift)); if (biasdist < bestbiasd) { bestbiasd = biasdist; bestbiaspos = i; } betafreq = (freq[i] >> betashift); freq[i] -= betafreq; bias[i] += (betafreq << gammashift); } freq[bestpos] += beta; bias[bestpos] -= betagamma; return (bestbiaspos); } neuquant.apply(this, arguments); return exports; }
javascript code seems ignore c truncates results of operations decimal numbers before assign them integer variables. so, int = 5 / 2; 2 c, var = 5 / 2; 2.5 javascript.
said that, change line:
delta = samplepixels / ncycles; to:
delta = (samplepixels / ncycles) | 0; this solves issue, it's not clear me if change solves possible integer conversion problems, or 1 exposed in question.
note have used bitwise or operator truncate result. classic way truncate number in javascript, because bitwise operators treat operands integers of 32 bits.
Comments
Post a Comment