Box/sync filtering does NOT require the transform to be axis-aligned.
The ideal/slow solution is this:
- The inverse transform is used to map the *corners* of the output pixel
back to the input image space. This defines a quadrilateral in the input
image. If perspective transforms are not allowed this quad will be the
same shape for every output pixel, but it will be translated by
non-integer amounts.
- This quadrilateral is used to scale and distort a filtering pattern.
There is no ideal filtering pattern, but it's cross-section will
resemble this, where the quad itself is from -.5 to +.5:
_
/ \
__ / \ __
------/--\--/-----\--/--\------------------
\/ \/
-3 -2 -1 0 1 2 3
This is the sinc function. The integers are NOT pixels, but measured
in the size of the quadrilateral. Also notice that this is not zero at
the edges of the quad. It is zero at +/-1 (and all higher integers).
Also note that it is infinitely large. The actual function is
sin(pi*x)/(pi*x). The filter must integrate over it's entire range to 1.0.
- The source image is multiplied by this filter, and the integral of the
entire result is the output pixel.
Okay, now here is how you get this to speed up:
- The quad is transformed to the closest axis-aligned rectangle *with
the same area*. For non-perspective transforms the size of the rectangle
can be figured out once from the transform matrix. This is only bad for
extreme skews of the image.
- You only have to multiply an input pixel by the value of the filter
exactly in the middle of it. This is reasonably close to the integral of
the filter over the entire pixel.
- The filter is made the multiplication of two 1-d filters that are
axis-aligned. This allows two-pass filtering.
- The filter is vastly simplified.
- "sinc" filters are usually the above function multiplied by
something that goes to zero at +/- 2 or 3.
- "triangle" filters are similar to the sinc truncated at 1, they are
1-abs(x) and 0 outside +/-1.
- "box" filters are 1 from -.5 to +.5 and 0 everywhere else. This is
the approach I recommend because it is by far the fastest and the
quality is quite good.
- When scaling up the quad is, in effect, enlarged to be at least 1 unit
in size. This will make the box filter identical to bilinear filtering
for any scales >= 1. (however OS/X does not do this, the result is that
the pixels in the source image turn into large anti-aliased squares, and
many users prefer this).
- If you want anything more complex than box, you pre-compute the values
of the filter at the center of pixels for a number of filter sizes and
also a number of fractional offsets of these pixel sizes, putting the
results in a table. The back-transform is rounded to the nearest entry
in the table to find the filter. To keep the table reasonable size, I
would switch to a box filter for any scales larger than 4 or so.
_______________________________________________
Pixman mailing list
Pixman@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman
