vendor: 12,906 bytes, lines 1-373
1/*! 2 * quantize.js Copyright 2008 Nick Rabinowitz. 3 * Licensed under the MIT license: http://www.opensource.org/licenses/mit-license.php 4 */ 5 6// fill out a couple protovis dependencies 7/*! 8 * Block below copied from Protovis: http://mbostock.github.com/protovis/ 9 * Copyright 2010 Stanford Visualization Group 10 * Licensed under the BSD License: http://www.opensource.org/licenses/bsd-license.php 11 */ 12if (!pv) { 13 var pv = { 14 map: function(array, f) { 15 var o = {}; 16 return f 17 ? array.map(function(d, i) { o.index = i; return f.call(o, d); }) 18 : array.slice(); 19 }, 20 naturalOrder: function(a, b) { 21 return (a < b) ? -1 : ((a > b) ? 1 : 0); 22 }, 23 sum: function(array, f) { 24 var o = {}; 25 return array.reduce(f 26 ? function(p, d, i) { o.index = i; return p + f.call(o, d); } 27 : function(p, d) { return p + d; }, 0); 28 }, 29 max: function(array, f) { 30 return Math.max.apply(null, f ? pv.map(array, f) : array); 31 } 32 } 33} 34 35/** 36 * Basic Javascript port of the MMCQ (modified median cut quantization) 37 * algorithm from the Leptonica library (http://www.leptonica.com/). 38 * Returns a color map you can use to map original pixels to the reduced 39 * palette. Still a work in progress. 40 * 41 * @author Nick Rabinowitz 42 * @example 43 44// array of pixels as [R,G,B] arrays 45var myPixels = [[190,197,190], [202,204,200], [207,214,210], [211,214,211], [205,207,207] 46 // etc 47 ]; 48var maxColors = 4; 49 50var cmap = MMCQ.quantize(myPixels, maxColors); 51var newPalette = cmap.palette(); 52var newPixels = myPixels.map(function(p) { 53 return cmap.map(p); 54}); 55 56 */ 57var MMCQ = (function() { 58 // private constants 59 var sigbits = 5, 60 rshift = 8 - sigbits, 61 maxIterations = 1000, 62 fractByPopulations = 0.75; 63 64 // get reduced-space color index for a pixel 65 function getColorIndex(r, g, b) { 66 return (r << (2 * sigbits)) + (g << sigbits) + b; 67 } 68 69 // Simple priority queue 70 function PQueue(comparator) { 71 var contents = [], 72 sorted = false; 73 74 function sort() { 75 contents.sort(comparator); 76 sorted = true; 77 } 78 79 return { 80 push: function(o) { 81 contents.push(o); 82 sorted = false; 83 }, 84 peek: function(index) { 85 if (!sorted) sort(); 86 if (index===undefined) index = contents.length - 1; 87 return contents[index]; 88 }, 89 pop: function() { 90 if (!sorted) sort(); 91 return contents.pop(); 92 }, 93 size: function() { 94 return contents.length; 95 }, 96 map: function(f) { 97 return contents.map(f); 98 }, 99 debug: function() { 100 if (!sorted) sort(); 101 return contents; 102 } 103 }; 104 } 105 106 // 3d color space box 107 function VBox(r1, r2, g1, g2, b1, b2, histo) { 108 var vbox = this; 109 vbox.r1 = r1; 110 vbox.r2 = r2; 111 vbox.g1 = g1; 112 vbox.g2 = g2; 113 vbox.b1 = b1; 114 vbox.b2 = b2; 115 vbox.histo = histo; 116 } 117 VBox.prototype = { 118 volume: function(force) { 119 var vbox = this; 120 if (!vbox._volume || force) { 121 vbox._volume = ((vbox.r2 - vbox.r1 + 1) * (vbox.g2 - vbox.g1 + 1) * (vbox.b2 - vbox.b1 + 1)); 122 } 123 return vbox._volume; 124 }, 125 count: function(force) { 126 var vbox = this, 127 histo = vbox.histo; 128 if (!vbox._count_set || force) { 129 var npix = 0, 130 i, j, k; 131 for (i = vbox.r1; i <= vbox.r2; i++) { 132 for (j = vbox.g1; j <= vbox.g2; j++) { 133 for (k = vbox.b1; k <= vbox.b2; k++) { 134 index = getColorIndex(i,j,k); 135 npix += (histo[index] || 0); 136 } 137 } 138 } 139 vbox._count = npix; 140 vbox._count_set = true; 141 } 142 return vbox._count; 143 }, 144 copy: function() { 145 var vbox = this; 146 return new VBox(vbox.r1, vbox.r2, vbox.g1, vbox.g2, vbox.b1, vbox.b2, vbox.histo); 147 }, 148 avg: function(force) { 149 var vbox = this, 150 histo = vbox.histo; 151 if (!vbox._avg || force) { 152 var ntot = 0, 153 mult = 1 << (8 - sigbits), 154 rsum = 0, 155 gsum = 0, 156 bsum = 0, 157 hval, 158 i, j, k, histoindex; 159 for (i = vbox.r1; i <= vbox.r2; i++) { 160 for (j = vbox.g1; j <= vbox.g2; j++) { 161 for (k = vbox.b1; k <= vbox.b2; k++) { 162 histoindex = getColorIndex(i,j,k); 163 hval = histo[histoindex] || 0; 164 ntot += hval; 165 rsum += (hval * (i + 0.5) * mult); 166 gsum += (hval * (j + 0.5) * mult); 167 bsum += (hval * (k + 0.5) * mult); 168 } 169 } 170 } 171 if (ntot) { 172 vbox._avg = [~~(rsum/ntot), ~~(gsum/ntot), ~~(bsum/ntot)]; 173 } else { 174// console.log('empty box'); 175 vbox._avg = [ 176 ~~(mult * (vbox.r1 + vbox.r2 + 1) / 2), 177 ~~(mult * (vbox.g1 + vbox.g2 + 1) / 2), 178 ~~(mult * (vbox.b1 + vbox.b2 + 1) / 2) 179 ]; 180 } 181 } 182 return vbox._avg; 183 }, 184 contains: function(pixel) { 185 var vbox = this, 186 rval = pixel[0] >> rshift; 187 gval = pixel[1] >> rshift; 188 bval = pixel[2] >> rshift; 189 return (rval >= vbox.r1 && rval <= vbox.r2 && 190 gval >= vbox.g1 && rval <= vbox.g2 && 191 bval >= vbox.b1 && rval <= vbox.b2); 192 } 193 }; 194 195 // Color map 196 function CMap() { 197 this.vboxes = new PQueue(function(a,b) { 198 return pv.naturalOrder( 199 a.vbox.count()*a.vbox.volume(), 200 b.vbox.count()*b.vbox.volume() 201 ) 202 });; 203 } 204 CMap.prototype = { 205 push: function(vbox) { 206 this.vboxes.push({ 207 vbox: vbox, 208 color: vbox.avg() 209 }); 210 }, 211 palette: function() { 212 return this.vboxes.map(function(vb) { return vb.color }); 213 }, 214 size: function() { 215 return this.vboxes.size(); 216 }, 217 map: function(color) { 218 var vboxes = this.vboxes; 219 for (var i=0; i<vboxes.size(); i++) { 220 if (vboxes.peek(i).vbox.contains(color)) { 221 return vboxes.peek(i).color; 222 } 223 } 224 return this.nearest(color); 225 }, 226 nearest: function(color) { 227 var vboxes = this.vboxes, 228 d1, d2, pColor; 229 for (var i=0; i<vboxes.size(); i++) { 230 d2 = Math.sqrt( 231 Math.pow(color[0] - vboxes.peek(i).color[0], 2) + 232 Math.pow(color[1] - vboxes.peek(i).color[1], 2) + 233 Math.pow(color[1] - vboxes.peek(i).color[1], 2) 234 ); 235 if (d2 < d1 || d1 === undefined) { 236 d1 = d2; 237 pColor = vboxes.peek(i).color; 238 } 239 } 240 return pColor; 241 }, 242 forcebw: function() { 243 // XXX: won't work yet 244 var vboxes = this.vboxes; 245 vboxes.sort(function(a,b) { return pv.naturalOrder(pv.sum(a.color), pv.sum(b.color) )}); 246 247 // force darkest color to black if everything < 5 248 var lowest = vboxes[0].color; 249 if (lowest[0] < 5 && lowest[1] < 5 && lowest[2] < 5) 250 vboxes[0].color = [0,0,0]; 251 252 // force lightest color to white if everything > 251 253 var idx = vboxes.length-1, 254 highest = vboxes[idx].color; 255 if (highest[0] > 251 && highest[1] > 251 && highest[2] > 251) 256 vboxes[idx].color = [255,255,255]; 257 } 258 }; 259 260 // histo (1-d array, giving the number of pixels in 261 // each quantized region of color space), or null on error 262 function getHisto(pixels) { 263 var histosize = 1 << (3 * sigbits), 264 histo = new Array(histosize), 265 index, rval, gval, bval; 266 pixels.forEach(function(pixel) { 267 rval = pixel[0] >> rshift; 268 gval = pixel[1] >> rshift; 269 bval = pixel[2] >> rshift; 270 index = getColorIndex(rval, gval, bval); 271 histo[index] = (histo[index] || 0) + 1; 272 }); 273 return histo; 274 } 275 276 function vboxFromPixels(pixels, histo) { 277 var rmin=1000000, rmax=0, 278 gmin=1000000, gmax=0, 279 bmin=1000000, bmax=0, 280 rval, gval, bval; 281 // find min/max 282 pixels.forEach(function(pixel) { 283 rval = pixel[0] >> rshift; 284 gval = pixel[1] >> rshift; 285 bval = pixel[2] >> rshift; 286 if (rval < rmin) rmin = rval; 287 else if (rval > rmax) rmax = rval; 288 if (gval < gmin) gmin = gval; 289 else if (gval > gmax) gmax = gval; 290 if (bval < bmin) bmin = bval; 291 else if (bval > bmax) bmax = bval; 292 }); 293 return new VBox(rmin, rmax, gmin, gmax, bmin, bmax, histo); 294 } 295 296 function medianCutApply(histo, vbox) { 297 if (!vbox.count()) return; 298 299 var rw = vbox.r2 - vbox.r1 + 1, 300 gw = vbox.g2 - vbox.g1 + 1, 301 bw = vbox.b2 - vbox.b1 + 1, 302 maxw = pv.max([rw, gw, bw]); 303 // only one pixel, no split 304 if (vbox.count() == 1) { 305 return [vbox.copy()] 306 } 307 /* Find the partial sum arrays along the selected axis. */ 308 var total = 0, 309 partialsum = [], 310 lookaheadsum = [], 311 i, j, k, sum, index; 312 if (maxw == rw) { 313 for (i = vbox.r1; i <= vbox.r2; i++) { 314 sum = 0; 315 for (j = vbox.g1; j <= vbox.g2; j++) { 316 for (k = vbox.b1; k <= vbox.b2; k++) { 317 index = getColorIndex(i,j,k); 318 sum += (histo[index] || 0); 319 } 320 } 321 total += sum; 322 partialsum[i] = total; 323 } 324 } 325 else if (maxw == gw) { 326 for (i = vbox.g1; i <= vbox.g2; i++) { 327 sum = 0; 328 for (j = vbox.r1; j <= vbox.r2; j++) { 329 for (k = vbox.b1; k <= vbox.b2; k++) { 330 index = getColorIndex(j,i,k); 331 sum += (histo[index] || 0); 332 } 333 } 334 total += sum; 335 partialsum[i] = total; 336 } 337 } 338 else { /* maxw == bw */ 339 for (i = vbox.b1; i <= vbox.b2; i++) { 340 sum = 0; 341 for (j = vbox.r1; j <= vbox.r2; j++) { 342 for (k = vbox.g1; k <= vbox.g2; k++) { 343 index = getColorIndex(j,k,i); 344 sum += (histo[index] || 0); 345 } 346 } 347 total += sum; 348 partialsum[i] = total; 349 } 350 } 351 partialsum.forEach(function(d,i) { 352 lookaheadsum[i] = total-d 353 }); 354 function doCut(color) { 355 var dim1 = color + '1', 356 dim2 = color + '2', 357 left, right, vbox1, vbox2, d2, count2=0; 358 for (i = vbox[dim1]; i <= vbox[dim2]; i++) { 359 if (partialsum[i] > total / 2) { 360 vbox1 = vbox.copy(); 361 vbox2 = vbox.copy(); 362 left = i - vbox[dim1]; 363 right = vbox[dim2] - i; 364 if (left <= right) 365 d2 = Math.min(vbox[dim2] - 1, ~~(i + right / 2)); 366 else d2 = Math.max(vbox[dim1], ~~(i - 1 - left / 2)); 367 // avoid 0-count boxes 368 while (!partialsum[d2]) d2++; 369 count2 = lookaheadsum[d2]; 370 while (!count2 && partialsum[d2-1]) count2 = lookaheadsum[--d2]; 371 // set dimensions 372 vbox1[dim2] = d2; 373 vbox2[dim1] = vbox1[dim2] + 1;
374// console.log('vbox counts:', vbox.count(), vbox1.count(), vbox2.count()); 375 return [vbox1, vbox2]; 376 } 377 } 378 379 } 380 // determine the cut planes 381 return maxw == rw ? doCut('r') : 382 maxw == gw ? doCut('g') : 383 doCut('b'); 384 } 385 386 function quantize(pixels, maxcolors) { 387 // short-circuit 388 if (!pixels.length || maxcolors < 2 || maxcolors > 256) { 389// console.log('wrong number of maxcolors'); 390 return false; 391 } 392 393 // XXX: check color content and convert to grayscale if insufficient 394 395 var histo = getHisto(pixels), 396 histosize = 1 << (3 * sigbits); 397 398 // check that we aren't below maxcolors already 399 var nColors = 0; 400 histo.forEach(function() { nColors++ }); 401 if (nColors <= maxcolors) { 402 // XXX: generate the new colors from the histo and return 403 } 404 405 // get the beginning vbox from the colors 406 var vbox = vboxFromPixels(pixels, histo), 407 pq = new PQueue(function(a,b) { return pv.naturalOrder(a.count(), b.count()) }); 408 pq.push(vbox); 409 410 // inner function to do the iteration 411 function iter(lh, target) { 412 var ncolors = 1, 413 niters = 0, 414 vbox; 415 while (niters < maxIterations) { 416 vbox = lh.pop(); 417 if (!vbox.count()) { /* just put it back */ 418 lh.push(vbox); 419 niters++; 420 continue; 421 } 422 // do the cut 423 var vboxes = medianCutApply(histo, vbox), 424 vbox1 = vboxes[0], 425 vbox2 = vboxes[1]; 426 427 if (!vbox1) { 428// console.log("vbox1 not defined; shouldn't happen!"); 429 return; 430 } 431 lh.push(vbox1); 432 if (vbox2) { /* vbox2 can be null */ 433 lh.push(vbox2); 434 ncolors++; 435 } 436 if (ncolors >= target) return; 437 if (niters++ > maxIterations) { 438// console.log("infinite loop; perhaps too few pixels!"); 439 return; 440 } 441 } 442 } 443 444 // first set of colors, sorted by population 445 iter(pq, fractByPopulations * maxcolors); 446 // console.log(pq.size(), pq.debug().length, pq.debug().slice()); 447 448 // Re-sort by the product of pixel occupancy times the size in color space. 449 var pq2 = new PQueue(function(a,b) { 450 return pv.naturalOrder(a.count()*a.volume(), b.count()*b.volume()) 451 }); 452 while (pq.size()) { 453 pq2.push(pq.pop()); 454 } 455 456 // next set - generate the median cuts using the (npix * vol) sorting. 457 iter(pq2, maxcolors - pq2.size()); 458 459 // calculate the actual colors 460 var cmap = new CMap(); 461 while (pq2.size()) { 462 cmap.push(pq2.pop()); 463 } 464 465 return cmap; 466 } 467 468 return { 469 quantize: quantize 470 } 471})();
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.