Abstract

We discuss the problem of how to determine whether two patterns are identical up to some rotation. Much work on this topic in machine vision relies on first-order correlation procedures to determine the magnitudes of the angular-frequency components in the patterns. Because phase information at each frequency is ignored, such strategies identify patterns that are not related by a rotation. How can we capture this phase information, which is needed for fully rotation-invariant recognition? Generalized autocorrelation functions¹ provide increasingly more information about relative phases at each angular frequency as the order of the generalized autocorrelation is increased. We examine the conditions on image patterns under which nth-order autocorrelation functions can be used for fully rotation-invariant recognition. The results show that for many applications fully rotation-invariant recognition can be achieved only through generalized correlation procedures that are computationally intractable. We show that this difficulty in capturing the rotation-invariant aspects of patterns extends to many groups of transformations of interest in vision research that have as a subgroup the group SO(2) of rotations.

© 1990 Optical Society of America