Retry r88137:

Add code to calculate the dominant color for a favicon.

Currently we calculate the dominant/representative color only for those favicons we need it for (i.e. the ones shown on the NTP). We don't do any caching either in memory or in the favicon db but that can be tacked on later if deemed suitable.

Code in color_analysis.* authored by dtrainor

BUG=none
TEST=trybots

Review URL: http://codereview.chromium.org/7031078

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

1 files changed, 324 insertions, 0 deletions

diff --git a/ui/gfx/color_analysis.cc b/ui/gfx/color_analysis.cc
new file mode 100644
index 0000000..b781108
--- /dev/null
+++ b/ui/gfx/color_analysis.cc
@@ -0,0 +1,324 @@
+// Copyright (c) 2011 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 <algorithm>
+#include <vector>
+
+#include "ui/gfx/codec/png_codec.h"
+
+namespace {
+
+// RGBA KMean Constants
+const uint32_t kNumberOfClusters = 4;
+const int kNumberOfIterations = 50;
+const uint32_t kMaxBrightness = 600;
+const uint32_t kMinDarkness = 100;
+
+// Background Color Modification Constants
+const SkColor kDefaultBgColor = SK_ColorWHITE;
+
+// Support class to hold information about each cluster of pixel data in
+// the KMean algorithm. While this class does not contain all of the points
+// that exist in the cluster, it keeps track of the aggregate sum so it can
+// compute the new center appropriately.
+class KMeanCluster {
+ public:
+  KMeanCluster() {
+    Reset();
+  }
+
+  void Reset() {
+    centroid[0] = centroid[1] = centroid[2] = 0;
+    aggregate[0] = aggregate[1] = aggregate[2] = 0;
+    counter = 0;
+    weight = 0;
+  }
+
+  inline void SetCentroid(uint8_t r, uint8_t g, uint8_t b) {
+    centroid[0] = r;
+    centroid[1] = g;
+    centroid[2] = b;
+  }
+
+  inline void GetCentroid(uint8_t* r, uint8_t* g, uint8_t* b) {
+    *r = centroid[0];
+    *g = centroid[1];
+    *b = centroid[2];
+  }
+
+  inline bool IsAtCentroid(uint8_t r, uint8_t g, uint8_t b) {
+    return r == centroid[0] && g == centroid[1] && b == centroid[2];
+  }
+
+  // Recomputes the centroid of the cluster based on the aggregate data. The
+  // number of points used to calculate this center is stored for weighting
+  // purposes. The aggregate and counter are then cleared to be ready for the
+  // next iteration.
+  inline void RecomputeCentroid() {
+    if (counter > 0) {
+      centroid[0] = aggregate[0] / counter;
+      centroid[1] = aggregate[1] / counter;
+      centroid[2] = aggregate[2] / counter;
+
+      aggregate[0] = aggregate[1] = aggregate[2] = 0;
+      weight = counter;
+      counter = 0;
+    }
+  }
+
+  inline void AddPoint(uint8_t r, uint8_t g, uint8_t b) {
+    aggregate[0] += r;
+    aggregate[1] += g;
+    aggregate[2] += b;
+    ++counter;
+  }
+
+  // Just returns the distance^2. Since we are comparing relative distances
+  // there is no need to perform the expensive sqrt() operation.
+  inline uint32_t GetDistanceSqr(uint8_t r, uint8_t g, uint8_t b) {
+    return (r - centroid[0]) * (r - centroid[0]) +
+           (g - centroid[1]) * (g - centroid[1]) +
+           (b - centroid[2]) * (b - centroid[2]);
+  }
+
+  // In order to determine if we have hit convergence or not we need to see
+  // if the centroid of the cluster has moved. This determines whether or
+  // not the centroid is the same as the aggregate sum of points that will be
+  // used to generate the next centroid.
+  inline bool CompareCentroidWithAggregate() {
+    if (counter == 0)
+      return false;
+
+    return aggregate[0] / counter == centroid[0] &&
+           aggregate[1] / counter == centroid[1] &&
+           aggregate[2] / counter == centroid[2];
+  }
+
+  // Returns the previous counter, which is used to determine the weight
+  // of the cluster for sorting.
+  inline uint32_t GetWeight() {
+    return weight;
+  }
+
+  static bool SortKMeanClusterByWeight(KMeanCluster a, KMeanCluster b) {
+    return a.GetWeight() > b.GetWeight();
+  }
+
+ private:
+  uint8_t centroid[3];
+
+  // Holds the sum of all the points that make up this cluster. Used to
+  // generate the next centroid as well as to check for convergence.
+  uint32_t aggregate[3];
+  uint32_t counter;
+
+  // The weight of the cluster, determined by how many points were used
+  // to generate the previous centroid.
+  uint32_t weight;
+};
+
+} // namespace
+
+namespace color_utils {
+
+KMeanImageSampler::KMeanImageSampler() {
+}
+
+KMeanImageSampler::~KMeanImageSampler() {
+}
+
+RandomSampler::RandomSampler() {
+}
+
+RandomSampler::~RandomSampler() {
+}
+
+int RandomSampler::GetSample(int width, int height) {
+  return rand();
+}
+
+GridSampler::GridSampler() : calls_(0) {
+}
+
+GridSampler::~GridSampler() {
+}
+
+int GridSampler::GetSample(int width, int height) {
+  calls_++;
+  // We may keep getting called after we've gone of the edge of the grid; in
+  // this case we offset future return values by the number of times we've gone
+  // off the grid.
+  return (width * height * calls_ / kNumberOfClusters) % (width * height) +
+      calls_ / kNumberOfClusters;
+}
+
+SkColor CalculateRecommendedBgColorForPNG(
+    scoped_refptr<RefCountedMemory> png) {
+  RandomSampler sampler;
+  return CalculateRecommendedBgColorForPNG(png, sampler);
+}
+
+SkColor CalculateKMeanColorOfPNG(scoped_refptr<RefCountedMemory> png,
+                                 uint32_t darkness_limit,
+                                 uint32_t brightness_limit) {
+  RandomSampler sampler;
+  return CalculateKMeanColorOfPNG(png, darkness_limit, brightness_limit,
+                                  sampler);
+}
+
+SkColor CalculateRecommendedBgColorForPNG(
+    scoped_refptr<RefCountedMemory> png,
+    KMeanImageSampler& sampler) {
+  return CalculateKMeanColorOfPNG(png,
+                                  kMinDarkness,
+                                  kMaxBrightness,
+                                  sampler);
+}
+
+SkColor CalculateKMeanColorOfPNG(scoped_refptr<RefCountedMemory> png,
+                                 uint32_t darkness_limit,
+                                 uint32_t brightness_limit,
+                                 KMeanImageSampler& sampler) {
+  int img_width, img_height;
+  std::vector<uint8_t> decoded_data;
+  SkColor color = kDefaultBgColor;
+
+  if (png.get() &&
+      png->size() &&
+      gfx::PNGCodec::Decode(png->front(),
+                            png->size(),
+                            gfx::PNGCodec::FORMAT_BGRA,
+                            &decoded_data,
+                            &img_width,
+                            &img_height)) {
+    std::vector<KMeanCluster> clusters;
+    clusters.resize(kNumberOfClusters, KMeanCluster());
+
+    // Pick a starting point for each cluster
+    std::vector<KMeanCluster>::iterator cluster = clusters.begin();
+    while (cluster != clusters.end()) {
+      // Try up to 10 times to find a unique color. If no unique color can be
+      // found, destroy this cluster.
+      bool color_unique = false;
+      for (int i = 0; i < 10; ++i) {
+        int pixel_pos = sampler.GetSample(img_width, img_height) %
+            (img_width * img_height);
+
+        uint8_t b = decoded_data[pixel_pos * 4];
+        uint8_t g = decoded_data[pixel_pos * 4 + 1];
+        uint8_t r = decoded_data[pixel_pos * 4 + 2];
+
+        // Loop through the previous clusters and check to see if we have seen
+        // this color before.
+        color_unique = true;
+        for (std::vector<KMeanCluster>::iterator
+            cluster_check = clusters.begin();
+            cluster_check != cluster; ++cluster_check) {
+          if (cluster_check->IsAtCentroid(r, g, b)) {
+            color_unique = false;
+            break;
+          }
+        }
+
+        // If we have a unique color set the center of the cluster to
+        // that color.
+        if (color_unique) {
+          cluster->SetCentroid(r, g, b);
+          break;
+        }
+      }
+
+      // If we don't have a unique color erase this cluster.
+      if (!color_unique) {
+        cluster = clusters.erase(cluster);
+      } else {
+        // Have to increment the iterator here, otherwise the increment in the
+        // for loop will skip a cluster due to the erase if the color wasn't
+        // unique.
+        ++cluster;
+      }
+    }
+
+    bool convergence = false;
+    for (int iteration = 0;
+        iteration < kNumberOfIterations && !convergence && !clusters.empty();
+        ++iteration) {
+
+      // Loop through each pixel so we can place it in the appropriate cluster.
+      std::vector<uint8_t>::iterator pixel = decoded_data.begin();
+      while (pixel != decoded_data.end()) {
+        uint8_t b = *(pixel++);
+        if (pixel == decoded_data.end())
+          continue;
+        uint8_t g = *(pixel++);
+        if (pixel == decoded_data.end())
+          continue;
+        uint8_t r = *(pixel++);
+        if (pixel == decoded_data.end())
+          continue;
+        ++pixel; // Ignore the alpha channel.
+
+        uint32_t distance_sqr_to_closest_cluster = UINT_MAX;
+        std::vector<KMeanCluster>::iterator closest_cluster = clusters.begin();
+
+        // Figure out which cluster this color is closest to in RGB space.
+        for (std::vector<KMeanCluster>::iterator cluster = clusters.begin();
+            cluster != clusters.end(); ++cluster) {
+          uint32_t distance_sqr = cluster->GetDistanceSqr(r, g, b);
+
+          if (distance_sqr < distance_sqr_to_closest_cluster) {
+            distance_sqr_to_closest_cluster = distance_sqr;
+            closest_cluster = cluster;
+          }
+        }
+
+        closest_cluster->AddPoint(r, g, b);
+      }
+
+      // Calculate the new cluster centers and see if we've converged or not.
+      convergence = true;
+      for (std::vector<KMeanCluster>::iterator cluster = clusters.begin();
+          cluster != clusters.end(); ++cluster) {
+        convergence &= cluster->CompareCentroidWithAggregate();
+
+        cluster->RecomputeCentroid();
+      }
+    }
+
+    // Sort the clusters by population so we can tell what the most popular
+    // color is.
+    std::sort(clusters.begin(), clusters.end(),
+              KMeanCluster::SortKMeanClusterByWeight);
+
+    // Loop through the clusters to figure out which cluster has an appropriate
+    // color. Skip any that are too bright/dark and go in order of weight.
+    for (std::vector<KMeanCluster>::iterator cluster = clusters.begin();
+        cluster != clusters.end(); ++cluster) {
+      uint8_t r, g, b;
+      cluster->GetCentroid(&r, &g, &b);
+      // Sum the RGB components to determine if the color is too bright or too
+      // dark.
+      // TODO (dtrainor): Look into using HSV here instead. This approximation
+      // might be fine though.
+      uint32_t summed_color = r + g + b;
+
+      if (summed_color < brightness_limit && summed_color > darkness_limit) {
+        // If we found a valid color just set it and break. We don't want to
+        // check the other ones.
+        color = SkColorSetARGB(0xFF, r, g, b);
+        break;
+      } else if (cluster == clusters.begin()) {
+        // We haven't found a valid color, but we are at the first color so
+        // set the color anyway to make sure we at least have a value here.
+        color = SkColorSetARGB(0xFF, r, g, b);
+      }
+    }
+  }
+
+  return color;
+}
+
+}  // color_utils