Unifying and generalizing spatial transformation

(Edit 2008-01-14: updated formatting.)

I’m trying out an idea I had a while back for unifying and generalizing different notions of spatial transformation in Pan (and spatial & temporal transformation in Fran. The three notions are transforming a point, an image (which is a function from point to alpha), and an image filter (which is a function from image to image). A basic “transform” is a function from points to points. To transform a point, just apply the function. To transform an image, inversely transform the points fed into the image. To transform a filter, inversely transform the source image and forward transform the result image.

type VectorE       = (DoubleE,DoubleE)
type PointE        = (DoubleE, DoubleE)
type Image c       = PointE -> c
type HyperFilter c = Filter c -> Filter c

Then for instance, scaling has these three variants:

scaleP :: VectorE -> TransformE
scaleP (sx,sy) = \ (x,y) -> (sx * x, sy * y)

scale :: VectorE -> Filter c
scale (sx,sy) = (. scaleP (1/sx, 1/sy))

atScale :: VectorE -> HyperFilter c
atScale (sx,sy) xf =
  scale (sx,sy) . xf . scale(1/sx,1/sy)

Hyperfilters allow some beautifully modular formulations of filters.

Note how in scale and atScale, I’m inverting the scaling. Exactly this pattern of inversion happens for other types of transformations as well (translation, rotation, swirl, etc). The new idea is to capture this inversion pattern once in a general rule for transforming functions. A type class specifies types that can be spatially transformed, which is direct for points, a do-nothing for numbers and booleans, distributes over tupling, and works similarly to atScale above for functions. To make this fly, I’m changing my representation of points and vectors from pairs to data types, which makes the code less succinct but is more strongly typed.

There’s a big catch in this plan: I only know how to handle invertible transformations, which rules out, e.g., tiling.

Here’s the class of transformable values:

class ITrans a where
  iTrans :: ITransformE -> a -> a

and the handling of functions:

instance (ITrans a, ITrans b) => ITrans (a->b) where
iTrans xf f = iTrans xf . f . iTrans (invIT xf)

The type of invertible transforms simply has a pair of transforms:

data ITransformE =
  ITransformE { itForward  :: TransformE
              , itBackward :: TransformE }

invIT :: ITransformE -> ITransformE
invIT (ITransformE forw back) = ITransformE back forw

Besides doing what I already do more uniformly, this generalized approach to transformation should be just the thing for interactive images, which may be neatly formulated again, as functions.

Leave a comment