The problem of recognizing and locating rigid objects in 3-D space is important for applications of robotics and naviga tion. We analyze the task requirements in terms of what information needs to be represented, how to represent it, what kind of paradigms can be used to process it, and how to implement the paradigms. We describe shape surfaces by curves and patches, which we represent by linear primitives, such as points, lines, and planes. Next we describe algo rithms to construct this representation from range data. We then propose the paradigm of recognizing objects while locat ing them. We analyze the basic constraint of rigidity that can be exploited, which we implement as a prediction and verifi cation scheme that makes efficient use of the representation. Results are presented for data obtained from a laser range finder, but both the shape representation and the matching algorithm are general and can be used for other types of data, such as ultrasound, stereo, and tactile.
Get full access to this article
View all access options for this article.
References
1.
Agin, G.J.1972. Representation and description of curved objects. Tech. Report AIM-73. Stanford, Calif.: Stanford University.
2.
Ayache, N., and Faugeras, O.D.1984(August). A new method for the recognition and positioning of 2-D objects. Proc. 7th Int. Conf. onPattern Recognition , pp. 1274-1280.
3.
Baker, H.H., and Binford, T.O.1982. A system for automated stereo mapping. Proc. Image Understanding Workshop, pp. 215-222. Sciences Applications, Inc.
4.
Ballard, D.H.1981. Generalizing the Hough transform to arbitrary shapes . Pattern Recognition13(2):111-122.
5.
Boissonnat, J.D.1984 (August, Montreal, Canada). Representing 2-D and 3-D shapes with the Delaunay triangulation. Proc. 7th Int. Conf. on Pattern Recognition, pp. 745-748.
6.
Bolle, R., and Cooper, D.1984 (December). On optimally combining pieces of information with application to estimating 3-D complex-object position from range data. Tech. Report LEMS-8, Providence, R.I.: Brown University, Division of Engineering.
7.
Brady, M., and Asada, H.1984. Smoothed local symmetries and their implementation . Int. J. Robotics Res.3(3), 36-61.
8.
Brady, M., et al. 1984 (Kyoto, Japan). Describing surfaces. Proc. 2nd Int. Symp. on Robotics Res ., MIT Press, pp. 434-445.
9.
Cernushi, B., Belhumer, P., and Cooper, B.1985 (June). Estimating and recognizing parametrized 3-D objects using a moving camera. Proc. CVPR'85 , pp. 167-170.
10.
Faugeras, O.D., and Berthod, M.1980. Improving consistency and reducing ambiguity in stochastic labeling: an optimization approach. IEEE Trans. on Pattern Analysis and Machine Intell. PAMI-3(4): 412-424.
11.
Faugeras, O.D., and Hebert, M.1983 (August, Karlsruhe, Germany). A 3-D recognition and positioning algorithm using geometrical constraints between primitive surfaces. Proc. 8th Joint Conf. on Artificial Intell, pp. 996-1002.
12.
Faugeras, O.D., et al. 1982. Towards a flexible vision system. In Robot vision, ed. A. Pugh. United Kingdom: IFS, pp. 129-142.
13.
Gaston, P.C., and Lozano-Perez, T.1983. Tactile recognition and localization using object models. Tech. Report AIM- 705, Cambridge: MIT Artificial Intelligence Laboratory.
14.
Grimson, W.E.L.1981. From images to surfaces: a computational study of the human early visual system. Cambridge: MIT Press.
15.
Grimson, W.E.L., and Lozano-Perez, T.1983. Model-based recognition and localization from sparse three-dimensional data. Int. J. Robotics Res.3(3):3-35.
16.
Hamilton, W.R.1969. Elements of quaternions. New York: Chelsea.
17.
Hebert, M.1983. Reconnaissance de formes tridimensionnelles. Ph. D. thesis, University of Paris South. Available as INRIA Tech. Rep. ISBN 2-7261-0379-0.
18.
Horaud, P., and Bolles, R.C.1984 (Atlanta, Georgia). 3-DPO's strategy for matching three-dimensional data. Proc. of the Int. Conf. on Robotics, pp. 78-85.
19.
Horn, B.K.P.1975. Obtaining shape from shading information. In The Psychology of computer vision, ed. P. H. Winston.New York: McGraw-Hill, pp. 115-155.
20.
Hummel R., and Zucker, S.1983. On the foundations of relaxation labeling processes . IEEE Trans. on Pattern Analysis and Machine Intell. PAMI-5:267-287.
Marr, D., and Poggio, T.1979. A computational theory of human stereo vision. Proc. Roy. Soc. Lond. (204):301- 328.
23.
Nishihara, H.K.1983. PRISM: a practical realtime imaging stereo system . In Proc. 3rd Int. Conf. on Robot Vision and Sensory Control , ed. B. Rooks. IFS publications and Amsterdam: North-Holland.
24.
Ohta, Y., and Kanade, T.1983. Stereo by intra- and inter-scanline search using dynamic programming. Tech. Rep. CMU-CS-83-162. Pittsburgh : Carnegie Mellon University.
25.
Oshima, M., and Shirai, Y.1983. Object recognition using three-dimensional information . IEEE Trans. on Pattern Analysis and Machine Intell. PAMI-5(4): pp. 353-361.
26.
Ponce, J.1983. Representation et manipulation d'objets tridimensionnels . Ph. D. thesis, University of Paris South. Also available as INRIA Tech. Rep. ISBN 2-7261-0378-2.
27.
Ponce, J., and Brady, M.1985 (March). Toward a surface primal sketch. Proc. Int. Conf. Robotics and Automation, pp. 420-425.
28.
Rosenfeld, A., Hummel, R., and Zucker, S.1979. Scene labeling by relaxation operations. IEEE Trans. on Systems, Man and Cybernetics (6):420-433.
29.
Witkin, A.P.1981. Recovering surface shape and orientation from texture . In Computer vision, ed. M. Brady, Amsterdam: North-Holland .
