1 // Copyright (c) 2006-2012 The Chromium Authors. All rights reserved.
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above copyright
9 // notice, this list of conditions and the following disclaimer in
10 // the documentation and/or other materials provided with the
12 // * Neither the name of Google, Inc. nor the names of its contributors
13 // may be used to endorse or promote products derived from this
14 // software without specific prior written permission.
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
22 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
23 // OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24 // AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26 // OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 #include "base/basictypes.h"
31 #define _USE_MATH_DEFINES
36 #include "image_operations.h"
38 #include "base/stack_container.h"
39 #include "convolver.h"
40 #include "skia/SkColorPriv.h"
41 #include "skia/SkBitmap.h"
42 #include "skia/SkRect.h"
43 #include "skia/SkFontHost.h"
49 // Returns the ceiling/floor as an integer.
50 inline int CeilInt(float val
) {
51 return static_cast<int>(ceil(val
));
53 inline int FloorInt(float val
) {
54 return static_cast<int>(floor(val
));
57 // Filter function computation -------------------------------------------------
59 // Evaluates the box filter, which goes from -0.5 to +0.5.
60 float EvalBox(float x
) {
61 return (x
>= -0.5f
&& x
< 0.5f
) ? 1.0f
: 0.0f
;
64 // Evaluates the Lanczos filter of the given filter size window for the given
67 // |filter_size| is the width of the filter (the "window"), outside of which
68 // the value of the function is 0. Inside of the window, the value is the
69 // normalized sinc function:
70 // lanczos(x) = sinc(x) * sinc(x / filter_size);
72 // sinc(x) = sin(pi*x) / (pi*x);
73 float EvalLanczos(int filter_size
, float x
) {
74 if (x
<= -filter_size
|| x
>= filter_size
)
75 return 0.0f
; // Outside of the window.
76 if (x
> -std::numeric_limits
<float>::epsilon() &&
77 x
< std::numeric_limits
<float>::epsilon())
78 return 1.0f
; // Special case the discontinuity at the origin.
79 float xpi
= x
* static_cast<float>(M_PI
);
80 return (sin(xpi
) / xpi
) * // sinc(x)
81 sin(xpi
/ filter_size
) / (xpi
/ filter_size
); // sinc(x/filter_size)
84 // Evaluates the Hamming filter of the given filter size window for the given
87 // The filter covers [-filter_size, +filter_size]. Outside of this window
88 // the value of the function is 0. Inside of the window, the value is sinus
89 // cardinal multiplied by a recentered Hamming function. The traditional
90 // Hamming formula for a window of size N and n ranging in [0, N-1] is:
91 // hamming(n) = 0.54 - 0.46 * cos(2 * pi * n / (N-1)))
92 // In our case we want the function centered for x == 0 and at its minimum
93 // on both ends of the window (x == +/- filter_size), hence the adjusted
95 // hamming(x) = (0.54 -
96 // 0.46 * cos(2 * pi * (x - filter_size)/ (2 * filter_size)))
97 // = 0.54 - 0.46 * cos(pi * x / filter_size - pi)
98 // = 0.54 + 0.46 * cos(pi * x / filter_size)
99 float EvalHamming(int filter_size
, float x
) {
100 if (x
<= -filter_size
|| x
>= filter_size
)
101 return 0.0f
; // Outside of the window.
102 if (x
> -std::numeric_limits
<float>::epsilon() &&
103 x
< std::numeric_limits
<float>::epsilon())
104 return 1.0f
; // Special case the sinc discontinuity at the origin.
105 const float xpi
= x
* static_cast<float>(M_PI
);
107 return ((sin(xpi
) / xpi
) * // sinc(x)
108 (0.54f
+ 0.46f
* cos(xpi
/ filter_size
))); // hamming(x)
111 // ResizeFilter ----------------------------------------------------------------
113 // Encapsulates computation and storage of the filters required for one complete
117 ResizeFilter(ImageOperations::ResizeMethod method
,
118 int src_full_width
, int src_full_height
,
119 int dest_width
, int dest_height
,
120 const SkIRect
& dest_subset
);
122 // Returns the filled filter values.
123 const ConvolutionFilter1D
& x_filter() { return x_filter_
; }
124 const ConvolutionFilter1D
& y_filter() { return y_filter_
; }
127 // Returns the number of pixels that the filer spans, in filter space (the
128 // destination image).
129 float GetFilterSupport(float scale
) {
131 case ImageOperations::RESIZE_BOX
:
132 // The box filter just scales with the image scaling.
133 return 0.5f
; // Only want one side of the filter = /2.
134 case ImageOperations::RESIZE_HAMMING1
:
135 // The Hamming filter takes as much space in the source image in
136 // each direction as the size of the window = 1 for Hamming1.
138 case ImageOperations::RESIZE_LANCZOS2
:
139 // The Lanczos filter takes as much space in the source image in
140 // each direction as the size of the window = 2 for Lanczos2.
142 case ImageOperations::RESIZE_LANCZOS3
:
143 // The Lanczos filter takes as much space in the source image in
144 // each direction as the size of the window = 3 for Lanczos3.
151 // Computes one set of filters either horizontally or vertically. The caller
152 // will specify the "min" and "max" rather than the bottom/top and
153 // right/bottom so that the same code can be re-used in each dimension.
155 // |src_depend_lo| and |src_depend_size| gives the range for the source
156 // depend rectangle (horizontally or vertically at the caller's discretion
157 // -- see above for what this means).
159 // Likewise, the range of destination values to compute and the scale factor
160 // for the transform is also specified.
161 void ComputeFilters(int src_size
,
162 int dest_subset_lo
, int dest_subset_size
,
163 float scale
, float src_support
,
164 ConvolutionFilter1D
* output
);
166 // Computes the filter value given the coordinate in filter space.
167 inline float ComputeFilter(float pos
) {
169 case ImageOperations::RESIZE_BOX
:
171 case ImageOperations::RESIZE_HAMMING1
:
172 return EvalHamming(1, pos
);
173 case ImageOperations::RESIZE_LANCZOS2
:
174 return EvalLanczos(2, pos
);
175 case ImageOperations::RESIZE_LANCZOS3
:
176 return EvalLanczos(3, pos
);
182 ImageOperations::ResizeMethod method_
;
184 // Size of the filter support on one side only in the destination space.
185 // See GetFilterSupport.
186 float x_filter_support_
;
187 float y_filter_support_
;
189 // Subset of scaled destination bitmap to compute.
192 ConvolutionFilter1D x_filter_
;
193 ConvolutionFilter1D y_filter_
;
195 DISALLOW_COPY_AND_ASSIGN(ResizeFilter
);
198 ResizeFilter::ResizeFilter(ImageOperations::ResizeMethod method
,
199 int src_full_width
, int src_full_height
,
200 int dest_width
, int dest_height
,
201 const SkIRect
& dest_subset
)
203 out_bounds_(dest_subset
) {
204 // method_ will only ever refer to an "algorithm method".
205 SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD
<= method
) &&
206 (method
<= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD
));
208 float scale_x
= static_cast<float>(dest_width
) /
209 static_cast<float>(src_full_width
);
210 float scale_y
= static_cast<float>(dest_height
) /
211 static_cast<float>(src_full_height
);
213 x_filter_support_
= GetFilterSupport(scale_x
);
214 y_filter_support_
= GetFilterSupport(scale_y
);
216 // Support of the filter in source space.
217 float src_x_support
= x_filter_support_
/ scale_x
;
218 float src_y_support
= y_filter_support_
/ scale_y
;
220 ComputeFilters(src_full_width
, dest_subset
.fLeft
, dest_subset
.width(),
221 scale_x
, src_x_support
, &x_filter_
);
222 ComputeFilters(src_full_height
, dest_subset
.fTop
, dest_subset
.height(),
223 scale_y
, src_y_support
, &y_filter_
);
226 // TODO(egouriou): Take advantage of periods in the convolution.
227 // Practical resizing filters are periodic outside of the border area.
228 // For Lanczos, a scaling by a (reduced) factor of p/q (q pixels in the
229 // source become p pixels in the destination) will have a period of p.
230 // A nice consequence is a period of 1 when downscaling by an integral
231 // factor. Downscaling from typical display resolutions is also bound
232 // to produce interesting periods as those are chosen to have multiple
234 // Small periods reduce computational load and improve cache usage if
235 // the coefficients can be shared. For periods of 1 we can consider
236 // loading the factors only once outside the borders.
237 void ResizeFilter::ComputeFilters(int src_size
,
238 int dest_subset_lo
, int dest_subset_size
,
239 float scale
, float src_support
,
240 ConvolutionFilter1D
* output
) {
241 int dest_subset_hi
= dest_subset_lo
+ dest_subset_size
; // [lo, hi)
243 // When we're doing a magnification, the scale will be larger than one. This
244 // means the destination pixels are much smaller than the source pixels, and
245 // that the range covered by the filter won't necessarily cover any source
246 // pixel boundaries. Therefore, we use these clamped values (max of 1) for
247 // some computations.
248 float clamped_scale
= std::min(1.0f
, scale
);
250 // Speed up the divisions below by turning them into multiplies.
251 float inv_scale
= 1.0f
/ scale
;
253 StackVector
<float, 64> filter_values
;
254 StackVector
<int16_t, 64> fixed_filter_values
;
256 // Loop over all pixels in the output range. We will generate one set of
257 // filter values for each one. Those values will tell us how to blend the
258 // source pixels to compute the destination pixel.
259 for (int dest_subset_i
= dest_subset_lo
; dest_subset_i
< dest_subset_hi
;
261 // Reset the arrays. We don't declare them inside so they can re-use the
262 // same malloc-ed buffer.
263 filter_values
->clear();
264 fixed_filter_values
->clear();
266 // This is the pixel in the source directly under the pixel in the dest.
267 // Note that we base computations on the "center" of the pixels. To see
268 // why, observe that the destination pixel at coordinates (0, 0) in a 5.0x
269 // downscale should "cover" the pixels around the pixel with *its center*
270 // at coordinates (2.5, 2.5) in the source, not those around (0, 0).
271 // Hence we need to scale coordinates (0.5, 0.5), not (0, 0).
272 float src_pixel
= (static_cast<float>(dest_subset_i
) + 0.5f
) * inv_scale
;
274 // Compute the (inclusive) range of source pixels the filter covers.
275 int src_begin
= std::max(0, FloorInt(src_pixel
- src_support
));
276 int src_end
= std::min(src_size
- 1, CeilInt(src_pixel
+ src_support
));
278 // Compute the unnormalized filter value at each location of the source
280 float filter_sum
= 0.0f
; // Sub of the filter values for normalizing.
281 for (int cur_filter_pixel
= src_begin
; cur_filter_pixel
<= src_end
;
282 cur_filter_pixel
++) {
283 // Distance from the center of the filter, this is the filter coordinate
284 // in source space. We also need to consider the center of the pixel
285 // when comparing distance against 'src_pixel'. In the 5x downscale
286 // example used above the distance from the center of the filter to
287 // the pixel with coordinates (2, 2) should be 0, because its center
289 float src_filter_dist
=
290 ((static_cast<float>(cur_filter_pixel
) + 0.5f
) - src_pixel
);
292 // Since the filter really exists in dest space, map it there.
293 float dest_filter_dist
= src_filter_dist
* clamped_scale
;
295 // Compute the filter value at that location.
296 float filter_value
= ComputeFilter(dest_filter_dist
);
297 filter_values
->push_back(filter_value
);
299 filter_sum
+= filter_value
;
302 // The filter must be normalized so that we don't affect the brightness of
303 // the image. Convert to normalized fixed point.
304 int16_t fixed_sum
= 0;
305 for (size_t i
= 0; i
< filter_values
->size(); i
++) {
306 int16_t cur_fixed
= output
->FloatToFixed(filter_values
[i
] / filter_sum
);
307 fixed_sum
+= cur_fixed
;
308 fixed_filter_values
->push_back(cur_fixed
);
311 // The conversion to fixed point will leave some rounding errors, which
312 // we add back in to avoid affecting the brightness of the image. We
313 // arbitrarily add this to the center of the filter array (this won't always
314 // be the center of the filter function since it could get clipped on the
315 // edges, but it doesn't matter enough to worry about that case).
316 int16_t leftovers
= output
->FloatToFixed(1.0f
) - fixed_sum
;
317 fixed_filter_values
[fixed_filter_values
->size() / 2] += leftovers
;
319 // Now it's ready to go.
320 output
->AddFilter(src_begin
, &fixed_filter_values
[0],
321 static_cast<int>(fixed_filter_values
->size()));
324 output
->PaddingForSIMD(8);
327 ImageOperations::ResizeMethod
ResizeMethodToAlgorithmMethod(
328 ImageOperations::ResizeMethod method
) {
329 // Convert any "Quality Method" into an "Algorithm Method"
330 if (method
>= ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD
&&
331 method
<= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD
) {
334 // The call to ImageOperationsGtv::Resize() above took care of
335 // GPU-acceleration in the cases where it is possible. So now we just
336 // pick the appropriate software method for each resize quality.
338 // Users of RESIZE_GOOD are willing to trade a lot of quality to
339 // get speed, allowing the use of linear resampling to get hardware
340 // acceleration (SRB). Hence any of our "good" software filters
341 // will be acceptable, and we use the fastest one, Hamming-1.
342 case ImageOperations::RESIZE_GOOD
:
343 // Users of RESIZE_BETTER are willing to trade some quality in order
344 // to improve performance, but are guaranteed not to devolve to a linear
345 // resampling. In visual tests we see that Hamming-1 is not as good as
346 // Lanczos-2, however it is about 40% faster and Lanczos-2 itself is
347 // about 30% faster than Lanczos-3. The use of Hamming-1 has been deemed
348 // an acceptable trade-off between quality and speed.
349 case ImageOperations::RESIZE_BETTER
:
350 return ImageOperations::RESIZE_HAMMING1
;
352 return ImageOperations::RESIZE_LANCZOS3
;
358 // Resize ----------------------------------------------------------------------
361 SkBitmap
ImageOperations::Resize(const SkBitmap
& source
,
363 int dest_width
, int dest_height
,
364 const SkIRect
& dest_subset
,
365 void* dest_pixels
/* = nullptr */) {
366 if (method
== ImageOperations::RESIZE_SUBPIXEL
)
367 return ResizeSubpixel(source
, dest_width
, dest_height
, dest_subset
);
369 return ResizeBasic(source
, method
, dest_width
, dest_height
, dest_subset
,
374 SkBitmap
ImageOperations::ResizeSubpixel(const SkBitmap
& source
,
375 int dest_width
, int dest_height
,
376 const SkIRect
& dest_subset
) {
377 // Currently only works on Linux/BSD because these are the only platforms
378 // where SkFontHost::GetSubpixelOrder is defined.
380 // Understand the display.
381 const SkFontHost::LCDOrder order
= SkFontHost::GetSubpixelOrder();
382 const SkFontHost::LCDOrientation orientation
=
383 SkFontHost::GetSubpixelOrientation();
385 // Decide on which dimension, if any, to deploy subpixel rendering.
388 switch (orientation
) {
389 case SkFontHost::kHorizontal_LCDOrientation
:
390 w
= dest_width
< source
.width() ? 3 : 1;
392 case SkFontHost::kVertical_LCDOrientation
:
393 h
= dest_height
< source
.height() ? 3 : 1;
398 const int width
= dest_width
* w
;
399 const int height
= dest_height
* h
;
400 SkIRect subset
= { dest_subset
.fLeft
, dest_subset
.fTop
,
401 dest_subset
.fLeft
+ dest_subset
.width() * w
,
402 dest_subset
.fTop
+ dest_subset
.height() * h
};
403 SkBitmap img
= ResizeBasic(source
, ImageOperations::RESIZE_LANCZOS3
, width
,
405 const int row_words
= img
.rowBytes() / 4;
406 if (w
== 1 && h
== 1)
409 // Render into subpixels.
411 SkImageInfo info
= SkImageInfo::Make(dest_subset
.width(),
412 dest_subset
.height(),
413 kBGRA_8888_SkColorType
,
414 kPremul_SkAlphaType
);
417 result
.allocPixels(info
);
418 if (!result
.readyToDraw())
421 SkAutoLockPixels
locker(img
);
422 if (!img
.readyToDraw())
425 uint32_t* src_row
= img
.getAddr32(0, 0);
426 uint32_t* dst_row
= result
.getAddr32(0, 0);
427 for (int y
= 0; y
< dest_subset
.height(); y
++) {
428 uint32_t* src
= src_row
;
429 uint32_t* dst
= dst_row
;
430 for (int x
= 0; x
< dest_subset
.width(); x
++, src
+= w
, dst
++) {
431 uint8_t r
= 0, g
= 0, b
= 0, a
= 0;
433 case SkFontHost::kRGB_LCDOrder
:
434 switch (orientation
) {
435 case SkFontHost::kHorizontal_LCDOrientation
:
436 r
= SkGetPackedR32(src
[0]);
437 g
= SkGetPackedG32(src
[1]);
438 b
= SkGetPackedB32(src
[2]);
439 a
= SkGetPackedA32(src
[1]);
441 case SkFontHost::kVertical_LCDOrientation
:
442 r
= SkGetPackedR32(src
[0 * row_words
]);
443 g
= SkGetPackedG32(src
[1 * row_words
]);
444 b
= SkGetPackedB32(src
[2 * row_words
]);
445 a
= SkGetPackedA32(src
[1 * row_words
]);
449 case SkFontHost::kBGR_LCDOrder
:
450 switch (orientation
) {
451 case SkFontHost::kHorizontal_LCDOrientation
:
452 b
= SkGetPackedB32(src
[0]);
453 g
= SkGetPackedG32(src
[1]);
454 r
= SkGetPackedR32(src
[2]);
455 a
= SkGetPackedA32(src
[1]);
457 case SkFontHost::kVertical_LCDOrientation
:
458 b
= SkGetPackedB32(src
[0 * row_words
]);
459 g
= SkGetPackedG32(src
[1 * row_words
]);
460 r
= SkGetPackedR32(src
[2 * row_words
]);
461 a
= SkGetPackedA32(src
[1 * row_words
]);
465 case SkFontHost::kNONE_LCDOrder
:
468 // Premultiplied alpha is very fragile.
472 *dst
= SkPackARGB32(a
, r
, g
, b
);
474 src_row
+= h
* row_words
;
475 dst_row
+= result
.rowBytes() / 4;
477 result
.setAlphaType(img
.alphaType());
481 #endif // OS_POSIX && !OS_MACOSX && !defined(OS_ANDROID)
485 SkBitmap
ImageOperations::ResizeBasic(const SkBitmap
& source
,
487 int dest_width
, int dest_height
,
488 const SkIRect
& dest_subset
,
489 void* dest_pixels
/* = nullptr */) {
490 // Ensure that the ResizeMethod enumeration is sound.
491 SkASSERT(((RESIZE_FIRST_QUALITY_METHOD
<= method
) &&
492 (method
<= RESIZE_LAST_QUALITY_METHOD
)) ||
493 ((RESIZE_FIRST_ALGORITHM_METHOD
<= method
) &&
494 (method
<= RESIZE_LAST_ALGORITHM_METHOD
)));
496 // If the size of source or destination is 0, i.e. 0x0, 0xN or Nx0, just
498 if (source
.width() < 1 || source
.height() < 1 ||
499 dest_width
< 1 || dest_height
< 1)
502 method
= ResizeMethodToAlgorithmMethod(method
);
503 // Check that we deal with an "algorithm methods" from this point onward.
504 SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD
<= method
) &&
505 (method
<= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD
));
507 SkAutoLockPixels
locker(source
);
508 if (!source
.readyToDraw())
511 ResizeFilter
filter(method
, source
.width(), source
.height(),
512 dest_width
, dest_height
, dest_subset
);
514 // Get a source bitmap encompassing this touched area. We construct the
515 // offsets and row strides such that it looks like a new bitmap, while
516 // referring to the old data.
517 const uint8_t* source_subset
=
518 reinterpret_cast<const uint8_t*>(source
.getPixels());
520 // Convolve into the result.
522 SkImageInfo info
= SkImageInfo::Make(dest_subset
.width(),
523 dest_subset
.height(),
524 kBGRA_8888_SkColorType
,
525 kPremul_SkAlphaType
);
528 result
.installPixels(info
, dest_pixels
, info
.minRowBytes());
530 result
.allocPixels(info
);
533 if (!result
.readyToDraw())
536 BGRAConvolve2D(source_subset
, static_cast<int>(source
.rowBytes()),
537 !source
.isOpaque(), filter
.x_filter(), filter
.y_filter(),
538 static_cast<int>(result
.rowBytes()),
539 static_cast<unsigned char*>(result
.getPixels()),
542 // Preserve the "opaque" flag for use as an optimization later.
543 result
.setAlphaType(source
.alphaType());
549 SkBitmap
ImageOperations::Resize(const SkBitmap
& source
,
551 int dest_width
, int dest_height
,
552 void* dest_pixels
/* = nullptr */) {
553 SkIRect dest_subset
= { 0, 0, dest_width
, dest_height
};
554 return Resize(source
, method
, dest_width
, dest_height
, dest_subset
,