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)
@@ skipping 245 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) {

[Alexei Svitkine (slow), 2013/04/11 18:25:37]

Nit: Remove {}'s.

[motek., 2013/04/12 10:50:59]

Done.

+    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];
+
+      accval >>= ConvolutionFilter1D::kShiftBits;
+      if (absolute_values)
+        accval = std::abs(accval);
+      *target_byte = ClampTo8(accval);
+    }
+
+    // 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];
+      }
+      // Bring this value back in range. All of the filter scaling factors
+      // are in fixed point with kShiftBits bits of fractional part.
+      accval >>= ConvolutionFilter1D::kShiftBits;
+      if (absolute_values)
+        accval = std::abs(accval);
+      *target_byte = ClampTo8(accval);
+    }
+
+    for (; c < image_size.width(); ++c, target_byte += output_channel_count) {
+      int accval = 0;
+      int overlap_taps = image_size.width() - c + centrepoint;
+      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];
+
+      accval >>= ConvolutionFilter1D::kShiftBits;
+      if (absolute_values)
+        accval = std::abs(accval);
+      *target_byte = ClampTo8(accval);
+    }
+
+    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.

[Alexei Svitkine (slow), 2013/04/11 18:25:37]

This logic seems identical to SingleChannelConvolveX1D(). Can you refactor the
common functionality to a helper function in an anon namespace?

[motek., 2013/04/12 10:50:59]

Sort of, kind of. I have plucked a fragment that was indeed repeated verbatim
over and over and moved it to a common part. Where it comes to the parts of
iteration, it is more complicated than that. For instance, to refactor out the
four lines of code here (two four loops + shift-back, which I indeed refactored
now) I would need a function with more parameters than I can count (all but one
trivial). So, picking these individual parts out is probably not worth it. 

On the other hand, you are correct to remark that the logic of both routines is
very alike. But they process the image in different order (row first, column
first) and that makes abstracting parts out a bit of a bother.

It is not impossible, of course. Since in reality this is all operating on 1d
buffers, some clever use of inter-pixel and inter-row strides could result in
basically one function invoked in two different ways. This is not so easy though
and code becomes tricky to interpret because the direct reference to
rows/columns gets lost. In fact, we have discussed this option with senorblanco@
and as far as I remember he agreed with me that we wouldn't do it. At least not
now. Generally I'd leave this option open as I continue to work on this code,
but I am not sure of it yet.

+        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];
+
+      accval >>= ConvolutionFilter1D::kShiftBits;
+      if (absolute_values)
+        accval = std::abs(accval);
+      *target_byte = ClampTo8(accval);
+    }
+
+    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];
+      }
+
+      accval >>= ConvolutionFilter1D::kShiftBits;
+      if (absolute_values)
+        accval = std::abs(accval);
+      *target_byte = ClampTo8(accval);
+    }
+
+    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];
+
+      accval >>= ConvolutionFilter1D::kShiftBits;
+      if (absolute_values)
+        accval = std::abs(accval);
+      *target_byte = ClampTo8(accval);
+    }
+  }
+}
+
 }  // namespace skia