Home | History | Annotate | Download | only in gfx 
      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
    564