Please wait a minute...
浙江大学学报(工学版)
J4  2014, Vol. 48 Issue (2): 360-367    DOI: 10.3785/j.issn.1008-973X.2014.02.026
电气工程、计算机技术     
基于并行欧式距离变换的三维障碍距离场计算
解聪1, 雷辉2, 徐星1, 陈伟锋1, 陈海东1,杨劲松3, 严丹方3, 陈为1, 严森祥3
1.浙江大学 CAD&CG国家重点实验室,浙江 杭州 310058; 2.湖南长沙理工大学 电气与信息工程学院,
湖南 长沙 410000; 3. 浙江大学 附属第一医院放疗科,浙江 杭州 310000
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
 全文: PDF(2277 KB)   HTML
摘要：

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

国家自然科学基金资助项目(81172124,61232012)；国家“863”高技术研究发展计划资助项目(2012AA12090);浙江省公益技术研究社会发展项目（N2013C33121）；湖南省科技计划资助项目(2010GK3064).
通讯作者: 严森祥，男，教授.     E-mail: yansenxiang@zju.edu.cn
作者简介: 解聪（1989—)，男，硕士，主要研究方向为医学影像可视化.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

解聪, 雷辉, 徐星, 陈伟锋, 陈海东,杨劲松, 严丹方, 陈为, 严森祥. 基于并行欧式距离变换的三维障碍距离场计算[J]. J4, 2014, 48(2): 360-367.

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.

链接本文:

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

［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] 全卉, 马利庄. 基于生物电阻抗的人体内脏脂肪预测方法[J]. J4, 2011, 45(2): 301-305.
[2] 张宝军, 平玲娣, 潘雪增, 等. 高速网络环境下数据的压缩存储[J]. J4, 2009, 43(09): 1585-1590.