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 doi:  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

  • Received: 2020-08-27
  • 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 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 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 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 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 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 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 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 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 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 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]. Chaos, 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures (10)  / Tables (1)

Metrics

Abstract Views (8) PDF downloads (2) Citations (0)

EDT Method for Multiple Labelled Objects Subject to Tied Distances

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 doi:  10.1007/s11633-021-1285-0
    • The Euclidean distance transform (EDT) has been successfully applied to address a wide set of scientific problems. This applicability is credited to the multidisciplinary shape of EDT, as distance transform-based (DT) methods function perfectly to represent, exploit, and process solutions for multiple research areas.

      Its origins can be traced back to the work of [2], after which the respective theory has been used as a fundamental geometrical operator with great applicability in computer vision and graphics[3-5], texture analysis[6-10], shape analysis[11,12], visual inspection[13-15] and pattern recognition[16-19]. In addition, exact EDT, namely EEDT, is an extension that covers many other important entities such as medial axes[20], Voronoi diagrams[21], shortest-path computation[22], image segmentation[23] and fractal geometry[10].

      Due to its wide applicability, efficient non-Euclidean DT algorithms have been reported since 1966[2], while fast algorithms for the EEDT started to appear only in the 1990s[1, 24-27]. Despite many works involving EEDT, most of them exploiting computational efficiency, there are still aspects that remain challenging and, in general, have been neglected in the literature.

      Among them, we mention the possibility of processing the DT with labelled seeds, resulting in a Voronoi diagram (VD)[25, 26]. The most common EDT application with labelled seeds is the 2D skeletonization[28-30], where a thin version of a shape (1-pixel-thick wide) is built by assigning a labelled seed for each pixel on the boundary. After performing the EDT, an inner point of the shape belongs to the skeleton if it has at least two closest seeds. The key point is, therefore, the fact that skeletonization method uses pixels that are equidistant or tied to the seeds, suggesting that the useful information, to some extent, is not in the VD itself, but in the tied regions generated from it.

      Despite the skeletonization application example, that uses several labelled seeds (one for each border pixel), recent advances employ this idea (i.e., the use of tied info, not the VD itself) to perform texture analysis[6, 7] and to estimate dataset classification complexity[31, 32]. In both cases, labels are structured inside the EDT transform, and the info provided by equidistant regions of the seeds are used as features, in order to better describe objects. Although some EDT applications use multiple labelled seeds (and its natural consequence: the equidistant regions), their extensive use is still limited, as the existing exact algorithms do not provide such a functionality natively. In the research cases mentioned above, the treatment of labelled seeds is conducted later, and separately from the EDT, which requires substantial computational effort.

      In this way, the main drawback found when employing the labelled DT, specially in 3D or higher domains, is the problem with tied pixels: if any point is equidistant to two or more distinct seeds (a tied pixel), which seed would this point be assigned to? This question raises a number of limitations, such as the impossibility of having 2 seeds with the same origin ($ (x,y) $ coordinates) and the inaccuracy generated by the lack of criteria to choose the seed that will be linked to the pixel. A single tied pixel may not impact on the final Voronoi partition or region of interest size. However, in a discrete space we have to sometimes face several tied pixels, which causes substantial distortion in the sizes of the Voronoi regions.

      The main contribution of this work is an efficient modification of the method in [1], in order to correctly deal with tied pixels. This appears as an interesting property on multiple labelled seeds/objects problems. We also investigate their effects on the final Voronoi partitions and additionally propose an EDT operator that allows a high generalization on the choice for labelling seeds. Previous results also explore the idea of tied distances (also called co-cyclic points)[29, 33], however: 1) they do not consider the size of their influence region for each every labelled seed; and 2) they assume only one label with the same seed.

    • An important concept revisited throughout this paper is the point-wise Voronoi diagram (VD), sometimes also called Voronoi partition. The definitions used here are presented briefly in the following, while a more comprehensive account is found in [34].

      Formally, a VD can be represented by a mathematical structure derived from a set of Voronoi regions (VR). A VR includes a set of points that are strictly closer to a given location, called a Voronoi site (VS), than to any other interest point.

      In our examples, an interest point consists of zero-valued black or gray pixels. We denote by $ P $ the set of all pixels. The VS closest to a given pixel $ p \in P $ is denoted by ${\rm{V}}{\rm{S}}(p)$. In case $ p $ has two or more closest sites, one of them is arbitrarily chosen to be ${\rm{V}}{\rm{S}}(p)$. Then, in its turn, VD can be defined as the set of VR, i.e.,

      $ {\rm{VD}} = \{ {\rm{V}}{\rm{R}}^1 \cup {\rm{V}}{\rm{R}}^2 \cup \cdots \cup {\rm{V}}{\rm{R}}^n\} $

      (1)

      for

      $ {\rm{VR}}^1 \cap {\rm{VR}}^2 \cap \cdots \cap {\rm{VR}}^n \neq \emptyset \ . $

      (2)

      To build the partition ${\rm{V}}{\rm{D}}$, each point in ${\rm{V}}{\rm{D}}$ is arbitrarily assigned to the ${\rm{V}}{\rm{R}}$ of one site minimally equidistant to it. Then, ${\rm{V}}{\rm{D}}$ can be constructed by a label map ${\cal{L}}$ that associates to each VS a label (represented by a color in our examples) that identifies this VS and pixels of its ${\rm{V}}{\rm{R}}$. In the image processing terminology, given an image $I: \varOmega \subset {Z}^2 \mapsto {0,1}$ and in particular, $\varOmega = 1,\cdots,m\times 1,\cdots,n$ (unless otherwise stated) a map ${\cal{L}}$ is defined as

      $ {\cal{L}} : \Omega \mapsto \{0,\cdots,l-1\} $

      (3)

      where $ l $ is the number of Voronoi sites. Basically, the function ${\cal{L}}$ maps a domain $ \varOmega $ into a set of labels $\{0,\cdots,l-1\}$. For each point $ p \in \varOmega $, it follows that

      $ p \mapsto {\cal{L}}(p) = \{{\cal{L}} (q) \; |\; q = {\rm{V}}{\rm{S}}(p)\} . $

      (4)

      Fig. 1 shows an example of a VD obtained from 3 VS. For a given VD, we can measure the size of each ${\rm{V}}{\rm{R}}^i \in {\rm{V}}{\rm{D}}$ as the sum of all pixels $p \in {\rm{V}}{\rm{R}}$ (see Fig. 1(c)). If there is no point equidistant to two or more distinct seeds (a tied pixel), the point is assigned to some VR without specific criteria. A single tied pixel may not have significant influence on the size of the final VD or VR. However, when working on a discrete space, and especially when it contains a high number of interest points, the number of tied pixels may increase, causing distortions in the VR sizes. Thus, this paper proposes an alternative to deal with tied pixels through the association of labels that correct possible distortions, as shown in Figs. 1(c) and 1(b).

      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.

    • Voronoi diagrams (as shown in Fig. 1(c)) are commonly obtained by the application of the distance transform (DT) method. The central problem of a DT is to compute the distance of each point of the plane to a given subset of it (i.e., the seeds or Voronoi site). In the image processing terminology, by convention, 0 is associated to the black, and 1 to the white colour. Then, we have an object $ O $ represented by the white pixels:

      $ O = \{p \in \varOmega \; |\; I(p) = 1\} . $

      (5)

      In this case, the set $ O $ is called an object or background and it consists of any subset of the image domain, including disjoint sets. Its complement, $O^c$, is the set of black pixels in $ \varOmega $, and it is called foreground. From the DT point of view, foreground pixels are called interest points, seeds, sources, feature points, sites, or Voronoi elements.

      Finally, the DT can be defined as a map $ D $ that returns the shortest distance from each pixel $ p \in O $ to $ q \in O^c $, i.e.,

      $ D(p) = \min \{d(p,q) | q \in O^c \wedge I(q) = 0\} . $

      (6)

      Map $ D $ is called the distance map of $ I $ (or of $ O $, in case $ I $ is tacitly understood). $ D $ itself can also be called a distance transform, if there is no ambiguity between the image $ D $ and the transformation that generates it. The term DT may also refer to a DT algorithm, depending on the context.

      Here, we assume that $ O^c $ has at least one pixel (as in [2]), or the DT is undefined otherwise. Moreover, $ d(p, q) $ is generally taken as the Euclidean distance given by

      $ d(p,q) = \sqrt{(p_x-q_x)^2+(p_y-q_y)^2} \ . $

      (7)

      The literature usually refers to the distance transform based on the Euclidean distance as the Euclidean distance transform (EDT). Fig. 2 shows a numerical example of EDT. For each pixel in Fig. 2(a), the corresponding pixel in the DT of Fig. 2(b) holds the shortest Euclidean distance with respect to all other black pixels. The squared Euclidean distance is used for saving storage: since the pixel coordinates are integers, the square of the Euclidean distance $ d(p, q)^2 $ is also an integer.

      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].

      In addition to the Euclidean distance, other metrics can be used to compute the distance in (7), such as city-block ($ d_1 $) and chessboard ($d_\infty$)[35]. They are less expensive to process, but in general less applicable. Euclidean distance is often preferable due to its good properties. For example, it is radially symmetric, which enables us to generate shape representations and properties that are virtually invariant to rotation, a crucial task for robust recognition.

    • Despite its simplicity, the DT is hard to be computed efficiently. This difficulty relies on the fact that its definition involves a point-wise distance minimization. The most straightforward way to compute it is by applying (6), which involves measuring the distance between every object pixel and every foreground pixel. The computational complexity of this procedure is proportional to the number of pixels in the image squared, which can be very high, justifying more efficient algorithms.

      Since 1980, approximations to the EDT have been proposed based on greedy heuristics[34]. However, this approach does not correspond to the exact distance transform[36]. From the 1990s, new algorithms start to emerge, most of them with polynomial complexity and capabilities to accurately calculate the EDT[1, 34, 37, 38].

      The Saito and Toriwaki method[1], in particular, belongs to a class called independent scanning algorithms, and it consists of: 1) constructing a 1D transformation for each row (or column) independently; 2) using this intermediate result to construct the full 2D transform[34]. Stage 1 is common to all Euclidean DTs and it is based on independent scanning. Given an input image $ F $, the first transformation of independent scan generates an image $ G $ defined by

      $ G(i,j) = \underset{y}{{\rm{min}}}\{(j-y)^2 \mid F(i,y) = 0\}. $

      (8)

      This corresponds to computing, for each pixel $ (i,j) $, its (squared) distance to the closest black pixel in the same row. This transformation is efficiently implemented by performing a forward scan (left to right) followed by a backward scan (right to left) in each image row. The result of this transformation (Algorithm 3) for a simple image is illustrated in Fig. 3.

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

      Differently, the stage 2 requires a non-trivial processing. Here, each algorithm applies its specific strategy to generate the 2D EDT from the 1D line-wise transform. Starting from the image $ G $, the second transformation of the Saito and Toriwaki method generates an image $ H $, which is the distance map of $ F $:

      $ H(i,j) = \underset{x}{{\rm{min}}} \{G(x,j)+(i-x)^2\} .$

      (9)

      Fig. 4 illustrates the stage 2. After Transformation 1, every pixel $ (x, j) $ of column $ j $ has the value $ G(x, j) $, which is the squared distance between $ (x, j) $ and the nearest black pixel in the same row[34]. Saito and Toriwaki implement Transformation 2 by using a downward scan followed by an upward scan in each column of $ G $. To obtain $ H (i, j) $, a scan is performed for each pixel $ (x, j) $ in its respective column $ j $, calculating the value of $ x $, which minimizes $ G (x, j) + (i - x) ^ 2 $[1].

      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$.

      The soundness behind the Saito and Toriwaki method is that any $ k $-dimensional transformation can be derived by simply repeating the second transformation $ k-1 $ times, one for each coordinate axis.

      In [1], this method is called as basic type. However, specific Euclidean properties were exploited by subsequent methods in order to restrict the number of computations for each pixel during the second scan phase. One of the variants, uses properties based on parabola intersections, which is called as fast type[1].

      Their seminal work shows how the basic type EDT transform can be modified in order to segment the space and generate Voronoi diagrams[1]. However, it was not demonstrated how to perform similarly with the fast type, and the authors only claim this to be possible. The main problem encountered in space segmentation, not only in [1], using basic type or fast type, but also in other literature methods, is the labelling error that occurs in the regions equidistant to two or more seeds (as described in Section 1). Generally, points equidistant to two or more seeds receive the label from only one of these seeds, causing inconsistencies in the final VD.

      In the following sections, we proposed solutions for the two following problems:

      1) We propose a method that receives any input (i.e., any binary N-dimensional space) and generates EDT and VD using the fast type of the method in [1].

      2) We also solve the tied pixel problem, by enabling the assignment of different labels to a single pixel.

    • The kernel of the proposed method is implemented by Algorithm 1. Its receives as input the vectors $ X $, $ Y $, $ Z $ (i.e., coordinate vectors) and $ L $ (i.e., labelling vector), and returns the matrices $ A $ and $ V $ (i.e., matrices of distances and labels). The input data, the input conversion of the coordinate vectors and labelling vectors into the matrices $ A $ and $ V $, and the final labelled transform, are explained in the following.

      Algorithm 1. Perform Voronoi diagram

      Input: Vector of coordinates $ X $; Vector of coordinates $ Y $; Vector of coordinates $ Z $; Vector of labels $ L $;

      Output: Matrix of distances $ A $; Matrix of Voronoi $ V $;

      1) $ [A, V] \gets {\rm{Initialization}} (X, Y, Z, L) $;

      2) $ [A, V] \gets {\rm{Transformation \;1}}(A, V) $;

      3) $ [A, V] \gets {\rm{Transformation\; 2}}(A, V) $;

      4) $ [A, V] \gets {\rm{Transformation\; 3}}(A, V) $;

    • In any N-dimensional space (for N representing the natural set), two input data are required to obtain the VD: the set of points (Voronoi sites) belonging to the N-dimensional space, representing the foreground; and their respective labels. Fig. 5(a) shows an example of input with 4 points and 3 different labels in a 2-dimensional space.

      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).

    • Given the two input data, the next step is transforming them into a format that allows the EDT processing. As in [1], the input of the EDT is the two N-dimensional matrices, $ A $ containing foreground and background information, and $ V $ containing foreground label information.

      In other works that perform EDT with labels (e.g., [1, 29, 33]), each element ${\rm{VS}}$ in $ V $ is associated with an integer that indicates its label. This implies that the Voronoi region assigned to each seed may not correspond to the reality, since no partial regions are counted. In this work, differently, we pay special attention to source points with more than one label, and also points that are equidistant to two or more seeds. To address this feature properly, we consider that each bit composing this integer represents the presence or absence of a given label.

      By using this new strategy to store labels, it becomes possible to assign more than one label to a given point. One bit or more can be activated in the variable that stores the labelling, thus enabling applications such as [6].

      Since labels are now represented by bits, rather than integers, our algorithm can be implemented in such a way that each $ V $ element is a single 64-bit integer variable, considering a usual 64 bits computational architecture (or equivalently adapted to others). Therefore, the maximum number of discrete labels to be allowed is 64. However, $ V $ can be implemented so that each of its elements is a record with several integer variables. In this case there would be no limit related to the number of labels, other than the memory available.

      The transformation of a list of points and their respective labels to these two N-dimensional matrices is shown in Algorithm 2. The initialization of $ A $ and $ V $ matrices is performed by storing the coordinates and respective labelling of the foreground points.

      Algorithm 2. Initialization

      Input: Vector of coordinates $ X $; Vector of coordinates $ Y $; Vector of coordinates $ Z $; Vector of labels $ Lab $;

      Output: Matrix of distances $ A $; Matrix of Voronoi $ V $;

      1) $ A \gets \infty $;

      2) $ V \gets 0 $;

      3) for $ u \gets 0 $ to $ sizeof(L)-1 $ do

      4)  $ A[X[u]][Y[u]][Z[u]] \gets 0 $;

      5)  $V[X[u]][Y[u]][Z[u]]\getsBitOR(V[X[u]][Y[u]][Z[u]],\,Bit$  $ShiftLeft(1, L[u])) $;

      6) end

      In the matrix $ A $, foreground is represented by $ 0 $, and background by $ \infty $. In the matrix $ V$, the points belonging to the background do not have bits enabled and the foreground points have their bits activated through the bitwise OR operator. Then, if a point needs to be labelled with more than one label, we simply duplicate its coordinates in the initialization vectors. Changing the labelling implies that the corresponding bits are activated in the labelling matrix $ V $.

      In the vector $ L $, the labels must be represented by integers, starting with 0. As the proposed method uses the bits of an integer to represent labels, the label $ U $ means that the bit at position $ U $ will be activated, i.e.,

      $ set(bitU) = 2^{U} = {{BitwiseShiftLeft}} {(1,U)} . $

      This means that the activation of bits $ U_1 $ and $ U_2 $ follows from:

      $ \begin{split} &set(bitU1, bitU2) = 2^{U_1} + 2^{U_2} = \\ &\;\;\;\;\;\;{{BitwiseOR}} ({{BitwiseShiftLeft}}(1, U_1) ,\\&\;\;\;\;\;\;{{BitwiseShiftLeft}}(1, U_2)). \end{split} $

      In $ V $, the value $0 \cdots 00$ means that no label is activated. Fig. 5 shows an example of this operation. The input Fig. 5(a) has two VS with only one label, and two more VS in the same $ (x,y) $ coordinate. One of the points has coordinates $ (4,1) $ and desired label 1; the other point has coordinates $ (4,5) $ and desired label 2; and finally two other points have the same coordinate $ (1, 3) $ and desired labels 0 and 1. Using the proposed method to obtain the VD requires to define the coordinate vectors $X = $$ \left[1, 1, 4, 4\right]$, $ Y = \left[3, 3, 1, 5\right] $, and the labelling vector $L = $$ \left[0,1,1,2\right]$ as input to Algorithm 2.

      For the sake of illustration, the example assumes the binary representation of only 3 bits. After running Algorithm 2, the first point is represented in $ V $ by $ V_{(4,1)} = 010 $; the second point by $ V_{(4,5)} = 100 $; and the following two points by $ V_{(1,3)} = 011 $. Note that, in the first point, bit 1 was activated; in the second point, bit 2; and in the others, bits 0 and 1 were activated, according to the labels expressed in the vector $ L $. Therefore, the values in $ L $ must be numeric and they represent the bits to be activated in $ V $, because the Bitwise Shift Left is used to select the bit, and the operator Bitwise OR to activate it.

    • Once the input is obtained properly (i.e., in matrix form), we process Transformations 1 and 2, respectively according to Algorithms 3 and 6, extended from [1]. The modifications added by the labelled dilatation with respect to the original Saito and Toriwaki method, are marked with the symbol * in the algorithms.

      Algorithm 3 uses the background of $ A $ as $ \infty $. The modification of this step, if compared with [1], is the insertion of $ V $. In step Forward scan, the label belonging to the background is assigned according to the last seed (VS) found in the same line (Algorithm 4). In step Backward scan (Algorithm 5), if the new distance calculated for a point belonging to the background is smaller than the one found, the label is replaced. Otherwise, if the distance is equal (a tie), the Bitwise OR operator is used to hold the current label and join it with the new label.

      Algorithm 3. Transformation 1

      Input: Matrix of distances $ A $; Matrix of Voronoi $ V $;

      Output: Matrix of distances $ A $; Matrix of Voronoi $ V $;

      1) $ XX \gets {\rm{Number\; of\; rows}} (V) $;

      2) $ YY \gets {\rm{Number\; of\; columns}} (V) $;

      3) $ ZZ \gets {\rm{Number\; of\; slices}} (V) $;

      4) for $ x \gets 0 $ to $ XX-1 $ do

      5)  for $ y \gets 0 $ to $ YY-1 $ do

      6)  //Forward scan (Algorithm 4)

      7)   //Backward scan (Algorithm 5)

      8)  end

      9) end

      Algorithm 4. Transformation 1 Forward scan

      1) $ u \gets -1 $;

      2) * $ label \gets V[x][y][0] $;

      3) for $ z \gets 0 $ to $ ZZ-1 $ do

      4)  if $ A[x][y][z] = 0 $ then

      5)   $ u \gets z $;

      6)   * $ label \gets V[x][y][z] $;

      7)  else if $ u > 0 $ then

      8)   * $ V[x][y][z] \gets label $;

      9)   $ A[x][y][z] \gets (z - u)^2 $;

      10)  end

      11) end

      For the second transformation, Algorithm 6 uses the output of Transformation 1 as input. That is, its input is the 1D EDT applied to one of the axes in $ A $ and its respective label matrix $ V $. As in Transformation 1, the labelling procedure in Transformation 2 consists of replacing the label if there is a foreground point closer to a given background point than previously estimated. If the distance is the same, the Bitwise OR operator is used to keep the current label and join it with the new label. Forward scan and backward scan steps are shown in Algorithms 7 and 8, respectively.

      The result of these transformations is presented in Figs. 5(d) and 5(e). Fig. 5(d) shows only the distance matrix, similar to [1], or other EDT method, while Figs. 5(e) is obtained by using the method proposed in this paper. Note that we obtain a vector of labels for each pixel in the image, most of them having only 1 label enabled. However, for equidistant pixels (e.g., (4,3), (5,3) and (6,3)), both labels are assigned.

      The same logic applies to the pixels that belong to the VR from (1,3) VS. Note that, as this VS has 2 labels, all pixels that belong to this VR also do. For 3-dimensional (or higher) cases, Transformation 2 is repeated by modifying the axis analysed in Algorithm 6. For example, if we iterate along the Z-axis in Transformation 1, the axis of columns (axis Y) is iterated in Transformation 2, which then is repeated in the lines (X-axis).

      Algorithm 5. Transformation 1 backward scan

      1) $ u \gets -1 $;

      2) * $ label \gets V[x][y][ZZ - 1] $;

      3) for $ z \gets ZZ-1 $ to $ 0 $ do

      4)  if $ A[x][y][z] = 0 $ then

      5)   $ u \gets z $;

      6)   * $ label \gets V[x][y][z] $;

      7)  else if $ u > 0 $ then

      8)   $ d \gets (z - u)^2 $;

      9)   if $ d < A[x][y][z] $ then

      10)    * $ V[x][y][z] \gets label $;

      11)    $ A[i][y][z] \gets d $;

      12)   * else if $ d = A[x][y][z] $ then

      13)    * $ V[x][y][z] \gets BitOR(V[x][y][z], label) $;

      14)   end

      15)  end

      16) end

      Algorithm 6. Transformation 2

      Input: Matrix of distances $ A $; Matrix of Voronoi $ V $;

      Output: Matrix of distances $ A $; Matrix of Voronoi $ V $;

      1) $ XX \gets {\rm{Number\; of\; rows}} (V) $;

      2) $ YY \gets {\rm{Number\; of\; columns}} (V) $;

      3) $ ZZ \gets {\rm{Number \;of\; slices}} (V) $;

      4) for $ x \gets 0 $ to $ XX-1 $ do

      5)  for $ z \gets 0 $ to $ ZZ-1 $ do

      6)   for $ y \gets 0 $ to $ YY-1 $ do

      7)    $ buff[y] \gets A[x][y][z] $;

      8)    * $ buffV[y] \gets V[x][y][z] $;

      9)   end

      10)  //Forward scan (Algorithm 7)

      11)   //Backward scan (Algorithm 8)

      12)  end

      13) end

    • Figs. 6 and 7 illustrate the dilation process resulting from the proposed method. There are three labels, R, G, and B. The voxels in other colours are ties: yellow is a tie between R and G; magenta between R and B; cyan between G and B; and white between R, G, and B.

      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.

      Fig. 8 shows another example of dilatation with radius 8. The final result of the process is shown in Fig. 8(d). The final voxels with only one label are shown in Figs. 8(a)-8(c). The final voxels with more than one label is shown in Fig. 8(f). We remark that there is a considerable amount of tied voxels, which must be taken into account when computing the discrete EDT[6, 31].

      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.

      Algorithm 7. Transformation 2 forward scan

      1) $ a \gets 0 $;

      2) for $ y \gets 1 $ to $ YY-1 $ do

      3)  if $ a > 0 $ then

      4)   $ a \gets a - 1 $;

      5)  end

      6)  if $ buff[y] > buff[y - 1] $ then

      7)   $ b \gets (buff[y] - buff[y - 1]) / 2 $;

      8)   if $ b \geq YY - y $ then

      9)    $ b \gets (YY - 1)- y $;

      10)   end

      11)   for $ n \gets a $ to $ b $ do

      12)    $ m \gets buff[y - 1] + (n + 1)^2 $;

      13)    if $ buff[y + n] < m $ then

      14)     break;

      15)    end

      16)    if $ A[x][y + n][z] > m $ then

      17)     $ A[x][y + n][z] \gets m $;

      18)     * $ V[x][y + n][z] \gets buffV[y - 1] $;

      19)    * else if $ m = A[x][y + n][z] $ then

      20)     * $V[x][y+n][z] \gets BitOR(V[x][y+n][z], buffV $$ [y - 1])$;

      21)    end

      22)   end

      23)   $ a \gets b $;

      24)  else

      25)   $ a \gets 0 $;

      26)  end

      27) end

      Algorithm 8. Transformation 2 backward scan

      1) $ a \gets 0 $;

      2) for $ y \gets YY - 2 $ downto $ 0 $ do

      3)  if $ a > 0 $ then

      4)   $ a \gets a - 1 $;

      5)  end

      6)  if $ buff[y] > buff[y + 1] $ then

      7)   $ b \gets (buff[y] - buff[y + 1]) / 2 $;

      8)   if $ y - b < 0 $ then

      9)     $ b \gets y $;

      10)   end

      11)   for $ n \gets a $ to $ b $ do

      12)    $ m \gets buff[y + 1] + (n + 1)^2 $;

      13)    if $ buff[y - n] < m $ then

      14)     break;

      15)    end

      16)    if $ A[x][y - n][z] > m $ then

      17)     $ A[x][y - n][z] \gets m $;

      18)     * $ V[x][y - n][z] \gets buffV[y + 1] $;

      19)    * else if $ m = A[x][y - n][z] $ then

      20)     * $V[x][y-n][z]\getsBitOR(V[x][y-n][z], buffV$      $[y + 1]) $;

      21)    end

      22)   end

      23)   $ a \gets b $;

      24)  else

      25)   $ a \gets 0 $;

      26)  end

      27) end

      As we can notice from the exemplified dilations, several voxels have more than one label. In order to measure the amount of tied voxels, we construct Table 1 to compare the pure EDT of Saito and Toriwaki with the proposed method. For this comparison, we use 6 different sets containing 1000 input points each (randomly chosen), inside a discrete cube of $ 100 \times 100 \times 100 $, and 3 labels. A maximum expansion radius of 20 was defined, so that the cube boundaries are increased by 20 for all directions, similar to what Fig. 8 does. The measured values refer to points with $A[x][y][z] \le 20$. Note that, for all inputs, approximately 2.5% of the voxels have tied distances.

      Label Set 01 Set 02 Set 03 Set 04 Set 05 Set 06
      Tied NTied Tied NTied Tied NTied Tied NTied Tied NTied Tied NTied
      100 936247 944462 822954 831422 831523 839873 983186 991294 879977 888355 895426 903816
      010 831824 839400 859005 867982 965758 973871 817325 824627 923833 932493 922427 930366
      001 951265 960138 1034859 1044596 922561 930256 918394 928079 914561 923152 901768 909818
      110 7555 0 8175 0 8596 0 6374 0 8196 0 7882 0
      101 8237 0 7907 0 8152 0 9456 0 8312 0 9171 0
      011 8740 0 10956 0 7308 0 9120 0 9000 0 7231 0
      111 132 0 144 0 102 0 145 0 121 0 95 0

      Table 1.  Comparison of the proposed method with and without tied voxels (Tied and NTied, respectively). Each test represents a point cloud with only 3 labels and 1000 points placed randomly in a discrete cube of 100 × 100 × 100

      It is important to note that previous research[29,33] does not measure the amount of tied voxels for each label. For this to be possible, new algorithms have to be proposed we claim this feature a contribution of this work.

      We also remark that the number of tied voxels with 3 distinct labels tends to be smaller in comparison to 2 labels. This is expected as equidistant regions to 3 VS are less likely to occur. In contrast, the higher the number of labels, the greater the number of ties that may occur. Figs. 9 and 10 show this relationship.

      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.

      As we can see in Fig. 9, the consequence of increasing the number of interest points (VS), or of labels, is an increase in the number of tied pixels. The order of growth seems to be described approximately as a linear function. In addition, Fig. 10 shows the probability for a voxel to be within an equidistant region of 2, 3, 4, or 5 Voronoi sites. For this result we use the log scale, since the probability for a tie to occur between 2 VS is much higher than the others.

    • At the same time as the presented approach improves on the method in [1], it also does not increase its complexity. In fact, they both have the same computational cost, which is not affected by the number of labels.

      Formally, let a binary image $ I $, with $ C \times R $ pixels size, and $N = C\times R$, be the input for a two-dimensional EDT transform. Considering $ n = \sqrt{N} $, the asymptotic complexity of Transformation 1 is $ O(n) $, therefore linear to the image size. Also Algorithms 4 and 5 are linear, following Transformation 1.

      In Transformation 2, Algorithms 6−8, have worst case when the conditions $ b \geq N - y $ (Algorithm 7, Line 7) and $ y - b < 0 $ (Algorithm 8, Line 7), are satisfied. This occurs when $ b - a $ results in the largest possible value, which is close to $ n $. In this case, the asymptotic complexity is $ O(n^3) $, i.e., Transformation 2 can be processed in polynomial time limited to the constant 3. Although this can prevent our approach from being applied over large problem domains, we claim that this worst case rarely appears and, in general, relies on the average time complexity as $O(R_m \times n^2)$, where $ R_m $ is the average radius of the output from Transformation 1 (i.e., the average value of $ b - a $).

      Combined, Algorithms 1−8 add a new point of view to EDT transform, without increasing the time-related computational complexity with respect to similar methods in the literature. The labelling flexibility is limited only by memory requirements, since each used label is associated with a bit in the labelling matrix.

    • This paper modifies and improves on the Saito and Toriwaki method, a fast type Euclidean distance transform algorithm, in order to produce results that solve the tied pixel problem by assigning different labels into a single pixel. It is shown that information about tied pixels, provided by the equidistant regions of seeds, can be employed to perform a better description of objects under analysis, e.g., texture analysis[6], or estimation of dataset classification complexity[31].

      We expect that the proposed methodology opens up new possibilities for future works and trends, looking for new labelling alternatives, in order to better and uniquely describe objects. Computational complexity issues emerging as a result of new applications involving our method are expected to be addressed in future works. A reasonable approach to test is a modular strategy based on cloud decentralization and multi-core processing to allow both parallel and recursive solutions. Engineering applications and tests are also part of our future perspectives.

    • This work was supported by the Brazilian National Council for Scientific and Technological Development (CNPq), Araucaria Foundation, Coordination for the Improvement of Higher Education Personnel (CAPES), and Funding Authority for Studies and Projects (FINEP).

Reference (38)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return