class RgbQuant { constructor(opts) { opts = opts || {}; // 1 = by global population, 2 = subregion population threshold this.method = opts.method || 2; // desired final palette size this.colors = opts.colors || 256; // # of highest-frequency colors to start with for palette reduction this.initColors = opts.initColors || 4096; // color-distance threshold for initial reduction pass this.initDist = opts.initDist || 0.01; // subsequent passes threshold this.distIncr = opts.distIncr || 0.005; // palette grouping this.hueGroups = opts.hueGroups || 10; this.satGroups = opts.satGroups || 10; this.lumGroups = opts.lumGroups || 10; // if > 0, enables hues stats and min-color retention per group this.minHueCols = opts.minHueCols || 0; // HueStats instance this.hueStats = this.minHueCols ? new HueStats(this.hueGroups, this.minHueCols) : null; // subregion partitioning box size this.boxSize = opts.boxSize || [64,64]; // number of same pixels required within box for histogram inclusion this.boxPxls = opts.boxPxls || 2; // palette locked indicator this.palLocked = false; // palette sort order // this.sortPal = ['hue-','lum-','sat-']; // dithering/error diffusion kernel name this.dithKern = opts.dithKern || null; // dither serpentine pattern this.dithSerp = opts.dithSerp || false; // minimum color difference (0-1) needed to dither this.dithDelta = opts.dithDelta || 0; // accumulated histogram this.histogram = {}; // palette - rgb triplets this.idxrgb = opts.palette ? opts.palette.slice(0) : []; // palette - int32 vals this.idxi32 = []; // reverse lookup {i32:idx} this.i32idx = {}; // {i32:rgb} this.i32rgb = {}; // enable color caching (also incurs overhead of cache misses and cache building) this.useCache = opts.useCache !== false; // min color occurance count needed to qualify for caching this.cacheFreq = opts.cacheFreq || 10; // allows pre-defined palettes to be re-indexed (enabling palette compacting and sorting) this.reIndex = opts.reIndex || this.idxrgb.length == 0; // selection of color-distance equation this.colorDist = opts.colorDist == "manhattan" ? distManhattan : distEuclidean; // if pre-defined palette, build lookups if (this.idxrgb.length > 0) { var self = this; this.idxrgb.forEach(function(rgb, i) { var i32 = ( (255 << 24) | // alpha (rgb[2] << 16) | // blue (rgb[1] << 8) | // green rgb[0] // red ) >>> 0; self.idxi32[i] = i32; self.i32idx[i32] = i; self.i32rgb[i32] = rgb; }); } } //end constructor // gathers histogram info sample (img, width) { if (this.palLocked) throw "Cannot sample additional images, palette already assembled."; var data = getImageData(img, width); switch (this.method) { case 1: this.colorStats1D(data.buf32); break; case 2: this.colorStats2D(data.buf32, data.width); break; } } // image quantizer // todo: memoize colors here also // @retType: 1 - Uint8Array (default), 2 - Indexed array, 3 - Match @img type (unimplemented, todo) reduce(img, retType, dithKern, dithSerp) { if (!this.palLocked) this.buildPal(); dithKern = dithKern || this.dithKern; dithSerp = typeof dithSerp != "undefined" ? dithSerp : this.dithSerp; retType = retType || 1; // reduce w/dither if (dithKern) var out32 = this.dither(img, dithKern, dithSerp); else { var data = getImageData(img), buf32 = data.buf32, len = buf32.length, out32 = new Uint32Array(len); for (var i = 0; i < len; i++) { var i32 = buf32[i]; out32[i] = this.nearestColor(i32); } } if (retType == 1) return new Uint8Array(out32.buffer); if (retType == 2) { var out = [], len = out32.length; for (var i = 0; i < len; i++) { var i32 = out32[i]; out[i] = this.i32idx[i32]; } return out; } } // adapted from http://jsbin.com/iXofIji/2/edit by PAEz dither (img, kernel, serpentine) { // http://www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/ var kernels = { FloydSteinberg: [ [7 / 16, 1, 0], [3 / 16, -1, 1], [5 / 16, 0, 1], [1 / 16, 1, 1] ], FalseFloydSteinberg: [ [3 / 8, 1, 0], [3 / 8, 0, 1], [2 / 8, 1, 1] ], Stucki: [ [8 / 42, 1, 0], [4 / 42, 2, 0], [2 / 42, -2, 1], [4 / 42, -1, 1], [8 / 42, 0, 1], [4 / 42, 1, 1], [2 / 42, 2, 1], [1 / 42, -2, 2], [2 / 42, -1, 2], [4 / 42, 0, 2], [2 / 42, 1, 2], [1 / 42, 2, 2] ], Atkinson: [ [1 / 8, 1, 0], [1 / 8, 2, 0], [1 / 8, -1, 1], [1 / 8, 0, 1], [1 / 8, 1, 1], [1 / 8, 0, 2] ], Jarvis: [ // Jarvis, Judice, and Ninke / JJN? [7 / 48, 1, 0], [5 / 48, 2, 0], [3 / 48, -2, 1], [5 / 48, -1, 1], [7 / 48, 0, 1], [5 / 48, 1, 1], [3 / 48, 2, 1], [1 / 48, -2, 2], [3 / 48, -1, 2], [5 / 48, 0, 2], [3 / 48, 1, 2], [1 / 48, 2, 2] ], Burkes: [ [8 / 32, 1, 0], [4 / 32, 2, 0], [2 / 32, -2, 1], [4 / 32, -1, 1], [8 / 32, 0, 1], [4 / 32, 1, 1], [2 / 32, 2, 1], ], Sierra: [ [5 / 32, 1, 0], [3 / 32, 2, 0], [2 / 32, -2, 1], [4 / 32, -1, 1], [5 / 32, 0, 1], [4 / 32, 1, 1], [2 / 32, 2, 1], [2 / 32, -1, 2], [3 / 32, 0, 2], [2 / 32, 1, 2], ], TwoSierra: [ [4 / 16, 1, 0], [3 / 16, 2, 0], [1 / 16, -2, 1], [2 / 16, -1, 1], [3 / 16, 0, 1], [2 / 16, 1, 1], [1 / 16, 2, 1], ], SierraLite: [ [2 / 4, 1, 0], [1 / 4, -1, 1], [1 / 4, 0, 1], ], }; if (!kernel || !kernels[kernel]) { throw 'Unknown dithering kernel: ' + kernel; } var ds = kernels[kernel]; var data = getImageData(img), // buf8 = data.buf8, buf32 = data.buf32, width = data.width, height = data.height, len = buf32.length; var dir = serpentine ? -1 : 1; for (var y = 0; y < height; y++) { if (serpentine) dir = dir * -1; var lni = y * width; for (var x = (dir == 1 ? 0 : width - 1), xend = (dir == 1 ? width : 0); x !== xend; x += dir) { // Image pixel var idx = lni + x, i32 = buf32[idx], r1 = (i32 & 0xff), g1 = (i32 & 0xff00) >> 8, b1 = (i32 & 0xff0000) >> 16; // Reduced pixel var i32x = this.nearestColor(i32), r2 = (i32x & 0xff), g2 = (i32x & 0xff00) >> 8, b2 = (i32x & 0xff0000) >> 16; buf32[idx] = (255 << 24) | // alpha (b2 << 16) | // blue (g2 << 8) | // green r2; // dithering strength if (this.dithDelta) { var dist = this.colorDist([r1, g1, b1], [r2, g2, b2]); if (dist < this.dithDelta) continue; } // Component distance var er = r1 - r2, eg = g1 - g2, eb = b1 - b2; for (var i = (dir == 1 ? 0 : ds.length - 1), end = (dir == 1 ? ds.length : 0); i !== end; i += dir) { var x1 = ds[i][1] * dir, y1 = ds[i][2]; var lni2 = y1 * width; if (x1 + x >= 0 && x1 + x < width && y1 + y >= 0 && y1 + y < height) { var d = ds[i][0]; var idx2 = idx + (lni2 + x1); var r3 = (buf32[idx2] & 0xff), g3 = (buf32[idx2] & 0xff00) >> 8, b3 = (buf32[idx2] & 0xff0000) >> 16; var r4 = Math.max(0, Math.min(255, r3 + er * d)), g4 = Math.max(0, Math.min(255, g3 + eg * d)), b4 = Math.max(0, Math.min(255, b3 + eb * d)); buf32[idx2] = (255 << 24) | // alpha (b4 << 16) | // blue (g4 << 8) | // green r4; // red } } } } return buf32; } // reduces histogram to palette, remaps & memoizes reduced colors buildPal (noSort) { if (this.palLocked || this.idxrgb.length > 0 && this.idxrgb.length <= this.colors) return; var histG = this.histogram, sorted = sortedHashKeys(histG, true); if (sorted.length == 0) throw "Nothing has been sampled, palette cannot be built."; switch (this.method) { case 1: var cols = this.initColors, last = sorted[cols - 1], freq = histG[last]; var idxi32 = sorted.slice(0, cols); // add any cut off colors with same freq as last var pos = cols, len = sorted.length; while (pos < len && histG[sorted[pos]] == freq) idxi32.push(sorted[pos++]); // inject min huegroup colors if (this.hueStats) this.hueStats.inject(idxi32); break; case 2: var idxi32 = sorted; break; } // int32-ify values idxi32 = idxi32.map(function(v){return +v;}); this.reducePal(idxi32); if (!noSort && this.reIndex) this.sortPal(); // build cache of top histogram colors if (this.useCache) this.cacheHistogram(idxi32); this.palLocked = true; } palette (tuples, noSort) { this.buildPal(noSort); return tuples ? this.idxrgb : new Uint8Array((new Uint32Array(this.idxi32)).buffer); } prunePal(keep) { var i32; for (var j = 0; j < this.idxrgb.length; j++) { if (!keep[j]) { i32 = this.idxi32[j]; this.idxrgb[j] = null; this.idxi32[j] = null; delete this.i32idx[i32]; } } // compact if (this.reIndex) { var idxrgb = [], idxi32 = [], i32idx = {}; for (var j = 0, i = 0; j < this.idxrgb.length; j++) { if (this.idxrgb[j]) { i32 = this.idxi32[j]; idxrgb[i] = this.idxrgb[j]; i32idx[i32] = i; idxi32[i] = i32; i++; } } this.idxrgb = idxrgb; this.idxi32 = idxi32; this.i32idx = i32idx; } } // reduces similar colors from an importance-sorted Uint32 rgba array reducePal(idxi32) { var sort = isArrSortStable() ? Array.prototype.sort : stableSort; // if pre-defined palette's length exceeds target if (this.idxrgb.length > this.colors) { // quantize histogram to existing palette var len = idxi32.length, keep = {}, uniques = 0, idx, pruned = false; for (var i = 0; i < len; i++) { // palette length reached, unset all remaining colors (sparse palette) if (uniques == this.colors && !pruned) { this.prunePal(keep); pruned = true; } idx = this.nearestIndex(idxi32[i]); if (uniques < this.colors && !keep[idx]) { keep[idx] = true; uniques++; } } if (!pruned) { this.prunePal(keep); pruned = true; } } // reduce histogram to create initial palette else { // build full rgb palette var idxrgb = idxi32.map(function(i32) { return [ (i32 & 0xff), (i32 & 0xff00) >> 8, (i32 & 0xff0000) >> 16, ]; }); var len = idxrgb.length, palLen = len, thold = this.initDist; // palette already at or below desired length if (palLen > this.colors) { while (palLen > this.colors) { var memDist = []; // iterate palette for (var i = 0; i < len; i++) { var pxi = idxrgb[i], i32i = idxi32[i]; if (!pxi) continue; for (var j = i + 1; j < len; j++) { var pxj = idxrgb[j], i32j = idxi32[j]; if (!pxj) continue; var dist = this.colorDist(pxi, pxj); if (dist < thold) { // store index,rgb,dist memDist.push([j, pxj, i32j, dist]); // kill squashed value delete(idxrgb[j]); palLen--; } } } // palette reduction pass // console.log("palette length: " + palLen); // if palette is still much larger than target, increment by larger initDist thold += (palLen > this.colors * 3) ? this.initDist : this.distIncr; } // if palette is over-reduced, re-add removed colors with largest distances from last round if (palLen < this.colors) { // sort descending sort.call(memDist, function(a,b) { return b[3] - a[3]; }); var k = 0; while (palLen < this.colors) { // re-inject rgb into final palette idxrgb[memDist[k][0]] = memDist[k][1]; palLen++; k++; } } } var len = idxrgb.length; for (var i = 0; i < len; i++) { if (!idxrgb[i]) continue; this.idxrgb.push(idxrgb[i]); this.idxi32.push(idxi32[i]); this.i32idx[idxi32[i]] = this.idxi32.length - 1; this.i32rgb[idxi32[i]] = idxrgb[i]; } } } // global top-population colorStats1D(buf32) { var histG = this.histogram, num = 0, col, len = buf32.length; for (var i = 0; i < len; i++) { col = buf32[i]; // skip transparent if ((col & 0xff000000) >> 24 == 0) continue; // collect hue stats if (this.hueStats) this.hueStats.check(col); if (col in histG) histG[col]++; else histG[col] = 1; } } // population threshold within subregions // FIXME: this can over-reduce (few/no colors same?), need a way to keep // important colors that dont ever reach local thresholds (gradients?) colorStats2D(buf32, width) { var boxW = this.boxSize[0], boxH = this.boxSize[1], area = boxW * boxH, boxes = makeBoxes(width, buf32.length / width, boxW, boxH), histG = this.histogram, self = this; boxes.forEach(function(box) { var effc = Math.max(Math.round((box.w * box.h) / area) * self.boxPxls, 2), histL = {}, col; iterBox(box, width, function(i) { col = buf32[i]; // skip transparent if ((col & 0xff000000) >> 24 == 0) return; // collect hue stats if (self.hueStats) self.hueStats.check(col); if (col in histG) histG[col]++; else if (col in histL) { if (++histL[col] >= effc) histG[col] = histL[col]; } else histL[col] = 1; }); }); if (this.hueStats) this.hueStats.inject(histG); } // TODO: group very low lum and very high lum colors // TODO: pass custom sort order sortPal() { var self = this; this.idxi32.sort(function(a,b) { var idxA = self.i32idx[a], idxB = self.i32idx[b], rgbA = self.idxrgb[idxA], rgbB = self.idxrgb[idxB]; var hslA = rgb2hsl(rgbA[0],rgbA[1],rgbA[2]), hslB = rgb2hsl(rgbB[0],rgbB[1],rgbB[2]); // sort all grays + whites together var hueA = (rgbA[0] == rgbA[1] && rgbA[1] == rgbA[2]) ? -1 : hueGroup(hslA.h, self.hueGroups); var hueB = (rgbB[0] == rgbB[1] && rgbB[1] == rgbB[2]) ? -1 : hueGroup(hslB.h, self.hueGroups); var hueDiff = hueB - hueA; if (hueDiff) return -hueDiff; var lumDiff = lumGroup(+hslB.l.toFixed(2)) - lumGroup(+hslA.l.toFixed(2)); if (lumDiff) return -lumDiff; var satDiff = satGroup(+hslB.s.toFixed(2)) - satGroup(+hslA.s.toFixed(2)); if (satDiff) return -satDiff; }); // sync idxrgb & i32idx this.idxi32.forEach(function(i32, i) { self.idxrgb[i] = self.i32rgb[i32]; self.i32idx[i32] = i; }); } // TOTRY: use HUSL - http://boronine.com/husl/ nearestColor(i32) { var idx = this.nearestIndex(i32); return idx === null ? 0 : this.idxi32[idx]; }; // TOTRY: use HUSL - http://boronine.com/husl/ nearestIndex(i32) { // alpha 0 returns null index if ((i32 & 0xff000000) >> 24 == 0) return null; if (this.useCache && (""+i32) in this.i32idx) return this.i32idx[i32]; var min = 1000, idx, rgb = [ (i32 & 0xff), (i32 & 0xff00) >> 8, (i32 & 0xff0000) >> 16, ], len = this.idxrgb.length; for (var i = 0; i < len; i++) { if (!this.idxrgb[i]) continue; // sparse palettes var dist = this.colorDist(rgb, this.idxrgb[i]); if (dist < min) { min = dist; idx = i; } } return idx; } cacheHistogram(idxi32) { for (var i = 0, i32 = idxi32[i]; i < idxi32.length && this.histogram[i32] >= this.cacheFreq; i32 = idxi32[i++]) this.i32idx[i32] = this.nearestIndex(i32); } }