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 #include "ui/gfx/color_utils.h"
  17
  18 namespace color_utils {
  19 namespace {
  20
  21 // RGBA KMean Constants
  22 const uint32_t kNumberOfClusters = 4;
  23 const int kNumberOfIterations = 50;
  24
  25 const HSL kDefaultLowerHSLBound = {-1, -1, 0.15};
  26 const HSL kDefaultUpperHSLBound = {-1, -1, 0.85};
  27
  28 // Background Color Modification Constants
  29 const 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.
  35 class 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] = static_cast<uint8_t>(aggregate_[0] / counter_);
  71       centroid_[1] = static_cast<uint8_t>(aggregate_[1] / counter_);
  72       centroid_[2] = static_cast<uint8_t>(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.
 134 void 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
 145 KMeanImageSampler::KMeanImageSampler() {
 146 }
 147
 148 KMeanImageSampler::~KMeanImageSampler() {
 149 }
 150
 151 GridSampler::GridSampler() : calls_(0) {
 152 }
 153
 154 GridSampler::~GridSampler() {
 155 }
 156
 157 int 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
 181 SkColor 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.
 215 SkColor 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
 357 SkColor 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
 383 SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png) {
 384   GridSampler sampler;
 385   return CalculateKMeanColorOfPNG(
 386       png, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler);
 387 }
 388
 389 SkColor 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
 408 SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap) {
 409   GridSampler sampler;
 410   return CalculateKMeanColorOfBitmap(
 411       bitmap, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler);
 412 }
 413
 414 gfx::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() == kN32_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<float>(
 461           static_cast<double>(rr_sum) / pixel_n -
 462               static_cast<double>(r_sum * r_sum) / pixel_n / pixel_n),
 463       static_cast<float>(
 464           static_cast<double>(rg_sum) / pixel_n -
 465               static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n),
 466       static_cast<float>(
 467           static_cast<double>(rb_sum) / pixel_n -
 468               static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n),
 469       static_cast<float>(
 470           static_cast<double>(rg_sum) / pixel_n -
 471               static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n),
 472       static_cast<float>(
 473           static_cast<double>(gg_sum) / pixel_n -
 474               static_cast<double>(g_sum * g_sum) / pixel_n / pixel_n),
 475       static_cast<float>(
 476           static_cast<double>(gb_sum) / pixel_n -
 477               static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n),
 478       static_cast<float>(
 479           static_cast<double>(rb_sum) / pixel_n -
 480               static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n),
 481       static_cast<float>(
 482           static_cast<double>(gb_sum) / pixel_n -
 483               static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n),
 484       static_cast<float>(
 485           static_cast<double>(bb_sum) / pixel_n -
 486               static_cast<double>(b_sum * b_sum) / pixel_n / pixel_n));
 487   return covariance;
 488 }
 489
 490 bool ApplyColorReduction(const SkBitmap& source_bitmap,
 491                          const gfx::Vector3dF& color_transform,
 492                          bool fit_to_range,
 493                          SkBitmap* target_bitmap) {
 494   DCHECK(target_bitmap);
 495   SkAutoLockPixels source_lock(source_bitmap);
 496   SkAutoLockPixels target_lock(*target_bitmap);
 497
 498   DCHECK(source_bitmap.getPixels());
 499   DCHECK(target_bitmap->getPixels());
 500   DCHECK_EQ(kN32_SkColorType, source_bitmap.colorType());
 501   DCHECK_EQ(kAlpha_8_SkColorType, target_bitmap->colorType());
 502   DCHECK_EQ(source_bitmap.height(), target_bitmap->height());
 503   DCHECK_EQ(source_bitmap.width(), target_bitmap->width());
 504   DCHECK(!source_bitmap.empty());
 505
 506   // Elements of color_transform are explicitly off-loaded to local values for
 507   // efficiency reasons. Note that in practice images may correspond to entire
 508   // tab captures.
 509   float t0 = 0.0;
 510   float tr = color_transform.x();
 511   float tg = color_transform.y();
 512   float tb = color_transform.z();
 513
 514   if (fit_to_range) {
 515     // We will figure out min/max in a preprocessing step and adjust
 516     // actual_transform as required.
 517     float max_val = std::numeric_limits<float>::min();
 518     float min_val = std::numeric_limits<float>::max();
 519     for (int y = 0; y < source_bitmap.height(); ++y) {
 520       const SkPMColor* source_color_row = static_cast<SkPMColor*>(
 521           source_bitmap.getAddr32(0, y));
 522       for (int x = 0; x < source_bitmap.width(); ++x) {
 523         SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
 524         uint8_t r = SkColorGetR(c);
 525         uint8_t g = SkColorGetG(c);
 526         uint8_t b = SkColorGetB(c);
 527         float gray_level = tr * r + tg * g + tb * b;
 528         max_val = std::max(max_val, gray_level);
 529         min_val = std::min(min_val, gray_level);
 530       }
 531     }
 532
 533     // Adjust the transform so that the result is scaling.
 534     float scale = 0.0;
 535     t0 = -min_val;
 536     if (max_val > min_val)
 537       scale = 255.0f / (max_val - min_val);
 538     t0 *= scale;
 539     tr *= scale;
 540     tg *= scale;
 541     tb *= scale;
 542   }
 543
 544   for (int y = 0; y < source_bitmap.height(); ++y) {
 545     const SkPMColor* source_color_row = static_cast<SkPMColor*>(
 546         source_bitmap.getAddr32(0, y));
 547     uint8_t* target_color_row = target_bitmap->getAddr8(0, y);
 548     for (int x = 0; x < source_bitmap.width(); ++x) {
 549       SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
 550       uint8_t r = SkColorGetR(c);
 551       uint8_t g = SkColorGetG(c);
 552       uint8_t b = SkColorGetB(c);
 553
 554       float gl = t0 + tr * r + tg * g + tb * b;
 555       if (gl < 0)
 556         gl = 0;
 557       if (gl > 0xFF)
 558         gl = 0xFF;
 559       target_color_row[x] = static_cast<uint8_t>(gl);
 560     }
 561   }
 562
 563   return true;
 564 }
 565
 566 bool ComputePrincipalComponentImage(const SkBitmap& source_bitmap,
 567                                     SkBitmap* target_bitmap) {
 568   if (!target_bitmap) {
 569     NOTREACHED();
 570     return false;
 571   }
 572
 573   gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap);
 574   gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros();
 575   gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors);
 576   gfx::Vector3dF principal = eigenvectors.get_column(0);
 577   if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF())
 578     return false;  // This may happen for some edge cases.
 579   return ApplyColorReduction(source_bitmap, principal, true, target_bitmap);
 580 }
 581
 582 }  // color_utils