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