Article Contents
Citation: A. Marasca, A. Backes, F. Favarim, M. Teixeira, D. Casanova. Edt method for multiple labelled objects subject to tied distances. International Journal of Automation and Computing. http://doi.org/10.1007/s11633-021-1285-0 doi:  10.1007/s11633-021-1285-0
Cite as: Citation: A. Marasca, A. Backes, F. Favarim, M. Teixeira, D. Casanova. Edt method for multiple labelled objects subject to tied distances. International Journal of Automation and Computing . http://doi.org/10.1007/s11633-021-1285-0

# EDT Method for Multiple Labelled Objects Subject to Tied Distances

Author Biography:
• Andre Marasca received the B. Sc. degree in computer engineering from Federal University of Technology-Parana (UTFPR) − Pato Branco (PB), Brazil in 2016, the M. Sc. degree in electrical engineering from UTFPR − PB, Brazil in 2019. Currently, he has a startup in Brazil. His research interests include algorithms, computer vision, machine learning and metaheuristics. E-mail: eng.andremarasca@gmail.com ORCID iD: 0000-0003-4058-957X

Andre Backes received the B. Sc., M. Sc. and Ph. D. degrees in computer science from University of Sao Paulo, Brazil in 2003, 2006 and 2010, respectively. He is an associate professor at School of Computer Science, Federal University of Uberlandia, Brazil. His research interests include computer vision, image analysis and pattern recognition.E-mail: arbackes@yahoo.com.brORCID iD: 0000-0002-7486-4253

Fabio Favarim received the B. Sc. degree in computer science, the M. Sc. degree in electrical engineering, the Ph. D. degree in electrical engineering from Faculty of Sciences, University of Lisboa, Portugal in 2000, 2003 and 2009, respectively. Currently, he is an associate professor at the Federal University of Technology − Parana (UTFPR), Brazil.His research interests include parallel and distributed systems, computer networks and internet of things.E-mail: favarim@utfpr.edu.brORCID iD: 0000-0001-7490-8167

Marcelo Teixeira received the B. Sc. degree in computer science, the M. Sc. degree in computer engineering, the Ph. D. degree in automation & systems engineering, from University of Waikato, New Zealand in 2007, 2009 and 2013, respectively. Currently, he is teaching and researching for the Federal University of Technology − Parana, in Brazil, in both graduation and undergraduation levels. He′s been an active member of the IEEE since 2016, participating of the Industrial Electronic Society (IES), Technical Committee on Factory Automation, Subcommittee Industrial Automated Systems and Control.His research interests include discrete-event systems, cyber-physical systems, flexible manufacturing systems, industry 4.0, synthesis of controllers for industrial processes, industrial automation, and automatic synthesis of software.E-mail: mtex@utfpr.edu.br (Corresponding author)ORCID iD: 0000-0002-1008-7838

Dalcimar Casanova received the B. Sc. degree in computer science from University of the West of Santa Catarina (UNOESC), Brazil in 2005, the M. Sc. degree in computer science and computational mathematics from Institute of Mathematics and Computer Sciences, University of Sao Paulo (USP), Brazil in 2008, the Ph. D. degree in computational physics from Institute of Physics of São Carlos, USP, Brazil in 2013. Currently, he is a professor at the Federal University of Technology − Parana (UTFPR).His research interests include computational physics and applications multidisciplinary areas, mainly in the following topics:computer vision, complex networks, machine learning, and bioinformatics.E-mail: dalcimar@gmail.comORCID iD: 0000-0002-1905-4602

• Accepted: 2021-01-28
• Published Online: 2021-03-23
• The success of new scientific areas can be assessed by their potential for contributing to new theoretical approaches aligned with real-world applications. The Euclidean distance transform (EDT) has fared well in both cases, providing a sound theoretical basis for a number of applications, such as median axis transform, fractal analysis, skeletonization, and Voronoi diagrams. Despite its wide applicability, the discrete form of the EDT includes interesting properties that have not yet been fully exploited in the literature. In this paper, we are particularly interested in the properties of 1) working with multiple objects/labels; and 2) identifying and counting equidistant pixels/voxels from certain points of interest. In some domains (such as dataset classification, texture, and complexity analysis), the result of applying the EDT transform with different objects, and their respective tied distances, may compromise the performance. In this sense, we propose an efficient modification in the method presented in [1], which leads to a novel approach for computing the distance transform in a space with multiple objects, and for counting equidistant pixels/voxels.
• 1In this work, we use the term EDT to refer to the exact EDT, since it is the most conventional form found in the literature.
1A Voronoi region is also known as Voronoi polygon, tile, or region of influence.2A Voronoi site is also known as an interest point, Voronoi element, seed, or source. All these expressions will be used interchangeably in this article when the context is clear.
3A Voronoi site is also known as an interest point, Voronoi element, seed, or source. All these expressions will be used interchangeably in this article when the context is clear.
•  [1] T. Saito, J. I. Toriwaki.  New algorithms for Euclidean distance transformation of an \begin{document}$n$\end{document}-dimensional digitized picture with applications[J]. Pattern RecognitionPattern Recognition, 1994, 27(11): 1551-1565. doi: 10.1016/0031-3203(94)90133-3 [2] A. Rosenfeld, J. L. Pfaltz.  Sequential operations in digital picture processing[J]. Journal of the ACMJournal of the ACM, 1966, 13(4): 471-494. doi: 10.1145/321356.321357 [3] R. Y. Jiang, K. Reinhard, V. Tobi, S. G. Wang.  Lane detection and tracking using a new lane model and distance transform[J]. Machine Vision and ApplicationsMachine Vision and Applications, 2011, 22(4): 721-737. doi: 10.1007/s00138-010-0307-7 [4] S. Gustavson, R. Strand.  Anti-aliased Euclidean distance transform[J]. Pattern Recognition LettersPattern Recognition Letters, 2011, 32(2): 252-257. doi: 10.1016/j.patrec.2010.08.010 [5] H. Xu, Y. Ma, H. C. Liu, D. Deb, H. Liu, J. L. Tang, A. K. Jain.  Adversarial attacks and defenses in images, graphs and text: A review[J]. International Journal of Automation and ComputingInternational Journal of Automation and Computing, 2020, 17(2): 151-178. doi: 10.1007/s11633-019-1211-x [6] D. Casanova, J. B. Florindo, M. Falvo, O. M. Bruno.  Texture analysis using fractal descriptors estimated by the mutual interference of color channels[J]. Information SciencesInformation Sciences, 2016, 346−347(): 58-72. doi: 10.1016/j.ins.2016.01.077 [7] Y. Hao, Z. J. Xu, Y. Liu, J. Wang, J. L. Fan.  Effective crowd anomaly detection through spatio-temporal texture analysis[J]. International Journal of Automation and ComputingInternational Journal of Automation and Computing, 2019, 16(1): 27-39. doi: 10.1007/s11633-018-1141-z [8] J. B. Florindo, D. Casanova, O. M. Bruno.  Fractal measures of complex networks applied to texture analysis[J]. Journal of Physics: Conference SeriesJournal of Physics: Conference Series, 2013, 410(): 012091-. doi: 10.1088/1742-6596/410/1/012091 [9] J. B. Florindo, D. Casanova, O. M. Bruno.  A Gaussian pyramid approach to bouligand-minkowski fractal descriptors[J]. Information SciencesInformation Sciences, 2018, 459(): 36-52. doi: 10.1016/j.ins.2018.05.037 [10] M. W. da S. Oliveira, D. Casanova, J. B. Florindo, O. M. Bruno.  Enhancing fractal descriptors on images by combining boundary and interior of minkowski dilation[J]. Physica A: Statistical Mechanics and its ApplicationsPhysica A: Statistical Mechanics and its Applications, 2014, 416(): 41-48. doi: 10.1016/j.physa.2014.07.074 [11] A. R. Backes, J. B. Florindo, O. M. Bruno.  Shape analysis using fractal dimension: A curvature based approach[J]. ChaosChaos, 2012, 22(4): 043103-. doi: 10.1063/1.4757226 [12] L. C. Ribas, M. B. Neiva, O. M. Bruno.  Distance transform network for shape analysis[J]. Information SciencesInformation Sciences, 2019, 470(): 28-42. doi: 10.1016/j.ins.2018.08.038 [13] P. Liatsis, J. Y. Goulermas, X. J. Zeng, E. Milonidis.  A flexible visual inspection system based on neural networks[J]. International Journal of Systems ScienceInternational Journal of Systems Science, 2009, 40(2): 173-186. doi: 10.1080/00207720802630719 [14] G. A. Ruz, P. A. Estevez, P. A. Ramirez.  Automated visual inspection system for wood defect classification using computational intelligence techniques[J]. International Journal of Systems ScienceInternational Journal of Systems Science, 2009, 40(2): 163-172. doi: 10.1080/00207720802630685 [15] F. Q. Liu, Z. Y. Wang.  Automatic “ground truth" annotation and industrial workpiece dataset generation for deep learning[J]. International Journal of Automation and ComputingInternational Journal of Automation and Computing, 2020, 17(4): 539-550. doi: 10.1007/s11633-020-1221-8 [16] B. B. Machado, D. Casanova, W. N. Gonçalves, O. M. Bruno.  Partial differential equations and fractal analysis to plant leaf identification[J]. Journal of Physics: Conference SeriesJournal of Physics: Conference Series, 2013, 410(1): 012066-. doi: 10.1088/1742-6596/410/1/012066 [17] W. J. Staszewski.  Advanced data pre-processing for damage identification based on pattern recognition[J]. International Journal of Systems ScienceInternational Journal of Systems Science, 2000, 31(11): 1381-1396. doi: 10.1080/00207720050197776 [18] H. Liu, G. F. Xiao, Y. L. Tan, C. J. Ouyang.  Multi-source remote sensing image registration based on contourlet transform and multiple feature fusion[J]. International Journal of Automation and ComputingInternational Journal of Automation and Computing, 2019, 16(5): 575-588. doi: 10.1007/s11633-018-1163-6 [19] D. Haputhanthri, G. Brihadiswaran, S. Gunathilaka, D. Meedeniya, S. Jayarathna, M. Jaime, C. Harshaw.  Integration of facial thermography in EEG-based classification of ASD[J]. International Journal of Automation and ComputingInternational Journal of Automation and Computing, 2020, 17(6): 837-854. doi: 10.1007/s11633-020-1231-6 [20] E. Remy, E. Thiel.  Exact medial axis with Euclidean distance[J]. Image and Vision ComputingImage and Vision Computing, 2005, 23(2): 167-175. doi: 10.1016/j.imavis.2004.06.007 [21] L. Vincent. Exact Euclidean distance function by chain propagations. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Maui, USA, pp. 520−525, 1991. DOI: 10.1109/CVPR.1991.139746. [22] F. Y. Shih, Y. T. Wu.  Three-dimensional Euclidean distance transformation and its application to shortest path planning[J]. Pattern RecognitionPattern Recognition, 2004, 37(1): 79-92. doi: 10.1016/j.patcog.2003.08.003 [23] L. Antón-Canalís, M. Hernández-Tejera, E. Sánchez-Nielsen. Analysis of relevant maxima in distance transform. An application to fast coarse image segmentation. In Proceedings of the 3rd Iberian Conference on Pattern Recognition and Image Analysis, Springer, Girona, Spain, pp. 97−104. 2007. DOI: 10.1007/978-3-540-72847-4_14. [24] H. Breu, J. Gil, D. Kirkpatrick, M. Werman.  Linear time Euclidean distance transform algorithms[J]. IEEE Transactions on Pattern Analysis and Machine IntelligenceIEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(5): 529-533. doi: 10.1109/34.391389 [25] T. Hirata.  A unified linear-time algorithm for computing distance maps[J]. Information Processing LettersInformation Processing Letters, 1996, 58(3): 129-133. doi: 10.1016/0020-0190(96)00049-X [26] C. R. Maurer, R. S. Qi, V. Raghavan.  A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions[J]. IEEE Transactions on Pattern Analysis and Machine IntelligenceIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(2): 265-270. doi: 10.1109/TPAMI.2003.1177156 [27] D. G. Bailey. An efficient Euclidean distance transform. In Proceedings of the 10th International Workshop on Combinatorial Image Analysis, Springer, Auckland, New Zealand, pp. 394−408, 2004. DOI: 10.1007/978-3-540-30503-3_28. [28] F. Y. Shih, C. C. Pu.  A skeletonization algorithm by maxima tracking on Euclidean distance transform[J]. Pattern RecognitionPattern Recognition, 1995, 28(3): 331-341. doi: 10.1016/0031-3203(94)00104-T [29] M. Couprie, D. Coeurjolly, R. Zrour.  Discrete bisector function and Euclidean skeleton in 2D and 3D[J]. Image and Vision ComputingImage and Vision Computing, 2007, 25(10): 1543-1556. doi: 10.1016/j.imavis.2006.06.020 [30] N. Karmakar, S. Mondal, A. Biswas.  Determination of 3D curve skeleton of a digital object[J]. Information SciencesInformation Sciences, 2019, 499(): 84-101. doi: 10.1016/j.ins.2018.06.021 [31] A. L. Marasca, D. Casanova, M. Teixeira.  Assessing classification complexity of datasets using fractals[J]. International Journal of Computational Science and EngineeringInternational Journal of Computational Science and Engineering, 2019, 20(1): 102-119. doi: 10.1504/IJCSE.2019.103261 [32] S. Sahoo, A. Subudhi, M. Dash, S. Sabut.  Automatic classification of cardiac arrhythmias based on hybrid features and decision tree algorithm[J]. International Journal of Automation and ComputingInternational Journal of Automation and Computing, 2020, 17(4): 551-561. doi: 10.1007/s11633-019-1219-2 [33] W. H. Hesselink.  A linear-time algorithm for Euclidean feature transform sets[J]. Information Processing LettersInformation Processing Letters, 2007, 102(5): 181-186. doi: 10.1016/j.ipl.2006.12.005 [34] R. Fabbri, L. da F. Costa, J. C. Torelli, O. M. Bruno.  2D Euclidean distance transform algorithms: A comparative survey[J]. ACM Computing SurveysACM Computing Surveys, 2008, 40(1): 2-. doi: 10.1145/1322432.1322434 [35] L. da Fontoura Costa, R. M. Cesar Jr. Shape Analysis and Classification: Theory and Practice, Boca Raton, USA: CRC Press, 2010. [36] D. W. Paglieroni.  Distance transforms: Properties and machine vision applications[J]. CVGIP: Graphical Models and Image ProcessingCVGIP: Graphical Models and Image Processing, 1992, 54(1): 56-74. doi: 10.1016/1049-9652(92)90034-U [37] O. Cuisenaire, B. Macq.  Fast Euclidean distance transformation by propagation using multiple neighborhoods[J]. Computer Vision and Image UnderstandingComputer Vision and Image Understanding, 1999, 76(2): 163-172. doi: 10.1006/cviu.1999.0783 [38] R. A. Lotufo, F. A. Zampirolli. Fast multidimensional parallel Euclidean distance transform based on mathematical morphology. In Proceedings of the 14th Brazilian Symposium on Computer Graphics and Image Processing, IEEE, Florianopolis, Brazil, pp. 100−105, 2001. DOI: 10.1109/SIBGRAPI.2001.963043.
•  [1] Hai-Rong Fang, Tong Zhu, Hai-Qiang Zhang, Hui Yang, Bing-Shan Jiang. Design and Analysis of a Novel Hybrid Processing Robot Mechanism . International Journal of Automation and Computing,  doi: 10.1007/s11633-020-1228-1 [2] Atlas Khan, Yan-Peng Qu, Zheng-Xue Li. Convergence Analysis of a New MaxMin-SOMO Algorithm . International Journal of Automation and Computing,  doi: 10.1007/s11633-016-0996-0 [3] Yu Hao, Zhi-Jie Xu, Ying Liu, Jing Wang, Jiu-Lun Fan. Effective Crowd Anomaly Detection Through Spatio-temporal Texture Analysis . International Journal of Automation and Computing,  doi: 10.1007/s11633-018-1141-z [4] Chen Li, Hong-Ji Yang, Mei-Yu Shi, Wei Zhu. xBreeze/ADL: A Language for Software Architecture Specification and Analysis . International Journal of Automation and Computing,  doi: 10.1007/s11633-016-1028-9 [5] Mohamadreza Homayounzade,  Mehdi Keshmiri,  Mostafa Ghobadi. A Robust Tracking Controller for Electrically Driven Robot Manipulators: Stability Analysis and Experiment . International Journal of Automation and Computing,  doi: 10.1007/s11633-014-0850-1 [6] Guo-Jin Feng,  James Gu,  Dong Zhen,  Mustafa Aliwan,  Feng-Shou Gu,  Andrew D. Ball. Implementation of Envelope Analysis on a Wireless Condition Monitoring System for Bearing Fault Diagnosis . International Journal of Automation and Computing,  doi: 10.1007/s11633-014-0862-x [7] Imen Manaa,  Nabil Barhoumi,  Faouzi Msahli. Global Stability Analysis of Switched Nonlinear Observers . International Journal of Automation and Computing,  doi: 10.1007/s11633-014-0855-9 [8] Hua-Ping Zhang,  Rui-Qi Zhang,  Yan-Ping Zhao,  Bao-Jun Ma. Big Data Modeling and Analysis of Microblog Ecosystem . International Journal of Automation and Computing,  doi: 10.1007/s11633-014-0774-9 [9] Hai-Peng Zhang,  Bao-Qun Yin,  Xiao-Nong Lu. Modeling and Analysis for Streaming Service Systems . International Journal of Automation and Computing,  doi: 10.1007/s11633-014-0812-7 [10] Fan Guo, Jin Tang, Zi-Xing Cai. Image Dehazing Based on Haziness Analysis . International Journal of Automation and Computing,  doi: 10.1007/s11633-014-0768-7 [11] . Analysis of Nonlinear Electrical Circuits Using Bernstein Polynomials . International Journal of Automation and Computing,  doi: 10.1007/s11633-012-0619-3 [12] Wu-Yi Yang, Sheng-Xing Liu, Tai-Song Jin, Xiao-Mei Xu. An Optimization Criterion for Generalized Marginal Fisher Analysis on Undersampled Problems . International Journal of Automation and Computing,  doi: 10.1007/s11633-011-0573-5 [13] Wei-Guo Yi, Ming-Yu Lu, Zhi Liu. Regression Analysis of the Number of Association Rules . International Journal of Automation and Computing,  doi: 10.1007/s11633-010-0557-x [14] Jin-Liang Wang, Huai-Ning Wu, Zhi-Chun Yang. Passivity Analysis of Impulsive Complex Networks . International Journal of Automation and Computing,  doi: 10.1007/s11633-011-0607-z [15] Jing Wang,  Zhi-Jie Xu. Video Analysis Based on Volumetric Event Detection . International Journal of Automation and Computing,  doi: 10.1007/s11633-010-0516-6 [16] S. Prabhudeva,  A. K. Verma. Coverage Modeling and Reliability Analysis Using Multi-state Function . International Journal of Automation and Computing,  doi: 10.1007/s11633-007-0380-1 [17] Magda Bogalecka,  Krzysztof Kolowrocki. Probabilistic Approach to Risk Analysis of Chemical Spills at Sea . International Journal of Automation and Computing,  doi: 10.1007/s11633-006-0117-6 [18] Renkuan Guo, Charles Ernie Love. Grey Repairable System Analysis . International Journal of Automation and Computing,  doi: 10.1007/s11633-006-0131-8 [19] De Xu, Carlos A. Acosta Calderon, John Q. Gan, Huosheng Hu, Min Tan. An Analysis of the Inverse Kinematics for a 5-DOF Manipulator . International Journal of Automation and Computing,  doi: 10.1007/s11633-005-0114-1 [20] Zai-Li Yang, Jin Wang, Steve Bonsall, Jian-Bo Yang, Quan-Gen Fang. A Subjective Risk Analysis Approach of Container Supply Chains . International Journal of Automation and Computing,  doi: 10.1007/s11633-005-0085-2
###### 通讯作者: 陈斌, bchen63@163.com
• 1.

沈阳化工大学材料科学与工程学院 沈阳 110142

Figures (10)  / Tables (1)

## EDT Method for Multiple Labelled Objects Subject to Tied Distances

###### 1. Federal University of Technology − Parana, Pato Branco 85503-390, Brazil2. Federal University of Uberlandia, Uberlandia 38400-902, Brazil

Abstract: The success of new scientific areas can be assessed by their potential for contributing to new theoretical approaches aligned with real-world applications. The Euclidean distance transform (EDT) has fared well in both cases, providing a sound theoretical basis for a number of applications, such as median axis transform, fractal analysis, skeletonization, and Voronoi diagrams. Despite its wide applicability, the discrete form of the EDT includes interesting properties that have not yet been fully exploited in the literature. In this paper, we are particularly interested in the properties of 1) working with multiple objects/labels; and 2) identifying and counting equidistant pixels/voxels from certain points of interest. In some domains (such as dataset classification, texture, and complexity analysis), the result of applying the EDT transform with different objects, and their respective tied distances, may compromise the performance. In this sense, we propose an efficient modification in the method presented in [1], which leads to a novel approach for computing the distance transform in a space with multiple objects, and for counting equidistant pixels/voxels.

1In this work, we use the term EDT to refer to the exact EDT, since it is the most conventional form found in the literature.
1A Voronoi region is also known as Voronoi polygon, tile, or region of influence.2A Voronoi site is also known as an interest point, Voronoi element, seed, or source. All these expressions will be used interchangeably in this article when the context is clear.
3A Voronoi site is also known as an interest point, Voronoi element, seed, or source. All these expressions will be used interchangeably in this article when the context is clear.
Citation: A. Marasca, A. Backes, F. Favarim, M. Teixeira, D. Casanova. Edt method for multiple labelled objects subject to tied distances. International Journal of Automation and Computing. http://doi.org/10.1007/s11633-021-1285-0 doi:  10.1007/s11633-021-1285-0
 Citation: Citation: A. Marasca, A. Backes, F. Favarim, M. Teixeira, D. Casanova. Edt method for multiple labelled objects subject to tied distances. International Journal of Automation and Computing . http://doi.org/10.1007/s11633-021-1285-0
Reference (38)

/