Abstract
Convexity is one of the useful geometric properties of digital sets in digital image processing. There are various applications which require deforming digital convex sets while preserving their convexity. In this article, we consider the contraction of such digital sets by removing digital points one by one. For this aim, we use some tools of combinatorics on words to detect a set of removable points and to define such convexity-preserving contraction of a digital set as an operation of re-writing its boundary word. In order to chose one of removable points for each contraction step, we present three geometrical strategies, which are related to vertex angle and area changes. We also show experimental results of applying the methods to repair some non-convex digital sets, which are obtained by rotations of convex digital sets.
This work was partly funded by the French National Research Agency, grant agreements ANR-10-LABX-58 (Labex Bézout) and ANR-15-CE40-0006 (CoMeDiC).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Berstel, J., Lauve, A., Reutenauer, C., Saliola, F.: Combinatorics on words: Christoffel words and repetition in words (2008)
Borel, J.-P., Laubie, F.: Quelques mots sur la droite projective réelle. J. de théorie des nombres de Bordeaux 5(1), 23–51 (1993)
Brlek, S., Lachaud, J.-O., Provençal, X., Reutenauer, C.: Lyndon+ Christoffel=digitally convex. Pattern Recognit. 42(10), 2239–2246 (2009)
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S.: Combinatorial aspects of L-convex polyominoes. Eur. J. Comb. 28(6), 1724–1741 (2007)
Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: Enumeration of l-convex polyominoes by rows and columns. Theor. Comput. Sci. 347(1–2), 336–352 (2005)
Charrier, E., Buzer, L.: Approximating a real number by a rational number with a limited denominator: a geometric approach. Discrete Appl. Math. 157(16), 3473–3484 (2009)
Chen, K., Fox, R., Lyndon, R.: Free differential calculus IV. The quotient groups of the lower central series. Ann. Math. 68, 81–95 (1958)
Christoffel, E.: Observatio arithmetica. Annali di Matematica Pura ed Applicata (1867–1897), 6(1), 148–152 (1875)
Del Lungo, A., Duchi, E., Frosini, A., Rinaldi, S.: Enumeration of convex polyominoes using the ECO method. In: DMCS, pp. 103–116 (2003)
Del Lungo, A., Duchi, E., Frosini, A., Rinaldi, S.: On the generation and enumeration of some classes of convex polyominoes. Electron. J. Comb. 11(1), 60 (2004)
Dulio, P., Frosini, A., Rinaldi, S., Tarsissi, L., Vuillon, L.: First steps in the algorithmic reconstruction of digital convex sets. In: Brlek, S., Dolce, F., Reutenauer, C., Vandomme, É. (eds.) WORDS 2017. LNCS, vol. 10432, pp. 164–176. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66396-8_16
Duval, J.: Mots de lyndon et périodicité. RAIRO, Informatique théorique 14(2), 181–191 (1980)
Freeman, H.: On the encoding of arbitrary geometric configurations. IRE Trans. Electron. Comput. 2, 260–268 (1961)
Hayes, A.C., Larman, D.G.: The vertices of the knapsack polytope. Discrete Appl. Math. 6(2), 135–138 (1983)
Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Publishers Inc., San Francisco (2004)
Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 90. Cambridge University Press, Cambridge (2002)
Lyndon, R.: Identities in finite algebras. Proc. Am. Math. Soc. 5(1), 8–9 (1954)
Minsky, M., Papert, S.: Perceptrons. MIT Press, Cambridge (1969)
Pick, G.: Geometrisches zur zahlenlehre. Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines für Böhmen “Lotos” in Prag., vol. 47–48, pp. 1899–1900 (1906)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Tarsissi, L., Coeurjolly, D., Kenmochi, Y., Romon, P. (2020). Convexity Preserving Contraction of Digital Sets. In: Palaiahnakote, S., Sanniti di Baja, G., Wang, L., Yan, W. (eds) Pattern Recognition. ACPR 2019. Lecture Notes in Computer Science(), vol 12047. Springer, Cham. https://doi.org/10.1007/978-3-030-41299-9_48
Download citation
DOI: https://doi.org/10.1007/978-3-030-41299-9_48
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-41298-2
Online ISBN: 978-3-030-41299-9
eBook Packages: Computer ScienceComputer Science (R0)