三维完全欧氏距离变换的改进算法  

Improved Algorithm of Complete Three-dimensional Euclidean Distance Transform

作　　者：董箭[1] 彭认灿[1] 郑义东[1] 

机构地区：[1]海军大连舰艇学院海洋测绘系,辽宁大连116018

出　　处：《海洋测绘》2013年第1期5-8,共4页Hydrographic Surveying and Charting

基　　金：国家自然科学基金项目(40801189);国家863计划项目(2009AA12Z202)

摘　　要：三维欧氏距离变换是对由黑白像素构成的三维二值图像中所有像素找出其到最近黑色像素的欧氏距离。在对现有三维欧氏距离变换算法进行深入研究的基础上,充分利用二维欧氏距离变换的结果,进一步减少参与距离计算和比较的黑点个数,进而提出了三维完全欧氏距离变换的改进算法。整个算法的时间复杂度为O((n3log n)/φ(n))。并将该改进算法应用于海底污染源的扩散分析,取得了较好的效果。The three-dimensional euclidean distance transform converts a three-dimensional image into one where each pixel has a value equal to its euclidean distance to the nearest foreground pixel. After having lucubrated the existent algorithm of three-dimensional euclidean distance transform, the paper makes full use of the result of binary euclidean distance transform to reduce the number of pixels in distance calculation and comparison, and the improved algorithm of complete three-dimensional euclidean distance transform with time complexity O（ （n3log n）/φ（n））has been put forward. Moreover, the improved algorithm is used to analyse pollution diffusion, and good result has been obtained.

关 键 词：三维完全欧氏距离变换 二维欧氏距离变换 改进算法 时间复杂度 

分 类 号：P237[天文地球—摄影测量与遥感]