Palettejs

color-cut-quantizer.js

import FastPriorityQueue from 'faspriorityqueue';

import { Swatch } from './palette';

const COMPONENT_RED = -3;
const COMPONENT_GREEN = -2;
const COMPONENT_BLUE = -1;

const QUANTIZE_WORD_WIDTH = 5;
const QUANTIZE_WORD_MASK = (1 << QUANTIZE_WORD_WIDTH) - 1;

const VBOX_COMPARATOR_VOLUME = (a, b) => b.getVolume() - a.getVolume();

export default class ColorCutQuantizer {
    constructor (pixels, maxColors, filters) {
        if (! this instanceof ColorCutQuantizer) {
            return new ColorCutQuantizer(pixels, maxColors, filters);
        }

        this.filters = filters;

        let hist = this.histogram = new Int32Array(1 << (QUANTIZE_WORD_WIDTH * 3));
        for (let i = 0; i < pixels.length; i++) {
            const quantizedColor = quantizeFromRgb888(pixels[i]);
            pixels[i] = quantizedColor;
            hist[quantizedColor]++;
        }

        let distinctColorCount = 0;
        for (let color = 0; color < hist.length; color++) {
            if (hist[color] > 0 && shouldIgnoreColor565(color)) {
                hist[color] = 0;
            }
            if (hist[color] > 0) {
                distinctColorCount++;
            }
        }

        const colors = this.colors = new Int32Array(distinctColorCount);
        let distinctColorIndex = 0;
        for (let color = 0; color < hist.length; color++) {
            if (hist[color] > 0) {
                colors[distinctColorIndex++] = color;
            }
        }

        if (distinctColorCount <= maxColors) {
            this.quantizedColors = [];
            for (let color of colors) {
                this.quantizedColors.push(new Swatch(approximateToRgb888Color(color), hist[color]));
            }
        } else {
            this.quantizedColors = quantizePixels(this.colors.length, maxColors);
        }
    }

    get quantizedColors () {
        return this.quantizedColors;
    }
}

function quantizePixels (colorsLength, maxColors) {
    const pq = new FastPriorityQueue(VBOX_COMPARATOR_VOLUME);
    pq.array = new Array(maxColors); // hack, no default size
    pq.add(new Vbox(0, colorsLength - 1));
    splitBoxes(pq, maxColors);
    return generateAverageColors(pq);
}

function splitBoxes (queue, maxSize) {
    while (queue.size < maxSize) {
        const vbox = queue.poll();
        if (vbox != undefined && vbox.canSplit()) {
            queue.add(vbox.splitBox());
            queue.add(vbox);
        } else {
            return;
        }
    }
}

function generateAverageColors (vboxes) {
    let colors = new Array(vboxes.size);
    for (let vbox of vboxes.array) {
        let swatch = vbox.getAverageColor();
        if (! shouldIgnoreColorSwatch(swatch)) {
            colors.push(swatch);
        }
    }
    return colors;
}

class Vbox {
    constructor (lowerIndex, upperIndex) {
        this.lowerIndex = lowerIndex;
        this.upperIndex = upperIndex;
        fitBox();
    }

    getVolume () {
        return (this.maxRed - this.minRed + 1) * (this.maxGreen - this.minGreen + 1) *
                (this.maxBlue - this.minBlue + 1);
    }

    canSplit () {
        return getColorCount() > 1;
    }

    getColorCount () {
        return 1 + this.upperIndex - this.lowerIndex;
    }

    fitBox () {
        const colors = this.colors;
        const hist = this.histogram;

        let minRed, minGreen, minBlue;
        minRed = minGreen = minBlue = Number.MAX_SAFE_INTEGER;
        let maxRed, maxGreen, maxBlue;
        maxRed = maxGreen = maxBlue = Number.MIN_SAFE_INTEGER;
        let count = 0;

        for (let i = this.lowerIndex; i <= this.upperIndex; i++) {
            const color = colors[i];
            count += hist[color];

            const r = quantizedRed(color);
            const g = quantizedGreen(color);
            const b = quantizedBlue(color);
            if (r > maxRed) {
                maxRed = r;
            }
            if (r < minRed) {
                minRed = r;
            }
            if (g > maxGreen) {
                maxGreen = g;
            }
            if (g < minGreen) {
                minGreen = g;
            }
            if (b > maxBlue) {
                maxBlue = b;
            }
            if (b < minBlue) {
                minBlue = b;
            }
        }

        this.minRed = minRed;
        this.maxRed = maxRed;
        this.minGreen = minGreen;
        this.maxGreen = maxGreen;
        this.minBlue = minBlue;
        this.maxBlue = maxBlue;
        this.population = count;
    }

    splitBox () {
        if (! canSplit()) {
            throw new Error('Can not split a box with only 1 color');
        }

        const splitPoint = findSplitPoint();

        let newBox = new Vbox(splitPoint + 1, this.upperIndex);

        this.upperIndex = splitPoint;
        fitBox();

        return newBox;
    }

    getLongestColorDimension () {
        const redLength = this.maxRed - this.minRed;
        const greenLength = this.maxGreen - this.minGreen;
        const blueLength = this.maxBlue - this.minBlue;

        if (redLength >= greenLength && redLength >= blueLength) {
            return COMPONENT_RED;
        } else if (greenLength >= redLength && greenLength >= blueLength) {
            return COMPONENT_GREEN
        } else {
            return COMPONENT_BLUE;
        }
    }

    findSplitPoint () {
        const longestDimension = getLongestColorDimension();
        let colors = this.colors;
        const hist = this.histogram;

        modifySignificantOctet(colors, longestDimension, this.lowerIndex, this.upperIndex);

        colors = colors.slice(0, this.lowerIndex).concat(colors.slice(this.lowerIndex, this.upperIndex + 1).sort())
                .concat(colors.slice(this.upperIndex)); // hack, no array sort from-to index
        
        modifySignificantOctet(colors, longestDimension, this.lowerIndex, this.upperIndex);

        const midPoint = this.population / 2;
        for (let i = this.lowerIndex, count = 0; i <= this.upperIndex; i++) {
            count += hist[colors[i]];
            if (count >= midPoint) {
                return i;
            }
        }

        return this.lowerIndex;
    }

    getAverageColor () {
        const colors = this.colors;
        const hist = this.histogram;
        let redSum = 0;
        let greenSum = 0;
        let blueSum = 0;
        let totalPopulation = 0;

        for (let i = this.lowerIndex; i <= this.upperIndex; i++) {
            const color = colors[i];
            const colorPopulation = hist[color];

            totalPopulation += colorPopulation;
            redSum += colorPopulation * quantizedRed(color);
            greenSum += colorPopulation * quantizedGreen(color);
            blueSum += colorPopulation * quantizedBlue(color);
        }

        const redMean = Math.round(redSum / totalPopulation);
        const greenMean = Math.round(greenSum / totalPopulation);
        const blueMean = Math.round(blueSum / totalPopulation);

        return new Swatch(approximateToRgb888(redMean, greenMean, blueMean), totalPopulation);
    }

    shouldIgnoreColor565 (color565) {
        const rgb = approximateToRgb888Color(color565);
        let hsl = colorToHSL(rgb);
        return shouldIgnoreColor(rgb, hsl);
    }

    shouldIgnoreColorSwatch (swatch) {
        return shouldIgnoreColor(swatch.getRgb(), swatch.getHsl());
    }

    shouldIgnoreColor (rgb, hsl) {
        if (this.filters && this.filters.length > 0) {
            for (let i = 0, count = this.filters.length; i < count; i++) {
                if (! this.filters[i].isAllowed(rgb, hsl)) {
                    return true;
                }
            }
        }
        return false;
    }
}

function modifySignificantOctet (a, dimension, lower, upper) {
    switch (dimension) {
        case COMPONENT_RED:
            break;
        case COMPONENT_GREEN:
            for (let i = lower; i <= upper; i++) {
                const color = a[i];
                a[i] = quantizedGreen(color) << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH)
                        | quantizedRed(color) << QUANTIZE_WORD_WIDTH
                        | quantizedBlue(color);
            }
            break;
        case COMPONENT_BLUE:
            for (let i = lower; i <= upper; i++) {
                const color = a[i];
                a[i] = quantizedBlue(color) << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH)
                        | quantizedGreen(color) << QUANTIZE_WORD_WIDTH
                        | quantizedRed(color);
            }
            break;
    }
}

function colorToHSL (color) {
    const rf = ((color >> 16) & 0xFF) / 255;
    const gf = ((color >>8) & 0xFF) / 255;
    const bf = (color & 0xFF) / 255;

    const max = Math.max(rf, Math.max(gf, bf));
    const min = Math.min(rf, Math.min(gf, bf));
    const deltaMaxMin = max - min;

    let h, s;
    let l = (max + min) / 2;

    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;
        } else {
            h = ((rf - gf) / deltaMaxMin) + 4;
        }

        s = deltaMaxMin / (1 - Math.abs(2 * l - 1));
    }

    return [(h * 60) % 360, s, l];
}

function quantizeFromRgb888 (color) {
    let r = modifyWordWidth((color >> 16) & 0xFF, 8, QUANTIZE_WORD_WIDTH);
    let g = modifyWordWidth((color >> 8) & 0xFF, 8, QUANTIZE_WORD_WIDTH);
    let b = modifyWordWidth(color & 0xFF, 8, QUANTIZE_WORD_WIDTH);
    return r << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) | g << QUANTIZE_WORD_WIDTH | b;
}

function approximateToRgb888 (r, g, b) {
    return (0xFF << 24) | modifyWordWidth(r, QUANTIZE_WORD_WIDTH, 8) << 16
            | modifyWordWidth(g, QUANTIZE_WORD_WIDTH, 8) << 8
            | modifyWordWidth(b, QUANTIZE_WORD_WIDTH, 8);
}

function approximateToRgb888Color (color) {
    return approximateToRgb888(quantizedRed(color), quantizedGreen(color), quantizedBlue(color));
}

function quantizedRed (color) {
    return (color >> (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH)) & QUANTIZE_WORD_MASK;
}

function quantizedGreen (color) {
    return (color >> QUANTIZE_WORD_WIDTH) & QUANTIZE_WORD_MASK;
}

function quantizedBlue (color) {
    return color & QUANTIZE_WORD_MASK;
}

function modifyWordWidth (value, currentWidth, targetWidth) {
    let newValue;
    if (targetWidth > currentWidth) {
        newValue = value << (targetWidth - currentWidth);
    } else {
        newValue = value >> (currentWidth - targetWidth);
    }
    return newValue & ((1 << targetWidth) - 1);
}

package.json

{
    "name": "palettejs",
    "version": "0.0.1",
    "dependencies": {
        "fastpriorityqueue": "^0.3.1"
    }
}

palette.js

import Target from './target';
import ColorCutQuantizer from './color-cut-quantizer';

const DEFAULT_RESIZE_BITMAP_AREA = 112 * 112;
const DEFAULT_CALCULATE_NUMBER_COLORS = 16;

const MIN_CONTRAST_TITLE_TEXT = 3.0;
const MIN_CONTRAST_BODY_TEXT = 4.5;

export function from (src) {
    if (src instanceof Array) {
        return new Builder(src).generate();
    }

    return new Builder(src);
}

export default class Palette {
    constructor (swatches, targets) {
        this.swatches = swatches;
        this.targets = targets;

        this.usedColors = [];
        this.selectedSwatches = new Map();

        this.dominantSwatch = findDominantSwatch();
    }

    get swatches () {
        return this.swatches; // fixme, immutable
    }

    get targets () {
        return this.targets; // fixme, immutable
    }
}

class Builder {
    constructor (src) {
        if (!src) {
            throw new Error('Source is not valid');
        }
        this.filters = [DEFAULT_FILTER];
        this.targets = [];
        this.maxColors = DEFAULT_CALCULATE_NUMBER_COLORS;
        this.resizeArea = DEFAULT_RESIZE_BITMAP_AREA;
        this.resizeMaxDimension = -1;

        if (src instanceof Array) {
            if (src.length == 0) {
                throw new Error('List of Swatches is not valid');
            }
            this.swatches = src;
            this.bitmap = null;
        } else {
            this.bitmap = src;
            this.swatches = null;

            this.targets.push(Target.LIGHT_VIBRANT);
            this.targets.push(Target.VIBRANT);
            this.targets.push(Target.DARK_VIBRANT);
            this.targets.push(Target.LIGHT_MUTED);
            this.targets.push(Target.MUTED);
            this.targets.push(Target.DARK_MUTED);
        }
    }

    maximumColorCount (colors) {
        this.maxColors = colors;
        return this;
    }

    resizeBitmapSize (maxDimension) {
        this.resizeMaxDimension = maxDimension;
        this.resizeArea = -1;
        return this;
    }

    resizeBitmapArea (area) {
        this.resizeArea = area;
        this.resizeMaxDimension = -1;
        return this;
    }

    clearFilters () {
        this.filters = [];
        return this;
    }

    addFilter (filter) {
        if (filter) {
            this.filters.push(filter);
        }
        return this;
    }

    setRegion (left, top, right, bottom) {
        if (this.bitmap != null) {
            if (! this.region) {
                this.region = new Rect();
            }
            this.region.set(0, 0, this.bitmap.getWidth(), this.bitmap.getHeight());
            if (!this.region.intersect(left, top, right, bottom)) {
                throw new Error('The given region must intersect with the Bitmap\'s dimensions.');
            }
        }
        return this;
    }

    clearRegion () {
        this.region = null;
        return this;
    }

    addTarget (target) {
        if (target && !this.targets.includes(target)) {
            this.targets.push(target);
        }
        return this;
    }

    clearTargets () {
        this.targets = [];
        return this;
    }

    generate () {
        let swatches;

        if (this.bitmap != null) {
            let bitmap = scaleBitmapDown(this.bitmap);

            const region = this.region;
            if (bitmap != this.bitmap && region != null) {
                const scale = bitmap.getWidth() / this.bitmap.getWidth();
                region.left = Math.floor(region.left * scale);
                region.top = Math.floor(region.top * scale);
                region.right = Math.min(Math.ceil(region.right * scale), bitmap.getWidth());
                region.bottom = Math.min(Math.ceil(region.bottom * scale), bitmap.getHeight());
            }

            const quantizer = new ColorCutQuantizer(getPixelsFromBitmap(bitmap), this.maxColors, this.filters);

            if (bitmap != this.bitmap) {
                delete bitmap;
            }

            swatches = quantizer.quantizedColors;
        } else {
            swatches = this.swatches;
        }

        const p = new Palette(swatches, this.targets);
        p.generate();

        return p;
    }

    generateAsync () {
        return new Promise((resolve, reject) => {
            try {
                resolve(generate());
            } catch(e) {
                reject(e);
            }
        });
    }
}

export class Swatch {

}

class Rect {
    get width () {
        return this.right - this.left;
    }

    get height () {
        return this.bottom - this.top;
    }

    set (left, top, right, bottom) {
        this.left = left;
        this.top = top;
        this.right = right;
        this.bottom = bottom;
    }

    intersect (left, top, right, bottom) {
        if (this.left < right && left < this.right && this.top < bottom && top < this.bottom) {
            if (this.left < left) {
                this.left = left;
            }
            if (this.top < top) {
                this.top = top;
            }
            if (this.right < right) {
                this.right = right;
            }
            if (this.bottom < bottom) {
                this.bottom = bottom;
            }
            return true;
        }
        return false;
    }
}

target.js

const TARGET_DARK_LUMA = 0.26;
const MAX_DARK_LUMA = 0.45;

const MIN_LIGHT_LUMA = 0.55;
const TARGET_LIGHT_LUMA = 0.74;

const MIN_NORMAL_LUMA = 0.3;
const TARGET_NORMAL_LUMA = 0.5;
const MAX_NORMAL_LUMA = 0.7;

const TARGET_MUTED_SATURATION = 0.3;
const MAX_MUTED_SATURATION = 0.4;

const TARGET_VIBRANT_SATURATION = 1;
const MIN_VIBRANT_SATURATION = 0.35;

const WEIGHT_SATURATION = 0.24;
const WEIGHT_LUMA = 0.52;
const WEIGHT_POPULATION = 0.24;

export const LIGHT_VIBRANT = new Target();
setDefaultLightLightnessValues(LIGHT_VIBRANT);
setDefaultVibrantSaturationValues(LIGHT_VIBRANT);

export const VIBRANT = new Target();
setDefaultNormalLightnessValues(VIBRANT);
setDefaultVibrantSaturationValues(VIBRANT);

export const DARK_VIBRANT = new Target();
setDefaultDarkLightnessValues(DARK_VIBRANT);
setDefaultVibrantSaturationValues(DARK_VIBRANT);

export const LIGHT_MUTED = new Target();
setDefaultLightLightnessValues(LIGHT_MUTED);
setDefaultMutedSaturationValues(LIGHT_MUTED);

export const MUTED = new Target();
setDefaultNormalLightnessValues(MUTED);
setDefaultMutedSaturationValues(MUTED);

export const DARK_MUTED = new Target();
setDefaultDarkLightnessValues(DARK_MUTED);
setDefaultMutedSaturationValues(DARK_MUTED);

class Target {
    constructor () {
        this.saturationTargets = new Float32Array([0.0, 0.5, 1.0]);
        this.lightnessTargets = new Float32Array([0.0, 0.5, 1.0]);
        this.weights = new Float32Array([WEIGHT_SATURATION, WEIGHT_LUMA, WEIGHT_POPULATION]);
        this.isExclusive = true;
    }

    get minimumSaturation () {
        return this.saturationTargets[0];
    }

    get targetSaturation () {
        return this.saturationTargets[1];
    }

    get maximumSaturation () {
        return this.saturationTargets[2];
    }

    get minimumLightness () {
        return this.lightnessTargets[0];
    }

    get targetLightness () {
        return this.lightnessTargets[1];
    }

    get maximumLightness () {
        return this.lightnessTargets[2];
    }

    get saturationWeight () {
        return this.weights[0];
    }

    get lightessWeight () {
        return this.weights[1];
    }

    get populationWeight () {
        return this.weights[2];
    }

    get isExclusive () {
        return this.isExclusive;
    }

    normalizeWeights () {
        let sum = 0.0;
        for (let i = 0, z = this.weights.length; i < z; i++) {
            let weight = this.weights[i];
            if (weight > 0) {
                sum += weight;
            }
        }
        if (sum != 0.0) {
            for (let i = 0, z = this.weights.length; i < z; i++) {
                if (this.weights[i] > 0) {
                    this.weights[i] /= sum;
                }
            }
        }
    }
}

function setDefaultDarkLightnessValues (target) {
    target.lightnessTargets[1] = TARGET_DARK_LUMA;
    target.lightnessTargets[2] = MAX_DARK_LUMA;
}

function setDefaultNormalLightnessValues (target) {
    target.lightnessTargets[0] = MIN_NORMAL_LUMA;
    target.lightnessTargets[1] = TARGET_NORMAL_LUMA;
    target.lightnessTargets[2] = MAX_NORMAL_LUMA;
}

function setDefaultLightLightnessValues (target) {
    target.lightnessTargets[0] = MIN_LIGHT_LUMA;
    target.lightnessTargets[1] = TARGET_LIGHT_LUMA;
}

function setDefaultVibrantSaturationValues (target) {
    target.saturationTargets[0] = MIN_VIBRANT_SATURATION;
    target.saturationTargets[1] = TARGET_VIBRANT_SATURATION;
}

function setDefaultMutedSaturationValues (target) {
    target.saturationTargets[1] = TARGET_MUTED_SATURATION;
    target.saturationTargets[2] = MAX_MUTED_SATURATION;
}

export class Builder {
    constructor (other = null) {
        this.target = new Target();
        if (other != null) {
            this.target.saturationTargets = other.saturationTargets.slice(0);
            this.target.lightnessTargets = other.lightnessTargets.slice(0);
            this.target.weights = other.weights.slice(0);
        }
    }

    setMinimumSaturation (value) {
        this.target.saturationTargets[0] = value;
        return this;
    }

    setTargetSaturation (value) {
        this.target.saturationTargets[1] = value;
        return this;
    }

    setMaximumSaturation (value) {
        this.target.saturationTargets[2] = value;
        return this;
    }

    setMinimumLightness (value) {
        this.target.lightnessTargets[0] = value;
        return this;
    }

    setTargetLightness (value) {
        this.target.lightnessTargets[1] = value;
        return this;
    }

    setMaximumLightness (value) {
        this.target.lightnessTargets[2] = value;
        return this;
    }

    setSaturationWeight (weight) {
        this.target.weights[0] = weight;
        return this;
    }

    setLightnessWeight (weight) {
        this.target.weights[1] = weight;
        return this;
    }

    setPopulationWeight (weight) {
        this.target.weights[2] = weight;
        return this;
    }

    setExclusive (exclusive) {
        this.target.isExclusive = exclusive;
        return this;
    }

    build () {
        return this.target;
    }
}