A fast algorithm for integrating connected-component labeling and Euler number computation
A fast algorithm for integrating connected-component labeling and Euler number computation
复制标题
一种集成连通分量标记和欧拉数计算的快速算法
DOI：
10.1007/s11554-015-0499-1
复制
发表时间：
2017
影响因子：
3
通讯作者：
Y. Chao
中科院分区：
文献类型：
--
作者：
Lifeng He;B. Yao;X. Zhao;H. Kasuya;Y. Chao
提出了一种将连通分支标号和欧拉数计算相结合的快速算法。该算法基于图论，在连通成分标记过程的第一次扫描中，通过统计用于处理前景像素的掩模的四个模式的出现次数来计算二值图像的欧拉数，这四个模式不需要任何额外的计算就可以直接找到，从而可以更有效地将连通成分标记和欧拉数的计算结合在一起。此外，与其他传统算法不同的是，在计算欧拉数时，该算法不需要处理背景像素。实验结果表明，无论是单独计算欧拉数，还是同时计算欧拉数和标号连通分支，该算法都比传统算法有更高的效率。
This paper proposes a fast algorithm for integrating connected-component labeling and Euler number computation. Based on graph theory, the Euler number of a binary image in the proposed algorithm is calculated by counting the occurrences of four patterns of the mask for processing foreground pixels in the first scan of a connected-component labeling process, where these four patterns can be found directly without any additional calculation; thus, connected-component labeling and Euler number computation can be integrated more efficiently. Moreover, when computing the Euler number, unlike other conventional algorithms, the proposed algorithm does not need to process background pixels. Experimental results demonstrate that the proposed algorithm is much more efficient than conventional algorithms either for calculating the Euler number alone or simultaneously calculating the Euler number and labeling connected components.