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