以障碍物凸角点为中继源的欧氏距离变换算法

摘要

已有的测地距离变换算法顾及了障碍物的影响，但存在较大的距离误差。针对这一问题，提出了一种在障碍空间中进行精确的测地距离变换的蛮力算法。该算法将障碍物的凸角点视为中继源，利用中继源计算特征像元到障碍物背后的背景像元的最短可通行距离。与已有的测地距离变换算法不同，该算法选取的中继源位于最短距离传播路径上，偏移量为零。实验结果表明，该算法不存在距离计算误差，其距离准确性不受障碍物数量、位置和形状的影响。%The existing geodesic distance transform algorithms consider the influence of obstacles,but the calculated distances have errors.A brute-force algorithm is suggested for accurate geodesic distance transform in a space with obstacles in this paper.It takes the convex corners on obstacles as relay sources to calculate the length of the shortest passable path from foreground pixels to background pixels behind the obstacles.The relay sources of this algorithm lie on the shortest passable paths from foreground pixels to background pixels,and thus distance errors are avoided,better than other relay sources suggested in the existing geodesic distance transform algorithms.Experimental results show that there is no distance error in the new algorithm,and it is applicable for distance transform in space with obstacles in any shapes.