| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Matching 3-D Line Segments with Applications to Multiple-Object Motion Estimation
October 1990 (vol. 12 no. 10)
pp. 1002-1008
A two-stage algorithm for matching line segments using three-dimensional data is presented. In the first stage, a tree-search based on the orientation of the line segments is applied to establish potential matches. the sign ambiguity of line segments is fixed by a simple congruency constraint. In the second stage, a Hough clustering technique based on the position of line segments is applied to verify potential matches. Any paired line segments of a match that cannot be brought to overlap by the translation determined by the clustering are removed from the match. Unlike previous methods, this algorithm combats noise more effectively, and ensures the global consistency of a match. While the original motivation for the algorithm is multiple-object motion estimation from stereo image sequences, the algorithm can also be applied to other domains, such as object recognition and object model construction from multiple views.
[1] T. S. Huang, S. D. Blostein, A. Werkheiser, M. McDonnell, and M. Lew, "Motion detection and estimation from stereo image sequences: Some preliminary experimental results," inIEEE Proc. Workshop Motion: Representation and Control, 1986, pp. 45-46.
[2] T. O. Binford, "Survey of model-based image analysis systems,"Int. I. Robotics Res., vol. 1, pp. 18-64, 1982.
[3] P. J. Besl and R. C. Jain, "Three-dimensional object recognition,"ACM Comput. Surveys, vol. 17, no. 1, pp. 75-145, Mar. 1985.
[4] P. V. C. Hough, "Methods and means for recognizing complex shapes," U.S. Patent 3 069 654, 1962.
[5] L. S. Davis, "Hierarchical generalized Hough transform and line-segment based generalized Hough transform,"Pattern Recog., vol. 15, no. 4, pp. 277-285, 1982.
[6] G. Stockman, "Object recognition and localization via pose clustering,"Comp. Vision Graphics Image Processing, vol. 40, pp. 361-387, 1987.
[7] J. O'Rourke, "Motion detection using Hough techniques," inProc. IEEE Conf. Pattern Recognition Image Processing, 1981, pp. 82-87.
[8] R. Horaud, "New methods for matching 3-D objects with single perspective views,"IEEE Trans. Patt. Anal. Machine Intell., vol. PAMI-9, pp. 401-412, May 1987.
[9] H. T. Tanaka, D. H. Ballard, S. Tsuji, and M. Curtiss, "Parallel polyhedral shape recognition," inProc. Conf. Computer Vision Pattern Recognition, San Francisco, CA, June 1985, pp. 491-496.
[10] D. H. Ballard and D. Sabbah, "Viewer independent shape recognition,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, no. 6, pp. 653-659, Nov. 1983.
[11] B. A. Boyter and J. K. Aggarwal, "Recognition of polyhedra from range data,"IEEE Expert, pp. 47-59, 1986.
[12] W. E. Grimson and T. Lozano-Pérez, "Model-based recognition and localization from sparse range or tactile data,"Int. J. Robotics Res., vol. 3, no. 3, pp. 3-35, 1984.
[13] O. D. Faugeras, N. Ayache, and B. Faverjon, "A geometric matcher for recognizing and positioning 3-D rigid objects," inProc. First Int. Conf. Artificial Intell. Appl., Dec. 1984, pp. 218-224.
[14] 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.
[15] M. Hebert and T. Kanade, "The 3D-profile method for object recognition," inProc. Conf. Computer Vision Pattern Recognition, 1985, pp. 458-463.
[16] D. J. Burr, "On computer stereo vision with wire frame models," Coordinated Sci. Lab., Univ. Illinois, Rep. R-805, 1977.
[17] M. Herman, "Matching three-dimensional symbolic descriptions obtained from multiple views of a scene," inProc. Conf. Computer Vision and Pattern Recognition, San Francisco, CA, June 1985, pp. 585-590.
[18] M. J. Magee, B. A. Boyter, C-H. Chien, and J. K. Aggarwal, "Experiments in intensity guided sensing recognition of three-dimensional objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-7, no. 6, pp. 629-637, Nov. 1985.
[19] Y.C. Kim and J.K. Aggarwal, "Determining object motion in a sequence of stereo images,"IEEE J. Robotics and Automat., vol. RA-3, pp. 599-614, Dec. 1987.
[20] D. W. Murray and D. B. Cook, "Using the orientation of fragmented 3D edge segments for polyhedral object recognition,"Int. J. Comput. Vision, vol. 2, pp. 153-169, 1988.
[21] G. Medioni and R. Nevatia, "Matching images using linear features,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 6, pp. 675-685, Nov. 1984.
[22] C. Clark, D. Conti, W. Eckhardt, T. McCulloh, and R. Nevatia, "Matching of natural terrain scenes," inProc. Int. Conf. Pattern Recognition, 1980, pp. 217-222.
[23] N. Ayache and O. D. Faugeras, "HYPER: A new approach for the recognition and positioning of two-dimensional objects,"IEEE Trans. Patt. Anal. Machine Intell., vol. 8, no. 1, pp. 44-54, 1986.
[24] H. H. Chen and T. S. Huang, "Maximal matching of 3-D points for multiple-object motion estimation,"Patt. Recognition, vol. 21, no. 2, pp. 75-90, 1988.
[25] J. K. Cheng and T. S. Huang, "Algonthms for matching relational structures and their applications to image processing," School Elect. Eng., Purdue Univ.. West Lafayette, IN, Tech. Rep. 80-83, Dec.1980.
[26] 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.
[27] B. K. P. Horn,Robot Vision. Cambridge, MA: M.I.T. Press, 1986.
[28] T. Lozano-Pérez, "Spatial planning: A configuration space approach,"IEEE Trans. Comput., vol. C-32, pp. 108-120, 1983.
[29] J.D. Foley and A. Van Dam,Fundamentals of Interactive Computer Graphics(The System Programming Series). Reading, MA: Addison-Wesley, 1982.
[30] Y. I. Abdel-Aziz and H. M. Karara, "Direct linear transformation from comparator coordinates into object space coordinates in closed range photogrammetry," inProc. ASPIUI Symp. Close-Range Photogrammetry, Urbana, IL, Jan. 1971.
[31] H. H. Chen and T. S. Huang, "Using motion from orthographic projections to prune 3-D point matches," inProc. Workshop Visual Motion, 1989, pp. 290-297.
Index Terms:
pattern recognition; 3-D line segments; multiple-object motion estimation; two-stage algorithm; matching; tree-search; sign ambiguity; congruency constraint; Hough clustering technique; global consistency; stereo image sequences; object recognition; object model construction; pattern recognition; search problems; trees (mathematics)
Citation:
H.H. Chen, T.S. Huang, "Matching 3-D Line Segments with Applications to Multiple-Object Motion Estimation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 10, pp. 1002-1008, Oct. 1990, doi:10.1109/34.58872
