Palette library

ColorCutQuantinizer.js

function ColorCutQuantizer(imageData, maxColors) {
    var colorHist = new ColorHistogram(imageData);

    var rawColors = colorHist.getColors();
    this._colorPopulations = colorHist.getColorPopulations();

    /** @type {Color[]} */
    this._colors = [];
    for (var i = 0; i < rawColors.length; i++) {
        var color = rawColors[i];
        if (this._shouldIgnoreColor(color)) {
            continue;
        }

        this._colors.push(color);
    }

    if (this._colors.length <= maxColors) {
        //if (true) {
        this._quantizedColors = [];
        for (var i = 0; i < this._colors.length; i++) {
            var color = this._colors[i];
            this._quantizedColors.push(new PaletteItem(color, this._colorPopulations[color.rgbValue()]));
        }
    } else {
        this._quantizedColors = this._quantizePixels(this._colors.length - 1, maxColors);
    }
}

/**
 * @returns {PaletteItem[]}
 */
ColorCutQuantizer.prototype.getQuantizedColors = function() {
    return this._quantizedColors;
};

ColorCutQuantizer.prototype._quantizePixels = function(maxColorIndex, maxColors) {
    var pq = new PriorityQueue({
        comparator: function(lhs, rhs) {
            return rhs.getVolume() - lhs.getVolume();
        }
    });

    pq.queue(new ColorCutQuantizer.Vbox(this, 0, maxColorIndex));
    this._splitBoxes(pq, maxColors);
    return this._generateAverageColors(pq);
};

/**
 * @param {PriorityQueue} queue
 * @param {Number} maxSize
 * @private
 */
ColorCutQuantizer.prototype._splitBoxes = function(queue, maxSize) {
    while (queue.length < maxSize) {
        var vbox = queue.dequeue();
        if (vbox !== null && vbox.canSplit()) {
            queue.queue(vbox.splitBox());
            queue.queue(vbox);
        } else {
            return;
        }
    }
};

/**
 * @param {PriorityQueue} vboxQueue
 * @private
 */
ColorCutQuantizer.prototype._generateAverageColors = function(vboxQueue) {
    var colors = [];
    while (vboxQueue.length > 0) {
        var vbox = vboxQueue.dequeue();
        var color = vbox.getAverageColor();
        if (!this._shouldIgnoreColor(color)) {
            colors.push(color);
        }
    }
    return colors;
};

/**
 * @param {Color} color
 * @return {Boolean}
 * @private
 */
ColorCutQuantizer.prototype._shouldIgnoreColor = function(color) {
    return color.isWhite() || color.isBlack() || color.isTransparent() || color.isNearRedILine();
};

ColorCutQuantinizer.Vbox.js

/**
 * @param {ColorCutQuantizer} parent
 * @param lowerIndex
 * @param upperIndex
 * @constructor
 */
ColorCutQuantizer.Vbox = function(parent, lowerIndex, upperIndex) {
    this._parent = parent;
    this._lowerIndex = lowerIndex;
    this._upperIndex = upperIndex;
    this.fitBox();
};

ColorCutQuantizer.Vbox.prototype.getVolume = function() {
    return ((this._maxRed - this._minRed) + 1) * ((this._maxGreen - this._minGreen) + 1) * ((this._maxBlue - this._minBlue) + 1);
};

ColorCutQuantizer.Vbox.prototype.canSplit = function() {
    return this.getColorCount() > 1;
};

ColorCutQuantizer.Vbox.prototype.getColorCount = function() {
    return this._upperIndex - this._lowerIndex;
};

ColorCutQuantizer.Vbox.prototype.fitBox = function() {
    this._minRed = this._minGreen = this._minBlue = 255;
    this._maxRed = this._maxGreen = this._maxBlue = 0;

    for (var i = this._lowerIndex; i <= this._upperIndex; i++) {
        var color = this._parent._colors[i];
        var r = color.red;
        var g = color.green;
        var b = color.blue;
        if (r > this._maxRed) {
            this._maxRed = r;
        }
        if (r < this._minRed) {
            this._minRed = r;
        }
        if (g > this._maxGreen) {
            this._maxGreen = g;
        }
        if (g < this._minGreen) {
            this._minGreen = g;
        }
        if (b > this._maxBlue) {
            this._maxBlue = b;
        }
        if (b < this._minBlue) {
            this._minBlue = b;
        }
    }
};

ColorCutQuantizer.Vbox.prototype.splitBox = function() {
    if (!this.canSplit()) {
        throw new Error("Can not split a box with only 1 color");
    }

    var splitPoint = this.findSplitPoint();
    var newBox = new ColorCutQuantizer.Vbox(this._parent, splitPoint + 1, this._upperIndex);
    this._upperIndex = splitPoint;
    this.fitBox();
    return newBox;
};

ColorCutQuantizer.Vbox.prototype.getLongestColorDimension = function() {
    var redLength = this._maxRed - this._minRed;
    var greenLength = this._maxGreen - this._minGreen;
    var blueLength = this._maxBlue - this._minBlue;

    if (redLength >= greenLength && redLength >= blueLength) {
        return -3;
    }

    return greenLength < redLength || greenLength < blueLength ? -1 : -2;
};

ColorCutQuantizer.Vbox.prototype.findSplitPoint = function() {
    var longestDimension = this.getLongestColorDimension();
    var sortOrder = ['red', 'green', 'blue'];
    if (longestDimension === -2) {
        sortOrder = ['green', 'red', 'blue'];
    } else if (longestDimension === -1) {
        sortOrder = ['blue', 'green', 'blue'];
    }
    var beforeRange = this._parent._colors.slice(0, this._lowerIndex);
    var rangeColors = this._parent._colors.slice(this._lowerIndex, this._upperIndex + 1);
    rangeColors = rangeColors.sort(Color.sort(sortOrder));
    var afterRange = this._parent._colors.slice(this._upperIndex + 1);
    this._parent._colors = beforeRange.concat(rangeColors, afterRange);

    var dimensionMidpoint = this.midPoint(longestDimension);
    for (var i = this._lowerIndex; i < this._upperIndex; i++) {
        var color = this._parent._colors[i];
        switch (longestDimension) {
            default:
                break;

            case -3:
                if (color.red >= dimensionMidpoint) {
                    return i;
                }
                break;

            case -2:
                if (color.green >= dimensionMidpoint) {
                    return i;
                }
                break;

            case -1:
                if (color.blue >= dimensionMidpoint) {
                    return i;
                }
                break;
        }
    }

    return this._lowerIndex;
};

ColorCutQuantizer.Vbox.prototype.getAverageColor = function() {
    var redSum = 0;
    var greenSum = 0;
    var blueSum = 0;
    var totalPopulation = 0;
    for (var i = this._lowerIndex; i <= this._upperIndex; i++) {
        var color = this._parent._colors[i];
        var colorPopulation = this._parent._colorPopulations[color.rgbValue()];
        totalPopulation += colorPopulation;
        redSum += colorPopulation * color.red;
        greenSum += colorPopulation * color.green;
        blueSum += colorPopulation * color.blue;
    }

    var redAverage = Math.round(redSum / totalPopulation);
    var greenAverage = Math.round(greenSum / totalPopulation);
    var blueAverage = Math.round(blueSum / totalPopulation);

    return new PaletteItem(new Color(redAverage, greenAverage, blueAverage), totalPopulation);
};

ColorCutQuantizer.Vbox.prototype.midPoint = function(dimension) {
    switch (dimension) {
        case -3:
        default:
            return (this._minRed + this._maxRed) / 2;

        case -2:
            return (this._minGreen + this._maxGreen) / 2;

        case -1:
            return (this._minBlue + this._maxBlue) / 2;
    }
};

ColorHistogram.js

/**
 * @param {ImageData} imageData
 * @constructor
 */
function ColorHistogram(imageData) {
    var pixels = [];

    var data = imageData.data;
    for (var i = 0; i < data.length; i += 4) {
        pixels.push(new Color(data[i], data[i + 1], data[i + 2], data[i + 3]));
    }

    pixels = pixels.sort(Color.sort());

    this._colorPopulations = _.countBy(pixels, function(color) {
        return color.rgbValue();
    });

    this._colors = _.uniq(pixels, function(color) {
        return color.rgbValue();
    });
}

/**
 * @returns {Color[]}
 */
ColorHistogram.prototype.getColors = function() {
    return this._colors;
};

/**
 * @returns {Object.<Number, Number>}
 */
ColorHistogram.prototype.getColorPopulations = function() {
    return this._colorPopulations;
};

ColorUtils.js

var ColorUtils = {
    RGBtoHSL: function(r, g, b) {
        var rf = r / 255;
        var gf = g / 255;
        var bf = b / 255;
        var max = Math.max(rf, Math.max(gf, bf));
        var min = Math.min(rf, Math.min(gf, bf));
        var deltaMaxMin = max - min;
        var l = (max + min) / 2.0;
        var h;
        var s;
        if (max == min) {
            h = s = 0.0;
        } else {
            if (max == rf)
                h = ((gf - bf) / deltaMaxMin) % 6;
            else if (max == gf)
                h = (bf - rf) / deltaMaxMin + 2.0;
            else
                h = (rf - gf) / deltaMaxMin + 4;
            s = deltaMaxMin / (1.0 - Math.abs(2.0 * l - 1.0));
        }

        return {
            0: (h * 60) % 360,
            1: s,
            2: l
        };
    }
};

Palette.js

/**
 * @param {PaletteItem[]} palette
 * @constructor
 */
function Palette(palette) {
    this._palette = palette;
    this._colors = {
        vibrant: this._findColor(0.5, 0.3, 0.7, 1.0, 0.35, 1.0),
        lightVibrant: this._findColor(0.74, 0.55, 1.0, 1.0, 0.35, 1.0),
        darkVibrant: this._findColor(0.26, 0.0, 0.45, 1.0, 0.35, 1.0),
        muted: this._findColor(0.5, 0.3, 0.7, 0.3, 0.0, 0.4),
        lightMuted: this._findColor(0.74, 0.55, 1.0, 0.3, 0.0, 0.4),
        darkMuted: this._findColor(0.26, 0.0, 0.45, 0.3, 0.0, 0.4)
    };
}

Palette.prototype.getVibrantColor = function() {
    return this._colors.vibrant;
};

Palette.prototype.getAccentColors = function() {
    return this._colors;
};

Palette.prototype.getColors = function() {
    return this._palette;
};

/**
 * @param targetLuma
 * @param minLuma
 * @param maxLuma
 * @param targetSaturation
 * @param minSaturation
 * @param maxSaturation
 * @return {PaletteItem}
 */
Palette.prototype._findColor = function(targetLuma, minLuma, maxLuma, targetSaturation, minSaturation, maxSaturation) {
    var max = null;
    var maxValue = 0.0;

    for (var i = 0; i < this._palette.length; i++) {
        var paletteItem = this._palette[i];
        var sat = paletteItem.getHsl()[1];
        var luma = paletteItem.getHsl()[2];
        if (sat >= minSaturation && sat <= maxSaturation && luma >= minLuma && luma <= maxLuma && !this._isAlreadySelected(paletteItem)) {
            var thisValue = this._createComparisonValue(sat, targetSaturation, luma, targetLuma, paletteItem._getPopulation(), this._getMaxPopulation());
            if (max === null || thisValue > maxValue) {
                max = paletteItem;
                maxValue = thisValue;
            }
        }
    }

    return max;
};

Palette.prototype._isAlreadySelected = function(item) {
    return _.contains(this._colors, item);
};

Palette.prototype._createComparisonValue = function(saturation, targetSatuation, luma, targetLuma, population, highestPopulation) {
    return this._weightedMean([
        [3, this._invertDiff(saturation, targetSatuation)],
        [6.5, this._invertDiff(luma, targetLuma)],
        [0.5, population / highestPopulation]
    ]);
};

Palette.prototype._invertDiff = function(value, targetValue) {
    return 1.0 - Math.abs(value - targetValue);
};

Palette.prototype._weightedMean = function(values) {
    var sum = _.reduce(values, function(memo, value) {
        return memo + value[0] * value[1]
    });
    var sumWeight = _.reduce(values, function(memo, value) {
        return memo + value[0]
    });

    return sum / sumWeight;
};

Palette.prototype._getMaxPopulation = function() {
    if (this._maxPopulation === undefined) {
        var population = 0;
        for (var i = 0; i < this._palette.length; i++) {
            var item = this._palette[i];
            population = Math.max(population, item._getPopulation());
        }
        this._maxPopulation = population;
    }

    return this._maxPopulation;
};


Palette.generate = function(image) {
    var self = this;

    return new Promise(function(fullfill, reject) {
        self._getScaledImageData(image)
            .done(function(imageData) {
                var quantizer = new ColorCutQuantizer(imageData, 16);
                fullfill(new Palette(quantizer.getQuantizedColors()))
            },
            function(error) {
                reject(error)
            });
    });
};

Palette._getScaledImageData = function(image) {
    var self = this;

    return new Promise(function(fullfill, reject) {
        if (image[0].naturalWidth !== 0) {
            fullfill(self._scaleImage(image[0]));
        }
        image
            .on('load', function(a, b, c) {
                fullfill(self._scaleImage(image[0]));
            })
            .on('error', function(a, b, c) {
                console.error(this, a, b, c);
            });
    });
};

/**
 * @param {HTMLImageElement} image
 * @returns {ImageData}
 * @private
 */
Palette._scaleImage = function(image) {
    var minDimension = Math.min(image.width, image.height);

    if (minDimension <= 100) {
        return this._getImageData(image, image.width, image.height);
    } else {
        var scaleRatio = 100 / minDimension;
        return this._getImageData(image, Math.round(image.width * scaleRatio), Math.round(image.height * scaleRatio));
    }
};

/**
 * @param {HTMLImageElement} image
 * @param {Number} width
 * @param {Number} height
 * @returns {ImageData}
 * @private
 */
Palette._getImageData = function(image, width, height) {
    canvas = document.createElement('canvas');
    canvas.width = width;
    canvas.height = height;
    ctx = canvas.getContext('2d');
    ctx.drawImage(image, 0, 0, width, height);

    return ctx.getImageData(0, 0, width, height);
};

PaletteItem.js

function PaletteItem(color, population) {
    this._color = color;
    this._population = population;
}

PaletteItem.prototype.getPopulation = function() {
    return this._population;
};

PaletteItem.prototype.getHsl = function() {
    return this._color.getHsl();
};

PaletteItem.prototype.isBlack = function() {
    return this._color.isBlack();
};

PaletteItem.prototype.isWhite = function() {
    return this._color.isWhite();
};

PaletteItem.prototype.isTransparent = function() {
    return this._color.isTransparent();
};

PaletteItem.prototype.toHex = function() {
    function toHex(int) {
        var hex = int.toString(16);
        if (hex.length < 2) {
            hex = '0' + hex;
        }
        return hex;
    }

    return '#' + toHex(this._color.alpha) + toHex(this._color.red) + toHex(this._color.green) + toHex(this._color.blue);
};

PaletteItem.prototype.isNearRedILine = function() {
    return this._color.isNearRedILine();
};


PaletteItem.prototype._getPopulation = function() {
    return this._population;
};

PaletteItem.prototype.toString = function() {
    return this._color.toString();
};

Originally these were all in one big file. It worked, but feels wrong.

(function(window, undefined) {
    …

    // Exports
    window.Palette = Palette;
})(window);