Most existing algorithms of three-dimensional distance transform are extensions of two-dimensional approximate Euclidean distance transform algorithms such as the city block/chessboard. Such algorithms can only get the approximate Euclidean distance. A new method of three-dimensional true Euclidean distance transform is presented in this paper. The proposed method can get the true Euclidean distance with time complexity O(n3*log n). Moreover, this method is used to render the soft tissue in three-dimensional medical CT images, and good result has been obtained.
[1] Rosenfield, A., Pfaltz, J. Sequential operations in digital picture processing. Journal of Association for Computing Machinery, 1996,13(4):471~494.
[2] Chen, Ling. Optimal algorithm of true Euclidean distance transform. Chinese Journal of Computers, 1995,8(18):611~616 (in Chinese).陈山 菱.完全欧几里德距离变换的最优算法.计算机学报,1995,8(18):611~616.
[3] Okabe, N., Toriwaki, J., Fukumura, T. Paths and distance functions on three-dimensional digitized pictures. Pattern Recognition Letter, 1983,1:205~212.
[4] Borgefors, G. On digital distance transforms in three dimensions. Computer Vision and Image Understanding, 1996,64(3):368~376.
[5] Ragnemalm, I. The Euclidean distance transform in arbitrary dimensions. Pattern Recognition Letter, 1993,14:883~888.