1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <stddef.h>
6 #include <stdint.h>
7
8 #include <algorithm>
9 #include <limits>
10
11 #include "skia/ext/image_operations.h"
12
13 #include "base/check.h"
14 #include "base/containers/stack_container.h"
15 #include "base/macros.h"
16 #include "base/metrics/histogram_macros.h"
17 #include "base/notreached.h"
18 #include "base/numerics/math_constants.h"
19 #include "base/time/time.h"
20 #include "base/trace_event/trace_event.h"
21 #include "build/build_config.h"
22 #include "skia/ext/convolver.h"
23 #include "third_party/skia/include/core/SkColorPriv.h"
24 #include "third_party/skia/include/core/SkRect.h"
25
26 namespace skia {
27
28 namespace {
29
30 // Returns the ceiling/floor as an integer.
CeilInt(float val)31 inline int CeilInt(float val) {
32 return static_cast<int>(ceil(val));
33 }
FloorInt(float val)34 inline int FloorInt(float val) {
35 return static_cast<int>(floor(val));
36 }
37
38 // Filter function computation -------------------------------------------------
39
40 // Evaluates the box filter, which goes from -0.5 to +0.5.
EvalBox(float x)41 float EvalBox(float x) {
42 return (x >= -0.5f && x < 0.5f) ? 1.0f : 0.0f;
43 }
44
45 // Evaluates the Lanczos filter of the given filter size window for the given
46 // position.
47 //
48 // |filter_size| is the width of the filter (the "window"), outside of which
49 // the value of the function is 0. Inside of the window, the value is the
50 // normalized sinc function:
51 // lanczos(x) = sinc(x) * sinc(x / filter_size);
52 // where
53 // sinc(x) = sin(pi*x) / (pi*x);
EvalLanczos(int filter_size,float x)54 float EvalLanczos(int filter_size, float x) {
55 if (x <= -filter_size || x >= filter_size)
56 return 0.0f; // Outside of the window.
57 if (x > -std::numeric_limits<float>::epsilon() &&
58 x < std::numeric_limits<float>::epsilon())
59 return 1.0f; // Special case the discontinuity at the origin.
60 float xpi = x * base::kPiFloat;
61 return (sin(xpi) / xpi) * // sinc(x)
62 sin(xpi / filter_size) / (xpi / filter_size); // sinc(x/filter_size)
63 }
64
65 // Evaluates the Hamming filter of the given filter size window for the given
66 // position.
67 //
68 // The filter covers [-filter_size, +filter_size]. Outside of this window
69 // the value of the function is 0. Inside of the window, the value is sinus
70 // cardinal multiplied by a recentered Hamming function. The traditional
71 // Hamming formula for a window of size N and n ranging in [0, N-1] is:
72 // hamming(n) = 0.54 - 0.46 * cos(2 * pi * n / (N-1)))
73 // In our case we want the function centered for x == 0 and at its minimum
74 // on both ends of the window (x == +/- filter_size), hence the adjusted
75 // formula:
76 // hamming(x) = (0.54 -
77 // 0.46 * cos(2 * pi * (x - filter_size)/ (2 * filter_size)))
78 // = 0.54 - 0.46 * cos(pi * x / filter_size - pi)
79 // = 0.54 + 0.46 * cos(pi * x / filter_size)
EvalHamming(int filter_size,float x)80 float EvalHamming(int filter_size, float x) {
81 if (x <= -filter_size || x >= filter_size)
82 return 0.0f; // Outside of the window.
83 if (x > -std::numeric_limits<float>::epsilon() &&
84 x < std::numeric_limits<float>::epsilon())
85 return 1.0f; // Special case the sinc discontinuity at the origin.
86 const float xpi = x * base::kPiFloat;
87
88 return ((sin(xpi) / xpi) * // sinc(x)
89 (0.54f + 0.46f * cos(xpi / filter_size))); // hamming(x)
90 }
91
92 // ResizeFilter ----------------------------------------------------------------
93
94 // Encapsulates computation and storage of the filters required for one complete
95 // resize operation.
96 class ResizeFilter {
97 public:
98 ResizeFilter(ImageOperations::ResizeMethod method,
99 int src_full_width, int src_full_height,
100 int dest_width, int dest_height,
101 const SkIRect& dest_subset);
102
103 // Returns the filled filter values.
x_filter()104 const ConvolutionFilter1D& x_filter() { return x_filter_; }
y_filter()105 const ConvolutionFilter1D& y_filter() { return y_filter_; }
106
107 private:
108 // Returns the number of pixels that the filer spans, in filter space (the
109 // destination image).
GetFilterSupport(float scale)110 float GetFilterSupport(float scale) {
111 switch (method_) {
112 case ImageOperations::RESIZE_BOX:
113 // The box filter just scales with the image scaling.
114 return 0.5f; // Only want one side of the filter = /2.
115 case ImageOperations::RESIZE_HAMMING1:
116 // The Hamming filter takes as much space in the source image in
117 // each direction as the size of the window = 1 for Hamming1.
118 return 1.0f;
119 case ImageOperations::RESIZE_LANCZOS3:
120 // The Lanczos filter takes as much space in the source image in
121 // each direction as the size of the window = 3 for Lanczos3.
122 return 3.0f;
123 default:
124 NOTREACHED();
125 return 1.0f;
126 }
127 }
128
129 // Computes one set of filters either horizontally or vertically. The caller
130 // will specify the "min" and "max" rather than the bottom/top and
131 // right/bottom so that the same code can be re-used in each dimension.
132 //
133 // |src_depend_lo| and |src_depend_size| gives the range for the source
134 // depend rectangle (horizontally or vertically at the caller's discretion
135 // -- see above for what this means).
136 //
137 // Likewise, the range of destination values to compute and the scale factor
138 // for the transform is also specified.
139 void ComputeFilters(int src_size,
140 int dest_subset_lo, int dest_subset_size,
141 float scale,
142 ConvolutionFilter1D* output);
143
144 // Computes the filter value given the coordinate in filter space.
ComputeFilter(float pos)145 inline float ComputeFilter(float pos) {
146 switch (method_) {
147 case ImageOperations::RESIZE_BOX:
148 return EvalBox(pos);
149 case ImageOperations::RESIZE_HAMMING1:
150 return EvalHamming(1, pos);
151 case ImageOperations::RESIZE_LANCZOS3:
152 return EvalLanczos(3, pos);
153 default:
154 NOTREACHED();
155 return 0;
156 }
157 }
158
159 ImageOperations::ResizeMethod method_;
160
161 ConvolutionFilter1D x_filter_;
162 ConvolutionFilter1D y_filter_;
163
164 DISALLOW_COPY_AND_ASSIGN(ResizeFilter);
165 };
166
ResizeFilter(ImageOperations::ResizeMethod method,int src_full_width,int src_full_height,int dest_width,int dest_height,const SkIRect & dest_subset)167 ResizeFilter::ResizeFilter(ImageOperations::ResizeMethod method,
168 int src_full_width,
169 int src_full_height,
170 int dest_width,
171 int dest_height,
172 const SkIRect& dest_subset)
173 : method_(method) {
174 // method_ will only ever refer to an "algorithm method".
175 SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method) &&
176 (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));
177
178 float scale_x = static_cast<float>(dest_width) /
179 static_cast<float>(src_full_width);
180 float scale_y = static_cast<float>(dest_height) /
181 static_cast<float>(src_full_height);
182
183 ComputeFilters(src_full_width, dest_subset.fLeft, dest_subset.width(),
184 scale_x, &x_filter_);
185 ComputeFilters(src_full_height, dest_subset.fTop, dest_subset.height(),
186 scale_y, &y_filter_);
187 }
188
189 // TODO(egouriou): Take advantage of periods in the convolution.
190 // Practical resizing filters are periodic outside of the border area.
191 // For Lanczos, a scaling by a (reduced) factor of p/q (q pixels in the
192 // source become p pixels in the destination) will have a period of p.
193 // A nice consequence is a period of 1 when downscaling by an integral
194 // factor. Downscaling from typical display resolutions is also bound
195 // to produce interesting periods as those are chosen to have multiple
196 // small factors.
197 // Small periods reduce computational load and improve cache usage if
198 // the coefficients can be shared. For periods of 1 we can consider
199 // loading the factors only once outside the borders.
ComputeFilters(int src_size,int dest_subset_lo,int dest_subset_size,float scale,ConvolutionFilter1D * output)200 void ResizeFilter::ComputeFilters(int src_size,
201 int dest_subset_lo, int dest_subset_size,
202 float scale,
203 ConvolutionFilter1D* output) {
204 int dest_subset_hi = dest_subset_lo + dest_subset_size; // [lo, hi)
205
206 // When we're doing a magnification, the scale will be larger than one. This
207 // means the destination pixels are much smaller than the source pixels, and
208 // that the range covered by the filter won't necessarily cover any source
209 // pixel boundaries. Therefore, we use these clamped values (max of 1) for
210 // some computations.
211 float clamped_scale = std::min(1.0f, scale);
212
213 // This is how many source pixels from the center we need to count
214 // to support the filtering function.
215 float src_support = GetFilterSupport(clamped_scale) / clamped_scale;
216
217 // Speed up the divisions below by turning them into multiplies.
218 float inv_scale = 1.0f / scale;
219
220 base::StackVector<float, 64> filter_values;
221 base::StackVector<int16_t, 64> fixed_filter_values;
222
223 // Loop over all pixels in the output range. We will generate one set of
224 // filter values for each one. Those values will tell us how to blend the
225 // source pixels to compute the destination pixel.
226 for (int dest_subset_i = dest_subset_lo; dest_subset_i < dest_subset_hi;
227 dest_subset_i++) {
228 // Reset the arrays. We don't declare them inside so they can re-use the
229 // same malloc-ed buffer.
230 filter_values->clear();
231 fixed_filter_values->clear();
232
233 // This is the pixel in the source directly under the pixel in the dest.
234 // Note that we base computations on the "center" of the pixels. To see
235 // why, observe that the destination pixel at coordinates (0, 0) in a 5.0x
236 // downscale should "cover" the pixels around the pixel with *its center*
237 // at coordinates (2.5, 2.5) in the source, not those around (0, 0).
238 // Hence we need to scale coordinates (0.5, 0.5), not (0, 0).
239 float src_pixel = (static_cast<float>(dest_subset_i) + 0.5f) * inv_scale;
240
241 // Compute the (inclusive) range of source pixels the filter covers.
242 int src_begin = std::max(0, FloorInt(src_pixel - src_support));
243 int src_end = std::min(src_size - 1, CeilInt(src_pixel + src_support));
244
245 // Compute the unnormalized filter value at each location of the source
246 // it covers.
247 float filter_sum = 0.0f; // Sub of the filter values for normalizing.
248 for (int cur_filter_pixel = src_begin; cur_filter_pixel <= src_end;
249 cur_filter_pixel++) {
250 // Distance from the center of the filter, this is the filter coordinate
251 // in source space. We also need to consider the center of the pixel
252 // when comparing distance against 'src_pixel'. In the 5x downscale
253 // example used above the distance from the center of the filter to
254 // the pixel with coordinates (2, 2) should be 0, because its center
255 // is at (2.5, 2.5).
256 float src_filter_dist =
257 ((static_cast<float>(cur_filter_pixel) + 0.5f) - src_pixel);
258
259 // Since the filter really exists in dest space, map it there.
260 float dest_filter_dist = src_filter_dist * clamped_scale;
261
262 // Compute the filter value at that location.
263 float filter_value = ComputeFilter(dest_filter_dist);
264 filter_values->push_back(filter_value);
265
266 filter_sum += filter_value;
267 }
268 DCHECK(!filter_values->empty()) << "We should always get a filter!";
269
270 // The filter must be normalized so that we don't affect the brightness of
271 // the image. Convert to normalized fixed point.
272 int16_t fixed_sum = 0;
273 for (size_t i = 0; i < filter_values->size(); i++) {
274 int16_t cur_fixed = output->FloatToFixed(filter_values[i] / filter_sum);
275 fixed_sum += cur_fixed;
276 fixed_filter_values->push_back(cur_fixed);
277 }
278
279 // The conversion to fixed point will leave some rounding errors, which
280 // we add back in to avoid affecting the brightness of the image. We
281 // arbitrarily add this to the center of the filter array (this won't always
282 // be the center of the filter function since it could get clipped on the
283 // edges, but it doesn't matter enough to worry about that case).
284 int16_t leftovers = output->FloatToFixed(1.0f) - fixed_sum;
285 fixed_filter_values[fixed_filter_values->size() / 2] += leftovers;
286
287 // Now it's ready to go.
288 output->AddFilter(src_begin, &fixed_filter_values[0],
289 static_cast<int>(fixed_filter_values->size()));
290 }
291
292 output->PaddingForSIMD();
293 }
294
ResizeMethodToAlgorithmMethod(ImageOperations::ResizeMethod method)295 ImageOperations::ResizeMethod ResizeMethodToAlgorithmMethod(
296 ImageOperations::ResizeMethod method) {
297 // Convert any "Quality Method" into an "Algorithm Method"
298 if (method >= ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD &&
299 method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD) {
300 return method;
301 }
302 // The call to ImageOperationsGtv::Resize() above took care of
303 // GPU-acceleration in the cases where it is possible. So now we just
304 // pick the appropriate software method for each resize quality.
305 switch (method) {
306 // Users of RESIZE_GOOD are willing to trade a lot of quality to
307 // get speed, allowing the use of linear resampling to get hardware
308 // acceleration (SRB). Hence any of our "good" software filters
309 // will be acceptable, and we use the fastest one, Hamming-1.
310 case ImageOperations::RESIZE_GOOD:
311 // Users of RESIZE_BETTER are willing to trade some quality in order
312 // to improve performance, but are guaranteed not to devolve to a linear
313 // resampling. In visual tests we see that Hamming-1 is not as good as
314 // Lanczos-2, however it is about 40% faster and Lanczos-2 itself is
315 // about 30% faster than Lanczos-3. The use of Hamming-1 has been deemed
316 // an acceptable trade-off between quality and speed.
317 case ImageOperations::RESIZE_BETTER:
318 return ImageOperations::RESIZE_HAMMING1;
319 default:
320 return ImageOperations::RESIZE_LANCZOS3;
321 }
322 }
323
324 } // namespace
325
326 // Resize ----------------------------------------------------------------------
327
328 // static
Resize(const SkPixmap & source,ResizeMethod method,int dest_width,int dest_height,const SkIRect & dest_subset,SkBitmap::Allocator * allocator)329 SkBitmap ImageOperations::Resize(const SkPixmap& source,
330 ResizeMethod method,
331 int dest_width,
332 int dest_height,
333 const SkIRect& dest_subset,
334 SkBitmap::Allocator* allocator) {
335 TRACE_EVENT2("disabled-by-default-skia", "ImageOperations::Resize",
336 "src_pixels", source.width() * source.height(), "dst_pixels",
337 dest_width * dest_height);
338 // Ensure that the ResizeMethod enumeration is sound.
339 SkASSERT(((RESIZE_FIRST_QUALITY_METHOD <= method) &&
340 (method <= RESIZE_LAST_QUALITY_METHOD)) ||
341 ((RESIZE_FIRST_ALGORITHM_METHOD <= method) &&
342 (method <= RESIZE_LAST_ALGORITHM_METHOD)));
343
344 // Time how long this takes to see if it's a problem for users.
345 base::TimeTicks resize_start = base::TimeTicks::Now();
346
347 // If the size of source or destination is 0, i.e. 0x0, 0xN or Nx0, just
348 // return empty.
349 if (source.width() < 1 || source.height() < 1 ||
350 dest_width < 1 || dest_height < 1)
351 return SkBitmap();
352
353 SkIRect dest = {0, 0, dest_width, dest_height};
354 DCHECK(dest.contains(dest_subset))
355 << "The supplied subset does not fall within the destination image.";
356
357 method = ResizeMethodToAlgorithmMethod(method);
358 // Check that we deal with an "algorithm methods" from this point onward.
359 SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method) &&
360 (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));
361
362 if (!source.addr() || source.colorType() != kN32_SkColorType)
363 return SkBitmap();
364
365 ResizeFilter filter(method, source.width(), source.height(),
366 dest_width, dest_height, dest_subset);
367
368 // Get a source bitmap encompassing this touched area. We construct the
369 // offsets and row strides such that it looks like a new bitmap, while
370 // referring to the old data.
371 const uint8_t* source_subset =
372 reinterpret_cast<const uint8_t*>(source.addr());
373
374 // Convolve into the result.
375 SkBitmap result;
376 result.setInfo(
377 source.info().makeWH(dest_subset.width(), dest_subset.height()));
378 result.allocPixels(allocator);
379 if (!result.readyToDraw())
380 return SkBitmap();
381
382 BGRAConvolve2D(source_subset, static_cast<int>(source.rowBytes()),
383 !source.isOpaque(), filter.x_filter(), filter.y_filter(),
384 static_cast<int>(result.rowBytes()),
385 static_cast<unsigned char*>(result.getPixels()),
386 true);
387
388 base::TimeDelta delta = base::TimeTicks::Now() - resize_start;
389 UMA_HISTOGRAM_TIMES("Image.ResampleMS", delta);
390
391 return result;
392 }
393
394 // static
Resize(const SkBitmap & source,ResizeMethod method,int dest_width,int dest_height,const SkIRect & dest_subset,SkBitmap::Allocator * allocator)395 SkBitmap ImageOperations::Resize(const SkBitmap& source,
396 ResizeMethod method,
397 int dest_width,
398 int dest_height,
399 const SkIRect& dest_subset,
400 SkBitmap::Allocator* allocator) {
401 SkPixmap pixmap;
402 if (!source.peekPixels(&pixmap))
403 return SkBitmap();
404 return Resize(pixmap, method, dest_width, dest_height, dest_subset,
405 allocator);
406 }
407
408 // static
Resize(const SkBitmap & source,ResizeMethod method,int dest_width,int dest_height,SkBitmap::Allocator * allocator)409 SkBitmap ImageOperations::Resize(const SkBitmap& source,
410 ResizeMethod method,
411 int dest_width, int dest_height,
412 SkBitmap::Allocator* allocator) {
413 SkIRect dest_subset = { 0, 0, dest_width, dest_height };
414 return Resize(source, method, dest_width, dest_height, dest_subset,
415 allocator);
416 }
417
418 } // namespace skia
419