admin管理员组文章数量:1292784
NeuQuant.js works well when the image width and height are a multiple of 100:
300x300
Otherwise, there is obviously a bug:
299x300
(These were made with this web app.)
I'm 90% sure that the bug is in NeuQuant.js. I have made tests using it with jsgif and omggif, and both encoders have the same bug. It is only obvious with photographic images (quantize to 256 colors) when the image size is anything other than a multiple of 100.
If you understand neural networks, color quantization, and/or issues with porting AS3 to JS, please take a look. The original porter has abandoned the project, and it is so close to working!
Here is my code that implements it in a worker with OMGGIF:
importScripts('omggif.js', 'NeuQuant.js');
var rgba2rgb = function (data) {
var pixels = [];
var count = 0;
var len = data.length;
for ( 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;
for ( 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 with 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 to new palette
var k = 0;
for (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 all frames
for (var i = 0; i<framesLength; i++) {
addFrame( frames[i] );
self.postMessage({
type: "progress",
data: Math.round( (i+1)/framesLength*100 )
});
}
// Finish
var string = '';
for ( var i = 0, l = gif.end(); i < l; i ++ ) {
string += String.fromCharCode( buffer[ i ] );
}
self.postMessage({
type: "gif",
data: string,
frameCount: framesLength,
encodeTime: Math.round( (Date.now()-startTime)/10 ) / 100
});
};
And all of NeuQuant.js:
/*
* NeuQuant Neural-Net Quantization Algorithm
* ------------------------------------------
*
* Copyright (c) 1994 Anthony Dekker
*
* NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. See
* "Kohonen neural networks for optimal colour quantization" in "Network:
* Computation in Neural Systems" Vol. 5 (1994) pp 351-367. for a discussion of
* the algorithm.
*
* Any party obtaining a copy of these files from the author, directly or
* indirectly, is granted, free of charge, a full and unrestricted irrevocable,
* world-wide, paid up, royalty-free, nonexclusive right and license to deal in
* this software and documentation files (the "Software"), including without
* limitation the rights to use, copy, modify, merge, publish, distribute,
* sublicense, and/or sell copies of the Software, and to permit persons who
* receive copies from any such party to do so, with the only requirement being
* that this copyright notice remain intact.
*/
/*
* This class handles Neural-Net quantization algorithm
* @author Kevin Weiner (original Java version - [email protected])
* @author Thibault Imbert (AS3 version - bytearray)
* @version 0.1 AS3 implementation
*/
//import flash.utils.ByteArray;
NeuQuant = function()
{
var exports = {};
/*private_static*/ var netsize/*int*/ = 256; /* number of colours used */
/* four primes near 500 - assume no image has a length so large */
/* that it is divisible by all four 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 for input image */
/*
* Program Skeleton ---------------- [select samplefac in range 1..30] [read
* image from 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 for colour values */
/*private_static*/ var ncycles/*int*/ = 100; /* no. of learning cycles */
/* defs for freq and bias */
/*private_static*/ var intbiasshift/*int*/ = 16; /* bias for 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 for decreasing radius factor */
/*private_static*/ var initrad/*int*/ = (netsize >> 3); /*
* for 256 cols, radius
* starts
*/
/*private_static*/ var radiusbiasshift/*int*/ = 6; /* at 32.0 biased by 6 bits */
/*private_static*/ var radiusbias/*int*/ = (1 << radiusbiasshift);
/*private_static*/ var initradius/*int*/ = (initrad * radiusbias); /*
* and
* decreases
* by a
*/
/*private_static*/ var radiusdec/*int*/ = 30; /* factor of 1/30 each cycle */
/* defs for decreasing alpha factor */
/*private_static*/ var alphabiasshift/*int*/ = 10; /* alpha starts at 1.0 */
/*private_static*/ var initalpha/*int*/ = (1 << alphabiasshift);
/*private*/ var alphadec/*int*/ /* biased by 10 bits */
/* radbias and alpharadbias used for 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 and Global Variables --------------------------
*/
/*private*/ var thepicture/*ByteArray*//* the input image itself */
/*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*/; /* the network itself - [netsize][4] */
/*protected*/ var netindex/*Array*/ = new Array();
/* for network lookup - really 256 */
/*private*/ var bias/*Array*/ = new Array();
/* bias and freq arrays for 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);
for (i = 0; i < 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);
for (var i/*int*/ = 0; i < netsize; i++)
index[network[i][3]] = i;
var k/*int*/ = 0;
for (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 and building of netindex[0..255] (to do 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;
for (i = 0; i < netsize; i++)
{
p = network[i];
smallpos = i;
smallval = p[1]; /* index on g */
/* find smallest in i.size-1 */
for (j = i + 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) and 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 is now in position i */
if (smallval != previouscol)
{
netindex[previouscol] = (startpos + i) >> 1;
for (j = previouscol + 1; j < smallval; j++) netindex[j] = i;
previouscol = smallval;
startpos = i;
}
}
netindex[previouscol] = (startpos + maxnetpos) >> 1;
for (j = previouscol + 1; j < 256; j++) netindex[j] = maxnetpos; /* really 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;
for (i = 0; i < rad; i++) radpower[i] = alpha * (((rad * rad - i * 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;
}
}
i = 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;
for (j = 0; j < rad; j++) radpower[j] = alpha * (((rad * rad - j * j) * radbias) / (rad * rad));
}
}
}
/*
** Search for BGR values 0..255 (after net is unbiased) and 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 is 256*3 */
best = -1;
i = netindex[g]; /* index on g */
j = i - 1; /* start at netindex[g] and work outwards */
while ((i < netsize) || (j >= 0))
{
if (i < netsize)
{
p = network[i];
dist = p[1] - g; /* inx key */
if (dist >= bestd) i = netsize; /* stop iter */
else
{
i++;
if (dist < 0) dist = -dist;
a = p[0] - b;
if (a < 0) a = -a;
dist += a;
if (dist < bestd)
{
a = p[2] - r;
if (a < 0) a = -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;
a = p[0] - b;
if (a < 0) a = -a;
dist += a;
if (dist < bestd)
{
a = 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 to give byte values 0..255 and record position i to prepare
* for sort
* -----------------------------------------------------------------------------------
*/
var unbiasnet = function unbiasnet()/*void*/
{
var i/*int*/;
var j/*int*/;
for (i = 0; i < netsize; i++)
{
network[i][0] >>= netbiasshift;
network[i][1] >>= netbiasshift;
network[i][2] >>= netbiasshift;
network[i][3] = i; /* record colour no */
}
}
/*
* Move adjacent neurons by preputed 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 = i - rad;
if (lo < -1) lo = -1;
hi = i + rad;
if (hi > netsize) hi = netsize;
j = i + 1;
k = i - 1;
m = 1;
while ((j < hi) || (k > lo))
{
a = 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 mispilation
}
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 i towards biased (b,g,r) by 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 for biased BGR values ----------------------------
*/
var contest = function contest(b/*int*/, g/*int*/, r/*int*/)/*int*/
{
/* finds closest neuron (min dist) and updates freq */
/* finds best neuron (min dist-bias) and returns position */
/* for frequently chosen neurons, freq[i] is high and bias[i] is 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;
for (i = 0; i < netsize; i++)
{
n = network[i];
dist = n[0] - b;
if (dist < 0) dist = -dist;
a = n[1] - g;
if (a < 0) a = -a;
dist += a;
a = n[2] - r;
if (a < 0) a = -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;
}
NeuQuant.js works well when the image width and height are a multiple of 100:
300x300
Otherwise, there is obviously a bug:
299x300
(These were made with this web app.)
I'm 90% sure that the bug is in NeuQuant.js. I have made tests using it with jsgif and omggif, and both encoders have the same bug. It is only obvious with photographic images (quantize to 256 colors) when the image size is anything other than a multiple of 100.
If you understand neural networks, color quantization, and/or issues with porting AS3 to JS, please take a look. The original porter has abandoned the project, and it is so close to working!
Here is my code that implements it in a worker with OMGGIF:
importScripts('omggif.js', 'NeuQuant.js');
var rgba2rgb = function (data) {
var pixels = [];
var count = 0;
var len = data.length;
for ( 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;
for ( 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 with 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 to new palette
var k = 0;
for (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 all frames
for (var i = 0; i<framesLength; i++) {
addFrame( frames[i] );
self.postMessage({
type: "progress",
data: Math.round( (i+1)/framesLength*100 )
});
}
// Finish
var string = '';
for ( var i = 0, l = gif.end(); i < l; i ++ ) {
string += String.fromCharCode( buffer[ i ] );
}
self.postMessage({
type: "gif",
data: string,
frameCount: framesLength,
encodeTime: Math.round( (Date.now()-startTime)/10 ) / 100
});
};
And all of NeuQuant.js:
/*
* NeuQuant Neural-Net Quantization Algorithm
* ------------------------------------------
*
* Copyright (c) 1994 Anthony Dekker
*
* NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. See
* "Kohonen neural networks for optimal colour quantization" in "Network:
* Computation in Neural Systems" Vol. 5 (1994) pp 351-367. for a discussion of
* the algorithm.
*
* Any party obtaining a copy of these files from the author, directly or
* indirectly, is granted, free of charge, a full and unrestricted irrevocable,
* world-wide, paid up, royalty-free, nonexclusive right and license to deal in
* this software and documentation files (the "Software"), including without
* limitation the rights to use, copy, modify, merge, publish, distribute,
* sublicense, and/or sell copies of the Software, and to permit persons who
* receive copies from any such party to do so, with the only requirement being
* that this copyright notice remain intact.
*/
/*
* This class handles Neural-Net quantization algorithm
* @author Kevin Weiner (original Java version - [email protected])
* @author Thibault Imbert (AS3 version - bytearray)
* @version 0.1 AS3 implementation
*/
//import flash.utils.ByteArray;
NeuQuant = function()
{
var exports = {};
/*private_static*/ var netsize/*int*/ = 256; /* number of colours used */
/* four primes near 500 - assume no image has a length so large */
/* that it is divisible by all four 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 for input image */
/*
* Program Skeleton ---------------- [select samplefac in range 1..30] [read
* image from 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 for colour values */
/*private_static*/ var ncycles/*int*/ = 100; /* no. of learning cycles */
/* defs for freq and bias */
/*private_static*/ var intbiasshift/*int*/ = 16; /* bias for 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 for decreasing radius factor */
/*private_static*/ var initrad/*int*/ = (netsize >> 3); /*
* for 256 cols, radius
* starts
*/
/*private_static*/ var radiusbiasshift/*int*/ = 6; /* at 32.0 biased by 6 bits */
/*private_static*/ var radiusbias/*int*/ = (1 << radiusbiasshift);
/*private_static*/ var initradius/*int*/ = (initrad * radiusbias); /*
* and
* decreases
* by a
*/
/*private_static*/ var radiusdec/*int*/ = 30; /* factor of 1/30 each cycle */
/* defs for decreasing alpha factor */
/*private_static*/ var alphabiasshift/*int*/ = 10; /* alpha starts at 1.0 */
/*private_static*/ var initalpha/*int*/ = (1 << alphabiasshift);
/*private*/ var alphadec/*int*/ /* biased by 10 bits */
/* radbias and alpharadbias used for 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 and Global Variables --------------------------
*/
/*private*/ var thepicture/*ByteArray*//* the input image itself */
/*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*/; /* the network itself - [netsize][4] */
/*protected*/ var netindex/*Array*/ = new Array();
/* for network lookup - really 256 */
/*private*/ var bias/*Array*/ = new Array();
/* bias and freq arrays for 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);
for (i = 0; i < 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);
for (var i/*int*/ = 0; i < netsize; i++)
index[network[i][3]] = i;
var k/*int*/ = 0;
for (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 and building of netindex[0..255] (to do 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;
for (i = 0; i < netsize; i++)
{
p = network[i];
smallpos = i;
smallval = p[1]; /* index on g */
/* find smallest in i.size-1 */
for (j = i + 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) and 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 is now in position i */
if (smallval != previouscol)
{
netindex[previouscol] = (startpos + i) >> 1;
for (j = previouscol + 1; j < smallval; j++) netindex[j] = i;
previouscol = smallval;
startpos = i;
}
}
netindex[previouscol] = (startpos + maxnetpos) >> 1;
for (j = previouscol + 1; j < 256; j++) netindex[j] = maxnetpos; /* really 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;
for (i = 0; i < rad; i++) radpower[i] = alpha * (((rad * rad - i * 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;
}
}
i = 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;
for (j = 0; j < rad; j++) radpower[j] = alpha * (((rad * rad - j * j) * radbias) / (rad * rad));
}
}
}
/*
** Search for BGR values 0..255 (after net is unbiased) and 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 is 256*3 */
best = -1;
i = netindex[g]; /* index on g */
j = i - 1; /* start at netindex[g] and work outwards */
while ((i < netsize) || (j >= 0))
{
if (i < netsize)
{
p = network[i];
dist = p[1] - g; /* inx key */
if (dist >= bestd) i = netsize; /* stop iter */
else
{
i++;
if (dist < 0) dist = -dist;
a = p[0] - b;
if (a < 0) a = -a;
dist += a;
if (dist < bestd)
{
a = p[2] - r;
if (a < 0) a = -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;
a = p[0] - b;
if (a < 0) a = -a;
dist += a;
if (dist < bestd)
{
a = 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 to give byte values 0..255 and record position i to prepare
* for sort
* -----------------------------------------------------------------------------------
*/
var unbiasnet = function unbiasnet()/*void*/
{
var i/*int*/;
var j/*int*/;
for (i = 0; i < netsize; i++)
{
network[i][0] >>= netbiasshift;
network[i][1] >>= netbiasshift;
network[i][2] >>= netbiasshift;
network[i][3] = i; /* record colour no */
}
}
/*
* Move adjacent neurons by preputed 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 = i - rad;
if (lo < -1) lo = -1;
hi = i + rad;
if (hi > netsize) hi = netsize;
j = i + 1;
k = i - 1;
m = 1;
while ((j < hi) || (k > lo))
{
a = 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 mispilation
}
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 i towards biased (b,g,r) by 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 for biased BGR values ----------------------------
*/
var contest = function contest(b/*int*/, g/*int*/, r/*int*/)/*int*/
{
/* finds closest neuron (min dist) and updates freq */
/* finds best neuron (min dist-bias) and returns position */
/* for frequently chosen neurons, freq[i] is high and bias[i] is 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;
for (i = 0; i < netsize; i++)
{
n = network[i];
dist = n[0] - b;
if (dist < 0) dist = -dist;
a = n[1] - g;
if (a < 0) a = -a;
dist += a;
a = n[2] - r;
if (a < 0) a = -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;
}
- The original: members.ozemail..au/~dekker/NEUQUANT.HTML – forresto Commented May 7, 2013 at 12:09
- There might be a hack solution to construct a %100==0 pixel array for the color quantization and then cropping it again for the GIF encoding... – forresto Commented May 8, 2013 at 11:24
-
Where are the raw frames ing from? Are you sure that the stride is equal to
width*sizeof(pixel)? For example, if you've got a 32-bit RGBA frame with a stride that is required to be a multiple of 8 bytes, then a 299-pixel line would occupyround_up(299*4/8)*8==1200bytes. That is, each line would contain 4 bytes of padding. If that's the case, you'll have to make the quantizer take the padding into account. – Michael Commented May 10, 2013 at 14:21 - @Michael I'm getting the image data from an html canvas, and converting from canvas' RGBA to the RGB array that NeuQuant expects. Not sure if your point could be issue in the JS version, since the image data is just an array of integers. – forresto Commented May 11, 2013 at 11:09
- Ok. One easy way to eliminate the canvas and GIF encoder as the error sources would be to take your RGB data, generate a 332 palette (i.e. use bit-shifting to quantize each pixel to use 3 bits of red, 3 bits of green and 2 bits of blue, for a total of 256 colors maximum) and feed that to the GIF encoder. If it ends up looking the same for a 300-width image and a 299-width image then I'd say you've isolated NeuQuant as the problem source. – Michael Commented May 11, 2013 at 11:55
2 Answers
Reset to default 11 +100JavaScript code seems to ignore that C truncates the results of the operations with decimal numbers before assign them to integer variables. So, int i = 5 / 2; is 2 to C, but var i = 5 / 2; is 2.5 to JavaScript.
Said that, change this line:
delta = samplepixels / ncycles;
to:
delta = (samplepixels / ncycles) | 0;
This solves the issue, but it's not clear to me if this change solves all the possible integer conversion problems, or only the one exposed in the question.
Note that I have used the bitwise OR operator to truncate the result. This is a classic way to truncate a number in JavaScript, because bitwise operators treat their operands as integers of 32 bits.
It took me a few days to figure out this subtle bug. The problem is not limited to JavaScript implementations, the C/C++ and C# versions have it too. The bug is in the way pixels are sampled during the learning process. The code uses one of four prime numbers, 499, 491, 487 and 503. In case the image is 500x499, for example, it chooses 491, and pixels are sampled pretty uniformly, as follows (red dots are sampled pixels):
Good sampling:
Now, with a 500x500 image, 499 is chosen and the sampling is awfully bad:
Bad sampling:
I got rid of all the prime number nonsense and used a good old random number generator:
int step = ((float)rand() / (float)RAND_MAX) * lengthcount;
if( step >= lengthcount )
step = lengthcount - 1;
p = thepicture + step;
Works great with any image size!
本文标签： neural networkNeuQuantjs (JavaScript color quantization) hidden bug in JS conversionStack Overflow
版权声明：本文标题：neural network - NeuQuant.js (JavaScript color quantization) hidden bug in JS conversion - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741562020a2385504.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论