Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-26T17:07:35.187Z Has data issue: false hasContentIssue false

10 - Representing and Matching Shape

from Part III - Image Understanding

Published online by Cambridge University Press:  25 October 2017

Wesley E. Snyder  and
Hairong Qi
Wesley E. Snyder
Affiliation:
North Carolina State University
Hairong Qi
Affiliation:
University of Tennessee
Get access

Summary

Shape is what is left when the effects associated with translation, scaling, and rotation are filtered away.

– David Kendall

Introduction

In this chapter, we assume a successful segmentation, and explore the question of characterization of the resulting regions. We begin by considering two-dimensional regions that are denoted by each pixel in the region having value 1 and all background pixels having value 0.We assume only one region is processed at a time, since in studying segmentation, we learned how to realize these assumptions.

When thinking about shapes, and measures for shapes, it is important to keep in mind that certain measures may have invariance properties. That is, a measure may remain the same if the object is (for example) rotated. Consider the height of a person in a picture – if the camera rotates, the apparent height of the person will change, unless, of course, the person rotates with the camera.

The common transformations considered in this chapter are those described by some linear operation on the shape matrix, discussed in section 4.2.3.

In the remainder of this chapter, we will be constantly thinking about operations that exhibit various invariances, and can be used to match shapes of regions.

  • • (Section 10.2) To understand invariances, we must first understand the deformations that may alter the shape of a region, and most of those can be described by matrix operations.

  • • (Section 10.3) One particularly important matrix is the covariance matrix of the distribution of points in a region, since the eigenvalues and eigenvectors of that matrix describe shape in a very robust way.

  • • (Section 10.4) In this section, we introduce some important features used to describe a region. We start from some simple properties of a region like perimeter, diameter, and thinness. We then extend the discussion to some invariant features (to various linear transformations) like moments, chain codes, Fourier descriptors, and the medial axis.

  • • (Section 10.5) Since, in earlier sections, we have represented the regions by sets of numbers called features, in this section, we discuss how to match such sets of numbers.

    • Type
    Chapter
    Information
    Fundamentals of Computer Vision , pp. 218 - 266
    Publisher: Cambridge University Press
    Print publication year: 2017

    Access options

    Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

    References

    [10.1] S., Abbasi, F., Mokhtarian, and J., Kittler. Curvature scale space image in shape similarity retrieval. Multimedia Syst., 7 (6), 1999.Google Scholar
    [10.2] V., Anh, J., Shi, and H., Tsai. Scaling theorems for zero crossings of bandlimited signals. IEEE Trans. Pattern Anal. and Machine Intel., 18 (3), 1996.Google Scholar
    [10.3] H., Arbter,W., Snyder, H., Burkhardt, and G., Hirzinger. Application of affine-invariant fourier descriptors to recognition of 3-d objects. IEEE Trans. Pattern Anal. and Machine Intel., 12 (7), July 1990.Google Scholar
    [10.4] S., Belongie and J., Malik.Matching with shape context. In IEEE Workshop on Content-based Access of Image and Video Libraries (CBAIVL-2000), 2000.
    [10.5] S., Belongie, J., Malik, and J., Puzicha. Shape matching and object recognition using shape contexts. In Technical Report UCB//CSD00 -1128. UC Berkeley, January 2001.
    [10.6] S., Belongie, J., Malik, and J., Puzicha. Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. and Machine Intel., 24 (4), April 2002.Google Scholar
    [10.7] A., Califano and R., Mohan. Multidimensional indexing for recognizing visual shapes. IEEE Trans. Pattern Anal. and Machine Intel., 16 (4), April 1994.Google Scholar
    [10.8] J., Chuang, C., Tsai, and M., Ko. Skeletonization of three-dimensional object using generalized potential field. IEEE Trans. Pattern Anal. and Machine Intel., 22 (11), November 2000.Google Scholar
    [10.9] G., Dantzig. Origins of the simplex method A history of scientific computing. Systems Optimization Laboratory, Stanford University, 1987.
    [10.10] R. O., Duda, P. E., Hart, and D. G., Stork. Pattern Classification. Wiley Interscience, 2nd edition, 2000.
    [10.11] A., Ferreira and S., Ubeda. Computing the medial axis transform in parallel with eight scan operations. IEEE Trans. Pattern Anal. and Machine Intel., 21 (3), March 1999.Google Scholar
    [10.12] R., Gonzalez and P., Wintz. Digital Image Processing. Pearson, 1977.
    [10.13] M., Gruber and K., Hsu. Moment-based image normalization with high noise-tolerance. IEEE Trans. Pattern Anal. and Machine Intel., 19 (2), February 1997.Google Scholar
    [10.14] D., Helman and J., JáJá. Efficient image processing algorithms on the scan line array processor. IEEE Trans. Pattern Anal. and Machine Intel., 17 (1), January 1995.Google Scholar
    [10.15] M., Hu. Visual pattern recognition by moment invariants. IRE Trans. Information Theory, 8, 1962.Google Scholar
    [10.16] K., Sohn, J., Kim, and S., Yoon. A robust boundary-based object recognition in occlusion environment by hybrid hopfield neural networks. Pattern Recognition, 29 (12), December 1996.Google Scholar
    [10.17] R., Jonker and A., Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38, 1987.Google Scholar
    [10.18] S., Joshi, E., Klassen, A., Srivastava, and I., Jermyn. A novel representation for Riemannian analysis of elastic curves in Rn. In Computer Vision and Pattern Recognition, CVPR07, June 2007.
    [10.19] K., Kanatani. Comments on symmetry as a continuous feature. IEEE Trans. Pattern Anal. and Machine Intel., 19 (3), March 1997.Google Scholar
    [10.20] H., Kauppinen, T., Seppnen, and M., Pietikinen. An experimental comparison of autoregressive and Fourier-based descriptors in 2d shape classification. IEEE Trans. Pattern Anal. and Machine Intel., 17 (2), February 1995.Google Scholar
    [10.21] D. G., Kendall, D., Barden, T. K., Carne, and H., Le. Shape and Shape Theory. Wiley, 1999.
    [10.22] K., Krish, S., Heinrich, W., Snyder, H., Cakir, and S., Khorram. A new feature based image registration algorithm. In ASPRS 2008 Annual Conference, April 2008.
    [10.23] Harold W., Kuhn. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2, 1955.Google Scholar
    [10.24] S., Liao and M., Pawlak. On image analysis by moments. IEEE Trans. Pattern Anal. and Machine Intel., 18 (3), March 1996.Google Scholar
    [10.25] F, Mokhtarian, S, Abbasi, and J, Kittler. Efficient and robust retrieval by shape through curvature scale space. In Proceedings of the First International Workshop on Image Databases and Multi-Media Search, pages 35–42, August 1996.
    [10.26] T., Nguyen and B., Oommen. Moment-preserving piecewise linear approximations of signals and images. IEEE Trans. Pattern Anal. and Machine Intel., 19 (1), January 1997.Google Scholar
    [10.27] Euclid of Alexandria. Elements. Unknown, 300 BC.
    [10.28] L., O'Gorman. Subpixel precision of straight-edged shapes for registration and measurement. IEEE Trans. Pattern Anal. and Machine Intel., 18 (7), 1996.Google Scholar
    [10.29] S., Pizer, C., Burbeck, J., Coggins, D., Fritsch, and B., Morse. Object shape before boundary shape: Scale space medial axis. J. Math. Imaging and Vision, 4, 1994.Google Scholar
    [10.30] I., Rothe, H., Süsse, and K., Voss. The method of normalization to determine invariants. IEEE Trans. Pattern Anal. and Machine Intel., 18 (4), 1996.Google Scholar
    [10.31] G., Sandini and V., Tagliasco. An anthropomorphic retina-like structure for scene analysis. Computer Graphics and Image Processing, 14, 1980.Google Scholar
    [10.32] E., Schwartz. Computational anatomy and functional architecture of the striate cortex: a spatial mapping approach to perceptual coding. Vision Res., 20, 1980.Google Scholar
    [10.33] M., Shamos. Geometric complexity. In 7th Annual ACM Symposium on Theory of Computation, 1975.
    [10.34] D., Sinclair and A., Blake. Isoperimetric normalization of planar curves. IEEE Trans. Pattern Anal. and Machine Intel., 16 (8), August 1994.Google Scholar
    [10.35] W., Snyder and I., Tang. Finding the extrema of a region. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980.
    [10.36] C., Therrien. Decision, Estimation, and Classification. Wiley, 1989.
    [10.37] F., Tong and Z., Li. Reciprocal-wedge transform for space-variant sensing. IEEE Trans. Pattern Anal. and Machine Intel., 17 (5), May 1995.Google Scholar
    [10.38] A., Veeraraghavan, A., Roy-Chowhury, and R., Chellappa.Matching shape sequences in video with applications in human movement analysis. IEEE Trans. on Pattern Analy. and Machine Intel., 27 (12), 2005.Google Scholar
    [10.39] C., Weiman and G., Chaikin. Logarithmic spiral grids for image processing and display. Computer Graphics and Image Processing, 11, 1979.Google Scholar
    [10.40] D., Weinshall and C., Tomasi. Linear and incremental acquisition of invariant shape models from image sequences. IEEE Trans. Pattern Anal. and Machine Intel., 17 (5), May 1995.Google Scholar
    [10.41] M., Werman and D., Weinshall. Similarity and affine invariant distances between 2d point sets. IEEE Trans. Pattern Anal. and Machine Intel., 17 (8), August 1995.Google Scholar
    [10.42] R., Yip, P., Tam, and D., Leung. Application of elliptic Fourier descriptors to symmetry detection under parallel projection. IEEE Trans. Pattern Anal. and Machine Intel., 16 (3), March 1994.Google Scholar
    [10.43] H., Zabrodsky, S., Peleg, and D., Avnir. Symmetry as a continuous feature. IEEE Trans. Pattern Anal. and Machine Intel., 17 (12), December 1995.Google Scholar
    [10.44] D., Zhang and G., Lu. A comparative study of curvature scale space and fourier descriptors for shape-based image retrieval. Journal of Visual Communication and Image Representation, 14 (1), March 2002.Google Scholar

    Save book to Kindle

    To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

    Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

    Find out more about the Kindle Personal Document Service.

    Available formats
    ×

    Save book to Dropbox

    To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

    Available formats
    ×

    Save book to Google Drive

    To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

    Available formats
    ×