The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes

Grant ID: #F33615-86-C-5-38

Text Reference

James L. Crowley and Richard M. Stern, "Fast Computation of the Difference of Low-Pass Transform," tech. report CMU-RI-TR-82-18, Robotics Institute, Carnegie Mellon University, November, 1982

BibTeX Reference

@techreport{Crowley_1982_47,
   author = "James L Crowley and Richard M. Stern",
   title = "Fast Computation of the Difference of Low-Pass Transform",
   booktitle = "",
   institution = "Robotics Institute",
   month = "November",
   year = "1982",
   number= "CMU-RI-TR-82-18",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu