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