| /* |
| * Copyright (C) 2017 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License |
| */ |
| |
| package com.android.internal.graphics.palette; |
| |
| /* |
| * Copyright 2014 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| import android.graphics.Color; |
| import android.util.TimingLogger; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.List; |
| import java.util.PriorityQueue; |
| |
| import com.android.internal.graphics.ColorUtils; |
| import com.android.internal.graphics.palette.Palette.Swatch; |
| |
| /** |
| * Copied from: frameworks/support/v7/palette/src/main/java/android/support/v7/ |
| * graphics/ColorCutQuantizer.java |
| * |
| * An color quantizer based on the Median-cut algorithm, but optimized for picking out distinct |
| * colors rather than representation colors. |
| * |
| * The color space is represented as a 3-dimensional cube with each dimension being an RGB |
| * component. The cube is then repeatedly divided until we have reduced the color space to the |
| * requested number of colors. An average color is then generated from each cube. |
| * |
| * What makes this different to median-cut is that median-cut divided cubes so that all of the cubes |
| * have roughly the same population, where this quantizer divides boxes based on their color volume. |
| * This means that the color space is divided into distinct colors, rather than representative |
| * colors. |
| */ |
| final class ColorCutQuantizer { |
| |
| private static final String LOG_TAG = "ColorCutQuantizer"; |
| private static final boolean LOG_TIMINGS = false; |
| |
| static final int COMPONENT_RED = -3; |
| static final int COMPONENT_GREEN = -2; |
| static final int COMPONENT_BLUE = -1; |
| |
| private static final int QUANTIZE_WORD_WIDTH = 5; |
| private static final int QUANTIZE_WORD_MASK = (1 << QUANTIZE_WORD_WIDTH) - 1; |
| |
| final int[] mColors; |
| final int[] mHistogram; |
| final List<Swatch> mQuantizedColors; |
| final TimingLogger mTimingLogger; |
| final Palette.Filter[] mFilters; |
| |
| private final float[] mTempHsl = new float[3]; |
| |
| /** |
| * Constructor. |
| * |
| * @param pixels histogram representing an image's pixel data |
| * @param maxColors The maximum number of colors that should be in the result palette. |
| * @param filters Set of filters to use in the quantization stage |
| */ |
| ColorCutQuantizer(final int[] pixels, final int maxColors, final Palette.Filter[] filters) { |
| mTimingLogger = LOG_TIMINGS ? new TimingLogger(LOG_TAG, "Creation") : null; |
| mFilters = filters; |
| |
| final int[] hist = mHistogram = new int[1 << (QUANTIZE_WORD_WIDTH * 3)]; |
| for (int i = 0; i < pixels.length; i++) { |
| final int quantizedColor = quantizeFromRgb888(pixels[i]); |
| // Now update the pixel value to the quantized value |
| pixels[i] = quantizedColor; |
| // And update the histogram |
| hist[quantizedColor]++; |
| } |
| |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("Histogram created"); |
| } |
| |
| // Now let's count the number of distinct colors |
| int distinctColorCount = 0; |
| for (int color = 0; color < hist.length; color++) { |
| if (hist[color] > 0 && shouldIgnoreColor(color)) { |
| // If we should ignore the color, set the population to 0 |
| hist[color] = 0; |
| } |
| if (hist[color] > 0) { |
| // If the color has population, increase the distinct color count |
| distinctColorCount++; |
| } |
| } |
| |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("Filtered colors and distinct colors counted"); |
| } |
| |
| // Now lets go through create an array consisting of only distinct colors |
| final int[] colors = mColors = new int[distinctColorCount]; |
| int distinctColorIndex = 0; |
| for (int color = 0; color < hist.length; color++) { |
| if (hist[color] > 0) { |
| colors[distinctColorIndex++] = color; |
| } |
| } |
| |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("Distinct colors copied into array"); |
| } |
| |
| if (distinctColorCount <= maxColors) { |
| // The image has fewer colors than the maximum requested, so just return the colors |
| mQuantizedColors = new ArrayList<>(); |
| for (int color : colors) { |
| mQuantizedColors.add(new Swatch(approximateToRgb888(color), hist[color])); |
| } |
| |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("Too few colors present. Copied to Swatches"); |
| mTimingLogger.dumpToLog(); |
| } |
| } else { |
| // We need use quantization to reduce the number of colors |
| mQuantizedColors = quantizePixels(maxColors); |
| |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("Quantized colors computed"); |
| mTimingLogger.dumpToLog(); |
| } |
| } |
| } |
| |
| /** |
| * @return the list of quantized colors |
| */ |
| List<Swatch> getQuantizedColors() { |
| return mQuantizedColors; |
| } |
| |
| private List<Swatch> quantizePixels(int maxColors) { |
| // Create the priority queue which is sorted by volume descending. This means we always |
| // split the largest box in the queue |
| final PriorityQueue<Vbox> pq = new PriorityQueue<>(maxColors, VBOX_COMPARATOR_VOLUME); |
| |
| // To start, offer a box which contains all of the colors |
| pq.offer(new Vbox(0, mColors.length - 1)); |
| |
| // Now go through the boxes, splitting them until we have reached maxColors or there are no |
| // more boxes to split |
| splitBoxes(pq, maxColors); |
| |
| // Finally, return the average colors of the color boxes |
| return generateAverageColors(pq); |
| } |
| |
| /** |
| * Iterate through the {@link java.util.Queue}, popping |
| * {@link ColorCutQuantizer.Vbox} objects from the queue |
| * and splitting them. Once split, the new box and the remaining box are offered back to the |
| * queue. |
| * |
| * @param queue {@link java.util.PriorityQueue} to poll for boxes |
| * @param maxSize Maximum amount of boxes to split |
| */ |
| private void splitBoxes(final PriorityQueue<Vbox> queue, final int maxSize) { |
| while (queue.size() < maxSize) { |
| final Vbox vbox = queue.poll(); |
| |
| if (vbox != null && vbox.canSplit()) { |
| // First split the box, and offer the result |
| queue.offer(vbox.splitBox()); |
| |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("Box split"); |
| } |
| // Then offer the box back |
| queue.offer(vbox); |
| } else { |
| if (LOG_TIMINGS) { |
| mTimingLogger.addSplit("All boxes split"); |
| } |
| // If we get here then there are no more boxes to split, so return |
| return; |
| } |
| } |
| } |
| |
| private List<Swatch> generateAverageColors(Collection<Vbox> vboxes) { |
| ArrayList<Swatch> colors = new ArrayList<>(vboxes.size()); |
| for (Vbox vbox : vboxes) { |
| Swatch swatch = vbox.getAverageColor(); |
| if (!shouldIgnoreColor(swatch)) { |
| // As we're averaging a color box, we can still get colors which we do not want, so |
| // we check again here |
| colors.add(swatch); |
| } |
| } |
| return colors; |
| } |
| |
| /** |
| * Represents a tightly fitting box around a color space. |
| */ |
| private class Vbox { |
| // lower and upper index are inclusive |
| private int mLowerIndex; |
| private int mUpperIndex; |
| // Population of colors within this box |
| private int mPopulation; |
| |
| private int mMinRed, mMaxRed; |
| private int mMinGreen, mMaxGreen; |
| private int mMinBlue, mMaxBlue; |
| |
| Vbox(int lowerIndex, int upperIndex) { |
| mLowerIndex = lowerIndex; |
| mUpperIndex = upperIndex; |
| fitBox(); |
| } |
| |
| final int getVolume() { |
| return (mMaxRed - mMinRed + 1) * (mMaxGreen - mMinGreen + 1) * |
| (mMaxBlue - mMinBlue + 1); |
| } |
| |
| final boolean canSplit() { |
| return getColorCount() > 1; |
| } |
| |
| final int getColorCount() { |
| return 1 + mUpperIndex - mLowerIndex; |
| } |
| |
| /** |
| * Recomputes the boundaries of this box to tightly fit the colors within the box. |
| */ |
| final void fitBox() { |
| final int[] colors = mColors; |
| final int[] hist = mHistogram; |
| |
| // Reset the min and max to opposite values |
| int minRed, minGreen, minBlue; |
| minRed = minGreen = minBlue = Integer.MAX_VALUE; |
| int maxRed, maxGreen, maxBlue; |
| maxRed = maxGreen = maxBlue = Integer.MIN_VALUE; |
| int count = 0; |
| |
| for (int i = mLowerIndex; i <= mUpperIndex; i++) { |
| final int color = colors[i]; |
| count += hist[color]; |
| |
| final int r = quantizedRed(color); |
| final int g = quantizedGreen(color); |
| final int 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; |
| } |
| } |
| |
| mMinRed = minRed; |
| mMaxRed = maxRed; |
| mMinGreen = minGreen; |
| mMaxGreen = maxGreen; |
| mMinBlue = minBlue; |
| mMaxBlue = maxBlue; |
| mPopulation = count; |
| } |
| |
| /** |
| * Split this color box at the mid-point along its longest dimension |
| * |
| * @return the new ColorBox |
| */ |
| final Vbox splitBox() { |
| if (!canSplit()) { |
| throw new IllegalStateException("Can not split a box with only 1 color"); |
| } |
| |
| // find median along the longest dimension |
| final int splitPoint = findSplitPoint(); |
| |
| Vbox newBox = new Vbox(splitPoint + 1, mUpperIndex); |
| |
| // Now change this box's upperIndex and recompute the color boundaries |
| mUpperIndex = splitPoint; |
| fitBox(); |
| |
| return newBox; |
| } |
| |
| /** |
| * @return the dimension which this box is largest in |
| */ |
| final int getLongestColorDimension() { |
| final int redLength = mMaxRed - mMinRed; |
| final int greenLength = mMaxGreen - mMinGreen; |
| final int blueLength = mMaxBlue - mMinBlue; |
| |
| if (redLength >= greenLength && redLength >= blueLength) { |
| return COMPONENT_RED; |
| } else if (greenLength >= redLength && greenLength >= blueLength) { |
| return COMPONENT_GREEN; |
| } else { |
| return COMPONENT_BLUE; |
| } |
| } |
| |
| /** |
| * Finds the point within this box's lowerIndex and upperIndex index of where to split. |
| * |
| * This is calculated by finding the longest color dimension, and then sorting the |
| * sub-array based on that dimension value in each color. The colors are then iterated over |
| * until a color is found with at least the midpoint of the whole box's dimension midpoint. |
| * |
| * @return the index of the colors array to split from |
| */ |
| final int findSplitPoint() { |
| final int longestDimension = getLongestColorDimension(); |
| final int[] colors = mColors; |
| final int[] hist = mHistogram; |
| |
| // We need to sort the colors in this box based on the longest color dimension. |
| // As we can't use a Comparator to define the sort logic, we modify each color so that |
| // its most significant is the desired dimension |
| modifySignificantOctet(colors, longestDimension, mLowerIndex, mUpperIndex); |
| |
| // Now sort... Arrays.sort uses a exclusive toIndex so we need to add 1 |
| Arrays.sort(colors, mLowerIndex, mUpperIndex + 1); |
| |
| // Now revert all of the colors so that they are packed as RGB again |
| modifySignificantOctet(colors, longestDimension, mLowerIndex, mUpperIndex); |
| |
| final int midPoint = mPopulation / 2; |
| for (int i = mLowerIndex, count = 0; i <= mUpperIndex; i++) { |
| count += hist[colors[i]]; |
| if (count >= midPoint) { |
| // we never want to split on the upperIndex, as this will result in the same |
| // box |
| return Math.min(mUpperIndex - 1, i); |
| } |
| } |
| |
| return mLowerIndex; |
| } |
| |
| /** |
| * @return the average color of this box. |
| */ |
| final Swatch getAverageColor() { |
| final int[] colors = mColors; |
| final int[] hist = mHistogram; |
| int redSum = 0; |
| int greenSum = 0; |
| int blueSum = 0; |
| int totalPopulation = 0; |
| |
| for (int i = mLowerIndex; i <= mUpperIndex; i++) { |
| final int color = colors[i]; |
| final int colorPopulation = hist[color]; |
| |
| totalPopulation += colorPopulation; |
| redSum += colorPopulation * quantizedRed(color); |
| greenSum += colorPopulation * quantizedGreen(color); |
| blueSum += colorPopulation * quantizedBlue(color); |
| } |
| |
| final int redMean = Math.round(redSum / (float) totalPopulation); |
| final int greenMean = Math.round(greenSum / (float) totalPopulation); |
| final int blueMean = Math.round(blueSum / (float) totalPopulation); |
| |
| return new Swatch(approximateToRgb888(redMean, greenMean, blueMean), totalPopulation); |
| } |
| } |
| |
| /** |
| * Modify the significant octet in a packed color int. Allows sorting based on the value of a |
| * single color component. This relies on all components being the same word size. |
| * |
| * @see Vbox#findSplitPoint() |
| */ |
| static void modifySignificantOctet(final int[] a, final int dimension, |
| final int lower, final int upper) { |
| switch (dimension) { |
| case COMPONENT_RED: |
| // Already in RGB, no need to do anything |
| break; |
| case COMPONENT_GREEN: |
| // We need to do a RGB to GRB swap, or vice-versa |
| for (int i = lower; i <= upper; i++) { |
| final int color = a[i]; |
| a[i] = quantizedGreen(color) << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) |
| | quantizedRed(color) << QUANTIZE_WORD_WIDTH |
| | quantizedBlue(color); |
| } |
| break; |
| case COMPONENT_BLUE: |
| // We need to do a RGB to BGR swap, or vice-versa |
| for (int i = lower; i <= upper; i++) { |
| final int color = a[i]; |
| a[i] = quantizedBlue(color) << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) |
| | quantizedGreen(color) << QUANTIZE_WORD_WIDTH |
| | quantizedRed(color); |
| } |
| break; |
| } |
| } |
| |
| private boolean shouldIgnoreColor(int color565) { |
| final int rgb = approximateToRgb888(color565); |
| ColorUtils.colorToHSL(rgb, mTempHsl); |
| return shouldIgnoreColor(rgb, mTempHsl); |
| } |
| |
| private boolean shouldIgnoreColor(Swatch color) { |
| return shouldIgnoreColor(color.getRgb(), color.getHsl()); |
| } |
| |
| private boolean shouldIgnoreColor(int rgb, float[] hsl) { |
| if (mFilters != null && mFilters.length > 0) { |
| for (int i = 0, count = mFilters.length; i < count; i++) { |
| if (!mFilters[i].isAllowed(rgb, hsl)) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Comparator which sorts {@link Vbox} instances based on their volume, in descending order |
| */ |
| private static final Comparator<Vbox> VBOX_COMPARATOR_VOLUME = new Comparator<Vbox>() { |
| @Override |
| public int compare(Vbox lhs, Vbox rhs) { |
| return rhs.getVolume() - lhs.getVolume(); |
| } |
| }; |
| |
| /** |
| * Quantized a RGB888 value to have a word width of {@value #QUANTIZE_WORD_WIDTH}. |
| */ |
| private static int quantizeFromRgb888(int color) { |
| int r = modifyWordWidth(Color.red(color), 8, QUANTIZE_WORD_WIDTH); |
| int g = modifyWordWidth(Color.green(color), 8, QUANTIZE_WORD_WIDTH); |
| int b = modifyWordWidth(Color.blue(color), 8, QUANTIZE_WORD_WIDTH); |
| return r << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) | g << QUANTIZE_WORD_WIDTH | b; |
| } |
| |
| /** |
| * Quantized RGB888 values to have a word width of {@value #QUANTIZE_WORD_WIDTH}. |
| */ |
| static int approximateToRgb888(int r, int g, int b) { |
| return Color.rgb(modifyWordWidth(r, QUANTIZE_WORD_WIDTH, 8), |
| modifyWordWidth(g, QUANTIZE_WORD_WIDTH, 8), |
| modifyWordWidth(b, QUANTIZE_WORD_WIDTH, 8)); |
| } |
| |
| private static int approximateToRgb888(int color) { |
| return approximateToRgb888(quantizedRed(color), quantizedGreen(color), quantizedBlue(color)); |
| } |
| |
| /** |
| * @return red component of the quantized color |
| */ |
| static int quantizedRed(int color) { |
| return (color >> (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH)) & QUANTIZE_WORD_MASK; |
| } |
| |
| /** |
| * @return green component of a quantized color |
| */ |
| static int quantizedGreen(int color) { |
| return (color >> QUANTIZE_WORD_WIDTH) & QUANTIZE_WORD_MASK; |
| } |
| |
| /** |
| * @return blue component of a quantized color |
| */ |
| static int quantizedBlue(int color) { |
| return color & QUANTIZE_WORD_MASK; |
| } |
| |
| private static int modifyWordWidth(int value, int currentWidth, int targetWidth) { |
| final int newValue; |
| if (targetWidth > currentWidth) { |
| // If we're approximating up in word width, we'll shift up |
| newValue = value << (targetWidth - currentWidth); |
| } else { |
| // Else, we will just shift and keep the MSB |
| newValue = value >> (currentWidth - targetWidth); |
| } |
| return newValue & ((1 << targetWidth) - 1); |
| } |
| |
| } |