Description and Recognition of Curved Objects

Ramakant Nevatia, Thomas O. BinfordArtificial Intelligence 1977 · DOI

This paper from 1977 tackles the challenging problem of describing and recognizing complex 3D objects with curved surfaces, moving beyond the simpler world of polyhedra. The authors introduce a novel approach using generalized cones to represent object parts and a structured method for segmenting and matching these representations, laying groundwork for more robust 3D scene analysis.

TL;DR

This paper presents a system for describing and recognizing 3D curved objects by segmenting them into generalized cone primitives. It introduces a method for generating symbolic descriptions and matching them against stored models, demonstrating success with articulated objects like toy animals and tools.

What Problem Does This Paper Address?

Traditional computer vision in the 1970s largely focused on analyzing 2D images or scenes composed of simple polyhedral objects. These methods often relied on global features or template matching, which proved inadequate for the complexities of real-world 3D objects. Challenges like occlusion (objects blocking each other), varying viewing angles, and articulated parts (like limbs) made it difficult to reliably identify and understand objects. The authors aimed to bridge this gap by developing techniques for analyzing scenes with curved objects, enabling machines to generate structured, symbolic descriptions that could be used for recognition.

Methods

The core of the paper lies in its representation and segmentation strategy:

  • Generalized Cones as Primitives: Objects are broken down into simpler parts, each represented as a "generalized cone." A generalized cone is defined by an axis (a space curve) and cross-sections perpendicular to the axis that can change along its length. This allows for the representation of a wide variety of shapes, especially elongated ones.
  • Segmentation via Projection: To segment an object into these generalized cones, the authors employ a projection technique. They project the object's boundary onto various planes and analyze the resulting cross-sections. By examining neighboring cross-sections and their mid-points, they can infer local cone axes.
  • Axis Refinement and Cone Extension: The initial cone axes are refined by fitting lines to axis points and recomputing cross-sections. Local cones are then extended to cover larger portions of the object, allowing for smooth changes in axis direction.
  • Choice of Segmentation: The system generates multiple potential segmentations. A selection process favors elongated and cylindrical parts, aiming for mutually compatible sub-part descriptions.
  • Symbolic Descriptions: The segmented parts and their connectivity form a symbolic description. This includes descriptions of individual parts (size, shape, type) and the relationships between them (joints).
  • Recognition via Matching: Recognition is achieved by matching the generated symbolic description of an unknown object against a database of stored model descriptions. This matching process considers scale changes, limb articulations, and partial views due to occlusion.

Datasets

The paper does not explicitly mention specific datasets used for training or evaluation. Instead, it describes experiments conducted on "five objects, a doll, a horse, a glove, a snake, and a ring," processed in "scenes of single as well as multiple objects in various orientations and with various articulations of limbs." The authors note that pictorial results are not reproduced in the paper but are available in a referenced thesis.

Key Insights and Ideas

  • Moving Beyond Polyhedra: The paper highlights the limitations of previous 3D vision work focused on polyhedra and argues for the necessity of handling curved surfaces for real-world applications.
  • Hierarchical Representation: Segmenting complex objects into simpler, generalized cone primitives allows for a hierarchical and structured representation, which is crucial for robust analysis.
  • Importance of Connectivity: The connectivity of segmented parts (forming a graph structure) is identified as a key component of the object's shape description, providing structural information beyond individual part shapes.
  • Handling Articulation and Occlusion: The proposed methods are designed to cope with articulated limbs and partial views due to occlusion, which are significant challenges in 3D vision.
  • Symbolic Matching for Recognition: The shift from raw image data to symbolic descriptions enables a more abstract and flexible matching process for recognition, allowing for variations in pose and articulation.

Key Results

The paper reports successful segmentation and recognition for scenes with multiple, occluding objects in various orientations and with articulated parts.

  • The system could discriminate well between objects of different structures (e.g., a hammer vs. a glove vs. a doll).
  • For objects with similar structures (e.g., a horse and a doll), discrimination was based on the relative sizes of parts.
  • Scenes with moderate occlusion were analyzed successfully, with performance dependent on the amount of visible structure.
  • The computer time required to process a typical scene was 5-10 minutes on a PDP-10, KA-10 processor, with much of the time spent in lower-level processing like boundary linking and segmentation.

Limitations and Future Work

The authors acknowledge several limitations and suggest avenues for future research:

  • Segmentation Imperfections: Local discontinuities in boundaries can lead to undesired splitting of parts. The need for "redescription routines" to utilize existing segmentations is highlighted.
  • Incomplete Descriptions: Models lacking information about complete cross-sections or articulation limits can hinder reliable discrimination between similar objects.
  • Uncertainty in Descriptors: Widths and lengths of parts have uncertainties, which could be reduced by redescription techniques that leverage neighboring part descriptions.
  • Verification: The paper notes that verification methods (checking differences between object and model descriptions) were not implemented but would be beneficial for choosing between alternate matches.
  • Heavy Occlusion: Cases of heavy occlusion, where little structure is visible, are not addressed and would require additional techniques for hypothesizing structures from fragmented parts.
  • Generalization: While the representation proved useful for a variety of objects, it could be strengthened by adding more primitives.
  • Indexing: The indexing scheme was a preliminary effort and could be improved with real-valued descriptors and more extensive testing with a larger model database.
  • Articulation Limits: Incorporating knowledge of limb articulation limits into models would significantly improve discrimination.

Summary updated

BibTeX
@article{nevatia1977description,
  author = {Ramakant Nevatia and Thomas O. Binford},
  title = {{Description and Recognition of Curved Objects}},
  journal = {Artificial Intelligence},
  year = {1977},
  doi = {10.1016/0004-3702(77)90006-6},
}
Figure