二值图像，顾名思义就是图像的亮度值只有两个状态：黑(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个像素）。
连通区域标记算法有很多种，有的算法可以一次遍历图像完成标记，有的则需要2次或更多次遍历图像。这也就造成了不同的算法时间效率的差别，在这里我们介绍2种算法。
第一种算法是现在matlab中连通区域标记函数bwlabel中使的算法，它一次遍历图像，并记下每一行（或列）中连续的团（run）和标记的等价对，然后通过等价对对原来的图像进行重新标记，这个算法是目前我尝试的几个中效率最高的一个，但是算法里用到了稀疏矩阵与Dulmage-Mendelsohn分解算法用来消除等价对，这部分原理比较麻烦，所以本文里将不介绍这个分解算法，取而代这的用图的深度优先遍历来替换等价对。
第二种算法是现在开源库cvBlob中使用的标记算法，它通过定位连通区域的内外轮廓来标记整个图像，这个算法的核心是轮廓的搜索算法，这个我们将在文章中详细介绍。这个算法相比与第一种方法效率上要低一些，但是在连通区域个数在100以内时，两者几乎无差别，当连通区域个数到了3
我们首先给出算法的描述，然后再结合实际图像来说明算法的步骤。
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函数完成所有团的查找与记录；
1 void fillRunVectors(const Mat& bwImage, int& NumberOfRuns, vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun) 2 { 3 for (int i = 0; i < bwImage.rows; i++) 4 { 5 const uchar* rowData = bwImage.ptr<uchar>(i); 6 7 if (rowData[0] == 255) 8 { 9 NumberOfRuns++; 10 stRun.push_back(0); 11 rowRun.push_back(i); 12 } 13 for (int j = 1; j < bwImage.cols; j++) 14 { 15 if (rowData[j - 1] == 0 && rowData[j] == 255) 16 { 17 NumberOfRuns++; 18 stRun.push_back(j); 19 rowRun.push_back(i); 20 } 21 else if (rowData[j - 1] == 255 && rowData[j] == 0) 22 { 23 enRun.push_back(j - 1); 24 } 25 } 26 if (rowData[bwImage.cols - 1]) 27 { 28 enRun.push_back(bwImage.cols - 1); 29 } 30 } 31 }
2）firstPass函数完成团的标记与等价对列表的生成。相比之下第二个函数要稍微难理解一些。
1 void firstPass(vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun, int NumberOfRuns, 2 vector<int>& runLabels, vector<pair<int, int>>& equivalences, int offset) 3 { 4 runLabels.assign(NumberOfRuns, 0); 5 int idxLabel = 1; 6 int curRowIdx = 0; 7 int firstRunOnCur = 0; 8 int firstRunOnPre = 0; 9 int lastRunOnPre = -1; 10 for (int i = 0; i < NumberOfRuns; i++) 11 { 12 if (rowRun[i] != curRowIdx) 13 { 14 curRowIdx = rowRun[i]; 15 firstRunOnPre = firstRunOnCur; 16 lastRunOnPre = i - 1; 17 firstRunOnCur = i; 18 19 } 20 for (int j = firstRunOnPre; j <= lastRunOnPre; j++) 21 { 22 if (stRun[i] <= enRun[j] + offset && enRun[i] >= stRun[j] - offset) 23 { 24 if (runLabels[i] == 0) // 没有被标号过 25 runLabels[i] = runLabels[j]; 26 else if (runLabels[i] != runLabels[j])// 已经被标号 27 equivalences.push_back(make_pair(runLabels[i], runLabels[j])); // 保存等价对 28 } 29 } 30 if (runLabels[i] == 0) // 没有与前一列的任何run重合 31 { 32 runLabels[i] = idxLabel++; 33 } 34 35 } 36 }
接下来是我们的重点，即等价对的处理，我们需要将它转化为若干个等价序列。比如有如下等价对：
(1,2),(1,6),(3,7),(9-3),(8,1),(8,10),(11,5),(11,8),(11,12),(11,13),(11,14),(15,11)
我们需要得到最终序列是：
一个思路是将1-15个点都看成图的结点，而等价对（1，2）说明结点1与结点2之间有通路，而且形成的图是无向图，即（1，2）其实包含了（2，1）。我们需要遍历图，找出其中的所有连通图。所以我们采用了图像深入优先遍历的原理，进行等价序列的查找。
从结点1开始，它有3个路径1-2，1-6，1-8。2和6后面都没有路径，8有2条路径通往10和11，而10没有后续路径，11则有5条路径通往5，12，13，14，15。等价表1查找完毕。
第2条等价表从3开始，则只有2条路径通向7和9，7和9后面无路径，等价表2查找完毕。
最后只剩下4，它没有在等价对里出现过，所以单儿形成一个序列（这里假设步骤2中团的最大标号为15）。
下面是这个过程的C++实现，每个等价表用一个vector<int>来保存，等价对列表保存在map<pair<int,int>>里。
1 void replaceSameLabel(vector<int>& runLabels, vector<pair<int, int>>& 2 equivalence) 3 { 4 int maxLabel = *max_element(runLabels.begin(), runLabels.end()); 5 vector<vector<bool>> eqTab(maxLabel, vector<bool>(maxLabel, false)); 6 vector<pair<int, int>>::iterator vecPairIt = equivalence.begin(); 7 while (vecPairIt != equivalence.end()) 8 { 9 eqTab[vecPairIt->first - 1][vecPairIt->second - 1] = true; 10 eqTab[vecPairIt->second - 1][vecPairIt->first - 1] = true; 11 vecPairIt++; 12 } 13 vector<int> labelFlag(maxLabel, 0); 14 vector<vector<int>> equaList; 15 vector<int> tempList; 16 cout << maxLabel << endl; 17 for (int i = 1; i <= maxLabel; i++) 18 { 19 if (labelFlag[i - 1]) 20 { 21 continue; 22 } 23 labelFlag[i - 1] = equaList.size() + 1; 24 tempList.push_back(i); 25 for (vector<int>::size_type j = 0; j < tempList.size(); j++) 26 { 27 for (vector<bool>::size_type k = 0; k != eqTab[tempList [j] - 1].size(); k++) 28 { 29 if (eqTab[tempList[j] - 1][k] && !labelFlag[k]) 30 { 31 tempList.push_back(k + 1); 32 labelFlag[k] = equaList.size() + 1; 33 } 34 } 35 } 36 equaList.push_back(tempList); 37 tempList.clear(); 38 } 39 cout << equaList.size() << endl; 40 for (vector<int>::size_type i = 0; i != runLabels.size(); i++) 41 { 42 runLabels[i] = labelFlag[runLabels[i]-1]; 43 } 44 }
在这里我还是先给出算法描述：
1，从上至下，从左至右依次遍历图像。
2，如下图A所示，A为遇到一个外轮廓点（其实上遍历过程中第一个遇到的白点即为外轮廓点），且没有被标记过，则给A一个新的标记号。我们从A点出发，按照一定的规则（这个规则后面详细介绍）将A所在的外轮廓点全部跟踪到，然后回到A点，并将路径上的点全部标记为A的标号。
3，如下图B所示，如果遇到已经标记过的外轮廓点′
′
′
4，如下图C所示，如果遇到了一个已经被标记的点B，且是内轮廓的点(它的正下方像素为黑色像素且不在外轮廓上)，则从B点开始，跟踪内轮廓，路径上的点都设置为B的标号，因为B已经被标记过与A相同，所以内轮廓与外轮廓将标记相同的标号。
5，如下图D所示，如果遍历到内轮廓上的点，则也是用轮廓的标号去标记它右侧的点，直到遇到黑色像素为止。
6，结束。
所以总结起来，这个算法步骤非常简单：
1）找到所有外轮廓及与之对应的内轮廓（如果有的话），并给轮廓上的点标上标号。
2）遍历标记的图像，如果这个点在原来二值图像上为白色点，且在标记图像上没有标记过，则给它一个标号且等于它左边点的标号。
显然，这个算法的重点在于轮廓的查找与标记，而对于轮廓的查找，就是确定搜索策略的问题，我们下面给内轮廓与外轮廓定义tracker规则。
我们对一点像素点周围的8个位置作一个记号，对于外轮廓上的点A，如果它是起始点，则从位置7开始按顺时针方向查找，直到遇到白色像素，则按那个方向搜索一步。如果不是起始点，那它有一个进入点位置（路径传过来的位置）N，我们则从
这里特别要做的一步是，一个点在它周围搜索过程中，在找到白色的路上，把它们都标记为负值，说明已经搜索过。
如下边中间图像所示，从S点开始形成的路径是STUTSVWVS。最右边图像显示了P点的搜索路径，完成搜索后，轮廓点的周围都被标记为了负值。
在OpenCV中查找轮廓的函数已经存在了，而且可以得到轮廓之间的层次关系。这个函数按上面的算法实现起来并不困难，所以这里就不再实现这个函数，有兴趣的可以看OpenCV的源码（contours.cpp）。
1 void bwLabel(const Mat& imgBw, Mat & imgLabeled) 2 { 3 // 对图像周围扩充一格 4 Mat imgClone = Mat(imgBw.rows + 1, imgBw.cols + 1, imgBw.type(), Scalar(0)); 5 imgBw.copyTo(imgClone(Rect(1, 1, imgBw.cols, imgBw.rows))); 6 7 imgLabeled.create(imgClone.size(), imgClone.type()); 8 imgLabeled.setTo(Scalar::all(0)); 9 10 vector<vector<Point>> contours; 11 vector<Vec4i> hierarchy; 12 findContours(imgClone, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE); 13 14 vector<int> contoursLabel(contours.size(), 0); 15 int numlab = 1; 16 // 标记外围轮廓 17 for (vector<vector<Point>>::size_type i = 0; i < contours.size(); i++) 18 { 19 if (hierarchy[i][3] >= 0) // 有父轮廓 20 { 21 continue; 22 } 23 for (vector<Point>::size_type k = 0; k != contours[i].size(); k++) 24 { 25 imgLabeled.at<uchar>(contours[i][k].y, contours[i][k].x) = numlab; 26 } 27 contoursLabel[i] = numlab++; 28 } 29 // 标记内轮廓 30 for (vector<vector<Point>>::size_type i = 0; i < contours.size(); i++) 31 { 32 if (hierarchy[i][3] < 0) 33 { 34 continue; 35 } 36 for (vector<Point>::size_type k = 0; k != contours[i].size(); k++) 37 { 38 imgLabeled.at<uchar>(contours[i][k].y, contours[i][k].x) = contoursLabel[hierarchy[i][3]]; 39 } 40 } 41 // 非轮廓像素的标记 42 for (int i = 0; i < imgLabeled.rows; i++) 43 { 44 for (int j = 0; j < imgLabeled.cols; j++) 45 { 46 if (imgClone.at<uchar>(i, j) != 0 && imgLabeled.at<uchar>(i,j) == 0) 47 { 48 imgLabeled.at<uchar>(i, j) = imgLabeled.at<uchar>(i, j-1); 49 } 50 } 51 } 52 imgLabeled = imgLabeled(Rect(1, 1, imgBw.cols, imgBw.rows)).clone(); // 将边界裁剪掉1像素 53 }
原文：http://www.cnblogs.com/ronny/p/img_aly_01.html
