Abstract
In this article, we propose algorithms for pixelwise deformations of digital convex sets preserving their convexity using the combinatorics on words to identify digital convex sets via their boundary words, namely Lyndon and Christoffel words. The notion of removable and insertable points are used with a geometric strategy for choosing one of those pixels for each deformation step. The worst-case time complexity of each deflation and inflation step, which is the atomic deformation, is also analysed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Acketa, D.M., Žunić, J.: On the maximal number of edges of convex digital polygons included into an m x m-grid. J. Comb. Theor. Ser. A 69, 358–368 (1995)
Alexander, J.C., Thaler, A.I.: The boundary count of digital pictures. J. ACM 18(1), 105–112 (1971)
Andrews, G.: A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Am. Math. Soc. 106, 270–279 (1963)
Berstel, J.: Tracé de droites, fractions continues et morphismes itérés. In: Mots, pp. 298–309. Hermès (1990)
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)
Borel, J.P., Laubie, F.: Construction de mots de Christoffel. Comptes Rendus de l’Académie des Sciences. Série I. Mathématique 313(8), 483–485 (1991)
Brlek, S., Lachaud, J.O., Provençal, X., Reutenauer, C.: Lyndon + christoffel = digitally convex. Pattern Recogn. 42(10), 2239–2246 (2009)
Chen, K.T., Fox, R.H., Lyndon, R.C.: Free differential calculus, iv. the quotient groups of the lower central series. Ann. Math. 68(1), 81–95 (1958)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 2nd edn. MIT Press, Cambridge (2001)
Crombez, L.: Digital convex + unimodular mapping = 8-connected (all points but one 4-connected). In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) DGMM 2021. LNCS, vol. 12708, pp. 164–176. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-76657-3_11
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.P.: Factorizing words over an ordered alphabet. J. Algorithms 4(4), 363–381 (1983)
Eckhardt, U.: Digital lines and digital convexity. In: Bertrand, G., Imiya, A., Klette, R. (eds.) Digital and Image Geometry. LNCS, vol. 2243, pp. 209–228. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45576-0_13
Freeman, H.: On the Encoding of Arbitrary Geometric Configurations. IRE Trans. Electron. Comput. EC-10(2), 260–268 (1961)
Kim, C.E.: On the Cellular Convexity of Complexes. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-3(6), 617–625 (1981)
Kong, T.Y., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vision Graph. Image Process. 48(3), 357–393 (1989)
Lachaud, J.-O.: An alternative definition for digital convexity. J. Math. Imaging Vision , 1–18 (2022). https://doi.org/10.1007/s10851-022-01076-0
Lothaire, M.: Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge (2002)
Lyndon, R.C.: On burnside’s problem. Trans. Am. Math. Soc. 77(2), 202–215 (1954)
Roussillon, T.: An arithmetical characterization of the convex hull of digital straight segments. In: Barcucci, E., Frosini, A., Rinaldi, S. (eds.) DGCI 2014. LNCS, vol. 8668, pp. 150–161. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09955-2_13
Tarsissi, L., Coeurjolly, D., Kenmochi, Y., Romon, P.: Convexity preserving contraction of digital sets. In: Palaiahnakote, S., Sanniti di Baja, G., Wang, L., Yan, W.Q. (eds.) ACPR 2019. LNCS, vol. 12047, pp. 611–624. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-41299-9_48
Tarsissi, L., Kenmochi, Y., Romon, P., Coeurjolly, D., Borel, J.P.: Convexity preserving deformations of digital sets: characterization of removable and insertable points. Technical report, LIGM (2022)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Tarsissi, L., Kenmochi, Y., Djerroumi, H., Coeurjolly, D., Romon, P., Borel, JP. (2022). Algorithms for Pixelwise Shape Deformations Preserving Digital Convexity. In: Baudrier, É., Naegel, B., Krähenbühl, A., Tajine, M. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2022. Lecture Notes in Computer Science, vol 13493. Springer, Cham. https://doi.org/10.1007/978-3-031-19897-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-19897-7_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-19896-0
Online ISBN: 978-3-031-19897-7
eBook Packages: Computer ScienceComputer Science (R0)