Abstract
The Euclidean distance transform (EDT) is used in many essential operations in image processing, such as basic morphology, level sets, registration and path finding. The anti-aliased Euclidean distance transform (AAEDT), previously presented for two-dimensional images, uses the gray-level information in, for example, area sampled images to calculate distances with sub-pixel precision. Here, we extend the studies of AAEDT to three dimensions, and to the Body-Centered Cubic (BCC) and Face-Centered Cubic (FCC) lattices, which are, in many respects, considered the optimal three-dimensional sampling lattices. We compare different ways of converting gray-level information to distance values, and find that the lesser directional dependencies of optimal sampling lattices lead to better approximations of the true Euclidean distance.
Chapter PDF
Similar content being viewed by others
References
Borgefors, G.: Applications using distance transforms. In: Arcelli, C., Cordella, L.P., Sanniti di Baja, G. (eds.) Aspects of Visual Form Processing: Proceedings of the Second International Workshop on Visual Form, pp. 83–108. World Scientific Publishing (1994)
Chen, W., Li, M., Su, X.: Error analysis about ccd sampling in fourier transform profilometry. Optik - International Journal for Light and Electron Optics 120(13), 652–657 (2009)
Clifford Chao, K.S., Ozyigit, G., Blanco, A.I., Thorstad, W.L., O Deasy, J., Haughey, B.H., Spector, G.J., Sessions, D.G.: Intensity-modulated radiation therapy for oropharyngeal carcinoma: impact of tumor volume. International Journal of Radiation Oncology*Biology*Physics 59(1), 43–50 (2004)
Entezari, A.: Towards computing on non-cartesian lattices. Tech. rep. (2006)
Gustavson, S., Strand, R.: Anti-aliased Euclidean distance transform. Pattern Recognition Letters 32(2), 252–257 (2011)
Jones, M.W., Bærentsen, J.A., Sramek, M.: 3D distance fields: A survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics 12(4), 581–599 (2006)
Lebioda, A., Żyromska, A., Makarewicz, R., Furtak, J.: Tumour surface area as a prognostic factor in primary and recurrent glioblastoma irradiated with 192ir implantation. Reports of Practical Oncology & Radiotherapy 13(1), 15–22 (2008)
Linnér, E., Strand, R.: Aliasing properties of voxels in three-dimensional sampling lattices. In: Lirkov, I., Margenov, S., Waśniewski, J. (eds.) LSSC 2011. LNCS, vol. 7116, pp. 507–514. Springer, Heidelberg (2012)
Linnér, E., Strand, R.: A graph-based implementation of the anti-aliased Euclidean distance transform. In: International Conference on Pattern Recognition (August 2014)
Meng, T., Smith, B., Entezari, A., Kirkpatrick, A.E., Weiskopf, D., Kalantari, L., Möller, T.: On visual quality of optimal 3D sampling and reconstruction. In: Proceedings of Graphics Interface (2007)
Metropolis, N., Ulam, S.: The monte carlo method. Journal of the American Statistical Association 44(247), 335–341 (1949)
Sladoje, N., Lindblad, J.: High-precision boundary length estimation by utilizing gray-level information. IEEE Transactions on Pattern Analysis and Machine Intelligence 31(2), 357–363 (2009)
Sladoje, N., Nyström, I., Saha, P.K.: Measurements of digitized objects with fuzzy borders in 2D and 3D. Image and Vision Computing 23(2), 123–132 (2005)
Strand, R.: Sampling and aliasing properties of three-dimensional point-lattices (2010), http://www.diva-portal.org/smash/record.jsf?searchId=1&pid=diva2:392445&rvn=3
Theußl, T., Möller, T., Gröller, M.E.: Optimal regular volume sampling. In: Proceedings of the Conference on Visualization (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Linnér, E., Strand, R. (2014). Anti-Aliased Euclidean Distance Transform on 3D Sampling Lattices. In: Barcucci, E., Frosini, A., Rinaldi, S. (eds) Discrete Geometry for Computer Imagery. DGCI 2014. Lecture Notes in Computer Science, vol 8668. Springer, Cham. https://doi.org/10.1007/978-3-319-09955-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-09955-2_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09954-5
Online ISBN: 978-3-319-09955-2
eBook Packages: Computer ScienceComputer Science (R0)