1059178a8c7cc80848e5594a9287be91bd924831aChris Banes/* 2059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Copyright 2014 The Android Open Source Project 3059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 4059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Licensed under the Apache License, Version 2.0 (the "License"); 5059178a8c7cc80848e5594a9287be91bd924831aChris Banes * you may not use this file except in compliance with the License. 6059178a8c7cc80848e5594a9287be91bd924831aChris Banes * You may obtain a copy of the License at 7059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 8059178a8c7cc80848e5594a9287be91bd924831aChris Banes * http://www.apache.org/licenses/LICENSE-2.0 9059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 10059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Unless required by applicable law or agreed to in writing, software 11059178a8c7cc80848e5594a9287be91bd924831aChris Banes * distributed under the License is distributed on an "AS IS" BASIS, 12059178a8c7cc80848e5594a9287be91bd924831aChris Banes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13059178a8c7cc80848e5594a9287be91bd924831aChris Banes * See the License for the specific language governing permissions and 14059178a8c7cc80848e5594a9287be91bd924831aChris Banes * limitations under the License. 15059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 16059178a8c7cc80848e5594a9287be91bd924831aChris Banes 17059178a8c7cc80848e5594a9287be91bd924831aChris Banespackage android.support.v7.graphics; 18059178a8c7cc80848e5594a9287be91bd924831aChris Banes 19059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport android.graphics.Bitmap; 20059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport android.graphics.Color; 21f3082d731b24a0cee4305ee6bba168a11c11f068Chris Banesimport android.support.v7.graphics.Palette.Swatch; 22059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport android.util.SparseIntArray; 23059178a8c7cc80848e5594a9287be91bd924831aChris Banes 24059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport java.util.ArrayList; 25059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport java.util.Arrays; 26059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport java.util.Collection; 27059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport java.util.Comparator; 28059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport java.util.List; 29059178a8c7cc80848e5594a9287be91bd924831aChris Banesimport java.util.PriorityQueue; 30059178a8c7cc80848e5594a9287be91bd924831aChris Banes 31059178a8c7cc80848e5594a9287be91bd924831aChris Banes/** 32059178a8c7cc80848e5594a9287be91bd924831aChris Banes * An color quantizer based on the Median-cut algorithm, but optimized for picking out distinct 33059178a8c7cc80848e5594a9287be91bd924831aChris Banes * colors rather than representation colors. 34059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 35059178a8c7cc80848e5594a9287be91bd924831aChris Banes * The color space is represented as a 3-dimensional cube with each dimension being an RGB 36059178a8c7cc80848e5594a9287be91bd924831aChris Banes * component. The cube is then repeatedly divided until we have reduced the color space to the 37059178a8c7cc80848e5594a9287be91bd924831aChris Banes * requested number of colors. An average color is then generated from each cube. 38059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 39059178a8c7cc80848e5594a9287be91bd924831aChris Banes * What makes this different to median-cut is that median-cut divided cubes so that all of the cubes 40059178a8c7cc80848e5594a9287be91bd924831aChris Banes * have roughly the same population, where this quantizer divides boxes based on their color volume. 41059178a8c7cc80848e5594a9287be91bd924831aChris Banes * This means that the color space is divided into distinct colors, rather than representative 42059178a8c7cc80848e5594a9287be91bd924831aChris Banes * colors. 43059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 44059178a8c7cc80848e5594a9287be91bd924831aChris Banesfinal class ColorCutQuantizer { 45059178a8c7cc80848e5594a9287be91bd924831aChris Banes 46059178a8c7cc80848e5594a9287be91bd924831aChris Banes private static final String LOG_TAG = ColorCutQuantizer.class.getSimpleName(); 47059178a8c7cc80848e5594a9287be91bd924831aChris Banes 48059178a8c7cc80848e5594a9287be91bd924831aChris Banes private final float[] mTempHsl = new float[3]; 49059178a8c7cc80848e5594a9287be91bd924831aChris Banes 508772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes private static final float BLACK_MAX_LIGHTNESS = 0.05f; 518772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes private static final float WHITE_MIN_LIGHTNESS = 0.95f; 52059178a8c7cc80848e5594a9287be91bd924831aChris Banes 53059178a8c7cc80848e5594a9287be91bd924831aChris Banes private static final int COMPONENT_RED = -3; 54059178a8c7cc80848e5594a9287be91bd924831aChris Banes private static final int COMPONENT_GREEN = -2; 55059178a8c7cc80848e5594a9287be91bd924831aChris Banes private static final int COMPONENT_BLUE = -1; 56059178a8c7cc80848e5594a9287be91bd924831aChris Banes 57059178a8c7cc80848e5594a9287be91bd924831aChris Banes private final int[] mColors; 58059178a8c7cc80848e5594a9287be91bd924831aChris Banes private final SparseIntArray mColorPopulations; 59059178a8c7cc80848e5594a9287be91bd924831aChris Banes 60c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes private final List<Swatch> mQuantizedColors; 61059178a8c7cc80848e5594a9287be91bd924831aChris Banes 62059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 63059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Factory-method to generate a {@link ColorCutQuantizer} from a {@link Bitmap} object. 64059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 65059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @param bitmap Bitmap to extract the pixel data from 66059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @param maxColors The maximum number of colors that should be in the result palette. 67059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 68059178a8c7cc80848e5594a9287be91bd924831aChris Banes static ColorCutQuantizer fromBitmap(Bitmap bitmap, int maxColors) { 69059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int width = bitmap.getWidth(); 70059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int height = bitmap.getHeight(); 71059178a8c7cc80848e5594a9287be91bd924831aChris Banes 72c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes final int[] pixels = new int[width * height]; 73c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes bitmap.getPixels(pixels, 0, width, 0, 0, width, height); 74059178a8c7cc80848e5594a9287be91bd924831aChris Banes 75c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes return new ColorCutQuantizer(new ColorHistogram(pixels), maxColors); 76059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 77059178a8c7cc80848e5594a9287be91bd924831aChris Banes 78059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 79059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Private constructor. 80059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 81c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes * @param colorHistogram histogram representing an image's pixel data 82059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @param maxColors The maximum number of colors that should be in the result palette. 83059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 84c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes private ColorCutQuantizer(ColorHistogram colorHistogram, int maxColors) { 85c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes final int rawColorCount = colorHistogram.getNumberOfColors(); 86c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes final int[] rawColors = colorHistogram.getColors(); 87c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes final int[] rawColorCounts = colorHistogram.getColorCounts(); 88059178a8c7cc80848e5594a9287be91bd924831aChris Banes 89059178a8c7cc80848e5594a9287be91bd924831aChris Banes // First, lets pack the populations into a SparseIntArray so that they can be easily 90059178a8c7cc80848e5594a9287be91bd924831aChris Banes // retrieved without knowing a color's index 91059178a8c7cc80848e5594a9287be91bd924831aChris Banes mColorPopulations = new SparseIntArray(rawColorCount); 92059178a8c7cc80848e5594a9287be91bd924831aChris Banes for (int i = 0; i < rawColors.length; i++) { 93059178a8c7cc80848e5594a9287be91bd924831aChris Banes mColorPopulations.append(rawColors[i], rawColorCounts[i]); 94059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 95059178a8c7cc80848e5594a9287be91bd924831aChris Banes 96059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Now go through all of the colors and keep those which we do not want to ignore 97059178a8c7cc80848e5594a9287be91bd924831aChris Banes mColors = new int[rawColorCount]; 98059178a8c7cc80848e5594a9287be91bd924831aChris Banes int validColorCount = 0; 99059178a8c7cc80848e5594a9287be91bd924831aChris Banes for (int color : rawColors) { 100059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (!shouldIgnoreColor(color)) { 101059178a8c7cc80848e5594a9287be91bd924831aChris Banes mColors[validColorCount++] = color; 102059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 103059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 104059178a8c7cc80848e5594a9287be91bd924831aChris Banes 105059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (validColorCount <= maxColors) { 106059178a8c7cc80848e5594a9287be91bd924831aChris Banes // The image has fewer colors than the maximum requested, so just return the colors 107c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes mQuantizedColors = new ArrayList<Swatch>(); 108059178a8c7cc80848e5594a9287be91bd924831aChris Banes for (final int color : mColors) { 109c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes mQuantizedColors.add(new Swatch(color, mColorPopulations.get(color))); 110059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 111059178a8c7cc80848e5594a9287be91bd924831aChris Banes } else { 112059178a8c7cc80848e5594a9287be91bd924831aChris Banes // We need use quantization to reduce the number of colors 113059178a8c7cc80848e5594a9287be91bd924831aChris Banes mQuantizedColors = quantizePixels(validColorCount - 1, maxColors); 114059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 115059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 116059178a8c7cc80848e5594a9287be91bd924831aChris Banes 117059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 118059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return the list of quantized colors 119059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 120c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes List<Swatch> getQuantizedColors() { 121059178a8c7cc80848e5594a9287be91bd924831aChris Banes return mQuantizedColors; 122059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 123059178a8c7cc80848e5594a9287be91bd924831aChris Banes 124c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes private List<Swatch> quantizePixels(int maxColorIndex, int maxColors) { 125059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Create the priority queue which is sorted by volume descending. This means we always 126059178a8c7cc80848e5594a9287be91bd924831aChris Banes // split the largest box in the queue 127059178a8c7cc80848e5594a9287be91bd924831aChris Banes final PriorityQueue<Vbox> pq = new PriorityQueue<Vbox>(maxColors, VBOX_COMPARATOR_VOLUME); 128059178a8c7cc80848e5594a9287be91bd924831aChris Banes 129059178a8c7cc80848e5594a9287be91bd924831aChris Banes // To start, offer a box which contains all of the colors 130059178a8c7cc80848e5594a9287be91bd924831aChris Banes pq.offer(new Vbox(0, maxColorIndex)); 131059178a8c7cc80848e5594a9287be91bd924831aChris Banes 132059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Now go through the boxes, splitting them until we have reached maxColors or there are no 133059178a8c7cc80848e5594a9287be91bd924831aChris Banes // more boxes to split 134059178a8c7cc80848e5594a9287be91bd924831aChris Banes splitBoxes(pq, maxColors); 135059178a8c7cc80848e5594a9287be91bd924831aChris Banes 136059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Finally, return the average colors of the color boxes 137059178a8c7cc80848e5594a9287be91bd924831aChris Banes return generateAverageColors(pq); 138059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 139059178a8c7cc80848e5594a9287be91bd924831aChris Banes 140059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 141059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Iterate through the {@link java.util.Queue}, popping 142059178a8c7cc80848e5594a9287be91bd924831aChris Banes * {@link ColorCutQuantizer.Vbox} objects from the queue 143059178a8c7cc80848e5594a9287be91bd924831aChris Banes * and splitting them. Once split, the new box and the remaining box are offered back to the 144059178a8c7cc80848e5594a9287be91bd924831aChris Banes * queue. 145059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 146059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @param queue {@link java.util.PriorityQueue} to poll for boxes 147059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @param maxSize Maximum amount of boxes to split 148059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 149059178a8c7cc80848e5594a9287be91bd924831aChris Banes private void splitBoxes(final PriorityQueue<Vbox> queue, final int maxSize) { 150059178a8c7cc80848e5594a9287be91bd924831aChris Banes while (queue.size() < maxSize) { 151059178a8c7cc80848e5594a9287be91bd924831aChris Banes final Vbox vbox = queue.poll(); 152059178a8c7cc80848e5594a9287be91bd924831aChris Banes 153059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (vbox != null && vbox.canSplit()) { 154059178a8c7cc80848e5594a9287be91bd924831aChris Banes // First split the box, and offer the result 155059178a8c7cc80848e5594a9287be91bd924831aChris Banes queue.offer(vbox.splitBox()); 156059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Then offer the box back 157059178a8c7cc80848e5594a9287be91bd924831aChris Banes queue.offer(vbox); 158059178a8c7cc80848e5594a9287be91bd924831aChris Banes } else { 159059178a8c7cc80848e5594a9287be91bd924831aChris Banes // If we get here then there are no more boxes to split, so return 160059178a8c7cc80848e5594a9287be91bd924831aChris Banes return; 161059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 162059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 163059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 164059178a8c7cc80848e5594a9287be91bd924831aChris Banes 165c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes private List<Swatch> generateAverageColors(Collection<Vbox> vboxes) { 166c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes ArrayList<Swatch> colors = new ArrayList<Swatch>(vboxes.size()); 167059178a8c7cc80848e5594a9287be91bd924831aChris Banes for (Vbox vbox : vboxes) { 168c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes Swatch color = vbox.getAverageColor(); 169059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (!shouldIgnoreColor(color)) { 170059178a8c7cc80848e5594a9287be91bd924831aChris Banes // As we're averaging a color box, we can still get colors which we do not want, so 171059178a8c7cc80848e5594a9287be91bd924831aChris Banes // we check again here 172059178a8c7cc80848e5594a9287be91bd924831aChris Banes colors.add(color); 173059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 174059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 175059178a8c7cc80848e5594a9287be91bd924831aChris Banes return colors; 176059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 177059178a8c7cc80848e5594a9287be91bd924831aChris Banes 178059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 179059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Represents a tightly fitting box around a color space. 180059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 181059178a8c7cc80848e5594a9287be91bd924831aChris Banes private class Vbox { 182e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes // lower and upper index are inclusive 183e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes private int mLowerIndex; 184e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes private int mUpperIndex; 185059178a8c7cc80848e5594a9287be91bd924831aChris Banes 186e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes private int mMinRed, mMaxRed; 187e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes private int mMinGreen, mMaxGreen; 188e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes private int mMinBlue, mMaxBlue; 189059178a8c7cc80848e5594a9287be91bd924831aChris Banes 190059178a8c7cc80848e5594a9287be91bd924831aChris Banes Vbox(int lowerIndex, int upperIndex) { 191e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mLowerIndex = lowerIndex; 192e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mUpperIndex = upperIndex; 193059178a8c7cc80848e5594a9287be91bd924831aChris Banes fitBox(); 194059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 195059178a8c7cc80848e5594a9287be91bd924831aChris Banes 196059178a8c7cc80848e5594a9287be91bd924831aChris Banes int getVolume() { 197e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes return (mMaxRed - mMinRed + 1) * (mMaxGreen - mMinGreen + 1) * 198e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes (mMaxBlue - mMinBlue + 1); 199059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 200059178a8c7cc80848e5594a9287be91bd924831aChris Banes 201059178a8c7cc80848e5594a9287be91bd924831aChris Banes boolean canSplit() { 202059178a8c7cc80848e5594a9287be91bd924831aChris Banes return getColorCount() > 1; 203059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 204059178a8c7cc80848e5594a9287be91bd924831aChris Banes 205059178a8c7cc80848e5594a9287be91bd924831aChris Banes int getColorCount() { 206e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes return mUpperIndex - mLowerIndex + 1; 207059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 208059178a8c7cc80848e5594a9287be91bd924831aChris Banes 209059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 210059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Recomputes the boundaries of this box to tightly fit the colors within the box. 211059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 212059178a8c7cc80848e5594a9287be91bd924831aChris Banes void fitBox() { 213059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Reset the min and max to opposite values 214e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMinRed = mMinGreen = mMinBlue = 0xFF; 215e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMaxRed = mMaxGreen = mMaxBlue = 0x0; 216059178a8c7cc80848e5594a9287be91bd924831aChris Banes 217e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes for (int i = mLowerIndex; i <= mUpperIndex; i++) { 218059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int color = mColors[i]; 219e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes final int r = Color.red(color); 220e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes final int g = Color.green(color); 221e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes final int b = Color.blue(color); 222e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes if (r > mMaxRed) { 223e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMaxRed = r; 224059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 225e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes if (r < mMinRed) { 226e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMinRed = r; 227059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 228e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes if (g > mMaxGreen) { 229e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMaxGreen = g; 230059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 231e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes if (g < mMinGreen) { 232e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMinGreen = g; 233059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 234e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes if (b > mMaxBlue) { 235e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMaxBlue = b; 236059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 237e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes if (b < mMinBlue) { 238e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mMinBlue = b; 239059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 240059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 241059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 242059178a8c7cc80848e5594a9287be91bd924831aChris Banes 243059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 244059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Split this color box at the mid-point along it's longest dimension 245059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 246059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return the new ColorBox 247059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 248059178a8c7cc80848e5594a9287be91bd924831aChris Banes Vbox splitBox() { 249059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (!canSplit()) { 250059178a8c7cc80848e5594a9287be91bd924831aChris Banes throw new IllegalStateException("Can not split a box with only 1 color"); 251059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 252059178a8c7cc80848e5594a9287be91bd924831aChris Banes 253059178a8c7cc80848e5594a9287be91bd924831aChris Banes // find median along the longest dimension 254059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int splitPoint = findSplitPoint(); 255059178a8c7cc80848e5594a9287be91bd924831aChris Banes 256e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes Vbox newBox = new Vbox(splitPoint + 1, mUpperIndex); 257059178a8c7cc80848e5594a9287be91bd924831aChris Banes 258059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Now change this box's upperIndex and recompute the color boundaries 259e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes mUpperIndex = splitPoint; 260059178a8c7cc80848e5594a9287be91bd924831aChris Banes fitBox(); 261059178a8c7cc80848e5594a9287be91bd924831aChris Banes 262059178a8c7cc80848e5594a9287be91bd924831aChris Banes return newBox; 263059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 264059178a8c7cc80848e5594a9287be91bd924831aChris Banes 265059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 266059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return the dimension which this box is largest in 267059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 268059178a8c7cc80848e5594a9287be91bd924831aChris Banes int getLongestColorDimension() { 269e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes final int redLength = mMaxRed - mMinRed; 270e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes final int greenLength = mMaxGreen - mMinGreen; 271e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes final int blueLength = mMaxBlue - mMinBlue; 272059178a8c7cc80848e5594a9287be91bd924831aChris Banes 273059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (redLength >= greenLength && redLength >= blueLength) { 274059178a8c7cc80848e5594a9287be91bd924831aChris Banes return COMPONENT_RED; 275059178a8c7cc80848e5594a9287be91bd924831aChris Banes } else if (greenLength >= redLength && greenLength >= blueLength) { 276059178a8c7cc80848e5594a9287be91bd924831aChris Banes return COMPONENT_GREEN; 277059178a8c7cc80848e5594a9287be91bd924831aChris Banes } else { 278059178a8c7cc80848e5594a9287be91bd924831aChris Banes return COMPONENT_BLUE; 279059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 280059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 281059178a8c7cc80848e5594a9287be91bd924831aChris Banes 282059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 283059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Finds the point within this box's lowerIndex and upperIndex index of where to split. 284059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 285059178a8c7cc80848e5594a9287be91bd924831aChris Banes * This is calculated by finding the longest color dimension, and then sorting the 286059178a8c7cc80848e5594a9287be91bd924831aChris Banes * sub-array based on that dimension value in each color. The colors are then iterated over 287059178a8c7cc80848e5594a9287be91bd924831aChris Banes * until a color is found with at least the midpoint of the whole box's dimension midpoint. 288059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 289059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return the index of the colors array to split from 290059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 291059178a8c7cc80848e5594a9287be91bd924831aChris Banes int findSplitPoint() { 292059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int longestDimension = getLongestColorDimension(); 293059178a8c7cc80848e5594a9287be91bd924831aChris Banes 294059178a8c7cc80848e5594a9287be91bd924831aChris Banes // We need to sort the colors in this box based on the longest color dimension. 295059178a8c7cc80848e5594a9287be91bd924831aChris Banes // As we can't use a Comparator to define the sort logic, we modify each color so that 296059178a8c7cc80848e5594a9287be91bd924831aChris Banes // it's most significant is the desired dimension 297e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes modifySignificantOctet(longestDimension, mLowerIndex, mUpperIndex); 298059178a8c7cc80848e5594a9287be91bd924831aChris Banes 299e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes // Now sort... Arrays.sort uses a exclusive toIndex so we need to add 1 300e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes Arrays.sort(mColors, mLowerIndex, mUpperIndex + 1); 301059178a8c7cc80848e5594a9287be91bd924831aChris Banes 302059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Now revert all of the colors so that they are packed as RGB again 303e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes modifySignificantOctet(longestDimension, mLowerIndex, mUpperIndex); 304059178a8c7cc80848e5594a9287be91bd924831aChris Banes 305059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int dimensionMidPoint = midPoint(longestDimension); 306059178a8c7cc80848e5594a9287be91bd924831aChris Banes 307e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes for (int i = mLowerIndex; i <= mUpperIndex; i++) { 308059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int color = mColors[i]; 309059178a8c7cc80848e5594a9287be91bd924831aChris Banes 310059178a8c7cc80848e5594a9287be91bd924831aChris Banes switch (longestDimension) { 311059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_RED: 312059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (Color.red(color) >= dimensionMidPoint) { 313059178a8c7cc80848e5594a9287be91bd924831aChris Banes return i; 314059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 315059178a8c7cc80848e5594a9287be91bd924831aChris Banes break; 316059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_GREEN: 317059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (Color.green(color) >= dimensionMidPoint) { 318059178a8c7cc80848e5594a9287be91bd924831aChris Banes return i; 319059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 320059178a8c7cc80848e5594a9287be91bd924831aChris Banes break; 321059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_BLUE: 322059178a8c7cc80848e5594a9287be91bd924831aChris Banes if (Color.blue(color) > dimensionMidPoint) { 323059178a8c7cc80848e5594a9287be91bd924831aChris Banes return i; 324059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 325059178a8c7cc80848e5594a9287be91bd924831aChris Banes break; 326059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 327059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 328059178a8c7cc80848e5594a9287be91bd924831aChris Banes 329e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes return mLowerIndex; 330059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 331059178a8c7cc80848e5594a9287be91bd924831aChris Banes 332059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 333059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return the average color of this box. 334059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 335c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes Swatch getAverageColor() { 336059178a8c7cc80848e5594a9287be91bd924831aChris Banes int redSum = 0; 337059178a8c7cc80848e5594a9287be91bd924831aChris Banes int greenSum = 0; 338059178a8c7cc80848e5594a9287be91bd924831aChris Banes int blueSum = 0; 339059178a8c7cc80848e5594a9287be91bd924831aChris Banes int totalPopulation = 0; 340059178a8c7cc80848e5594a9287be91bd924831aChris Banes 341e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes for (int i = mLowerIndex; i <= mUpperIndex; i++) { 342059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int color = mColors[i]; 343059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int colorPopulation = mColorPopulations.get(color); 344059178a8c7cc80848e5594a9287be91bd924831aChris Banes 345059178a8c7cc80848e5594a9287be91bd924831aChris Banes totalPopulation += colorPopulation; 346059178a8c7cc80848e5594a9287be91bd924831aChris Banes redSum += colorPopulation * Color.red(color); 347059178a8c7cc80848e5594a9287be91bd924831aChris Banes greenSum += colorPopulation * Color.green(color); 348059178a8c7cc80848e5594a9287be91bd924831aChris Banes blueSum += colorPopulation * Color.blue(color); 349059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 350059178a8c7cc80848e5594a9287be91bd924831aChris Banes 351059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int redAverage = Math.round(redSum / (float) totalPopulation); 352059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int greenAverage = Math.round(greenSum / (float) totalPopulation); 353059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int blueAverage = Math.round(blueSum / (float) totalPopulation); 354059178a8c7cc80848e5594a9287be91bd924831aChris Banes 355c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes return new Swatch(redAverage, greenAverage, blueAverage, totalPopulation); 356059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 357059178a8c7cc80848e5594a9287be91bd924831aChris Banes 358059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 359059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return the midpoint of this box in the given {@code dimension} 360059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 361059178a8c7cc80848e5594a9287be91bd924831aChris Banes int midPoint(int dimension) { 362059178a8c7cc80848e5594a9287be91bd924831aChris Banes switch (dimension) { 363059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_RED: 364059178a8c7cc80848e5594a9287be91bd924831aChris Banes default: 365e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes return (mMinRed + mMaxRed) / 2; 366059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_GREEN: 367e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes return (mMinGreen + mMaxGreen) / 2; 368059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_BLUE: 369e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes return (mMinBlue + mMaxBlue) / 2; 370059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 371059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 372059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 373059178a8c7cc80848e5594a9287be91bd924831aChris Banes 374059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 375059178a8c7cc80848e5594a9287be91bd924831aChris Banes * Modify the significant octet in a packed color int. Allows sorting based on the value of a 376059178a8c7cc80848e5594a9287be91bd924831aChris Banes * single color component. 377059178a8c7cc80848e5594a9287be91bd924831aChris Banes * 378059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @see Vbox#findSplitPoint() 379059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 380e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes private void modifySignificantOctet(final int dimension, int lowerIndex, int upperIndex) { 381059178a8c7cc80848e5594a9287be91bd924831aChris Banes switch (dimension) { 382059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_RED: 383059178a8c7cc80848e5594a9287be91bd924831aChris Banes // Already in RGB, no need to do anything 384059178a8c7cc80848e5594a9287be91bd924831aChris Banes break; 385059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_GREEN: 386059178a8c7cc80848e5594a9287be91bd924831aChris Banes // We need to do a RGB to GRB swap, or vice-versa 387e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes for (int i = lowerIndex; i <= upperIndex; i++) { 388059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int color = mColors[i]; 389059178a8c7cc80848e5594a9287be91bd924831aChris Banes mColors[i] = Color.rgb((color >> 8) & 0xFF, (color >> 16) & 0xFF, color & 0xFF); 390059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 391059178a8c7cc80848e5594a9287be91bd924831aChris Banes break; 392059178a8c7cc80848e5594a9287be91bd924831aChris Banes case COMPONENT_BLUE: 393059178a8c7cc80848e5594a9287be91bd924831aChris Banes // We need to do a RGB to BGR swap, or vice-versa 394e7410604e4f1743608ae16d5ebe6614e4d8e887dChris Banes for (int i = lowerIndex; i <= upperIndex; i++) { 395059178a8c7cc80848e5594a9287be91bd924831aChris Banes final int color = mColors[i]; 396059178a8c7cc80848e5594a9287be91bd924831aChris Banes mColors[i] = Color.rgb(color & 0xFF, (color >> 8) & 0xFF, (color >> 16) & 0xFF); 397059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 398059178a8c7cc80848e5594a9287be91bd924831aChris Banes break; 399059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 400059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 401059178a8c7cc80848e5594a9287be91bd924831aChris Banes 4028772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes private boolean shouldIgnoreColor(int color) { 4038772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes ColorUtils.RGBtoHSL(Color.red(color), Color.green(color), Color.blue(color), mTempHsl); 4048772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes return shouldIgnoreColor(mTempHsl); 405059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 406059178a8c7cc80848e5594a9287be91bd924831aChris Banes 407c6cdc41397bc3ad2c936069af6d448f242790513Chris Banes private static boolean shouldIgnoreColor(Swatch color) { 4088772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes return shouldIgnoreColor(color.getHsl()); 4098772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes } 4108772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes 4118772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes private static boolean shouldIgnoreColor(float[] hslColor) { 4122d2b62754f4d466c0ff1fadd2e2f77ace9342d38Chris Banes return isWhite(hslColor) || isBlack(hslColor) || isNearRedILine(hslColor); 413059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 414059178a8c7cc80848e5594a9287be91bd924831aChris Banes 415059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 416059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return true if the color represents a color which is close to black. 417059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 4188772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes private static boolean isBlack(float[] hslColor) { 4198772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes return hslColor[2] <= BLACK_MAX_LIGHTNESS; 420059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 421059178a8c7cc80848e5594a9287be91bd924831aChris Banes 422059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 423059178a8c7cc80848e5594a9287be91bd924831aChris Banes * @return true if the color represents a color which is close to white. 424059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 4258772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes private static boolean isWhite(float[] hslColor) { 4268772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes return hslColor[2] >= WHITE_MIN_LIGHTNESS; 427059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 428059178a8c7cc80848e5594a9287be91bd924831aChris Banes 429059178a8c7cc80848e5594a9287be91bd924831aChris Banes /** 4302d2b62754f4d466c0ff1fadd2e2f77ace9342d38Chris Banes * @return true if the color lies close to the red side of the I line. 431059178a8c7cc80848e5594a9287be91bd924831aChris Banes */ 4322d2b62754f4d466c0ff1fadd2e2f77ace9342d38Chris Banes private static boolean isNearRedILine(float[] hslColor) { 4338772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes return hslColor[0] >= 10f && hslColor[0] <= 37f && hslColor[1] <= 0.82f; 434059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 435059178a8c7cc80848e5594a9287be91bd924831aChris Banes 4368772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes /** 4378772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes * Comparator which sorts {@link Vbox} instances based on their volume, in descending order 4388772c3de9ca656e82f2fdb34ef95c266c831d48dChris Banes */ 439059178a8c7cc80848e5594a9287be91bd924831aChris Banes private static final Comparator<Vbox> VBOX_COMPARATOR_VOLUME = new Comparator<Vbox>() { 440059178a8c7cc80848e5594a9287be91bd924831aChris Banes @Override 441059178a8c7cc80848e5594a9287be91bd924831aChris Banes public int compare(Vbox lhs, Vbox rhs) { 442059178a8c7cc80848e5594a9287be91bd924831aChris Banes return rhs.getVolume() - lhs.getVolume(); 443059178a8c7cc80848e5594a9287be91bd924831aChris Banes } 444059178a8c7cc80848e5594a9287be91bd924831aChris Banes }; 445059178a8c7cc80848e5594a9287be91bd924831aChris Banes 446059178a8c7cc80848e5594a9287be91bd924831aChris Banes} 447