围线扫描欧氏距离变换算法是一种快速的完全欧氏距离变换算法,其时间复杂度达到最优,但需在围线区域进行全局搜索,计算时间并未优化.针对此问题,提出了一种基于围线分层扫描的完全欧氏距离算法.该算法首先根据中心像素的围线性质对二值图像像素点进行重新分类,然后按照围线区域像素与中心像素的空间关系,对中心像素的围线区域进行分层搜索,并给出了搜索的终止条件.该算法保持了最优的时间复杂度,可通过定量分析单个像素的计算时间来证明其计算时间已得到优化.实验结果表明,该算法能够得到准确的欧氏距离图像,且运行速度快.%Contour scanning based Euclidean distance transformation (EDT) is a fast and complete EDT algorithm and achieves the optimum complexity. But it needs to search all contour regions, so the computation is not optimal. To overcome this disadvantage, an EDT algorithm based on contour hierarchical scanning was proposed. First, reclassifying pixels of the binary image according contour character of central pixel is needed. Second, according the spatial relationship between contour region pixel and central pixel, searching contour region of central pixel hierarchically is the main step to reduce the computation. Finally, we use the proposed terminal condition ends the searching. Theoretically, the proposed algorithm maintains the optimum complexity and reduces the computation. Likewise, the experiments showed that the proposed algorithm can obtain the Euclidean distance images exactly and reduce the calculation time cost.
展开▼
