A run-based two-scan labeling algorithm
A run-based two-scan labeling algorithm
复制标题
DOI：
10.1109/tip.2008.919369
复制
发表时间：
2008-05-01
影响因子：
10.6
通讯作者：
Suzuki, Kenji
中科院分区：
文献类型：
--
作者：
He, Lifeng;Chao, Yuyan;Suzuki, Kenji
我们提出了一种高效的基于运行的两次扫描算法，用于标记二值图像中的连通分量。与解决临时标签之间的标签等效性的传统基于标签等效性的算法不同，我们的算法解决临时标签集之间的标签等效性。在任何时候，分配给连接组件的所有临时标签都被组合在一个集合中，并且最小的标签被用作代表标签。临时标签与其代表标签的对应关系记录在表格中。每当发现不同的连通分量存在连通时，将与这些连通分量有关的所有临时标签集合并在一起，并取最小的临时标签作为代表标签。第一次扫描完成后，分配给给定图像中每个连接组件的所有临时标签将具有唯一的代表性标签。在第二次扫描期间，我们只需要将每个临时标签替换为其代表标签即可。各种类型图像的实验结果表明，我们的算法优于所有传统的标记算法。
We present an efficient run-based two-scan algorithm for labeling connected components in a binary image. Unlike conventional label-equivalence-based algorithms, which resolve label equivalences between provisional labels, our algorithm resolves label equivalences between provisional label sets. At any time, all provisional labels that are assigned to a connected component are combined in a set, and the smallest label is used as the representative label. The corresponding relation of a provisional label and its representative label is recorded in a table. Whenever different connected components are found to be connected, all provisional label sets concerned with these connected components are merged together, and the smallest provisional label is taken as the representative label. When the first scan is finished, all provisional labels that were assigned to each connected component in the given image will have a unique representative label. During the second scan, we need only to replace each provisional label by its representative label. Experimental results on various types of images demonstrate that our algorithm outperforms all conventional labeling algorithms.