OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "ui/gfx/color_analysis.h" | 5 #include "ui/gfx/color_analysis.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <limits> | 8 #include <limits> |
9 #include <vector> | 9 #include <vector> |
10 | 10 |
(...skipping 22 matching lines...) Expand all Loading... |
33 // the KMean algorithm. While this class does not contain all of the points | 33 // the KMean algorithm. While this class does not contain all of the points |
34 // that exist in the cluster, it keeps track of the aggregate sum so it can | 34 // that exist in the cluster, it keeps track of the aggregate sum so it can |
35 // compute the new center appropriately. | 35 // compute the new center appropriately. |
36 class KMeanCluster { | 36 class KMeanCluster { |
37 public: | 37 public: |
38 KMeanCluster() { | 38 KMeanCluster() { |
39 Reset(); | 39 Reset(); |
40 } | 40 } |
41 | 41 |
42 void Reset() { | 42 void Reset() { |
43 centroid[0] = centroid[1] = centroid[2] = 0; | 43 centroid_[0] = centroid_[1] = centroid_[2] = 0; |
44 aggregate[0] = aggregate[1] = aggregate[2] = 0; | 44 aggregate_[0] = aggregate_[1] = aggregate_[2] = 0; |
45 counter = 0; | 45 counter_ = 0; |
46 weight = 0; | 46 weight_ = 0; |
47 } | 47 } |
48 | 48 |
49 inline void SetCentroid(uint8_t r, uint8_t g, uint8_t b) { | 49 inline void SetCentroid(uint8_t r, uint8_t g, uint8_t b) { |
50 centroid[0] = r; | 50 centroid_[0] = r; |
51 centroid[1] = g; | 51 centroid_[1] = g; |
52 centroid[2] = b; | 52 centroid_[2] = b; |
53 } | 53 } |
54 | 54 |
55 inline void GetCentroid(uint8_t* r, uint8_t* g, uint8_t* b) { | 55 inline void GetCentroid(uint8_t* r, uint8_t* g, uint8_t* b) { |
56 *r = centroid[0]; | 56 *r = centroid_[0]; |
57 *g = centroid[1]; | 57 *g = centroid_[1]; |
58 *b = centroid[2]; | 58 *b = centroid_[2]; |
59 } | 59 } |
60 | 60 |
61 inline bool IsAtCentroid(uint8_t r, uint8_t g, uint8_t b) { | 61 inline bool IsAtCentroid(uint8_t r, uint8_t g, uint8_t b) { |
62 return r == centroid[0] && g == centroid[1] && b == centroid[2]; | 62 return r == centroid_[0] && g == centroid_[1] && b == centroid_[2]; |
63 } | 63 } |
64 | 64 |
65 // Recomputes the centroid of the cluster based on the aggregate data. The | 65 // Recomputes the centroid of the cluster based on the aggregate data. The |
66 // number of points used to calculate this center is stored for weighting | 66 // number of points used to calculate this center is stored for weighting |
67 // purposes. The aggregate and counter are then cleared to be ready for the | 67 // purposes. The aggregate and counter are then cleared to be ready for the |
68 // next iteration. | 68 // next iteration. |
69 inline void RecomputeCentroid() { | 69 inline void RecomputeCentroid() { |
70 if (counter > 0) { | 70 if (counter_ > 0) { |
71 centroid[0] = aggregate[0] / counter; | 71 centroid_[0] = static_cast<uint8_t>(aggregate_[0] / counter_); |
72 centroid[1] = aggregate[1] / counter; | 72 centroid_[1] = static_cast<uint8_t>(aggregate_[1] / counter_); |
73 centroid[2] = aggregate[2] / counter; | 73 centroid_[2] = static_cast<uint8_t>(aggregate_[2] / counter_); |
74 | 74 |
75 aggregate[0] = aggregate[1] = aggregate[2] = 0; | 75 aggregate_[0] = aggregate_[1] = aggregate_[2] = 0; |
76 weight = counter; | 76 weight_ = counter_; |
77 counter = 0; | 77 counter_ = 0; |
78 } | 78 } |
79 } | 79 } |
80 | 80 |
81 inline void AddPoint(uint8_t r, uint8_t g, uint8_t b) { | 81 inline void AddPoint(uint8_t r, uint8_t g, uint8_t b) { |
82 aggregate[0] += r; | 82 aggregate_[0] += r; |
83 aggregate[1] += g; | 83 aggregate_[1] += g; |
84 aggregate[2] += b; | 84 aggregate_[2] += b; |
85 ++counter; | 85 ++counter_; |
86 } | 86 } |
87 | 87 |
88 // Just returns the distance^2. Since we are comparing relative distances | 88 // Just returns the distance^2. Since we are comparing relative distances |
89 // there is no need to perform the expensive sqrt() operation. | 89 // there is no need to perform the expensive sqrt() operation. |
90 inline uint32_t GetDistanceSqr(uint8_t r, uint8_t g, uint8_t b) { | 90 inline uint32_t GetDistanceSqr(uint8_t r, uint8_t g, uint8_t b) { |
91 return (r - centroid[0]) * (r - centroid[0]) + | 91 return (r - centroid_[0]) * (r - centroid_[0]) + |
92 (g - centroid[1]) * (g - centroid[1]) + | 92 (g - centroid_[1]) * (g - centroid_[1]) + |
93 (b - centroid[2]) * (b - centroid[2]); | 93 (b - centroid_[2]) * (b - centroid_[2]); |
94 } | 94 } |
95 | 95 |
96 // In order to determine if we have hit convergence or not we need to see | 96 // In order to determine if we have hit convergence or not we need to see |
97 // if the centroid of the cluster has moved. This determines whether or | 97 // if the centroid of the cluster has moved. This determines whether or |
98 // not the centroid is the same as the aggregate sum of points that will be | 98 // not the centroid is the same as the aggregate sum of points that will be |
99 // used to generate the next centroid. | 99 // used to generate the next centroid. |
100 inline bool CompareCentroidWithAggregate() { | 100 inline bool CompareCentroidWithAggregate() { |
101 if (counter == 0) | 101 if (counter_ == 0) |
102 return false; | 102 return false; |
103 | 103 |
104 return aggregate[0] / counter == centroid[0] && | 104 return aggregate_[0] / counter_ == centroid_[0] && |
105 aggregate[1] / counter == centroid[1] && | 105 aggregate_[1] / counter_ == centroid_[1] && |
106 aggregate[2] / counter == centroid[2]; | 106 aggregate_[2] / counter_ == centroid_[2]; |
107 } | 107 } |
108 | 108 |
109 // Returns the previous counter, which is used to determine the weight | 109 // Returns the previous counter, which is used to determine the weight |
110 // of the cluster for sorting. | 110 // of the cluster for sorting. |
111 inline uint32_t GetWeight() const { | 111 inline uint32_t GetWeight() const { |
112 return weight; | 112 return weight_; |
113 } | 113 } |
114 | 114 |
115 static bool SortKMeanClusterByWeight(const KMeanCluster& a, | 115 static bool SortKMeanClusterByWeight(const KMeanCluster& a, |
116 const KMeanCluster& b) { | 116 const KMeanCluster& b) { |
117 return a.GetWeight() > b.GetWeight(); | 117 return a.GetWeight() > b.GetWeight(); |
118 } | 118 } |
119 | 119 |
120 private: | 120 private: |
121 uint8_t centroid[3]; | 121 uint8_t centroid_[3]; |
122 | 122 |
123 // Holds the sum of all the points that make up this cluster. Used to | 123 // Holds the sum of all the points that make up this cluster. Used to |
124 // generate the next centroid as well as to check for convergence. | 124 // generate the next centroid as well as to check for convergence. |
125 uint32_t aggregate[3]; | 125 uint32_t aggregate_[3]; |
126 uint32_t counter; | 126 uint32_t counter_; |
127 | 127 |
128 // The weight of the cluster, determined by how many points were used | 128 // The weight of the cluster, determined by how many points were used |
129 // to generate the previous centroid. | 129 // to generate the previous centroid. |
130 uint32_t weight; | 130 uint32_t weight_; |
131 }; | 131 }; |
132 | 132 |
133 // Un-premultiplies each pixel in |bitmap| into an output |buffer|. | 133 // Un-premultiplies each pixel in |bitmap| into an output |buffer|. |
134 void UnPreMultiply(const SkBitmap& bitmap, uint32_t* buffer, int buffer_size) { | 134 void UnPreMultiply(const SkBitmap& bitmap, uint32_t* buffer, int buffer_size) { |
135 SkAutoLockPixels auto_lock(bitmap); | 135 SkAutoLockPixels auto_lock(bitmap); |
136 uint32_t* in = static_cast<uint32_t*>(bitmap.getPixels()); | 136 uint32_t* in = static_cast<uint32_t*>(bitmap.getPixels()); |
137 uint32_t* out = buffer; | 137 uint32_t* out = buffer; |
138 int pixel_count = std::min(bitmap.width() * bitmap.height(), buffer_size); | 138 int pixel_count = std::min(bitmap.width() * bitmap.height(), buffer_size); |
139 for (int i = 0; i < pixel_count; ++i) { | 139 for (int i = 0; i < pixel_count; ++i) { |
140 int alpha = SkGetPackedA32(*in); | 140 int alpha = SkGetPackedA32(*in); |
(...skipping 320 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
461 gb_sum += g * b; | 461 gb_sum += g * b; |
462 } | 462 } |
463 } | 463 } |
464 | 464 |
465 // Covariance (not normalized) is E(X*X.t) - m * m.t and this is how it | 465 // Covariance (not normalized) is E(X*X.t) - m * m.t and this is how it |
466 // is calculated below. | 466 // is calculated below. |
467 // Each row below represents a row of the matrix describing (co)variances | 467 // Each row below represents a row of the matrix describing (co)variances |
468 // of R, G and B channels with (R, G, B) | 468 // of R, G and B channels with (R, G, B) |
469 int pixel_n = bitmap.width() * bitmap.height(); | 469 int pixel_n = bitmap.width() * bitmap.height(); |
470 covariance.set( | 470 covariance.set( |
471 (static_cast<double>(rr_sum) / pixel_n - | 471 static_cast<float>( |
472 static_cast<double>(r_sum * r_sum) / pixel_n / pixel_n), | 472 static_cast<double>(rr_sum) / pixel_n - |
473 (static_cast<double>(rg_sum) / pixel_n - | 473 static_cast<double>(r_sum * r_sum) / pixel_n / pixel_n), |
474 static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n), | 474 static_cast<float>( |
475 (static_cast<double>(rb_sum) / pixel_n - | 475 static_cast<double>(rg_sum) / pixel_n - |
476 static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n), | 476 static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n), |
477 (static_cast<double>(rg_sum) / pixel_n - | 477 static_cast<float>( |
478 static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n), | 478 static_cast<double>(rb_sum) / pixel_n - |
479 (static_cast<double>(gg_sum) / pixel_n - | 479 static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n), |
480 static_cast<double>(g_sum * g_sum) / pixel_n / pixel_n), | 480 static_cast<float>( |
481 (static_cast<double>(gb_sum) / pixel_n - | 481 static_cast<double>(rg_sum) / pixel_n - |
482 static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n), | 482 static_cast<double>(r_sum * g_sum) / pixel_n / pixel_n), |
483 (static_cast<double>(rb_sum) / pixel_n - | 483 static_cast<float>( |
484 static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n), | 484 static_cast<double>(gg_sum) / pixel_n - |
485 (static_cast<double>(gb_sum) / pixel_n - | 485 static_cast<double>(g_sum * g_sum) / pixel_n / pixel_n), |
486 static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n), | 486 static_cast<float>( |
487 (static_cast<double>(bb_sum) / pixel_n - | 487 static_cast<double>(gb_sum) / pixel_n - |
488 static_cast<double>(b_sum * b_sum) / pixel_n / pixel_n)); | 488 static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n), |
| 489 static_cast<float>( |
| 490 static_cast<double>(rb_sum) / pixel_n - |
| 491 static_cast<double>(r_sum * b_sum) / pixel_n / pixel_n), |
| 492 static_cast<float>( |
| 493 static_cast<double>(gb_sum) / pixel_n - |
| 494 static_cast<double>(g_sum * b_sum) / pixel_n / pixel_n), |
| 495 static_cast<float>( |
| 496 static_cast<double>(bb_sum) / pixel_n - |
| 497 static_cast<double>(b_sum * b_sum) / pixel_n / pixel_n)); |
489 return covariance; | 498 return covariance; |
490 } | 499 } |
491 | 500 |
492 bool ApplyColorReduction(const SkBitmap& source_bitmap, | 501 bool ApplyColorReduction(const SkBitmap& source_bitmap, |
493 const gfx::Vector3dF& color_transform, | 502 const gfx::Vector3dF& color_transform, |
494 bool fit_to_range, | 503 bool fit_to_range, |
495 SkBitmap* target_bitmap) { | 504 SkBitmap* target_bitmap) { |
496 DCHECK(target_bitmap); | 505 DCHECK(target_bitmap); |
497 SkAutoLockPixels source_lock(source_bitmap); | 506 SkAutoLockPixels source_lock(source_bitmap); |
498 SkAutoLockPixels target_lock(*target_bitmap); | 507 SkAutoLockPixels target_lock(*target_bitmap); |
(...skipping 23 matching lines...) Expand all Loading... |
522 const SkPMColor* source_color_row = static_cast<SkPMColor*>( | 531 const SkPMColor* source_color_row = static_cast<SkPMColor*>( |
523 source_bitmap.getAddr32(0, y)); | 532 source_bitmap.getAddr32(0, y)); |
524 for (int x = 0; x < source_bitmap.width(); ++x) { | 533 for (int x = 0; x < source_bitmap.width(); ++x) { |
525 SkColor c; | 534 SkColor c; |
526 int alpha = SkGetPackedA32(source_color_row[x]); | 535 int alpha = SkGetPackedA32(source_color_row[x]); |
527 if (alpha != 0 && alpha != 255) | 536 if (alpha != 0 && alpha != 255) |
528 c = SkUnPreMultiply::PMColorToColor(source_color_row[x]); | 537 c = SkUnPreMultiply::PMColorToColor(source_color_row[x]); |
529 else | 538 else |
530 c = source_color_row[x]; | 539 c = source_color_row[x]; |
531 | 540 |
532 float r = SkColorGetR(c); | 541 uint8_t r = SkColorGetR(c); |
533 float g = SkColorGetG(c); | 542 uint8_t g = SkColorGetG(c); |
534 float b = SkColorGetB(c); | 543 uint8_t b = SkColorGetB(c); |
535 float gray_level = tr * r + tg * g + tb * b; | 544 float gray_level = tr * r + tg * g + tb * b; |
536 max_val = std::max(max_val, gray_level); | 545 max_val = std::max(max_val, gray_level); |
537 min_val = std::min(min_val, gray_level); | 546 min_val = std::min(min_val, gray_level); |
538 } | 547 } |
539 } | 548 } |
540 | 549 |
541 // Adjust the transform so that the result is scaling. | 550 // Adjust the transform so that the result is scaling. |
542 float scale = 0.0; | 551 float scale = 0.0; |
543 t0 = -min_val; | 552 t0 = -min_val; |
544 if (max_val > min_val) | 553 if (max_val > min_val) |
545 scale = 255.0 / (max_val - min_val); | 554 scale = 255.0f / (max_val - min_val); |
546 t0 *= scale; | 555 t0 *= scale; |
547 tr *= scale; | 556 tr *= scale; |
548 tg *= scale; | 557 tg *= scale; |
549 tb *= scale; | 558 tb *= scale; |
550 } | 559 } |
551 | 560 |
552 for (int y = 0; y < source_bitmap.height(); ++y) { | 561 for (int y = 0; y < source_bitmap.height(); ++y) { |
553 const SkPMColor* source_color_row = static_cast<SkPMColor*>( | 562 const SkPMColor* source_color_row = static_cast<SkPMColor*>( |
554 source_bitmap.getAddr32(0, y)); | 563 source_bitmap.getAddr32(0, y)); |
555 uint8_t* target_color_row = target_bitmap->getAddr8(0, y); | 564 uint8_t* target_color_row = target_bitmap->getAddr8(0, y); |
556 for (int x = 0; x < source_bitmap.width(); ++x) { | 565 for (int x = 0; x < source_bitmap.width(); ++x) { |
557 SkColor c; | 566 SkColor c; |
558 int alpha = SkGetPackedA32(source_color_row[x]); | 567 int alpha = SkGetPackedA32(source_color_row[x]); |
559 if (alpha != 0 && alpha != 255) | 568 if (alpha != 0 && alpha != 255) |
560 c = SkUnPreMultiply::PMColorToColor(source_color_row[x]); | 569 c = SkUnPreMultiply::PMColorToColor(source_color_row[x]); |
561 else | 570 else |
562 c = source_color_row[x]; | 571 c = source_color_row[x]; |
563 | 572 |
564 float r = SkColorGetR(c); | 573 uint8_t r = SkColorGetR(c); |
565 float g = SkColorGetG(c); | 574 uint8_t g = SkColorGetG(c); |
566 float b = SkColorGetB(c); | 575 uint8_t b = SkColorGetB(c); |
567 | 576 |
568 float gl = t0 + tr * r + tg * g + tb * b; | 577 float gl = t0 + tr * r + tg * g + tb * b; |
569 if (gl < 0) | 578 if (gl < 0) |
570 gl = 0; | 579 gl = 0; |
571 if (gl > 0xFF) | 580 if (gl > 0xFF) |
572 gl = 0xFF; | 581 gl = 0xFF; |
573 target_color_row[x] = static_cast<uint8_t>(gl); | 582 target_color_row[x] = static_cast<uint8_t>(gl); |
574 } | 583 } |
575 } | 584 } |
576 | 585 |
(...skipping 10 matching lines...) Expand all Loading... |
587 gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap); | 596 gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap); |
588 gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros(); | 597 gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros(); |
589 gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors); | 598 gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors); |
590 gfx::Vector3dF principal = eigenvectors.get_column(0); | 599 gfx::Vector3dF principal = eigenvectors.get_column(0); |
591 if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF()) | 600 if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF()) |
592 return false; // This may happen for some edge cases. | 601 return false; // This may happen for some edge cases. |
593 return ApplyColorReduction(source_bitmap, principal, true, target_bitmap); | 602 return ApplyColorReduction(source_bitmap, principal, true, target_bitmap); |
594 } | 603 } |
595 | 604 |
596 } // color_utils | 605 } // color_utils |
OLD | NEW |