[Pixman] Image resampling [PATCH 0/6]

[Søren Sandmann]

Hi,

Reviewing the supersampling patch here:

   http://cgit.freedesktop.org/~ajohnson/pixman/log/?h=supersampling

I wasn't happy with either the performance and image quality, and I
realized that the whole supersampling approach just isn't going to
fly. Since I told people to do it that way, I apologize for that. The
approach advocated by Bill Spitzak in the various downsampling threads
of computing a convolution kernel up front, is the much better way to
go. To make up for being misleading, the following patches implement
comprehensive support for high-quality image scaling filters.

Pixman already has a convolution filter, but since it only allows one
sample per pixel of the filter, it is limited in the quality that it can
support, so the following patches (to be applied on top of the three
rounding patches) add a new filter type
    
    PIXMAN_FILTER_SEPARABLE_CONVOLUTION

that supports multiple different convolution matrices that are chosen
between based on the subpixel source location. The matrices are
specified as tensor products of x/y vectors, which makes them
separable by definition.

The patches also add a helper function

    pixman_filter_create_separable_convolution()

that will create the parameters for the filter based on scaling
factors, filter kernels and subsampling resolution. Currently the
supported kernels are impulse, box, linear, cubic
(Mitchell-Netravali), lanczos2, lanczos3, lanczos3_stretched
(aka. Blinn's 'Nice' filter), and Gaussian.

There also a new demo program "demos/scale" that shows how
the new API can be used.

For some useful math regarding image transformations, see
http://people.redhat.com/otaylor/gtk/pixbuf-transform-math.ps . For
some informatino about how to compute the convolution matrices, see
the additions to rounding.txt in the second patch.


-=- Adding support to cairo and further work

Once these patches have landed in Pixman, support will have to be
added to cairo to make use of them. How to do that exactly requires
figuring out what new API to offer, and how the tradeoffs between
performance and quality should be made. This is not something that I
personally plan to work on anytime soon, except to make three notes:

  - While transformations that are not pure scalings will not
    generally result in a separable filter, OK-looking results for
    non-scalings can be achieved by using scaling factors based on the
    bounding box of a transformation 

  - For equivalent quality to GdkPixbuf do this: In each direction
    compute the scaling factors and then, if the scaling factor is
    less than 1 (ie., a downscaling), use PIXMAN_KERNEL_BOX for both
    reconstruction and sampling, and if it's greater than one, use
    PIXMAN_KERNEL_LINEAR for reconstruction and PIXMAN_KERNEL_IMPULSE
    for sampling.

  - If PIXMAN_KERNEL_GAUSSIAN is used with large downscaling factors
    and the resulting filter is then used with an identity transform,
    the result is a Gaussian blur, which is a feature that has
    sometimes been requested.

The code in demos/scale.c may be useful as an example.


-=- Further work and examples

There is some additional work that could be done:

- Performance improvements. Low-hanging fruit includes adding new fast
  path iterators that assume the source is a8r8g8b8 or r5g6b5. Higher
  hanging fruit is SIMD optimziations and implementations that take
  advantage of separability. It may also be interesting to speed up
  pixman_filter_create_separable_convolution() by tabularizing some of
  the trigonometric functions etc.

- A non-separable, but subsampled, convolution filter type could be
  interesting to allow correct filters for non-scaling transformations
  and non-separable filters in general.


As a reward for reading this entire mail, here are some images:

Original (2.6 MB):

         http://www.daimi.au.dk/~sandmann/house.jpg

Scaled down 12.9 times in each dimension:

- With a box filter:

           http://www.daimi.au.dk/~sandmann/house-box.png

- With Lanczos3:

           http://www.daimi.au.dk/~sandmann/house-lanczos3.png

- With stretched Lanczos3:

           http://www.daimi.au.dk/~sandmann/house-nice.png

For more examples, try demos/scale.

The patch series is also available in this repository:

    http://cgit.freedesktop.org/~sandmann/pixman/log/?h=separable


Soren