Computational strategies for object recognition

ABSTRACT

This article reviews the available methods for automated identification of objects in digital images. The techniques are classified into groups according to the nature of the computational strategy used. Four classes are proposed: (1) the simplest strategies, which work on data appropriate for feature vector classification, (2) methods that match models to symbolic data structures for situations involving reliable data and complex models, (3) approaches that fit models to the photometry and are appropriate for noisy data and simple models, and (4) combinations of these strategies, which must be adopted in complex situations. Representative examples of various methods are summarized, and the classes of strategies with respect to their appropriateness for particular applications.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Amir A. Amini , Terry E. Weymouth , David J. Anderson, A parallel algorithm for determining two-dimensional object positions using incomplete information about their boundaries, Pattern Recognition, v.22 n.1, p.21-28, January 1989 [doi>10.1016/0031-3203(89)90034-4]
	2	N Ayache , O D Faugeras, HYPER: a new approach for the recognition and positioning to two-dimensional objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.1, p.44-54, Jan. 1986 [doi>10.1109/TPAMI.1986.4767751]
	3	BALLARD, D. H. 1981. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recogn. 13, 111-122.
	4	Dana Harry Ballard , Christopher M. Brown, Computer Vision, Prentice Hall Professional Technical Reference, 1982
	5	BALLARD, D. H. AND SABBAH, D. 1981. On Shapes. International Joint Conference on Artificial Intelligence, 607-612.
	6	BAR~. A. H. 1981. Superquadrics and anglepreserving transformations. IEEE Comput. Graph. Appl. 1, 11-23.
	7	BELLMAN, R. AND DREYFUS, S. 1962. Applied Dynamic Programming, Princeton Univ Press, Princeton, N. J
	8	BERGMAN, A AND MULGAONKAR, P. G. 1988. Neural networks for address-block ranking: A comparison with classical techniques. In Proceedings of USPS Third Advanced Technology Conference (Washington, D C., May, 3-5).
	9	BINFORD, T. O. 1982. Survey of model-based image analysis systems. Int. J. Rob. Res. 1, 118-64.
	10	BOBICK, A. F. AND BOLLES, R. C. 1989. Representation space: An approach to the integration of visual information. In Proceedings of Computer Vision and Pattern Recognition (San Diego), IEEE Computer Science Press, Washington, 492-499.
	11	R C Bolles , P Horaud, 3DPO: A three-dimensional part orientation system, International Journal of Robotics Research, v.5 n.3, p.3-26, Fall 1986 [doi>10.1177/027836498600500301]
	12	BROOKS, R. A. 1981. Symbolic reasoning among 3-D models and 2-D images. Artif Intell. 17, 285-348.
	13	BROOKS, R. A. 1983. Model-based threedimensiona( interpretations of two-dimensional images. IEEE Trans. Patt. A,al. Mach. Intell. PAMI 5, 2, 140-150.
	14	J Canny, A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.6, p.679-698, Nov. 1986 [doi>10.1109/TPAMI.1986.4767851]
	15	CLOWES, M. B. 1971. On seeing things. Artif. Intell. 2, 1, 79-116.
	16	B. Draper , R. Collins , J. Brolio , A. Hanson , E. Riseman, The Schema System, University of Massachusetts, Amherst, MA, 1988
	17	DUDA, R. O. AND HART, P. E. 1973. Pattern Classification and Scene Analysis, John Wiley & Sons, New York.
	18	M A Eshera , K S Fu, An image understanding system using attributed symbolic representation and inexact graph-matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.5, p.604-618, Sept. 1986 [doi>10.1109/TPAMI.1986.4767835]
	19	FAN, T.-J., MED~ONI, G., AND NEVATIA, R. 1988. Matching 3-D objects using surface desriptions. In Proceedings of the 1988 IEEE International Conference on Robotics and Automation (Philadelphia), pp. 1400-1406.
	20	T.-J. Fan , G. Medioni , R. Nevatia, Recognizing 3-D Objects Using Surface Descriptions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.11, p.1140-1157, November 1989 [doi>10.1109/34.42853]
	21	FAUGERAS, O. ANn BERTHOD, M. 1981. Improving consistency and reducing ambiguities in stochastic labeling: An optimization approach. IEEE Trans. Patt. Anal. Mach. Intell. PAM! 3, 4, 412 424.
	22	FISCHLER, M. A. AND ELSCHLAGER, R. A. 1973. The representation and matching of pictorial structures. IEEE Trans. Comput. C-22, 1, 67-92.
	23	FISCHLER, M. A., TENENBAUM, J. M., AND WOLF, H.C. 1981. Detection of roads and linear structures in low-resolution aerial imagery using a multisource knowledge integration technique. Comput. Graph. Image Process. 15, 201-223.
	24	FUA, P. 1989. Object delineation as an optimization problem: A connection machine implementation. In Proceedings of the 4th International Conference on Supercomputing (Santa Clara, Calif.), pp. 476-484.
	25	FUA, P. AND HANSON, A. J. 1987. Using generic geometric models for intelligent shape extraction. In Proceedings of the AAAI 6th National Conference on Artificial Intelligence, (Los Altos, CA, July), Morgan-Kaufmann, pp 706-711.
	26	FUA, P. AND HANSON~ A. J. 1988. Extracting generic shapes using model-driven optimization. In Proceedings of the DARPA Image Uaderstanding Workshop, pp. 994-1004.
	27	P. Fua , A. J. Hanson, An optimization framework for feature extraction, Machine Vision and Applications, v.4 n.2, p.59-87, Spring 1991 [doi>10.1007/BF01257823]
	28	Pascal Fua , Yvan G. Leclerc, Model driven edge detection, Machine Vision and Applications, v.3 n.1, p.45-56, Winter 1990 [doi>10.1007/BF01211451]
	29	Francesco Gardin , Bernard Meltzer, Analogical representations of naive physics, Artificial Intelligence, v.38 n.2, p.139-159, March 1989 [doi>10.1016/0004-3702(89)90055-6]
	30	GEMAN, S. AND GEMAN, D. 1984. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Patt. Anal. Mach. Intell. PAMI 6, 721-741.
	31	GERBRANDS, J. J., BACKER, E., AND VAN DER HOEVEN, W. A. G. }986. Quantitative evaluation of edge detection by dynamic programming. In Pattern Recognitwn in Practice H, E. S. Gelsema and L. N. Kanal, Eds Elsevier Science Publishers B. V., Amsterdam, pp. 91-99.
	32	W. E. L. Grimson , D. P. Huttenlocher, On the Sensitivity of the Hough Transform for Object Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.3, p.255-274, March 1990 [doi>10.1109/34.49052]
	33	GROEN, F. C. A., TEN KATE, T. K. SMEULDERS, A. W. M., AND YOUNG, I. T. 1989. Human chromosome classification based on local band descriptors Pattern Recogn. Lett. 9, 3, 211-222.
	34	HALL, E. L. 1979. Computer Image Processing and Recognition, Academic Press, New York.
	35	Richard W. Hamming, Coding and information theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
	36	M Herman , T Kanade, Incremental reconstruction of 3D scenes from multiple, complex images, Artificial Intelligence, v.30 n.3, p.289-342, Dec. 1986 [doi>10.1016/0004-3702(86)90002-0]
	37	R. Horaud , T. Skordas, Stereo Correspondence Through Feature Grouping and Maximal Cliques, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.11, p.1168-1180, November 1989 [doi>10.1109/34.42855]
	38	HOUGH, P. V. C. 1962. Methods and Means for Recognizing Complex Patterns, U.S. Patent 3069654.
	39	HUERTAS, A. COLE, W., AND NEVATIA, R. 1987. Detecting runways in aerial images. In Proceedings of the DARPA Image Understanding Workshop. pp. 272-297.
	40	A. Huertas , R. Nevatia, Detecting buildings in aerial images, Computer Vision, Graphics, and Image Processing, v.41 n.2, p.131-152, Feb, 1988 [doi>10.1016/0734-189X(88)90016-3]
	41	I-IuFFMAN, D. A. 1971, Impossible objects as nonsense sentences. Mach. Intell. 6, 295-323.
	42	Vincent Shang-Shouq Hwang , Larry S Davis , Takashi Matsuyama, Hypothesis integration in image understanding systems, Computer Vision, Graphics, and Image Processing, v.36 n.2-3, p.321-371, Nov/ Dec. 1986 [doi>10.1016/0734-189X(86)90081-2]
	43	J. Illingworth , J. Kittler, A survey of the Hough transform, Computer Vision, Graphics, and Image Processing, v.44 n.1, p.87-116, Oct. 1988 [doi>10.1016/S0734-189X(88)80033-1]
	44	Anil K. Jain , Richard Hoffman, Evidence-Based Recognition of 3-D Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.6, p.783-802, November 1988 [doi>10.1109/34.9102]
	45	Alan Kalvin , Edith Schonberg , Jacob T. Schwartz , Micha Sharir, Two-dimensional, model-based, boundary matching using footprints, International Journal of Robotics Research, v.5 n.4, p.38-55, Winter, 1987 [doi>10.1177/027836498600500403]
	46	KANADE, T. 1980. Survey--Region segmentation: Signal versus semantics.Comput. Graph. Image Process. 13, 279-297.
	47	KASS, M., WITKIN, A., AND TERZOPOULOS, D. 1987. SNAKES: Active contour models. Int. J. Comput. Vision 1, 4, 321-331.
	48	KmKPATRICK, S., GELATT, C. D., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 671-680.
	49	J Kittler , J Illingworth, Relaxation labelling algorithms-a review, Image and Vision Computing, v.3 n.4, p.206-216, Nov. 1986 [doi>10.1016/0262-8856(85)90009-5]
	50	LAMDAN, Y. AND WOLFSON, H. J. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Proceedings of the 2nd International Conference on Computer Vision. IEEE Computer Society Press, Washington.
	51	LAWS, K. I. 1984. Goal-directed texture segmentation. Tech. Note 334, Artificial Intelligence Center, SRI International, Menlo Park, California. This method is an extension to the Ohlander et al. {1978} segmentation method.
	52	LECLERC, Y. G. 1989. Constructing simple stable descriptions for image partitioning. Int. J. Comput. Vision 3, 73-102.
	53	A D Léy-Mandel , A N Venetsanopoulos , J K Tsotsos, Knowledge-based landmarking of cephalograms, Computers and Biomedical Research, v.19 n.3, p.282-309, June 1986 [doi>10.1016/0010-4809(86)90023-6]
	54	D G Lowe, Three-dimensional object recognition from single two-dimensional images, Artificial Intelligence, v.31 n.3, p.355-395, March 1987 [doi>10.1016/0004-3702(87)90070-1]
	55	MACKWORTH, A. K. 1973. Interpreting pictures of polyhedral scenes. Artif. Intell. 4, 121-137
	56	Henri Maître , Yifeng Wu, Improving dynamic programming to solve image registration, Pattern Recognition, v.20 n.4, p.443-461, 1987 [doi>10.1016/0031-3203(87)90071-9]
	57	MALta, J. 1987. Interpreting line drawings of curved objects. Int. J. Comput. Vision 1, 73- 103.
	58	Abdul-Reza Mansouri , Alfred S. Malowany , Martin D. Levine, Line detection in digital pictures: a hypothesis prediction/verification pardigm, Computer Vision, Graphics, and Image Processing, v.40 n.1, p.95-114, Oct. 1987 [doi>10.1016/0734-189X(87)90058-2]
	59	J. Mantas, Methodologies in pattern recognition and image analysis-a brief survey, Pattern Recognition, v.20 n.1, p.1-6, 1987 [doi>10.1016/0031-3203(87)90012-4]
	60	MARR, D. 1982. Vision, W H. Freeman, San Francisco, Calif.
	61	Takashi Matsuyama, Expert systems for image processing: knowledge-based composition of image analysis processes, Computer Vision, Graphics, and Image Processing, v.48 n.1, p.22-49, Oct. 1989 [doi>10.1016/0734-189X(89)90103-5]
	62	MCKEOWN, D. M. AND DENLINGER, J. L. 1988. Cooperative methods for road tracking m aerial imagery. In Proceedmgs of the IEEE Computer Vision and Pattern Recognition (Ann Arbor, Mich.), IEEE Computer Society Press, Washington, pp. 662-672.
	63	McKEowN, D. M., HARVEY, W. A., AND McDERMOTT, J. 1985. Rule-based interpretation of aerial images. IEEE Trans. Pattern Anal. Mach. Intell. PAMI 7 5, 570-585
	64	David Mm McKeown, Jr. , Wilson A. Harvey , Lambert E. Wixson, Automating knowledge acquisition for aerial image interpretation, Computer Vision, Graphics, and Image Processing, v.46 n.1, p.37-81, April 1989 [doi>10.1016/S0734-189X(89)80016-7]
	65	MOHAN, R. AND NEVATIA, R. 1988. Perceptual grouping for the detection and description of structures in aerial images In Proceedings of the DARPA Image Understanding Workshop (Los Altos, CA), Morgan-Kaufmann, pp. 512-526.
	66	R. Mohan , R. Nevatia, Using Perceptual Organization to Extract 3D Structures, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.11, p.1121-1139, November 1989 [doi>10.1109/34.42852]
	67	MULGAONKAR, P. G., SHAPIRO, L. G., AND HARALICK, R. M. 1984. Matching "sticks, plates and blobs" objects using geometric relational constraints. Image Vision Comput. 2, 2, 85-98.
	68	D. W. Murray, Model-based recognition using 3D shape alone, Computer Vision, Graphics, and Image Processing, v.40 n.2, p.250-266, November 1, 1987 [doi>10.1016/S0734-189X(87)80118-4]
	69	D. W. Murray , B. F. Buxton, Scene segmentation from visual motion using global optimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.2, p.220-228, March 1987 [doi>10.1109/TPAMI.1987.4767896]
	70	NAGAO, M. 1984. Control strategies in pattern analysis. Pattern Recogn. 17, 1, 45-56.
	71	NAGAO, M. AND MATSUYAMA, T. 1980. A Structural Analysis of Complex Aerial Photographs, Plenum Press, New York.
	72	N. Nandhakumar , J. K. Aggarwal, The artificial intelligence approach to pattern recognition—a perspective and an overview, Pattern Recognition, v.18 n.6, p.383-389, 1985 [doi>10.1016/0031-3203(85)90009-3]
	73	NAZIF, A. M. AND LEVINE, M. D. 1984. Low level image segmentation: An expert system. IEEE Trans. Pattern Anal. Mach. Intell. PAMI 6, 5, 555-577.
	74	NIBLACK, W. AND PETKOVIC, D. 1988. On improving the accuracy of the Hough transform. In Proceedings of Computer Vlswn and Pattern Recognition (Ann Arbor, Mich.), IEEE Computer Society Press, Washington, pp. 574-579.
	75	NUYTS, J. MORTELMANS, L., SUETENS, P., OOSTERLINCK, A. AND DE ROO, M. 1989. Model-based quantification of myocardial perfusion images from SPECT. J. Nuclear Med. 30, 1992-2001.
	76	OHLANDER, R., PaICE, K., AND REDDY, D. R. 1978. Picture segmentation using a recursive region splitting method. Comput. Graph. Image Process. 8, 3, 313-333.
	77	Yuichi Ohta, Knowledge-based interpretation of outdoor natural color scenes, Pitman Publishing, Inc., Marshfield, MA, 1985
	78	PAVLIDIS, T. 1986. A critical survey of image analysis methods. In Proceedings of the 8th International Conference on Pattern Recognition. (Paris, France), IEEE Press, NY, pp. 502-511.
	79	Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
	80	Alex P. Pentland, Automatic extraction of deformable part models, International Journal of Computer Vision, v.4 n.2, p.107-126, Mar. 1990 [doi>10.1007/BF00127812]
	81	PREMOLI, A., GRATTOM, P., AND POLLASTRI, F. 1989. A non-sequential contour detection with a prior knowledge. Pattern Recogn. Lett. 9, 45-51.
	82	QUAM, L. H. 1978. Road tracking and anomaly detection in aerial imagery. SRI International AI Center Tech. Note 158. In Proceedings of the ARPA Image Understanding Workshop, (May) pp. 51-55.
	83	A. Ravishankar Rao , Ramesh Jain, Knowledge Representation and Control in Computer Vision Systems, IEEE Expert: Intelligent Systems and Their Applications, v.3 n.1, p.64-79, March 1988 [doi>10.1109/64.2096]
	84	REYNOLDS, G. O. DEVELIS, J. B., PARRENT, G. B., JR. AND THOMPSON, B. J. 1989. The new physical optics notebook: Tutorials in fourier optics. In Detectwn of Objects by Complex Inverse Filtering, SPIE and AIP, New York, pp. 417 420.
	85	J. A. Richards, Remote Sensing: Digital Image Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1986
	86	ROSENrELD, A. 1969. Picture Processing by Computer, Academic Press, New York.
	87	Azriel Rosenfeld, Image analysis: problems, progress, and prospects, Readings in computer vision: issues, problems, principles, and paradigms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
	88	ROSENFELD, A., HUMMEL, R. A., AND ZUCKER, S. W. 1976. Scene labeling by relaxation operations. IEEE Trans. Syst. Man Cybern. SMC 6, 6, 420-433.
	89	SHANNON, C. E. 1948. A mathematical theory of communication. Bells Syst. Tech. J. 27, 623-656.
	90	Michael O. Shneier , Ronald Lumia , Ernest W. Kent, Model-based strategies for high-level robot vision, Computer Vision, Graphics, and Image Processing, v.33 n.3, p.293-306, March 1986 [doi>10.1016/0734-189X(86)90178-7]
	91	SUETENS, P., SMETS, C., VAN DE WERF, F., AND OOSTERLINCK, A. 1989. Recognition of the coronary blood vessels on angiograms using hierarchical model-based iconic search. In Proceedings of Computer Vision and Pattern Recognition (San Diego, Calif.), IEEE Computer Society Press, Washington, pp. 576-581.
	92	TENENBAUM, J. M. AND BARROW, H. G. 1977 Experiments in interpretation-guided segmentation. Artif Intell. 8, 241-274.
	93	TENENBAUM, J. M., BARROW, H. G., BOLLES, R. C., FISCHLER, M. A., AND WOLF, H. C. 1979. Map-guided interpretation of remotely-sensed imagery. IEEE Pattern Recogn. Image Process., 610-617.
	94	Demetri Terzopoulos , Andrew Witkin , Michael Kass, Constraints on deformable models: recovering 3D shape and nongrid motion, Artificial Intelligence, v.36 n.1, p.91-123, August 1988 [doi>10.1016/0004-3702(88)90080-X]
	95	Tou, J. T. AND GONZALES, e. C. 1974. Pattern Recognition Principles, Addison-Wesley, Reading, Mass.
	96	A. M. Wallace, A comparison of approaches to high-level image interpretation, Pattern Recognition, v.21 n.3, p.241-259, 1988 [doi>10.1016/0031-3203(88)90059-3]
	97	WANG, C.-H. AND SRIt{ARr, S. N. 1988. A framework for object recognition in a visually complex environment and its application to locating address blocks on mail pieces. Int. J. Comput. Vision 2, 125-151.
	98	WHEELER, S. G. AND MISRA, P. N. 1980. Crop classification with landsat multispectral scanner data II. Pattern Reeogn. 12,219-228.
	99	Andrew Witkin , Kurt Fleischer , Alan Barr, Energy constraints on parameterized models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.225-232, July 1987
	100	WITKIN, A, TERZOPOULOS, D., AND KASS, M. 1987b. Signal matching through scale space. Int. d. Comput. Vtsion 1, 2, 133 144.
	101	Wv, Q., SUETENS, P., AND OOSTERLINCK, A. 1987. Toward an expert system for chromosome analysis. Knowledge-Based Syst. 1, 1, 43-52.
	102	Wu, Q., SUETENS, P., AND OOSTERHNCK, A. 1989 On knowledge-based improvement of biomedical pattern recognition: A case study. In Proceedings of the 5th IEEE Conference on Artificial Intelligence Applications (Miami, Fla.), IEEE, pp. 239-244.
	103	H. Yamada , C. Merritt , T. Kasvand, Recognition of Kidney Glomerulus by Dynamic Programming Matching Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.731-737, September 1988 [doi>10.1109/34.6784]
	104	Zhen Zhang , M. Simaan, A rule-based interpretation system for segmentation of seismic images, Pattern Recognition, v.20 n.1, p.45-53, 1987 [doi>10.1016/0031-3203(87)90016-1]