1/* 2 * Copyright 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.support.v7.graphics; 18 19import android.graphics.Color; 20import android.support.v4.graphics.ColorUtils; 21import android.support.v7.graphics.Palette.Swatch; 22import android.util.TimingLogger; 23 24import java.util.ArrayList; 25import java.util.Arrays; 26import java.util.Collection; 27import java.util.Comparator; 28import java.util.List; 29import java.util.PriorityQueue; 30 31/** 32 * An color quantizer based on the Median-cut algorithm, but optimized for picking out distinct 33 * colors rather than representation colors. 34 * 35 * The color space is represented as a 3-dimensional cube with each dimension being an RGB 36 * component. The cube is then repeatedly divided until we have reduced the color space to the 37 * requested number of colors. An average color is then generated from each cube. 38 * 39 * What makes this different to median-cut is that median-cut divided cubes so that all of the cubes 40 * have roughly the same population, where this quantizer divides boxes based on their color volume. 41 * This means that the color space is divided into distinct colors, rather than representative 42 * colors. 43 */ 44final class ColorCutQuantizer { 45 46 private static final String LOG_TAG = "ColorCutQuantizer"; 47 private static final boolean LOG_TIMINGS = false; 48 49 private static final int COMPONENT_RED = -3; 50 private static final int COMPONENT_GREEN = -2; 51 private static final int COMPONENT_BLUE = -1; 52 53 private static final int QUANTIZE_WORD_WIDTH = 5; 54 private static final int QUANTIZE_WORD_MASK = (1 << QUANTIZE_WORD_WIDTH) - 1; 55 56 final int[] mColors; 57 final int[] mHistogram; 58 final List<Swatch> mQuantizedColors; 59 final TimingLogger mTimingLogger; 60 final Palette.Filter[] mFilters; 61 62 private final float[] mTempHsl = new float[3]; 63 64 /** 65 * Constructor. 66 * 67 * @param pixels histogram representing an image's pixel data 68 * @param maxColors The maximum number of colors that should be in the result palette. 69 * @param filters Set of filters to use in the quantization stage 70 */ 71 ColorCutQuantizer(final int[] pixels, final int maxColors, final Palette.Filter[] filters) { 72 mTimingLogger = LOG_TIMINGS ? new TimingLogger(LOG_TAG, "Creation") : null; 73 mFilters = filters; 74 75 final int[] hist = mHistogram = new int[1 << (QUANTIZE_WORD_WIDTH * 3)]; 76 for (int i = 0; i < pixels.length; i++) { 77 final int quantizedColor = quantizeFromRgb888(pixels[i]); 78 // Now update the pixel value to the quantized value 79 pixels[i] = quantizedColor; 80 // And update the histogram 81 hist[quantizedColor]++; 82 } 83 84 if (LOG_TIMINGS) { 85 mTimingLogger.addSplit("Histogram created"); 86 } 87 88 // Now let's count the number of distinct colors 89 int distinctColorCount = 0; 90 for (int color = 0; color < hist.length; color++) { 91 if (hist[color] > 0 && shouldIgnoreColor(color)) { 92 // If we should ignore the color, set the population to 0 93 hist[color] = 0; 94 } 95 if (hist[color] > 0) { 96 // If the color has population, increase the distinct color count 97 distinctColorCount++; 98 } 99 } 100 101 if (LOG_TIMINGS) { 102 mTimingLogger.addSplit("Filtered colors and distinct colors counted"); 103 } 104 105 // Now lets go through create an array consisting of only distinct colors 106 final int[] colors = mColors = new int[distinctColorCount]; 107 int distinctColorIndex = 0; 108 for (int color = 0; color < hist.length; color++) { 109 if (hist[color] > 0) { 110 colors[distinctColorIndex++] = color; 111 } 112 } 113 114 if (LOG_TIMINGS) { 115 mTimingLogger.addSplit("Distinct colors copied into array"); 116 } 117 118 if (distinctColorCount <= maxColors) { 119 // The image has fewer colors than the maximum requested, so just return the colors 120 mQuantizedColors = new ArrayList<>(); 121 for (int color : colors) { 122 mQuantizedColors.add(new Swatch(approximateToRgb888(color), hist[color])); 123 } 124 125 if (LOG_TIMINGS) { 126 mTimingLogger.addSplit("Too few colors present. Copied to Swatches"); 127 mTimingLogger.dumpToLog(); 128 } 129 } else { 130 // We need use quantization to reduce the number of colors 131 mQuantizedColors = quantizePixels(maxColors); 132 133 if (LOG_TIMINGS) { 134 mTimingLogger.addSplit("Quantized colors computed"); 135 mTimingLogger.dumpToLog(); 136 } 137 } 138 } 139 140 /** 141 * @return the list of quantized colors 142 */ 143 List<Swatch> getQuantizedColors() { 144 return mQuantizedColors; 145 } 146 147 private List<Swatch> quantizePixels(int maxColors) { 148 // Create the priority queue which is sorted by volume descending. This means we always 149 // split the largest box in the queue 150 final PriorityQueue<Vbox> pq = new PriorityQueue<>(maxColors, VBOX_COMPARATOR_VOLUME); 151 152 // To start, offer a box which contains all of the colors 153 pq.offer(new Vbox(0, mColors.length - 1)); 154 155 // Now go through the boxes, splitting them until we have reached maxColors or there are no 156 // more boxes to split 157 splitBoxes(pq, maxColors); 158 159 // Finally, return the average colors of the color boxes 160 return generateAverageColors(pq); 161 } 162 163 /** 164 * Iterate through the {@link java.util.Queue}, popping 165 * {@link ColorCutQuantizer.Vbox} objects from the queue 166 * and splitting them. Once split, the new box and the remaining box are offered back to the 167 * queue. 168 * 169 * @param queue {@link java.util.PriorityQueue} to poll for boxes 170 * @param maxSize Maximum amount of boxes to split 171 */ 172 private void splitBoxes(final PriorityQueue<Vbox> queue, final int maxSize) { 173 while (queue.size() < maxSize) { 174 final Vbox vbox = queue.poll(); 175 176 if (vbox != null && vbox.canSplit()) { 177 // First split the box, and offer the result 178 queue.offer(vbox.splitBox()); 179 180 if (LOG_TIMINGS) { 181 mTimingLogger.addSplit("Box split"); 182 } 183 // Then offer the box back 184 queue.offer(vbox); 185 } else { 186 if (LOG_TIMINGS) { 187 mTimingLogger.addSplit("All boxes split"); 188 } 189 // If we get here then there are no more boxes to split, so return 190 return; 191 } 192 } 193 } 194 195 private List<Swatch> generateAverageColors(Collection<Vbox> vboxes) { 196 ArrayList<Swatch> colors = new ArrayList<>(vboxes.size()); 197 for (Vbox vbox : vboxes) { 198 Swatch swatch = vbox.getAverageColor(); 199 if (!shouldIgnoreColor(swatch)) { 200 // As we're averaging a color box, we can still get colors which we do not want, so 201 // we check again here 202 colors.add(swatch); 203 } 204 } 205 return colors; 206 } 207 208 /** 209 * Represents a tightly fitting box around a color space. 210 */ 211 private class Vbox { 212 // lower and upper index are inclusive 213 private int mLowerIndex; 214 private int mUpperIndex; 215 // Population of colors within this box 216 private int mPopulation; 217 218 private int mMinRed, mMaxRed; 219 private int mMinGreen, mMaxGreen; 220 private int mMinBlue, mMaxBlue; 221 222 Vbox(int lowerIndex, int upperIndex) { 223 mLowerIndex = lowerIndex; 224 mUpperIndex = upperIndex; 225 fitBox(); 226 } 227 228 final int getVolume() { 229 return (mMaxRed - mMinRed + 1) * (mMaxGreen - mMinGreen + 1) * 230 (mMaxBlue - mMinBlue + 1); 231 } 232 233 final boolean canSplit() { 234 return getColorCount() > 1; 235 } 236 237 final int getColorCount() { 238 return 1 + mUpperIndex - mLowerIndex; 239 } 240 241 /** 242 * Recomputes the boundaries of this box to tightly fit the colors within the box. 243 */ 244 final void fitBox() { 245 final int[] colors = mColors; 246 final int[] hist = mHistogram; 247 248 // Reset the min and max to opposite values 249 int minRed, minGreen, minBlue; 250 minRed = minGreen = minBlue = Integer.MAX_VALUE; 251 int maxRed, maxGreen, maxBlue; 252 maxRed = maxGreen = maxBlue = Integer.MIN_VALUE; 253 int count = 0; 254 255 for (int i = mLowerIndex; i <= mUpperIndex; i++) { 256 final int color = colors[i]; 257 count += hist[color]; 258 259 final int r = quantizedRed(color); 260 final int g = quantizedGreen(color); 261 final int b = quantizedBlue(color); 262 if (r > maxRed) { 263 maxRed = r; 264 } 265 if (r < minRed) { 266 minRed = r; 267 } 268 if (g > maxGreen) { 269 maxGreen = g; 270 } 271 if (g < minGreen) { 272 minGreen = g; 273 } 274 if (b > maxBlue) { 275 maxBlue = b; 276 } 277 if (b < minBlue) { 278 minBlue = b; 279 } 280 } 281 282 mMinRed = minRed; 283 mMaxRed = maxRed; 284 mMinGreen = minGreen; 285 mMaxGreen = maxGreen; 286 mMinBlue = minBlue; 287 mMaxBlue = maxBlue; 288 mPopulation = count; 289 } 290 291 /** 292 * Split this color box at the mid-point along it's longest dimension 293 * 294 * @return the new ColorBox 295 */ 296 final Vbox splitBox() { 297 if (!canSplit()) { 298 throw new IllegalStateException("Can not split a box with only 1 color"); 299 } 300 301 // find median along the longest dimension 302 final int splitPoint = findSplitPoint(); 303 304 Vbox newBox = new Vbox(splitPoint + 1, mUpperIndex); 305 306 // Now change this box's upperIndex and recompute the color boundaries 307 mUpperIndex = splitPoint; 308 fitBox(); 309 310 return newBox; 311 } 312 313 /** 314 * @return the dimension which this box is largest in 315 */ 316 final int getLongestColorDimension() { 317 final int redLength = mMaxRed - mMinRed; 318 final int greenLength = mMaxGreen - mMinGreen; 319 final int blueLength = mMaxBlue - mMinBlue; 320 321 if (redLength >= greenLength && redLength >= blueLength) { 322 return COMPONENT_RED; 323 } else if (greenLength >= redLength && greenLength >= blueLength) { 324 return COMPONENT_GREEN; 325 } else { 326 return COMPONENT_BLUE; 327 } 328 } 329 330 /** 331 * Finds the point within this box's lowerIndex and upperIndex index of where to split. 332 * 333 * This is calculated by finding the longest color dimension, and then sorting the 334 * sub-array based on that dimension value in each color. The colors are then iterated over 335 * until a color is found with at least the midpoint of the whole box's dimension midpoint. 336 * 337 * @return the index of the colors array to split from 338 */ 339 final int findSplitPoint() { 340 final int longestDimension = getLongestColorDimension(); 341 final int[] colors = mColors; 342 final int[] hist = mHistogram; 343 344 // We need to sort the colors in this box based on the longest color dimension. 345 // As we can't use a Comparator to define the sort logic, we modify each color so that 346 // it's most significant is the desired dimension 347 modifySignificantOctet(colors, longestDimension, mLowerIndex, mUpperIndex); 348 349 // Now sort... Arrays.sort uses a exclusive toIndex so we need to add 1 350 Arrays.sort(colors, mLowerIndex, mUpperIndex + 1); 351 352 // Now revert all of the colors so that they are packed as RGB again 353 modifySignificantOctet(colors, longestDimension, mLowerIndex, mUpperIndex); 354 355 final int midPoint = mPopulation / 2; 356 for (int i = mLowerIndex, count = 0; i <= mUpperIndex; i++) { 357 count += hist[colors[i]]; 358 if (count >= midPoint) { 359 return i; 360 } 361 } 362 363 return mLowerIndex; 364 } 365 366 /** 367 * @return the average color of this box. 368 */ 369 final Swatch getAverageColor() { 370 final int[] colors = mColors; 371 final int[] hist = mHistogram; 372 int redSum = 0; 373 int greenSum = 0; 374 int blueSum = 0; 375 int totalPopulation = 0; 376 377 for (int i = mLowerIndex; i <= mUpperIndex; i++) { 378 final int color = colors[i]; 379 final int colorPopulation = hist[color]; 380 381 totalPopulation += colorPopulation; 382 redSum += colorPopulation * quantizedRed(color); 383 greenSum += colorPopulation * quantizedGreen(color); 384 blueSum += colorPopulation * quantizedBlue(color); 385 } 386 387 final int redMean = Math.round(redSum / (float) totalPopulation); 388 final int greenMean = Math.round(greenSum / (float) totalPopulation); 389 final int blueMean = Math.round(blueSum / (float) totalPopulation); 390 391 return new Swatch(approximateToRgb888(redMean, greenMean, blueMean), totalPopulation); 392 } 393 } 394 395 /** 396 * Modify the significant octet in a packed color int. Allows sorting based on the value of a 397 * single color component. This relies on all components being the same word size. 398 * 399 * @see Vbox#findSplitPoint() 400 */ 401 private static void modifySignificantOctet(final int[] a, final int dimension, 402 final int lower, final int upper) { 403 switch (dimension) { 404 case COMPONENT_RED: 405 // Already in RGB, no need to do anything 406 break; 407 case COMPONENT_GREEN: 408 // We need to do a RGB to GRB swap, or vice-versa 409 for (int i = lower; i <= upper; i++) { 410 final int color = a[i]; 411 a[i] = quantizedGreen(color) << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) 412 | quantizedRed(color) << QUANTIZE_WORD_WIDTH 413 | quantizedBlue(color); 414 } 415 break; 416 case COMPONENT_BLUE: 417 // We need to do a RGB to BGR swap, or vice-versa 418 for (int i = lower; i <= upper; i++) { 419 final int color = a[i]; 420 a[i] = quantizedBlue(color) << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) 421 | quantizedGreen(color) << QUANTIZE_WORD_WIDTH 422 | quantizedRed(color); 423 } 424 break; 425 } 426 } 427 428 private boolean shouldIgnoreColor(int color565) { 429 final int rgb = approximateToRgb888(color565); 430 ColorUtils.colorToHSL(rgb, mTempHsl); 431 return shouldIgnoreColor(rgb, mTempHsl); 432 } 433 434 private boolean shouldIgnoreColor(Swatch color) { 435 return shouldIgnoreColor(color.getRgb(), color.getHsl()); 436 } 437 438 private boolean shouldIgnoreColor(int rgb, float[] hsl) { 439 if (mFilters != null && mFilters.length > 0) { 440 for (int i = 0, count = mFilters.length; i < count; i++) { 441 if (!mFilters[i].isAllowed(rgb, hsl)) { 442 return true; 443 } 444 } 445 } 446 return false; 447 } 448 449 /** 450 * Comparator which sorts {@link Vbox} instances based on their volume, in descending order 451 */ 452 private static final Comparator<Vbox> VBOX_COMPARATOR_VOLUME = new Comparator<Vbox>() { 453 @Override 454 public int compare(Vbox lhs, Vbox rhs) { 455 return rhs.getVolume() - lhs.getVolume(); 456 } 457 }; 458 459 /** 460 * Quantized a RGB888 value to have a word width of {@value #QUANTIZE_WORD_WIDTH}. 461 */ 462 private static int quantizeFromRgb888(int color) { 463 int r = modifyWordWidth(Color.red(color), 8, QUANTIZE_WORD_WIDTH); 464 int g = modifyWordWidth(Color.green(color), 8, QUANTIZE_WORD_WIDTH); 465 int b = modifyWordWidth(Color.blue(color), 8, QUANTIZE_WORD_WIDTH); 466 return r << (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH) | g << QUANTIZE_WORD_WIDTH | b; 467 } 468 469 /** 470 * Quantized RGB888 values to have a word width of {@value #QUANTIZE_WORD_WIDTH}. 471 */ 472 private static int approximateToRgb888(int r, int g, int b) { 473 return Color.rgb(modifyWordWidth(r, QUANTIZE_WORD_WIDTH, 8), 474 modifyWordWidth(g, QUANTIZE_WORD_WIDTH, 8), 475 modifyWordWidth(b, QUANTIZE_WORD_WIDTH, 8)); 476 } 477 478 private static int approximateToRgb888(int color) { 479 return approximateToRgb888(quantizedRed(color), quantizedGreen(color), quantizedBlue(color)); 480 } 481 482 /** 483 * @return red component of the quantized color 484 */ 485 private static int quantizedRed(int color) { 486 return (color >> (QUANTIZE_WORD_WIDTH + QUANTIZE_WORD_WIDTH)) & QUANTIZE_WORD_MASK; 487 } 488 489 /** 490 * @return green component of a quantized color 491 */ 492 private static int quantizedGreen(int color) { 493 return (color >> QUANTIZE_WORD_WIDTH) & QUANTIZE_WORD_MASK; 494 } 495 496 /** 497 * @return blue component of a quantized color 498 */ 499 private static int quantizedBlue(int color) { 500 return color & QUANTIZE_WORD_MASK; 501 } 502 503 private static int modifyWordWidth(int value, int currentWidth, int targetWidth) { 504 final int newValue; 505 if (targetWidth > currentWidth) { 506 // If we're approximating up in word width, we'll use scaling to approximate the 507 // new value 508 newValue = value * ((1 << targetWidth) - 1) / ((1 << currentWidth) - 1); 509 } else { 510 // Else, we will just shift and keep the MSB 511 newValue = value >> (currentWidth - targetWidth); 512 } 513 return newValue & ((1 << targetWidth) - 1); 514 } 515 516} 517