摘要
提出了一种顾及障碍物的欧氏距离变换方法。该方法基于栅格扫描方式进行距离变换,逐行逐列传播距离值,并在距离传播过程中进行可见性检测,从而使距离传递路径避开障碍物,得到一种反映实际通行距离的欧氏距离图像。该算法思路简单直接,不涉及任何复杂数据结构,具有线性时间复杂度。实验表明,该算法计算出的距离图像准确性高,优于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.
出处
《中山大学学报（自然科学版）》
CAS
CSCD
北大核心
2013年第1期130-135,共6页
Acta Scientiarum Naturalium Universitatis Sunyatseni
基金
国家自然科学基金资助项目(40971210)
关键词
欧氏距离变换
障碍物
可见性
Euclidean distance transform
obstacle
visibility
