Introduction
In this 1984 paper from the AAAI proceedings, Tod S. Levitt presents a foundational approach to computer vision: enabling machines to perceive objects not merely as clouds of points, but as collections of meaningful, symmetric parts. This work addresses the challenge of autonomous decomposition—how a machine can identify where one part ends and another begins without pre-programmed object models. By quantifying symmetry through group theory and optimizing a "goodness of figure" metric, Levitt proposes a method that aligns machine perception with human Gestalt principles.
Methodology
The author treats objects as point sets in Euclidean n-space ($E^n$) and introduces a framework based on three core components:
1. Quantifying Symmetry
Symmetry is defined mathematically using the order of the group of invariant transformations (reflections and rotations). The symmetry measure $m(S,c)$ is the reciprocal of the number of these transformations. For example, a square possesses eight invariant transformations—four rotations and four reflections—resulting in a measure of $1/8$.
2. The Evaluation Function ($E$)
To prevent the algorithm from over-segmenting objects into infinite, perfectly symmetric points, Levitt introduces a cost function. This function balances the number of parts ($k$) against the symmetry of each part. The goal is to find a decomposition that minimizes the total cost while maximizing the regularity of the identified components.
3. The Decomposition Algorithm
The algorithm utilizes a Hough Transform to identify potential axes of reflection by analyzing the midpoints of all pairs of points in a set. These axes are then clustered to identify rotations. Finally, a "lumping" criterion is applied to sequentially combine subsets until an optimal decomposition is reached in polynomial time ($O(N^8)$ worst-case).
Key Insights and Results
- Symmetry as Semantic Meaning: The core philosophical leap is that local symmetry serves as a proxy for "part-ness." If a subset of points is highly symmetric, it likely represents a distinct component of the object.
- Gestalt Alignment: The paper provides a mathematical basis for the Gestalt concept of "goodness of figure," showing that the algorithm's outputs match how humans naturally decompose shapes in psychological experiments.
- Domain Independence: Because the method relies on geometry rather than a library of known shapes (like "car" or "chair"), it is theoretically applicable to any spatial data, including CAD models and 3D sensor scans.
- Optimality of Regular Polygons: Levitt demonstrates that a decomposition into regular polygons is mathematically superior to one without them under the proposed evaluation metric.
Limitations and Future Work
While groundbreaking, the approach has limitations. The $O(N^8)$ complexity, though polynomial, is computationally intensive for large datasets. Furthermore, the algorithm is sensitive to noise, as it relies on exact midpoints and reflections. Future work suggested by the author includes adjusting quantization cells in the Hough transform to handle sensor error and extending the 2D logic to 3D planes of symmetry.
Summary updated