Geometric Reasoning for Recognition of Three-Dimensional Object Features

M. Marefat, R. L. Kashyap

Research output: Contribution to journalArticlepeer-review

169 Scopus citations


A method for extracting manufacturing shape features from the boundary representation of a polyhedral object is presented. In this approach, the depressions of the part are represented as cavity graphs, which are in turn used as a basis for hypothesis generation-elimination. The proposed cavity graphs are an extended representation in which the links reflect the concavity of the intersection between two faces, and the node labels reflect the relative orientation of the faces comprising the depression. The hypotheses are generated by decomposition of the cavity graphs into maximal constituents. The incorrect hypotheses are eliminated by rule-based experts which can discard a hypothesis or opportunistically improve and propose it for reexamination. Emphasis is put on automatic analysis of depressions which are formed by the interactions of primitive features because previous methods have limited success in handling interactions. It is shown that although there is a unique subgraph for each primitive feature, every cavity graph does not correspond to a unique set of primitive features. Consequently, since the cavity graph of a depression may not be the union of the representations for the involved primitives, we introduce the concept of virtual links for the formal analysis of the depressions based on cavity graphs. Finally, a suitable method for automatic determination of the virtual links is presented. This method is based on combining topologic and geometric evidences, and uses a combination of Dempster-Shafer decision theory and clustering techniques to reach its conclusions. Experimental results for a number of examples, which are not correctly analyzed by previous systems, are presented throughout the paper, and implementation details are discussed.

Original languageEnglish (US)
Pages (from-to)949-965
Number of pages17
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number10
StatePublished - Oct 1990


  • Artificial intelligence
  • computational geometry
  • computer-aided design
  • feature extraction
  • geometric modeling
  • manufacturing automation
  • matching
  • pattern recognition
  • shape classification
  • uncertainty reasoning

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Geometric Reasoning for Recognition of Three-Dimensional Object Features'. Together they form a unique fingerprint.

Cite this