ChromeOS color extraction - only look at a maximum of 10k pixels in the

ui/gfx/color_analysis.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/gfx/color_analysis.h"
 
 #include <limits.h>
 #include <stdint.h>
 
 #include <algorithm>
@@ skipping 350 matching lines @@
                                 const HSL& lower_bound,
                                 const HSL& upper_bound,
                                 const HSL& goal) {
   DCHECK(!bitmap.empty());
   DCHECK(!bitmap.isNull());
 
   SkAutoLockPixels auto_lock(bitmap);
   const uint32_t* pixels = static_cast<uint32_t*>(bitmap.getPixels());
   const int pixel_count = bitmap.width() * bitmap.height();
 
-  // We don't know exactly how many distinct colors there will be, so just
-  // reserve enough space to keep the maximum number of table resizes low.
-  // In our testing set, 2/3 of wallpapers have <200k unique colors and 1/4
-  // have <100k. Thus 200k is picked as a number that usually amounts to zero
-  // resizes but usually doesn't waste a lot of space.
-  std::unordered_map<SkColor, int> color_counts(200000);
+  // For better performance, only consider at most 10k pixels (evenly
+  // distributed throughout the image). This has a very minor impact on the
+  // outcome but improves runtime substantially for large images. 10,007 is a
+  // prime number to reduce the chance of picking an unrepresentative sample.

[James Cook, 2017/04/07 14:05:47]

Good idea.

[Nico, 2017/04/07 15:33:22]

I'm too dense to understand why the divisor being a prime number helps here. Can
you expand on this? My take would've been that if you walk the image with a
fixed stride, you can always end up with an unrepresentative sample (put red
pixels on the pixels you hit, make all other pixels white, and your thing will
always pick red even if the image is mostly white). This might be good enough in
practice, but I don't see how the prime helps.

(If you want to not have this kind of error, you could pick 10000 numbers
between 0 and pixel_count at random, then sort them so you don't thrash the
cache when you walk them, and collect those randomly-chosen pixels.)

+  constexpr int kMaxConsideredPixels = 10007;
+  const int pixel_increment = std::max(1, pixel_count / kMaxConsideredPixels);
+  std::unordered_map<SkColor, int> color_counts(kMaxConsideredPixels);
 
   // First extract all colors into counts.
-  for (int i = 0; i < pixel_count; ++i) {
+  for (int i = 0; i < pixel_count; i += pixel_increment) {
     // SkBitmap uses pre-multiplied alpha but the prominent color algorithm
     // needs non-pre-multiplied alpha.
     const SkColor pixel = SkUnPreMultiply::PMColorToColor(pixels[i]);
     if (SkColorGetA(pixel) == SK_AlphaTRANSPARENT)
       continue;
 
     color_counts[pixel]++;
   }
 
   // Now throw out some uninteresting colors.
@@ skipping 547 matching lines @@
   gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap);
   gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros();
   gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors);
   gfx::Vector3dF principal = eigenvectors.get_column(0);
   if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF())
     return false;  // This may happen for some edge cases.
   return ApplyColorReduction(source_bitmap, principal, true, target_bitmap);
 }
 
 }  // color_utils