fmw42 wrote:How do you define "filter space" and how to you get your pixels into that space?
The term is a bit loose, because of the fact that we don't scale distances to a [0, 1] range but a [0, support] range.
That being noted, deriving filter-space depends on what coordinate frame you're defining its basis vectors relative to. Let's consider the destination frame our global coordinate frame, because the axes of filter-space are parallel to our pixel-sized-ellipse axes, which are always parallel to our destination-space xy axes. Let's also define some axis-naming terminology, borrowed loosely from texture mapping:
- x and y axes are destination-space axes (consider it screenspace)
- u and v axes are source-space axes (consider it texture space)
- s and t axes are filter-space axes (not sure if those are the best letters to use, but whatever)
The basis-vectors of source-space in destination-space terms are:
- u_axis_in_dest_space = (dx/du, dy/du)
- v_axis_in_dest_space = (dx/dv, dy/dv)
The matrix that transforms source-space column vectors to destination-space column vectors is:
- x_axis_in_source_space = (du/dx, dv/dx) in source-space
- y_axis_in_source_space = (du/dy, dv/dy) in source-space
The matrix that transforms destination-space column vectors to source-space column vectors is the inverse of the above:
Those basis vectors and matrices are based on the distortion mapping or texture mapping, depending on context. In the case of EWA, we can naively project a pixel of a given radius into an ellipse in source space using the following mapping:
pixel_radius = sqrt(2.0)/2.0
naive_ellipse_s_axis_in_source_space = x_axis_in_source_space * pixel_radius
naive_ellipse_t_axis_in_source_space = y_axis_in_source_space * pixel_radius
I believe pixel_radius = sqrt(2.0)/2.0, because this is the smallest radius ensuring there are no "gaps" between pixels in any direction. Anyway, the axes of this ellipse (from center to edge) actually form the basis vectors of a coordinate frame of their own. I'll expand upon that later, but this frame is basically just a scaled version of destination-space and of filter-space. However, this ellipse formed by the pixel size is neither the correct size for finding source samples, nor does its coordinate frame form a proper basis for filtering:
- It's only the correct size for finding overlapping samples if you're using a filter whose support = pixel_radius...which may be the case for a cylindrical box filter, but nothing else. (Box filters have an orthogonal support radius of 0.5 units in filter-space. When you're just upsizing, this means box reconstruction filters have an orthogonal support radius of 0.5 source texels, tent filters have a support radius of 1 texel, cubics and Lanczos2 have a support radius of 2 texels, Lanczos4 has a support radius of 4 texels, etc. These orthogonal support radii expand for downsizing to 0.5, 1, 2, and 4 destination pixels respectively, due to the need for a low-pass resampling filter on top of the reconstruction filter. However, in the context of searching for EWA samples within an arbitrarily oriented ellipse, the support search radius for each filter is probably (2.0 * pixel_radius) times the filter's orthogonal support radius: When we're searching for source texels along an elliptical axis that's diagonal in source-space, neighbors along this axis could be as far as sqrt(2.0) texels apart.)
- ...and even for a box filter, a support radius equal to the pixel radius is only the right size when the distortion downsizes in both dimensions. If we're upsizing along one or both axes of our ellipse, it won't be big enough to contain our minimal number of support samples. Consider a 1024x1024 final image composed of a distortion of an 8x8 source image, for instance: Most destination pixels will only project to a tiny fraction of a source pixel.
- Weighting filters assume each source sample's distance from the destination is scaled according to the support size of the filter. For instance, a cubic filter expects source samples to be distributed (as evenly as possible) through a range of [0, 2] units away from the destination. However, transforming source-space offsets to the coordinate frame of a naively calculated ellipse will not satisfy this.
For these reasons, we need to resize the ellipse to create a proper sampling area and proper basis vectors for filter-space.
Constructing the basis vectors of filter-space actually depends on the length of the above vectors (whether you're upsizing or downsizing along a given dimension).
Let support = the support radius for you're chosen filter, (e.g. support = 2 for cubic filters, support = 4 for Lanczos4 sinc)
The s and t vectors will have the following mapping:
- s_axis_in_source_space = (du/ds, dv/ds)
- t_axis_in_source_space = (du/dt, dv/dt)
...and they are computed by the following vector operations:
EDIT: I had to update those (twice now), because I had them scaled wrong originally. :p
- s_axis_in_source_space = max(x_axis_in_source_space * pixel_radius * 2.0, normalize(x_axis_in_source_space) * pixel_radius * 2.0) = max(x_axis_in_source_space * sqrt(2.0), normalize(x_axis_in_source_space) * sqrt(2.0))
- t_axis_in_source_space = max(y_axis_in_source_space * pixel_radius * 2.0, normalize(y_axis_in_source_space) * pixel_radius * 2.0) = max(y_axis_in_source_space * sqrt(2.0), normalize(y_axis_in_source_space) * sqrt(2.0))
You want each radial ellipse axis to have a length equal to the diameter of 1 destination pixel for downsizing and 1 source texel for upsizing (keeping in mind that the diagonal distances between pixels and texels could be as much as sqrt(2.0)). That's equal to the size of a tent filter. We'll scale it later to the actual filter size for finding our support samples, but the above is correct for defining the filter space basis vectors, due to the fact that filters expect samples to be within a distance of [0, support] rather than [0, 1].
The matrix that transforms filter-space column vectors to source-space column vectors is:
The matrix that transforms source-space column vectors to filter-space column vectors is the inverse of that:
(which you'd get by computing the matrix inverse of the above)
That seems like a lot of math, but it's actually rather simple: s_axis_in_source_space and t_axis_in_source_space are the basis vectors of filter-space (expressed in source-space units). They form an ellipse, but this ellipse is not the same size as a pixel. Instead, it's related to the "support ellipse" you need to search for source samples inside in the following way:
- support_ellipse_s_axis_in_source_space = s_axis_in_source_space * support = support * max(x_axis_in_source_space * sqrt(2.0), normalize(x_axis_in_source_space) * sqrt(2.0))
- support_ellipse_t_axis_in_source_space = t_axis_in_source_space * support = support * max(y_axis_in_source_space * sqrt(2.0), normalize(y_axis_in_source_space) * sqrt(2.0))
The filter-space ellipse is scaled differently from the support-finding ellipse so that when you convert the source-space offset vectors of each source sample to filter-space (see above matrix), their length will be scaled correctly to fall within a range of [0, support].
I imagine ImageMagick does some of this more implicitly than explicitly, but from what I can tell, this is the correct way to size the EWA ellipse and compute filter weights for distortions. The concept of filter-space applies to regular resizing too, except it's more trivial to derive: Filter-space corresponds to destination-space for downsizing and source-space for upsizing, on a per-axis basis. It's only more complicated for distorts because the source and destination axes aren't necessarily parallel to each other.
- Get the basis vectors of the destination frame expressed in source frame coordinates, i.e.
x_axis_in_source_space = (du/dx, dv/dx)
y_axis_in_source_space = (du/dy, dv/dy)
- Scale those axes to get the basis vectors of filter-space:
s_axis_in_source_space = max(x_axis_in_source_space * sqrt(2.0), normalize(x_axis_in_source_space) * sqrt(2.0))
t_axis_in_source_space = max(y_axis_in_source_space * sqrt(2.0), normalize(y_axis_in_source_space) * sqrt(2.0))
- Find your source samples within the area covered by an ellipse with axes:
support_ellipse_s_axis_in_source_space = s_axis_in_source_space * support
support_ellipse_t_axis_in_source_space = t_axis_in_source_space * support
- Transform source sample offset vectors into filter-space by multiplying by the inverse of the matrix formed by the [s_axis_in_source_space, t_axis_in_source_space] vectors.