[cairo] [RFC] high-quality pixman image downscaling

[Bill Spitzak]

Jeff Muizelaar wrote:
> I've added the cairo list back to the cc.
> 
> On Mon, Jul 06, 2009 at 07:15:43PM -0700, Bill Spitzak wrote:
>> Jeff Muizelaar wrote:
>>
>>>> The api you designed does not allow an arbitrary integer division to be 
>>>> specified as you can only do original_width/integer values and thus the 
>>>> only integer scales allowed are factors of both the width and height. I 
>>>> would change this to a pair of integers (the scale is then 1/x,1/y, and 
>>>> there is certainly no rounding problems).
>>> I don't understand this comment. The scaled size is specified by
>>> scaled_width/scaled_height. What limitations does this have?
>> It cannot specify an integer scale that is not a divisor of the original 
>> size. The nearest integer scale is not likely to be a divisor of the 
>> image width and height.
> 
> I understand what you mean now. Can you explain what the advantage of
> this would be?

I figured it had to be an integer scale in order to get a fast 
implementation. Your idea of alternating two different integer-sized 
scales sounds like an interesting alternative that I had not thought of, 
however.

I think alternating two integer box filters is going to produce some 
annoying artifacts, especially when the scale is between 1 and 2. But I 
am not sure if it will be worse than the artifacts introduced when the 
box filter output is linear-interpolated to make the finale image.

 From a mathematical point of view it seems easier to choose the nearest 
integer scale figured out from the CTM. Any artifacts would be the same 
for a given CTM no matter how the source image is cropped, while if the 
destination is integer-sized then the artifacts will change depending on 
the original's dimensions.

> Currently the scaling code is designed around scaling to
> an integer number of pixels. The plan for scaling to an integer scale
> that is not a divisor would be to go through the two pass algorithm.
> i.e. scale to the nearest integer number of pixels and then resample
> that to desired size.

This sounds the same as what I was thinking of, though I always saw 
"interger scale" as being a scale factor of 1/N where N is an integer.
> 
>>>> A big problem is edge repeat. To allow algorithims like you are 
>>>> suggesting requires "repeat" handling of the edges of all images ALL THE 
>>>> TIME.
>>> Only the lanczos algorithm requires any edge handling. Currently, the
>>> code truncates the filter and therefor will not sample outside of the
>>> image.
>> I think there may be some confusion on either my or your part, as the 
>> need to handle box filters that extend outside the source image, and the 
>> need to handle scale factors that don't evenly divide the size of the 
>> image, are related.
> 
> The current box filters never extend outside the source image. Scale
> factors that don't evenly divide the size of the image are handled by
> two different strategies:
> 1) the box filter size alternates between two integer values such that
> there is no extension

This is an interesting idea that I had not thought of. It won't really 
alternate but it is fairly easy to choose which of two sizes to use 
interatively as you progress across the image. I would be very worried 
about artifacts such as diagonal lines looking crooked, though I am not 
sure if they are worse than the ones introduced by the linear 
interpolation step.

> 2) the box filter size is not an integer

This would be much much slower than an integer sized box filter, as one 
pixel contributes to two output pixels.

>> I suspect that removing the need to decide what type of padding is being 
>> done by the sampling will make it more efficient and thus a good first step.
> 
> We still need to support the different other repeat types so removing
> REPEAT_NONE doesn't help much. Doing the clip efficiently is probably
> the more interesting part.

The other repeat types can be successfully simulated, IMHO, though I 
have not done enough testing of this:

The actual source area scaled down would be larger than the image, with 
the correct repeat type applied to it. The image size would be rounded 
up to a multiple of the integer scale factor, and the rectangle 
positioned so that the center of one pixel on all edges of the output 
image lies outside or on the edge of the source image.

This would allow the center of all final output pixels to lie between 
two pixels of the intermediate image and make the linear interpolation 
easy with no edge cases to worry about.

When repeat-tiling it would produce an aliased line between the tiles as 
it selected between the left and right versions of the image. However 
these two locations would already be strongly blended together into the 
same value so this should not be visible.

Mirror tiling should work perfectly with this.

Repeat-outside for perfect results would require a larger intermediate 
image such that the outermost pixels are entirely sampled from outside 
the source. But the error only exists more than 1 intermediate pixel 
from the edge and I think the incorrect version (where all the sides are 
blended into each other) may be less objectionable than the correct version.

Black-outside would "work" but would *require* a full outside pixel, 
just like perfect repeat-outside would. Certainly blending any color 
into the outside samples would be obviously wrong so it cannot cheat 
like the repeat-outside version. Besides users want sharp black outside 
edges so I think it is pointless to even continue to consider it a 
filtering option and the best thing to do would be to eradicate it from 
the low-level code.