| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Model Construction and Shape Recognition from Occluding Contours
April 1989 (vol. 11 no. 4)
pp. 372-389
A technique is presented for recognizing a 3D object (a model in an image library) from a single 2D silhouette using information such as corners (points with high positive curvatures) and occluding contours, rather than straight line segments. The silhouette is assumed to be a parallel projection of the object. Each model is stored as a set of the principal quadtrees, from which the volume/surface octree of the model is generated. Feature points (i.e. corners) are extracted to guide the recognition process. Four-point correspondences between the 2D feature points of the observed object and 3D feature points of each model are hypothesized, and then verified by applying a variety of constraints to their associated viewing parameters. The result of the hypothesis and verification process is further validated by 2D contour matching. This approach allows for a method of handling both planar and curved objects in a uniform manner, and provides a solution to the recognition of multiple objects with occlusion as demonstrated by the experimental results.
[1] 372R. A. Jarvis, "A perspective on range finding techniques for computer vision,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI- 5, no. 2, Mar. 1983.[2] J. K. Aggarwal, L. S. Davis, W. N. Martin, and J. W. Roach, "Survey: Representation methods for three-dimensional objects," inProgress in Pattern Recognition, vol. 1, L. N. Kanal and A. Rosenfeld, Eds. New York: North-Holland, 1981, pp. 377-391.[3] A. A. Requicha, "Representations for rigid solids: Theory, methods, and systems,"Comput. Surveys, vol. 12, no. 4, pp. 437-465, 1980.[4] C. L. Jackins and S. L. Tanimoto, "Oct.trees and their use in representing three-dimensional objects,"Comput. Graphics Image Processing, vol. 14, pp. 249-270, 1980.[5] D. Meagher, "Geometric modeling using octree encoding,"Comput. Graphics Image Processing, vol. 19, pp. 129-147, 1982.[6] M. Yau and S. N. Srihari, "A hierarchical data structure for multi-dimensional digital images,"Commun. ACM, vol. 26, pp. 504-515, July 1983.[7] C.H. Chien and J. K. Aggarwal, "Volume/surface octrees for the representation of three-dimensional objects,"Comput. Vision, Graphics, Image Processing, vol. 36, pp. 100-113, 1986.[8] C.H. Chien and J.K. Aggarwal, "Identification of 3-D Objects from Multiple Silhouettes Using Quadtrees/Octrees,"Computer Vision, Graphics, and Image Processing, Nov./Dec. 1986, pp. 256-273.[9] C. H. Chien and J. K. Aggarwal, "Computation of volume/surface octrees from contours and silhouettes of multiple views," inProc. CVPR-86, Miami Beach, FL, June 22-26, 1986, pp. 250-255.[10] C. H. Chien, "Reconstruction and recognition of 3-D objects from occluding contours and silhouettes," Ph.D. dissertation, Dep. Elec. Comput. Eng., Univ. Texas, Austin, 1987; Also as Tech. Rep. TR- 87-5-37, Comput. and Vision Res. Center, Univ. Texas, Austin, May 1987.[11] A. Klinger and C. R. Dyer, "Experiments on picture representation using regular decomposition,"Comput. Graphics Image Processing, vol. 5, pp. 68-105, 1976.[12] H. Samet and A. Rosenfeld, "Quadtree structures for region processing," inProc. IJCPR, 1980, pp. 36-41.[13] C. H. Chien and J. K. Aggarwal, "A normalized quadtree representation,"Comput. Vision, Graphics, Image Processing, vol. 26, pp. 331-346, 1984.[14] D. Meagher, "The octree encoding method for efficient solid modeling," Ph.D. dissertation, Dep. Elec. Syst. Eng., Rensselaer Polytechnic Inst., Troy, NY.[15] W. N. Martin and J. K. Aggarwal, "Volumetric descriptions of objects from multiple views,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, no. 2, pp. 150-158, Mar. 1983.[16] D. Marr and T. Poggio, "A computational theory of human stereo vision,"Proc. Roy. Soc. London, Series B, no. 204, pp. 301-328, 1979.[17] B. K. P. Horn, "Obtaining shape from shading information," inThe Psychology of Computer Vision, P. H. Winston, Ed. New York: McGraw-Hill, 1975, pp. 115-155.[18] R. J. Woodham, "A cooperative algorithm for determining surface orientation from a single view, " inProc. IJCAI-79, 1979, pp. 413- 415.[19] J. J. Gibson,The Perception of the Visual World. Boston, MA: Houghton Mifflin, 1950.[20] K. Steven, "Surface/perception from local analysis of texture and contour," Ph.D. dissertation, Dep. Elec. Eng. Comput. Sci., MIT, Cambridge, MA, 1979.[21] J. R. Kender, "Shape from texture," Ph.D. dissertation, Carnegie-Mellon Univ., Pittsburgh, PA, Rep. CMU-CS-81-102, Nov. 1980.[22] A. P. Witkin, "Recovering surface shape and orientation from texture,"Artificial Intell., vol. 17, pp. 17-45, Aug. 1981.[23] H. G. Barrow and J. M. Tenenbaum, "Interpreting line drawings as three dimensional surfaces,"Artificial Intell., vol. 17, pp. 75-116, Aug. 1981.[24] M. Brady and A. Yuille, "An extremum principle for shape from contour,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 3, pp. 288-301, May 1984.[25] T. P. Wallace and P. A. Wintz, "An efficient three-dimensional aircraft recognition algorithm using normalized Fourier descriptors,"Comput. Graphics Image Processing, vol. 13, pp. 99-126. 1980.[26] P. J. Besl and R. C. Jain, "Three-dimensional object recognition,"ACM Comput. Surveys, vol. 17, no. 1, pp. 75-145, Mar. 1985.[27] M. A. Fischler and R. C. Bolles, "Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,"Commun. ACM, vol. 24, no. 6, pp. 381-395, 1981.[28] R. B. Fisher, "Using surfaces and object models to recognize partially obscured objects," inProc. 8th IJCAI, Karlsruhe, West Germany, Aug. 8-12, 1983, pp. 989-995.[29] C. Goad, "Fast 3D model-based vision," inFrom Pixels to Predicates, A. P. Pentland, Ed. Norwood, NJ: Ablex, 1986.[30] O. D. Faugeras and G. Toscani, "The calibration problem for stereo," inProc. CVPR-86, Miami Beach, FL, June 22-26, 1986, pp. 15-20.[31] J. Ben-Arie and A. A. Meiri. "3-D objects recognition by state space search: Optimal geometric matching," inProc. CVPR-86, Miami Beach, FL, June 22-26, 1986, pp. 456-461.[32] D. G. Lowe, "Three-dimensional object recognition from single two-dimensional images," Comput. Sci. Division, Courant Inst. Math. Sci., New York Univ., New York, NY, Tech. Rep. TR-202, Feb. 1986.[33] D. G. Schweikert, "An interpolation curve using a spline in tension,"J. Math. Phys., vol. 45, pp. 312-317, 1966.[34] A. K. Cline, "Smoothing by splines under tension," Dep. Comput. Sci., Univ. Texas at Austin, Rep. CNA-168, 1981.[35] R.O. Duda and P.E. Hart, "Use of the Hough transformation to detect lines and curves in pictures,"Commun. Ass. Comput. Mach., vol. 15, no. 1, pp. 11-15, Jan. 1972.[36] F. Attneave, "Some informational aspects of visual perception,"Psychol. Rev., vol. 61, pp. 183-193, 1954.[37] Y. F. Wang, M. J. Magee, and J. K. Aggarwal. "Matching three-dimensional objects using silhouettes,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 4, pp. 513-518, July 1984.
Index Terms:
picture processing; pattern recognition; shape recognition; occluding contours; 3D object; 2D silhouette; quadtrees; volume/surface octree; feature points; contour matching; pattern recognition; picture processing; trees (mathematics)
Citation:
C.H. Chien, J.K. Aggarwal, "Model Construction and Shape Recognition from Occluding Contours," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 4, pp. 372-389, Apr. 1989, doi:10.1109/34.19034
