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 <algorithm>
8#include <limits>
9#include <vector>
10
11#include "base/logging.h"
12#include "base/memory/scoped_ptr.h"
13#include "third_party/skia/include/core/SkBitmap.h"
14#include "third_party/skia/include/core/SkUnPreMultiply.h"
15#include "ui/gfx/codec/png_codec.h"
16#include "ui/gfx/color_utils.h"
17
18namespace color_utils {
19namespace {
20
21// RGBA KMean Constants
22const uint32_t kNumberOfClusters = 4;
23const int kNumberOfIterations = 50;
24
25const HSL kDefaultLowerHSLBound = {-1, -1, 0.15};
26const HSL kDefaultUpperHSLBound = {-1, -1, 0.85};
27
28// Background Color Modification Constants
29const SkColor kDefaultBgColor = SK_ColorWHITE;
30
31// Support class to hold information about each cluster of pixel data in
32// the KMean algorithm. While this class does not contain all of the points
33// that exist in the cluster, it keeps track of the aggregate sum so it can
34// compute the new center appropriately.
35class KMeanCluster {
36 public:
37  KMeanCluster() {
38    Reset();
39  }
40
41  void Reset() {
42    centroid[0] = centroid[1] = centroid[2] = 0;
43    aggregate[0] = aggregate[1] = aggregate[2] = 0;
44    counter = 0;
45    weight = 0;
46  }
47
48  inline void SetCentroid(uint8_t r, uint8_t g, uint8_t b) {
49    centroid[0] = r;
50    centroid[1] = g;
51    centroid[2] = b;
52  }
53
54  inline void GetCentroid(uint8_t* r, uint8_t* g, uint8_t* b) {
55    *r = centroid[0];
56    *g = centroid[1];
57    *b = centroid[2];
58  }
59
60  inline bool IsAtCentroid(uint8_t r, uint8_t g, uint8_t b) {
61    return r == centroid[0] && g == centroid[1] && b == centroid[2];
62  }
63
64  // Recomputes the centroid of the cluster based on the aggregate data. The
65  // number of points used to calculate this center is stored for weighting
66  // purposes. The aggregate and counter are then cleared to be ready for the
67  // next iteration.
68  inline void RecomputeCentroid() {
69    if (counter > 0) {
70      centroid[0] = aggregate[0] / counter;
71      centroid[1] = aggregate[1] / counter;
72      centroid[2] = aggregate[2] / counter;
73
74      aggregate[0] = aggregate[1] = aggregate[2] = 0;
75      weight = counter;
76      counter = 0;
77    }
78  }
79
80  inline void AddPoint(uint8_t r, uint8_t g, uint8_t b) {
81    aggregate[0] += r;
82    aggregate[1] += g;
83    aggregate[2] += b;
84    ++counter;
85  }
86
87  // Just returns the distance^2. Since we are comparing relative distances
88  // there is no need to perform the expensive sqrt() operation.
89  inline uint32_t GetDistanceSqr(uint8_t r, uint8_t g, uint8_t b) {
90    return (r - centroid[0]) * (r - centroid[0]) +
91           (g - centroid[1]) * (g - centroid[1]) +
92           (b - centroid[2]) * (b - centroid[2]);
93  }
94
95  // In order to determine if we have hit convergence or not we need to see
96  // if the centroid of the cluster has moved. This determines whether or
97  // not the centroid is the same as the aggregate sum of points that will be
98  // used to generate the next centroid.
99  inline bool CompareCentroidWithAggregate() {
100    if (counter == 0)
101      return false;
102
103    return aggregate[0] / counter == centroid[0] &&
104           aggregate[1] / counter == centroid[1] &&
105           aggregate[2] / counter == centroid[2];
106  }
107
108  // Returns the previous counter, which is used to determine the weight
109  // of the cluster for sorting.
110  inline uint32_t GetWeight() const {
111    return weight;
112  }
113
114  static bool SortKMeanClusterByWeight(const KMeanCluster& a,
115                                       const KMeanCluster& b) {
116    return a.GetWeight() > b.GetWeight();
117  }
118
119 private:
120  uint8_t centroid[3];
121
122  // Holds the sum of all the points that make up this cluster. Used to
123  // generate the next centroid as well as to check for convergence.
124  uint32_t aggregate[3];
125  uint32_t counter;
126
127  // The weight of the cluster, determined by how many points were used
128  // to generate the previous centroid.
129  uint32_t weight;
130};
131
132// Un-premultiplies each pixel in |bitmap| into an output |buffer|. Requires
133// approximately 10 microseconds for a 16x16 icon on an Intel Core i5.
134void UnPreMultiply(const SkBitmap& bitmap, uint32_t* buffer, int buffer_size) {
135  SkAutoLockPixels auto_lock(bitmap);
136  uint32_t* in = static_cast<uint32_t*>(bitmap.getPixels());
137  uint32_t* out = buffer;
138  int pixel_count = std::min(bitmap.width() * bitmap.height(), buffer_size);
139  for (int i = 0; i < pixel_count; ++i)
140    *out++ = SkUnPreMultiply::PMColorToColor(*in++);
141}
142
143} // namespace
144
145KMeanImageSampler::KMeanImageSampler() {
146}
147
148KMeanImageSampler::~KMeanImageSampler() {
149}
150
151GridSampler::GridSampler() : calls_(0) {
152}
153
154GridSampler::~GridSampler() {
155}
156
157int GridSampler::GetSample(int width, int height) {
158  // Hand-drawn bitmaps often have special outlines or feathering at the edges.
159  // Start our sampling inset from the top and left edges. For example, a 10x10
160  // image with 4 clusters would be sampled like this:
161  // ..........
162  // .0.4.8....
163  // ..........
164  // .1.5.9....
165  // ..........
166  // .2.6......
167  // ..........
168  // .3.7......
169  // ..........
170  const int kPadX = 1;
171  const int kPadY = 1;
172  int x = kPadX +
173      (calls_ / kNumberOfClusters) * ((width - 2 * kPadX) / kNumberOfClusters);
174  int y = kPadY +
175      (calls_ % kNumberOfClusters) * ((height - 2 * kPadY) / kNumberOfClusters);
176  int index = x + (y * width);
177  ++calls_;
178  return index % (width * height);
179}
180
181SkColor FindClosestColor(const uint8_t* image,
182                         int width,
183                         int height,
184                         SkColor color) {
185  uint8_t in_r = SkColorGetR(color);
186  uint8_t in_g = SkColorGetG(color);
187  uint8_t in_b = SkColorGetB(color);
188  // Search using distance-squared to avoid expensive sqrt() operations.
189  int best_distance_squared = kint32max;
190  SkColor best_color = color;
191  const uint8_t* byte = image;
192  for (int i = 0; i < width * height; ++i) {
193    uint8_t b = *(byte++);
194    uint8_t g = *(byte++);
195    uint8_t r = *(byte++);
196    uint8_t a = *(byte++);
197    // Ignore fully transparent pixels.
198    if (a == 0)
199      continue;
200    int distance_squared =
201        (in_b - b) * (in_b - b) +
202        (in_g - g) * (in_g - g) +
203        (in_r - r) * (in_r - r);
204    if (distance_squared < best_distance_squared) {
205      best_distance_squared = distance_squared;
206      best_color = SkColorSetRGB(r, g, b);
207    }
208  }
209  return best_color;
210}
211
212// For a 16x16 icon on an Intel Core i5 this function takes approximately
213// 0.5 ms to run.
214// TODO(port): This code assumes the CPU architecture is little-endian.
215SkColor CalculateKMeanColorOfBuffer(uint8_t* decoded_data,
216                                    int img_width,
217                                    int img_height,
218                                    const HSL& lower_bound,
219                                    const HSL& upper_bound,
220                                    KMeanImageSampler* sampler) {
221  SkColor color = kDefaultBgColor;
222  if (img_width > 0 && img_height > 0) {
223    std::vector<KMeanCluster> clusters;
224    clusters.resize(kNumberOfClusters, KMeanCluster());
225
226    // Pick a starting point for each cluster
227    std::vector<KMeanCluster>::iterator cluster = clusters.begin();
228    while (cluster != clusters.end()) {
229      // Try up to 10 times to find a unique color. If no unique color can be
230      // found, destroy this cluster.
231      bool color_unique = false;
232      for (int i = 0; i < 10; ++i) {
233        int pixel_pos = sampler->GetSample(img_width, img_height) %
234            (img_width * img_height);
235
236        uint8_t b = decoded_data[pixel_pos * 4];
237        uint8_t g = decoded_data[pixel_pos * 4 + 1];
238        uint8_t r = decoded_data[pixel_pos * 4 + 2];
239        uint8_t a = decoded_data[pixel_pos * 4 + 3];
240        // Skip fully transparent pixels as they usually contain black in their
241        // RGB channels but do not contribute to the visual image.
242        if (a == 0)
243          continue;
244
245        // Loop through the previous clusters and check to see if we have seen
246        // this color before.
247        color_unique = true;
248        for (std::vector<KMeanCluster>::iterator
249            cluster_check = clusters.begin();
250            cluster_check != cluster; ++cluster_check) {
251          if (cluster_check->IsAtCentroid(r, g, b)) {
252            color_unique = false;
253            break;
254          }
255        }
256
257        // If we have a unique color set the center of the cluster to
258        // that color.
259        if (color_unique) {
260          cluster->SetCentroid(r, g, b);
261          break;
262        }
263      }
264
265      // If we don't have a unique color erase this cluster.
266      if (!color_unique) {
267        cluster = clusters.erase(cluster);
268      } else {
269        // Have to increment the iterator here, otherwise the increment in the
270        // for loop will skip a cluster due to the erase if the color wasn't
271        // unique.
272        ++cluster;
273      }
274    }
275
276    // If all pixels in the image are transparent we will have no clusters.
277    if (clusters.empty())
278      return color;
279
280    bool convergence = false;
281    for (int iteration = 0;
282        iteration < kNumberOfIterations && !convergence;
283        ++iteration) {
284
285      // Loop through each pixel so we can place it in the appropriate cluster.
286      uint8_t* pixel = decoded_data;
287      uint8_t* decoded_data_end = decoded_data + (img_width * img_height * 4);
288      while (pixel < decoded_data_end) {
289        uint8_t b = *(pixel++);
290        uint8_t g = *(pixel++);
291        uint8_t r = *(pixel++);
292        uint8_t a = *(pixel++);
293        // Skip transparent pixels, see above.
294        if (a == 0)
295          continue;
296
297        uint32_t distance_sqr_to_closest_cluster = UINT_MAX;
298        std::vector<KMeanCluster>::iterator closest_cluster = clusters.begin();
299
300        // Figure out which cluster this color is closest to in RGB space.
301        for (std::vector<KMeanCluster>::iterator cluster = clusters.begin();
302            cluster != clusters.end(); ++cluster) {
303          uint32_t distance_sqr = cluster->GetDistanceSqr(r, g, b);
304
305          if (distance_sqr < distance_sqr_to_closest_cluster) {
306            distance_sqr_to_closest_cluster = distance_sqr;
307            closest_cluster = cluster;
308          }
309        }
310
311        closest_cluster->AddPoint(r, g, b);
312      }
313
314      // Calculate the new cluster centers and see if we've converged or not.
315      convergence = true;
316      for (std::vector<KMeanCluster>::iterator cluster = clusters.begin();
317          cluster != clusters.end(); ++cluster) {
318        convergence &= cluster->CompareCentroidWithAggregate();
319
320        cluster->RecomputeCentroid();
321      }
322    }
323
324    // Sort the clusters by population so we can tell what the most popular
325    // color is.
326    std::sort(clusters.begin(), clusters.end(),
327              KMeanCluster::SortKMeanClusterByWeight);
328
329    // Loop through the clusters to figure out which cluster has an appropriate
330    // color. Skip any that are too bright/dark and go in order of weight.
331    for (std::vector<KMeanCluster>::iterator cluster = clusters.begin();
332        cluster != clusters.end(); ++cluster) {
333      uint8_t r, g, b;
334      cluster->GetCentroid(&r, &g, &b);
335
336      SkColor current_color = SkColorSetARGB(SK_AlphaOPAQUE, r, g, b);
337      HSL hsl;
338      SkColorToHSL(current_color, &hsl);
339      if (IsWithinHSLRange(hsl, lower_bound, upper_bound)) {
340        // If we found a valid color just set it and break. We don't want to
341        // check the other ones.
342        color = current_color;
343        break;
344      } else if (cluster == clusters.begin()) {
345        // We haven't found a valid color, but we are at the first color so
346        // set the color anyway to make sure we at least have a value here.
347        color = current_color;
348      }
349    }
350  }
351
352  // Find a color that actually appears in the image (the K-mean cluster center
353  // will not usually be a color that appears in the image).
354  return FindClosestColor(decoded_data, img_width, img_height, color);
355}
356
357SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png,
358                                 const HSL& lower_bound,
359                                 const HSL& upper_bound,
360                                 KMeanImageSampler* sampler) {
361  int img_width = 0;
362  int img_height = 0;
363  std::vector<uint8_t> decoded_data;
364  SkColor color = kDefaultBgColor;
365
366  if (png.get() && png->size() &&
367      gfx::PNGCodec::Decode(png->front(),
368                            png->size(),
369                            gfx::PNGCodec::FORMAT_BGRA,
370                            &decoded_data,
371                            &img_width,
372                            &img_height)) {
373    return CalculateKMeanColorOfBuffer(&decoded_data[0],
374                                       img_width,
375                                       img_height,
376                                       lower_bound,
377                                       upper_bound,
378                                       sampler);
379  }
380  return color;
381}
382
383SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png) {
384  GridSampler sampler;
385  return CalculateKMeanColorOfPNG(
386      png, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler);
387}
388
389SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap,
390                                    const HSL& lower_bound,
391                                    const HSL& upper_bound,
392                                    KMeanImageSampler* sampler) {
393  // SkBitmap uses pre-multiplied alpha but the KMean clustering function
394  // above uses non-pre-multiplied alpha. Transform the bitmap before we
395  // analyze it because the function reads each pixel multiple times.
396  int pixel_count = bitmap.width() * bitmap.height();
397  scoped_ptr<uint32_t[]> image(new uint32_t[pixel_count]);
398  UnPreMultiply(bitmap, image.get(), pixel_count);
399
400  return CalculateKMeanColorOfBuffer(reinterpret_cast<uint8_t*>(image.get()),
401                                     bitmap.width(),
402                                     bitmap.height(),
403                                     lower_bound,
404                                     upper_bound,
405                                     sampler);
406}
407
408SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap) {
409  GridSampler sampler;
410  return CalculateKMeanColorOfBitmap(
411      bitmap, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler);
412}
413
414gfx::Matrix3F ComputeColorCovariance(const SkBitmap& bitmap) {
415  // First need basic stats to normalize each channel separately.
416  SkAutoLockPixels bitmap_lock(bitmap);
417  gfx::Matrix3F covariance = gfx::Matrix3F::Zeros();
418  if (!bitmap.getPixels())
419    return covariance;
420
421  // Assume ARGB_8888 format.
422  DCHECK(bitmap.colorType() == kPMColor_SkColorType);
423
424  int64_t r_sum = 0;
425  int64_t g_sum = 0;
426  int64_t b_sum = 0;
427  int64_t rr_sum = 0;
428  int64_t gg_sum = 0;
429  int64_t bb_sum = 0;
430  int64_t rg_sum = 0;
431  int64_t rb_sum = 0;
432  int64_t gb_sum = 0;
433
434  for (int y = 0; y < bitmap.height(); ++y) {
435    SkPMColor* current_color = static_cast<uint32_t*>(bitmap.getAddr32(0, y));
436    for (int x = 0; x < bitmap.width(); ++x, ++current_color) {
437      SkColor c = SkUnPreMultiply::PMColorToColor(*current_color);
438      SkColor r = SkColorGetR(c);
439      SkColor g = SkColorGetG(c);
440      SkColor b = SkColorGetB(c);
441
442      r_sum += r;
443      g_sum += g;
444      b_sum += b;
445      rr_sum += r * r;
446      gg_sum += g * g;
447      bb_sum += b * b;
448      rg_sum += r * g;
449      rb_sum += r * b;
450      gb_sum += g * b;
451    }
452  }
453
454  // Covariance (not normalized) is E(X*X.t) - m * m.t and this is how it
455  // is calculated below.
456  // Each row below represents a row of the matrix describing (co)variances
457  // of R, G and B channels with (R, G, B)
458  int pixel_n = bitmap.width() * bitmap.height();
459  covariance.set(
460      (static_cast<double>(rr_sum) / pixel_n -
461       static_cast<double>(r_sum * r_sum) / pixel_n / pixel_n),
462      (static_cast<double>(rg_sum) / pixel_n -
463       static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n),
464      (static_cast<double>(rb_sum) / pixel_n -
465       static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n),
466      (static_cast<double>(rg_sum) / pixel_n -
467       static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n),
468      (static_cast<double>(gg_sum) / pixel_n -
469       static_cast<double>(g_sum * g_sum) / pixel_n / pixel_n),
470      (static_cast<double>(gb_sum) / pixel_n -
471       static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n),
472      (static_cast<double>(rb_sum) / pixel_n -
473       static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n),
474      (static_cast<double>(gb_sum) / pixel_n -
475       static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n),
476      (static_cast<double>(bb_sum) / pixel_n -
477       static_cast<double>(b_sum * b_sum) / pixel_n / pixel_n));
478  return covariance;
479}
480
481bool ApplyColorReduction(const SkBitmap& source_bitmap,
482                         const gfx::Vector3dF& color_transform,
483                         bool fit_to_range,
484                         SkBitmap* target_bitmap) {
485  DCHECK(target_bitmap);
486  SkAutoLockPixels source_lock(source_bitmap);
487  SkAutoLockPixels target_lock(*target_bitmap);
488
489  DCHECK(source_bitmap.getPixels());
490  DCHECK(target_bitmap->getPixels());
491  DCHECK_EQ(kPMColor_SkColorType, source_bitmap.colorType());
492  DCHECK_EQ(kAlpha_8_SkColorType, target_bitmap->colorType());
493  DCHECK_EQ(source_bitmap.height(), target_bitmap->height());
494  DCHECK_EQ(source_bitmap.width(), target_bitmap->width());
495  DCHECK(!source_bitmap.empty());
496
497  // Elements of color_transform are explicitly off-loaded to local values for
498  // efficiency reasons. Note that in practice images may correspond to entire
499  // tab captures.
500  float t0 = 0.0;
501  float tr = color_transform.x();
502  float tg = color_transform.y();
503  float tb = color_transform.z();
504
505  if (fit_to_range) {
506    // We will figure out min/max in a preprocessing step and adjust
507    // actual_transform as required.
508    float max_val = std::numeric_limits<float>::min();
509    float min_val = std::numeric_limits<float>::max();
510    for (int y = 0; y < source_bitmap.height(); ++y) {
511      const SkPMColor* source_color_row = static_cast<SkPMColor*>(
512          source_bitmap.getAddr32(0, y));
513      for (int x = 0; x < source_bitmap.width(); ++x) {
514        SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
515        float r = SkColorGetR(c);
516        float g = SkColorGetG(c);
517        float b = SkColorGetB(c);
518        float gray_level = tr * r + tg * g + tb * b;
519        max_val = std::max(max_val, gray_level);
520        min_val = std::min(min_val, gray_level);
521      }
522    }
523
524    // Adjust the transform so that the result is scaling.
525    float scale = 0.0;
526    t0 = -min_val;
527    if (max_val > min_val)
528      scale = 255.0 / (max_val - min_val);
529    t0 *= scale;
530    tr *= scale;
531    tg *= scale;
532    tb *= scale;
533  }
534
535  for (int y = 0; y < source_bitmap.height(); ++y) {
536    const SkPMColor* source_color_row = static_cast<SkPMColor*>(
537        source_bitmap.getAddr32(0, y));
538    uint8_t* target_color_row = target_bitmap->getAddr8(0, y);
539    for (int x = 0; x < source_bitmap.width(); ++x) {
540      SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
541      float r = SkColorGetR(c);
542      float g = SkColorGetG(c);
543      float b = SkColorGetB(c);
544
545      float gl = t0 + tr * r + tg * g + tb * b;
546      if (gl < 0)
547        gl = 0;
548      if (gl > 0xFF)
549        gl = 0xFF;
550      target_color_row[x] = static_cast<uint8_t>(gl);
551    }
552  }
553
554  return true;
555}
556
557bool ComputePrincipalComponentImage(const SkBitmap& source_bitmap,
558                                    SkBitmap* target_bitmap) {
559  if (!target_bitmap) {
560    NOTREACHED();
561    return false;
562  }
563
564  gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap);
565  gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros();
566  gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors);
567  gfx::Vector3dF principal = eigenvectors.get_column(0);
568  if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF())
569    return false;  // This may happen for some edge cases.
570  return ApplyColorReduction(source_bitmap, principal, true, target_bitmap);
571}
572
573}  // color_utils
574