一种顾及障碍物的欧氏距离变换方法  

Euclidean Distance Transform by Raster Scan in Obstacle Space

作　　者：张青年[1] 

机构地区：[1]中山大学地理科学与规划学院,广东广州510275

出　　处：《中山大学学报（自然科学版）》2013年第1期130-135,共6页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金资助项目(40971210)

摘　　要：提出了一种顾及障碍物的欧氏距离变换方法。该方法基于栅格扫描方式进行距离变换,逐行逐列传播距离值,并在距离传播过程中进行可见性检测,从而使距离传递路径避开障碍物,得到一种反映实际通行距离的欧氏距离图像。该算法思路简单直接,不涉及任何复杂数据结构,具有线性时间复杂度。实验表明,该算法计算出的距离图像准确性高,优于ArcGIS基于距离累计的算法,适合于点、线、面3种形态的源和障碍物的欧氏距离变换。An algorithm of Euclidean distance transform was proposed by raster scan in obstacle space. It propagates distances line by line, checking the visibility of target pixels, and calculating the distance by finding a shortest way from a source to the target keeping away from obstacles. The algorithm is straightforward for distance calculation, involving in no complicated data structure, and having a linear computational complexity. Case study showed that the calculated distances by this algorithm were accu- rate, better than the results by the distance accumulation-based algorithm, and suitable for sources and obstacles in any types of shapes, including point, line and area objects.

关 键 词：欧氏距离变换 障碍物 可见性 

分 类 号：P208[天文地球—地图制图学与地理信息工程]