| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Multidimensional Indexing for Recognizing Visual Shapes
April 1994 (vol. 16 no. 4)
pp. 373-392
This paper introduces an analytical framework for studying some properties of model acquisition and recognition techniques based on indexing. The goal is to demonstrate that several problems previously associated with the approach can be attributed to the low dimensionality of invariants used. These include limited index selectivity. Excessive accumulation of votes in the look-up table buckets, and excessive sensitivity to quantization parameters. Theoretical results demonstrate that using high-dimensional, highly descriptive global invariants produces better results in terms of accuracy, false positive suppression, and computation time. A practical example of high-dimensional global invariants is introduced and used to implement a 2-D shape acquisition/recognition system. The acquisition/recognition system is based on a two-step table look-up mechanism. First, local curve descriptors are obtained by correlating image contour information at short range. Then, seven-dimensional global invariants are computed by correlating triplets of local curve descriptors at longer range. This experimental system is meant to illustrate the behavior of a high-dimensional indexing scheme. Indeed, its performance shows good agreement with the analytical model with respect to database size, fault tolerance, and recognition speed. Model acquisition time is linear to cubic in the number of object features. Object recognition time is constant to linear in the number of models in the database and linear to cubic in the number of features in the image. The system has been tested extensively. With more than 250 arbitrary shapes in the database. Unsupervised shape and subpart acquisition is demonstrated.
[1] H. Asada and M. Brady, "The curvature primal sketch,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, no. 1, pp. 2-14, 1986.
[2] N. Ayache, O. Faugeras, and B. Faverjon, "A geometric matcher for recognizing and positioning 3-D rigid objects,"Int. Conf. Intelligent Robots and Computer Vision, Proc. SPIE, Oct. 1984.
[3] D. H. Ballard, "Parameter nets: A theory of low level vision," inProc. 7th Int. Joint Conf. Artificial Intelligence, Aug. 1981, pp. 1068-1078.
[4] D. H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes,"Pattern Recogn., vol. 13, no. 2, 1981, pp. 111-122.
[5] R. M. Bolle, A. Califano, R. Kjeldsen, and R. W. Taylor, "Computer vision research," inProc. DARPA Image Understanding Workshop, Palo Alto, CA, May 1989.
[6] R. M. Bolle, A. Califano, R. Kjeldsen, and R. W. Taylor, "Visual recognition using concurrent and layered parameter networks," IBM Tech. Rep., Nov. 1988; IEEE Conf. Computer Vision and Pattern Recognition, 1989.
[7] B. Bhanu and O. D. Faugeras, "Shape matching of two-dimensional objects,"IEEE Trans. Pattern Anal. Machine Intell., vol. 8, no. 2, pp. 137-155, Mar. 1984.
[8] P. J. Besl and R. C. Jain, "Three-dimensional object recognition,"ACM Comput. Surveys, vol. 17, no. 1, pp. 75-145, Mar. 1985.
[9] A. P. Blicher, "A shape representation based on geometric topology: Bumps, Gaussian curvature, and the topological zodiac," inProc. 10th Int. Joint Conf. Artificial Intelligence, Aug. 1987, pp. 767-770.
[10] R. C. Bolles and R. A. Cain, "Recognizing and locating partially visible objects: The local feature focus approach,"Int. J. Robotics Research. vol. 1, no. 3, pp. 57-82, Fall 1982.
[11] R. C. Bolles, P. Horaud, and M. J. Hannah, "3-DPO: A three-dimensional part orientation system," inProc. 8th Int. Joint Conf. on Artificial Intelligence, Aug. 1983, pp. 1116-1120.
[12] R. A. Brooks, "Model-based three-dimensional interpretations of two-dimensional images,"IEEE Trans. Pattern Anal. Machine Intell., vol. 5, no. 2, pp. 140-150, Mar. 1983.
[13] P. Burt, "Smart sensing within a pyramid vision machine,"Proc. IEEE, vol. 76, no. 8, pp. 1006-1015, 1988.
[14] J. F. Canny, "A computational approach to edge detection,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-8, pp. 679-697, 1986.
[15] A. Califano, "Feature recognition using correlated information contained in multiple neighborhoods," inProc. 7th Nat. Conf. Artificial Intelligence, July 1988, pp. 831-836.
[16] R. M. Bolle and R. W. Taylor, "Generalized neighborhoods: A new approach to feature extraction," inProc. IEEE Conf. Computer Vision and Pattern Recognition, June 1989.
[17] A. Califano and R. Mohan, "Generalized shape autocorrelation," inProc. AAAI-90, July 1990, pp. 1067-1073.
[18] A. Califano and R. Mohan, "Multidimesional indexing for recognizing visual shapes," inProc. IEEE Conf. Comp. Vision Patt. Recogn., June 1991, pp. 28-33.
[19] I. Chakravarty and H. Freeman, "Characteristic view as a basis for three-dimensional object recognition," inProc. SPIE Conf. Robot Vision, 1982, pp. 37-45.
[20] R.T. Chin and C. R. Dyer, "Model-based recognition in robot vision,"ACM Comput. Surveys, vol. 18, no. 1, pp. 67-108, Mar. 1986.
[21] D. T. Clemens and D. W. Jacobs, "Model group indexing for recognition," inProc. IEEE Conf. Computer Vision and Pattern Recognition, June 1991, pp. 4-9.
[22] 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.
[23] G. J. Ettinger, "Large hierarchical object recognition using libraries of parameterized model sub-parts,"Patt. Recog., pp. 32-41, 1988.
[24] O. D. Faugeras and M. Hebert, "A 3-D recognition and positioning algorithm using geometric matching between primitive surfaces," inProc. 8th Int. Joint Conf. Artificial Intelligence, Aug. 1983, pp. 996-1002.
[25] J. A. Feldman and D. H. Ballard, "Connectionist models and their properties,"Cognitive Sci., vol. 6, 1981, pp. 205-254.
[26] W. E. L. Grimson and T. Lozano-Perez, "Model-based recognition and localization from sparse range data or tactile data,"Int. J. Robotics Research, vol. 3, no. 3, pp. 3-34, Fall 1984.
[27] Z. Gigus and J. Malik, "Computing the aspect graph for line drawings of polyhedral objects,"IEEE Trans. Pattern Anal. and Machine Intell., vol. 12, no. 2, Feb. 1990.
[28] C. Goad, "Special purpose automatic programming for 3-D model-based vision," inProc. DARPA Image Understanding Workshop, 1983, pp. 94-104.
[29] W. E. L. Grimson, "The combinatorics of heuristic search termination for object recognition in cluttered environments," Tech. Rep. 1111, AI Lab., Mass. Inst. Technol., 1989.
[30] W. E. L. Grimson and D. P. Huttenlocher, "On the sensitivity of geometric hashing," inProc. 3rd Int. Conf. Computer Vision, Osaka, Japan, 1990.
[31] C. Hansen and T. Henderson, "CAGD-based computer vision," inProc. Workshop on Computer Vision, Nov.-Dec. 1987, pp. 100-105.
[32] Parallel Models of Associative Memory, E. Hinton and J.A. Anderson, eds., Lawrence Erlbaum Associates, Hillsdale, N.J., 1989 (updated edition).
[33] R. Horaud and R.C. Bolles, "3DPO's strategy for matching three-dimensional objects in range data," inProc. Int. Conf. Robotics, (Atlanta, GA), Mar. 1984, pp. 78-85.
[34] P. V. C. Hough, "Methods and means for recognizing complex patterns," U. S. Patent 3069654, 1962.
[35] D. P. Huttenlocher and S. Ullman, "Object recognition using alignment," inProc. 1st. Int. Conf. Computer Vision, pp. 102-111, 1987.
[36] D. P. Huttenlocher, "Three-dimensional recognition of solid objects from a two-dimensional image," M.I.T. Artificial Intell. Lab., TR 1045, 1989.
[37] K. Ikeuchi and T. Kanade, "Automatic generation of object recognition programs,"Proc. IEEE, vol. 76, no. 8, pp. 1016-1035, Aug. 1988.
[38] A. Kalvin, E. Schonberg, J. Schwartz, and M. Sharir, "Two-dimensional, model-based, boundary matching using footprints."Int. J. Robotics Res., vol. 5, no. 4, pp. 38-55, 1986.
[39] J. Koenderink and A. van Doorn, "The internal representation of solid shape with respect to vision,"Biological Cybern., vol. 32, pp. 211-216, 1979.
[40] Y. Lamdan, J. T. Schwartz, and H. J. Wolfson, "On recognition of 3-D objects from 2-D images," inProc. IEEE Int. Conf. Robotics Automat., Apr. 1988.
[41] Y. Lamdan, J. T. Schwartz, and H. J. Wolfson, "Object recognition by affine invariant matching," inProc. CVPR 88, 1988.
[42] Y. Lamdan and H. J. Wolfson, "Geometric hashing: A general and efficient model-based recognition scheme," inProc. 2nd Int. Conf. Computer vision, 1988.
[43] Y. Lamdan and H. J. Wolfson, "On the error analysis of geometric hashing," Robotics Lab, New York University, Tech. Rep. 213, Oct. 1989.
[44] D. G. Lowe, "The viewpoint consistency constraint,"Int. J. Comput. Vision, vol. 1, 1987, pp. 57-72.
[45] R. Mohan and R. Nevatia, "Perceptual organization for scene segmentation and description," inIEEE Trans. Pattern Anal. and Machine Intell., vol. 14, no. 6, June 1992, pp. 616-635.
[46] J. L. Mundy and A. J. Heller, "The evolution and testing of a model-based object recognition system," inProc. 3rd. Int. Conf. Computer Vision, pp. 268-282, 1990.
[47] R. Nevatia and T. O. Binford, "Description and recognition of curved objects,"Artificial Intell., vol. 8, no. 1, pp. 77-98, 1977.
[48] Suggested by one of the referees, during the review process.
[49] I. Rigoutsos and R. Hummel, "On a scalable parallel implementation of geometric hashing on the connection machine," Courant Inst. of Math. Science, New York Univ., Tech. Rep. 554, Apr. 1991.
[50] I. Rigoutsos and R. Hummel, "Robust similarity invariant matching in the presence of noise," inProc. 8th. Israeli Conf. Artificial Intelligence and Computer Vision, Dec., 1991.
[51] A. Rosenfeld and A. Kak,Digital Picture Processing, New York: Academic, 1976.
[52] J. L. McClelland and D. E. Rumelhart, Eds.,Parallel Distributed Processing, vol. 1, 2. Cambridge, MA: M.I.T. Press, 1986.
[53] D. Sabbah, "Computing with connections in visual recognition of origami objects,"Cognitive Sci., vol. 9, no. 1, Jan.-Mar. 1985, pp. 25-50.
[54] R. Shapira and H. Freeman, "Reconstruction of curved-surface bodies from a set of imperfect projections," inProc. 5th Int. Joint Conf. Artificial Intelligence, Aug. 1977, pp. 22-26.
[55] F. Stein and G. Medioni, "Efficient two dimensional object recognition," inProc. Int. Conf. Patt. Recogn.(Atlantic City, NJ), June 1990.
[56] G. Taubin, "Nonplanar curve and surface estimation in 3-space," inProc. IEEE Conf. Robotics Automation, May 1988.
[57] J. L. Turney, T. N. Mudge, and R. A. Volz, "Recognizing partially occluded parts,"IEEE Trans. Pattern Anal. Machine Intell., vol. 7, no. 4, pp. 410-421, July 1985.
[58] I. Weiss, "Projective invariants of shapes," inProc. DARPA Image Understanding Workshop, pp. 1125-1134, Apr. 1988.
[59] A. Witkin, "Scale space filtering," inProc. 8th Int. Joint Conf. Artificial Intelligence, Aug. 1983, pp. 1019-1021.
Index Terms:
computer vision; table lookup; image recognition; image sequences; multidimensional indexing; visual shapes recognition; limited index selectivity; look-up table buckets; high-dimensional highly descriptive global invariants; 2-D shape acquisition/recognition system; local curve descriptors; image contour information
Citation:
A. Califano, R. Mohan, "Multidimensional Indexing for Recognizing Visual Shapes," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 4, pp. 373-392, Apr. 1994, doi:10.1109/34.277591
