二值图像的图像的亮度值只有两个状态：黑(0)和白(255)。二值图像在图像分析与识别中有着举足轻重的地位，因为其模式简单，对像素在空间上的关系有着极强的表现力。在实际应用中，很多图像的分析最终都转换为二值图像的分析，比如：医学图像分析、前景检测、字符识别，形状识别。二值化+数学形态学能解决很多计算机识别工程中目标提取的问题。

二值图像分析最重要的方法就是连通区域标记，它是所有二值图像分析的基础，它通过对二值图像中白色像素（目标）的标记，让每个单独的连通区域形成一个被标识的块，进一步的我们就可以获取这些块的轮廓、外接矩形、质心、不变矩等几何参数。

下面是一个二值图像被标记后，比较形象的显示效果，这就是我们这篇文章的目标。

在我们讨论连通区域标记的算法之前，我们先要明确什么是连通区域，怎样的像素邻接关系构成连通。在图像中，最小的单位是像素，每个像素周围有8个邻接像素，常见的邻接关系有2种：4邻接与8邻接。4邻接一共4个点，即上下左右，如下左图所示。8邻接的点一共有8个，包括了对角线位置的点，如下右图所示。

如果像素点A与B邻接，我们称A与B连通，于是我们不加证明的有如下的结论：

如果A与B连通，B与C连通，则A与C连通。

在视觉上看来，彼此连通的点形成了一个区域，而不连通的点形成了不同的区域。这样的一个所有的点彼此连通点构成的集合，我们称为一个连通区域。

下面这符图中，如果考虑4邻接，则有3个连通区域；如果考虑8邻接，则有2个连通区域。（注：图像是被放大的效果，图像正方形实际只有4个像素）。

三、连通区域分析

连通区域（Connected Component）一般是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域（Region，Blob）。连通区域分析（Connected Component Analysis,Connected Component Labeling）是指将图像中的各个连通区域找出并标记。

连通区域分析是一种在CVPR和图像分析处理的众多应用领域中较为常用和基本的方法。例如：OCR识别中字符分割提取（车牌识别、文本识别、字幕识别等）、视觉跟踪中的运动前景目标分割与提取（行人入侵检测、遗留物体检测、基于视觉的车辆检测与跟踪等）、医学图像处理（感兴趣目标区域提取）、等等。也就是说，在需要将前景目标提取出来以便后续进行处理的应用场景中都能够用到连通区域分析方法，通常连通区域分析处理的对象是一张二值化后的图像。

连通区域标记算法有很多种，有的算法可以一次遍历图像完成标记，有的则需要2次或更多次遍历图像。这也就造成了不同的算法时间效率的差别，在这里我们介绍2种算法。

第一种算法是现在matlab中连通区域标记函数bwlabel中使的算法，它一次遍历图像，并记下每一行（或列）中连续的团（run）和标记的等价对，然后通过等价对对原来的图像进行重新标记，这个算法是目前我尝试的几个中效率最高的一个，但是算法里用到了稀疏矩阵与Dulmage-Mendelsohn分解算法用来消除等价对，这部分原理比较麻烦，所以本文里将不介绍这个分解算法，取而代这的用图的深度优先遍历来替换等价对。

第二种算法是现在开源库cvBlob中使用的标记算法，它通过定位连通区域的内外轮廓来标记整个图像，这个算法的核心是轮廓的搜索算法，这个我们将在文章中详细介绍。这个算法相比与第一种方法效率上要低一些，但是在连通区域个数在100以内时，两者几乎无差别，当连通区域个数到了 103 103数量级时，上面的算法会比该算法快10倍以上。

我们首先给出算法的描述，然后再结合实际图像来说明算法的步骤。

1，逐行扫描图像，我们把每一行中连续的白色像素组成一个序列称为一个团(run)，并记下它的起点start、它的终点end以及它所在的行号。

2，对于除了第一行外的所有行里的团，如果它与前一行中的所有团都没有重合区域，则给它一个新的标号；如果它仅与上一行中一个团有重合区域，则将上一行的那个团的标号赋给它；如果它与上一行的2个以上的团有重叠区域，则给当前团赋一个相连团的最小标号，并将上一行的这几个团的标记写入等价对，说明它们属于一类。

3，将等价对转换为等价序列，每一个序列需要给一相同的标号，因为它们都是等价的。从1开始，给每个等价序列一个标号。

4，遍历开始团的标记，查找等价序列，给予它们新的标记。

5，将每个团的标号填入标记图像中。

6，结束。

我们来结合一个三行的图像说明，上面的这些操作。

第一行，我们得到两个团：[2,6]和[10,13]，同时给它们标记1和2。

第二行，我们又得到两个团：[6,7]和[9,10]，但是它们都和上一行的团有重叠区域，所以用上一行的团标记，即1和2。

第三行，两个：[2,4]和[7,8]。[2,4]这个团与上一行没有重叠的团，所以给它一个新的记号为3；而[2,4]这个团与上一行的两个团都有重叠，所以给它一个两者中最小的标号，即1，然后将（1，2）写入等价对。

全部图像遍历结束，我们得到了很多个团的起始坐标，终止坐标，它们所在的行以及它们的标号。同时我们还得到了一个等价对的列表。

下面我们用C++实现上面的过程，即步骤2，分两个进行：

1）fillRunVectors函数完成所有团的查找与记录；

2）firstPass函数完成团的标记与等价对列表的生成。相比之下第二个函数要稍微难理解一些。

3）颜色标记（用于显示）