二值图像连通域搜索

Answer 1

matlab中连通区域标记函数bwlabel中的算法，一次遍历图像，并记下每一行（或列）中连续的团（run）和标记的等价对，然后通过等价对对原来的图像进行重新标记。

创建RUN（团）结构体，包含（纵坐标、横坐标开始、横坐标结束、标记号） 开始逐行扫描图像，寻找所有的团，将他们放到一个二维数组vector< vector >中，以下为每一行的操作。 当遇到一个255时，创建一个团的对象，标记纵坐标和横坐标的开始。 从开始点向右寻找，直到遇到0或者这行结束，则标记为这个团的横坐标结束。 将该行的RUN push到对应的位置。回到步骤2.1. 对众多的团进行分析，对团进行标记且得到等价对，创建一个vector< pair<int, int> >用于存放所有的等价对。 遍历所有相邻行。 若该行为第一行，则直接进行标记。 对于相邻行，遍历该行的所有RUN，对于每一个RUN，遍历上一行的所有RUN（超出范围即停止循环）。 若上一行中没有与该行RUN邻接，则创建新的标记。 若上一行只有一个与该RUN邻接，则沿用相邻RUN的标记。 若上一行有多个与该RUN邻接，则使用这多个RUN中最小的标记，并创建多个等价对。 消除等价对，可使用并查集，使得所有的团都拥有自己的祖先。 假设标记从0开始，到1000结束。标记对为类似的(0,10).(10,39)。 创建一个prev[1000]数组，初始化值为-1，记录该标记的上一级领导。初始prev[10]=0,prev[39]=10。初始化所有的等价对。 遍历所有的等价对，修改每一级的上一级领导为最上层领导。 修改每个团中的标记为最上层领导的标记。 代码见 github

https://github.com/liqiang311/snippets/blob/master/%E4%BA%8C%E5%80%BC%E5%9B%BE%E5%83%8F%E8%BF%9E%E9%80%9A%E5%9F%9F%E9%97%AE%E9%A2%98.cpp

开源库cvBlob中使用的标记算法，它通过定位连通区域的内外轮廓来标记整个图像，这个算法的核心是轮廓的搜索算法

TODO:轮廓跟踪算法