Port Android palette API for deriving a prominent color from an image.

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>
+#include <cmath>
 #include <limits>
+#include <map>
 #include <memory>
+#include <queue>
 #include <vector>
 
 #include "base/logging.h"
 #include "third_party/skia/include/core/SkBitmap.h"
 #include "third_party/skia/include/core/SkUnPreMultiply.h"
 #include "ui/gfx/codec/png_codec.h"
+#include "ui/gfx/color_palette.h"
 #include "ui/gfx/color_utils.h"
+#include "ui/gfx/range/range.h"
 
 namespace color_utils {
 namespace {
 
 // RGBA KMean Constants
 const uint32_t kNumberOfClusters = 4;
 const int kNumberOfIterations = 50;
 
 const HSL kDefaultLowerHSLBound = {-1, -1, 0.15};
 const HSL kDefaultUpperHSLBound = {-1, -1, 0.85};
@@ skipping 106 matching lines @@
 // approximately 10 microseconds for a 16x16 icon on an Intel Core i5.
 void UnPreMultiply(const SkBitmap& bitmap, uint32_t* buffer, int buffer_size) {
   SkAutoLockPixels auto_lock(bitmap);
   uint32_t* in = static_cast<uint32_t*>(bitmap.getPixels());
   uint32_t* out = buffer;
   int pixel_count = std::min(bitmap.width() * bitmap.height(), buffer_size);
   for (int i = 0; i < pixel_count; ++i)
     *out++ = SkUnPreMultiply::PMColorToColor(*in++);
 }
 
+// Prominent color utilities ---------------------------------------------------
+
+// A color value with an associated weight (equivalent to the popularity of that
+// color).
+struct WeightedColor {
+  SkColor color;
+  int weight;
+};
+
+// A |ColorBox| represents a region in a color space (an ordered set of colors).
+// It is a range in the ordered set, with a low index and a high index. The
+// diversity (volume) of the box is computed by looking at the range of color
+// values it spans, where r, g, and b components are considered separately.
+class ColorBox {
+ public:
+  explicit ColorBox(std::vector<SkColor>* color_space)
+      : ColorBox(color_space, gfx::Range(0, color_space->size() - 1)) {}
+  ColorBox(const ColorBox& other) = default;
+  ColorBox& operator=(const ColorBox& other) = default;
+  ~ColorBox() {}
+
+  // Can't split if there's only one color in the box.
+  bool CanSplit() { return !color_range_.is_empty(); }

[sadrul, 2017/02/10 19:36:44]

const

[Evan Stade, 2017/02/13 19:01:13]

Done.

+
+  // Splits |this| in two and returns the other half.
+  ColorBox Split() {

[sadrul, 2017/02/10 19:36:44]

What happens if Split() is called when this has just one color?

[Evan Stade, 2017/02/13 19:01:13]

It's an error to do that. You'd hit the dcheck in RecomputeBounds().

+    // Calculate which component has the largest range...
+    int r_dimension = max_r_ - min_r_;
+    int g_dimension = max_g_ - min_g_;
+    int b_dimension = max_b_ - min_b_;
+    int long_dimension = std::max({r_dimension, g_dimension, b_dimension});
+
+    // ... and sort along that axis. Split at the median of that axis.
+    std::function<bool(SkColor, SkColor)> sort_function = [](
+        SkColor a, SkColor b) { return SkColorGetR(a) < SkColorGetR(b); };

[sadrul, 2017/02/10 19:36:44]

https://chromium-cpp.appspot.com/ claims this is banned. Use base::Bind instead
(which does take lambdas, e.g. base::Bind([](SkColor a...)

[Evan Stade, 2017/02/13 19:01:13]

well that's pretty annoying as std::sort doesn't take a base::Callback, but I've
reworked this code to a (sadly more verbose) version that doesn't use
std::function.

+    int median = (min_r_ + max_r_) / 2;
+    if (g_dimension == long_dimension) {
+      sort_function = [](SkColor a, SkColor b) {
+        return SkColorGetG(a) < SkColorGetG(b);
+      };
+      median = (min_g_ + max_g_) / 2;
+    } else if (b_dimension == long_dimension) {
+      sort_function = [](SkColor a, SkColor b) {
+        return SkColorGetB(a) < SkColorGetB(b);
+      };
+      median = (min_b_ + max_b_) / 2;
+    }
+
+    // Just the portion of |color_space_| that's covered by this box should be
+    // sorted.
+    std::sort(color_space_->begin() + color_range_.start(),
+              color_space_->begin() + color_range_.end(), sort_function);
+
+    // Split at the first color value that's not less than the median.
+    uint32_t split_point = color_range_.end();
+    for (auto i = color_range_.start() + 1; i < color_range_.end(); ++i) {

[sadrul, 2017/02/10 19:36:44]

Just use uint32_t here?

[Evan Stade, 2017/02/13 19:01:13]

Done.

+      if (!sort_function(color_space_->at(i),
+                         SkColorSetRGB(median, median, median))) {
+        split_point = i;
+        break;
+      }
+    }
+
+    // Break off half and return it.
+    gfx::Range other_range = color_range_;
+    other_range.set_end(split_point - 1);
+    ColorBox other_box(color_space_, other_range);
+
+    // Keep the other half in |this| and recalculate our color bounds.
+    color_range_.set_start(split_point);
+    RecomputeBounds();
+    return other_box;
+  }
+
+  // Returns the average color of this box, weighted by its popularity in
+  // |color_counts|.
+  WeightedColor GetWeightedAverageColor(
+      const std::map<SkColor, int>& color_counts) const {
+    int sum_r = 0;
+    int sum_g = 0;
+    int sum_b = 0;
+    int total_count_in_box = 0;
+
+    for (auto i = color_range_.start(); i <= color_range_.end(); ++i) {

[sadrul, 2017/02/10 19:36:44]

uint32_t

[Evan Stade, 2017/02/13 19:01:13]

Done.

+      const SkColor color = color_space_->at(i);
+      auto color_count_iter = color_counts.find(color);
+      DCHECK(color_count_iter != color_counts.end());
+      const int color_count = color_count_iter->second;
+
+      total_count_in_box += color_count;
+      sum_r += color_count * SkColorGetR(color);
+      sum_g += color_count * SkColorGetG(color);
+      sum_b += color_count * SkColorGetB(color);
+    }
+
+    WeightedColor weighted_color;
+    weighted_color.weight = total_count_in_box;
+    weighted_color.color = SkColorSetRGB(
+        std::round(static_cast<float>(sum_r) / total_count_in_box),
+        std::round(static_cast<float>(sum_g) / total_count_in_box),
+        std::round(static_cast<float>(sum_b) / total_count_in_box));
+    return weighted_color;
+  }
+
+  // Comparisons are done by volume.
+  bool operator<(const ColorBox& other) const {
+    return volume_ < other.volume_;
+  }
+
+ private:
+  ColorBox(std::vector<SkColor>* color_space, const gfx::Range& color_range)
+      : color_space_(color_space), color_range_(color_range) {
+    RecomputeBounds();
+  }
+
+  void RecomputeBounds() {
+    DCHECK(!color_range_.is_reversed());
+    DCHECK_LT(color_range_.end(), color_space_->size());
+
+    min_r_ = 0xFF;
+    min_g_ = 0xFF;
+    min_b_ = 0xFF;
+    max_r_ = 0;
+    max_g_ = 0;
+    max_b_ = 0;
+
+    for (auto i = color_range_.start(); i < color_range_.end(); ++i) {

[sadrul, 2017/02/10 19:36:44]

uint32_t

[Evan Stade, 2017/02/13 19:01:13]

Done.

+      SkColor color = color_space_->at(i);
+      min_r_ = std::min<uint8_t>(SkColorGetR(color), min_r_);
+      min_g_ = std::min<uint8_t>(SkColorGetG(color), min_g_);
+      min_b_ = std::min<uint8_t>(SkColorGetB(color), min_b_);
+      max_r_ = std::max<uint8_t>(SkColorGetR(color), max_r_);
+      max_g_ = std::max<uint8_t>(SkColorGetG(color), max_g_);
+      max_b_ = std::max<uint8_t>(SkColorGetB(color), max_b_);
+    }
+
+    volume_ =
+        (max_r_ - min_r_ + 1) * (max_g_ - min_g_ + 1) * (max_b_ - min_b_ + 1);
+  }
+
+  // The set of colors of which this box captures a subset. This vector is not
+  // owned but may be modified during the split operation.
+  std::vector<SkColor>* color_space_;
+
+  // The range of indexes into |color_space_| that are part of this box.
+  gfx::Range color_range_;
+
+  // Cached min and max color component values for the colors in this box.
+  uint8_t min_r_ = 0;
+  uint8_t min_g_ = 0;
+  uint8_t min_b_ = 0;
+  uint8_t max_r_ = 0;
+  uint8_t max_g_ = 0;
+  uint8_t max_b_ = 0;
+
+  // Cached volume value, which is the product of the range of each color
+  // component.
+  int volume_ = 0;
+};
+
+// Some color values should be ignored for the purposes of determining prominent
+// colors.
+bool IsInterestingColor(SkColor color) {
+  float average_channel_value =
+      (SkColorGetR(color) + SkColorGetG(color) + SkColorGetB(color)) / 3.0f;
+  // If a color is too close to white or black, ignore it.
+  if (average_channel_value >= 237 || average_channel_value <= 22)
+    return false;
+
+  // Also rule out skin tones.
+  HSL hsl;
+  SkColorToHSL(color, &hsl);
+  return !(hsl.h >= 0.028f && hsl.h <= 0.10f && hsl.s <= 0.82f);
+}
+
+// This algorithm is a port of Android's Palette API. Compare to package
+// android.support.v7.graphics and see that code for additional high-level
+// explanation of this algorithm. There are some minor differences:
+//   * This code doesn't exclude the same color from being used for
+//   different color profiles.
+//   * This code doesn't try to heuristically derive missing colors from
+//   existing colors.
+SkColor CalculateProminentColorOfBuffer(uint8_t* decoded_data,
+                                        int img_width,
+                                        int img_height,
+                                        const HSL& lower_bound,
+                                        const HSL& upper_bound,
+                                        const HSL& goal) {
+  DCHECK_GT(img_width, 0);
+  DCHECK_GT(img_height, 0);
+  std::map<SkColor, int> color_counts;
+
+  // First extract all colors.
+  for (int i = 0; i < img_width * img_height; ++i) {
+    // TODO(port): This code assumes the CPU architecture is little-endian.
+    uint8_t b = decoded_data[i * 4];
+    uint8_t g = decoded_data[i * 4 + 1];
+    uint8_t r = decoded_data[i * 4 + 2];
+    uint8_t a = decoded_data[i * 4 + 3];
+    if (a == SK_AlphaTRANSPARENT)
+      continue;
+
+    SkColor pixel = SkColorSetRGB(r, g, b);
+    color_counts[pixel]++;
+  }
+
+  // Now throw out some uninteresting colors.
+  std::vector<SkColor> interesting_colors;
+  for (auto color_count : color_counts) {
+    SkColor color = color_count.first;
+    if (IsInterestingColor(color))
+      interesting_colors.push_back(color);
+  }
+
+  if (interesting_colors.empty())
+    return SK_ColorTRANSPARENT;
+
+  // Group the colors into "boxes" and repeatedly split the most voluminous box.
+  // We stop the process when a box can no longer be split (there's only one
+  // color in it) or when the number of color boxes reaches 12. As per the
+  // Android docs,
+  //
+  //   For landscapes, good values are in the range 12-16. For images which
+  //   are largely made up of people's faces then this value should be increased
+  //   to 24-32.
+  const int kMaxColors = 12;
+  // Boxes are sorted by volume with the most voluminous at the front of the PQ.
+  std::priority_queue<ColorBox> boxes;
+  boxes.emplace(&interesting_colors);
+  while (boxes.size() < kMaxColors) {
+    auto box = boxes.top();
+    if (!box.CanSplit())
+      break;
+    boxes.pop();
+    boxes.push(box.Split());
+    boxes.push(box);
+  }
+
+  // Now extract a single color to represent each box. This is the average color
+  // in the box, weighted by the frequency of that color in the source image.
+  std::vector<WeightedColor> box_colors;
+  int max_weight = 0;
+  while (!boxes.empty()) {
+    box_colors.push_back(boxes.top().GetWeightedAverageColor(color_counts));
+    boxes.pop();
+    max_weight = std::max(max_weight, box_colors.back().weight);
+  }
+
+  // Given these box average colors, find the best one for the desired color
+  // profile. "Best" in this case means the color which fits in the provided
+  // bounds and comes closest to |goal|. It's possible that no color will fit in
+  // the provided bounds, in which case we'll return an empty color.
+  double best_suitability = 0;
+  SkColor best_color = SK_ColorTRANSPARENT;
+  for (const auto& box_color : box_colors) {
+    HSL hsl;
+    SkColorToHSL(box_color.color, &hsl);
+    if (!IsWithinHSLRange(hsl, lower_bound, upper_bound))
+      continue;
+
+    double suitability =
+        (1 - std::abs(hsl.s - goal.s)) * 3 +
+        (1 - std::abs(hsl.l - goal.l)) * 6.5 +
+        (box_color.weight / static_cast<float>(max_weight)) * 0.5;
+    if (suitability > best_suitability) {
+      best_suitability = suitability;
+      best_color = box_color.color;
+    }
+  }
+
+  return best_color;
+}
+
 } // namespace
 
 KMeanImageSampler::KMeanImageSampler() {
 }
 
 KMeanImageSampler::~KMeanImageSampler() {
 }
 
 GridSampler::GridSampler() : calls_(0) {
 }
@@ skipping 238 matching lines @@
                                     const HSL& upper_bound,
                                     KMeanImageSampler* sampler) {
   // SkBitmap uses pre-multiplied alpha but the KMean clustering function
   // above uses non-pre-multiplied alpha. Transform the bitmap before we
   // analyze it because the function reads each pixel multiple times.
   int pixel_count = bitmap.width() * bitmap.height();
   std::unique_ptr<uint32_t[]> image(new uint32_t[pixel_count]);
   UnPreMultiply(bitmap, image.get(), pixel_count);
 
   return CalculateKMeanColorOfBuffer(reinterpret_cast<uint8_t*>(image.get()),
-                                     bitmap.width(),
-                                     bitmap.height(),
-                                     lower_bound,
-                                     upper_bound,
-                                     sampler);
+                                     bitmap.width(), bitmap.height(),
+                                     lower_bound, upper_bound, sampler);
 }
 
 SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap) {
   GridSampler sampler;
   return CalculateKMeanColorOfBitmap(
       bitmap, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler);
 }
 
+SkColor CalculateProminentColorOfBitmap(const SkBitmap& bitmap,
+                                        int color_profile) {
+  // SkBitmap uses pre-multiplied alpha but the prominent color algorithm
+  // above uses non-pre-multiplied alpha. Transform the bitmap before we
+  // analyze it because the function reads each pixel multiple times.
+  int pixel_count = bitmap.width() * bitmap.height();
+  if (pixel_count == 0)
+    return SK_ColorTRANSPARENT;
+
+  std::unique_ptr<uint32_t[]> image(new uint32_t[pixel_count]);
+  UnPreMultiply(bitmap, image.get(), pixel_count);
+
+  // The hue is not relevant to our bounds or goal colors.
+  HSL lower_bound = {
+      -1,
+  };
+  HSL upper_bound = {
+      -1,
+  };
+  HSL goal = {
+      -1,
+  };
+
+  // Set the luma.
+  if (color_profile & LIGHT) {
+    lower_bound.l = 0.55f;
+    upper_bound.l = 1;
+    goal.l = 0.74f;
+  } else if (color_profile & NORMAL) {
+    lower_bound.l = 0.3f;
+    upper_bound.l = 0.7f;
+    goal.l = 0.5f;
+  } else {
+    DCHECK(color_profile & DARK);
+    lower_bound.l = 0;
+    upper_bound.l = 0.45f;
+    goal.l = 0.26f;
+  }
+
+  // Set the saturation.
+  if (color_profile & VIBRANT) {
+    lower_bound.s = 0.35f;
+    upper_bound.s = 1;
+    goal.s = 1;
+  } else {
+    DCHECK(color_profile & MUTED);
+    lower_bound.s = 0;
+    upper_bound.s = 0.4f;
+    goal.s = 0.3f;
+  }
+
+  return CalculateProminentColorOfBuffer(
+      reinterpret_cast<uint8_t*>(image.get()), bitmap.width(), bitmap.height(),
+      lower_bound, upper_bound, goal);
+}
+
 gfx::Matrix3F ComputeColorCovariance(const SkBitmap& bitmap) {
   // First need basic stats to normalize each channel separately.
   SkAutoLockPixels bitmap_lock(bitmap);
   gfx::Matrix3F covariance = gfx::Matrix3F::Zeros();
   if (!bitmap.getPixels())
     return covariance;
 
   // Assume ARGB_8888 format.
   DCHECK(bitmap.colorType() == kN32_SkColorType);
 
@@ skipping 149 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