diff options
author | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
---|---|---|
committer | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
commit | 5f8de423f190bbb79a62f804151bc24824fa32d8 (patch) | |
tree | 10027f336435511475e392454359edea8e25895d /toolkit/components/places/ColorAnalyzer_worker.js | |
parent | 49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff) | |
download | UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip |
Add m-esr52 at 52.6.0
Diffstat (limited to 'toolkit/components/places/ColorAnalyzer_worker.js')
-rw-r--r-- | toolkit/components/places/ColorAnalyzer_worker.js | 392 |
1 files changed, 392 insertions, 0 deletions
diff --git a/toolkit/components/places/ColorAnalyzer_worker.js b/toolkit/components/places/ColorAnalyzer_worker.js new file mode 100644 index 000000000..01fce0637 --- /dev/null +++ b/toolkit/components/places/ColorAnalyzer_worker.js @@ -0,0 +1,392 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +"use strict"; + +importScripts("ClusterLib.js", "ColorConversion.js"); + +// Offsets in the ImageData pixel array to reach pixel colors +const PIXEL_RED = 0; +const PIXEL_GREEN = 1; +const PIXEL_BLUE = 2; +const PIXEL_ALPHA = 3; + +// Number of components in one ImageData pixel (RGBA) +const NUM_COMPONENTS = 4; + +// Shift a color represented as a 24 bit integer by N bits to get a component +const RED_SHIFT = 16; +const GREEN_SHIFT = 8; + +// Only run the N most frequent unique colors through the clustering algorithm +// Images with more than this many unique colors will have reduced accuracy. +const MAX_COLORS_TO_MERGE = 500; + +// Each cluster of colors has a mean color in the Lab color space. +// If the euclidean distance between the means of two clusters is greater +// than or equal to this threshold, they won't be merged. +const MERGE_THRESHOLD = 12; + +// The highest the distance handicap can be for large clusters +const MAX_SIZE_HANDICAP = 5; +// If the handicap is below this number, it is cut off to zero +const SIZE_HANDICAP_CUTOFF = 2; + +// If potential background colors deviate from the mean background color by +// this threshold or greater, finding a background color will fail +const BACKGROUND_THRESHOLD = 10; + +// Alpha component of colors must be larger than this in order to make it into +// the clustering algorithm or be considered a background color (0 - 255). +const MIN_ALPHA = 25; + +// The euclidean distance in the Lab color space under which merged colors +// are weighted lower for being similar to the background color +const BACKGROUND_WEIGHT_THRESHOLD = 15; + +// The range in which color chroma differences will affect desirability. +// Colors with chroma outside of the range take on the desirability of +// their nearest extremes. Should be roughly 0 - 150. +const CHROMA_WEIGHT_UPPER = 90; +const CHROMA_WEIGHT_LOWER = 1; +const CHROMA_WEIGHT_MIDDLE = (CHROMA_WEIGHT_UPPER + CHROMA_WEIGHT_LOWER) / 2; + +/** + * When we receive a message from the outside world, find the representative + * colors of the given image. The colors will be posted back to the caller + * through the "colors" property on the event data object as an array of + * integers. Colors of lower indices are more representative. + * This array can be empty if this worker can't find a color. + * + * @param event + * A MessageEvent whose data should have the following properties: + * imageData - A DOM ImageData instance to analyze + * maxColors - The maximum number of representative colors to find, + * defaults to 1 if not provided + */ +onmessage = function(event) { + let imageData = event.data.imageData; + let pixels = imageData.data; + let width = imageData.width; + let height = imageData.height; + let maxColors = event.data.maxColors; + if (typeof(maxColors) != "number") { + maxColors = 1; + } + + let allColors = getColors(pixels, width, height); + + // Only merge top colors by frequency for speed. + let mergedColors = mergeColors(allColors.slice(0, MAX_COLORS_TO_MERGE), + width * height, MERGE_THRESHOLD); + + let backgroundColor = getBackgroundColor(pixels, width, height); + + mergedColors = mergedColors.map(function(cluster) { + // metadata holds a bunch of information about the color represented by + // this cluster + let metadata = cluster.item; + + // the basis of color desirability is how much of the image the color is + // responsible for, but we'll need to weigh this number differently + // depending on other factors + metadata.desirability = metadata.ratio; + let weight = 1; + + // if the color is close to the background color, we don't want it + if (backgroundColor != null) { + let backgroundDistance = labEuclidean(metadata.mean, backgroundColor); + if (backgroundDistance < BACKGROUND_WEIGHT_THRESHOLD) { + weight = backgroundDistance / BACKGROUND_WEIGHT_THRESHOLD; + } + } + + // prefer more interesting colors, but don't knock low chroma colors + // completely out of the running (lower bound), and we don't really care + // if a color is slightly more intense than another on the higher end + let chroma = labChroma(metadata.mean); + if (chroma < CHROMA_WEIGHT_LOWER) { + chroma = CHROMA_WEIGHT_LOWER; + } else if (chroma > CHROMA_WEIGHT_UPPER) { + chroma = CHROMA_WEIGHT_UPPER; + } + weight *= chroma / CHROMA_WEIGHT_MIDDLE; + + metadata.desirability *= weight; + return metadata; + }); + + // only send back the most desirable colors + mergedColors.sort(function(a, b) { + return b.desirability != a.desirability ? b.desirability - a.desirability : b.color - a.color; + }); + mergedColors = mergedColors.map(function(metadata) { + return metadata.color; + }).slice(0, maxColors); + postMessage({ colors: mergedColors }); +}; + +/** + * Given the pixel data and dimensions of an image, return an array of objects + * associating each unique color and its frequency in the image, sorted + * descending by frequency. Sufficiently transparent colors are ignored. + * + * @param pixels + * Pixel data array for the image to get colors from (ImageData.data). + * @param width + * Width of the image, in # of pixels. + * @param height + * Height of the image, in # of pixels. + * + * @return An array of objects with color and freq properties, sorted + * descending by freq + */ +function getColors(pixels, width, height) { + let colorFrequency = {}; + for (let x = 0; x < width; x++) { + for (let y = 0; y < height; y++) { + let offset = (x * NUM_COMPONENTS) + (y * NUM_COMPONENTS * width); + + if (pixels[offset + PIXEL_ALPHA] < MIN_ALPHA) { + continue; + } + + let color = pixels[offset + PIXEL_RED] << RED_SHIFT + | pixels[offset + PIXEL_GREEN] << GREEN_SHIFT + | pixels[offset + PIXEL_BLUE]; + + if (color in colorFrequency) { + colorFrequency[color]++; + } else { + colorFrequency[color] = 1; + } + } + } + + let colors = []; + for (var color in colorFrequency) { + colors.push({ color: +color, freq: colorFrequency[+color] }); + } + colors.sort(descendingFreqSort); + return colors; +} + +/** + * Given an array of objects from getColors, the number of pixels in the + * image, and a merge threshold, run the clustering algorithm on the colors + * and return the set of merged clusters. + * + * @param colorFrequencies + * An array of objects from getColors to cluster + * @param numPixels + * The number of pixels in the image + * @param threshold + * The maximum distance between two clusters for which those clusters + * can be merged. + * + * @return An array of merged clusters + * + * @see clusterlib.hcluster + * @see getColors + */ +function mergeColors(colorFrequencies, numPixels, threshold) { + let items = colorFrequencies.map(function(colorFrequency) { + let color = colorFrequency.color; + let freq = colorFrequency.freq; + return { + mean: rgb2lab(color >> RED_SHIFT, color >> GREEN_SHIFT & 0xff, + color & 0xff), + // the canonical color of the cluster + // (one w/ highest freq or closest to mean) + color: color, + colors: [color], + highFreq: freq, + highRatio: freq / numPixels, + // the individual color w/ the highest frequency in this cluster + highColor: color, + // ratio of image taken up by colors in this cluster + ratio: freq / numPixels, + freq: freq, + }; + }); + + let merged = clusterlib.hcluster(items, distance, merge, threshold); + return merged; +} + +function descendingFreqSort(a, b) { + return b.freq != a.freq ? b.freq - a.freq : b.color - a.color; +} + +/** + * Given two items for a pair of clusters (as created in mergeColors above), + * determine the distance between them so we know if we should merge or not. + * Uses the euclidean distance between their mean colors in the lab color + * space, weighted so larger items are harder to merge. + * + * @param item1 + * The first item to compare + * @param item2 + * The second item to compare + * + * @return The distance between the two items + */ +function distance(item1, item2) { + // don't cluster large blocks of color unless they're really similar + let minRatio = Math.min(item1.ratio, item2.ratio); + let dist = labEuclidean(item1.mean, item2.mean); + let handicap = Math.min(MAX_SIZE_HANDICAP, dist * minRatio); + if (handicap <= SIZE_HANDICAP_CUTOFF) { + handicap = 0; + } + return dist + handicap; +} + +/** + * Find the euclidean distance between two colors in the Lab color space. + * + * @param color1 + * The first color to compare + * @param color2 + * The second color to compare + * + * @return The euclidean distance between the two colors + */ +function labEuclidean(color1, color2) { + return Math.sqrt( + Math.pow(color2.lightness - color1.lightness, 2) + + Math.pow(color2.a - color1.a, 2) + + Math.pow(color2.b - color1.b, 2)); +} + +/** + * Given items from two clusters we know are appropriate for merging, + * merge them together into a third item such that its metadata describes both + * input items. The "color" property is set to the color in the new item that + * is closest to its mean color. + * + * @param item1 + * The first item to merge + * @param item2 + * The second item to merge + * + * @return An item that represents the merging of the given items + */ +function merge(item1, item2) { + let lab1 = item1.mean; + let lab2 = item2.mean; + + /* algorithm tweak point - weighting the mean of the cluster */ + let num1 = item1.freq; + let num2 = item2.freq; + + let total = num1 + num2; + + let mean = { + lightness: (lab1.lightness * num1 + lab2.lightness * num2) / total, + a: (lab1.a * num1 + lab2.a * num2) / total, + b: (lab1.b * num1 + lab2.b * num2) / total + }; + + let colors = item1.colors.concat(item2.colors); + + // get the canonical color of the new cluster + let color; + let avgFreq = colors.length / (item1.freq + item2.freq); + if ((item1.highFreq > item2.highFreq) && (item1.highFreq > avgFreq * 2)) { + color = item1.highColor; + } else if (item2.highFreq > avgFreq * 2) { + color = item2.highColor; + } else { + // if there's no stand-out color + let minDist = Infinity, closest = 0; + for (let i = 0; i < colors.length; i++) { + let color = colors[i]; + let lab = rgb2lab(color >> RED_SHIFT, color >> GREEN_SHIFT & 0xff, + color & 0xff); + let dist = labEuclidean(lab, mean); + if (dist < minDist) { + minDist = dist; + closest = i; + } + } + color = colors[closest]; + } + + const higherItem = item1.highFreq > item2.highFreq ? item1 : item2; + + return { + mean: mean, + color: color, + highFreq: higherItem.highFreq, + highColor: higherItem.highColor, + highRatio: higherItem.highRatio, + ratio: item1.ratio + item2.ratio, + freq: item1.freq + item2.freq, + colors: colors, + }; +} + +/** + * Find the background color of the given image. + * + * @param pixels + * The pixel data for the image (an array of component integers) + * @param width + * The width of the image + * @param height + * The height of the image + * + * @return The background color of the image as a Lab object, or null if we + * can't determine the background color + */ +function getBackgroundColor(pixels, width, height) { + // we'll assume that if the four corners are roughly the same color, + // then that's the background color + let coordinates = [[0, 0], [width - 1, 0], [width - 1, height - 1], + [0, height - 1]]; + + // find the corner colors in LAB + let cornerColors = []; + for (let i = 0; i < coordinates.length; i++) { + let offset = (coordinates[i][0] * NUM_COMPONENTS) + + (coordinates[i][1] * NUM_COMPONENTS * width); + if (pixels[offset + PIXEL_ALPHA] < MIN_ALPHA) { + // we can't make very accurate judgements below this opacity + continue; + } + cornerColors.push(rgb2lab(pixels[offset + PIXEL_RED], + pixels[offset + PIXEL_GREEN], + pixels[offset + PIXEL_BLUE])); + } + + // we want at least two points at acceptable alpha levels + if (cornerColors.length <= 1) { + return null; + } + + // find the average color among the corners + let averageColor = { lightness: 0, a: 0, b: 0 }; + cornerColors.forEach(function(color) { + for (let i in color) { + averageColor[i] += color[i]; + } + }); + for (let i in averageColor) { + averageColor[i] /= cornerColors.length; + } + + // if we have fewer points due to low alpha, they need to be closer together + let threshold = BACKGROUND_THRESHOLD + * (cornerColors.length / coordinates.length); + + // if any of the corner colors deviate enough from the average, they aren't + // similar enough to be considered the background color + for (let cornerColor of cornerColors) { + if (labEuclidean(cornerColor, averageColor) > threshold) { + return null; + } + } + return averageColor; +} |