⼀、前⾔
⼆值图像，顾名思义就是图像的亮度值只有两个状态：⿊(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个像素）。
eee17三、连通区域的标记
连通区域标记算法有很多种，有的算法可以⼀次遍历图像完成标记，有的则需要2次或更多次遍历图像。这也就造成了不同的算法时间效率的差别，在这⾥我们介绍2种算法。
第⼀种算法是现在matlab中连通区域标记函数bwlabel中使的算法，它⼀次遍历图像，并记下每⼀⾏（或列）中连续的团（run）和标记的等价对，然后通过等价对对原来的图像进⾏重新标记，这个算法是⽬前我尝试的⼏个中效率最⾼的⼀个，但是算法⾥⽤到了稀疏矩阵与Dulmage-Mendelsohn分解算 法⽤来消除等价对，这部分原理⽐较⿇烦，所以本⽂⾥将不介绍这个分解算法，取⽽代这的⽤图的深度优先遍历来替换等价对。
第⼆种算法是现在开源库clob中使⽤的标记算法，它通过定位连通区域的内外轮廓来标记整个图像，这个算法的核⼼是轮廓的搜索算法，这个我们将在⽂章中详细介绍。这个算法相⽐与第⼀种⽅法效率上要低⼀些，但是在连通区域个数在100以内时，两者⼏乎⽆差别，当连通区域个数到了数量级时，上⾯的算法会⽐该算法快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）写⼊等价对。
全部图像遍历结束，我们得到了很多个团的起始坐标，终⽌坐标，它们所在的⾏以及它们的标号。同时我们还得到了⼀个等价对的列表。连通区域
下⾯我们⽤实现上⾯的过程，即步骤2，分两个进⾏：
1）fillRunVectors函数完成所有团的查与记录；
void fillRunVectors(const Mat& bwImage, int& NumberOfRuns, vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun)
{
for (int i = 0; i < ws; i++)
{
const uchar* rowData = bwImage.ptr<uchar>(i);
if (rowData[0] == 255)
{
NumberOfRuns++;
stRun.push_back(0);
rowRun.push_back(i);
}
for (int j = 1; j < ls; j++)
{
if (rowData[j - 1] == 0 && rowData[j] == 255)
{
NumberOfRuns++;
stRun.push_back(j);
rowRun.push_back(i);
}
else if (rowData[j - 1] == 255 && rowData[j] == 0)
{
enRun.push_back(j - 1);
}
冰醋酸溶液
}
if (ls - 1])
{
enRun.push_ls - 1);
}
}
}
//fillRunVectors
2）firstPass函数完成团的标记与等价对列表的⽣成。相⽐之下第⼆个函数要稍微难理解⼀些。
void firstPass(vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun, int NumberOfRuns,
vector<int>& runLabels, vector<pair<int, int>>& equivalences, int offset)
{
runLabels.assign(NumberOfRuns, 0);
int idxLabel = 1;
int curRowIdx = 0;
int firstRunOnCur = 0;
int firstRunOnPre = 0;
int lastRunOnPre = -1;
for (int i = 0; i < NumberOfRuns; i++)
{
if (rowRun[i] != curRowIdx)
{
curRowIdx = rowRun[i];
firstRunOnPre = firstRunOnCur;
lastRunOnPre = i - 1;
firstRunOnCur = i;
}
for (int j = firstRunOnPre; j <= lastRunOnPre; j++)
{
if (stRun[i] <= enRun[j] + offset && enRun[i] >= stRun[j] - offset)
{
if (runLabels[i] == 0) // 没有被标号过
runLabels[i] = runLabels[j];
else if (runLabels[i] != runLabels[j])// 已经被标号
equivalences.push_back(make_pair(runLabels[i], runLabels[j])); // 保存等价对中长波加热器
}
}
if (runLabels[i] == 0) // 没有与前⼀列的任何run重合
{
runLabels[i] = idxLabel++;
}
}
}
//firstPass
接下来是我们的重点，即等价对的处理，我们需要将它转化为若⼲个等价序列。⽐如有如下等价对：
(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-2-5-6-8-10-11-12-13-14-15
3-7-9
4
⼀个思路是将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>>⾥。
void replaceSameLabel(vector<int>& runLabels, vector<pair<int, int>>&
equivalence)
{
int maxLabel = *max_element(runLabels.begin(), d());
vector<vector<bool>> eqTab(maxLabel, vector<bool>(maxLabel, false));
vector<pair<int, int>>::iterator vecPairIt = equivalence.begin();
while (vecPairIt != d())
{
eqTab[vecPairIt->first - 1][vecPairIt->second - 1] = true;
eqTab[vecPairIt->second - 1][vecPairIt->first - 1] = true;
vecPairIt++;
}
vector<int> labelFlag(maxLabel, 0);
vector<vector<int>> equaList;
vector<int> tempList;
cout << maxLabel << endl;
for (int i = 1; i <= maxLabel; i++)
{
if (labelFlag[i - 1])
{
continue;
}
labelFlag[i - 1] = equaList.size() + 1;
tempList.push_back(i);
for (vector<int>::size_type j = 0; j < tempList.size(); j++)
{
for (vector<bool>::size_type k = 0; k != eqTab[tempList [j] - 1].size(); k++)
{
if (eqTab[tempList[j] - 1][k] && !labelFlag[k])
{
tempList.push_back(k + 1);
labelFlag[k] = equaList.size() + 1;
}
}
}
equaList.push_back(tempList);
tempList.clear();
}
cout << equaList.size() << endl;
for (vector<int>::size_type i = 0; i != runLabels.size(); i++)
{
runLabels[i] = labelFlag[runLabels[i]-1];
}
}
//replaceSameLabel
五、基于轮廓的标记
在这⾥我还是先给出算法描述：
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）。
void bwLabel(const Mat& imgBw, Mat & imgLabeled)
{
// 对图像周围扩充⼀格
Mat imgClone = ws + 1, ls + 1, pe(), Scalar(0));
安全带插扣
imgLabeled.setTo(Scalar::all(0));
vector<vector<Point>> contours;
vector<Vec4i> hierarchy;
findContours(imgClone, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE);
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议