Implementation of principal-component color reduction.

R=asvitkine@chromium.org,reed@chromium.org
BUG=155269


Review URL: https://chromiumcodereview.appspot.com/12335009

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@184174 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 297 insertions, 0 deletions

diff --git a/ui/gfx/color_analysis.cc b/ui/gfx/color_analysis.cc
index 8878519..f8987cf 100644
--- a/ui/gfx/color_analysis.cc
+++ b/ui/gfx/color_analysis.cc
@@ -5,6 +5,7 @@
 #include "ui/gfx/color_analysis.h"
 
 #include <algorithm>
+#include <limits>
 #include <vector>
 
 #include "base/logging.h"
@@ -467,4 +468,96 @@ gfx::Matrix3F ComputeColorCovariance(const SkBitmap& bitmap) {
   return covariance;
 }
 
+bool ApplyColorReduction(const SkBitmap& source_bitmap,
+                         const gfx::Vector3dF& color_transform,
+                         bool fit_to_range,
+                         SkBitmap* target_bitmap) {
+  DCHECK(target_bitmap);
+  SkAutoLockPixels source_lock(source_bitmap);
+  SkAutoLockPixels target_lock(*target_bitmap);
+
+  DCHECK(source_bitmap.getPixels());
+  DCHECK(target_bitmap->getPixels());
+  DCHECK_EQ(SkBitmap::kARGB_8888_Config, source_bitmap.config());
+  DCHECK_EQ(SkBitmap::kA8_Config, target_bitmap->config());
+  DCHECK_EQ(source_bitmap.height(), target_bitmap->height());
+  DCHECK_EQ(source_bitmap.width(), target_bitmap->width());
+  DCHECK(!source_bitmap.empty());
+
+  // Elements of color_transform are explicitly off-loaded to local values for
+  // efficiency reasons. Note that in practice images may correspond to entire
+  // tab captures.
+  float t0 = 0.0;
+  float tr = color_transform.x();
+  float tg = color_transform.y();
+  float tb = color_transform.z();
+
+  if (fit_to_range) {
+    // We will figure out min/max in a preprocessing step and adjust
+    // actual_transform as required.
+    float max_val = std::numeric_limits<float>::min();
+    float min_val = std::numeric_limits<float>::max();
+    for (int y = 0; y < source_bitmap.height(); ++y) {
+      const SkPMColor* source_color_row = static_cast<SkPMColor*>(
+          source_bitmap.getAddr32(0, y));
+      for (int x = 0; x < source_bitmap.width(); ++x) {
+        SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
+        float r = SkColorGetR(c);
+        float g = SkColorGetG(c);
+        float b = SkColorGetB(c);
+        float gray_level = tr * r + tg * g + tb * b;
+        max_val = std::max(max_val, gray_level);
+        min_val = std::min(min_val, gray_level);
+      }
+    }
+
+    // Adjust the transform so that the result is scaling.
+    float scale = 0.0;
+    t0 = -min_val;
+    if (max_val > min_val)
+      scale = 255.0 / (max_val - min_val);
+    t0 *= scale;
+    tr *= scale;
+    tg *= scale;
+    tb *= scale;
+  }
+
+  for (int y = 0; y < source_bitmap.height(); ++y) {
+    const SkPMColor* source_color_row = static_cast<SkPMColor*>(
+        source_bitmap.getAddr32(0, y));
+    uint8_t* target_color_row = target_bitmap->getAddr8(0, y);
+    for (int x = 0; x < source_bitmap.width(); ++x) {
+      SkColor c = SkUnPreMultiply::PMColorToColor(source_color_row[x]);
+      float r = SkColorGetR(c);
+      float g = SkColorGetG(c);
+      float b = SkColorGetB(c);
+
+      float gl = t0 + tr * r + tg * g + tb * b;
+      if (gl < 0)
+        gl = 0;
+      if (gl > 0xFF)
+        gl = 0xFF;
+      target_color_row[x] = static_cast<uint8_t>(gl);
+    }
+  }
+
+  return true;
+}
+
+bool ComputePrincipalComponentImage(const SkBitmap& source_bitmap,
+                                    SkBitmap* target_bitmap) {
+  if (!target_bitmap) {
+    NOTREACHED();
+    return false;
+  }
+
+  gfx::Matrix3F covariance = ComputeColorCovariance(source_bitmap);
+  gfx::Matrix3F eigenvectors = gfx::Matrix3F::Zeros();
+  gfx::Vector3dF eigenvals = covariance.SolveEigenproblem(&eigenvectors);
+  gfx::Vector3dF principal = eigenvectors.get_column(0);
+  if (eigenvals == gfx::Vector3dF() || principal == gfx::Vector3dF())
+    return false;  // This may happen for some edge cases.
+  return ApplyColorReduction(source_bitmap, principal, true, target_bitmap);
+}
+
 }  // color_utils
diff --git a/ui/gfx/color_analysis.h b/ui/gfx/color_analysis.h
index 0d208f8..1d0b1a5 100644
--- a/ui/gfx/color_analysis.h
+++ b/ui/gfx/color_analysis.h
@@ -102,6 +102,26 @@ UI_EXPORT SkColor CalculateKMeanColorOfBitmap(const SkBitmap& bitmap);
 // Compute color covariance matrix for the input bitmap.
 UI_EXPORT gfx::Matrix3F ComputeColorCovariance(const SkBitmap& bitmap);
 
+// Apply a color reduction transform defined by |color_transform| vector to
+// |source_bitmap|. The result is put into |target_bitmap|, which is expected
+// to be initialized to the required size and type (SkBitmap::kA8_Config).
+// If |fit_to_range|, result is transfored linearly to fit 0-0xFF range.
+// Otherwise, data is clipped.
+// Returns true if the target has been computed.
+UI_EXPORT bool ApplyColorReduction(const SkBitmap& source_bitmap,
+                                   const gfx::Vector3dF& color_transform,
+                                   bool fit_to_range,
+                                   SkBitmap* target_bitmap);
+
+// Compute a monochrome image representing the principal color component of
+// the |source_bitmap|. The result is stored in |target_bitmap|, which must be
+// initialized to the required size and type (SkBitmap::kA8_Config).
+// Returns true if the conversion succeeded. Note that there might be legitimate
+// reasons for the process to fail even if all input was correct. This is a
+// condition the caller must be able to handle.
+UI_EXPORT bool ComputePrincipalComponentImage(const SkBitmap& source_bitmap,
+                                              SkBitmap* target_bitmap);
+
 }  // namespace color_utils
 
 #endif  // UI_GFX_COLOR_ANALYSIS_H_
diff --git a/ui/gfx/color_analysis_unittest.cc b/ui/gfx/color_analysis_unittest.cc
index d895369..c76681c 100644
--- a/ui/gfx/color_analysis_unittest.cc
+++ b/ui/gfx/color_analysis_unittest.cc
@@ -135,6 +135,27 @@ bool ChannelApproximatelyEqual(int expected, uint8_t channel) {
   return (abs(expected - static_cast<int>(channel)) <= 1);
 }
 
+// Compute minimal and maximal graylevel (or alphalevel) of the input |bitmap|.
+// |bitmap| has to be allocated and configured to kA8_Config.
+void Calculate8bitBitmapMinMax(const SkBitmap& bitmap,
+                               uint8_t* min_gl,
+                               uint8_t* max_gl) {
+  SkAutoLockPixels bitmap_lock(bitmap);
+  DCHECK(bitmap.getPixels());
+  DCHECK(bitmap.config() == SkBitmap::kA8_Config);
+  DCHECK(min_gl);
+  DCHECK(max_gl);
+  *min_gl = std::numeric_limits<uint8_t>::max();
+  *max_gl = std::numeric_limits<uint8_t>::min();
+  for (int y = 0; y < bitmap.height(); ++y) {
+    uint8_t* current_color = bitmap.getAddr8(0, y);
+    for (int x = 0; x < bitmap.width(); ++x, ++current_color) {
+      *min_gl = std::min(*min_gl, *current_color);
+      *max_gl = std::max(*max_gl, *current_color);
+    }
+  }
+}
+
 } // namespace
 
 class ColorAnalysisTest : public testing::Test {
@@ -293,3 +314,166 @@ TEST_F(ColorAnalysisTest, ComputeColorCovarianceWithCanvas) {
                           -1600, 400, 2400);
   EXPECT_EQ(expected_covariance, covariance);
 }
+
+TEST_F(ColorAnalysisTest, ApplyColorReductionSingleColor) {
+  // The test runs color reduction on a single-colot image, where results are
+  // bound to be uninteresting. This is an important edge case, though.
+  SkBitmap source, result;
+  source.setConfig(SkBitmap::kARGB_8888_Config, 300, 200);
+  result.setConfig(SkBitmap::kA8_Config, 300, 200);
+
+  source.allocPixels();
+  result.allocPixels();
+  source.eraseRGB(50, 150, 200);
+
+  gfx::Vector3dF transform(1.0f, .5f, 0.1f);
+  // This transform, if not scaled, should result in GL=145.
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, false, &result));
+
+  uint8_t min_gl = 0;
+  uint8_t max_gl = 0;
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+  EXPECT_EQ(145, min_gl);
+  EXPECT_EQ(145, max_gl);
+
+  // Now scan requesting rescale. Expect all 0.
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, true, &result));
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+  EXPECT_EQ(0, min_gl);
+  EXPECT_EQ(0, max_gl);
+
+  // Test cliping to upper limit.
+  transform.set_z(1.1f);
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, false, &result));
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+  EXPECT_EQ(0xFF, min_gl);
+  EXPECT_EQ(0xFF, max_gl);
+
+  // Test cliping to upper limit.
+  transform.Scale(-1.0f);
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, false, &result));
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+  EXPECT_EQ(0x0, min_gl);
+  EXPECT_EQ(0x0, max_gl);
+}
+
+TEST_F(ColorAnalysisTest, ApplyColorReductionBlackAndWhite) {
+  // Check with images with multiple colors. This is really different only when
+  // the result is scaled.
+  gfx::Canvas canvas(gfx::Size(300, 200), ui::SCALE_FACTOR_100P, true);
+
+  // The image consists of vertical non-overlapping stripes 150 pixels wide.
+  canvas.FillRect(gfx::Rect(0, 0, 150, 200), SkColorSetRGB(0, 0, 0));
+  canvas.FillRect(gfx::Rect(150, 0, 150, 200), SkColorSetRGB(255, 255, 255));
+  SkBitmap source =
+      skia::GetTopDevice(*canvas.sk_canvas())->accessBitmap(false);
+  SkBitmap result;
+  result.setConfig(SkBitmap::kA8_Config, 300, 200);
+  result.allocPixels();
+
+  gfx::Vector3dF transform(1.0f, 0.5f, 0.1f);
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, true, &result));
+  uint8_t min_gl = 0;
+  uint8_t max_gl = 0;
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+
+  EXPECT_EQ(0, min_gl);
+  EXPECT_EQ(255, max_gl);
+  EXPECT_EQ(min_gl, SkColorGetA(result.getColor(0, 0)));
+  EXPECT_EQ(max_gl, SkColorGetA(result.getColor(299, 199)));
+
+  // Reverse test.
+  transform.Scale(-1.0f);
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, true, &result));
+  min_gl = 0;
+  max_gl = 0;
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+
+  EXPECT_EQ(0, min_gl);
+  EXPECT_EQ(255, max_gl);
+  EXPECT_EQ(max_gl, SkColorGetA(result.getColor(0, 0)));
+  EXPECT_EQ(min_gl, SkColorGetA(result.getColor(299, 199)));
+}
+
+TEST_F(ColorAnalysisTest, ApplyColorReductionMultiColor) {
+  // Check with images with multiple colors. This is really different only when
+  // the result is scaled.
+  gfx::Canvas canvas(gfx::Size(300, 200), ui::SCALE_FACTOR_100P, true);
+
+  // The image consists of vertical non-overlapping stripes 100 pixels wide.
+  canvas.FillRect(gfx::Rect(0, 0, 100, 200), SkColorSetRGB(100, 0, 0));
+  canvas.FillRect(gfx::Rect(100, 0, 100, 200), SkColorSetRGB(0, 255, 0));
+  canvas.FillRect(gfx::Rect(200, 0, 100, 200), SkColorSetRGB(0, 0, 128));
+  SkBitmap source =
+      skia::GetTopDevice(*canvas.sk_canvas())->accessBitmap(false);
+  SkBitmap result;
+  result.setConfig(SkBitmap::kA8_Config, 300, 200);
+  result.allocPixels();
+
+  gfx::Vector3dF transform(1.0f, 0.5f, 0.1f);
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, false, &result));
+  uint8_t min_gl = 0;
+  uint8_t max_gl = 0;
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+  EXPECT_EQ(12, min_gl);
+  EXPECT_EQ(127, max_gl);
+  EXPECT_EQ(min_gl, SkColorGetA(result.getColor(299, 199)));
+  EXPECT_EQ(max_gl, SkColorGetA(result.getColor(150, 0)));
+  EXPECT_EQ(100U, SkColorGetA(result.getColor(0, 0)));
+
+  EXPECT_TRUE(color_utils::ApplyColorReduction(
+      source, transform, true, &result));
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+  EXPECT_EQ(0, min_gl);
+  EXPECT_EQ(255, max_gl);
+  EXPECT_EQ(min_gl, SkColorGetA(result.getColor(299, 199)));
+  EXPECT_EQ(max_gl, SkColorGetA(result.getColor(150, 0)));
+  EXPECT_EQ(193U, SkColorGetA(result.getColor(0, 0)));
+}
+
+TEST_F(ColorAnalysisTest, ComputePrincipalComponentImageNotComputable) {
+  SkBitmap source, result;
+  source.setConfig(SkBitmap::kARGB_8888_Config, 300, 200);
+  result.setConfig(SkBitmap::kA8_Config, 300, 200);
+
+  source.allocPixels();
+  result.allocPixels();
+  source.eraseRGB(50, 150, 200);
+
+  // This computation should fail since all colors always vary together.
+  EXPECT_FALSE(color_utils::ComputePrincipalComponentImage(source, &result));
+}
+
+TEST_F(ColorAnalysisTest, ComputePrincipalComponentImage) {
+  gfx::Canvas canvas(gfx::Size(300, 200), ui::SCALE_FACTOR_100P, true);
+
+  // The image consists of vertical non-overlapping stripes 100 pixels wide.
+  canvas.FillRect(gfx::Rect(0, 0, 100, 200), SkColorSetRGB(10, 10, 10));
+  canvas.FillRect(gfx::Rect(100, 0, 100, 200), SkColorSetRGB(100, 100, 100));
+  canvas.FillRect(gfx::Rect(200, 0, 100, 200), SkColorSetRGB(255, 255, 255));
+  SkBitmap source =
+      skia::GetTopDevice(*canvas.sk_canvas())->accessBitmap(false);
+  SkBitmap result;
+  result.setConfig(SkBitmap::kA8_Config, 300, 200);
+  result.allocPixels();
+
+  // This computation should fail since all colors always vary together.
+  EXPECT_TRUE(color_utils::ComputePrincipalComponentImage(source, &result));
+
+  uint8_t min_gl = 0;
+  uint8_t max_gl = 0;
+  Calculate8bitBitmapMinMax(result, &min_gl, &max_gl);
+
+  EXPECT_EQ(0, min_gl);
+  EXPECT_EQ(255, max_gl);
+  EXPECT_EQ(min_gl, SkColorGetA(result.getColor(0, 0)));
+  EXPECT_EQ(max_gl, SkColorGetA(result.getColor(299, 199)));
+  EXPECT_EQ(93U, SkColorGetA(result.getColor(150, 0)));
+}