Implementation of principal-component color reduction.

ui/gfx/color_utils.cc

Index: ui/gfx/color_utils.cc
diff --git a/ui/gfx/color_utils.cc b/ui/gfx/color_utils.cc
index 07980d84d8c2cc37d832e3efe3e303a9afd10362..42e9fea65efad0634b8781a2655c83fa72dc71da 100644
--- a/ui/gfx/color_utils.cc
+++ b/ui/gfx/color_utils.cc
@@ -10,6 +10,7 @@
 #endif
 
 #include <algorithm>
+#include <limits>
 
 #include "base/basictypes.h"
 #include "base/logging.h"
@@ -18,6 +19,10 @@
 #include "skia/ext/skia_utils_win.h"
 #endif
 #include "third_party/skia/include/core/SkBitmap.h"
+#include "third_party/skia/include/core/SkUnPreMultiply.h"
+#include "ui/gfx/color_analysis.h"
+#include "ui/gfx/matrix3_f.h"
+#include "ui/gfx/vector3d_f.h"
 
 namespace color_utils {
 
@@ -261,4 +266,100 @@ SkColor GetSysSkColor(int which) {
 #endif
 }
 
+bool ApplyColorReduction(const SkBitmap& source_bitmap,
+                         const gfx::Vector3dF& color_transform,
+                         bool scale_result,
+                         SkBitmap* target_bitmap) {
+  if (!target_bitmap) {

[Alexei Svitkine (slow), 2013/02/21 19:49:33]

Do you really need all these early returns? Can you make it the caller's
responsibility that they pass a non-NULL bitmap with pixels available, etc. and
just DCHECK() on that?

[motek., 2013/02/21 22:45:03]

I think I borrowed this idiom from somewhere. Likely it is not needed. Done as
suggested.

+    NOTREACHED();
+    return false;
+  }
+
+  SkAutoLockPixels source_lock(source_bitmap);
+  SkAutoLockPixels target_lock(*target_bitmap);
+
+  if (!source_bitmap.getPixels())
+    return false;
+
+  if (!target_bitmap->getPixels()) {
+    NOTREACHED();
+    return false;
+  }
+
+  DCHECK(source_bitmap.config() == SkBitmap::kARGB_8888_Config);
+  DCHECK(target_bitmap->config() == SkBitmap::kA8_Config);
+  DCHECK_EQ(source_bitmap.height(), target_bitmap->height());
+  DCHECK_EQ(source_bitmap.width(), target_bitmap->width());
+
+  int height = std::min(source_bitmap.height(), target_bitmap->height());
+  int width = std::min(source_bitmap.width(), target_bitmap->width());
+  DCHECK(height > 0 && width > 0);
+
+  float a0 = 0.0;
+  float scale = 1.0;
+  if (scale_result) {

[Alexei Svitkine (slow), 2013/02/21 19:49:33]

I think it would be cleaner to do the scaling in a separate function.

Here's my reasoning:

1. It would make this function cleaner and easier to read.
2. Sure, you'd need an extra iteration over the pixels, but you wouldn't need to
do the gfx::DotProduct() twice for each pixel, which you currently do.
3. In the case where scaling is not needed, you avoid a float multiplication for
each pixel.

Also, I'm not sure "scaling" is the best term for this, since for bitmaps it
usually means resizing the bitmap. Perhaps "normalize"?

[motek., 2013/02/21 22:45:03]

I don't really follow. To know how to scale I need to know the range. Thus this
extra pass (with dot-products) is needed. If I wanted to do it once, I'd need
some form of intermediate storage (because the target is 8-bit). Data loss would
be a problem. 

[Alexei Svitkine (slow), 2013/02/22 02:24:06]

Ah, you're right, I didn't realise we couldn't re-use the same bitmap for the
intermediate storage - without losing precision. Fair enough.

+    // 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 < height; ++y) {
+      SkPMColor* current_color = static_cast<uint32_t*>(

[Alexei Svitkine (slow), 2013/02/21 19:49:33]

Should this be a static_cast<SkPMColor*>?

[motek., 2013/02/21 22:45:03]

Seems you are right. Done.

+          source_bitmap.getAddr32(0, y));
+      for (int x = 0; x < width; ++x, ++current_color) {
+        SkColor c = SkUnPreMultiply::PMColorToColor(*current_color);
+        float r = SkColorGetR(c);
+        float g = SkColorGetG(c);
+        float b = SkColorGetB(c);
+        float gray_level = gfx::DotProduct(color_transform, r, g, 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 scalling.
+    a0 = -min_val;
+    if (max_val > min_val)
+      scale = 255.0 / (max_val - min_val);
+    else
+      scale = 0.0;  // If min==max, uniform 0-level image is expected.
+  }
+
+  for (int y = 0; y < height; ++y) {
+    SkPMColor* current_color = static_cast<uint32_t*>(

[Alexei Svitkine (slow), 2013/02/21 19:49:33]

Likewise, cast to SkPMColor*?

[motek., 2013/02/21 22:45:03]

Done.

+        source_bitmap.getAddr32(0, y));
+    uint8_t* target_color = target_bitmap->getAddr8(0, y);
+    for (int x = 0; x < width; ++x, ++current_color) {
+      SkColor c = SkUnPreMultiply::PMColorToColor(*current_color);
+      float r = SkColorGetR(c);
+      float g = SkColorGetG(c);
+      float b = SkColorGetB(c);
+
+      float gl = (a0 + gfx::DotProduct(color_transform, r, g, b)) * scale;
+      if (gl < 0)
+        gl = 0;
+      if (gl > 0xFF)
+        gl = 0xFF;
+      target_color[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);
+}
+
 }  // namespace color_utils