ui/gfx/color_analysis.cc

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