Abstract
Symmetry is an important cue in shape analysis. It has lead to the definition of popular shape descriptors like the medial axis. Its properties have been analyzed with a superset, called the symmetry set which represents the midpoints of circles that are at least bitangent to a shape.
In this work we investigate the pre-symmetry set. This set considers the pairs of points at which the bitangent contact occurs. One thus obtains pairwise symmetric points of a 2D shape. A closed 2D shape has a parameterization P with finite length. Its pre-symmetry can therefore be represented by a symmetric diagram curves formed from the pairs of points (p i ,p j )∈S 1×S 1.
We discuss the properties of the pre-symmetry set visualized by this diagram. We firstly give the so-called transitions, changes caused by a perturbation of the shape and show the changes of the curves in the pre-symmetry set diagram. Secondly, we investigate curves that are spanned by all points on the shape. We name the curves essential loops and discuss their properties and transitions. As one important result we show that their are either zero or two essential loops. In the latter case a part of the medial axis is spanned by an essential loop and can therefore be considered as the main axis of the medial axis.
As application of pre-symmetry sets, we discuss two possibilities for shape matching based on representations of the pre-symmetry set. The first shape descriptor we present is given by a circular diagram representing the shape, with a set of points representing the extrema of the curvature in the order they appear on the shape. They are pairwise connected and endowed with a length measure. This descriptor is directly related to the curves and their lengths in the pre-symmetry set diagram. The second descriptor is given by a binary array representing the areas enclosed by the curves in the pre-symmetry set diagram. It is area based and relates to the geometric derivation of the symmetry set.
Similar content being viewed by others
Notes
I would like to thank Peter Giblin from Liverpool University for providing this example, see also [40].
References
Adluru, N., Latecki, L.J.: Contour grouping based on contour-skeleton duality. Int. J. Comput. Vis. 83(1), 12–29 (2009)
Blake, A., Taylor, M.: Planning planar grasps of smooth contours. In: Proceedings IEEE International Conference on Robotics and Automation, vol. 2, pp. 834–839 (1993)
Blake, A., Taylor, M., Cox, A.: Grasping visual symmetry. In: Proceedings Fourth International Conference on Computer Vision, pp. 724–733 (1993)
Blum, H.: Biological shape and visual science (part I). J. Theor. Biol. 38, 205–287 (1973)
Bruce, J.W., Giblin, P.J.: Growth, motion and 1-parameter families of symmetry sets. Proc. R. Soc. Edinb. 104(A), 179–204 (1986)
Bruce, J.W., Giblin, P.J., Gibson, C.: Symmetry sets. Proc. R. Soc. Edinb. 101(A), 163–186 (1985)
Cao, F.: Geometric Curve Evolution and Image Processing. Lecture Notes in Mathematics, vol. 1805. Springer, Berlin (2003)
Dirks, R.M., Bois, J.S., Schaeffer, J.M., Winfree, E., Pierce, N.A.: Thermodynamic analysis of interacting nucleic acid strands. SIAM Rev. 49(1), 65–88 (2007)
Giblin, P.J., Brassett, S.A.: Local symmetry of plane curves. Am. Math. Mon. 92(10), 689–707 (1985)
Giblin, P.J., Kimia, B.B.: On the intrinsic reconstruction of shape from its symmetries. IEEE Trans. Pattern Anal. Mach. Intell. 25(7), 895–911 (2003)
Giblin, P.J., Kimia, B.B.: On the local form and transitions of symmetry sets, medial axes, and shocks. Int. J. Comput. Vis. 54(1/2), 143–156 (2003)
Gorelick, L., Galun, M., Sharon, E., Basri, R., Brandt, A.: Shape representation and classification using the Poisson equation. IEEE Trans. Pattern Anal. Mach. Intell. 28(12), 1991–2005 (2006)
Havukkala, I., Pang, S., Jain, V., Kasabov, N.: Classifying microRNAs by Gabor filter features from 2D structure bitmap images on a case study of human microRNAs. J. Comput. Theor. Nanosci. 2(4), 506–513 (2005). Special Issue on Computational Intelligence for Bioinformatics
Havukkala, I., Benuskova, L., Pang, P., Jain, V., Kroon, R., Kasabov, N.: Image and fractal information processing for large-scale chemoinformatics, genomics analyses and pattern discovery. In: Lecture Notes in Bioinformatics, vol. 4146, pp. 163–173. Springer, Berlin (2006)
Kimia, B.B.: On the role of medial geometry in human vision. J. Physiol. 97(2–3), 155–190 (2003)
Kimmel, R., Sochen, N., Weickert, J. (eds.): Scale Space and PDE Methods in Computer Vision. Lecture Notes in Computer Science, vol. 3459. Springer, Berlin (2005)
Koenderink, J.J.: Solid Shape. MIT Press, Cambridge (1990)
Kuijper, A., Havukkala, I.: Computationally efficient matching of microRNA shapes using mutual symmetry. In: 9th International Conference on Signal and Image Processing, SIP 2007, August 20–22, 2007, Honolulu, Hawaii, USA, pp. 477–482 (2007)
Kuijper, A., Olsen, O.F.: Transitions of the pre-symmetry set. In: Proceedings of the 17th International Conference on Pattern Recognition, vol. III, pp. 190–193 (2004)
Kuijper, A., Olsen, O.F.: Essential loops and their relevance for skeletons and symmetry sets. In: Olsen et al. [30], pp. 24–35 (2005)
Kuijper, A., Olsen, O.F.: The structure of shapes: scale space aspects of the (pre-) symmetry set. In: Kimmel et al. [16], pp. 291–302 (2005)
Kuijper, A., Olsen, O.F.: Describing and matching 2D shapes by their points of mutual symmetry. In: 9th European Conference on Computer Vision, Graz, Austria, May 7–13, 2006, Part III. LNCS, vol. 3953, pp. 213–225 (2006)
Kuijper, A., Olsen, O.F., Giblin, P.J., Bille, Ph., Nielsen, M.: From a 2D shape to a string structure using the symmetry set. In: Proceedings of the 8th European Conference on Computer Vision, vol. II. LNCS, vol. 3022, pp. 313–326 (2004)
Kuijper, A., Olsen, O.F., Giblin, P.J., Bille, Ph.: Matching shapes using the symmetry set. In: International Conference on Pattern Recognition, 20–24 August 2006, Hong Kong, vol. II, pp. 179–182 (2006)
Kuijper, A., Olsen, O.F., Giblin, P.J., Nielsen, M.: Alternative 2D shape representations using the symmetry set. J. Math. Imaging Vis. 26(1/2), 127–147 (2006)
Mi, X., DeCarlo, D.: Separating parts from 2d shapes using relatability. In: IEEE 11th International Conference on Computer Vision, ICCV 2007, Rio de Janeiro, Brazil, October 14–20, 2007, pp. 1–8 (2007)
Mi, X., DeCarlo, D., Stone, M.: Abstraction of 2d shapes in terms of parts. In: Proceedings of the 7th International Symposium on Non-photorealistic Animation and Rendering (NPAR) 2009, New Orleans, Louisiana, USA, August 1–2, 2009, pp. 15–24 (2009)
Mokhtarian, F., Bober, M.Z.: Curvature Scale Space Representation: Theory, Applications, & Mpeg-7 Standardization. Computational Imaging and Vision Series, vol. 25. Kluwer Academic, Dordrecht (2003)
Ogniewicz, R.L., Kübler, O.: Hierarchic Voronoi skeletons. Pattern Recognit. 28(3), 343–359 (1995)
Olsen, O.F., Florack, L.M.J., Kuijper, A. (eds.): Deep Structure, Singularities, and Computer Vision. Lecture Notes in Computer Science, vol. 3753. Springer, Berlin (2005). ISBN 978-3-540-29836-6
Pelillo, M., Siddiqi, K., Zucker, S.: Matching hierarchical structures using association graphs. IEEE Trans. Pattern Anal. Mach. Intell. 21(11), 1105–1120 (1999)
Polyak, M., Viro, O.: Gauss diagram formulas for Vassiliev invariants. Int. Math. Res. Notes 11, 445–454 (1994)
Sanniti di Baja, G.: On medial representations. In: Proceedings of 13th Iberoamerican Congress on Pattern Recognition, CIARP 2008. LNCS, vol. 5197, pp. 1–13 (2008)
Sebastian, T.B., Kimia, B.B.: Curves vs. skeletons in object recognition. Signal Process. 85(2), 247–263 (2005)
Sebastian, T.B., Klein, P.N., Kimia, B.B.: Recognition of shapes by editing shock graphs. In: Proceedings of the 8th International Conference on Computer Vision, pp. 755–762 (2001)
Sebastian, T.B., Klein, P.N., Kimia, B.B.: Recognition of shapes by editing shock graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(5), 550–571 (2004)
Sharvit, D., Chan, J., Tek, H., Kimia, B.B.: Symmetry-based indexing of image databases. J. Vis. Commun. Image Represent. 9(4), 366–380 (1998)
Siddiqi, K., Kimia, B.B.: A shock grammar for recognition. In: Proceedings CVPR’96, pp. 507–513 (1996)
Siddiqi, K., Pizer, S. (eds.): Medial Representations: Mathematics, Algorithms and Applications. Computational Imaging and Vision Series, vol. 37. Kluwer Academic, Dordrecht (2008)
Tabachnikov, S.: The (un)equal tangents problem. Am. Math. Mon. 110, 398–405 (2012)
Trinh, N.H., Kimia, B.B.: Skeleton search: category-specific object recognition and segmentation using a skeletal shape model. Int. J. Comput. Vis. 94(2), 215–240 (2011)
Vassiliev, V.A.: Homology of spaces of knots in any dimensions. Philos. Trans., Math. Phys. Eng. Sci. 359(1784), 1343–1364 (2001)
Zhang, D., Lu, G.: Review of shape representation and description techniques. Pattern Recognit. 37(1), 1–19 (2004)
Acknowledgements
This work was partially supported by the Deep Structure, Singularities, and Computer Vision (DSSCV) project, an IST Programme of the European Union (IST-2001-35443), and carried out by the author while he was at the IT University of Copenhagen, Denmark. Parts of this work were presented at several conferences [19, 20, 22, 24]. I would like to thank my colleagues Peter Giblin at the University of Liverpool, UK, and Ole Fogh Olsen, Mads Nielsen, and Philip Bille at the (IT) University of Copenhagen, Denmark, for the stimulating discussions leading to those publications which formed the starting point for this paper, and the reviewers for suggestions to improve the readability of this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kuijper, A. On the Local Form and Transitions of Pre-symmetry Sets. J Math Imaging Vis 45, 13–30 (2013). https://doi.org/10.1007/s10851-012-0341-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-012-0341-3