TY - JOUR
T1 - Geometric Reasoning for Recognition of Three-Dimensional Object Features
AU - Marefat, M.
AU - Kashyap, R. L.
N1 - Funding Information:
Manuscript received May l, 1989; revised March 27, 1990. Recommended for acceptance by J. L. Mundy. This work was supported in part by the National Science Foundation under Grant CDR 8803017 to the Pur-due Engineering Research Center for Intelligent Manufacturing Systems, and in part by the U.S. Army Research Office under Contract DAAL03-89K-0032. The authors are with the School of Electrical Engineering, Purdue University, West Lafayette, IN 47907. IEEE Log Number 9037575.
PY - 1990/10
Y1 - 1990/10
N2 - 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.
AB - 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.
KW - Artificial intelligence
KW - computational geometry
KW - computer-aided design
KW - feature extraction
KW - geometric modeling
KW - manufacturing automation
KW - matching
KW - pattern recognition
KW - shape classification
KW - uncertainty reasoning
UR - http://www.scopus.com/inward/record.url?scp=0025504864&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025504864&partnerID=8YFLogxK
U2 - 10.1109/34.58868
DO - 10.1109/34.58868
M3 - Article
AN - SCOPUS:0025504864
SN - 0162-8828
VL - 12
SP - 949
EP - 965
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
IS - 10
ER -