| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
3-D Object Recognition Using Bipartite Matching Embedded in Discrete Relaxation
March 1991 (vol. 13 no. 3)
pp. 224-251
The authors 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 presented is 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. Bipartite matching is used for quick wholesale rejection of inapplicable models and for the determination of compatibility of a scene surface with a potential model surface taking into account relational considerations. The time complexity function associated with those aspects of the procedure that are implemented via bipartite matching is provided. The algorithms do not take more than a couple of iterations, even for objects with more than 30 surfaces.
[1] 224K. S. Arun, T. S. Huang, and S. D. Blostein, "Least-squares fitting of two 3-D point sets,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-9, no. 5, pp. 698-700, 1987.[2] B. Bhanu, "Representation and shape matching of 3-D objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 3, May 1984.[3] R. C. Bolles and P. Horaud, "3DPO: A three dimensional part orientation svstem,"Int. J. Robotics Res., vol. 5, no. 3, Fall 1986, pp. 3-26.[4] J. A. Bondy and U.S.R. Murty,Graph Theory with Applications. New York: Elsevier, 1982.[5] C. H. Chen and A. C. Kak, "A robot vision system for recognizing 3-D objects in low-order polynomial time,"IEEE Trans. Syst., Man Cybern., vol. 19, no. 6, pp. 1535-1563, Nov./Dec. 1989.[6] C. H. Chen and A. C. Kak, "3D-POLY: A robot vision system for recognizing objects in occluded environments," Dept. Elec. Eng., Purdue Univ., West Lafayette, IN, Tech. Rep. 88-48, 1988.[7] N. Deo,Graph Theory with Applications to Engineering and Computer Science. Englewood Cliffs, NJ: Prentice-Hall, 1974, pp. 314-321.[8] J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems,"J. Ass. Comput. Mach., vol. 19, no. 2, pp. 248-264, Apr. 1972.[9] T. J. Fan, G. Medioni, and R. Nevatia, "Recognizing 3-D objects using surface descriptions," presented at the 2nd Int. Conf. Computer Vision, Dec. 5-8, 1988.[10] O. D. Faugeras, "New steps toward a flexible 3-D vision system for robotics," inProc. 2nd Int. Symp. Robotics Res., 1985.[11] O. D. Faugeras and M. Hebert, "A 3-D recognition and positioning algorithm using geometrical matching between primitive surfaces," inProc. 8th Int. Joint Conf. Artificial Intell., Aug. 1983, pp. 996-1002.[12] O. D. Faugeras and M. Hebert, "The representation, recognition, and locating of 3-D objects,"Int. J. Robotics Res., vol. 5, no. 3, Fall 1986, pp. 27-52.[13] H. N. Gabow, "An efficient implementation of Edmonds' algorithm for maximum matching on graphs,"J. Ass. Comput. Mach., vol. 23, no. 2, pp. 221-234, April 1976.[14] Z. Galil, "Efficient algorithms for finding maximum matching in graphs,"ACM Comput. Surveys, vol. 18, no. 1, March 1986.[15] W. E. L. Grimson, "On the recognition of parameterized 2D objects,"Int. J. Computer Vision, vol. 3, pp. 353-372, 1988.[16] W. E. L. Grimson, "On the recognition of curved objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 6, June 1989.[17] W. E. L. Grimson and T. Lozano-Perez, "Model-based recognition and localization from sparse range or tactile data,"Int. J. Robotics Res., vol. 3, no. 3, Fall 1984.[18] W. E. L. Grimson and T. Lozano-Perez, "Localizing overlapping parts by searching the interpretation tree,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-9, no. 4, July 1987.[19] J. Han, R. A. Volz, and T. N. Mudge, "Range image segmentation and surface parameter extraction for 3-D object recognition of industrial parts," inProc. IEEE Int. Conf. on Robotics and Automation, Mar. 31-Apr. 3, 1987, pp. 380-386.[20] R. M. Haralick and G. L. Elliott, "Increasing tree search efficiency for constraint satisfaction problems,"Artificial Intell., vol. 14, pp. 263-313, 1980.[21] R. M. Haralick and J. S. Kartus, "Arrangements, homomorphisms, and discrete relaxation,"IEEE Trans. Syst., Man Cybern., vol. SMC-8, no. 8, Aug. 1978.[22] R. M. Haralick and L. G. Shapiro, "The consistent labeling problem: Part I,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-1, no. 2, May 1979.[23] M. Hebert and T. Kanade, "The 3D-profile method for object recognition," presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recognition, San Francisco, CA, June 19-23, 1985.[24] J. E. Hopcroft and R. M. Karp, "An5/2algorithm for maximum matching in bipartite graphs,"J. SIAM Comp., vol. 2, pp. 225-231, 1973.[25] D. P. Huttenlocher and S. Ullman, "Object recognition using alignment," inProc. 1st Int. Conf. Computer Vision, 1987.[26] K. Ikeuchi, "Generating an interpretation tree from a CAD model for 3D-object recognition in bin-picking task,"Int. J. Computer Vision, vol. 1, no. 2, pp. 145-165, 1987.[27] A. Itai, M. Rodeh, and S. L. Tanimoto, "Some matching problems for bipartite graphs,"J. Ass. Comput. Mach., vol. 25, no. 4, pp. 517-525, Oct. 1978.[28] A. K. Jain and R. Hoffman, "Evidence-based recognition of 3D objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. 10, no. 6, 1988.[29] T. Kim and K. Y. Chwa, "AnO(nlognlog logn) parallel maximum matching algorithm for bipartite graphs,"Inform. Process. Lett., vol. 24, pp. 15-17, 1987.[30] L. Kitchen and A. Rosenfeld, "Discrete relaxation for matching relational structures,"IEEE Trans. Syst., Man, Cybern., vol. SMC-9, no. 12, Dec. 1979.[31] H. W. Kuhn, "The Hungarian method for the assignment problem,"Naval Res. Logist. Quart., vol. 2, pp. 83-97, 1955.[32] Y. Lamdan and H. J. Wolfson, "Geometric hashing: A general and efficient model-based recognition scheme," inProc. 2nd Int. Conf. Computer vision, 1988.[33] D. G. Lowe, "Three-dimensional object recognition from single two-dimensional images,"Artificial Intell., vol. 31, 1987.[34] T. Lozano-Perez, J. L. Jones, E. Mazer, P. A. O'Donnel, and W. E. Grimson, "Handey: A robot system that recognizes, plans, and manipulates," inProc. IEEE Int. Conf. Robotics and Automation, 1987.[35] D. W. Murray, "Model-based recognition using 3D shape alone,"Computer Vision, Graphics and Image Process., vol. 40, pp. 250-266, 1987.[36] M. Oshima and Y. Shirai, "Object recognition using three-dimensional information,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, no. 4, July 1983.[37] C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982.[38] A. A. Requicha, "Representations for rigid solids: Theory, methods, and systems,"Comput. Surveys, vol. 12, no. 4, pp. 437-465, 1980.[39] A. Rosenfeld, R. A. Hummel, and S. W. Zucker, "Scene labeling by relaxation operations,"IEEE Trans. Syst., Man, Cybern., vol. SMC- 6, pp. 420-433, June 1976.[40] L. G. Shapiro and R. M. Haralick, "Structural descriptions and inexact matching,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-3, no. 5, Sept. 1981.[41] S. L. Tanimoto, "Analysis of biomedical images using maximal matching," inProc. IEEE Conf. Decision&control, Dec. 1-3, 1976, pp. 171-176.[42] S. Umeyama, T. Kasvand, and M. Hospital, "Recognition and positioning of three-dimensional objects by combining matchings of primitive local patterns,"Computer Vision, Graphics, and Image Process., vol. 44, pp. 58-76, 1988.[43] A. K. C. Wong and S. W. Lu, "Representation of 3-D objects by attributed hypergraphs for computer vision," inProc. 1983 Int. Conf. Syst., Man, Cybern., pp. 49-53.[44] A. K. C. Wong and S. W. Lu, "Recognition and knowledge synthesis of 3-D object images," inProc. 1985 Computer Vision and Pattern Recognition, pp. 162-166.[45] A. K. C. Wong, S. W. Lu, and M. Rioux, "Recognition and shape synthesis of 3-D objects based on attributed hypergraphs,"IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 3, Mar. 1989.
Index Terms:
computer vision; 3-D object recognition; bipartite matching; discrete relaxation; pruning; search space; scene surface; time complexity function; computer vision; graph theory
Citation:
W.Y. Kim, A.C. Kak, "3-D Object Recognition Using Bipartite Matching Embedded in Discrete Relaxation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 3, pp. 224-251, Mar. 1991, doi:10.1109/34.75511
