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 #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] = 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.
    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() == 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 
    481 bool 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 
    557 bool 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