Space-Variant Fourier Analysis: The Exponential Chirp Transform

Space-variant sensing is the architectural basis of all higher vertebrate visual systems (Schwartz, 1994). One evident motivation for this is that the space-complexity of the human visual system is reduced by up to four orders of magnitude (Rojer and Schwartz, 1990) via the use of space-variant architecture (for a given ratio offield width to maximum resolution). This observation has obvious practical advantages for application in machine vision. Unfortunately, the practical application of space-variant image architectures is obstructed by the difficulty of performing common image processing operations in a domain of varying pixel size and connectivity. Despite some recent progress in this area (e.g. see (Wallace et al., 1994)) it has so far been impossible to apply familiar frequency domain image processing techniques directly to space-variant images. In this paper we focus on a particular space-variant map, the log-polar map, which has been shown to model the primate visual system and which has been applied to machine vision contexts by a number of investigators during the past two decades. Associated with the log-polar map is an exponential chirp transform which allows frequency domain estimation in the log-polar plane, while preserving an aspect of the shift-invariant properties of the usual Fourier transform. (Note that the familiar Mellin transform, which is a Fourier transform applied to the log polar FREQUENCY domain, is a related, but very different approach. Specifically, the Mellin transform is a shift-invariant form of image processing which, per se, has absolutely nothing to do with foveal vision). We demonstrate application of the exponential chirp with several simple template matching examples, and show that aspects of shift, size and rotation invariance are provided, while still preserving the underlying space-variant architecture of the sensor. We describe three different algorithms for computing the exponential chirp transform of an image. Somewhat surprisingly, we show that by combining the exponential chirp with the Mellin transform, it is possible to evaluate the exponential chirp transform with the same computational complexity as the FFT. Thus, the favorable space-complexity of the log-polar architecture may be joined with the computational complexity of the FIT. Moreover, the favorable sytnmetry properties of the Mellin transform and log-polar mapping are combined, using the methods of this paper, with a foveal image architecture, to provide a form of invariant template matching (using frequency domain convolution) at rates which are several orders of magnitude faster than is possible with conventional space-invariant image formats. We suggest that the methods outlined in this paper provide a practical means of performing machine vision on log-polar image formats.Office of Naval Research (N00014-92-C-0119