Abstract
Thinning in 2D is an iterative object reduction to produce centerlines of discrete binary objects. A thinning algorithm is 1-attempt if whenever a border point is not deleted in the actual iteration step, it belongs to the resulting centerline. Parallel thinning algorithms alter all deletable points simultaneously, while sequential ones traverse object points in the current picture, and delete the actually visited one if it is designated as deletable. A pair of thinning algorithms are equivalent if they produce the same centerline for any input picture. This paper presents the very first 1-attempt, equivalent, and topology-preserving pair of parallel and sequential thinning algorithms acting on the nonconventional hexagonal grid. It is also illustrated that 1-attempt property involves a remarkable speed up.
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
References
Bertrand, G.: On P-simple points. Compte Rendu de l’Académie des Sciences de Paris, Série Math. 321, 1077–1084 (1995)
Beucher, S.: From non connected to homotopic skeletons in multidimensional digital space. In: Proceedings of the International Symposium on Mathematical Morphology and Its Applications to Signal Processing, pp. 139–144 (1993)
Deutsch, E.S.: Thinning algorithms on rectangular hexagonal and triangular arrays. Commun. ACM 15, 827–837 (1972). https://doi.org/10.1145/361573.361583
Hall, R.W.: Parallel connectivity-preserving thinning algorithms. In: Kong, T.Y., Rosenfeld, A. (eds.) Topological Algorithms for Digital Image Processing, pp. 145–179. Elsevier Science, Amsterdam (1996). https://doi.org/10.1016/S0923-0459(96)80014-0
Kardos, P., Palágyi, K.: On topology preservation for hexagonal parallel thinning algorithms. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K.N., Korutcheva, E.R. (eds.) IWCIA 2011. LNCS, vol. 6636, pp. 31–42. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21073-0_6
Kardos, P., Palágyi, K.: Hexagonal parallel thinning algorithms based on sufficient conditions for topology preservation. In: Proceedings of the 3rd International Symposium of Computational Modeling on Objects Presented in Images: Fundamentals, Methods, and Applications, pp. 63–68 (2012). https://doi.org/10.1201/b12753-12
Kardos, P., Palágyi, K.: On topology preservation in triangular, square, and hexagonal grids. In: Proceedings of the 8th International Symposium on Image and Signal Processing and Analysis, pp. 782–787 (2013). https://doi.org/10.1109/ISPA.2013.6703844
Kardos, P., Palágyi, K.: Topology-preserving hexagonal thinning. Int. J. Comput. Math. 90, 1607–1617 (2013). https://doi.org/10.1080/00207160.2012.724198
Kong, T.Y., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vis. Graph. Image Process. 48, 357–393 (1989). https://doi.org/10.1016/0734-189X(89)90147-3
Lee, M., Jayanthi, S.: Hexagonal Image Processing: A Practical Approach. Springer, London (2005)
Marchand-Maillet, S., Sharaiha, Y.M.: Binary Digital Image Processing: A Discrete Approach. Academic Press, London (2000). https://doi.org/10.1117/1.1326456
Palágyi, K.: A 3D fully parallel surface-thinning algorithm. Theor. Comput. Sci. 406, 119–135 (2008). https://doi.org/10.1016/j.tcs.2008.06.041
Palágyi, K.: Equivalent 2D sequential and parallel thinning algorithms. In: Barneva, R.P., Brimkov, V.E., Šlapal, J. (eds.) IWCIA 2014. LNCS, vol. 8466, pp. 91–100. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07148-0_9
Palágyi, K.: Equivalent sequential and parallel reductions in arbitrary binary pictures. Int. J. Pattern Recogn. Artif. Intell. 28, 1460009 (2014). https://doi.org/10.1142/S021800141460009X
Palágyi, K.: How sufficient conditions are related for topology-preserving reductions. Acta Cybernetica 23, 939–958 (2018). https://doi.org/10.14232/actacyb.23.3.2018.14
Palágyi, K., Németh, G.: 1-attempt subfield-based parallel thinning. In: Proceedings of the 12th International Symposium on Image and Signal Processing and Analysis, pp. 306–311 (2021). https://doi.org/10.1109/ISPA52656.2021.9552163
Palágyi, K., Németh, G.: 1-attempt 4-cycle parallel thinning algorithms. In: Proceedings of the 11th International Conference on Pattern Recognition Applications and Methods, pp. 229–236 (2022). https://doi.org/10.5220/0010819700003122
Palágyi, K., Németh, G.: 1-attempt parallel thinning. J. Comb. Optim. 44, 2395–2409 (2022). https://doi.org/10.1007/s10878-021-00744-y
Palágyi, K., Németh, G., Kardos, P.: Topology-preserving equivalent parallel and sequential 4-subiteration 2D thinning algorithms. In: Proceedings of the 9th International Symposium on Image and Signal Processing and Analysis, pp. 306–311 (219–224). https://doi.org/10.1109/ISPA.2015.7306077
Saha, P.K., Borgefors, G., Sanniti di Baja, G.: Skeletonization: Theory, Methods and Applications. Academic Press, London (2017). https://doi.org/10.1016/B978-0-08-101291-8.00017-1
Siddiqi, K., Pizer, S.M.: Medial Representations: Mathematics, Algorithms and Applications. Springer, Dordrecht (2008). https://doi.org/10.1007/978-1-4020-8658-8
Staunton, R.C.: An analysis of hexagonal thinning algorithms and skeletal shape representation. Pattern Recogn. 29, 1131–1146 (1999). https://doi.org/10.1016/0031-3203(94)00155-3
Staunton, R.C.: One-pass parallel hexagonal thinning algorithm. In: IEE Proceedings of Vision, Image and Signal Processing, vol. 148, pp. 45–53 (2001). https://doi.org/10.1049/ip-vis:20010076
Acknowledgements
This research was supported by project TKP2021-NVA-09. Project no. TKP2021-NVA-09 has been implemented with the support provided by the Ministry of Innovation and Technology of Hungary from the National Research, Development and Innovation Fund, financed under the TKP2021-NVA funding scheme.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Palágyi, K. (2024). 1-Attempt and Equivalent Thinning on the Hexagonal Grid. In: Brunetti, S., Frosini, A., Rinaldi, S. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2024. Lecture Notes in Computer Science, vol 14605. Springer, Cham. https://doi.org/10.1007/978-3-031-57793-2_30
Download citation
DOI: https://doi.org/10.1007/978-3-031-57793-2_30
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57792-5
Online ISBN: 978-3-031-57793-2
eBook Packages: Computer ScienceComputer Science (R0)