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:轮廓跟踪算法