Retry r88137:

ui/gfx/color_analysis.cc

Index: ui/gfx/color_analysis.cc
diff --git a/ui/gfx/color_analysis.cc b/ui/gfx/color_analysis.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b781108a2f4500412d626f3108930a798452c4c6
--- /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