| OLD | NEW |
|---|
| (Empty) |
| 1 /* NeuQuant Neural-Net Quantization Algorithm | |
| 2 * ------------------------------------------ | |
| 3 * | |
| 4 * Copyright (c) 1994 Anthony Dekker | |
| 5 * | |
| 6 * NEUQUANT Neural-Net quantization algorithm by Anthony Dekker, 1994. | |
| 7 * See "Kohonen neural networks for optimal colour quantization" | |
| 8 * in "Network: Computation in Neural Systems" Vol. 5 (1994) pp 351-367. | |
| 9 * for a discussion of the algorithm. | |
| 10 * See also http://members.ozemail.com.au/~dekker/NEUQUANT.HTML | |
| 11 * | |
| 12 * Any party obtaining a copy of these files from the author, directly or | |
| 13 * indirectly, is granted, free of charge, a full and unrestricted irrevocable, | |
| 14 * world-wide, paid up, royalty-free, nonexclusive right and license to deal | |
| 15 * in this software and documentation files (the "Software"), including without | |
| 16 * limitation the rights to use, copy, modify, merge, publish, distribute, subli
cense, | |
| 17 * and/or sell copies of the Software, and to permit persons who receive | |
| 18 * copies from any such party to do so, with the only requirement being | |
| 19 * that this copyright notice remain intact. | |
| 20 * | |
| 21 * (JavaScript port 2012 by Johan Nordberg) | |
| 22 */ | |
| 23 | |
| 24 var ncycles = 100; // number of learning cycles | |
| 25 var netsize = 256; // number of colors used | |
| 26 var maxnetpos = netsize - 1; | |
| 27 | |
| 28 // defs for freq and bias | |
| 29 var netbiasshift = 4; // bias for colour values | |
| 30 var intbiasshift = 16; // bias for fractions | |
| 31 var intbias = (1 << intbiasshift); | |
| 32 var gammashift = 10; | |
| 33 var gamma = (1 << gammashift); | |
| 34 var betashift = 10; | |
| 35 var beta = (intbias >> betashift); /* beta = 1/1024 */ | |
| 36 var betagamma = (intbias << (gammashift - betashift)); | |
| 37 | |
| 38 // defs for decreasing radius factor | |
| 39 var initrad = (netsize >> 3); // for 256 cols, radius starts | |
| 40 var radiusbiasshift = 6; // at 32.0 biased by 6 bits | |
| 41 var radiusbias = (1 << radiusbiasshift); | |
| 42 var initradius = (initrad * radiusbias); //and decreases by a | |
| 43 var radiusdec = 30; // factor of 1/30 each cycle | |
| 44 | |
| 45 // defs for decreasing alpha factor | |
| 46 var alphabiasshift = 10; // alpha starts at 1.0 | |
| 47 var initalpha = (1 << alphabiasshift); | |
| 48 var alphadec; // biased by 10 bits | |
| 49 | |
| 50 /* radbias and alpharadbias used for radpower calculation */ | |
| 51 var radbiasshift = 8; | |
| 52 var radbias = (1 << radbiasshift); | |
| 53 var alpharadbshift = (alphabiasshift + radbiasshift); | |
| 54 var alpharadbias = (1 << alpharadbshift); | |
| 55 | |
| 56 // four primes near 500 - assume no image has a length so large that it is | |
| 57 // divisible by all four primes | |
| 58 var prime1 = 499; | |
| 59 var prime2 = 491; | |
| 60 var prime3 = 487; | |
| 61 var prime4 = 503; | |
| 62 var minpicturebytes = (3 * prime4); | |
| 63 | |
| 64 /* | |
| 65 Constructor: NeuQuant | |
| 66 | |
| 67 Arguments: | |
| 68 | |
| 69 pixels - array of pixels in RGB format | |
| 70 samplefac - sampling factor 1 to 30 where lower is better quality | |
| 71 | |
| 72 > | |
| 73 > pixels = [r, g, b, r, g, b, r, g, b, ..] | |
| 74 > | |
| 75 */ | |
| 76 function NeuQuant(pixels, samplefac) { | |
| 77 var network; // int[netsize][4] | |
| 78 var netindex; // for network lookup - really 256 | |
| 79 | |
| 80 // bias and freq arrays for learning | |
| 81 var bias; | |
| 82 var freq; | |
| 83 var radpower; | |
| 84 | |
| 85 /* | |
| 86 Private Method: init | |
| 87 | |
| 88 sets up arrays | |
| 89 */ | |
| 90 function init() { | |
| 91 network = []; | |
| 92 netindex = new Int32Array(256); | |
| 93 bias = new Int32Array(netsize); | |
| 94 freq = new Int32Array(netsize); | |
| 95 radpower = new Int32Array(netsize >> 3); | |
| 96 | |
| 97 var i, v; | |
| 98 for (i = 0; i < netsize; i++) { | |
| 99 v = (i << (netbiasshift + 8)) / netsize; | |
| 100 network[i] = new Float64Array([v, v, v, 0]); | |
| 101 //network[i] = [v, v, v, 0] | |
| 102 freq[i] = intbias / netsize; | |
| 103 bias[i] = 0; | |
| 104 } | |
| 105 } | |
| 106 | |
| 107 /* | |
| 108 Private Method: unbiasnet | |
| 109 | |
| 110 unbiases network to give byte values 0..255 and record position i to prepare
for sort | |
| 111 */ | |
| 112 function unbiasnet() { | |
| 113 for (var i = 0; i < netsize; i++) { | |
| 114 network[i][0] >>= netbiasshift; | |
| 115 network[i][1] >>= netbiasshift; | |
| 116 network[i][2] >>= netbiasshift; | |
| 117 network[i][3] = i; // record color number | |
| 118 } | |
| 119 } | |
| 120 | |
| 121 /* | |
| 122 Private Method: altersingle | |
| 123 | |
| 124 moves neuron *i* towards biased (b,g,r) by factor *alpha* | |
| 125 */ | |
| 126 function altersingle(alpha, i, b, g, r) { | |
| 127 network[i][0] -= (alpha * (network[i][0] - b)) / initalpha; | |
| 128 network[i][1] -= (alpha * (network[i][1] - g)) / initalpha; | |
| 129 network[i][2] -= (alpha * (network[i][2] - r)) / initalpha; | |
| 130 } | |
| 131 | |
| 132 /* | |
| 133 Private Method: alterneigh | |
| 134 | |
| 135 moves neurons in *radius* around index *i* towards biased (b,g,r) by factor
*alpha* | |
| 136 */ | |
| 137 function alterneigh(radius, i, b, g, r) { | |
| 138 var lo = Math.abs(i - radius); | |
| 139 var hi = Math.min(i + radius, netsize); | |
| 140 | |
| 141 var j = i + 1; | |
| 142 var k = i - 1; | |
| 143 var m = 1; | |
| 144 | |
| 145 var p, a; | |
| 146 while ((j < hi) || (k > lo)) { | |
| 147 a = radpower[m++]; | |
| 148 | |
| 149 if (j < hi) { | |
| 150 p = network[j++]; | |
| 151 p[0] -= (a * (p[0] - b)) / alpharadbias; | |
| 152 p[1] -= (a * (p[1] - g)) / alpharadbias; | |
| 153 p[2] -= (a * (p[2] - r)) / alpharadbias; | |
| 154 } | |
| 155 | |
| 156 if (k > lo) { | |
| 157 p = network[k--]; | |
| 158 p[0] -= (a * (p[0] - b)) / alpharadbias; | |
| 159 p[1] -= (a * (p[1] - g)) / alpharadbias; | |
| 160 p[2] -= (a * (p[2] - r)) / alpharadbias; | |
| 161 } | |
| 162 } | |
| 163 } | |
| 164 | |
| 165 /* | |
| 166 Private Method: contest | |
| 167 | |
| 168 searches for biased BGR values | |
| 169 */ | |
| 170 function contest(b, g, r) { | |
| 171 /* | |
| 172 finds closest neuron (min dist) and updates freq | |
| 173 finds best neuron (min dist-bias) and returns position | |
| 174 for frequently chosen neurons, freq[i] is high and bias[i] is negative | |
| 175 bias[i] = gamma * ((1 / netsize) - freq[i]) | |
| 176 */ | |
| 177 | |
| 178 var bestd = ~(1 << 31); | |
| 179 var bestbiasd = bestd; | |
| 180 var bestpos = -1; | |
| 181 var bestbiaspos = bestpos; | |
| 182 | |
| 183 var i, n, dist, biasdist, betafreq; | |
| 184 for (i = 0; i < netsize; i++) { | |
| 185 n = network[i]; | |
| 186 | |
| 187 dist = Math.abs(n[0] - b) + Math.abs(n[1] - g) + Math.abs(n[2] - r); | |
| 188 if (dist < bestd) { | |
| 189 bestd = dist; | |
| 190 bestpos = i; | |
| 191 } | |
| 192 | |
| 193 biasdist = dist - ((bias[i]) >> (intbiasshift - netbiasshift)); | |
| 194 if (biasdist < bestbiasd) { | |
| 195 bestbiasd = biasdist; | |
| 196 bestbiaspos = i; | |
| 197 } | |
| 198 | |
| 199 betafreq = (freq[i] >> betashift); | |
| 200 freq[i] -= betafreq; | |
| 201 bias[i] += (betafreq << gammashift); | |
| 202 } | |
| 203 | |
| 204 freq[bestpos] += beta; | |
| 205 bias[bestpos] -= betagamma; | |
| 206 | |
| 207 return bestbiaspos; | |
| 208 } | |
| 209 | |
| 210 /* | |
| 211 Private Method: inxbuild | |
| 212 | |
| 213 sorts network and builds netindex[0..255] | |
| 214 */ | |
| 215 function inxbuild() { | |
| 216 var i, j, p, q, smallpos, smallval, previouscol = 0, startpos = 0; | |
| 217 for (i = 0; i < netsize; i++) { | |
| 218 p = network[i]; | |
| 219 smallpos = i; | |
| 220 smallval = p[1]; // index on g | |
| 221 // find smallest in i..netsize-1 | |
| 222 for (j = i + 1; j < netsize; j++) { | |
| 223 q = network[j]; | |
| 224 if (q[1] < smallval) { // index on g | |
| 225 smallpos = j; | |
| 226 smallval = q[1]; // index on g | |
| 227 } | |
| 228 } | |
| 229 q = network[smallpos]; | |
| 230 // swap p (i) and q (smallpos) entries | |
| 231 if (i != smallpos) { | |
| 232 j = q[0]; q[0] = p[0]; p[0] = j; | |
| 233 j = q[1]; q[1] = p[1]; p[1] = j; | |
| 234 j = q[2]; q[2] = p[2]; p[2] = j; | |
| 235 j = q[3]; q[3] = p[3]; p[3] = j; | |
| 236 } | |
| 237 // smallval entry is now in position i | |
| 238 | |
| 239 if (smallval != previouscol) { | |
| 240 netindex[previouscol] = (startpos + i) >> 1; | |
| 241 for (j = previouscol + 1; j < smallval; j++) | |
| 242 netindex[j] = i; | |
| 243 previouscol = smallval; | |
| 244 startpos = i; | |
| 245 } | |
| 246 } | |
| 247 netindex[previouscol] = (startpos + maxnetpos) >> 1; | |
| 248 for (j = previouscol + 1; j < 256; j++) | |
| 249 netindex[j] = maxnetpos; // really 256 | |
| 250 } | |
| 251 | |
| 252 /* | |
| 253 Private Method: inxsearch | |
| 254 | |
| 255 searches for BGR values 0..255 and returns a color index | |
| 256 */ | |
| 257 function inxsearch(b, g, r) { | |
| 258 var a, p, dist; | |
| 259 | |
| 260 var bestd = 1000; // biggest possible dist is 256*3 | |
| 261 var best = -1; | |
| 262 | |
| 263 var i = netindex[g]; // index on g | |
| 264 var j = i - 1; // start at netindex[g] and work outwards | |
| 265 | |
| 266 while ((i < netsize) || (j >= 0)) { | |
| 267 if (i < netsize) { | |
| 268 p = network[i]; | |
| 269 dist = p[1] - g; // inx key | |
| 270 if (dist >= bestd) i = netsize; // stop iter | |
| 271 else { | |
| 272 i++; | |
| 273 if (dist < 0) dist = -dist; | |
| 274 a = p[0] - b; if (a < 0) a = -a; | |
| 275 dist += a; | |
| 276 if (dist < bestd) { | |
| 277 a = p[2] - r; if (a < 0) a = -a; | |
| 278 dist += a; | |
| 279 if (dist < bestd) { | |
| 280 bestd = dist; | |
| 281 best = p[3]; | |
| 282 } | |
| 283 } | |
| 284 } | |
| 285 } | |
| 286 if (j >= 0) { | |
| 287 p = network[j]; | |
| 288 dist = g - p[1]; // inx key - reverse dif | |
| 289 if (dist >= bestd) j = -1; // stop iter | |
| 290 else { | |
| 291 j--; | |
| 292 if (dist < 0) dist = -dist; | |
| 293 a = p[0] - b; if (a < 0) a = -a; | |
| 294 dist += a; | |
| 295 if (dist < bestd) { | |
| 296 a = p[2] - r; if (a < 0) a = -a; | |
| 297 dist += a; | |
| 298 if (dist < bestd) { | |
| 299 bestd = dist; | |
| 300 best = p[3]; | |
| 301 } | |
| 302 } | |
| 303 } | |
| 304 } | |
| 305 } | |
| 306 | |
| 307 return best; | |
| 308 } | |
| 309 | |
| 310 /* | |
| 311 Private Method: learn | |
| 312 | |
| 313 "Main Learning Loop" | |
| 314 */ | |
| 315 function learn() { | |
| 316 var i; | |
| 317 | |
| 318 var lengthcount = pixels.length; | |
| 319 var alphadec = 30 + ((samplefac - 1) / 3); | |
| 320 var samplepixels = lengthcount / (3 * samplefac); | |
| 321 var delta = ~~(samplepixels / ncycles); | |
| 322 var alpha = initalpha; | |
| 323 var radius = initradius; | |
| 324 | |
| 325 var rad = radius >> radiusbiasshift; | |
| 326 | |
| 327 if (rad <= 1) rad = 0; | |
| 328 for (i = 0; i < rad; i++) | |
| 329 radpower[i] = alpha * (((rad * rad - i * i) * radbias) / (rad * rad)); | |
| 330 | |
| 331 var step; | |
| 332 if (lengthcount < minpicturebytes) { | |
| 333 samplefac = 1; | |
| 334 step = 3; | |
| 335 } else if ((lengthcount % prime1) !== 0) { | |
| 336 step = 3 * prime1; | |
| 337 } else if ((lengthcount % prime2) !== 0) { | |
| 338 step = 3 * prime2; | |
| 339 } else if ((lengthcount % prime3) !== 0) { | |
| 340 step = 3 * prime3; | |
| 341 } else { | |
| 342 step = 3 * prime4; | |
| 343 } | |
| 344 | |
| 345 var b, g, r, j; | |
| 346 var pix = 0; // current pixel | |
| 347 | |
| 348 i = 0; | |
| 349 while (i < samplepixels) { | |
| 350 b = (pixels[pix] & 0xff) << netbiasshift; | |
| 351 g = (pixels[pix + 1] & 0xff) << netbiasshift; | |
| 352 r = (pixels[pix + 2] & 0xff) << netbiasshift; | |
| 353 | |
| 354 j = contest(b, g, r); | |
| 355 | |
| 356 altersingle(alpha, j, b, g, r); | |
| 357 if (rad !== 0) alterneigh(rad, j, b, g, r); // alter neighbours | |
| 358 | |
| 359 pix += step; | |
| 360 if (pix >= lengthcount) pix -= lengthcount; | |
| 361 | |
| 362 i++; | |
| 363 | |
| 364 if (delta === 0) delta = 1; | |
| 365 if (i % delta === 0) { | |
| 366 alpha -= alpha / alphadec; | |
| 367 radius -= radius / radiusdec; | |
| 368 rad = radius >> radiusbiasshift; | |
| 369 | |
| 370 if (rad <= 1) rad = 0; | |
| 371 for (j = 0; j < rad; j++) | |
| 372 radpower[j] = alpha * (((rad * rad - j * j) * radbias) / (rad * rad)); | |
| 373 } | |
| 374 } | |
| 375 } | |
| 376 | |
| 377 /* | |
| 378 Method: buildColormap | |
| 379 | |
| 380 1. initializes network | |
| 381 2. trains it | |
| 382 3. removes misconceptions | |
| 383 4. builds colorindex | |
| 384 */ | |
| 385 function buildColormap() { | |
| 386 init(); | |
| 387 learn(); | |
| 388 unbiasnet(); | |
| 389 inxbuild(); | |
| 390 } | |
| 391 this.buildColormap = buildColormap; | |
| 392 | |
| 393 /* | |
| 394 Method: getColormap | |
| 395 | |
| 396 builds colormap from the index | |
| 397 | |
| 398 returns array in the format: | |
| 399 | |
| 400 > | |
| 401 > [r, g, b, r, g, b, r, g, b, ..] | |
| 402 > | |
| 403 */ | |
| 404 function getColormap() { | |
| 405 var map = []; | |
| 406 var index = []; | |
| 407 | |
| 408 for (var i = 0; i < netsize; i++) | |
| 409 index[network[i][3]] = i; | |
| 410 | |
| 411 var k = 0; | |
| 412 for (var l = 0; l < netsize; l++) { | |
| 413 var j = index[l]; | |
| 414 map[k++] = (network[j][0]); | |
| 415 map[k++] = (network[j][1]); | |
| 416 map[k++] = (network[j][2]); | |
| 417 } | |
| 418 return map; | |
| 419 } | |
| 420 this.getColormap = getColormap; | |
| 421 | |
| 422 /* | |
| 423 Method: lookupRGB | |
| 424 | |
| 425 looks for the closest *r*, *g*, *b* color in the map and | |
| 426 returns its index | |
| 427 */ | |
| 428 this.lookupRGB = inxsearch; | |
| 429 } | |
| 430 | |
| 431 module.exports = NeuQuant; | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 786953007:
npm_modules: Fork bower_components into Polymer 0.4.0 and 0.5.0 versions (Closed)
Base URL: https://chromium.googlesource.com/infra/third_party/npm_modules.git@master