EDT Method for Multiple Labelled Objects Subject to Tied Distances

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

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

###### Author Bio: 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
• pn1pn2pn3
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.
• Figure  1.  Example of a VD. (a) is an input with 3 VSs containing different labels (the zero-valued pixels with dark or grey colours); (b) shows the result of a traditional VD, where each VR is represented by the coloured label of its respective VS. The final size of each VR is: 18, 17, and 14, for black, dark grey, and light grey, respectively; (c) shows a modified VD, where the white region represents 3 tied pixels from 2 or more VSs. The final size of each VR, in this case, is: 18, 17, and 17, for black, dark grey, and light grey. In (b) and (c), the numerical values represent the smallest quadratic Euclidean distance between the analysed point and any VS.

Figure  2.  Numerical example of distance transform. In (b), there is the Euclidean distance of each pixel to the nearest black pixel. The distance values are squared so that only integer values are stored[34].

Figure  3.  Example of the 1D transformation common to independent scanning EDTs[34]. (a) Input image F; (b) 1D EDT $G$ along each row.

Figure  4.  Example of Transformation 2 to a pixel $(i, j)$[34]. It is specifically calculated $H(3, 4)$ for $i = 0, \cdots, M - 1$ and $j = 0, \cdots, N - 1$. For that, one calculates all possible values of $G (x, j) + (i - x) ^ 2$ on axis $j$ and then value $x = 1$ is selected, which results in $H(i, j) = 4$.

Figure  5.  Vectors represented in (a) are converted into matrix A (b) and V (d). After the EDT, matrix A is exposed as in (c), and matrix V as in (e).

Figure  6.  First example of dilatation process for a labelled 3D matrix of (a) with 5 different radius values. Tied voxels are represented in yellow, magenta, cyan and white.

Figure  7.  Second example of dilatation process for a labelled 3D matrix input of Fig. 6(a) with 5 different radius values. Tied voxels are represented in yellow, magenta, cyan and white.

Figure  8.  The sub-figure (d) shows a final example of dilation and its respective cut (e). (a)−(c) represent the voxel with only one label at the end of the dilation. And (f) shows all voxels with more than one label.

Figure  9.  Relationship between number of points, labels, and tied voxels. Average values for 100 executions within an 100 × 100 × 100 cube.

Figure  10.  Comparison between the number of interest points and of tied voxels. Each curve counts the tied voxels that occurred for a given number of labels. Average values for 20 runs within an 100 × 100 × 100 cube and a total of 30 distinct labels.

•  [1] T. Saito, J. I. Toriwaki. New algorithms for Euclidean distance transformation of an $n$-dimensional digitized picture with applications. Pattern Recognition, vol. 27, no. 11, pp. 1551–1565, 1994. DOI:  10.1016/0031-3203(94)90133-3. [2] A. Rosenfeld, J. L. Pfaltz. Sequential operations in digital picture processing. Journal of the ACM, vol. 13, no. 4, pp. 471–494, 1966. 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. Machine Vision and Applications, vol. 22, no. 4, pp. 721–737, 2011. DOI:  10.1007/s00138-010-0307-7. [4] S. Gustavson, R. Strand. Anti-aliased Euclidean distance transform. Pattern Recognition Letters, vol. 32, no. 2, pp. 252–257, 2011. 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. International Journal of Automation and Computing, vol. 17, no. 2, pp. 151–178, 2020. 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. Information Sciences, vol. 346−347, pp. 58–72, 2016. 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. International Journal of Automation and Computing, vol. 16, no. 1, pp. 27–39, 2019. 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. Journal of Physics:Conference Series, vol. 410, Article number 012091, 2013. 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. Information Sciences, vol. 459, pp. 36–52, 2018. 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. Physica A:Statistical Mechanics and its Applications, vol. 416, pp. 41–48, 2014. 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. Chaos, vol. 22, no. 4, Article number 043103, 2012. DOI:  10.1063/1.4757226. [12] L. C. Ribas, M. B. Neiva, O. M. Bruno. Distance transform network for shape analysis. Information Sciences, vol. 470, pp. 28–42, 2019. 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. International Journal of Systems Science, vol. 40, no. 2, pp. 173–186, 2009. 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. International Journal of Systems Science, vol. 40, no. 2, pp. 163–172, 2009. DOI:  10.1080/00207720802630685. [15] F. Q. Liu, Z. Y. Wang. Automatic “ground truth" annotation and industrial workpiece dataset generation for deep learning. International Journal of Automation and Computing, vol. 17, no. 4, pp. 539–550, 2020. 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. Journal of Physics:Conference Series, vol. 410, no. 1, Article number 012066, 2013. DOI:  10.1088/1742-6596/410/1/012066. [17] W. J. Staszewski. Advanced data pre-processing for damage identification based on pattern recognition. International Journal of Systems Science, vol. 31, no. 11, pp. 1381–1396, 2000. 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. International Journal of Automation and Computing, vol. 16, no. 5, pp. 575–588, 2019. 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. International Journal of Automation and Computing, vol. 17, no. 6, pp. 837–854, 2020. DOI:  10.1007/s11633-020-1231-6. [20] E. Remy, E. Thiel. Exact medial axis with Euclidean distance. Image and Vision Computing, vol. 23, no. 2, pp. 167–175, 2005. 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. Pattern Recognition, vol. 37, no. 1, pp. 79–92, 2004. 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. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 529–533, 1995. DOI:  10.1109/34.391389. [25] T. Hirata. A unified linear-time algorithm for computing distance maps. Information Processing Letters, vol. 58, no. 3, pp. 129–133, 1996. 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. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 2, pp. 265–270, 2003. 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. Pattern Recognition, vol. 28, no. 3, pp. 331–341, 1995. 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. Image and Vision Computing, vol. 25, no. 10, pp. 1543–1556, 2007. DOI:  10.1016/j.imavis.2006.06.020. [30] N. Karmakar, S. Mondal, A. Biswas. Determination of 3D curve skeleton of a digital object. Information Sciences, vol. 499, pp. 84–101, 2019. DOI:  10.1016/j.ins.2018.06.021. [31] A. L. Marasca, D. Casanova, M. Teixeira. Assessing classification complexity of datasets using fractals. International Journal of Computational Science and Engineering, vol. 20, no. 1, pp. 102–119, 2019. 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. International Journal of Automation and Computing, vol. 17, no. 4, pp. 551–561, 2020. DOI:  10.1007/s11633-019-1219-2. [33] W. H. Hesselink. A linear-time algorithm for Euclidean feature transform sets. Information Processing Letters, vol. 102, no. 5, pp. 181–186, 2007. 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. ACM Computing Surveys, vol. 40, no. 1, Article number 2, 2008. 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. CVGIP:Graphical Models and Image Processing, vol. 54, no. 1, pp. 56–74, 1992. DOI:  10.1016/1049-9652(92)90034-U. [37] O. Cuisenaire, B. Macq. Fast Euclidean distance transformation by propagation using multiple neighborhoods. Computer Vision and Image Understanding, vol. 76, no. 2, pp. 163–172, 1999. 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

##### 计量
• 文章访问数:  8
• HTML全文浏览量:  14
• PDF下载量:  2
• 被引次数: 0
##### 出版历程
• 收稿日期:  2020-08-27
• 录用日期:  2021-01-28
• 网络出版日期:  2021-03-23

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

pn1pn2pn3

### English Abstract

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

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈