Fast Computation of the Difference of Low-Pass Transform

Abstract

This paper defines the Difference of Low-Pass (DOLP) transform and describes a fast algorithm for its computation. The DOLP is a reversible transform which converts an image into a set of band-pass images. A DOLP transform is shown to require O(N2) multiplies and produce O(N Log(N)) samples from an N sample image. When Gaussian low-pass filters are used, the result is a set of images which have been convolved with difference of Gaussian ( DOG) filters from an exponential set of sizes. A fast computation technique based on "resampling" is described and shown to reduce the DOLP transform complexity to O(N Log(N)) multiplies and O(N) storage locations. A second technique, "cascaded convolution with expansion", is then defined and also shown to reduce the computational cost to O(N Log(N)) multiplies. Combining these two techniques yields an algorithm for a DOLP transform that requires O(N) storage cells and requires O(N) multiplies. The DOLP transform provides a basis for a structural description of gray-scale shape. Descriptions of shape in this representation may be matched efficiently to descriptions of shape from other images to determine motion or stereo correspondence. Such descriptions may also be matched independent of their size or image plane orientation.