loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Object Matching Using Deformable Templates
March 1996 (vol. 18 no. 3)
pp. 267-278

Abstract—We propose a general object localization and retrieval scheme based on object shape using deformable templates. Prior knowledge of an object shape is described by a prototype template which consists of the representative contour/edges, and a set of probabilistic deformation transformations on the template. A Bayesian scheme, which is based on this prior knowledge and the edge information in the input image, is employed to find a match between the deformed template and objects in the image. Computational efficiency is achieved via a coarse-to-fine implementation of the matching algorithm. Our method has been applied to retrieve objects with a variety of shapes from images with complex background. The proposed scheme is invariant to location, rotation, and moderate scale changes of the template.

[1] 267 Y. Amit and U. Grenander, and M. Piccioni, "Structural image restoration through deformable template," J. Am. Statistical Assn., vol. 86, no. 414, pp. 376-387, June 1991.[2] D.H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes, Pattern Recognition, vol. 13, no. 2, pp. 111-122, 1981.[3] D.J. Burr, "Elastic matching of line drawings," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 3, no. 6, pp. 708-713, Nov. 1981.[4] A. Chakraborty, L.H. Staib, and J.S. Duncan, "Deformable boundary finding influenced by region homogeneity," Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR),Seattle, pp. 624-627, June 1994.[5] Y.S. Chow, U. Grenander, and D.M. Keenan, HANDS. A Pattern-Theoretic Study Of Biological Shapes.New York: Springer-Verlag, 1991.[6] L.D. Cohen and I. Cohen, “Finite-Element Methods for Active Contour Models and Balloons for 2D and 3D Images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1,131-1,147, Nov. 1993.[7] T.F. Cootes, C.J. Taylor, and A. Lanitis, "Active shape models: Evaluation of a multi-resolution method for improving image search," Proc. British Machine Vision Conf.," vol 1, pp. 327-336, 1994[8] R.O. Duda and P.E. Hart, "Use of the Hough transforms to detect lines and curves in pictures," Comm. ACM, vol. 15, no. 1, pp. 11-15, 1972[9] C. Faloutsos, R. Barber, M. Flicker, J. Hafner, W. Niblack, and W. Equitz, "Efficient and effective querying by image content," J. Intell. Information Systems," vol. 3, pp. 231-262, 1994.[10] M. Figueiredo and J. Leitao, "Bayesian estimation of ventricular contours in angiographic images, IEEE Trans. Medical Imaging, vol. 11, no. 3, pp. 416-429, Sept. 1992[11] S.B. Gelfand and S.K. Mitter, "Metropolis-type annealing algorithms for global optimization in${\cal R}$," Siam J. Control and Optimization, vol. 31, no. 1, pp. 111-131, Jan. 1993.[12] S. Geman private communication, Apr. 1995.[13] S. Geman, D. Geman, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721-742, Nov. 1984.[14] S. Geman, C. Huang, "Diffusions for global optimazation," SIAM J. Control and Optimization, vol. 24, pp 1,031-1,043, Sept. 1986.[15] B. Gidas, "Global optimization via the Langevin equation," Proc. IEEE Conf. Decision and Control,Fort Lauderdale, Fla., pp. 774-778, 1985.[16] M.M. Gorkani and R.W. Picard, "Texture orientation for sorting photos at a glance," Proc. 12th Intl Conf. Pattern Recognition,Jerusalem, vol. 67, no. 5, pp. A459-A464, Oct. 1994.[17] U. Grenander, "Pattern synthesis: Lectures in pattern theory," Applied Mathematical Sciences. Springer-Verlag, vol. 18, 1976.[18] U. Grenander and D.M. Keenan, "Towards automated image understanding, Advances in Applied Statistics: Statistics and Images vol. 1," K.V. Mardia and G.K. Kanji, eds., Chap. 6, pp. 89-103. Carfax Publishing Company, 1993.[19] U. Grenander and M. I. Miller, "Representations of knowledge in complex systems," J. Royal Statistical Society, vol. 56, no. 3, pp. 1-33, 1994.[20] B. Holt and L. Hartwick, "Visual image retrieval for applications in art and art history," Proc. SPIE, vol. 2,185, pp. 70-81, Feb. 1994.[21] P.V.C. Hough, "Method and means for recognizing complex patterns," U.S. Patent 3069654, 1962.[22] J. Illingworth and J. Kitter, "A survey of Hough transform," CVGIP, vol. 44, pp. 87-116, 1988.[23] M. Kass, A. Witkin, and D. Terzopoulos, "Snakes: active contour models, IJCV, vol. 1, no. 4, pp. 321-331, 1988.[24] S. Lakshmanan and H. Grimmer, "Detecting straight edges in radar images using deformable templates," to appear, IEEE Trans. Pattern Analysis and Machine Intelligence.[25] V.F. Leavers, "Survey: Which Hough transform?," CVGIP: Image Understanding, vol. 58, no. 2, pp. 250-264, Sept. 1993.[26] F. Leymarie and M. Levine, "Tracking deformable objects in the plane using an active contour model, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 6, pp. 617-634, June 1993.[27] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Reller, and E. Teller, "Equations of state calculations by fast computing machines," J. Chem. Phys., vol. 21, pp. 1,087-1,092, 1953.[28] M.I. Miller, G.E. Christensen, Y. Amit, and U. Grenander, "Mathematical textbook of deformable neuroanatomies," Proc. Natl. Academy of Science, vol. 90, pp. 11,944-11,948, Dec. 1993.[29] M. Moshfeghi, S. Ranganath, and K. Nawyn, "Three-dimensional elastic matching of volumes," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 3, no. 2, pp. 128-138, Mar. 1994.[30] L.H. Staib and J.S. Duncan, “Boundary Finding with Parametrically Deformable Models,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 11, pp. 1,061-1,075, Nov. 1992.[31] G. Storvik, "A Bayesian approach to dynamic contours through stochastic sampling and simulated annealing," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 10, pp. 976-986, Oct. 1994[32] R. Szeliski and J. Coughlan, "Hierarchical spline-based registration," Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR),"Seattle, pp. 194-201, June 1994.[33] D. Terzopolous, A. Witkin, and M. Kass, "Constraints on deformable models: Recovering 3D shape and nonrigid motion, AI, no. 36, pp. 91-123, 1988.[34] A. Witkin, D. Terzopoulos, and M. Kass, "Signal matching through scale space," Int'l J. Computer Vision, pp. 133-144, 1987.[35] A.L. Yuille, P.W. Hallinan, and D.S. Cohen, "Feature extraction from faces using deformable templates," Int'l J. Computer Vision, vol. 8, no. 2, 133-144, 1992.

Index Terms:
Object matching, deformable templates, image database, image segmentation, Bayesian optimization, multi-resolution algorithm.
Citation:
Anil K. Jain, Yu Zhong, Sridhar Lakshmanan, "Object Matching Using Deformable Templates," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 3, pp. 267-278, Mar. 1996, doi:10.1109/34.485555
Usage of this product signifies your acceptance of the Terms of Use.