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 ---------------------------------------------------

[Nico, 2017/02/17 21:37:05]

kind of looks long enough that it could go into its own file

[Evan Stade, 2017/02/17 23:23:18]

I like having all the moving parts to this algorithm in the same file,
especially as they're not relevant to anything else. The overall file should get
a lot shorter when the kmeans algorithm is removed (see cbrug.com/689704)

+
+// A color value with an associated weight (equivalent to the popularity of that
+// color).
+struct WeightedColor {
+  SkColor color;
+  int weight;

[sky, 2017/02/17 21:42:19]

Initialize color and weight?

[sky, 2017/02/17 21:42:19]

Document what the range for this is. Always positive? Have a limit?

[Evan Stade, 2017/02/17 23:23:18]

done

[Evan Stade, 2017/02/17 23:23:18]

changed it to use an explicit constructor

+};
+
+// A |ColorBox| represents a region in a color space (an ordered set of colors).

[sky, 2017/02/17 21:42:19]

Did you consider the name OrderedColorSet? IMO that better describes what it is.

[Evan Stade, 2017/02/17 23:23:18]

no, I didn't consider that name. I drew the names from the Android code and I
think there is value in matching that general terminology to make it easier to
compare the code.

Android doesn't have a ColorBox but it does use "box" extensively and the
closest equivalent class is called "Vbox".

[sky, 2017/02/18 00:01:34]

I actually think 'box' is misleading in this context. Given the context it
implies a region in the image, but that isn't at all what it is. That's why I
like using OrderedColorSet, or perhaps just ColorSet. But naming is hard, so if
you feel strongly leave it.

+// 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)) {}

[sky, 2017/02/17 21:42:20]

DCHECK color_space !empty. That said, CanSplit() seems to check for empty, so do
you know color_space is non-empty?
Also, if the vector is ordered, should you DCHECK on the order?

[Evan Stade, 2017/02/17 23:23:18]

An empty color_space would trip the second DCHECK in RecomputeBounds (which is
called on construction).
The vector isn't initially ordered.

+  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() const { return !color_range_.is_empty(); }
+
+  // Splits |this| in two and returns the other half.
+  ColorBox Split() {

[sky, 2017/02/17 21:42:19]

This also sorts. Maybe SortAndSplit?

[Evan Stade, 2017/02/17 23:26:26]

oops, missed this one. It sorts in an unpredictable way and only sorts a part of
the color space. SortAndMutateColorSpace doesn't seem better than Sort to me.

+    // Calculate which component has the largest range...
+    int r_dimension = max_r_ - min_r_;

[sky, 2017/02/17 21:42:19]

As you have min/max as uint8_t, why did you use int instead of int8_t here?
Also, why is long_dimension a long instead of uint8_t? If there is a good reason
to use int over uint8_t, I would expect long_dimension to match the type.

[Evan Stade, 2017/02/17 23:23:18]

updated these all to uint8_t. int8_t could overflow. (max value for int8_t is
127 right?)
long_dimension was an int

+    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});
+    enum ColorChannel {
+      RED,
+      GREEN,
+      BLUE,
+    };

[Nico, 2017/02/17 21:37:05]

optional nit: Since you don't use the name, I'd do

  enum { RED, GREEN, BLUE } channel = ...

[Evan Stade, 2017/02/17 23:23:18]

I like it, done.

+    ColorChannel channel = long_dimension == r_dimension
+                               ? RED
+                               : long_dimension == g_dimension ? GREEN : BLUE;
+
+    // ... and sort along that axis.
+    auto sort_function = [channel](SkColor a, SkColor b) {
+      switch (channel) {
+        case RED:
+          return SkColorGetR(a) < SkColorGetR(b);
+        case GREEN:
+          return SkColorGetG(a) < SkColorGetG(b);
+        case BLUE:
+          return SkColorGetB(a) < SkColorGetB(b);
+      }
+      NOTREACHED();
+      return SkColorGetB(a) < SkColorGetB(b);
+    };
+    // 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.

[Nico, 2017/02/17 21:37:06]

You mean "mean" not "median" here, right? Else you could just take the middle
index of the range?

[Evan Stade, 2017/02/17 23:23:18]

hmm, I copied this terminology without thinking much about it. It's not the
median but it's not the mean (of all values). It's the mean of the start and end
values. Changed to midpoint.

+    uint32_t split_point = color_range_.end();
+    for (uint32_t i = color_range_.start() + 1; i < color_range_.end(); ++i) {
+      bool past_median = false;
+      switch (channel) {
+        case RED:
+          past_median =
+              SkColorGetR(color_space_->at(i)) > (min_r_ + max_r_) / 2;

[sky, 2017/02/17 21:42:19]

optional: at -> (*color_space_)[i]

[Evan Stade, 2017/02/17 23:23:18]

Done.

+          break;
+        case GREEN:
+          past_median =
+              SkColorGetG(color_space_->at(i)) > (min_g_ + max_g_) / 2;
+          break;
+        case BLUE:
+          past_median =
+              SkColorGetB(color_space_->at(i)) > (min_b_ + max_b_) / 2;
+          break;
+      }
+      if (past_median) {
+        split_point = i;
+        break;
+      }
+    }
+
+    // Break off half and return it.
+    gfx::Range other_range = color_range_;

[sky, 2017/02/17 21:42:19]

Does this do the right thing with 1 color? If there is only one color, then
might the other_range get set to an end of start - 1?

[Evan Stade, 2017/02/17 23:23:18]

it's an error to call this function in that case (CanSplit would have returned
false) and we'll DCHECK in RecomputeBounds.

+    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;

[Nico, 2017/02/17 21:37:05]

For a 4096x4096 all-red image I think this will overflow. Is there a fixed upper
bound on images passed in to this?

[Evan Stade, 2017/02/17 23:23:18]

that's bad. I've changed this to uint64_t.

I do expect we'll want to limit the size of images fed to this function, but
exactly where depends on performance. Testing and setting limits is one of the
first steps we'll be taking while hooking this up  (bruthig@ and me).

+    int sum_g = 0;
+    int sum_b = 0;
+    int total_count_in_box = 0;
+
+    for (uint32_t i = color_range_.start(); i <= color_range_.end(); ++i) {
+      const SkColor color = color_space_->at(i);

[sky, 2017/02/17 21:42:19]

If you're going to use const (which I like) use it consistently. By which I mean
r_dimension, color_channel and others can be const as well.

[Evan Stade, 2017/02/17 23:23:18]

Done.

+      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.

[sky, 2017/02/17 21:42:19]

Using operator < to mean compare by volume is obscure and easy to miss. I would
prefer an explicit function.

[Evan Stade, 2017/02/17 23:23:18]

done. (If there's a more elegant way to do this, please point it out.)

+  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() {

[sky, 2017/02/17 21:42:19]

optional: There are no bounds in here, and the name bounds slightly implies a
relation to color_range_. Maybe RecomputeCachedValues? RecomputeColors()?

[Evan Stade, 2017/02/17 23:23:18]

min_* and max_* describe upper and lower bounds for the colors this box covers.

+    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 (uint32_t i = color_range_.start(); i < color_range_.end(); ++i) {
+      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.

[sky, 2017/02/17 21:42:19]

Why did you make this inclusive vs exclusive? Inclusive is mildly confusing and
not what I would have expected.

[Evan Stade, 2017/02/17 23:23:18]

changed. In fact I think there was a bug in the std::sort call because of this.

+  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.

[sky, 2017/02/17 21:42:19]

Can you DCHECK on the image type? That it's 32bit?

[Evan Stade, 2017/02/17 23:23:18]

I was kind of just blindly copying this bit. I've rewritten this to be more C++
and less C-hacker.

+    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())

[sky, 2017/02/17 21:42:19]

If there is only one color, is it the prominent color?

[Evan Stade, 2017/02/17 23:23:18]

it could be, but only if it's "interesting" and within the provided bounds.

If we have fewer than 12 colors to pick from we'll break out of the while loop
below with the !cansplit break.

+    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,
+                                        LumaRange luma,
+                                        SaturationRange saturation) {
+  // 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]);

[sky, 2017/02/17 21:42:19]

image_data? bitmap_data?

[Evan Stade, 2017/02/17 23:23:18]

removed

+  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,
+  };
+
+  switch (luma) {
+    case LumaRange::LIGHT:
+      lower_bound.l = 0.55f;
+      upper_bound.l = 1;
+      goal.l = 0.74f;
+      break;
+    case LumaRange::NORMAL:
+      lower_bound.l = 0.3f;
+      upper_bound.l = 0.7f;
+      goal.l = 0.5f;
+      break;
+    case LumaRange::DARK:
+      lower_bound.l = 0;
+      upper_bound.l = 0.45f;
+      goal.l = 0.26f;
+      break;
+  }
+
+  switch (saturation) {
+    case SaturationRange::VIBRANT:
+      lower_bound.s = 0.35f;
+      upper_bound.s = 1;
+      goal.s = 1;
+      break;
+    case SaturationRange::MUTED:
+      lower_bound.s = 0;
+      upper_bound.s = 0.4f;
+      goal.s = 0.3f;
+      break;
+  }
+
+  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