Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Measure of Q-convexity for Shape Analysis

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

In this paper, we study three basic novel measures of convexity for shape analysis. The convexity considered here is the so-called Q-convexity, that is, convexity by quadrants. The measures are based on the geometrical properties of Q-convex shapes and have the following features: (1) their values range from 0 to 1; (2) their values equal 1 if and only if the binary image is Q-convex; and (3) they are invariant by translation, reflection, and rotation by 90 degrees. We design a new algorithm for the computation of the measures whose time complexity is linear in the size of the binary image representation. We investigate the properties of our measures by solving object ranking problems and give an illustrative example of how these convexity descriptors can be utilized in classification problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Notes

  1. The different conventions used to indexing an item in the matrix representation starting from the top left corner and a point in the Cartesian coordinate system starting from the bottom left corner result in the discrepancy in the indexing.

  2. This number provides the condition of termination of the algorithm (see Fig. 9)

References

  1. Alajlan, N., El Rube, I., Kamel, M.S., Freeman, G.: Shape retrieval using triangle-area representation and dynamic space warping. Pattern Recognit. 40, 1911–1920 (2007)

    Article  Google Scholar 

  2. Balázs, P., Ozsvár, Z., Tasi, T.S., Nyúl, L.G.: A measure of directional convexity inspired by binary tomography. Fundam. Inform. 141(2–3), 151–167 (2015)

    Article  MathSciNet  Google Scholar 

  3. Balázs, P., Brunetti, S.: A Measure of \({Q}\)-convexity. Lecture Notes in Computer Science 9647, Discrete Geometry for Computer Imagery (DGCI), pp. 219–230. Nantes, France (2016)

  4. Balázs, P., Brunetti, S.: A New Shape Descriptor Based on a \(Q\)-convexity Measure. Lecture Notes in Computer Science 1502, Discrete Geometry for Computer Imagery (DGCI), pp. 267–278. Vienna, Austria (2017)

  5. Balázs, P., Brunetti, S.: A \(Q\)-convexity vector descriptor for image analysis. J. Math. Imaging Vis. 61(2), 193–203 (2019)

    Article  MathSciNet  Google Scholar 

  6. Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Medians of polyominoes: a property for the reconstruction. Int. J. Imaging Syst. Technol. 9, 69–77 (1998)

    Article  Google Scholar 

  7. Blondin Masse, A., Brlek, S., Tremblay, H.: Efficient operations on discrete paths. Theor. Comput. Sci. 624, 121–135 (2016)

    Article  MathSciNet  Google Scholar 

  8. Boxer, L.: Computing deviations from convexity in polygons. Pattern Recogn. Lett. 14, 163–167 (1993)

    Article  Google Scholar 

  9. Brlek, S., Tremblay, H., Tremblay, J., Weber, R.: Efficient Computation of the Outer Hull of a Discrete Path. Lecture Notes in Computer Science 8668, Discrete Geometry for Computer Imagery (DGCI), pp. 122–133. Siena, Italy (2014)

  10. Brunetti, S., Daurat, A.: Random generation of \(Q\)-convex sets. Theor. Comput. Sci. 347(1–2), 393–414 (2005)

    Article  MathSciNet  Google Scholar 

  11. Brunetti, S., Daurat, A.: Reconstruction of convex lattice sets from tomographic projections in quartic time. Theor. Comput. Sci. 406(1–2), 55–62 (2008)

    Article  MathSciNet  Google Scholar 

  12. Chrobak, M., Dürr, C.: Reconstructing \(hv\)-convex polyominoes from orthogonal projections. Inform. Process. Lett. 69(6), 283–289 (1999)

    Article  MathSciNet  Google Scholar 

  13. Daurat, A.: Salient points of \(Q\)-convex sets. Int. J. Pattern Recognit. Artifi. Intell. 15(7), 1023–1030 (2001)

    Article  Google Scholar 

  14. Daurat, A., Nivat, M.: Salient and reentrant points of discrete sets. Electron. Notes Discrete Math. 12, 208–219 (2003)

    Article  MathSciNet  Google Scholar 

  15. Gonzalez, R.C., Woods, R.E.: Digital Image Processing, 3rd edn. Prentice Hall, New Jersey (2008)

    Google Scholar 

  16. Gorelick, L., Veksler, O., Boykov, Y., Nieuwenhuis, C.: Convexity Shape Prior for Segmentation. Lecture Notes in Computer Science 8693, European Conference on Computer Vision (ECCV), pp. 675–690. Switzerland, Zürich (2014)

  17. Gorelick, L., Veksler, O., Boykov, Y., Nieuwenhuis, C.: Convexity shape prior for binary segmentation. In: IEEE transactions on pattern analysis and machine intelligence, pp. 258–271 (2017)

  18. Hu, M.K.: Visual pattern recognition by moment invariants. IRE Trans. Inform. Theory 8, 179–187 (1962)

    MATH  Google Scholar 

  19. Latecki, L.J., Lakamper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vis. Image Underst. 73(3), 441–454 (1999)

    Article  Google Scholar 

  20. Pavel, P., Novovičová, J., Kittler, J.: Floating search methods in feature selection. Pattern Recognit. Lett. 15(11), 1119–1125 (1994)

    Article  Google Scholar 

  21. Popov, A.T.: Convexity indicators based on fuzzy morphology. Pattern Recognit. Lett. 18, 259–267 (1997)

    Article  Google Scholar 

  22. Rahtu, E., Salo, M., Heikkila, J.: A new convexity measure based on a probabilistic interpretation of images. IEEE Trans. Pattern Anal. Mach. Intell. 28(9), 1501–1512 (2006)

    Article  Google Scholar 

  23. Rosin, P.L., Žunić, J.: Probabilistic convexity measure. IET Image Process. 1(2), 182–188 (2007)

    Article  Google Scholar 

  24. Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis, and Machine Vision, 3rd edn. Thomson Learning, Toronto (2008)

    Google Scholar 

  25. Stern, H.: Polygonal entropy: a convexity measure. Pattern Recognit. Lett. 10, 229–235 (1998)

    Article  Google Scholar 

  26. Wang, X., Feng, B., Bai, X., Liu, W., Latecki, L.J.: Bag of contour fragments for robust shape classification. Pattern Recognit. 47, 2116–2125 (2014)

    Article  Google Scholar 

  27. Žunić, J., Rosin, P.L.: A new convexity measure for polygons. IEEE Trans. Pattern Anal. Mach. Intell. 26(7), 923–934 (2004)

    Article  Google Scholar 

Download references

Acknowledgements

The authors thank P.L. Rosin for providing the datasets used in [23].

We wish to thank the anonymous reviewers for their comments that greatly improved the paper.

The research was carried out during the visit of P. Balázs at the University of Siena. The authors gratefully acknowledge INdAM support for this visit through the “visiting professors” project. S. Brunetti is also member of Gruppo Nazionale per il Calcolo Scientifico – Istituto Nazionale di Alta Matematica.

Funding

This research was supported by the project “Integrated program for training new generation of scientists in the fields of computer science,” no. EFOP-3.6.3-VEKOP- 16-2017-00002. This research was supported by grant TUDFO/47138-1/2019-ITM of the Ministry for Innovation and Technology, Hungary.

Author information

Authors and Affiliations

  1. Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2., Szeged, 6720, Hungary

    Péter Balázs

  2. Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Via Roma, 56, 53100, Siena, Italy

    Sara Brunetti

Authors
  1. Péter Balázs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sara Brunetti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sara Brunetti.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Balázs, P., Brunetti, S. A Measure of Q-convexity for Shape Analysis. J Math Imaging Vis 62, 1121–1135 (2020). https://doi.org/10.1007/s10851-020-00962-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-020-00962-9

Keywords

Search

Navigation