Complete (but inefficient) implementation of the image retargetting method.

skia/ext/convolver.cc

 // Copyright (c) 2011 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.
 
 #include <algorithm>
 
 #include "skia/ext/convolver.h"
 #include "skia/ext/convolver_SSE2.h"
+#include "third_party/skia/include/core/SkSize.h"
 #include "third_party/skia/include/core/SkTypes.h"
 
 namespace skia {
 
 namespace {
 
 // Converts the argument to an 8-bit unsigned value by clamping to the range
 // 0-255.
 inline unsigned char ClampTo8(int a) {
   if (static_cast<unsigned>(a) < 256)
     return a;  // Avoid the extra check in the common case.
   if (a < 0)
     return 0;
   return 255;
 }
 
+// Takes the value produced by accumulating element-wise product of image with
+// a kernel and brings it back into range.
+// All of the filter scaling factors are in fixed point with kShiftBits bits of
+// fractional part.
+inline unsigned char BringBackTo8(int a, bool take_absolute) {
+  a >>= ConvolutionFilter1D::kShiftBits;
+  if (take_absolute)
+    a = std::abs(a);
+  return ClampTo8(a);
+}
+
 // Stores a list of rows in a circular buffer. The usage is you write into it
 // by calling AdvanceRow. It will keep track of which row in the buffer it
 // should use next, and the total number of rows added.
 class CircularRowBuffer {
  public:
   // The number of pixels in each row is given in |source_row_pixel_width|.
   // The maximum number of rows needed in the buffer is |max_y_filter_size|
   // (we only need to store enough rows for the biggest filter).
   //
   // We use the |first_input_row| to compute the coordinates of all of the
@@ skipping 229 matching lines @@
   AddFilter(filter_offset, &fixed_values[0], filter_length);
 }
 
 void ConvolutionFilter1D::AddFilter(int filter_offset,
                                     const Fixed* filter_values,
                                     int filter_length) {
   // It is common for leading/trailing filter values to be zeros. In such
   // cases it is beneficial to only store the central factors.
   // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on
   // a 1080p image this optimization gives a ~10% speed improvement.
+  int filter_size = filter_length;
   int first_non_zero = 0;
   while (first_non_zero < filter_length && filter_values[first_non_zero] == 0)
     first_non_zero++;
 
   if (first_non_zero < filter_length) {
     // Here we have at least one non-zero factor.
     int last_non_zero = filter_length - 1;
     while (last_non_zero >= 0 && filter_values[last_non_zero] == 0)
       last_non_zero--;
 
     filter_offset += first_non_zero;
     filter_length = last_non_zero + 1 - first_non_zero;
     SkASSERT(filter_length > 0);
 
     for (int i = first_non_zero; i <= last_non_zero; i++)
       filter_values_.push_back(filter_values[i]);
   } else {
     // Here all the factors were zeroes.
     filter_length = 0;
   }
 
   FilterInstance instance;
 
   // We pushed filter_length elements onto filter_values_
   instance.data_location = (static_cast<int>(filter_values_.size()) -
                             filter_length);
   instance.offset = filter_offset;
-  instance.length = filter_length;
+  instance.trimmed_length = filter_length;
+  instance.length = filter_size;
   filters_.push_back(instance);
 
   max_filter_ = std::max(max_filter_, filter_length);
 }
 
+const ConvolutionFilter1D::Fixed* ConvolutionFilter1D::GetSingleFilter(
+    int* specified_filter_length,
+    int* filter_offset,
+    int* filter_length) const {
+  const FilterInstance& filter = filters_[0];
+  *filter_offset = filter.offset;
+  *filter_length = filter.trimmed_length;
+  *specified_filter_length = filter.length;
+  if (filter.trimmed_length == 0)
+    return NULL;
+
+  return &filter_values_[filter.data_location];
+}
+
 typedef void (*ConvolveVertically_pointer)(
     const ConvolutionFilter1D::Fixed* filter_values,
     int filter_length,
     unsigned char* const* source_data_rows,
     int pixel_width,
     unsigned char* out_row,
     bool has_alpha);
 typedef void (*Convolve4RowsHorizontally_pointer)(
     const unsigned char* src_data[4],
     const ConvolutionFilter1D& filter,
@@ skipping 154 matching lines @@
                                source_has_alpha);
     } else {
       ConvolveVertically(filter_values, filter_length,
                          first_row_for_filter,
                          filter_x.num_values(), cur_output_row,
                          source_has_alpha);
     }
   }
 }
 
+void SingleChannelConvolveX1D(const unsigned char* source_data,
+                              int source_byte_row_stride,
+                              int input_channel_index,
+                              int input_channel_count,
+                              const ConvolutionFilter1D& filter,
+                              const SkISize& image_size,
+                              unsigned char* output,
+                              int output_byte_row_stride,
+                              int output_channel_index,
+                              int output_channel_count,
+                              bool absolute_values) {
+  int filter_offset, filter_length, filter_size;
+  // Very much unlike BGRAConvolve2D, here we expect to have the same filter
+  // for all pixels.
+  const ConvolutionFilter1D::Fixed* filter_values =
+      filter.GetSingleFilter(&filter_size, &filter_offset, &filter_length);
+
+  if (filter_values == NULL)
+    return;
+
+  int centrepoint = filter_length / 2;
+  if (filter_size - filter_offset != 2 * filter_offset) {
+    // This means the original filter was not symmetrical AND
+    // got clipped from one side more than from the other.
+    centrepoint = filter_size / 2 - filter_offset;
+  }
+
+  const unsigned char* source_data_row = source_data;
+  unsigned char* output_row = output;
+
+  for (int r = 0; r < image_size.height(); ++r) {
+    unsigned char* target_byte = output_row + output_channel_index;
+    // Process the lead part, padding image to the left with the first pixel.
+    int c = 0;
+    for (; c < centrepoint; ++c, target_byte += output_channel_count) {
+      int accval = 0;
+      int i = 0;
+      int pixel_byte_index = input_channel_index;
+      for (; i < centrepoint - c; ++i)  // Padding part.
+        accval += filter_values[i] * source_data_row[pixel_byte_index];
+
+      for (; i < filter_length; ++i, pixel_byte_index += input_channel_count)
+        accval += filter_values[i] * source_data_row[pixel_byte_index];
+
+      *target_byte = BringBackTo8(accval, absolute_values);
+    }
+
+    // Now for the main event.
+    for (; c < image_size.width() - centrepoint;
+         ++c, target_byte += output_channel_count) {
+      int accval = 0;
+      int pixel_byte_index = (c - centrepoint) * input_channel_count +
+          input_channel_index;
+
+      for (int i = 0; i < filter_length;
+           ++i, pixel_byte_index += input_channel_count) {
+        accval += filter_values[i] * source_data_row[pixel_byte_index];
+      }
+
+      *target_byte = BringBackTo8(accval, absolute_values);
+    }
+
+    for (; c < image_size.width(); ++c, target_byte += output_channel_count) {
+      int accval = 0;
+      int overlap_taps = image_size.width() - c + centrepoint;

[Stephen White, 2013/04/12 12:15:21]

Does this handle the case where the image width is less than the filter width?

+      int pixel_byte_index = (c - centrepoint) * input_channel_count +
+          input_channel_index;
+      int i = 0;
+      for (; i < overlap_taps - 1; ++i, pixel_byte_index += input_channel_count)
+        accval += filter_values[i] * source_data_row[pixel_byte_index];
+
+      for (; i < filter_length; ++i)
+        accval += filter_values[i] * source_data_row[pixel_byte_index];
+
+      *target_byte = BringBackTo8(accval, absolute_values);
+    }
+
+    source_data_row += source_byte_row_stride;
+    output_row += output_byte_row_stride;
+  }
+}
+
+void SingleChannelConvolveY1D(const unsigned char* source_data,
+                              int source_byte_row_stride,
+                              int input_channel_index,
+                              int input_channel_count,
+                              const ConvolutionFilter1D& filter,
+                              const SkISize& image_size,
+                              unsigned char* output,
+                              int output_byte_row_stride,
+                              int output_channel_index,
+                              int output_channel_count,
+                              bool absolute_values) {
+  int filter_offset, filter_length, filter_size;
+  // Very much unlike BGRAConvolve2D, here we expect to have the same filter
+  // for all pixels.
+  const ConvolutionFilter1D::Fixed* filter_values =
+      filter.GetSingleFilter(&filter_size, &filter_offset, &filter_length);
+
+  if (filter_values == NULL)
+    return;
+
+  int centrepoint = filter_length / 2;
+  if (filter_size - filter_offset != 2 * filter_offset) {
+    // This means the original filter was not symmetrical AND
+    // got clipped from one side more than from the other.
+    centrepoint = filter_size / 2 - filter_offset;
+  }
+
+  for (int c = 0; c < image_size.width(); ++c) {
+    unsigned char* target_byte = output + c * output_channel_count +
+        output_channel_index;
+    int r = 0;
+
+    for (; r < centrepoint; ++r, target_byte += output_byte_row_stride) {
+      int accval = 0;
+      int i = 0;
+      int pixel_byte_index = c * input_channel_count + input_channel_index;
+
+      for (; i < centrepoint - r; ++i)  // Padding part.
+        accval += filter_values[i] * source_data[pixel_byte_index];
+
+      for (; i < filter_length; ++i, pixel_byte_index += source_byte_row_stride)
+        accval += filter_values[i] * source_data[pixel_byte_index];
+
+      *target_byte = BringBackTo8(accval, absolute_values);
+    }
+
+    for (; r < image_size.height() - centrepoint;
+         ++r, target_byte += output_byte_row_stride) {
+      int accval = 0;
+      int pixel_byte_index = (r - centrepoint) * source_byte_row_stride +
+          c * input_channel_count + input_channel_index;
+      for (int i = 0; i < filter_length;
+           ++i, pixel_byte_index += source_byte_row_stride) {
+        accval += filter_values[i] * source_data[pixel_byte_index];
+      }
+
+      *target_byte = BringBackTo8(accval, absolute_values);
+    }
+
+    for (; r < image_size.height();
+         ++r, target_byte += output_byte_row_stride) {
+      int accval = 0;
+      int overlap_taps = image_size.height() - r + centrepoint;
+      int pixel_byte_index = (r - centrepoint) * source_byte_row_stride +
+          c * input_channel_count + input_channel_index;
+      int i = 0;
+      for (; i < overlap_taps - 1;
+           ++i, pixel_byte_index += source_byte_row_stride) {
+        accval += filter_values[i] * source_data[pixel_byte_index];
+      }
+
+      for (; i < filter_length; ++i)
+        accval += filter_values[i] * source_data[pixel_byte_index];
+
+      *target_byte = BringBackTo8(accval, absolute_values);
+    }
+  }
+}
+
 }  // namespace skia