Current three-dimensional vision algorithms can generate depth maps or vector maps from images, but few algorithms extract high-level information from these depth maps. This paper identifies one algorithm that determines an object's orientation by matching object models to depth map data. The object models are constructed by mapping surface orien tation data onto spheres. This process is based on a mathe matical theorem that can be applied only to convex objects, but some extensions for nonconvex objects are presented. The paper shows that a global approach can be used successfully in cases where objects do not touch one another. Another important result illustrates the size of the space of rotations. It shows that even when 6,000 rotations are almost uniformly distributed for matching, errors of 17 degrees are still possible.
Get full access to this article
View all access options for this article.
References
1.
Ambler, A., and Popplestone, R.1975. Inferring the positions of bodies from specified spatial relationships. Artificial Intell.6(2):157 -174.
2.
Bajcsy, R.1980 (December, Miami, Fla.). Three-dimensional scene analysis. 5th IJCPR. pp. 1064-1074.
3.
Ballard, D.H., and Sabbah, D.1981 (August, Vancouver, B.C.). On shapes . IJCAI, pp. 607-612.
4.
Binford, T.O.1981. Inferring surfaces from images. Artificial Intell. J. vol. 17, pp. 205-244.
5.
Bolles, R.C., Horaud, P., and Hannah, M.J.1983 (August, Bretton Woods, N.H.). 3DPO: A three-dimensional part orientation system. Int. Symp. Robotics Res
6.
Brou, P.1981. Implementation of high level commands for robots. Master of science thesis. Massachusetts Institute of Technology. Department of Electrical Engineering and ComputerScience.
7.
Brou, P.1983. Finding the orientation of objects in vector maps. Ph.D. thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and ComputerScience.
8.
Cook, R.L., and Torrance, K.E.1982. A reflectance model for computer graphics. ACM Trans. on Graphics1 (1):7 -24.
9.
Coxeter, H.M.S.1973. Regular polytopes. New York: Dover.
10.
Dane, C., and Bajcsy. R.1981. Three-dimensional segmentation using the Gaussian image and spatial information. Computer and Informational Sciences Department. Moore School of Electrical Engineering, University of Pennsylvania .
11.
Do Carmo, M.P.1976. Differential geometry of curves and surfaces. Englewoods Cliffs, N.J.: Prentice-Hall.
12.
Doctor, L.J., and Torborg, J.G.1981. Display techniques for octree-encoded objects. IEEE Computer Graphics and Applications1(3).
13.
Drake, S.H.1977. Using compliance in lieu of sensory feedback for automatic assembly. Ph.D. thesis, Massachusetts Institute of Technology , Department of Mechanical Engineering.
14.
Faugeras, O.D., Hebert, M., and Pauchon, E.1982. Segmentation of range data into planar and quadratic patches . INRIA, France.
15.
Faugeras, O.D., et al. 1983 (Bretton Woods, N.H.). Object representation, identification and positioning from range data. Int. Symp. Robotics Res
16.
Giraud, A.1983 (Bretton Woods, N.H.). Generalized active compliance for part mating with assembly robots. Int. Symp. Robotics Res
17.
Hamilton, W.R.1969. Elements of quaternions. New York: Chelsea.
18.
Horn, B.K.P.1975. Obtaining shape from shading information. The Psychology of Computer Vision, ed. P. H. Winston.New York: McGraw-Hill, pp. 115 -155.
19.
Horn, B.K.P., Woodham, R.J., and Silver, W.M.1978. Determining shape and reflectance using multiple images. AIM-490. Cambridge: M.I.T. Artificial Intelligence Laboratory.
20.
Horn, B.K.P., and Sjoberg, R.W.1979. Calculating the reflectance map. Applied Optics, vol. 18, pp. 1770-1779.
21.
Horn, B.K.P.1984. Robot vision. Cambridge: MIT Press.
22.
Ikeuchi, K.1980 (February). Numerical shape from shading and occluding contours in a single view. A.I. Memo 566. Cambridge: M.I.T. Artificial Intelligence Laboratory.
23.
Ikeuchi. K.1981 (April). Recognition of 3-D objects using the extended Gaussian image. Niihari-gun, Japan: Electrotechnical Laboratory, Computer Vision Section.
24.
Ikeuchi, K.1983 (April). Determining attitude of object from needle map using extended Gaussian image. A.I. Memo 714. Cambridge : M.I.T. Artificial Intelligence Laboratory.
25.
Jackins, C.L., and Tanimoto, S.L.1980(August). Octrees and their use in the representation of three-dimensional objects. Internal rept. Seattle: University of Washington, Department of Computer Science .
26.
Jarvis, R.A.1983. A laser time of flight range scanner for robotic vision . IEEE Trans. on Pattern Analysis and Machine Intell.5(5):505-511.
27.
Kenner, H.1976. Geodesic math and how to use it. Berkeley, Calif.: University of California Press.
28.
Little, J.J.1983. An iterative method for reconstructing convex polyhedra from extended Gaussian images. Vancouver: University of British Columbia, Department of Computer Science.
29.
Lyusternik, L.A.1963. Convex figures and polyhedra. New York : Dover.
30.
Mackay, A.L.1980. The packing of three-dimensional spheres on the surface of a four-dimensional hypersphere. J. Phys. A. Math. Gen. , vol. 13, pp. 3375-3379.
31.
Marr, D.1976. Early processing of visual information. Phil. Trans. of the Royal Soc. of London, vol. 275, pp. 483-534.
32.
Marr, D., and Poggio, T.1979. A theory of human stereo vision. Proc. Royal Soc. of London, vol. 204, pp. 301-328.
33.
Meagher, D.J.1980 (October). Octree encoding: A new technique for the representation, manipulation and display of arbitrary three-dimensional objects. IPL-TR-80-111 . Troy, N.Y.: Rensselaer Polytechnic Institute, Image Processing Laboratory.
34.
Nagel, R.N., and Rosenfeld, A.1972. Ordered search technique in template matching. Proc. IEEEC-22( 1 ):242-244.
35.
Nevatia, R., and Binford, T.O.1977. Description and recognition of curved objects. Artificial Intell., vol. 8, pp. 77-98.
36.
Nishihara, H.K.1983(November). Prism: A practical real-time imaging stereo matcher. 3rd Int. Conf. on Robot Vision. Cambridge, Mass.: Society of Photo-Optical Instrumentation Engineers, p. 449.
37.
Nitzan, D., Brain, A.E., and Duda, R.O.1977. The measurement and use of registered reflectance and range data in scene analysis. Proc. IEEE, vol. 65, pp. 206-220.
38.
O'Rourke, J., and Badler, N.1979. Decomposition of three-dimensional objects into spheres . IEEE Trans. on Pattern Analysis and Machine Intell.1(3):295-305.
39.
Okada, T.1982. Development of an optical distance sensor for robots. Int. J. Robotics Res.1(4):3-14.
40.
Pearce, P., and Pearce, S.1978. Polyhedra primer. New York: Van Nostrand Reinhold.
41.
Pipitone, F.J., and Marshall, T.G.1983. A wide-field scanning triangulation rangefinder for machine vision. Int. J. Robotics Res.2(1):39-49.
42.
Pogorelov, A.V.1973. Extrinsic geometry of convex surfaces. Translations of Mathematical Monographs, vol. 35. Providence, R.I.: American Mathematical Society.
43.
Pogorelov, A.V.1978. The Minkowsky multidimensional problem. New York: Winston.
44.
Porter, G., and Mundy, J.1982. A non-contact profile sensor system for visual inspections . IEEE Workshop on Ind. Appl. of Machine Vision , p. 119.
45.
Preparata, F.P., and Hong, S.J.1977. Convex hulls of finite sets of points in two and three dimensions. Comm. ACM20(2):87-93.
46.
Pugh, A.1976. Polyhedra: A visual approach. Berkeley, Calif.: University of California Press.
47.
Requicha, A.A.G., and Tilove, R.B.1977a. Mathematical foundations of constructive solid geometry: General topology of regular closed sets. Tech. memo no. 26. Rochester, N.Y.: University of Rochester, Production Automation Project.
48.
Requicha, A.A.G., and Voelcker, H.B.1977b. Constructive solid geometry. Tech memo no. 25. Rochester, N.Y.: University of Rochester, Production Automation Project.
49.
Rosenfeld, A., and Kak, C.1976. Digital picture processing. New York : Academic Press, pp. 256-450.
50.
Salamin, E.1979. Application of quaternions to computation with rotations. Internal working paper. Stanford, Calif.: Stanford UniversityArtificial Intelligence Laboratory .
51.
Shirai, Y.1982. Image processing for data capture. IEEE Computer15( 11 ):21-34.
52.
Silver, W.M.1980. Determining shape and reflectance using multiple images. Master of science thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and ComputerScience.
53.
Smith, D.1979 (May). Using enhanced spherical images. AI Memo 451. Cambridge: M.I.T. Artificial Intelligence Laboratory .
54.
Taylor, R.H.1983. Planning and execution of straight line manipulator trajectories. Robot motion, ed. Mike Brady.Cambridge: MIT Press.
55.
Toth, F.L.1964. Regular figures. New York: Macmillan.
56.
Voelcker, H.B., and Requicha, A.A.G.1977(October). Geometric modeling of mechanical parts and processes. Tech memo no. 23. Rochester, N.Y.: University of Rochester, Production Automation Project.
57.
Wenninger, M.J.1979. Spherical models. Cambridge: Cambridge University Press.
58.
Widrow, B.1973. The rubber-mask technique. Pattern Recognition , vol. 5, pp. 175-197.
