Fixed the two issues reported by leeoniya and by iOSBrett * green is being used again here instead of blue. (line 233) * incorrectly used rval 3 times (line 189)
/*! | |
* quantize.js Copyright 2008 Nick Rabinowitz. | |
* Licensed under the MIT license: http://www.opensource.org/licenses/mit-license.php | |
*/ | |
// fill out a couple protovis dependencies | |
/*! | |
* Block below copied from Protovis: http://mbostock.github.com/protovis/ | |
* Copyright 2010 Stanford Visualization Group | |
* Licensed under the BSD License: http://www.opensource.org/licenses/bsd-license.php | |
*/ | |
if (!pv) { | |
var pv = { | |
map: function(array, f) { | |
var o = {}; | |
return f | |
? array.map(function(d, i) { o.index = i; return f.call(o, d); }) | |
: array.slice(); | |
}, | |
naturalOrder: function(a, b) { | |
return (a < b) ? -1 : ((a > b) ? 1 : 0); | |
}, | |
sum: function(array, f) { | |
var o = {}; | |
return array.reduce(f | |
? function(p, d, i) { o.index = i; return p + f.call(o, d); } | |
: function(p, d) { return p + d; }, 0); | |
}, | |
max: function(array, f) { | |
return Math.max.apply(null, f ? pv.map(array, f) : array); | |
} | |
} | |
} | |
/** | |
* Basic Javascript port of the MMCQ (modified median cut quantization) | |
* algorithm from the Leptonica library (http://www.leptonica.com/). | |
* Returns a color map you can use to map original pixels to the reduced | |
* palette. Still a work in progress. | |
* | |
* @author Nick Rabinowitz | |
* @example | |
// array of pixels as [R,G,B] arrays | |
var myPixels = [[190,197,190], [202,204,200], [207,214,210], [211,214,211], [205,207,207] | |
// etc | |
]; | |
var maxColors = 4; | |
var cmap = MMCQ.quantize(myPixels, maxColors); | |
var newPalette = cmap.palette(); | |
var newPixels = myPixels.map(function(p) { | |
return cmap.map(p); | |
}); | |
*/ | |
var MMCQ = (function() { | |
// private constants | |
var sigbits = 5, | |
rshift = 8 - sigbits, | |
maxIterations = 1000, | |
fractByPopulations = 0.75; | |
// get reduced-space color index for a pixel | |
function getColorIndex(r, g, b) { | |
return (r << (2 * sigbits)) + (g << sigbits) + b; | |
} | |
// Simple priority queue | |
function PQueue(comparator) { | |
var contents = [], | |
sorted = false; | |
function sort() { | |
contents.sort(comparator); | |
sorted = true; | |
} | |
return { | |
push: function(o) { | |
contents.push(o); | |
sorted = false; | |
}, | |
peek: function(index) { | |
if (!sorted) sort(); | |
if (index===undefined) index = contents.length - 1; | |
return contents[index]; | |
}, | |
pop: function() { | |
if (!sorted) sort(); | |
return contents.pop(); | |
}, | |
size: function() { | |
return contents.length; | |
}, | |
map: function(f) { | |
return contents.map(f); | |
}, | |
debug: function() { | |
if (!sorted) sort(); | |
return contents; | |
} | |
}; | |
} | |
// 3d color space box | |
function VBox(r1, r2, g1, g2, b1, b2, histo) { | |
var vbox = this; | |
vbox.r1 = r1; | |
vbox.r2 = r2; | |
vbox.g1 = g1; | |
vbox.g2 = g2; | |
vbox.b1 = b1; | |
vbox.b2 = b2; | |
vbox.histo = histo; | |
} | |
VBox.prototype = { | |
volume: function(force) { | |
var vbox = this; | |
if (!vbox._volume || force) { | |
vbox._volume = ((vbox.r2 - vbox.r1 + 1) * (vbox.g2 - vbox.g1 + 1) * (vbox.b2 - vbox.b1 + 1)); | |
} | |
return vbox._volume; | |
}, | |
count: function(force) { | |
var vbox = this, | |
histo = vbox.histo; | |
if (!vbox._count_set || force) { | |
var npix = 0, | |
i, j, k; | |
for (i = vbox.r1; i <= vbox.r2; i++) { | |
for (j = vbox.g1; j <= vbox.g2; j++) { | |
for (k = vbox.b1; k <= vbox.b2; k++) { | |
index = getColorIndex(i,j,k); | |
npix += (histo[index] || 0); | |
} | |
} | |
} | |
vbox._count = npix; | |
vbox._count_set = true; | |
} | |
return vbox._count; | |
}, | |
copy: function() { | |
var vbox = this; | |
return new VBox(vbox.r1, vbox.r2, vbox.g1, vbox.g2, vbox.b1, vbox.b2, vbox.histo); | |
}, | |
avg: function(force) { | |
var vbox = this, | |
histo = vbox.histo; | |
if (!vbox._avg || force) { | |
var ntot = 0, | |
mult = 1 << (8 - sigbits), | |
rsum = 0, | |
gsum = 0, | |
bsum = 0, | |
hval, | |
i, j, k, histoindex; | |
for (i = vbox.r1; i <= vbox.r2; i++) { | |
for (j = vbox.g1; j <= vbox.g2; j++) { | |
for (k = vbox.b1; k <= vbox.b2; k++) { | |
histoindex = getColorIndex(i,j,k); | |
hval = histo[histoindex] || 0; | |
ntot += hval; | |
rsum += (hval * (i + 0.5) * mult); | |
gsum += (hval * (j + 0.5) * mult); | |
bsum += (hval * (k + 0.5) * mult); | |
} | |
} | |
} | |
if (ntot) { | |
vbox._avg = [~~(rsum/ntot), ~~(gsum/ntot), ~~(bsum/ntot)]; | |
} else { | |
console.log('empty box'); | |
vbox._avg = [ | |
~~(mult * (vbox.r1 + vbox.r2 + 1) / 2), | |
~~(mult * (vbox.g1 + vbox.g2 + 1) / 2), | |
~~(mult * (vbox.b1 + vbox.b2 + 1) / 2) | |
]; | |
} | |
} | |
return vbox._avg; | |
}, | |
contains: function(pixel) { | |
var vbox = this, | |
rval = pixel[0] >> rshift; | |
gval = pixel[1] >> rshift; | |
bval = pixel[2] >> rshift; | |
return (rval >= vbox.r1 && rval <= vbox.r2 && | |
gval >= vbox.g1 && gval <= vbox.g2 && | |
bval >= vbox.b1 && bval <= vbox.b2); | |
} | |
}; | |
// Color map | |
function CMap() { | |
this.vboxes = new PQueue(function(a,b) { | |
return pv.naturalOrder( | |
a.vbox.count()*a.vbox.volume(), | |
b.vbox.count()*b.vbox.volume() | |
) | |
});; | |
} | |
CMap.prototype = { | |
push: function(vbox) { | |
this.vboxes.push({ | |
vbox: vbox, | |
color: vbox.avg() | |
}); | |
}, | |
palette: function() { | |
return this.vboxes.map(function(vb) { return vb.color }); | |
}, | |
size: function() { | |
return this.vboxes.size(); | |
}, | |
map: function(color) { | |
var vboxes = this.vboxes; | |
for (var i=0; i<vboxes.size(); i++) { | |
if (vboxes.peek(i).vbox.contains(color)) { | |
return vboxes.peek(i).color; | |
} | |
} | |
return this.nearest(color); | |
}, | |
nearest: function(color) { | |
var vboxes = this.vboxes, | |
d1, d2, pColor; | |
for (var i=0; i<vboxes.size(); i++) { | |
d2 = Math.sqrt( | |
Math.pow(color[0] - vboxes.peek(i).color[0], 2) + | |
Math.pow(color[1] - vboxes.peek(i).color[1], 2) + | |
Math.pow(color[2] - vboxes.peek(i).color[2], 2) | |
); | |
if (d2 < d1 || d1 === undefined) { | |
d1 = d2; | |
pColor = vboxes.peek(i).color; | |
} | |
} | |
return pColor; | |
}, | |
forcebw: function() { | |
// XXX: won't work yet | |
var vboxes = this.vboxes; | |
vboxes.sort(function(a,b) { return pv.naturalOrder(pv.sum(a.color), pv.sum(b.color) )}); | |
// force darkest color to black if everything < 5 | |
var lowest = vboxes[0].color; | |
if (lowest[0] < 5 && lowest[1] < 5 && lowest[2] < 5) | |
vboxes[0].color = [0,0,0]; | |
// force lightest color to white if everything > 251 | |
var idx = vboxes.length-1, | |
highest = vboxes[idx].color; | |
if (highest[0] > 251 && highest[1] > 251 && highest[2] > 251) | |
vboxes[idx].color = [255,255,255]; | |
} | |
}; | |
// histo (1-d array, giving the number of pixels in | |
// each quantized region of color space), or null on error | |
function getHisto(pixels) { | |
var histosize = 1 << (3 * sigbits), | |
histo = new Array(histosize), | |
index, rval, gval, bval; | |
pixels.forEach(function(pixel) { | |
rval = pixel[0] >> rshift; | |
gval = pixel[1] >> rshift; | |
bval = pixel[2] >> rshift; | |
index = getColorIndex(rval, gval, bval); | |
histo[index] = (histo[index] || 0) + 1; | |
}); | |
return histo; | |
} | |
function vboxFromPixels(pixels, histo) { | |
var rmin=1000000, rmax=0, | |
gmin=1000000, gmax=0, | |
bmin=1000000, bmax=0, | |
rval, gval, bval; | |
// find min/max | |
pixels.forEach(function(pixel) { | |
rval = pixel[0] >> rshift; | |
gval = pixel[1] >> rshift; | |
bval = pixel[2] >> rshift; | |
if (rval < rmin) rmin = rval; | |
else if (rval > rmax) rmax = rval; | |
if (gval < gmin) gmin = gval; | |
else if (gval > gmax) gmax = gval; | |
if (bval < bmin) bmin = bval; | |
else if (bval > bmax) bmax = bval; | |
}); | |
return new VBox(rmin, rmax, gmin, gmax, bmin, bmax, histo); | |
} | |
function medianCutApply(histo, vbox) { | |
if (!vbox.count()) return; | |
var rw = vbox.r2 - vbox.r1 + 1, | |
gw = vbox.g2 - vbox.g1 + 1, | |
bw = vbox.b2 - vbox.b1 + 1, | |
maxw = pv.max([rw, gw, bw]); | |
// only one pixel, no split | |
if (vbox.count() == 1) { | |
return [vbox.copy()] | |
} | |
/* Find the partial sum arrays along the selected axis. */ | |
var total = 0, | |
partialsum = [], | |
lookaheadsum = [], | |
i, j, k, sum, index; | |
if (maxw == rw) { | |
for (i = vbox.r1; i <= vbox.r2; i++) { | |
sum = 0; | |
for (j = vbox.g1; j <= vbox.g2; j++) { | |
for (k = vbox.b1; k <= vbox.b2; k++) { | |
index = getColorIndex(i,j,k); | |
sum += (histo[index] || 0); | |
} | |
} | |
total += sum; | |
partialsum[i] = total; | |
} | |
} | |
else if (maxw == gw) { | |
for (i = vbox.g1; i <= vbox.g2; i++) { | |
sum = 0; | |
for (j = vbox.r1; j <= vbox.r2; j++) { | |
for (k = vbox.b1; k <= vbox.b2; k++) { | |
index = getColorIndex(j,i,k); | |
sum += (histo[index] || 0); | |
} | |
} | |
total += sum; | |
partialsum[i] = total; | |
} | |
} | |
else { /* maxw == bw */ | |
for (i = vbox.b1; i <= vbox.b2; i++) { | |
sum = 0; | |
for (j = vbox.r1; j <= vbox.r2; j++) { | |
for (k = vbox.g1; k <= vbox.g2; k++) { | |
index = getColorIndex(j,k,i); | |
sum += (histo[index] || 0); | |
} | |
} | |
total += sum; | |
partialsum[i] = total; | |
} | |
} | |
partialsum.forEach(function(d,i) { | |
lookaheadsum[i] = total-d | |
}); | |
function doCut(color) { | |
var dim1 = color + '1', | |
dim2 = color + '2', | |
left, right, vbox1, vbox2, d2, count2=0; | |
for (i = vbox[dim1]; i <= vbox[dim2]; i++) { | |
if (partialsum[i] > total / 2) { | |
vbox1 = vbox.copy(); | |
vbox2 = vbox.copy(); | |
left = i - vbox[dim1]; | |
right = vbox[dim2] - i; | |
if (left <= right) | |
d2 = Math.min(vbox[dim2] - 1, ~~(i + right / 2)); | |
else d2 = Math.max(vbox[dim1], ~~(i - 1 - left / 2)); | |
// avoid 0-count boxes | |
while (!partialsum[d2]) d2++; | |
count2 = lookaheadsum[d2]; | |
while (!count2 && partialsum[d2-1]) count2 = lookaheadsum[--d2]; | |
// set dimensions | |
vbox1[dim2] = d2; | |
vbox2[dim1] = vbox1[dim2] + 1; | |
console.log('vbox counts:', vbox.count(), vbox1.count(), vbox2.count()); | |
return [vbox1, vbox2]; | |
} | |
} | |
} | |
// determine the cut planes | |
return maxw == rw ? doCut('r') : | |
maxw == gw ? doCut('g') : | |
doCut('b'); | |
} | |
function quantize(pixels, maxcolors) { | |
// short-circuit | |
if (!pixels.length || maxcolors < 2 || maxcolors > 256) { | |
console.log('wrong number of maxcolors'); | |
return false; | |
} | |
// XXX: check color content and convert to grayscale if insufficient | |
var histo = getHisto(pixels), | |
histosize = 1 << (3 * sigbits); | |
// check that we aren't below maxcolors already | |
var nColors = 0; | |
histo.forEach(function() { nColors++ }); | |
if (nColors <= maxcolors) { | |
// XXX: generate the new colors from the histo and return | |
} | |
// get the beginning vbox from the colors | |
var vbox = vboxFromPixels(pixels, histo), | |
pq = new PQueue(function(a,b) { return pv.naturalOrder(a.count(), b.count()) }); | |
pq.push(vbox); | |
// inner function to do the iteration | |
function iter(lh, target) { | |
var ncolors = 1, | |
niters = 0, | |
vbox; | |
while (niters < maxIterations) { | |
vbox = lh.pop(); | |
if (!vbox.count()) { /* just put it back */ | |
lh.push(vbox); | |
niters++; | |
continue; | |
} | |
// do the cut | |
var vboxes = medianCutApply(histo, vbox), | |
vbox1 = vboxes[0], | |
vbox2 = vboxes[1]; | |
if (!vbox1) { | |
console.log("vbox1 not defined; shouldn't happen!"); | |
return; | |
} | |
lh.push(vbox1); | |
if (vbox2) { /* vbox2 can be null */ | |
lh.push(vbox2); | |
ncolors++; | |
} | |
if (ncolors >= target) return; | |
if (niters++ > maxIterations) { | |
console.log("infinite loop; perhaps too few pixels!"); | |
return; | |
} | |
} | |
} | |
// first set of colors, sorted by population | |
iter(pq, fractByPopulations * maxcolors); | |
// console.log(pq.size(), pq.debug().length, pq.debug().slice()); | |
// Re-sort by the product of pixel occupancy times the size in color space. | |
var pq2 = new PQueue(function(a,b) { | |
return pv.naturalOrder(a.count()*a.volume(), b.count()*b.volume()) | |
}); | |
while (pq.size()) { | |
pq2.push(pq.pop()); | |
} | |
// next set - generate the median cuts using the (npix * vol) sorting. | |
iter(pq2, maxcolors - pq2.size()); | |
// calculate the actual colors | |
var cmap = new CMap(); | |
while (pq2.size()) { | |
cmap.push(pq2.pop()); | |
} | |
return cmap; | |
} | |
return { | |
quantize: quantize | |
} | |
})(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
jmcbee commentedOct 6, 2014
How do I use this? When I
console.log(MMCQ)
I getobject is not a function
.