3-D OBJECT RECOGNITION USING BIPARTITE MATCHING EMBEDDED IN DISCRETE RELAXATION

被引:68
作者
KIM, WY [1 ]
KAK, AC [1 ]
机构
[1] PURDUE UNIV, ROBOT VIS LAB, W LAFAYETTE, IN 47907 USA
关键词
ARTIFICIAL INTELLIGENCE; AUTOMATIC SCENE INTERPRETATION; BIPARTITE GRAPH MATCHING; COMPUTER VISION; DISCRETE RELAXATION; MACHINE INTELLIGENCE; ROBOT VISION; SENSOR-BASED ROBOTICS; STRUCTURED-LIGHT VISION; 3-D VISION;
D O I
10.1109/34.75511
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
In this paper we show how large efficiencies can be achieved in model-based 3-D vision by combining the notions of discrete relaxation and bipartite matching. The computational approach we present is empirically interesting and capable of pruning large segments of search space-an indispensable step when the number of objects in the model library is large and when recognition of complex objects with a large number of surfaces is called for. We use bipartite matching for quick wholesale rejection of inapplicable models. We also use bipartite matching for implementing one of the key steps of discrete relaxation: the determination of compatibility of a scene surface with a potential model surface taking into account relational considerations. While we are able to provide the time complexity function associated with those aspects of the procedure that are implemented via bipartite matching, we are not able to do so for the interative elements of the discrete relaxation computations. In defense of our claim regarding computational efficiencies of the method presented here, all we can say is that our algorithms do not take more than a couple of iterations even for objects with more than 30 surfaces.
引用
收藏
页码:224 / 281
页数:58
相关论文
共 45 条
[1]   LEAST-SQUARES FITTING OF 2 3-D POINT SETS [J].
ARUN, KS ;
HUANG, TS ;
BLOSTEIN, SD .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1987, 9 (05) :699-700
[2]  
BHANU B, 1984, IEEE T PATTERN ANAL, V6
[3]   3DPO - A 3-DIMENSIONAL PART ORIENTATION SYSTEM [J].
BOLLES, RC ;
HORAUD, P .
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1986, 5 (03) :3-26
[4]  
BONDY JA, 1982, GRAPH THEORY APPLICA
[5]   A ROBOT VISION SYSTEM FOR RECOGNIZING 3-D OBJECTS IN LOW-ORDER POLYNOMIAL-TIME [J].
CHEN, CH ;
KAK, AC .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1989, 19 (06) :1535-1563
[6]  
CHEN CH, 1988, 8848 PURD U DEP EL E
[7]  
DEO N, 1974, GRAPH THEORY APPLICA, P314
[8]   THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].
EDMONDS, J ;
KARP, RM .
JOURNAL OF THE ACM, 1972, 19 (02) :248-&
[9]  
FAN TJ, 1988, 2ND INT C COMP VIS
[10]   THE REPRESENTATION, RECOGNITION, AND LOCATING OF 3-D OBJECTS [J].
FAUGERAS, OD ;
HEBERT, M .
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 1986, 5 (03) :27-52