[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

EDT Method for Multiple Labelled Objects Subject to Tied Distances

  • Research Article
  • Published:
International Journal of Automation and Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  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: https://doi.org/10.1016/0031-3203(94)90133-3.

    Article  Google Scholar 

  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: https://doi.org/10.1145/321356.321357.

    Article  Google Scholar 

  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: https://doi.org/10.1007/s00138-010-0307-7.

    Article  Google Scholar 

  4. S. Gustavson, R. Strand. Anti-aliased Euclidean distance transform. Pattern Recognition Letters, vol. 32, no. 2, pp. 252–257, 2011. DOI: https://doi.org/10.1016/j.patrec.2010.08.010.

    Article  Google Scholar 

  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: https://doi.org/10.1007/s11633-019-1211-x.

    Article  Google Scholar 

  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: https://doi.org/10.1016/j.ins.2016.01.077.

    Article  Google Scholar 

  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: https://doi.org/10.1007/s11633-018-1141-z.

    Article  Google Scholar 

  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: https://doi.org/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: https://doi.org/10.1016/j.ins.2018.05.037.

    Article  MathSciNet  Google Scholar 

  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: https://doi.org/10.1016/j.physa.2014.07.074.

    Article  Google Scholar 

  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: https://doi.org/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: https://doi.org/10.1016/j.ins.2018.08.038.

    Article  Google Scholar 

  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: https://doi.org/10.1080/00207720802630719.

    Article  Google Scholar 

  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: https://doi.org/10.1080/00207720802630685.

    Article  Google Scholar 

  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: https://doi.org/10.1007/s11633-020-1221-8.

    Article  Google Scholar 

  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: https://doi.org/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: https://doi.org/10.1080/00207720050197776.

    Article  MathSciNet  Google Scholar 

  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: https://doi.org/10.1007/s11633-018-1163-6.

    Article  Google Scholar 

  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: https://doi.org/10.1007/s11633-020-1231-6.

    Article  Google Scholar 

  20. E. Remy, E. Thiel. Exact medial axis with Euclidean distance. Image and Vision Computing, vol. 23, no. 2, pp. 167–175, 2005. DOI: https://doi.org/10.1016/j.imavis.2004.06.007.

    Article  Google Scholar 

  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: https://doi.org/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: https://doi.org/10.1016/j.patcog.2003.08.003.

    Article  Google Scholar 

  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: https://doi.org/10.1007/978-3-540-72847-4_14.

    Chapter  Google Scholar 

  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: https://doi.org/10.1109/34.391389.

    Article  Google Scholar 

  25. T. Hirata. A unified linear-time algorithm for computing distance maps. Information Processing Letters, vol. 58, no. 3, pp. 129–133, 1996. DOI: https://doi.org/10.1016/0020-0190(96)00049-X.

    Article  MathSciNet  Google Scholar 

  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: https://doi.org/10.1109/TPAMI.2003.1177156.

    Article  Google Scholar 

  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: https://doi.org/10.1007/978-3-540-30503-3_28.

    Chapter  Google Scholar 

  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: https://doi.org/10.1016/0031-3203(94)00104-T.

    Article  Google Scholar 

  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: https://doi.org/10.1016/j.imavis.2006.06.020.

    Article  Google Scholar 

  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: https://doi.org/10.1016/j.ins.2018.06.021.

    Article  Google Scholar 

  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: https://doi.org/10.1504/IJCSE.2019.103261.

    Article  Google Scholar 

  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: https://doi.org/10.1007/s11633-019-1219-2.

    Article  Google Scholar 

  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: https://doi.org/10.1016/j.ipl.2006.12.005.

    Article  MathSciNet  Google Scholar 

  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: https://doi.org/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.

    Book  Google Scholar 

  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: https://doi.org/10.1016/1049-9652(92)90034-U.

    Google Scholar 

  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: https://doi.org/10.1006/cviu.1999.0783.

    Article  Google Scholar 

  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: https://doi.org/10.1109/SIBGRAPI.2001.963043.

    Chapter  Google Scholar 

Download references

Acknowledgements

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

Author information

Authors and Affiliations

  1. Federal University of Technology, Parana, Pato Branco, 85503-390, Brazil

    Andre Marasca, Fabio Favarim, Marcelo Teixeira & Dalcimar Casanova

  2. Federal University of Uberlandia, Uberlandia, 38400-902, Brazil

    Andre Backes

Authors
  1. Andre Marasca
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andre Backes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fabio Favarim
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marcelo Teixeira
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Dalcimar Casanova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marcelo Teixeira.

Additional information

Recommended by Associate Editor Bin Luo

Colored figures are available in the online version at https://link.springer.com/journal/11633

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.

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.

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.

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, cyberphysical systems, flexible manufacturing systems, industry 4.0, synthesis of controllers for industrial processes, industrial automation, and automatic synthesis of software.

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.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Marasca, A., Backes, A., Favarim, F. et al. EDT Method for Multiple Labelled Objects Subject to Tied Distances. Int. J. Autom. Comput. 18, 468–479 (2021). https://doi.org/10.1007/s11633-021-1285-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11633-021-1285-0

Keywords

Search

Navigation