Exact Area Box Filtering

I have been investigating the possibility of implementing exact area
box filtering in GEGL. Specifically, I would like to build a sampler
that behaves like exact area box filtering when downsampling but also
behaves reasonably when performing other transformations.

The basic idea is to average the piecewise constant "nearest
neighbour" surface on the smallest rectangle (width and height at
least 1) that contains the pull-back (inverse image, anti-image) of an
"output" pixel area by the inverse Jacobian (approximated if needed).

The main issues are:

1) Averaging over a region too large for the usual 64x128 tile.

If we downsample by a significant amount, the region to average over
may be larger than the size of a tile. This could be solved by either
calling gegl_sampler_get_ptr () repeatedly with a large, constant
footprint, or by devising a system to change the footprint on a
pixel-by-pixel basis. The latter solution just involves modifying
context_rect on the fly, which should be feasible.

2) Passing the four numbers which define (an approximation of) the
inverse Jacobian to the sampler from the operation which calls it.

I see that there are create_matrix () methods that seem to construct a
Jacobian for various affine transformations. The proposed method would
require the inverse Jacobian instead, which may require some changes
to the API. Since more complex warping may also make use of this
feature in the future, would it be acceptable to add methods to
support this?

3) Is there already code which does this?

I have noticed that resample_boxfilter_u8 seems to do something
related. How similar is this code and Is there too much overlap for
this project to be worthwhile?

I would appreciate any feedback or help that anyone can provide.



Adam Turcotte

> The basic idea is to average the piecewise constant "nearest
> neighbour" surface on the smallest rectangle (width and height at
> least 1) that contains the pull-back (inverse image, anti-image) of an
> "output" pixel area by the inverse Jacobian (approximated if needed).

An alternative is to pull back an output pixel area with a modified
inverse Jacobian set so that that its singular values are all at least
1, and then find the smallest rectangle which contains the
pull-back. This is somewhat related to what Craig DeForest has done in
PDL::transform (sp?). (You may also modify the Jacobian so that its
singular values are at most 1: no difference really in the final
result.)

I have an honour thesis student (Chantal Racette) trying to figure out
which approach is best. It is not really important to figure out now
which one is best because once the code is written for one approach,
it would be fairly easy to set it up for the other. (2x2 SVD's are not
really a big deal.)

Because the smallest rectangle is exactly the pull back when doing
straight downsampling, the method boils down to exact area box
filtering when downsizing images (e.g., thumbnail production). For
transformations which don't map axes to axes (most rotations, shear,
warp), the rectangle ends up being larger, which is a good thing
because aliasing is generally more pronounced.

Nicolas Robidoux
Laurentian University