Noncombinatorial detection of regular repetitions under perspective skew

We present a geometric framework for the efficient detection of regular repetitions of planar (but not necessarily coplanar) patterns. At the heart of our system, lie the fixed structures of the transformations that describe these regular configurations. The approach detects a number of symmetric configurations that have traditionally been dealt with separately, in that all configurations corresponding to planar homologies are detected. These include important cases such as periodicities, mirror symmetries, and reflections about a point. The approach can handle perspective distortions. It avoids to get trapped in combinatorics; through invariant-based hashing for pattern matching and through Hough transforms for the detection of fixed structures. Additional efficiency and robustness are obtained from the system's ability to "reason" about the consistency of multiple homologies. The performance of the system is demonstrated with several examples.