15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "ui/gfx/color_analysis.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <limits> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/memory/scoped_ptr.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "third_party/skia/include/core/SkBitmap.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "third_party/skia/include/core/SkUnPreMultiply.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "ui/gfx/codec/png_codec.h" 1646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)#include "ui/gfx/color_utils.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)namespace color_utils { 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// RGBA KMean Constants 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const uint32_t kNumberOfClusters = 4; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kNumberOfIterations = 50; 2446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) 2546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)const HSL kDefaultLowerHSLBound = {-1, -1, 0.15}; 2646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)const HSL kDefaultUpperHSLBound = {-1, -1, 0.85}; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Background Color Modification Constants 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const SkColor kDefaultBgColor = SK_ColorWHITE; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Support class to hold information about each cluster of pixel data in 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the KMean algorithm. While this class does not contain all of the points 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that exist in the cluster, it keeps track of the aggregate sum so it can 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// compute the new center appropriately. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class KMeanCluster { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KMeanCluster() { 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Reset(); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Reset() { 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[0] = centroid[1] = centroid[2] = 0; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[0] = aggregate[1] = aggregate[2] = 0; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter = 0; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) weight = 0; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void SetCentroid(uint8_t r, uint8_t g, uint8_t b) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[0] = r; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[1] = g; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[2] = b; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void GetCentroid(uint8_t* r, uint8_t* g, uint8_t* b) { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *r = centroid[0]; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *g = centroid[1]; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *b = centroid[2]; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline bool IsAtCentroid(uint8_t r, uint8_t g, uint8_t b) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return r == centroid[0] && g == centroid[1] && b == centroid[2]; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Recomputes the centroid of the cluster based on the aggregate data. The 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // number of points used to calculate this center is stored for weighting 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // purposes. The aggregate and counter are then cleared to be ready for the 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // next iteration. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void RecomputeCentroid() { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (counter > 0) { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[0] = aggregate[0] / counter; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[1] = aggregate[1] / counter; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) centroid[2] = aggregate[2] / counter; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[0] = aggregate[1] = aggregate[2] = 0; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) weight = counter; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter = 0; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void AddPoint(uint8_t r, uint8_t g, uint8_t b) { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[0] += r; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[1] += g; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[2] += b; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++counter; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Just returns the distance^2. Since we are comparing relative distances 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // there is no need to perform the expensive sqrt() operation. 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline uint32_t GetDistanceSqr(uint8_t r, uint8_t g, uint8_t b) { 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (r - centroid[0]) * (r - centroid[0]) + 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (g - centroid[1]) * (g - centroid[1]) + 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (b - centroid[2]) * (b - centroid[2]); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In order to determine if we have hit convergence or not we need to see 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if the centroid of the cluster has moved. This determines whether or 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not the centroid is the same as the aggregate sum of points that will be 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // used to generate the next centroid. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline bool CompareCentroidWithAggregate() { 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (counter == 0) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return aggregate[0] / counter == centroid[0] && 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[1] / counter == centroid[1] && 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aggregate[2] / counter == centroid[2]; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the previous counter, which is used to determine the weight 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of the cluster for sorting. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline uint32_t GetWeight() const { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return weight; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool SortKMeanClusterByWeight(const KMeanCluster& a, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const KMeanCluster& b) { 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return a.GetWeight() > b.GetWeight(); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t centroid[3]; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Holds the sum of all the points that make up this cluster. Used to 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // generate the next centroid as well as to check for convergence. 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t aggregate[3]; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t counter; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The weight of the cluster, determined by how many points were used 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to generate the previous centroid. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t weight; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Un-premultiplies each pixel in |bitmap| into an output |buffer|. Requires 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// approximately 10 microseconds for a 16x16 icon on an Intel Core i5. 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void UnPreMultiply(const SkBitmap& bitmap, uint32_t* buffer, int buffer_size) { 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkAutoLockPixels auto_lock(bitmap); 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint32_t* in = static_cast<uint32_t*>(bitmap.getPixels()); 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint32_t* out = buffer; 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int pixel_count = std::min(bitmap.width() * bitmap.height(), buffer_size); 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < pixel_count; ++i) 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *out++ = SkUnPreMultiply::PMColorToColor(*in++); 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)KMeanImageSampler::KMeanImageSampler() { 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)KMeanImageSampler::~KMeanImageSampler() { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)GridSampler::GridSampler() : calls_(0) { 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)GridSampler::~GridSampler() { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int GridSampler::GetSample(int width, int height) { 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Hand-drawn bitmaps often have special outlines or feathering at the edges. 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Start our sampling inset from the top and left edges. For example, a 10x10 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // image with 4 clusters would be sampled like this: 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .......... 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .0.4.8.... 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .......... 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .1.5.9.... 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .......... 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .2.6...... 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .......... 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .3.7...... 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // .......... 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const int kPadX = 1; 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const int kPadY = 1; 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int x = kPadX + 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (calls_ / kNumberOfClusters) * ((width - 2 * kPadX) / kNumberOfClusters); 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int y = kPadY + 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (calls_ % kNumberOfClusters) * ((height - 2 * kPadY) / kNumberOfClusters); 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int index = x + (y * width); 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ++calls_; 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return index % (width * height); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)SkColor FindClosestColor(const uint8_t* image, 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int width, 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int height, 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor color) { 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t in_r = SkColorGetR(color); 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t in_g = SkColorGetG(color); 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t in_b = SkColorGetB(color); 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Search using distance-squared to avoid expensive sqrt() operations. 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int best_distance_squared = kint32max; 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor best_color = color; 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const uint8_t* byte = image; 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int i = 0; i < width * height; ++i) { 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t b = *(byte++); 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t g = *(byte++); 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t r = *(byte++); 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t a = *(byte++); 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Ignore fully transparent pixels. 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (a == 0) 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) continue; 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int distance_squared = 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (in_b - b) * (in_b - b) + 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (in_g - g) * (in_g - g) + 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (in_r - r) * (in_r - r); 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (distance_squared < best_distance_squared) { 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) best_distance_squared = distance_squared; 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) best_color = SkColorSetRGB(r, g, b); 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return best_color; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// For a 16x16 icon on an Intel Core i5 this function takes approximately 2132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 0.5 ms to run. 2142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// TODO(port): This code assumes the CPU architecture is little-endian. 2152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)SkColor CalculateKMeanColorOfBuffer(uint8_t* decoded_data, 2162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int img_width, 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int img_height, 21846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) const HSL& lower_bound, 21946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) const HSL& upper_bound, 2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) KMeanImageSampler* sampler) { 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkColor color = kDefaultBgColor; 2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (img_width > 0 && img_height > 0) { 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<KMeanCluster> clusters; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) clusters.resize(kNumberOfClusters, KMeanCluster()); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pick a starting point for each cluster 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<KMeanCluster>::iterator cluster = clusters.begin(); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (cluster != clusters.end()) { 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try up to 10 times to find a unique color. If no unique color can be 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // found, destroy this cluster. 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool color_unique = false; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < 10; ++i) { 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int pixel_pos = sampler->GetSample(img_width, img_height) % 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (img_width * img_height); 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t b = decoded_data[pixel_pos * 4]; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t g = decoded_data[pixel_pos * 4 + 1]; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t r = decoded_data[pixel_pos * 4 + 2]; 2392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t a = decoded_data[pixel_pos * 4 + 3]; 2402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Skip fully transparent pixels as they usually contain black in their 2412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // RGB channels but do not contribute to the visual image. 2422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (a == 0) 2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) continue; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Loop through the previous clusters and check to see if we have seen 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this color before. 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) color_unique = true; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::vector<KMeanCluster>::iterator 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster_check = clusters.begin(); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster_check != cluster; ++cluster_check) { 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cluster_check->IsAtCentroid(r, g, b)) { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) color_unique = false; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we have a unique color set the center of the cluster to 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that color. 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (color_unique) { 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster->SetCentroid(r, g, b); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we don't have a unique color erase this cluster. 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!color_unique) { 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster = clusters.erase(cluster); 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Have to increment the iterator here, otherwise the increment in the 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for loop will skip a cluster due to the erase if the color wasn't 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // unique. 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++cluster; 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If all pixels in the image are transparent we will have no clusters. 2772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (clusters.empty()) 2782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return color; 2792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool convergence = false; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int iteration = 0; 2822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iteration < kNumberOfIterations && !convergence; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++iteration) { 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Loop through each pixel so we can place it in the appropriate cluster. 2862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t* pixel = decoded_data; 2872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t* decoded_data_end = decoded_data + (img_width * img_height * 4); 2882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (pixel < decoded_data_end) { 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t b = *(pixel++); 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t g = *(pixel++); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t r = *(pixel++); 2922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t a = *(pixel++); 2932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Skip transparent pixels, see above. 2942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (a == 0) 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t distance_sqr_to_closest_cluster = UINT_MAX; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::vector<KMeanCluster>::iterator closest_cluster = clusters.begin(); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Figure out which cluster this color is closest to in RGB space. 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::vector<KMeanCluster>::iterator cluster = clusters.begin(); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster != clusters.end(); ++cluster) { 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t distance_sqr = cluster->GetDistanceSqr(r, g, b); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (distance_sqr < distance_sqr_to_closest_cluster) { 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) distance_sqr_to_closest_cluster = distance_sqr; 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) closest_cluster = cluster; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) closest_cluster->AddPoint(r, g, b); 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Calculate the new cluster centers and see if we've converged or not. 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) convergence = true; 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::vector<KMeanCluster>::iterator cluster = clusters.begin(); 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster != clusters.end(); ++cluster) { 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) convergence &= cluster->CompareCentroidWithAggregate(); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster->RecomputeCentroid(); 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sort the clusters by population so we can tell what the most popular 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // color is. 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::sort(clusters.begin(), clusters.end(), 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KMeanCluster::SortKMeanClusterByWeight); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Loop through the clusters to figure out which cluster has an appropriate 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // color. Skip any that are too bright/dark and go in order of weight. 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (std::vector<KMeanCluster>::iterator cluster = clusters.begin(); 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster != clusters.end(); ++cluster) { 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8_t r, g, b; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cluster->GetCentroid(&r, &g, &b); 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 33646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) SkColor current_color = SkColorSetARGB(SK_AlphaOPAQUE, r, g, b); 33746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) HSL hsl; 33846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) SkColorToHSL(current_color, &hsl); 33946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) if (IsWithinHSLRange(hsl, lower_bound, upper_bound)) { 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we found a valid color just set it and break. We don't want to 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // check the other ones. 34246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) color = current_color; 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (cluster == clusters.begin()) { 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We haven't found a valid color, but we are at the first color so 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // set the color anyway to make sure we at least have a value here. 34746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) color = current_color; 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Find a color that actually appears in the image (the K-mean cluster center 3532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // will not usually be a color that appears in the image). 3542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return FindClosestColor(decoded_data, img_width, img_height, color); 3552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png, 35846d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) const HSL& lower_bound, 35946d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) const HSL& upper_bound, 3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) KMeanImageSampler* sampler) { 3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int img_width = 0; 3622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int img_height = 0; 3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::vector<uint8_t> decoded_data; 3642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor color = kDefaultBgColor; 3652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 36646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) if (png.get() && png->size() && 3672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::PNGCodec::Decode(png->front(), 3682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) png->size(), 3692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::PNGCodec::FORMAT_BGRA, 3702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) &decoded_data, 3712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) &img_width, 3722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) &img_height)) { 3732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return CalculateKMeanColorOfBuffer(&decoded_data[0], 3742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) img_width, 3752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) img_height, 37646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) lower_bound, 37746d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) upper_bound, 3782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) sampler); 3792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return color; 3812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 383cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)SkColor CalculateKMeanColorOfPNG(scoped_refptr<base::RefCountedMemory> png) { 384cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) GridSampler sampler; 38546d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) return CalculateKMeanColorOfPNG( 38646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) png, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler); 387cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)} 388cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 389cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap, 39046d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) const HSL& lower_bound, 39146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) const HSL& upper_bound, 392cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) KMeanImageSampler* sampler) { 3932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // SkBitmap uses pre-multiplied alpha but the KMean clustering function 3942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // above uses non-pre-multiplied alpha. Transform the bitmap before we 3952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // analyze it because the function reads each pixel multiple times. 3962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int pixel_count = bitmap.width() * bitmap.height(); 3972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scoped_ptr<uint32_t[]> image(new uint32_t[pixel_count]); 3982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) UnPreMultiply(bitmap, image.get(), pixel_count); 3992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 400cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return CalculateKMeanColorOfBuffer(reinterpret_cast<uint8_t*>(image.get()), 401cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bitmap.width(), 402cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bitmap.height(), 40346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) lower_bound, 40446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) upper_bound, 405cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) sampler); 406cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)} 407cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 408cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap) { 4092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) GridSampler sampler; 410cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return CalculateKMeanColorOfBitmap( 41146d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) bitmap, kDefaultLowerHSLBound, kDefaultUpperHSLBound, &sampler); 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)gfx::Matrix3F ComputeColorCovariance(const SkBitmap& bitmap) { 4152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // First need basic stats to normalize each channel separately. 4162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkAutoLockPixels bitmap_lock(bitmap); 4172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Matrix3F covariance = gfx::Matrix3F::Zeros(); 4182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!bitmap.getPixels()) 4192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return covariance; 4202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Assume ARGB_8888 format. 422a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK(bitmap.colorType() == kPMColor_SkColorType); 4232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t r_sum = 0; 4252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t g_sum = 0; 4262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t b_sum = 0; 4272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t rr_sum = 0; 4282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t gg_sum = 0; 4292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t bb_sum = 0; 4302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t rg_sum = 0; 4312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t rb_sum = 0; 4322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int64_t gb_sum = 0; 4332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int y = 0; y < bitmap.height(); ++y) { 4352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkPMColor* current_color = static_cast<uint32_t*>(bitmap.getAddr32(0, y)); 4362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int x = 0; x < bitmap.width(); ++x, ++current_color) { 4372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor c = SkUnPreMultiply::PMColorToColor(*current_color); 4382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor r = SkColorGetR(c); 4392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor g = SkColorGetG(c); 4402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor b = SkColorGetB(c); 4412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) r_sum += r; 4432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) g_sum += g; 4442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) b_sum += b; 4452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rr_sum += r * r; 4462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gg_sum += g * g; 4472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bb_sum += b * b; 4482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rg_sum += r * g; 4492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) rb_sum += r * b; 4502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gb_sum += g * b; 4512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Covariance (not normalized) is E(X*X.t) - m * m.t and this is how it 4552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // is calculated below. 4562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Each row below represents a row of the matrix describing (co)variances 4572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // of R, G and B channels with (R, G, B) 4582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int pixel_n = bitmap.width() * bitmap.height(); 4592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) covariance.set( 4602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(rr_sum) / pixel_n - 4612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(r_sum * r_sum) / pixel_n / pixel_n), 4622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(rg_sum) / pixel_n - 4632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n), 4642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(rb_sum) / pixel_n - 4652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n), 4662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(rg_sum) / pixel_n - 4672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n), 4682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(gg_sum) / pixel_n - 4692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(g_sum * g_sum) / pixel_n / pixel_n), 4702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(gb_sum) / pixel_n - 4712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n), 4722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(rb_sum) / pixel_n - 4732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n), 4742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(gb_sum) / pixel_n - 4752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n), 4762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) (static_cast<double>(bb_sum) / pixel_n - 4772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) static_cast<double>(b_sum * b_sum) / pixel_n / pixel_n)); 4782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return covariance; 4792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool ApplyColorReduction(const SkBitmap& source_bitmap, 4822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const gfx::Vector3dF& color_transform, 4832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool fit_to_range, 4842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkBitmap* target_bitmap) { 4852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(target_bitmap); 4862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkAutoLockPixels source_lock(source_bitmap); 4872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkAutoLockPixels target_lock(*target_bitmap); 4882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(source_bitmap.getPixels()); 4902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(target_bitmap->getPixels()); 491a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_EQ(kPMColor_SkColorType, source_bitmap.colorType()); 492a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_EQ(kAlpha_8_SkColorType, target_bitmap->colorType()); 4932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_EQ(source_bitmap.height(), target_bitmap->height()); 4942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_EQ(source_bitmap.width(), target_bitmap->width()); 4952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(!source_bitmap.empty()); 4962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Elements of color_transform are explicitly off-loaded to local values for 4982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // efficiency reasons. Note that in practice images may correspond to entire 4992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // tab captures. 5002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float t0 = 0.0; 5012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float tr = color_transform.x(); 5022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float tg = color_transform.y(); 5032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float tb = color_transform.z(); 5042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (fit_to_range) { 5062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // We will figure out min/max in a preprocessing step and adjust 5072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // actual_transform as required. 5082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float max_val = std::numeric_limits<float>::min(); 5092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float min_val = std::numeric_limits<float>::max(); 5102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int y = 0; y < source_bitmap.height(); ++y) { 5112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const SkPMColor* source_color_row = static_cast<SkPMColor*>( 5122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) source_bitmap.getAddr32(0, y)); 5132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int x = 0; x < source_bitmap.width(); ++x) { 5142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]); 5152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float r = SkColorGetR(c); 5162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float g = SkColorGetG(c); 5172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float b = SkColorGetB(c); 5182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float gray_level = tr * r + tg * g + tb * b; 5192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) max_val = std::max(max_val, gray_level); 5202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) min_val = std::min(min_val, gray_level); 5212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Adjust the transform so that the result is scaling. 5252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float scale = 0.0; 5262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) t0 = -min_val; 5272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (max_val > min_val) 5282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) scale = 255.0 / (max_val - min_val); 5292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) t0 *= scale; 5302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tr *= scale; 5312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tg *= scale; 5322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tb *= scale; 5332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int y = 0; y < source_bitmap.height(); ++y) { 5362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const SkPMColor* source_color_row = static_cast<SkPMColor*>( 5372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) source_bitmap.getAddr32(0, y)); 5382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) uint8_t* target_color_row = target_bitmap->getAddr8(0, y); 5392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (int x = 0; x < source_bitmap.width(); ++x) { 5402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]); 5412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float r = SkColorGetR(c); 5422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float g = SkColorGetG(c); 5432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float b = SkColorGetB(c); 5442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) float gl = t0 + tr * r + tg * g + tb * b; 5462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (gl < 0) 5472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gl = 0; 5482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (gl > 0xFF) 5492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gl = 0xFF; 5502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) target_color_row[x] = static_cast<uint8_t>(gl); 5512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 5552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool ComputePrincipalComponentImage(const SkBitmap& source_bitmap, 5582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkBitmap* target_bitmap) { 5592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!target_bitmap) { 5602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NOTREACHED(); 5612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 5622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap); 5652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros(); 5662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors); 5672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) gfx::Vector3dF principal = eigenvectors.get_column(0); 5682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF()) 5692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; // This may happen for some edge cases. 5702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return ApplyColorReduction(source_bitmap, principal, true, target_bitmap); 5712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // color_utils 574