Algorithm of complete Euclidean distance transformation based on contour hierarchical scanning
基于围线分层扫描的完全欧氏距离变换算法

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.