Please wait a minute...
J4  2014, Vol. 48 Issue (2): 360-367    DOI: 10.3785/j.issn.1008-973X.2014.02.026
    
Computing 3D distance fields with obstacles based on parallel Euclidean Distance Transform
XIE Cong1, LEI Hui2, XU Xing1, CHEN Wei-feng1, CHEN Hai-dong1, YANG Jin-song3, YAN Dan-fang3, CHEN Wei1, YAN Sen-xiang3
1. State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou,310058, China; 2. College of Electronic and
Information Engineering, Changsha University of Science and Technology, 410000, China; 3. Department of
Radiation Oncology,The First Affiliated Hospital of  Zhejiang University, Hangzhou, 310009, China
Download:   PDF(2277KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

To compute a 3D distance transform with obstacles swiftly, this paper proposed a novel GPU-based parallel Euclidean Distance Transform method that consists of two stages: 1) a three-dimensional Voronoi diagram was quickly computed by employing an improved parallelized Euclidean Distance Transform algorithm to the underlying object; 2) the Euclidean distance field with obstacles was computed using a multiple iteration process. The proposed algorithm was applied in radiation therapy planning, i.e., computing clinic treatment volume (CTV) from gross treatment volume (GTV). The result shows that our approach preserves the accuracy of the distance field and achieves great performance speedup comparing to existing approaches, which used brute-force solutions.



Published: 01 February 2014
CLC:  TP 39  
Cite this article:

XIE Cong, LEI Hui, XU Xing, CHEN Wei-feng, CHEN Hai-dong, YANG Jin-song. Computing 3D distance fields with obstacles based on parallel Euclidean Distance Transform. J4, 2014, 48(2): 360-367.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2014.02.026     OR     http://www.zjujournals.com/eng/Y2014/V48/I2/360


基于并行欧式距离变换的三维障碍距离场计算

为了快速计算空间有障碍物的三维欧式距离场,提出一种基于图形处理单元(GPU)的三维空间有障碍物的并行欧式距离场计算算法.该算法包含2步:1) 采用扩展的三维欧氏距离变换算法计算待求物体形状顶点的三维Voronoi图,并用GPU并行计算加速;2) 通过多次迭代快速优化计算有障碍物的欧式距离场.算法在放疗靶区的规划中可用于计算不同级别靶区(GTV)在有障碍物情况下到临床放疗靶区(CTV)的外扩.结果表明,该算法比现有方法一般采用暴力求解的方法性能上有较大提升,同时保持稳定的精度.

[1] AURENHAMMER F. Voronoi diagrams-a survey of a fundamental geometric data structure [J]. ACM Computing Surveys (CSUR), 1991,23(3): 345-405.
[2] MAURER C R Jr, QI R, RAGHAVAN V. A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions [J]. Pattern Analysis and Machine Intelligence, 2003, 25: 265-270.
[3] JANSEN E P M, DEWIT L G H, VAN HERK M, et al. Target volumes in radiotherapy for high-grade malignant glioma of the brain [J]. Radiotherapy and Oncology, 2000, 56(2): 151156.
[4] BARBER B C, DOBKIN D, HUHDANPAA H. The Quickhull algorithm for convex hulls [J]. ACM Transactions on Mathematical Software, 1996, 22(4): 469-483.
[5] DANIELSSON P E. Euclidean distance mapping [J]. Computer Graphics and Image Processing, 1980, 14(3): 227-248.
[6]  WANG Yuh-rau, HORNG Shi-jinn,  LEE Yu-hua, et al. Optimal parallel algorithms for the 3D Euclidean distance transform on the CRCW and EREW PRAM models[C]. ∥Proc. of the 19th Workshop on Comb. Math. and Comp. Theory. [S. l.]: [s. n.], 2001.
[7]  KOLOUNTZAKIS M N, KUTULAKOS K N. Fast computation of the Euclidian distance maps for binary images[J]. Information Processing Letters, 1992, 43(4): 181-184.
[8]  HAYASHI T, NAKANO K, OLARIU S. Optimal parallel algorithms for finding proximate points, with applications [J]. Parallel and Distributed Systems, 1998, 9(12): 1153-1166.
[9]  LEE Y, HORNG S J, SELTZER J. Parallel computation of the Euclidean distance transform on a three-dimensional image array [J]. Parallel and Distributed Systems, 2003, 14(3): 203-212.
[10] CUNTZ N, KOLB A. Fast hierarchical 3D distance transforms on the GPU[J]. Eurographics, Short-Paper, 2007: 93-96.
[11] SUD A, GOVINDARAJU N, GAYLE, et al. Interactive 3D distance field computation using linear factorization [C]∥ 2006 Symposium on Interactive 3D Graphics and Games. [S. l.]: ACM, 2006: 117-124.
[12] RONG G, TAN T S. Jump flooding in GPU with applications to Voronoi diagram and distance transform[C]∥ 2006 Symposium on Interactive 3D Graphics and Games. [S. l.]: ACM, 2006: 109-116.
[13] CAO T T, TANG K, MOHAMED A, et al. Parallel banding algorithm to compute exact distance transform with the GPU [C]∥ 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. Washington, D C: ACM, 2010: 83-90.
[14] BARRY J, WANG C A. Duality of constrained Voronoi diagrams and Delaunay triangulations [J]. Algorithmica, 1999, 9(2): 142-155.
[15] BHATTACHARY A, GAVRILOVA M L. Voronoi diagram in optimal path planning [C]∥ The 4th International Symposium on Voronoi Diagrams in Science and Engineering. [S. l.]: IEEE, 2007: 38-47.
[16] RON W. The Visibility-voronoi complex and its applications [J]. Computational Geometry, 2007, 36(26): 66-87.
[17] LORENSEN W E, CLINE H E. Marching cubes: a high resolution 3D surface construction algorithm[C]∥ACM Siggraph Computer Graphics. [S. l.]: ACM, 1987, 21(4): 163-169.
[18] DOCTOR L J, TORBORG J G. Display techniques for octree-encoded objects[J]. IEEE Computer Graphics and Applications, 1981, 1: 329.
[19] BARRETT W A, MORTENSEN E N. Interactive live-wire boundary extraction [J]. Medical Image Analysis, 1997, 1(4): 331-341.
[20] SCHROEDER W J, AVILA L S, HOFFMAN W. Visualizing with VTK: a tutoria \
[J\]. Computer Graphics and Applications, TEEE, 2000, 20(5): 20-27.

[1] QUAN Hui, MA Li-zhuang. Visceral fat estimation method based on
bioelectrical impedance technology
[J]. J4, 2011, 45(2): 301-305.
[2] ZHANG Bao-Jun, BENG Ling-Di, BO Xue-Ceng, et al. Data compression and storage under high speed network[J]. J4, 2009, 43(09): 1585-1590.