Improve K-mean dominant color selection for favicons

After running the favicon through K-mean clustering, find a color from the
image that is closest to the cluster center. This usually makes the colors
less "muddy", as K-mean clusters converge on an average color. It improves
selection for sites like reddit and imgur.

BUG=162315
TEST=added ui_unittests ColorAnalysisTest, FindClosestColor


Review URL: https://chromiumcodereview.appspot.com/11485011

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@172431 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 71 insertions, 3 deletions

diff --git a/ui/gfx/color_analysis.cc b/ui/gfx/color_analysis.cc
index 877d128..6a6cdca 100644
--- a/ui/gfx/color_analysis.cc
+++ b/ui/gfx/color_analysis.cc
@@ -175,6 +175,37 @@ int GridSampler::GetSample(int width, int height) {
   return index % (width * height);
 }
 
+SkColor FindClosestColor(const uint8_t* image,
+                         int width,
+                         int height,
+                         SkColor color) {
+  uint8_t in_r = SkColorGetR(color);
+  uint8_t in_g = SkColorGetG(color);
+  uint8_t in_b = SkColorGetB(color);
+  // Search using distance-squared to avoid expensive sqrt() operations.
+  int best_distance_squared = kint32max;
+  SkColor best_color = color;
+  const uint8_t* byte = image;
+  for (int i = 0; i < width * height; ++i) {
+    uint8_t b = *(byte++);
+    uint8_t g = *(byte++);
+    uint8_t r = *(byte++);
+    uint8_t a = *(byte++);
+    // Ignore fully transparent pixels.
+    if (a == 0)
+      continue;
+    int distance_squared =
+        (in_b - b) * (in_b - b) +
+        (in_g - g) * (in_g - g) +
+        (in_r - r) * (in_r - r);
+    if (distance_squared < best_distance_squared) {
+      best_distance_squared = distance_squared;
+      best_color = SkColorSetRGB(r, g, b);
+    }
+  }
+  return best_color;
+}
+
 // For a 16x16 icon on an Intel Core i5 this function takes approximately
 // 0.5 ms to run.
 // TODO(port): This code assumes the CPU architecture is little-endian.
@@ -317,7 +348,9 @@ SkColor CalculateKMeanColorOfBuffer(uint8_t* decoded_data,
     }
   }
 
-  return color;
+  // Find a color that actually appears in the image (the K-mean cluster center
+  // will not usually be a color that appears in the image).
+  return FindClosestColor(decoded_data, img_width, img_height, color);
 }
 
 SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png,
diff --git a/ui/gfx/color_analysis.h b/ui/gfx/color_analysis.h
index 7b7af93..6201874 100644
--- a/ui/gfx/color_analysis.h
+++ b/ui/gfx/color_analysis.h
@@ -46,6 +46,11 @@ class UI_EXPORT GridSampler : public KMeanImageSampler {
    int calls_;
 };
 
+// Returns the color in an ARGB |image| that is closest in RGB-space to the
+// provided |color|. Exported for testing.
+UI_EXPORT SkColor FindClosestColor(const uint8_t* image, int width, int height,
+                                   SkColor color);
+
 // Returns an SkColor that represents the calculated dominant color in the png.
 // This uses a KMean clustering algorithm to find clusters of pixel colors in
 // RGB space.
@@ -56,8 +61,6 @@ class UI_EXPORT GridSampler : public KMeanImageSampler {
 // acceptable as a color choice. This can be from 0 to 765.
 //
 // RGB KMean Algorithm (N clusters, M iterations):
-// TODO (dtrainor): Try moving most/some of this to HSV space?  Better for
-// color comparisons/averages?
 // 1.Pick N starting colors by randomly sampling the pixels. If you see a
 //   color you already saw keep sampling. After a certain number of tries
 //   just remove the cluster and continue with N = N-1 clusters (for an image
@@ -82,6 +85,9 @@ class UI_EXPORT GridSampler : public KMeanImageSampler {
 //   |darkness_limit| < SUM(R, G, B) < |brightness_limit|. Return that color.
 //   If no color fulfills that requirement return the color with the largest
 //   weight regardless of whether or not it fulfills the equation above.
+//
+// Note: Switching to HSV space did not improve the results of this algorithm
+// for typical favicon images.
 UI_EXPORT SkColor CalculateKMeanColorOfPNG(
     scoped_refptr<base::RefCountedMemory> png,
     uint32_t darkness_limit,
diff --git a/ui/gfx/color_analysis_unittest.cc b/ui/gfx/color_analysis_unittest.cc
index 7145a2e..b92deb4 100644
--- a/ui/gfx/color_analysis_unittest.cc
+++ b/ui/gfx/color_analysis_unittest.cc
@@ -10,6 +10,8 @@
 #include "third_party/skia/include/core/SkBitmap.h"
 #include "third_party/skia/include/core/SkColor.h"
 
+using color_utils::FindClosestColor;
+
 namespace {
 
 const unsigned char k1x1White[] = {
@@ -204,6 +206,33 @@ TEST_F(ColorAnalysisTest, GridSampler) {
   EXPECT_EQ(4 + 10 * kWidth, sampler.GetSample(kWidth, kHeight));
 }
 
+TEST_F(ColorAnalysisTest, FindClosestColor) {
+  // Empty image returns input color.
+  SkColor color = FindClosestColor(NULL, 0, 0, SK_ColorRED);
+  EXPECT_EQ(SK_ColorRED, color);
+
+  // Single color image returns that color.
+  SkBitmap bitmap;
+  bitmap.setConfig(SkBitmap::kARGB_8888_Config, 16, 16);
+  bitmap.allocPixels();
+  bitmap.eraseColor(SK_ColorWHITE);
+  color = FindClosestColor(static_cast<uint8_t*>(bitmap.getPixels()),
+                           bitmap.width(),
+                           bitmap.height(),
+                           SK_ColorRED);
+  EXPECT_EQ(SK_ColorWHITE, color);
+
+  // Write a black pixel into the image. A dark grey input pixel should match
+  // the black one in the image.
+  uint32_t* pixel = bitmap.getAddr32(0, 0);
+  *pixel = SK_ColorBLACK;
+  color = FindClosestColor(static_cast<uint8_t*>(bitmap.getPixels()),
+                           bitmap.width(),
+                           bitmap.height(),
+                           SK_ColorDKGRAY);
+  EXPECT_EQ(SK_ColorBLACK, color);
+}
+
 TEST_F(ColorAnalysisTest, CalculateKMeanColorOfBitmap) {
   // Create a 16x16 bitmap to represent a favicon.
   SkBitmap bitmap;