几种联通区域标记的算法介绍

联通区域标记(Connected Component Labeling)是图像处理里面常用的一个技术,它是用来检测二值图像中联通的区域,在许多跟踪检测算法中充当目标区域检测的作用。常见的CCL(Connected Component Labeling)包括Two-Pass的方法和One-Pass的方法,这里pass就是扫描的遍数,Two-Pass就是扫描两遍的算法,One-Pass就是扫描一遍的算法。下面仅就这两类算法中有代表性的算法做一个简单的介绍。

Two-Pass

传统的Two-Pass:

关于该算法的一个形象的描述可以参考博客Labelling connected components – Example。具体的流程是:

  1. 逐行扫描图像上的点,检查每个点是否是前景点,如果不是,继续扫描;
  2. 检查该前景点的左边的点和上边的点
  • 如果有一个为前景点,则为当前扫描点标记和此点相同编号;
  • 如果两个都是前景点,则选择标号小的,为当前扫描点标记编号;这里注意如果两个都是前景点且标号不同,需要把标号小的点设为标号大的点的父节点,以方便第二遍扫描的时候用并查集算法(参考利用不相交集实现等价元素的聚类)合并;
  • 如果都不是,则赋值目前标号label,label++(label初始值为零);
  1. 再次扫描图像,利用并查集算法合并联通的不同的label的区域。

Read More