Rapid Computation of Fourier Texture Descriptors

Steven L. Tanimoto U-157

The University of Connecticut Storrs, CT. 06268

ABSTRACT

Computer vision systems based on general pur­ pose computers often need efficient texture des­ cription algorithms . One common method is to cal­ culate two-dimensional discrete Fourier transforms over windowed regions of the light intensity ma­ trix. Although these methods described in the literature are based on the fast Fourier transform algorithm, the computation time is still too high to permit the description of texture for as many windows as are needed for good segmentation . When a set of transforms over a window at every position of the matrix is needed, an efficient method can be used. It saves information computed for previous windows and uses it to reduce the effort expended on the current window. For a window N x N and an image matrix M x M, the time complexity is reduced from O(N 2 M 2 logN) to O(N 2 M 2 ). This complexity can­ not be beaten by any nonparallel algorithm.

I. INTRODUCTION

One of the more elusive problems in machine Vision is the characterization of visual texture and the use of texture as a perceptual cue (Bajcsy 1973A). Texture has alternatively been defined in terms of impressionistic qualities, sur­ face microstructure, and statistical properties of surface functions. A class of methods for mea­ suring texture uses the two-dimensional Fourier transform computed over local windows of a digital picture (Bajcsy 1973B) followed by some other pro­ cessing. Although some of these methods have been shown reasonable and useful for segmentation into regions according to texture, the large amount of computation involved in transforming the windows has inhibited these methods ' use. Here it is shown how the effort required to transform all the local windows of a picture can be reduced by a significant factor. By taking advantage of this technique one can afford to compute a texture descriptor for each pixel rather than only each block of a partition; thus one can achieve finely­ resolved segmentations on the basis of texture (for a related study see Pavlidis & Tanimoto 1975).

I.I. UPDATING A DISCRETE FOURIER TRANSFORM

Halberstein (1966) showed how one could per­ form a useful updating process on a discrete Fourier transform in linear time (instead of N log N time to recompute from scratch). The problem is stated as follows. Let

f 0 , f 1 , ... ,fi, ... be an

infinite sequence of complex numbers. We desire to compute F[f 0 , f 1 , ... , fN_ 1 J, then

This updating formula is now extended for two-dimensional Fourier transforms. Let the pic­ ture function be described by the values f p,q Let F indicate the matrix whose values are the p,q NxN two-dimensional Fourier transform of the NxN window starting at row p, column q . Let a be s,t the s,t th coefficient ofF - p,q and let b t be the s' Then we have: th coefficient of F 1 p,q+ s,t

A symmetrically similar equation can be used to in­ crement p instead of q. It should be noted that the summation in the above expression is a dis­ crete Fourier transform of the difference vector between the "incoming" and "outgoing" columns and need only be computed once for the entire window 's update. The cost of that N lo~ N operation is small in comparison with the N multiplications needed to "shift the basis vectors". Thus O(N2) operations are required to update the transform of a window moved one row or column.

An algorithm for computing the two-dimen­ sional DFT on all NxN windows of an MxM picture has been devised using the technique described here (Tanimoto 1977). Assuming N is much smaller than M, the algorithm requires O(N2M2) complex multi ­ plications, saving a factor of log N.

Acknowledgement

The support ofT . Pavlidis and NSF Grants ENG72-04133-A01 and ENG76-09924 is gratefully appreciated.