A transform method for fast generalized image registration

We present an image transform and show that it is useful for fast generalized image registration. In particular, for an image of size N pixels, this transform takes O(N) additions/subtractions and O(N₁) multiplications, where N₁ is the bigger of the image height and width (and equals N¹2/ for a square image) - it is much faster than the FFT. Unlike FFT, whose speed depends on how the image size is factored, this transform has no such limit. Furthermore, for any invertible linear transform, including rotation, reflection, scaling, plus any translation, this transform can be used to match an image with its thus transformed image without any interpolation and with the above mentioned complexity. This transform can be applied naturally to signals of any dimension. Experiments show the advantages of this method.