1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "ui/gfx/color_analysis.h"
6
7 #include <limits.h>
8 #include <stdint.h>
9
10 #include <algorithm>
11 #include <cmath>
12 #include <limits>
13 #include <memory>
14 #include <queue>
15 #include <unordered_map>
16 #include <vector>
17
18 #include "base/bind.h"
19 #include "base/callback.h"
20 #include "base/logging.h"
21 #include "base/sys_byteorder.h"
22 #include "base/numerics/ranges.h"
23 #include "third_party/skia/include/core/SkBitmap.h"
24 #include "third_party/skia/include/core/SkUnPreMultiply.h"
25 #include "ui/gfx/codec/png_codec.h"
26 #include "ui/gfx/color_palette.h"
27 #include "ui/gfx/color_utils.h"
28 #include "ui/gfx/geometry/rect.h"
29 #include "ui/gfx/range/range.h"
30
31 namespace color_utils {
32 namespace {
33
34 // RGBA KMean Constants
35 const int kNumberOfClusters = 4;
36 const int kNumberOfIterations = 50;
37
38 const HSL kDefaultLowerHSLBound = {-1, -1, 0.15};
39 const HSL kDefaultUpperHSLBound = {-1, -1, 0.85};
40
41 // Background Color Modification Constants
42 const SkColor kDefaultBgColor = SK_ColorWHITE;
43
44 // Support class to hold information about each cluster of pixel data in
45 // the KMean algorithm. While this class does not contain all of the points
46 // that exist in the cluster, it keeps track of the aggregate sum so it can
47 // compute the new center appropriately.
48 class KMeanCluster {
49 public:
KMeanCluster()50 KMeanCluster() {
51 Reset();
52 }
53
Reset()54 void Reset() {
55 centroid_[0] = centroid_[1] = centroid_[2] = 0;
56 aggregate_[0] = aggregate_[1] = aggregate_[2] = 0;
57 counter_ = 0;
58 weight_ = 0;
59 }
60
SetCentroid(uint8_t r,uint8_t g,uint8_t b)61 inline void SetCentroid(uint8_t r, uint8_t g, uint8_t b) {
62 centroid_[0] = r;
63 centroid_[1] = g;
64 centroid_[2] = b;
65 }
66
GetCentroid(uint8_t * r,uint8_t * g,uint8_t * b)67 inline void GetCentroid(uint8_t* r, uint8_t* g, uint8_t* b) {
68 *r = centroid_[0];
69 *g = centroid_[1];
70 *b = centroid_[2];
71 }
72
IsAtCentroid(uint8_t r,uint8_t g,uint8_t b)73 inline bool IsAtCentroid(uint8_t r, uint8_t g, uint8_t b) {
74 return r == centroid_[0] && g == centroid_[1] && b == centroid_[2];
75 }
76
77 // Recomputes the centroid of the cluster based on the aggregate data. The
78 // number of points used to calculate this center is stored for weighting
79 // purposes. The aggregate and counter are then cleared to be ready for the
80 // next iteration.
RecomputeCentroid()81 inline void RecomputeCentroid() {
82 if (counter_ > 0) {
83 centroid_[0] = static_cast<uint8_t>(aggregate_[0] / counter_);
84 centroid_[1] = static_cast<uint8_t>(aggregate_[1] / counter_);
85 centroid_[2] = static_cast<uint8_t>(aggregate_[2] / counter_);
86
87 aggregate_[0] = aggregate_[1] = aggregate_[2] = 0;
88 weight_ = counter_;
89 counter_ = 0;
90 }
91 }
92
AddPoint(uint8_t r,uint8_t g,uint8_t b)93 inline void AddPoint(uint8_t r, uint8_t g, uint8_t b) {
94 aggregate_[0] += r;
95 aggregate_[1] += g;
96 aggregate_[2] += b;
97 ++counter_;
98 }
99
100 // Just returns the distance^2. Since we are comparing relative distances
101 // there is no need to perform the expensive sqrt() operation.
GetDistanceSqr(uint8_t r,uint8_t g,uint8_t b)102 inline uint32_t GetDistanceSqr(uint8_t r, uint8_t g, uint8_t b) {
103 return (r - centroid_[0]) * (r - centroid_[0]) +
104 (g - centroid_[1]) * (g - centroid_[1]) +
105 (b - centroid_[2]) * (b - centroid_[2]);
106 }
107
108 // In order to determine if we have hit convergence or not we need to see
109 // if the centroid of the cluster has moved. This determines whether or
110 // not the centroid is the same as the aggregate sum of points that will be
111 // used to generate the next centroid.
CompareCentroidWithAggregate()112 inline bool CompareCentroidWithAggregate() {
113 if (counter_ == 0)
114 return false;
115
116 return aggregate_[0] / counter_ == centroid_[0] &&
117 aggregate_[1] / counter_ == centroid_[1] &&
118 aggregate_[2] / counter_ == centroid_[2];
119 }
120
121 // Returns the previous counter, which is used to determine the weight
122 // of the cluster for sorting.
GetWeight() const123 inline uint32_t GetWeight() const {
124 return weight_;
125 }
126
SortKMeanClusterByWeight(const KMeanCluster & a,const KMeanCluster & b)127 static bool SortKMeanClusterByWeight(const KMeanCluster& a,
128 const KMeanCluster& b) {
129 return a.GetWeight() > b.GetWeight();
130 }
131
132 private:
133 uint8_t centroid_[3];
134
135 // Holds the sum of all the points that make up this cluster. Used to
136 // generate the next centroid as well as to check for convergence.
137 uint32_t aggregate_[3];
138 uint32_t counter_;
139
140 // The weight of the cluster, determined by how many points were used
141 // to generate the previous centroid.
142 uint32_t weight_;
143 };
144
145 // Prominent color utilities ---------------------------------------------------
146
147 // A |ColorBox| represents a 3-dimensional region in a color space (an ordered
148 // set of colors). It is a range in the ordered set, with a low index and a high
149 // index. The diversity (volume) of the box is computed by looking at the range
150 // of color values it spans, where r, g, and b components are considered
151 // separately.
152 class ColorBox {
153 public:
ColorBox(std::vector<SkColor> * color_space)154 explicit ColorBox(std::vector<SkColor>* color_space)
155 : ColorBox(color_space, gfx::Range(0, color_space->size())) {}
156 ColorBox(const ColorBox& other) = default;
157 ColorBox& operator=(const ColorBox& other) = default;
~ColorBox()158 ~ColorBox() {}
159
160 // Can't split if there's only one color in the box.
CanSplit() const161 bool CanSplit() const { return color_range_.length() > 1; }
162
163 // Splits |this| in two and returns the other half.
Split()164 ColorBox Split() {
165 // Calculate which component has the largest range...
166 const uint8_t r_dimension = max_r_ - min_r_;
167 const uint8_t g_dimension = max_g_ - min_g_;
168 const uint8_t b_dimension = max_b_ - min_b_;
169 const uint8_t long_dimension =
170 std::max({r_dimension, g_dimension, b_dimension});
171 const enum {
172 RED,
173 GREEN,
174 BLUE,
175 } channel = long_dimension == r_dimension
176 ? RED
177 : long_dimension == g_dimension ? GREEN : BLUE;
178
179 // ... and sort along that axis.
180 auto sort_function = [channel](SkColor a, SkColor b) {
181 switch (channel) {
182 case RED:
183 return SkColorGetR(a) < SkColorGetR(b);
184 case GREEN:
185 return SkColorGetG(a) < SkColorGetG(b);
186 case BLUE:
187 return SkColorGetB(a) < SkColorGetB(b);
188 }
189 NOTREACHED();
190 return SkColorGetB(a) < SkColorGetB(b);
191 };
192 // Just the portion of |color_space_| that's covered by this box should be
193 // sorted.
194 std::sort(color_space_->begin() + color_range_.start(),
195 color_space_->begin() + color_range_.end(), sort_function);
196
197 // Split at the first color value that's not less than the midpoint (mean of
198 // the start and values).
199 uint32_t split_point = color_range_.end() - 1;
200 for (uint32_t i = color_range_.start() + 1; i < color_range_.end() - 1;
201 ++i) {
202 bool past_midpoint = false;
203 switch (channel) {
204 case RED:
205 past_midpoint =
206 static_cast<uint8_t>(SkColorGetR((*color_space_)[i])) >
207 (min_r_ + max_r_) / 2;
208 break;
209 case GREEN:
210 past_midpoint =
211 static_cast<uint8_t>(SkColorGetG((*color_space_)[i])) >
212 (min_g_ + max_g_) / 2;
213 break;
214 case BLUE:
215 past_midpoint =
216 static_cast<uint8_t>(SkColorGetB((*color_space_)[i])) >
217 (min_b_ + max_b_) / 2;
218 break;
219 }
220 if (past_midpoint) {
221 split_point = i;
222 break;
223 }
224 }
225
226 // Break off half and return it.
227 gfx::Range other_range = color_range_;
228 other_range.set_end(split_point);
229 ColorBox other_box(color_space_, other_range);
230
231 // Keep the other half in |this| and recalculate our color bounds.
232 color_range_.set_start(split_point);
233 RecomputeBounds();
234 return other_box;
235 }
236
237 // Returns the average color of this box, weighted by its popularity in
238 // |color_counts|.
GetWeightedAverageColor(const std::unordered_map<SkColor,int> & color_counts) const239 Swatch GetWeightedAverageColor(
240 const std::unordered_map<SkColor, int>& color_counts) const {
241 size_t sum_r = 0;
242 size_t sum_g = 0;
243 size_t sum_b = 0;
244 size_t total_count_in_box = 0;
245
246 for (size_t i = color_range_.start(); i < color_range_.end(); ++i) {
247 const SkColor color = (*color_space_)[i];
248 const auto color_count_iter = color_counts.find(color);
249 DCHECK(color_count_iter != color_counts.end());
250 const size_t color_count = color_count_iter->second;
251
252 total_count_in_box += color_count;
253 sum_r += color_count * SkColorGetR(color);
254 sum_g += color_count * SkColorGetG(color);
255 sum_b += color_count * SkColorGetB(color);
256 }
257
258 return Swatch(
259 SkColorSetRGB(
260 std::round(static_cast<double>(sum_r) / total_count_in_box),
261 std::round(static_cast<double>(sum_g) / total_count_in_box),
262 std::round(static_cast<double>(sum_b) / total_count_in_box)),
263 total_count_in_box);
264 }
265
CompareByVolume(const ColorBox & a,const ColorBox & b)266 static bool CompareByVolume(const ColorBox& a, const ColorBox& b) {
267 return a.volume_ < b.volume_;
268 }
269
270 private:
ColorBox(std::vector<SkColor> * color_space,const gfx::Range & color_range)271 ColorBox(std::vector<SkColor>* color_space, const gfx::Range& color_range)
272 : color_space_(color_space), color_range_(color_range) {
273 RecomputeBounds();
274 }
275
RecomputeBounds()276 void RecomputeBounds() {
277 DCHECK(!color_range_.is_reversed());
278 DCHECK(!color_range_.is_empty());
279 DCHECK_LE(color_range_.end(), color_space_->size());
280
281 min_r_ = 0xFF;
282 min_g_ = 0xFF;
283 min_b_ = 0xFF;
284 max_r_ = 0;
285 max_g_ = 0;
286 max_b_ = 0;
287
288 for (uint32_t i = color_range_.start(); i < color_range_.end(); ++i) {
289 SkColor color = (*color_space_)[i];
290 min_r_ = std::min<uint8_t>(SkColorGetR(color), min_r_);
291 min_g_ = std::min<uint8_t>(SkColorGetG(color), min_g_);
292 min_b_ = std::min<uint8_t>(SkColorGetB(color), min_b_);
293 max_r_ = std::max<uint8_t>(SkColorGetR(color), max_r_);
294 max_g_ = std::max<uint8_t>(SkColorGetG(color), max_g_);
295 max_b_ = std::max<uint8_t>(SkColorGetB(color), max_b_);
296 }
297
298 volume_ =
299 (max_r_ - min_r_ + 1) * (max_g_ - min_g_ + 1) * (max_b_ - min_b_ + 1);
300 }
301
302 // The set of colors of which this box captures a subset. This vector is not
303 // owned but may be modified during the split operation.
304 std::vector<SkColor>* color_space_;
305
306 // The range of indexes into |color_space_| that are part of this box.
307 gfx::Range color_range_;
308
309 // Cached min and max color component values for the colors in this box.
310 uint8_t min_r_ = 0;
311 uint8_t min_g_ = 0;
312 uint8_t min_b_ = 0;
313 uint8_t max_r_ = 0;
314 uint8_t max_g_ = 0;
315 uint8_t max_b_ = 0;
316
317 // Cached volume value, which is the product of the range of each color
318 // component.
319 int volume_ = 0;
320 };
321
322 // Some color values should be ignored for the purposes of determining prominent
323 // colors.
IsInterestingColor(const SkColor & color)324 bool IsInterestingColor(const SkColor& color) {
325 const float average_channel_value =
326 (SkColorGetR(color) + SkColorGetG(color) + SkColorGetB(color)) / 3.0f;
327 // If a color is too close to white or black, ignore it.
328 if (average_channel_value >= 237 || average_channel_value <= 22)
329 return false;
330
331 HSL hsl;
332 SkColorToHSL(color, &hsl);
333 return !(hsl.h >= 0.028f && hsl.h <= 0.10f && hsl.s <= 0.82f);
334 }
335
336 // Used to group lower_bound, upper_bound, goal HSL color together for prominent
337 // color calculation.
338 struct ColorBracket {
339 HSL lower_bound = {-1};
340 HSL upper_bound = {-1};
341 HSL goal = {-1};
342 };
343
CalculateProminentColors(const SkBitmap & bitmap,const std::vector<ColorBracket> & color_brackets,const gfx::Rect & region,base::Optional<ColorSwatchFilter> filter)344 std::vector<Swatch> CalculateProminentColors(
345 const SkBitmap& bitmap,
346 const std::vector<ColorBracket>& color_brackets,
347 const gfx::Rect& region,
348 base::Optional<ColorSwatchFilter> filter) {
349 DCHECK(!bitmap.empty());
350 DCHECK(!bitmap.isNull());
351
352 std::vector<Swatch> box_colors =
353 CalculateColorSwatches(bitmap, 12, region, filter);
354
355 std::vector<Swatch> best_colors(color_brackets.size(), Swatch());
356 if (box_colors.empty())
357 return best_colors;
358
359 size_t max_weight = 0;
360 for (auto& weighted : box_colors)
361 max_weight = std::max(max_weight, weighted.population);
362
363 // Given these box average colors, find the best one for each desired color
364 // profile. "Best" in this case means the color which fits in the provided
365 // bounds and comes closest to |goal|. It's possible that no color will fit in
366 // the provided bounds, in which case we'll return an empty color.
367 for (size_t i = 0; i < color_brackets.size(); ++i) {
368 double best_suitability = 0;
369 for (const auto& box_color : box_colors) {
370 HSL hsl;
371 SkColorToHSL(box_color.color, &hsl);
372 if (!IsWithinHSLRange(hsl, color_brackets[i].lower_bound,
373 color_brackets[i].upper_bound)) {
374 continue;
375 }
376
377 double suitability =
378 (1 - std::abs(hsl.s - color_brackets[i].goal.s)) * 3 +
379 (1 - std::abs(hsl.l - color_brackets[i].goal.l)) * 6.5 +
380 (box_color.population / static_cast<float>(max_weight)) * 0.5;
381 if (suitability > best_suitability) {
382 best_suitability = suitability;
383 best_colors[i] = box_color;
384 }
385 }
386 }
387
388 return best_colors;
389 }
390
391 } // namespace
392
KMeanImageSampler()393 KMeanImageSampler::KMeanImageSampler() {
394 }
395
~KMeanImageSampler()396 KMeanImageSampler::~KMeanImageSampler() {
397 }
398
GridSampler()399 GridSampler::GridSampler() : calls_(0) {
400 }
401
~GridSampler()402 GridSampler::~GridSampler() {
403 }
404
GetSample(int width,int height)405 int GridSampler::GetSample(int width, int height) {
406 // Hand-drawn bitmaps often have special outlines or feathering at the edges.
407 // Start our sampling inset from the top and left edges. For example, a 10x10
408 // image with 4 clusters would be sampled like this:
409 // ..........
410 // .0.4.8....
411 // ..........
412 // .1.5.9....
413 // ..........
414 // .2.6......
415 // ..........
416 // .3.7......
417 // ..........
418 // But don't inset if the image is too narrow or too short.
419 const int kInsetX = (width > 2 ? 1 : 0);
420 const int kInsetY = (height > 2 ? 1 : 0);
421 int x = kInsetX + (calls_ / kNumberOfClusters) *
422 ((width - 2 * kInsetX) / kNumberOfClusters);
423 int y = kInsetY + (calls_ % kNumberOfClusters) *
424 ((height - 2 * kInsetY) / kNumberOfClusters);
425 int index = x + (y * width);
426 ++calls_;
427 return index % (width * height);
428 }
429
FindClosestColor(const uint8_t * image,int width,int height,SkColor color)430 SkColor FindClosestColor(const uint8_t* image,
431 int width,
432 int height,
433 SkColor color) {
434 uint8_t in_r = SkColorGetR(color);
435 uint8_t in_g = SkColorGetG(color);
436 uint8_t in_b = SkColorGetB(color);
437 // Search using distance-squared to avoid expensive sqrt() operations.
438 int best_distance_squared = std::numeric_limits<int32_t>::max();
439 SkColor best_color = color;
440 const uint8_t* byte = image;
441 for (int i = 0; i < width * height; ++i) {
442 #if defined(ARCH_CPU_LITTLE_ENDIAN)
443 uint8_t b = *(byte++);
444 uint8_t g = *(byte++);
445 uint8_t r = *(byte++);
446 uint8_t a = *(byte++);
447 #else
448 uint8_t a = *(byte++);
449 uint8_t r = *(byte++);
450 uint8_t g = *(byte++);
451 uint8_t b = *(byte++);
452 #endif
453 // Ignore fully transparent pixels.
454 if (a == 0)
455 continue;
456 int distance_squared =
457 (in_b - b) * (in_b - b) +
458 (in_g - g) * (in_g - g) +
459 (in_r - r) * (in_r - r);
460 if (distance_squared < best_distance_squared) {
461 best_distance_squared = distance_squared;
462 best_color = SkColorSetRGB(r, g, b);
463 }
464 }
465 return best_color;
466 }
467
468 // For a 16x16 icon on an Intel Core i5 this function takes approximately
469 // 0.5 ms to run.
CalculateKMeanColorOfBuffer(uint8_t * decoded_data,int img_width,int img_height,const HSL & lower_bound,const HSL & upper_bound,KMeanImageSampler * sampler,bool find_closest)470 SkColor CalculateKMeanColorOfBuffer(uint8_t* decoded_data,
471 int img_width,
472 int img_height,
473 const HSL& lower_bound,
474 const HSL& upper_bound,
475 KMeanImageSampler* sampler,
476 bool find_closest) {
477 SkColor color = kDefaultBgColor;
478 if (img_width > 0 && img_height > 0) {
479 std::vector<KMeanCluster> clusters;
480 clusters.resize(static_cast<size_t>(kNumberOfClusters), KMeanCluster());
481
482 // Pick a starting point for each cluster
483 auto new_cluster = clusters.begin();
484 while (new_cluster != clusters.end()) {
485 // Try up to 10 times to find a unique color. If no unique color can be
486 // found, destroy this cluster.
487 bool color_unique = false;
488 for (int i = 0; i < 10; ++i) {
489 int pixel_pos = sampler->GetSample(img_width, img_height) %
490 (img_width * img_height);
491
492 #if defined(ARCH_CPU_LITTLE_ENDIAN)
493 uint8_t b = decoded_data[pixel_pos * 4];
494 uint8_t g = decoded_data[pixel_pos * 4 + 1];
495 uint8_t r = decoded_data[pixel_pos * 4 + 2];
496 uint8_t a = decoded_data[pixel_pos * 4 + 3];
497 #else
498 uint8_t a = decoded_data[pixel_pos * 4];
499 uint8_t r = decoded_data[pixel_pos * 4 + 1];
500 uint8_t g = decoded_data[pixel_pos * 4 + 2];
501 uint8_t b = decoded_data[pixel_pos * 4 + 3];
502 #endif
503 // Skip fully transparent pixels as they usually contain black in their
504 // RGB channels but do not contribute to the visual image.
505 if (a == 0)
506 continue;
507
508 // Loop through the previous clusters and check to see if we have seen
509 // this color before.
510 color_unique = true;
511 for (auto cluster = clusters.begin(); cluster != new_cluster;
512 ++cluster) {
513 if (cluster->IsAtCentroid(r, g, b)) {
514 color_unique = false;
515 break;
516 }
517 }
518
519 // If we have a unique color set the center of the cluster to
520 // that color.
521 if (color_unique) {
522 new_cluster->SetCentroid(r, g, b);
523 break;
524 }
525 }
526
527 // If we don't have a unique color erase this cluster.
528 if (!color_unique) {
529 new_cluster = clusters.erase(new_cluster);
530 } else {
531 // Have to increment the iterator here, otherwise the increment in the
532 // for loop will skip a cluster due to the erase if the color wasn't
533 // unique.
534 ++new_cluster;
535 }
536 }
537
538 // If all pixels in the image are transparent we will have no clusters.
539 if (clusters.empty())
540 return color;
541
542 bool convergence = false;
543 for (int iteration = 0;
544 iteration < kNumberOfIterations && !convergence;
545 ++iteration) {
546
547 // Loop through each pixel so we can place it in the appropriate cluster.
548 uint8_t* pixel = decoded_data;
549 uint8_t* decoded_data_end = decoded_data + (img_width * img_height * 4);
550 while (pixel < decoded_data_end) {
551 #if defined(ARCH_CPU_LITTLE_ENDIAN)
552 uint8_t b = *(pixel++);
553 uint8_t g = *(pixel++);
554 uint8_t r = *(pixel++);
555 uint8_t a = *(pixel++);
556 #else
557 uint8_t a = *(pixel++);
558 uint8_t r = *(pixel++);
559 uint8_t g = *(pixel++);
560 uint8_t b = *(pixel++);
561 #endif
562 // Skip transparent pixels, see above.
563 if (a == 0)
564 continue;
565
566 uint32_t distance_sqr_to_closest_cluster = UINT_MAX;
567 auto closest_cluster = clusters.begin();
568
569 // Figure out which cluster this color is closest to in RGB space.
570 for (auto cluster = clusters.begin(); cluster != clusters.end();
571 ++cluster) {
572 uint32_t distance_sqr = cluster->GetDistanceSqr(r, g, b);
573
574 if (distance_sqr < distance_sqr_to_closest_cluster) {
575 distance_sqr_to_closest_cluster = distance_sqr;
576 closest_cluster = cluster;
577 }
578 }
579
580 closest_cluster->AddPoint(r, g, b);
581 }
582
583 // Calculate the new cluster centers and see if we've converged or not.
584 convergence = true;
585 for (auto cluster = clusters.begin(); cluster != clusters.end();
586 ++cluster) {
587 convergence &= cluster->CompareCentroidWithAggregate();
588
589 cluster->RecomputeCentroid();
590 }
591 }
592
593 // Sort the clusters by population so we can tell what the most popular
594 // color is.
595 std::sort(clusters.begin(), clusters.end(),
596 KMeanCluster::SortKMeanClusterByWeight);
597
598 // Loop through the clusters to figure out which cluster has an appropriate
599 // color. Skip any that are too bright/dark and go in order of weight.
600 for (auto cluster = clusters.begin(); cluster != clusters.end();
601 ++cluster) {
602 uint8_t r, g, b;
603 cluster->GetCentroid(&r, &g, &b);
604
605 SkColor current_color = SkColorSetARGB(SK_AlphaOPAQUE, r, g, b);
606 HSL hsl;
607 SkColorToHSL(current_color, &hsl);
608 if (IsWithinHSLRange(hsl, lower_bound, upper_bound)) {
609 // If we found a valid color just set it and break. We don't want to
610 // check the other ones.
611 color = current_color;
612 break;
613 } else if (cluster == clusters.begin()) {
614 // We haven't found a valid color, but we are at the first color so
615 // set the color anyway to make sure we at least have a value here.
616 color = current_color;
617 }
618 }
619 }
620
621 // The K-mean cluster center will not usually be a color that appears in the
622 // image. If desired, find a color that actually appears.
623 return find_closest
624 ? FindClosestColor(decoded_data, img_width, img_height, color)
625 : color;
626 }
627
CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png,const HSL & lower_bound,const HSL & upper_bound,KMeanImageSampler * sampler)628 SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png,
629 const HSL& lower_bound,
630 const HSL& upper_bound,
631 KMeanImageSampler* sampler) {
632 int img_width = 0;
633 int img_height = 0;
634 std::vector<uint8_t> decoded_data;
635 SkColor color = kDefaultBgColor;
636
637 if (png.get() && png->size() &&
638 gfx::PNGCodec::Decode(png->front(), png->size(),
639 #if defined(ARCH_CPU_LITTLE_ENDIAN)
640 gfx::PNGCodec::FORMAT_BGRA,
641 #else
642 gfx::PNGCodec::FORMAT_ARGB,
643 #endif
644 &decoded_data, &img_width, &img_height)) {
645 return CalculateKMeanColorOfBuffer(&decoded_data[0], img_width, img_height,
646 lower_bound, upper_bound, sampler, true);
647 }
648 return color;
649 }
650
CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png)651 SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png) {
652 GridSampler sampler;
653 return CalculateKMeanColorOfPNG(
654 png, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler);
655 }
656
CalculateKMeanColorOfBitmap(const SkBitmap & bitmap,int height,const HSL & lower_bound,const HSL & upper_bound,bool find_closest)657 SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap,
658 int height,
659 const HSL& lower_bound,
660 const HSL& upper_bound,
661 bool find_closest) {
662 // Clamp the height being used to the height of the provided image (otherwise,
663 // we can end up creating a larger buffer than we have data for, and the end
664 // of the buffer will remain uninitialized after we copy/UnPreMultiply the
665 // image data into it).
666 height = base::ClampToRange(height, 0, bitmap.height());
667
668 // SkBitmap uses pre-multiplied alpha but the KMean clustering function
669 // above uses non-pre-multiplied alpha. Transform the bitmap before we
670 // analyze it because the function reads each pixel multiple times.
671 int pixel_count = bitmap.width() * height;
672 std::unique_ptr<uint32_t[]> image(new uint32_t[pixel_count]);
673
674 // Un-premultiplies each pixel in bitmap into the buffer. Requires
675 // approximately 10 microseconds for a 16x16 icon on an Intel Core i5.
676 uint32_t* in = static_cast<uint32_t*>(bitmap.getPixels());
677 uint32_t* out = image.get();
678 for (int i = 0; i < pixel_count; ++i)
679 *out++ = SkUnPreMultiply::PMColorToColor(*in++);
680
681 GridSampler sampler;
682 return CalculateKMeanColorOfBuffer(reinterpret_cast<uint8_t*>(image.get()),
683 bitmap.width(), height, lower_bound,
684 upper_bound, &sampler, find_closest);
685 }
686
CalculateKMeanColorOfBitmap(const SkBitmap & bitmap)687 SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap) {
688 return CalculateKMeanColorOfBitmap(
689 bitmap, bitmap.height(), kDefaultLowerHSLBound, kDefaultUpperHSLBound,
690 true);
691 }
692
693 const int kMaxConsideredPixelsForSwatches = 10007;
694
695 // This algorithm is a port of Android's Palette API. Compare to package
696 // android.support.v7.graphics and see that code for additional high-level
697 // explanation of this algorithm. There are some minor differences:
698 // * This code doesn't exclude the same color from being used for
699 // different color profiles.
700 // * This code doesn't try to heuristically derive missing colors from
701 // existing colors.
CalculateColorSwatches(const SkBitmap & bitmap,size_t max_swatches,const gfx::Rect & region,base::Optional<ColorSwatchFilter> filter)702 std::vector<Swatch> CalculateColorSwatches(
703 const SkBitmap& bitmap,
704 size_t max_swatches,
705 const gfx::Rect& region,
706 base::Optional<ColorSwatchFilter> filter) {
707 DCHECK(!bitmap.empty());
708 DCHECK(!bitmap.isNull());
709 DCHECK(!region.IsEmpty());
710 DCHECK_LE(region.width(), bitmap.width());
711 DCHECK_LE(region.height(), bitmap.height());
712
713 const int pixel_count = region.width() * region.height();
714
715 // For better performance, only consider at most 10k pixels (evenly
716 // distributed throughout the image). This has a very minor impact on the
717 // outcome but improves runtime substantially for large images. 10,007 is a
718 // prime number to reduce the chance of picking an unrepresentative sample.
719 const int pixel_increment =
720 std::max(1, pixel_count / kMaxConsideredPixelsForSwatches);
721 std::unordered_map<SkColor, int> color_counts(
722 kMaxConsideredPixelsForSwatches);
723
724 // First extract all colors into counts.
725 for (int i = 0; i < pixel_count; i += pixel_increment) {
726 const int x = region.x() + (i % region.width());
727 const int y = region.y() + (i / region.width());
728
729 const SkColor pixel = bitmap.getColor(x, y);
730 if (SkColorGetA(pixel) == SK_AlphaTRANSPARENT)
731 continue;
732
733 color_counts[pixel]++;
734 }
735
736 // Now throw out some uninteresting colors if there is a filter.
737 std::vector<SkColor> interesting_colors;
738 interesting_colors.reserve(color_counts.size());
739 for (auto color_count : color_counts) {
740 SkColor color = color_count.first;
741 if (!filter || filter->Run(color))
742 interesting_colors.push_back(color);
743 }
744
745 if (interesting_colors.empty())
746 return {};
747
748 // Group the colors into "boxes" and repeatedly split the most voluminous box.
749 // We stop the process when a box can no longer be split (there's only one
750 // color in it) or when the number of color boxes reaches |max_colors|.
751 //
752 // Boxes are sorted by volume with the most voluminous at the front of the PQ.
753 std::priority_queue<ColorBox, std::vector<ColorBox>,
754 bool (*)(const ColorBox&, const ColorBox&)>
755 boxes(&ColorBox::CompareByVolume);
756 boxes.emplace(&interesting_colors);
757 while (boxes.size() < max_swatches) {
758 auto box = boxes.top();
759 if (!box.CanSplit())
760 break;
761 boxes.pop();
762 boxes.push(box.Split());
763 boxes.push(box);
764 }
765
766 // Now extract a single color to represent each box. This is the average color
767 // in the box, weighted by the frequency of that color in the source image.
768 size_t max_weight = 0;
769 std::vector<Swatch> box_colors;
770 box_colors.reserve(max_swatches);
771 while (!boxes.empty()) {
772 box_colors.push_back(boxes.top().GetWeightedAverageColor(color_counts));
773 boxes.pop();
774 max_weight = std::max(max_weight, box_colors.back().population);
775 }
776
777 return box_colors;
778 }
779
CalculateProminentColorsOfBitmap(const SkBitmap & bitmap,const std::vector<ColorProfile> & color_profiles,gfx::Rect * region,ColorSwatchFilter filter)780 std::vector<color_utils::Swatch> CalculateProminentColorsOfBitmap(
781 const SkBitmap& bitmap,
782 const std::vector<ColorProfile>& color_profiles,
783 gfx::Rect* region,
784 ColorSwatchFilter filter) {
785 if (color_profiles.empty())
786 return std::vector<Swatch>();
787
788 size_t size = color_profiles.size();
789 if (bitmap.empty() || bitmap.isNull())
790 return std::vector<Swatch>(size, Swatch());
791
792 // The hue is not relevant to our bounds or goal colors.
793 std::vector<ColorBracket> color_brackets(size);
794 for (size_t i = 0; i < size; ++i) {
795 switch (color_profiles[i].luma) {
796 case LumaRange::ANY:
797 color_brackets[i].lower_bound.l = 0;
798 color_brackets[i].upper_bound.l = 1;
799 color_brackets[i].goal.l = 0.5f;
800 break;
801 case LumaRange::LIGHT:
802 color_brackets[i].lower_bound.l = 0.55f;
803 color_brackets[i].upper_bound.l = 1;
804 color_brackets[i].goal.l = 0.74f;
805 break;
806 case LumaRange::NORMAL:
807 color_brackets[i].lower_bound.l = 0.3f;
808 color_brackets[i].upper_bound.l = 0.7f;
809 color_brackets[i].goal.l = 0.5f;
810 break;
811 case LumaRange::DARK:
812 color_brackets[i].lower_bound.l = 0;
813 color_brackets[i].upper_bound.l = 0.45f;
814 color_brackets[i].goal.l = 0.26f;
815 break;
816 }
817
818 switch (color_profiles[i].saturation) {
819 case SaturationRange::ANY:
820 color_brackets[i].lower_bound.s = 0;
821 color_brackets[i].upper_bound.s = 1;
822 color_brackets[i].goal.s = 0.5f;
823 break;
824 case SaturationRange::VIBRANT:
825 color_brackets[i].lower_bound.s = 0.35f;
826 color_brackets[i].upper_bound.s = 1;
827 color_brackets[i].goal.s = 1;
828 break;
829 case SaturationRange::MUTED:
830 color_brackets[i].lower_bound.s = 0;
831 color_brackets[i].upper_bound.s = 0.4f;
832 color_brackets[i].goal.s = 0.3f;
833 break;
834 }
835 }
836
837 return CalculateProminentColors(
838 bitmap, color_brackets,
839 region ? *region : gfx::Rect(bitmap.width(), bitmap.height()),
840 filter.is_null() ? base::BindRepeating(&IsInterestingColor) : filter);
841 }
842
ComputeColorCovariance(const SkBitmap & bitmap)843 gfx::Matrix3F ComputeColorCovariance(const SkBitmap& bitmap) {
844 // First need basic stats to normalize each channel separately.
845 gfx::Matrix3F covariance = gfx::Matrix3F::Zeros();
846 if (!bitmap.getPixels())
847 return covariance;
848
849 // Assume ARGB_8888 format.
850 DCHECK(bitmap.colorType() == kN32_SkColorType);
851
852 int64_t r_sum = 0;
853 int64_t g_sum = 0;
854 int64_t b_sum = 0;
855 int64_t rr_sum = 0;
856 int64_t gg_sum = 0;
857 int64_t bb_sum = 0;
858 int64_t rg_sum = 0;
859 int64_t rb_sum = 0;
860 int64_t gb_sum = 0;
861
862 for (int y = 0; y < bitmap.height(); ++y) {
863 SkPMColor* current_color = static_cast<uint32_t*>(bitmap.getAddr32(0, y));
864 for (int x = 0; x < bitmap.width(); ++x, ++current_color) {
865 SkColor c = SkUnPreMultiply::PMColorToColor(*current_color);
866 SkColor r = SkColorGetR(c);
867 SkColor g = SkColorGetG(c);
868 SkColor b = SkColorGetB(c);
869
870 r_sum += r;
871 g_sum += g;
872 b_sum += b;
873 rr_sum += r * r;
874 gg_sum += g * g;
875 bb_sum += b * b;
876 rg_sum += r * g;
877 rb_sum += r * b;
878 gb_sum += g * b;
879 }
880 }
881
882 // Covariance (not normalized) is E(X*X.t) - m * m.t and this is how it
883 // is calculated below.
884 // Each row below represents a row of the matrix describing (co)variances
885 // of R, G and B channels with (R, G, B)
886 int pixel_n = bitmap.width() * bitmap.height();
887 covariance.set(
888 static_cast<float>(
889 static_cast<double>(rr_sum) / pixel_n -
890 static_cast<double>(r_sum * r_sum) / pixel_n / pixel_n),
891 static_cast<float>(
892 static_cast<double>(rg_sum) / pixel_n -
893 static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n),
894 static_cast<float>(
895 static_cast<double>(rb_sum) / pixel_n -
896 static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n),
897 static_cast<float>(
898 static_cast<double>(rg_sum) / pixel_n -
899 static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n),
900 static_cast<float>(
901 static_cast<double>(gg_sum) / pixel_n -
902 static_cast<double>(g_sum * g_sum) / pixel_n / pixel_n),
903 static_cast<float>(
904 static_cast<double>(gb_sum) / pixel_n -
905 static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n),
906 static_cast<float>(
907 static_cast<double>(rb_sum) / pixel_n -
908 static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n),
909 static_cast<float>(
910 static_cast<double>(gb_sum) / pixel_n -
911 static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n),
912 static_cast<float>(
913 static_cast<double>(bb_sum) / pixel_n -
914 static_cast<double>(b_sum * b_sum) / pixel_n / pixel_n));
915 return covariance;
916 }
917
ApplyColorReduction(const SkBitmap & source_bitmap,const gfx::Vector3dF & color_transform,bool fit_to_range,SkBitmap * target_bitmap)918 bool ApplyColorReduction(const SkBitmap& source_bitmap,
919 const gfx::Vector3dF& color_transform,
920 bool fit_to_range,
921 SkBitmap* target_bitmap) {
922 DCHECK(target_bitmap);
923 DCHECK(source_bitmap.getPixels());
924 DCHECK(target_bitmap->getPixels());
925 DCHECK_EQ(kN32_SkColorType, source_bitmap.colorType());
926 DCHECK_EQ(kAlpha_8_SkColorType, target_bitmap->colorType());
927 DCHECK_EQ(source_bitmap.height(), target_bitmap->height());
928 DCHECK_EQ(source_bitmap.width(), target_bitmap->width());
929 DCHECK(!source_bitmap.empty());
930
931 // Elements of color_transform are explicitly off-loaded to local values for
932 // efficiency reasons. Note that in practice images may correspond to entire
933 // tab captures.
934 float t0 = 0.0;
935 float tr = color_transform.x();
936 float tg = color_transform.y();
937 float tb = color_transform.z();
938
939 if (fit_to_range) {
940 // We will figure out min/max in a preprocessing step and adjust
941 // actual_transform as required.
942 float max_val = std::numeric_limits<float>::min();
943 float min_val = std::numeric_limits<float>::max();
944 for (int y = 0; y < source_bitmap.height(); ++y) {
945 const SkPMColor* source_color_row = static_cast<SkPMColor*>(
946 source_bitmap.getAddr32(0, y));
947 for (int x = 0; x < source_bitmap.width(); ++x) {
948 SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
949 uint8_t r = SkColorGetR(c);
950 uint8_t g = SkColorGetG(c);
951 uint8_t b = SkColorGetB(c);
952 float gray_level = tr * r + tg * g + tb * b;
953 max_val = std::max(max_val, gray_level);
954 min_val = std::min(min_val, gray_level);
955 }
956 }
957
958 // Adjust the transform so that the result is scaling.
959 float scale = 0.0;
960 t0 = -min_val;
961 if (max_val > min_val)
962 scale = 255.0f / (max_val - min_val);
963 t0 *= scale;
964 tr *= scale;
965 tg *= scale;
966 tb *= scale;
967 }
968
969 for (int y = 0; y < source_bitmap.height(); ++y) {
970 const SkPMColor* source_color_row = static_cast<SkPMColor*>(
971 source_bitmap.getAddr32(0, y));
972 uint8_t* target_color_row = target_bitmap->getAddr8(0, y);
973 for (int x = 0; x < source_bitmap.width(); ++x) {
974 SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
975 uint8_t r = SkColorGetR(c);
976 uint8_t g = SkColorGetG(c);
977 uint8_t b = SkColorGetB(c);
978
979 float gl = t0 + tr * r + tg * g + tb * b;
980 if (gl < 0)
981 gl = 0;
982 if (gl > 0xFF)
983 gl = 0xFF;
984 target_color_row[x] = static_cast<uint8_t>(gl);
985 }
986 }
987
988 return true;
989 }
990
991 } // color_utils
992