三维欧氏距离变换快速算法  

A Fast 3D Euclidean Distance Transformation

作　　者：李均利[1] 陈爽[1] 王秀英 

机构地区：[1]四川师范大学计算机学院,成都610066 [2]School of Information Technologies,Sydney University

出　　处：《计算机辅助设计与图形学学报》2012年第12期1559-1567,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60832003)

摘　　要：为了提高三维距离变换在实际应用中的计算效率,提出一种三维快速距离变换算法.首先将三维图像降维为多张二维图像,为每张二维图像设置2个标记数组,并根据标记数组运用围线扫描方法依次计算出每一像素在二维图像上的距离变换;然后依据二维结果计算出所有像素在三维图像中的距离变换.实验结果表明,文中算法实现简单,比已有的边界剥离算法及基于Voronoi图的算法在时间和空间消耗上均有较大的提高,有更好的实用性.In order to improve the computing efficiency in practice, a fast distance transform algorithm for 3D image is proposed. Firstly, a 3D image is transformed into several slices of 2D images, for each 2D image two marked arrays are defined. Then, the distance transformation of each pixel in the 2D images is calculated according to the marked arrays, using the contour scanning method. Finally, the distance transformation of each pixel in the 3D image is calculated based on the results of the 2D distance transformations. The proposed algorithm is easy to implement and the experimental results show it demonstrates a significant improvement in reducing time and space complexity, comparing with the existing boundary striping and Voronoi-based algorithms, and thus it has stronger practicability.

关 键 词：欧氏距离变换 围线扫描 标记数组 搜索半径 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]