Integration of most changes from the GoogleTV project around the convolver/sc...

skia/ext/image_operations.cc

-// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #define _USE_MATH_DEFINES
+#include <algorithm>
 #include <cmath>
 #include <limits>
 
 #include "skia/ext/image_operations.h"
 
 // TODO(pkasting): skia/ext should not depend on base/!
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
 #include "base/stack_container.h"
 #include "base/time.h"
@@ skipping 36 matching lines @@
   if (x <= -filter_size || x >= filter_size)
     return 0.0f;  // Outside of the window.
   if (x > -std::numeric_limits<float>::epsilon() &&
       x < std::numeric_limits<float>::epsilon())
     return 1.0f;  // Special case the discontinuity at the origin.
   float xpi = x * static_cast<float>(M_PI);
   return (sin(xpi) / xpi) *  // sinc(x)
           sin(xpi / filter_size) / (xpi / filter_size);  // sinc(x/filter_size)
 }
 
+// Evaluates the Hamming filter of the given filter size window for the given
+// position.
+//
+// The filter covers [-filter_size, +filter_size]. Outside of this window
+// the value of the function is 0. Inside of the window, the value is sinus
+// cardinal multiplied by a recentered Hamming function. The traditional
+// Hamming formula for a window of size N and n ranging in [0, N-1] is:
+//   hamming(n) = 0.54 - 0.46 * cos(2 * pi * n / (N-1)))
+// In our case we want the function centered for x == 0 and at its minimum
+// on both ends of the window (x == +/- filter_size), hence the adjusted
+// formula:
+//   hamming(x) = (0.54 -
+//                 0.46 * cos(2 * pi * (x - filter_size)/ (2 * filter_size)))
+//              = 0.54 - 0.46 * cos(pi * x / filter_size - pi)
+//              = 0.54 + 0.46 * cos(pi * x / filter_size)
+float EvalHamming(int filter_size, float x) {
+  if (x <= -filter_size || x >= filter_size)
+    return 0.0f;  // Outside of the window.
+  if (x > -std::numeric_limits<float>::epsilon() &&
+      x < std::numeric_limits<float>::epsilon())
+    return 1.0f;  // Special case the sinc discontinuity at the origin.
+  const float xpi = x * static_cast<float>(M_PI);
+
+  return ((sin(xpi) / xpi) *  // sinc(x)
+          (0.54f + 0.46f * cos(xpi / filter_size)));  // hamming(x)
+}
+
 // ResizeFilter ----------------------------------------------------------------
 
 // Encapsulates computation and storage of the filters required for one complete
 // resize operation.
 class ResizeFilter {
  public:
   ResizeFilter(ImageOperations::ResizeMethod method,
                int src_full_width, int src_full_height,
                int dest_width, int dest_height,
                const SkIRect& dest_subset);
 
   // Returns the bounds in the input bitmap of data that is used in the output.
   // The filter offsets are within this rectangle.
   const SkIRect& src_depend() { return src_depend_; }
 
   // Returns the filled filter values.
   const ConvolutionFilter1D& x_filter() { return x_filter_; }
   const ConvolutionFilter1D& y_filter() { return y_filter_; }
 
  private:
   // Returns the number of pixels that the filer spans, in filter space (the
   // destination image).
   float GetFilterSupport(float scale) {
     switch (method_) {
       case ImageOperations::RESIZE_BOX:
         // The box filter just scales with the image scaling.
         return 0.5f;  // Only want one side of the filter = /2.
+      case ImageOperations::RESIZE_HAMMING1:
+        // The Hamming filter takes as much space in the source image in
+        // each direction as the size of the window = 1 for Hamming1.
+        return 1.0f;
+      case ImageOperations::RESIZE_LANCZOS2:

[brettw, 2010/12/17 20:07:55]

Where is LANCZOS1 handled? Same below.

[evannier, 2010/12/19 00:15:03]

LANCZOS1 should never have been in the checkin (it was an experiment I had).
Hamming1 provides the same CPU performance. I removed all references to it.

+        // The Lanczos filter takes as much space in the source image in
+        // each direction as the size of the window = 2 for Lanczos2.
+        return 2.0f;
       case ImageOperations::RESIZE_LANCZOS3:
-        // The lanczos filter takes as much space in the source image in
+        // The Lanczos filter takes as much space in the source image in
         // each direction as the size of the window = 3 for Lanczos3.
         return 3.0f;
       default:
         NOTREACHED();
         return 1.0f;
     }
   }
 
   // Computes one set of filters either horizontally or vertically. The caller
   // will specify the "min" and "max" rather than the bottom/top and
   // right/bottom so that the same code can be re-used in each dimension.
   //
   // |src_depend_lo| and |src_depend_size| gives the range for the source
   // depend rectangle (horizontally or vertically at the caller's discretion
   // -- see above for what this means).
   //
   // Likewise, the range of destination values to compute and the scale factor
   // for the transform is also specified.
   void ComputeFilters(int src_size,
                       int dest_subset_lo, int dest_subset_size,
                       float scale, float src_support,
                       ConvolutionFilter1D* output);
 
   // Computes the filter value given the coordinate in filter space.
   inline float ComputeFilter(float pos) {
     switch (method_) {
       case ImageOperations::RESIZE_BOX:
         return EvalBox(pos);
+      case ImageOperations::RESIZE_HAMMING1:
+        return EvalHamming(1, pos);
+      case ImageOperations::RESIZE_LANCZOS2:
+        return EvalLanczos(2, pos);
       case ImageOperations::RESIZE_LANCZOS3:
         return EvalLanczos(3, pos);
       default:
         NOTREACHED();
         return 0;
     }
   }
 
   ImageOperations::ResizeMethod method_;
 
@@ skipping 13 matching lines @@
 
   DISALLOW_COPY_AND_ASSIGN(ResizeFilter);
 };
 
 ResizeFilter::ResizeFilter(ImageOperations::ResizeMethod method,
                            int src_full_width, int src_full_height,
                            int dest_width, int dest_height,
                            const SkIRect& dest_subset)
     : method_(method),
       out_bounds_(dest_subset) {
+  // method_ will only ever refer to an "algorithm method".
+  SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method)
+           && (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));
+
   float scale_x = static_cast<float>(dest_width) /
                   static_cast<float>(src_full_width);
   float scale_y = static_cast<float>(dest_height) /
                   static_cast<float>(src_full_height);
 
   x_filter_support_ = GetFilterSupport(scale_x);
   y_filter_support_ = GetFilterSupport(scale_y);
 
-  SkIRect src_full = { 0, 0, src_full_width, src_full_height };
-  SkIRect dest_full = { 0, 0, static_cast<int>(src_full_width * scale_x + 0.5),
-                        static_cast<int>(src_full_height * scale_y + 0.5) };
-
   // Support of the filter in source space.
   float src_x_support = x_filter_support_ / scale_x;
   float src_y_support = y_filter_support_ / scale_y;
 
   ComputeFilters(src_full_width, dest_subset.fLeft, dest_subset.width(),
                  scale_x, src_x_support, &x_filter_);
   ComputeFilters(src_full_height, dest_subset.fTop, dest_subset.height(),
                  scale_y, src_y_support, &y_filter_);
 }
 
+// TODO(egouriou): Take advantage of periods in the convolution.
+// Practical resizing filters are periodic outside of the border area.
+// For Lanczos, a scaling by a (reduced) factor of p/q (q pixels in the
+// source become p pixels in the destination) will have a period of p.
+// A nice consequence is a period of 1 when downscaling by an integral
+// factor. Downscaling from typical display resolutions is also bound
+// to produce interesting periods as those are chosen to have multiple
+// small factors.
+// Small periods reduce computational load and improve cache usage if
+// the coefficients can be shared. For periods of 1 we can consider
+// loading the factors only once outside the borders.
 void ResizeFilter::ComputeFilters(int src_size,
                                   int dest_subset_lo, int dest_subset_size,
                                   float scale, float src_support,
                                   ConvolutionFilter1D* output) {
   int dest_subset_hi = dest_subset_lo + dest_subset_size;  // [lo, hi)
 
   // When we're doing a magnification, the scale will be larger than one. This
   // means the destination pixels are much smaller than the source pixels, and
   // that the range covered by the filter won't necessarily cover any source
   // pixel boundaries. Therefore, we use these clamped values (max of 1) for
@@ skipping 10 matching lines @@
   // filter values for each one. Those values will tell us how to blend the
   // source pixels to compute the destination pixel.
   for (int dest_subset_i = dest_subset_lo; dest_subset_i < dest_subset_hi;
        dest_subset_i++) {
     // Reset the arrays. We don't declare them inside so they can re-use the
     // same malloc-ed buffer.
     filter_values->clear();
     fixed_filter_values->clear();
 
     // This is the pixel in the source directly under the pixel in the dest.
-    float src_pixel = dest_subset_i * inv_scale;
+    // Note that we base computations on the "center" of the pixels. To see
+    // why, observe that the destination pixel at coordinates (0, 0) in a 5.0x
+    // downscale should "cover" the pixels around the pixel with *its center*
+    // at coordinates (2.5, 2.5) in the source, not those around (0, 0).
+    // Hence we need to scale coordinates (0.5, 0.5), not (0, 0).
+    float src_pixel = (static_cast<float>(dest_subset_i) + 0.5f) * inv_scale;

[brettw, 2010/12/17 20:07:55]

This change you made should shift everything by 0.5 pixels, is that right? (I'm
not arguing that this change is wrong, I just want to be clear what's happening.
I have suspected we have the pixel centers off by 0.5 in the past.)

[evannier, 2010/12/19 00:15:03]

This is correct.
Basically, if you did the simple experiment of taking an image that was a
checkerboard of black and white (or any two colors for that matter), and scale
it down exactly by a factor of 2, you would expect to have all pixels to
uniformly grey.
But without that change, the first generated pixels on the two axis x = 0 and y
= 0 had the color of the pixel in the source space at that position.
One of the unit tests you might have reviewed already covers this very issue.

[brettw, 2010/12/20 18:18:45]

That's great, thanks for this fix.

Unfortunately, this is the type of thing that can be difficult to land because
there are layout test results that depend on the old behavior. We'll need to
rebaseline the layout tests so things don't go red.

I talked to some of the people who work on WebKit who said that what we do
depend on the number of tests this "breaks." Can you do a try bot run with
layout tests to see how many this is?
  gcl try yourchange -b win_layout
Alternatively, you can run the tests locally with
  make test_shell; make ImageDiff; make DumpRenderTree
  webkit/tools/layout_tests/run_webkit_tests.sh --pixel-tests --debug

[evannier, 2011/01/18 21:51:53]

I have the fix in the code, but commented out for now. I have also filed issue
69999.
I will be happy to work with somebody on getting these fixes in if somebody is
willing to tell me all the necessary steps that I should go through to avoid
making mistakes when changing these images.
On 2010/12/20 18:18:45, brettw wrote:

 
     // Compute the (inclusive) range of source pixels the filter covers.
     int src_begin = std::max(0, FloorInt(src_pixel - src_support));
     int src_end = std::min(src_size - 1, CeilInt(src_pixel + src_support));
 
     // Compute the unnormalized filter value at each location of the source
     // it covers.
     float filter_sum = 0.0f;  // Sub of the filter values for normalizing.
     for (int cur_filter_pixel = src_begin; cur_filter_pixel <= src_end;
          cur_filter_pixel++) {
       // Distance from the center of the filter, this is the filter coordinate
-      // in source space.
-      float src_filter_pos = cur_filter_pixel - src_pixel;
+      // in source space. We also need to consider the center of the pixel
+      // when comparing distance against 'src_pixel'. In the 5x downscale
+      // example used above the distance from the center of the filter to
+      // the pixel with coordinates (2, 2) should be 0, because its center
+      // is at (2.5, 2.5).
+      float src_filter_dist = ((static_cast<float>(cur_filter_pixel) + 0.5f) -
+                               src_pixel);
 
       // Since the filter really exists in dest space, map it there.
-      float dest_filter_pos = src_filter_pos * clamped_scale;
+      float dest_filter_dist = src_filter_dist * clamped_scale;
 
       // Compute the filter value at that location.
-      float filter_value = ComputeFilter(dest_filter_pos);
+      float filter_value = ComputeFilter(dest_filter_dist);
       filter_values->push_back(filter_value);
 
       filter_sum += filter_value;
     }
     DCHECK(!filter_values->empty()) << "We should always get a filter!";
 
     // The filter must be normalized so that we don't affect the brightness of
     // the image. Convert to normalized fixed point.
     int16 fixed_sum = 0;
     for (size_t i = 0; i < filter_values->size(); i++) {
@@ skipping 128 matching lines @@
 #else
   return SkBitmap();
 #endif  // OS_POSIX && !OS_MACOSX
 }
 
 // static
 SkBitmap ImageOperations::ResizeBasic(const SkBitmap& source,
                                       ResizeMethod method,
                                       int dest_width, int dest_height,
                                       const SkIRect& dest_subset) {
+  // Ensure that the ResizeMethod enumeration is sound.
+  SkASSERT(((RESIZE_FIRST_QUALITY_METHOD <= method)
+            && (method <= RESIZE_LAST_QUALITY_METHOD))
+           || ((RESIZE_FIRST_ALGORITHM_METHOD <= method)
+               && (method <= RESIZE_LAST_ALGORITHM_METHOD)));
+
   // Time how long this takes to see if it's a problem for users.
   base::TimeTicks resize_start = base::TimeTicks::Now();
 
   SkIRect dest = { 0, 0, dest_width, dest_height };
   DCHECK(dest.contains(dest_subset)) <<
       "The supplied subset does not fall within the destination image.";
 
   // If the size of source or destination is 0, i.e. 0x0, 0xN or Nx0, just
   // return empty.
   if (source.width() < 1 || source.height() < 1 ||
       dest_width < 1 || dest_height < 1)
     return SkBitmap();
 
+  // Convert any "Quality Method" into an "Algorithm Method"
+  if (   (RESIZE_FIRST_QUALITY_METHOD <= method)

[brettw, 2010/12/17 20:07:55]

We'd normally put the && at the end of this first line, and delete the extra
space you added.

[evannier, 2010/12/19 00:15:03]

Done.

+      && (method <= RESIZE_LAST_QUALITY_METHOD)) {
+#if defined(GTV)

[brettw, 2010/12/17 20:07:55]

I don't think you need this define, it seems like your rules should be good for
everybody (and this won't change the current Chrome behavior at all since we use
hardcoded algorithms).

Can you make this lookup a separate function in the anonymous namespace at the
top? This function is getting quite long, and it would be easier to follow if it
just said
  if (<method in range>)
    method = QualityMethodToAlgorithmMethod(method);

[evannier, 2010/12/19 00:15:03]

That is correct. But as you can imagine, there will be a subsequent change that
will rename all instances inside Chrome to start using quality instead of
algorithm. That allows us to define a policy for a given platform in a single
place. Therefore, the ifdef would have to be there to cover that subsequent
change.
Good point. Cleaned up.

[brettw, 2010/12/20 18:18:45]

I agree we may need an ifdef for some platforms. But I think the default would
generally be the exact things you've defined here. Sometimes the subsequent
cleanup patches don't get landed, so I want to be sure that the meaning of the
GOOD/BETTER/BEST is reasonable and reflects what I would expect reading the
header. Currently, this is all LANCZOS3 which I would not expect. If some
platforms need to tweak the list you've made here, I would expect that to be
added as an ifdef at a later point.

[evannier, 2011/01/18 21:51:53]

Done. Fair enough. For now, I have removed the ifdef as you suggested. A
subsequent checkin will refine this.

+    // The call to ImageOperationsGtv::Resize() above took care of
+    // GPU-acceleration in the cases where it is possible. So now we just
+    // pick the appropriate software method for each resize quality.
+    switch (method) {
+      // Users of RESIZE_GOOD are willing to trade a lot of quality to
+      // get speed, allowing the use of linear resampling to get hardware
+      // acceleration (SRB). Hence any of our "good" software filters
+      // will be acceptable, and we use the fastest one, Hamming-1.
+      case RESIZE_GOOD:
+      // Users of RESIZE_BETTER are willing to trade some quality in order
+      // to improve performance, but are guaranteed not to devolve to a linear
+      // resampling. In visual tests we see that Hamming-1 is not as good as
+      // Lanczos-2, however it is about 40% faster and Lanczos-2 itself is
+      // about 30% faster than Lanczos-3. The use of Hamming-1 has been deemed
+      // an acceptable trade-off between quality and speed.
+      case RESIZE_BETTER:
+        method = RESIZE_HAMMING1;
+        break;
+      default:
+        method = RESIZE_LANCZOS3;
+        break;
+    }
+#else
+    method = RESIZE_LANCZOS3;
+#endif
+  }
+
+  // Check that we deal with an "algorithm methods" from this point onward.
+  SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method)
+           && (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));
+
   SkAutoLockPixels locker(source);
 
   ResizeFilter filter(method, source.width(), source.height(),
                       dest_width, dest_height, dest_subset);
 
   // Get a source bitmap encompassing this touched area. We construct the
   // offsets and row strides such that it looks like a new bitmap, while
   // referring to the old data.
   const uint8* source_subset =
       reinterpret_cast<const uint8*>(source.getPixels());
 
   // Convolve into the result.
   SkBitmap result;
   result.setConfig(SkBitmap::kARGB_8888_Config,
                    dest_subset.width(), dest_subset.height());
   result.allocPixels();
   BGRAConvolve2D(source_subset, static_cast<int>(source.rowBytes()),
                  !source.isOpaque(), filter.x_filter(), filter.y_filter(),
+                 static_cast<int>(result.rowBytes()),
                  static_cast<unsigned char*>(result.getPixels()));
 
   // Preserve the "opaque" flag for use as an optimization later.
   result.setIsOpaque(source.isOpaque());
 
   base::TimeDelta delta = base::TimeTicks::Now() - resize_start;
   UMA_HISTOGRAM_TIMES("Image.ResampleMS", delta);
 
   return result;
 }
 
 // static
 SkBitmap ImageOperations::Resize(const SkBitmap& source,
                                  ResizeMethod method,
                                  int dest_width, int dest_height) {
   SkIRect dest_subset = { 0, 0, dest_width, dest_height };
   return Resize(source, method, dest_width, dest_height, dest_subset);
 }
 
 }  // namespace skia