Efficient Recognition of Partially Visible Objects Using a Logarithmic Complexity Matching Technique

Abstract

An important task in computer vision is the recognition of partially visible two-dimensional objects in a gray scale image. Recent works addressing this problem have attempted to match spatially local features from the image to features generated by models of the objects. However, many algo rithms are considerably less efficient than they might be, typ ically being O(IN) or worse, where I is the number offeatures in the image and N is the number of features in the model set. This is invariably due to the feature-matching portion of the algorithm. In this paper we discuss an algorithm that significantly improves the efficiency offeature matching. In addition, we show experimentally that our recognition algo rithm is accurate and robust. Our algorithm uses the local shape of contour segments near critical points, represented in slope angle-arclength space (θ-s space), as fundamental fea ture vectors. These feature vectors are further processed by projecting them onto a subspace in θ-s space that is obtained by applying the Karhunen-Loève expansion to all such fea tures in the set of models, yielding the final feature vectors. This allows the data needed to store the features to be re duced, while retaining nearly all information important for recognition. The heart of the algorithm is a technique for performing matching between the observed image features and the precomputed model features, which reduces the runtime complexity from O(IN) to O(I log I + I log N), where I and N are as above. The matching is performed using a tree data structure, called a kD tree, which enables multidi mensional searches to be performed in O(log) time.

Get full access to this article

View all access options for this article.

References

Attneave, F. 1954. Some informational aspects of visual perception Psycholog. Rev. 61:183-193.

Ayache, N. , and Faugeras, O.D. 1986. HYPER: A new approach for the recognition and positioning of two-dimensional objects IEEE Trans. Pattern Anal. Mach. Intell. 8(1):44-54.

Ballard, D.H. 1981. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recog. 13(2):111-122.

Ballard, D.H. , and Sabbah, D. 1985. Viewer independent shape recognition. Proc. IEEE Conf. Pattern Recog. Image Process ., pp. 67-71.

Bentley, J.L. , and Friedman, J.H. 1979. Data structures for range searching Comp. Surv. 11(4):398-409.

Bhanu, B. , and Faugeras, O.D. 1984. Shape matching of two-dimensional objects IEEE Trans. Pattern Anal. Mach. Intell. 6(2):137-156.

Biederman, I. 1985, Human image understanding: Recent research and a theory . Comp. Vision, Graphics, Image Process . 32:29-73.

Blum, H. , and Nagel, R.N. 1978. Shape description using weighted symmetric axis features Pattern Recog. 10:167-180.

Bolles, R.C. , and Cain, R.A. 1982. Recognizing and locating partially visible objects: The local-feature-focus method Int. J. Robot. Res . 1(3):57-82.

10.

Bressenham, J.E. 1965. Algorithm for computer control of digital plotters IBM Sys. J. 4( 1 ):25- 30.

11.

Canny, J.F. 1983. Finding edges and lines in images Master's thesis, MIT, Cambridge, Mass.

12.

Chien, C.H. , and Aggarwal, J.K. 1987. Shape recognition from single silhouettes. Proc. IEEE First Int. Conf. Comp. Vision, pp. 481-490.

13.

Chin, R.T. , and Dyer, C.R. 1986. Model-based recognition in robot vision. Comp. Surv. 18(1):67-108.

14.

Cowan, C.K. , Chelberg, D.M. , and Lim, H.S. 1984. ACRONYM model based vision in the intelligent task automation project First Conf. AI Appl ., pp. 176-183.

15.

Dubois, S.R. , and Glanz, F.H. 1986. An autoregressive model approach to two-dimensional shape classification. IEEE Trans. Pattern Anal. Mach. Intell . 8(1):55-66.

16.

Freeman, H. 1977. Shape description via the use of critical points . Proc. IEEE Conf. Pattern Recog. Image Process ., pp. 168-174.

17.

Fu, K.S. 1974. Syntactic Methods in Pattern Recognition New York: Academic Press, 1974.

18.

Goad, C. 1983. Special purpose automatic programming for 3D model-based vision Proc. Image Understanding Workshop . DARPA, pp. 94-103.

19.

Gottschalk, P.G. , and Mudge, T. 1988. Efficient encoding of local shape: Features for 3-d object recognition Proc. SPIE: Intell. Robots Comp. Vision . Seventh in a Series, pp. 46-56.

20.

Gottschalk, P.G. , Turney, J.L. , and Mudge, T. 1987. Two-dimensional partially visible object recognition using efficient multidimensional range queries. Proc. IEEE Conf. Robot. Automat., pp. 1582-1589.

21.

Grimson, W.E.L. , and Lozano-Pérez, T. 1987. Localizing overlapping parts by searching the interpretation tree IEEE Trans. Pattern Anal. Mach. Intell. 9(4):469-482.

22.

Knoll, T.F. , and Jain, R.C. 1986. Recognizing partially visible objects using feature indexed hypotheses. IEEE J. Robot. Automat . 2(1):3-13.

23.

Koch, M.W. , and Kashyap, R.L. 1985. A vision system to identify occluded industrial parts Proc. IEEE Conf. Pattern Recog. Image Process ., pp. 55-60.

24.

Lamdan, Y. , Schwartz, J.T. , and Wolfson, H.J. 1988. On recognition of 3-d objects from 2-d images. Proc. IEEE Conf. Robot. Automat., pp. 1407-1413.

25.

Lowe, D.G. 1987. The viewpoint consistency constraint. Int. J. Comp. Vision 1(1):58-72.

26.

Mattill, J. 1976. The bin of parts problem and the ice-box puzzle . Technol. Rev. 78(7):18-19.

27.

McKee, J.W. , and Aggarwal, J.K. 1977. Computer recognition of partial views of curved objects . IEEE Trans. Comp. 26(8):790-800.

28.

Mudge, T.N. , Turney, J.L. , and Volz, R.A. 1987. Automatic generation of salient features for the recognition of partially occluded parts. Robotica , 5:117-127.

29.

Pavlidis, T. 1977. Structural Pattern Recognition New York: Springer.

30.

Perkins, W.A. 1978. A model-based vision system for industrial parts . IEEE Trans. Comp. 27(2):126-143.

31.

Rosenfeld, A. , and Kak, A.C. 1976

Digital Picture Processing

New York : Academic Press, pp. 109-123.

32.

Segen, J. 1983 (November). Locating randomly oriented shapes from partial views. Proc. Soc. Photo-optical In-strum. Eng. Cambridge Symp. Robot Vision and Sensory Controls, pp. 676-684.

33.

Schwartz, J.T. , and Sharir, M. 1986. Two-dimensional, model based boundary matching using footprints. Int. J. Robot. Res. 5(4):38-55.

34.

Tropf, H. 1980. Analysis-by-synthesis search for segmentation applied to workpiece recognition. Fifth IEEE Int. Conf. Pattern Recog., pp. 241- 244.

35.

Tsui, H.T. , and Chan, M.H. 1987. Recognition of partially occluded two-dimensional objects Comp. Digit. Tech., IEEE Proc. 134(1):9-16.

36.

Turney, J.L. 1986. Recognition of partially occluded parts. Ph.D. dissertation, Department of Electrical Engineering and Computer Science, University of Michigan.

37.

Turney, J.L. , Mudge, T. , and Volz, R.A. 1985. Recognizing partially occluded parts. IEEE Trans. Pattern Anal. Mach. Intell . 7(4):410-421.

38.

Turney, J.L. , Mudge, T. , and Volz, R.A. 1986. Solving the bin of parts problem. Vision 86 Conf. Proc., pp. 4-21-4-38.

39.

Yam, K.R. , Martin, W.N. , and Aggarwal, J.K. 1980. Analysis of scenes containing several occluding curvilinear objects TR-135. Austin, Texas: University of Texas at Austin.