图像处理 连通域_python opencv图像处理二值图像连通域颜色标记 - CSDN
精华内容
参与话题
  • 图像连通域分析

    万次阅读 多人点赞 2016-05-03 10:56:33
    在实际应用中,很多图像的分析最终都转换为二值图像的分析,比如:医学图像分析、前景检测、字符识别,形状识别。二值化+数学形态学能解决很多计算机识别工程中目标提取的问题。 二值图像分析最重要的方法就是连通...

    一、前言

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

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

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

    image

    二、连通域

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

    image        image

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

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

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

    下面这符图中,如果考虑4邻接,则有3个连通区域;如果考虑8邻接,则有2个连通区域。(注:图像是被放大的效果,图像正方形实际只有4个像素)。

    image

    三、连通区域分析

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

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


    四、连通区域的标记

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

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

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

    1)基于行程的标记

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

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

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

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

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

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

    6,结束。

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

    image

    第一行,我们得到两个团:[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函数完成所有团的查找与记录;

    void fillRunVectors(const Mat& bwImage, int& NumberOfRuns, vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun)
    {
        for (int i = 0; i < bwImage.rows; 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 < bwImage.cols; 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 (rowData[bwImage.cols - 1])
            {
                enRun.push_back(bwImage.cols - 1);
            }
        }
    }

    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 && rowRun[i] == rowRun[j] + 1)
                {
                    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++;
            }
    
        }
    }

    接下来是我们的重点,即等价对的处理,我们需要将它转化为若干个等价序列。比如有如下等价对:

    (1,2),(1,6),(3,7),(9-3),(8,1),(8,10),(11,5),(11,8),(11,12),(11,13),(11,14),(15,11)

    我们需要得到最终序列是:

    list1:list1:1-2-5-6-8-10-11-12-13-14-15

    list2:list2:3-7-9

    list3:list3: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)。

    image    image    image

    下面是这个过程的C++实现,每个等价表用一个vector<int>来保存,等价对列表保存在map<pair<int,int>>里。

    void replaceSameLabel(vector<int>& runLabels, vector<pair<int, int>>&
        equivalence)
    {
        int maxLabel = *max_element(runLabels.begin(), runLabels.end());
        vector<vector<bool>> eqTab(maxLabel, vector<bool>(maxLabel, false));
        vector<pair<int, int>>::iterator vecPairIt = equivalence.begin();
        while (vecPairIt != equivalence.end())
        {
            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];
        }
    }

    2)基于轮廓的标记

    算法描述:

    1,从上至下,从左至右依次遍历图像。

    2,如下图A所示,A为遇到一个外轮廓点(其实上遍历过程中第一个遇到的白点即为外轮廓点),且没有被标记过,则给A一个新的标记号。我们从A点出发,按照一定的规则(这个规则后面详细介绍)将A所在的外轮廓点全部跟踪到,然后回到A点,并将路径上的点全部标记为A的标号。

    3,如下图B所示,如果遇到已经标记过的外轮廓点AA′,则从AA′向右,将它右边的点都标记为AA′的标号,直到遇到黑色像素为止。

    4,如下图C所示,如果遇到了一个已经被标记的点B,且是内轮廓的点(它的正下方像素为黑色像素且不在外轮廓上),则从B点开始,跟踪内轮廓,路径上的点都设置为B的标号,因为B已经被标记过与A相同,所以内轮廓与外轮廓将标记相同的标号。

    5,如下图D所示,如果遍历到内轮廓上的点,则也是用轮廓的标号去标记它右侧的点,直到遇到黑色像素为止。

    6,结束。

     

    image

    整个算法步骤,我们只扫描了一次图像,同时我们对图像中的像素进行标记,要么赋予一个新的标号,要么用它同行的左边的标号去标记它,下面是算法更细的描述

    对于一个需要标记的图像II,我们定义一个与它对应的标记图像LL,用来保存标记信息,开始我们把L上的所有值设置为0,同时我们有一个标签变量CC,初始化为1。然后我们开始扫描图像I,遇到白色像素时,设这个点为PP点,我们需要按下面不同情况进行不同的处理:

    情况1:如果P(i,j)P(i,j)点是一个白色像素,在LL图像上这个位置没有被标记过,而且PP点的上方为黑色,则P是一个新的外轮廓的点,这时候我们将C的标签值标记给L图像上P点的位置(x,y)(x,y),即L(x,y)=CL(x,y)=C,接着我们沿着P点开始做轮廓跟踪,并把把轮廓上的点对应的L上都标记为C,完成整个轮廓的搜索与标记后,回到了P点。最后不要忘了把C的值加1。这个过程如下面图像S1中所示。

    image

     

    情况2:如果P点的下方的点是unmarked点(什么是unmark点,情况3介绍完就会给出定义),则P点一定是内轮廓上的点,这时候有两种情况,一种是P点在L上已经被标记过了,说明这个点同时也是外轮廓上的点;另一种情况是P点在L上还没有被标记过,那如果是按上面步骤来的,P点左边的点一定被标记了(这一处刚开始理解可能不容易,不妨画一个简单的图,自己试着一个点一个点标记试试,就容易理解了),所以这时候我们采用P点左边点的标记值来标记P,接着从P点开始跟踪内轮廓把内轮廓上的点都标记为P的标号。

    下面图像显示了上面分析的两种P的情况,左图的P点既是外轮廓上的点也是内轮廓上的点。

    image    image

    情况3:如果一个点P,不是上面两种情况之一,那么P点的左边一定被标记过(不理解,就手动去标记上面两幅图像),我们只需要用它左边的标号去标记L上的P点。

    现在我们只剩下一个问题了,就是什么是unmarked点,我们知道内轮廓点开始点P的下方一定是一个黑色像素,是不是黑色像素就是unmarked点呢,显然不是,如下图像的Q点,它的下面也是黑色像素,然而它却不是内轮廓上的点。

    实际上在我们在轮廓跟踪时,我们我轮廓点的周围做了标记,在轮廓点周围被查找过的点(查找方式见下面的轮廓跟踪算法)在L上被标记了一个负值(如下面右图所示),所以Q点的下方被标记为了负值,这样Q的下方就不是一个unmarked点,unmarked点,即在L上的标号没有被修改过,即为0。

    image      image

    显然,这个算法的重点在于轮廓的查找与标记,而对于轮廓的查找,就是确定搜索策略的问题,我们下面给内轮廓与外轮廓定义tracker规则。

    我们对一点像素点周围的8个点分析作一个标号0-7,因为我们在遍历图像中第一个遇到的点肯定是外轮廓点,所以我们先来确定外轮廓的搜索策略,对于外轮廓的点P,有两种情况:

    image

    1)如果P是外轮廓的起点,也就是说我们是从P点开始跟踪的,那么我们从7号(右上角)位置P1P1开始,看7号是不是白色点,如果是,则把这个点加入外轮廓点中,并将它标记与P点相同,如果7号点是黑色点,则按顺时针7-0-1-2-3-4-5-6这个顺序搜索直到遇到白点为止,把那个点确定为P1P1,加入外轮廓,并把这个点的标号设置与P点相同。这里很重要一步就是,假设我们2号点才是白点,那么7,0,1这三个位置我们都搜索过,所以我们要把这些点在L上标记为一个负值。如下图所示,其中右图像标记的结果。

    image    image

    2)那么如果P是不是外轮廓的起点,即P是外轮廓路径上的一个点,那么它肯定是由一个点进入的,我们设置为P1P−1点,P1P−1点的位置为x(0<=x<=7)x(0<=x<=7),那么P点从(x+2)mod8(x+2)mod8这个位置开始寻找下一步的路径,(x+2)mod8(x+2)mod8是加2取模的意思,它反映在图像就是从P-1点按顺时针数2个格子的位置。确定搜索起点后,按照上面一种情况进行下面的步骤。

    外轮廓点的跟踪方式确定了后,内轮廓点的跟踪方式大同小异,只是如果P是内轮廓的第一个点,则它的开始搜索位置不是7号点而是3号点。其他的与外轮廓完全一致。

    如要上面搜索方式,你不是很直观的理解,不妨尝试着去搜索下面这幅图像,你应该有能有明确的了解了。一个路径搜索结束的条件是,回到原始点S,则S周围不存在unmarked点。

    如下边中间图像所示,从S点开始形成的路径是STUTSVWV。

       image 

    在OpenCV中查找轮廓的函数已经存在了,而且可以得到轮廓之间的层次关系。这个函数按上面的算法实现起来并不困难,所以这里就不再实现这个函数,有兴趣的可以看OpenCV的源码(contours.cpp)。

    void bwLabel(const Mat& imgBw, Mat & imgLabeled)
    {
        // 对图像周围扩充一格
        Mat imgClone = Mat(imgBw.rows + 1, imgBw.cols + 1, imgBw.type(), Scalar(0));
        imgBw.copyTo(imgClone(Rect(1, 1, imgBw.cols, imgBw.rows)));
    
        imgLabeled.create(imgClone.size(), imgClone.type());
        imgLabeled.setTo(Scalar::all(0));
    
        vector<vector<Point>> contours;
        vector<Vec4i> hierarchy;
        findContours(imgClone, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE);
    
        vector<int> contoursLabel(contours.size(), 0);
        int numlab = 1;
        // 标记外围轮廓
        for (vector<vector<Point>>::size_type i = 0; i < contours.size(); i++)
        {
            if (hierarchy[i][3] >= 0) // 有父轮廓
            {
                continue;
            }
            for (vector<Point>::size_type k = 0; k != contours[i].size(); k++)
            {
                imgLabeled.at<uchar>(contours[i][k].y, contours[i][k].x) = numlab;
            }
            contoursLabel[i] = numlab++;
        }
        // 标记内轮廓
        for (vector<vector<Point>>::size_type i = 0; i < contours.size(); i++)
        {
            if (hierarchy[i][3] < 0)
            {
                continue;
            }
            for (vector<Point>::size_type k = 0; k != contours[i].size(); k++)
            {
                imgLabeled.at<uchar>(contours[i][k].y, contours[i][k].x) = contoursLabel[hierarchy[i][3]];
            }
        }
        // 非轮廓像素的标记
        for (int i = 0; i < imgLabeled.rows; i++)
        {
            for (int j = 0; j < imgLabeled.cols; j++)
            {
                if (imgClone.at<uchar>(i, j) != 0 && imgLabeled.at<uchar>(i, j) == 0)
                {
                    imgLabeled.at<uchar>(i, j) = imgLabeled.at<uchar>(i, j - 1);
                }
            }
        }
        imgLabeled = imgLabeled(Rect(1, 1, imgBw.cols, imgBw.rows)).clone(); // 将边界裁剪掉1像素
    }

    五 、连通区域分析的算法

    从连通区域的定义可以知道,一个连通区域是由具有相同像素值的相邻像素组成像素集合,因此,我们就可以通过这两个条件在图像中寻找连通区域,对于找到的每个连通区域,我们赋予其一个唯一的标识(Label),以区别其他连通区域。

    连通区域分析有基本的算法,也有其改进算法,本文介绍其中的两种常见算法:

    1)Two-Pass法;2)Seed-Filling种子填充法;

    Note:

    a、这里的扫描指的是按行或按列访问以便图像的所有像素,本文算法采用的是按行扫描方式;

    b、图像记为B,为二值图像:前景像素(pixel value = 1),背景像素(pixel value = 0)

    c、label从2开始计数;

    d、像素相邻关系:4-领域、8-领域,本文算法采用4-邻域;

                                         

    4—领域图例                                                     8—领域图例


    1)Two-Pass(两遍扫描法)

    两遍扫描法,正如其名,指的就是通过扫描两遍图像,就可以将图像中存在的所有连通区域找出并标记。

    思路:

    第一遍扫描时赋予每个像素位置一个label,扫描过程中同一个连通区域内的像素集合中可能会被赋予一个或多个不同label,因此需要将这些属于同一个连通区域但具有不同值的label合并,也就是记录它们之间的相等关系;

    第二遍扫描就是将具有相等关系的equal_labels所标记的像素归为一个连通区域并赋予一个相同的label(通常这个label是equal_labels中的最小值)。


    下面给出Two-Pass算法的简单步骤:

    (1)第一次扫描:

    访问当前像素B(x,y),如果B(x,y) == 1:

    a、如果B(x,y)的领域中像素值都为0,则赋予B(x,y)一个新的label:

    label += 1, B(x,y) = label;

    b、如果B(x,y)的领域中有像素值 > 1的像素Neighbors:

    1)将Neighbors中的最小值赋予给B(x,y):

    B(x,y) = min{Neighbors} 

    2)记录Neighbors中各个值(label)之间的相等关系,即这些值(label)同属同一个连通区域;

     labelSet[i] = { label_m, .., label_n },labelSet[i]中的所有label都属于同一个连通区域(注:这里可以有多种实现方式,只要能够记录这些具有相等关系的label之间的关系即可)

    (2)第二次扫描:

    访问当前像素B(x,y),如果B(x,y) > 1:

    a、找到与label = B(x,y)同属相等关系的一个最小label值,赋予给B(x,y);

    完成扫描后,图像中具有相同label值的像素就组成了同一个连通区域。

    下面这张图动态地演示了Two-pass算法:


    2)Seed Filling(种子填充法)

    种子填充方法来源于计算机图形学,常用于对某个图形进行填充。思路:选取一个前景像素点作为种子,然后根据连通区域的两个基本条件(像素值相同、位置相邻)将与种子相邻的前景像素合并到同一个像素集合中,最后得到的该像素集合则为一个连通区域。


    下面给出基于种子填充法的连通区域分析方法:

    (1)扫描图像,直到当前像素点B(x,y) == 1:

    a、将B(x,y)作为种子(像素位置),并赋予其一个label,然后将该种子相邻的所有前景像素都压入栈中;

    b、弹出栈顶像素,赋予其相同的label,然后再将与该栈顶像素相邻的所有前景像素都压入栈中;

    c、重复b步骤,直到栈为空;

    此时,便找到了图像B中的一个连通区域,该区域内的像素值被标记为label;

    (2)重复第(1)步,直到扫描结束;

    扫描结束后,就可以得到图像B中所有的连通区域;

    下面这张图动态地演示了Seed-Filling算法:


    在Two-pass连通域标记中,第一次标记(first pass)时从左向右,从上向下扫描,会将各个有效像素置一个label值,判断规则如下(以4邻域为例):

    1)         当该像素的左邻像素和上邻像素为无效值时,给该像素置一个新的label值,label ++;

    2)         当该像素的左邻像素或者上邻像素有一个为有效值时,将有效值像素的label赋给该像素的label值;

    3)         当该像素的左邻像素和上邻像素都为有效值时,选取其中较小的label值赋给该像素的label值。

    此时,还需维护一个关系表,记录哪些label值属于同一个连通域。这个关系表通常用union-find数据结构来实现。

    在union-find结构中,属于同一个连通域的label值被存储到同一个树形结构中,如图1所示,{1,2,3,4,8}属于同一个连通域,{5,6,7}属于同一个连通域。同时,树形结构的数据存储到一个vector或array中,vector的下标为label值,vector的存储值为该label的父节点label值,当vector的存储值为0时,说明该label是根节点。这样,对于任意一个label,我们都可以寻找其根节点,作为所在连通域的label值,即某一连通域所有像素都被置为同一个label值,即根节点label值。对给定的任意一个label,我们可以通过find算法寻找其根节点,如图2所示。

     

    如果知道两个label同属于一个连通域,要如何在vector中实现其存储关系呢?首先,各自寻找两个label的根节点,如果二者的根节点相同,则二者已经属于同一个连通域;如果二者的根节点不同,那么把其中一个根节点作为另一个的父节点即可,即将两个label划入同一个连通域,或者叫做连通域合并,算法如图3所示。

    那么这个存储label值的vector要如何初始化呢?将vector初始化为0即可,即各个label值都是根节点,大家互不相连。同时注意,vector[0]不使用。

    实现代码如下:

    [cpp] view plain copy
    1. const int max_size = 100;  
    2. int parent[100] = {0};  
    3.   
    4. // 找到label x的根节点  
    5. int find(int x, int parent[]){  
    6.     int i = x;  
    7.     while(0 != parent[i])  
    8.         i = parent[i];  
    9.     return i;  
    10. }  
    11.   
    12. // 将label x 和 label y合并到同一个连通域  
    13. void union_label(int x, int y, int parent[]){  
    14.     int i = x;  
    15.     int j = y;  
    16.     while(0 != parent[i])  
    17.         i = parent[i];  
    18.     while(0 != parent[j])  
    19.         j = parent[j];  
    20.     if(i != j)  
    21.         parent[i] = j;  
    22. }  
    参考:http://blog.csdn.net/lichengyu/article/details/13986521

    六、实验演示


    1)前景二值图像


    2)连通区域分析方法标记后得到的label图像


    Two-pass算法:



    Seed-filling算法:


    注:为了显示方便,将像素值乘以了一个整数进行放大。


    3)color后的label图像

    Two-pass算法:


    Seed-filling算法:



    注:颜色是随机生成的。


    七、代码


    1)Two-pass算法的一种实现

    说明:基于OpenCV和C++实现,领域:4-领域。实现与算法描述稍有差别(具体为记录具有相等关系的label方法实现上)。

    copy

    1. <span style="font-size:12px">//  Connected Component Analysis/Labeling By Two-Pass Algorithm   
    2. //  Author:  www.icvpr.com    
    3. //  Blog  :  http://blog.csdn.net/icvpr   
    4. #include <iostream>  
    5. #include <string>  
    6. #include <list>  
    7. #include <vector>  
    8. #include <map>  
    9.   
    10. #include <opencv2/imgproc/imgproc.hpp>  
    11. #include <opencv2/highgui/highgui.hpp>  
    12.   
    13.   
    14. void icvprCcaByTwoPass(const cv::Mat& _binImg, cv::Mat& _lableImg)  
    15. {  
    16.     // connected component analysis (4-component)  
    17.     // use two-pass algorithm  
    18.     // 1. first pass: label each foreground pixel with a label  
    19.     // 2. second pass: visit each labeled pixel and merge neighbor labels  
    20.     //   
    21.     // foreground pixel: _binImg(x,y) = 1  
    22.     // background pixel: _binImg(x,y) = 0  
    23.   
    24.   
    25.     if (_binImg.empty() ||  
    26.         _binImg.type() != CV_8UC1)  
    27.     {  
    28.         return ;  
    29.     }  
    30.   
    31.     // 1. first pass  
    32.   
    33.     _lableImg.release() ;  
    34.     _binImg.convertTo(_lableImg, CV_32SC1) ;  
    35.   
    36.     int label = 1 ;  // start by 2  
    37.     std::vector<int> labelSet ;  
    38.     labelSet.push_back(0) ;   // background: 0  
    39.     labelSet.push_back(1) ;   // foreground: 1  
    40.   
    41.     int rows = _binImg.rows - 1 ;  
    42.     int cols = _binImg.cols - 1 ;  
    43.     for (int i = 1; i < rows; i++)  
    44.     {  
    45.         int* data_preRow = _lableImg.ptr<int>(i-1) ;  
    46.         int* data_curRow = _lableImg.ptr<int>(i) ;  
    47.         for (int j = 1; j < cols; j++)  
    48.         {  
    49.             if (data_curRow[j] == 1)  
    50.             {  
    51.                 std::vector<int> neighborLabels ;  
    52.                 neighborLabels.reserve(2) ;  
    53.                 int leftPixel = data_curRow[j-1] ;  
    54.                 int upPixel = data_preRow[j] ;  
    55.                 if ( leftPixel > 1)  
    56.                 {  
    57.                     neighborLabels.push_back(leftPixel) ;  
    58.                 }  
    59.                 if (upPixel > 1)  
    60.                 {  
    61.                     neighborLabels.push_back(upPixel) ;  
    62.                 }  
    63.   
    64.                 if (neighborLabels.empty())  
    65.                 {  
    66.                     labelSet.push_back(++label) ;  // assign to a new label  
    67.                     data_curRow[j] = label ;  
    68.                     labelSet[label] = label ;  
    69.                 }  
    70.                 else  
    71.                 {  
    72.                     std::sort(neighborLabels.begin(), neighborLabels.end()) ;  
    73.                     int smallestLabel = neighborLabels[0] ;    
    74.                     data_curRow[j] = smallestLabel ;  
    75.   
    76.                     // save equivalence  
    77.                     for (size_t k = 1; k < neighborLabels.size(); k++)  
    78.                     {  
    79.                         int tempLabel = neighborLabels[k] ;  
    80.                         int& oldSmallestLabel = labelSet[tempLabel] ;  
    81.                         if (oldSmallestLabel > smallestLabel)  
    82.                         {                             
    83.                             labelSet[oldSmallestLabel] = smallestLabel ;  
    84.                             oldSmallestLabel = smallestLabel ;  
    85.                         }                         
    86.                         else if (oldSmallestLabel < smallestLabel)  
    87.                         {  
    88.                             labelSet[smallestLabel] = oldSmallestLabel ;  
    89.                         }  
    90.                     }  
    91.                 }                 
    92.             }  
    93.         }  
    94.     }  
    95.   
    96.     // update equivalent labels  
    97.     // assigned with the smallest label in each equivalent label set  
    98.     for (size_t i = 2; i < labelSet.size(); i++)  
    99.     {  
    100.         int curLabel = labelSet[i] ;  
    101.         int preLabel = labelSet[curLabel] ;  
    102.         while (preLabel != curLabel)  
    103.         {  
    104.             curLabel = preLabel ;  
    105.             preLabel = labelSet[preLabel] ;  
    106.         }  
    107.         labelSet[i] = curLabel ;  
    108.     }  
    109.   
    110.   
    111.     // 2. second pass  
    112.     for (int i = 0; i < rows; i++)  
    113.     {  
    114.         int* data = _lableImg.ptr<int>(i) ;  
    115.         for (int j = 0; j < cols; j++)  
    116.         {  
    117.             int& pixelLabel = data[j] ;  
    118.             pixelLabel = labelSet[pixelLabel] ;   
    119.         }  
    120.     }  
    121. }</span>  

    2)Seed-Filling种子填充方法

    说明:基于OpenCV和C++实现;领域:4-领域。

    1. <span style="font-size:12px">//  Connected Component Analysis/Labeling By Seed-Filling Algorithm   
    2. //  Author:  www.icvpr.com    
    3. //  Blog  :  http://blog.csdn.net/icvpr   
    4. #include <iostream>  
    5. #include <string>  
    6. #include <list>  
    7. #include <vector>  
    8. #include <map>  
    9. #include <stack>  
    10.   
    11. #include <opencv2/imgproc/imgproc.hpp>  
    12. #include <opencv2/highgui/highgui.hpp>  
    13.   
    14.   
    15. void icvprCcaBySeedFill(const cv::Mat& _binImg, cv::Mat& _lableImg)  
    16. {  
    17.     // connected component analysis (4-component)  
    18.     // use seed filling algorithm  
    19.     // 1. begin with a foreground pixel and push its foreground neighbors into a stack;  
    20.     // 2. pop the top pixel on the stack and label it with the same label until the stack is empty  
    21.     //   
    22.     // foreground pixel: _binImg(x,y) = 1  
    23.     // background pixel: _binImg(x,y) = 0  
    24.   
    25.   
    26.     if (_binImg.empty() ||  
    27.         _binImg.type() != CV_8UC1)  
    28.     {  
    29.         return ;  
    30.     }  
    31.   
    32.     _lableImg.release() ;  
    33.     _binImg.convertTo(_lableImg, CV_32SC1) ;  
    34.   
    35.     int label = 1 ;  // start by 2  
    36.   
    37.     int rows = _binImg.rows - 1 ;  
    38.     int cols = _binImg.cols - 1 ;  
    39.     for (int i = 1; i < rows-1; i++)  
    40.     {  
    41.         int* data= _lableImg.ptr<int>(i) ;  
    42.         for (int j = 1; j < cols-1; j++)  
    43.         {  
    44.             if (data[j] == 1)  
    45.             {  
    46.                 std::stack<std::pair<int,int>> neighborPixels ;     
    47.                 neighborPixels.push(std::pair<int,int>(i,j)) ;     // pixel position: <i,j>  
    48.                 ++label ;  // begin with a new label  
    49.                 while (!neighborPixels.empty())  
    50.                 {  
    51.                     // get the top pixel on the stack and label it with the same label  
    52.                     std::pair<int,int> curPixel = neighborPixels.top() ;  
    53.                     int curX = curPixel.first ;  
    54.                     int curY = curPixel.second ;  
    55.                     _lableImg.at<int>(curX, curY) = label ;  
    56.   
    57.                     // pop the top pixel  
    58.                     neighborPixels.pop() ;  
    59.   
    60.                     // push the 4-neighbors (foreground pixels)  
    61.                     if (_lableImg.at<int>(curX, curY-1) == 1)  
    62.                     {// left pixel  
    63.                         neighborPixels.push(std::pair<int,int>(curX, curY-1)) ;  
    64.                     }  
    65.                     if (_lableImg.at<int>(curX, curY+1) == 1)  
    66.                     {// right pixel  
    67.                         neighborPixels.push(std::pair<int,int>(curX, curY+1)) ;  
    68.                     }  
    69.                     if (_lableImg.at<int>(curX-1, curY) == 1)  
    70.                     {// up pixel  
    71.                         neighborPixels.push(std::pair<int,int>(curX-1, curY)) ;  
    72.                     }  
    73.                     if (_lableImg.at<int>(curX+1, curY) == 1)  
    74.                     {// down pixel  
    75.                         neighborPixels.push(std::pair<int,int>(curX+1, curY)) ;  
    76.                     }  
    77.                 }         
    78.             }  
    79.         }  
    80.     }  
    81. }</span>  

    3)颜色标记(用于显示)

    1. <span style="font-size:12px">//  Connected Component Analysis/Labeling -- Color Labeling   
    2. //  Author:  www.icvpr.com    
    3. //  Blog  :  http://blog.csdn.net/icvpr   
    4. #include <iostream>  
    5. #include <string>  
    6. #include <list>  
    7. #include <vector>  
    8. #include <map>  
    9. #include <stack>  
    10.   
    11. #include <opencv2/imgproc/imgproc.hpp>  
    12. #include <opencv2/highgui/highgui.hpp>  
    13.   
    14. cv::Scalar icvprGetRandomColor()  
    15. {  
    16.     uchar r = 255 * (rand()/(1.0 + RAND_MAX));  
    17.     uchar g = 255 * (rand()/(1.0 + RAND_MAX));  
    18.     uchar b = 255 * (rand()/(1.0 + RAND_MAX));  
    19.     return cv::Scalar(b,g,r) ;  
    20. }  
    21.   
    22.   
    23. void icvprLabelColor(const cv::Mat& _labelImg, cv::Mat& _colorLabelImg)   
    24. {  
    25.     if (_labelImg.empty() ||  
    26.         _labelImg.type() != CV_32SC1)  
    27.     {  
    28.         return ;  
    29.     }  
    30.   
    31.     std::map<int, cv::Scalar> colors ;  
    32.   
    33.     int rows = _labelImg.rows ;  
    34.     int cols = _labelImg.cols ;  
    35.   
    36.     _colorLabelImg.release() ;  
    37.     _colorLabelImg.create(rows, cols, CV_8UC3) ;  
    38.     _colorLabelImg = cv::Scalar::all(0) ;  
    39.   
    40.     for (int i = 0; i < rows; i++)  
    41.     {  
    42.         const int* data_src = (int*)_labelImg.ptr<int>(i) ;  
    43.         uchar* data_dst = _colorLabelImg.ptr<uchar>(i) ;  
    44.         for (int j = 0; j < cols; j++)  
    45.         {  
    46.             int pixelValue = data_src[j] ;  
    47.             if (pixelValue > 1)  
    48.             {  
    49.                 if (colors.count(pixelValue) <= 0)  
    50.                 {  
    51.                     colors[pixelValue] = icvprGetRandomColor() ;  
    52.                 }  
    53.                 cv::Scalar color = colors[pixelValue] ;  
    54.                 *data_dst++   = color[0] ;  
    55.                 *data_dst++ = color[1] ;  
    56.                 *data_dst++ = color[2] ;  
    57.             }  
    58.             else  
    59.             {  
    60.                 data_dst++ ;  
    61.                 data_dst++ ;  
    62.                 data_dst++ ;  
    63.             }  
    64.         }  
    65.     }  
    66. }  
    67. </span>  

    4)测试程序

    1. <span style="font-size:12px">//  Connected Component Analysis/Labeling -- Test code  
    2. //  Author:  www.icvpr.com    
    3. //  Blog  :  http://blog.csdn.net/icvpr   
    4. #include <iostream>  
    5. #include <string>  
    6. #include <list>  
    7. #include <vector>  
    8. #include <map>  
    9. #include <stack>  
    10.   
    11. #include <opencv2/imgproc/imgproc.hpp>  
    12. #include <opencv2/highgui/highgui.hpp>  
    13.   
    14. int main(int argc, char** argv)  
    15. {  
    16.     cv::Mat binImage = cv::imread("../icvpr.com.jpg", 0) ;  
    17.     cv::threshold(binImage, binImage, 50, 1, CV_THRESH_BINARY_INV) ;  
    18.   
    19.     // connected component labeling  
    20.     cv::Mat labelImg ;  
    21.     icvprCcaByTwoPass(binImage, labelImg) ;  
    22.     //icvprCcaBySeedFill(binImage, labelImg) ;  
    23.   
    24.     // show result  
    25.     cv::Mat grayImg ;  
    26.     labelImg *= 10 ;  
    27.     labelImg.convertTo(grayImg, CV_8UC1) ;  
    28.     cv::imshow("labelImg", grayImg) ;  
    29.   
    30.     cv::Mat colorLabelImg ;  
    31.     icvprLabelColor(labelImg, colorLabelImg) ;  
    32.     cv::imshow("colorImg", colorLabelImg) ;  
    33.     cv::waitKey(0) ;  
    34.   
    35.     return 0 ;  
    36. }</span>  


    参考:http://www.cnblogs.com/ronny/p/img_aly_01.html

             http://blog.csdn.net/sanwandoujiang/article/details/25734175

               http://blog.csdn.net/cooelf/article/details/26581539?utm_source=tuicool&utm_medium=referral

                二值图像连通域标记算法与代码


    展开全文
  • 图像处理 连通域标记

    千次阅读 2017-05-12 13:34:22
    连通域标记是二值图像分析中非常重要的一种方法,也是其他二值图像处理的基础与前提。   所谓连通域标记,就是将一副二值图像中的每个白色像素进行标记,属于同一个连通域的白色像素标记相同,不同连通域的白色...

    前言

       连通域标记是二值图像分析中非常重要的一种方法,也是其他二值图像处理的基础与前提。
       所谓连通域标记,就是将一副二值图像中的每个白色像素进行标记,属于同一个连通域的白色像素标记相同,不同连通域的白色像素有不同的标记,从而能将图像中每个连通域提取出来。
       连通域标记的算法有很多种,这里介绍其中一种基于一次遍历图像,记录等价对的标记方法,这种方法效率很高。

    算法原理

    4 邻接与 8 邻接

      在介绍算法前,我们先了解一下什么算是连通。如果两个白色像素邻接,则我们认为这两个像素是连通的;同时,若像素 A 与像素 B 连通,像素 B 与像素 C 连通,则像素 A 与 C 也是连通的。
      因此,我们需要定义什么样的两个像素点算是邻接的。常见的邻接关系有两种:4 邻接与 8 邻接。如下图所示:
    这里写图片描述
    如果另一个像素点在上图中黑点的位置,则表示这个像素点与 X 点邻接。

    遍历图像

    算法描述:

    for 二值图像中的每一行: //列也可以
       1. 记录此行白色像素的每一个序列的的起始位置,终止位置;
       2. 除第一行以外(第一行直接标记),判断是否与上一行序列有重叠:
            如果没有重叠,则分配一个新的标记;
            如果有一个重叠,则用上一行序列的标记进行标记;
            如果有一个以上的重叠,则用上一行重叠序列中最小的进行标记,同时将后面几个标记与此标记记为等价对;
    end

    这里写图片描述

    如上图所示,我们采用 4 邻接,行遍历来说明一下上面的操作
    第一行: 我们记录一个序列:(1,4)标记为 1;
    第二行:我们记录两个序列:(0,3),与上一行的序列重叠,因此标记为 1,(6,8),与上一行没有重叠,标记为 2;
    第三行:一个序列:(2,6),与上一行两个序列重叠,标记为上一行较小的标记,即 1,同时记录等价对 <1,2>;
    第四行:两个序列:(1,2),标记为 1,(6,8)标记为 1。

    消除等价对

      在上一步中,我们得到了若干个等价对,每一个等价对 <a,b> 表示被标记 a 区域与被标记 b 的区域是连通的,因此,我们希望将每个等价对中的标记更新为同一个标记。用图的遍历即可做到这一点。
       我们将每一个标记看作一个图的结点,每一个等价对看作是图的边,我们要做的就是通过图的遍历来寻找属于同一个最大连通子图的结点。这些结点锁表示的标记是等价的。

    这里写图片描述

    最后,我们将之前的标记更新为新的标记,如上图所示,之前标记为 1,2,5 的像素标记为 1;标记为 6 3 7 9 8 的像素重新标记为 2;标记为 4 的像素重新标记为 3。至此,拥有相同标记的像素点就构成了一个连通域,而标记的最大值就是连通域的个数。

    代码

    #include <opencv2\opencv.hpp>
    #include <iostream>
    #include <utility>
    #include <vector>
    #include <algorithm>
    #include <ctime>
    #include <list>
    #include <queue>
    #define HEIGHBOR_4 4
    #define HEIGHBOR_8 8
    #define UPWARDFIND 1
    #define DOWNWARDFIND 2
    using namespace std;
    using namespace cv;
    
    struct Group {
        int start;
        int end;
        int tag;
    };
    //寻找一个group与上一行的group是否有重叠,返回值若为-1,则表示没有重叠,若为其他值,则返回值是这个group的标记,同时记录等价对
    int findEqualPair(vector<pair<int,int>> &_equal_pairs, Group _group,const vector<Group> &_pre_groups,int _mode)
    {
        vector<int> tags;
        if (_mode == HEIGHBOR_4)
        {
            for (auto i : _pre_groups)
            {
                if (!(i.start > _group.end || _group.start > i.end))
                    tags.push_back(i.tag);
            }
        }
        if (_mode == HEIGHBOR_8)
        {
            for (auto i : _pre_groups)
            {
                if (!(i.start+1 > _group.end && _group.start+1 > i.end))
                    tags.push_back(i.tag);
            }
        }
        if (tags.size() == 0)
        {
            return -1;
        }
        sort(tags.begin(), tags.end());
        tags.erase(unique(tags.begin(), tags.end()), tags.end());
        int min_tag = tags[0];
        for (int i =1;i<tags.size();i++)
        {
            _equal_pairs.push_back(pair<int, int>(min_tag, tags[i]));
        }
        return min_tag;
    
    }
    //连通域标记
    int tagDomain(Mat &_image,Mat &_result,int _mode)
    {
        int width = _image.cols;
        int height = _image.rows;
        _result = Mat(_image.size(),CV_16UC1, Scalar::all(0));
        vector<vector<Group>> groups;//用于存团
        vector<pair<int, int>> equal_pairs;//存储等价对
        int tag_count = 0;
        //第一次遍历
        clock_t time1, time2;
        for (int i = 0; i < height; i++)
        {
            vector<Group> tmp_groups;
            uchar* row = _image.ptr<uchar>(i);
            int j = 0;
            time1 = clock();
            while (j < width)
            {
                if (row[j] == 255)
                {
                    Group group;
                    group.start = j;
                    j++;
                    while (row[j] == 255 && j < width)
                    {
                        j++;
                        continue;
                    }
                    group.end = j - 1;
                    if (i != 0)
                    {
                        int tmp_tag = findEqualPair(equal_pairs, group, groups[i - 1], _mode);
                        if (tmp_tag != -1)
                            group.tag = tmp_tag;
                        else
                            group.tag = ++tag_count;
                    }
                    else
                    {
                        group.tag = ++tag_count;
                    }
                    tmp_groups.push_back(group);
                    //cout << "(" << group.first << "," << group.end << "):" << group.tag << endl;
                }
                else 
                {
                    j++;
                }
            }
            time2 = clock();
            groups.push_back(tmp_groups);
        }
        //消除等价对(图的遍历)
        //消除重复的等价对
        sort(equal_pairs.begin(), equal_pairs.end());
        equal_pairs.erase(unique(equal_pairs.begin(), equal_pairs.end()), equal_pairs.end());
        //构建图
        int size = tag_count+1;
        vector<list<int>> graph(size);
        vector<int> updata_tag(size,0);
        for (auto equal_pair : equal_pairs)
        {
            graph[equal_pair.first].push_front(equal_pair.second);
            graph[equal_pair.second].push_front(equal_pair.first);
        }
        //遍历
        tag_count = 1;
        int first_node;
        bool finished = false;
        while (true)
        {
            finished = true;
            for (int i = 1; i < size; i++)
            {
                if (updata_tag[i] == 0)
                {
                    finished = false;
                    first_node = i;
                    break;
                }
            }
            if (finished)
                break;
            //图的广度优先遍历
            queue<int> q;
            updata_tag[first_node] = tag_count;
            q.push(first_node);
            while (!q.empty())
            {
                int tmp_node = q.front();
                q.pop();
                for (auto i : graph[tmp_node])
                {
                    if (updata_tag[i] == 0)
                    {
                        updata_tag[i] = tag_count;
                        q.push(i);
                    }
                }
            }
            tag_count++;
        }
        //
        for (int i = 0; i < height; i++)
        {
            ushort* data = _result.ptr<ushort>(i);
            for (auto j : groups[i])
            {
                int tmp_tag = updata_tag[j.tag];
                for (int n = j.start; n <= j.end; n++)
                {
                    data[n] = tmp_tag;
                }
            }
        }
        return tag_count-1;
    }
    //随机取色 
    Scalar random_color(RNG &_rng)
    {
        int icolor = (unsigned)_rng;
        return Scalar(icolor & 0xFF, (icolor >> 8) & 0xFF, (icolor >> 16) & 0xFF);
    }
    //给连通域涂上不同的颜色
    Mat drawDomain(Mat &_domain_tag, int _num, RNG &_rng)
    {
        Mat result(_domain_tag.size(), CV_8UC3, Scalar::all(0));
        vector<Scalar> colors;
        for (int i = 0; i < _num; i++)
        {
            colors.push_back(random_color(_rng));
        }
        int height = result.rows;
        int width = result.cols;
        for (int i = 0; i < height; i++)
        {
            Vec3b* data = result.ptr<Vec3b>(i);
            ushort* tag_data = _domain_tag.ptr<ushort>(i);
            for (int j = 0; j < width; j++)
            {
                Scalar color = colors[tag_data[j]-1];
                data[j][0] = color[0];
                data[j][1] = color[1];
                data[j][2] = color[2];
            }
        }
        return result;
    }
    
    int main()
    {
        Mat image = imread("images\\3.bmp");
        Mat binary;
        cvtColor(image, binary, CV_BGR2GRAY);//图像本身是二值图,转下灰度就可以了
        clock_t time1, time2;
        time1 = clock();
        Mat result;
        int num = tagDomain(binary, result, HEIGHBOR_4);
        Point seed1, seed2;
        seed1 = Point(2000, 2150);
        seed2 = Point(2000, 350);
        Point seam_point_down = findSeam(binary, seed1, DOWNWARDFIND);
        Point seam_point_up = findSeam(binary, seed2, UPWARDFIND);
        cout << num << endl;
        Mat draw_result = drawDomain(result, num, RNG(123));
        imwrite("images\\draw_result.bmp", draw_result);
        imshow("draw_result", draw_result);
        waitKey(0);
        return 0;
    }

    结果

    这里写图片描述

    这里写图片描述

    展开全文
  • 图像处理(五)——连通域

    万次阅读 2019-11-22 08:51:18
    连通区域(Connected Component)一般是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域(Region,Blob)。...连通区域分析是一种在CVPR和图像分析处理的众多应用领域中较为常用和基本的方法。例如:...

    连通区域(Connected Component)一般是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域(Region,Blob)。连通区域分析(Connected Component Analysis,Connected Component Labeling)是指将图像中的各个连通区域找出并标记。
    连通区域分析是一种在CVPR和图像分析处理的众多应用领域中较为常用和基本的方法。例如:OCR识别中字符分割提取(车牌识别、文本识别、字幕识别等)、视觉跟踪中的运动前景目标分割与提取(行人入侵检测、遗留物体检测、基于视觉的车辆检测与跟踪等)、医学图像处理(感兴趣目标区域提取)、等等。也就是说,在需要将前景目标提取出来以便后续进行处理的应用场景中都能够用到连通区域分析方法,通常连通区域分析处理的对象是一张二值化后的图像。

    而这次我要做的是实现图像的快速连通域算法,可以提取出图像中的连通域,并将不同连通域用不同颜色表示。

    寻找图像中的连通域的算法有两个,一个是Two-Pass方法

    Two-Pass算法的简单步骤:

    (1)第一次扫描:
    访问当前像素B(x,y),如果B(x,y) == 1:

    a、如果B(x,y)的领域中像素值都为0,则赋予B(x,y)一个新的label:
    label += 1, B(x,y) = label;

    b、如果B(x,y)的领域中有像素值 > 1的像素Neighbors:
    1)将Neighbors中的最小值赋予给B(x,y):
    B(x,y) = min{Neighbors}

    2)记录Neighbors中各个值(label)之间的相等关系,即这些值(label)同属同一个连通区域;

    labelSet[i] = { label_m, …, label_n },labelSet[i]中的所有label都属于同一个连通区域

    图示为:
    在这里插入图片描述

    // 1. 第一次遍历
    
    	_lableImg.release();
    	_binImg.convertTo(_lableImg, CV_32SC1);
    
    	int label = 1;  // start by 2
    	std::vector<int> labelSet;
    	labelSet.push_back(0);   // background: 0
    	labelSet.push_back(1);   // foreground: 1
    
    	int rows = _binImg.rows - 1;
    	int cols = _binImg.cols - 1;
    	for (int i = 1; i < rows; i++)
    	{
    		int* data_preRow = _lableImg.ptr<int>(i - 1);
    		int* data_curRow = _lableImg.ptr<int>(i);
    		for (int j = 1; j < cols; j++)
    		{
    			if (data_curRow[j] == 1)
    			{
    				std::vector<int> neighborLabels;
    				neighborLabels.reserve(2);
    				int leftPixel = data_curRow[j - 1];
    				int upPixel = data_preRow[j];
    				if (leftPixel > 1)
    				{
    					neighborLabels.push_back(leftPixel);
    				}
    				if (upPixel > 1)
    				{
    					neighborLabels.push_back(upPixel);
    				}
    
    				if (neighborLabels.empty())
    				{
    					labelSet.push_back(++label);  // assign to a new label
    					data_curRow[j] = label;
    					labelSet[label] = label;
    				}
    				else
    				{
    					std::sort(neighborLabels.begin(), neighborLabels.end());
    					int smallestLabel = neighborLabels[0];
    					data_curRow[j] = smallestLabel;
    
    					// save equivalence
    					for (size_t k = 1; k < neighborLabels.size(); k++)
    					{
    						int tempLabel = neighborLabels[k];
    						int& oldSmallestLabel = labelSet[tempLabel];
    						if (oldSmallestLabel > smallestLabel)
    						{
    							labelSet[oldSmallestLabel] = smallestLabel;
    							oldSmallestLabel = smallestLabel;
    						}
    						else if (oldSmallestLabel < smallestLabel)
    						{
    							labelSet[smallestLabel] = oldSmallestLabel;
    						}
    					}
    				}
    			}
    		}
    	}
    

    (2)第二次扫描:
    访问当前像素B(x,y),如果B(x,y) > 1:

    a、找到与label = B(x,y)同属相等关系的一个最小label值,赋予给B(x,y);
    完成扫描后,图像中具有相同label值的像素就组成了同一个连通区域。

    图示为:
    在这里插入图片描述

    // 2. 第二遍扫描
    	for (int i = 0; i < rows; i++)
    	{
    		int* data = _lableImg.ptr<int>(i);
    		for (int j = 0; j < cols; j++)
    		{
    			int& pixelLabel = data[j];
    			pixelLabel = labelSet[pixelLabel];
    		}
    	}
    }
    

    另一个方法就是Seed-Filling方法

    种子填充法的连通区域分析方法:

    (1)扫描图像,直到当前像素点B(x,y) == 1:

    a、将B(x,y)作为种子(像素位置),并赋予其一个label,然后将该种子相邻的所有前景像素都压入栈中;
    在这里插入图片描述
    b、弹出栈顶像素,赋予其相同的label,然后再将与该栈顶像素相邻的所有前景像素都压入栈中;
    在这里插入图片描述

    // 推及到四个邻居
    					if (_lableImg.at<int>(curX, curY - 1) == 1)
    					{// 左边的像素
    						neighborPixels.push(std::pair<int, int>(curX, curY - 1));
    					}
    					if (_lableImg.at<int>(curX, curY + 1) == 1)
    					{// 右边的像素
    						neighborPixels.push(std::pair<int, int>(curX, curY + 1));
    					}
    					if (_lableImg.at<int>(curX - 1, curY) == 1)
    					{// 上面的像素
    						neighborPixels.push(std::pair<int, int>(curX - 1, curY));
    					}
    					if (_lableImg.at<int>(curX + 1, curY) == 1)
    					{// 下面的像素
    						neighborPixels.push(std::pair<int, int>(curX + 1, curY));
    					}
    

    c、重复b步骤,直到栈为空;
    此时,便找到了图像B中的一个连通区域,该区域内的像素值被标记为label;
    在这里插入图片描述
    (2)重复第(1)步,直到扫描结束;
    在这里插入图片描述
    扫描结束后,就可以得到图像B中所有的连通区域;

    而我选择的是种子填充方法。
    对下面这张图片做处理在这里插入图片描述
    得到结果为:
    在这里插入图片描述

    改变连通域颜色:

    我用的方法是在刚开始的时候就随机设置三个RGB 值,然后为填充不同连通域(每个连通域的像素的RGB值都是随机的)。

    cv::Scalar icvprGetRandomColor()
    {
    	uchar r = 255 * (rand() / (1.0 + RAND_MAX));
    	uchar g = 255 * (rand() / (1.0 + RAND_MAX));
    	uchar b = 255 * (rand() / (1.0 + RAND_MAX));
    	return cv::Scalar(b, g, r);
    }
    

    同时也欢迎各位关注我的微信公众号 南木的下午茶

    在这里插入图片描述


    代码自取

    // CVE6.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <map>
    #include <stack>
    #include <opencv2/imgproc/imgproc.hpp>
    #include <opencv2/highgui/highgui.hpp>
    #include <stdio.h>
    using namespace cv;
    //Two Pass方法
    void icvprCcaByTwoPass(const cv::Mat& _binImg, cv::Mat& _lableImg)
    {
    	/*
    	 Two-Pass算法的简单步骤:
         (1)第一次扫描:
         访问当前像素B(x,y),如果B(x,y) == 1:
         a、如果B(x,y)的领域中像素值都为0,则赋予B(x,y)一个新的label:
         label += 1, B(x,y) = label;
         b、如果B(x,y)的领域中有像素值 > 1的像素Neighbors:
         1)将Neighbors中的最小值赋予给B(x,y):
         B(x,y) = min{Neighbors} 
         2)记录Neighbors中各个值(label)之间的相等关系,即这些值(label)同属同一个连通区域;
         labelSet[i] = { label_m, .., label_n },labelSet[i]中的所有label都属于同一个连通区域
    	 (2)第二次扫描:
    	 访问当前像素B(x,y),如果B(x,y) > 1:
    	 a、找到与label = B(x,y)同属相等关系的一个最小label值,赋予给B(x,y);
    	 完成扫描后,图像中具有相同label值的像素就组成了同一个连通区域。
    	*/
    
    	if (_binImg.empty() ||
    		_binImg.type() != CV_8UC1)
    	{
    		return;
    	}
    
    	// 1. 第一次遍历
    
    	_lableImg.release();
    	_binImg.convertTo(_lableImg, CV_32SC1);
    
    	int label = 1;  // start by 2
    	std::vector<int> labelSet;
    	labelSet.push_back(0);   // background: 0
    	labelSet.push_back(1);   // foreground: 1
    
    	int rows = _binImg.rows - 1;
    	int cols = _binImg.cols - 1;
    	for (int i = 1; i < rows; i++)
    	{
    		int* data_preRow = _lableImg.ptr<int>(i - 1);
    		int* data_curRow = _lableImg.ptr<int>(i);
    		for (int j = 1; j < cols; j++)
    		{
    			if (data_curRow[j] == 1)
    			{
    				std::vector<int> neighborLabels;
    				neighborLabels.reserve(2);
    				int leftPixel = data_curRow[j - 1];
    				int upPixel = data_preRow[j];
    				if (leftPixel > 1)
    				{
    					neighborLabels.push_back(leftPixel);
    				}
    				if (upPixel > 1)
    				{
    					neighborLabels.push_back(upPixel);
    				}
    
    				if (neighborLabels.empty())
    				{
    					labelSet.push_back(++label);  // assign to a new label
    					data_curRow[j] = label;
    					labelSet[label] = label;
    				}
    				else
    				{
    					std::sort(neighborLabels.begin(), neighborLabels.end());
    					int smallestLabel = neighborLabels[0];
    					data_curRow[j] = smallestLabel;
    
    					// save equivalence
    					for (size_t k = 1; k < neighborLabels.size(); k++)
    					{
    						int tempLabel = neighborLabels[k];
    						int& oldSmallestLabel = labelSet[tempLabel];
    						if (oldSmallestLabel > smallestLabel)
    						{
    							labelSet[oldSmallestLabel] = smallestLabel;
    							oldSmallestLabel = smallestLabel;
    						}
    						else if (oldSmallestLabel < smallestLabel)
    						{
    							labelSet[smallestLabel] = oldSmallestLabel;
    						}
    					}
    				}
    			}
    		}
    	}
    
    	// 更新标签
    	// 用每个连通域中最小的标签来表示这个连通域
    	for (size_t i = 2; i < labelSet.size(); i++)
    	{
    		int curLabel = labelSet[i];
    		int preLabel = labelSet[curLabel];
    		while (preLabel != curLabel)
    		{
    			curLabel = preLabel;
    			preLabel = labelSet[preLabel];
    		}
    		labelSet[i] = curLabel;
    	}
    
    	// 2. 第二遍扫描
    	for (int i = 0; i < rows; i++)
    	{
    		int* data = _lableImg.ptr<int>(i);
    		for (int j = 0; j < cols; j++)
    		{
    			int& pixelLabel = data[j];
    			pixelLabel = labelSet[pixelLabel];
    		}
    	}
    }
    
    void icvprCcaBySeedFill(const cv::Mat& _binImg, cv::Mat& _lableImg)
    {
    	/*
    	种子填充法的连通区域分析方法:
    (1)扫描图像,直到当前像素点B(x,y) == 1:
    a、将B(x,y)作为种子(像素位置),并赋予其一个label,然后将该种子相邻的所有前景像素都压入栈中;
    b、弹出栈顶像素,赋予其相同的label,然后再将与该栈顶像素相邻的所有前景像素都压入栈中;
    c、重复b步骤,直到栈为空;
    此时,便找到了图像B中的一个连通区域,该区域内的像素值被标记为label;
    (2)重复第(1)步,直到扫描结束;
    扫描结束后,就可以得到图像B中所有的连通区域;
    	*/
    
    	if (_binImg.empty() ||
    		_binImg.type() != CV_8UC1)
    	{
    		return;
    	}
    
    	_lableImg.release();
    	_binImg.convertTo(_lableImg, CV_32SC1);
    
    	int label = 1;  // start by 2
    
    	int rows = _binImg.rows - 1;
    	int cols = _binImg.cols - 1;
    	for (int i = 1; i < rows - 1; i++)
    	{
    		int* data = _lableImg.ptr<int>(i);
    		for (int j = 1; j < cols - 1; j++)
    		{
    			if (data[j] == 1)
    			{
    				std::stack<std::pair<int, int>> neighborPixels;
    				neighborPixels.push(std::pair<int, int>(i, j));     // 像素坐标: <i,j>
    				++label;  //从一个新label开始
    				while (!neighborPixels.empty())
    				{
    					// 栈中最上面的像素给予和与其连通的像素相同的label
    					std::pair<int, int> curPixel = neighborPixels.top();
    					int curX = curPixel.first;
    					int curY = curPixel.second;
    					_lableImg.at<int>(curX, curY) = label;
    
    					// 弹出最上面的像素
    					neighborPixels.pop();
    
    					// 推及到四个邻居
    					if (_lableImg.at<int>(curX, curY - 1) == 1)
    					{// 左边的像素
    						neighborPixels.push(std::pair<int, int>(curX, curY - 1));
    					}
    					if (_lableImg.at<int>(curX, curY + 1) == 1)
    					{// 右边的像素
    						neighborPixels.push(std::pair<int, int>(curX, curY + 1));
    					}
    					if (_lableImg.at<int>(curX - 1, curY) == 1)
    					{// 上面的像素
    						neighborPixels.push(std::pair<int, int>(curX - 1, curY));
    					}
    					if (_lableImg.at<int>(curX + 1, curY) == 1)
    					{// 下面的像素
    						neighborPixels.push(std::pair<int, int>(curX + 1, curY));
    					}
    				}
    			}
    		}
    	}
    }
    
    //为连通域加上颜色
    cv::Scalar icvprGetRandomColor()
    {
    	uchar r = 255 * (rand() / (1.0 + RAND_MAX));
    	uchar g = 255 * (rand() / (1.0 + RAND_MAX));
    	uchar b = 255 * (rand() / (1.0 + RAND_MAX));
    	return cv::Scalar(b, g, r);
    }
    
    void icvprLabelColor(const cv::Mat& _labelImg, cv::Mat& _colorLabelImg)
    {
    	if (_labelImg.empty() ||
    		_labelImg.type() != CV_32SC1)
    	{
    		return;
    	}
    
    	std::map<int, cv::Scalar> colors;
    
    	int rows = _labelImg.rows;
    	int cols = _labelImg.cols;
    
    	_colorLabelImg.release();
    	_colorLabelImg.create(rows, cols, CV_8UC3);
    	_colorLabelImg = cv::Scalar::all(0);
    
    	for (int i = 0; i < rows; i++)
    	{
    		const int* data_src = (int*)_labelImg.ptr<int>(i);
    		uchar* data_dst = _colorLabelImg.ptr<uchar>(i);
    		for (int j = 0; j < cols; j++)
    		{
    			int pixelValue = data_src[j];
    			if (pixelValue > 1)
    			{
    				if (colors.count(pixelValue) <= 0)
    				{
    					colors[pixelValue] = icvprGetRandomColor();
    				}
    				cv::Scalar color = colors[pixelValue];
    				*data_dst++ = color[0];
    				*data_dst++ = color[1];
    				*data_dst++ = color[2];
    			}
    			else
    			{
    				data_dst++;
    				data_dst++;
    				data_dst++;
    			}
    		}
    	}
    }
    
    int main(int argc, char** argv)
    {
    	cv::Mat binImage = cv::imread("E:/C++/CVE6/图片2.png", 0);
    	cv::imshow("img", binImage);
    	//cv::Mat binImage2;
    	cv::threshold(binImage, binImage, 50, 1, CV_THRESH_BINARY_INV);
    	
    	cv::Mat labelImg;
    	//icvprCcaByTwoPass(binImage, labelImg);
    	icvprCcaBySeedFill(binImage, labelImg) ;
    
    	// 展示结果
    	cv::Mat grayImg;
    	//结果*10,更突出
    	labelImg *= 10;
    	labelImg.convertTo(grayImg, CV_8UC1);
    	cv::imshow("labelImg", grayImg);
    
    	cv::Mat colorLabelImg;
    	//更改连通域颜色
    	icvprLabelColor(labelImg, colorLabelImg);
    	cv::imshow("colorImg", colorLabelImg);
    	cv::waitKey(0);
    
    	return 0;
    }
    
    
    
    
    展开全文
  • 连通域分析(connected component analysis)的目的是在二值图像中,利用像素之间的连接关系,获得分割不同的区域。 详细解释,参见wiki 下面是two-pass方法的Matlab实现: image = [0,0,1,0,0,1,0; 1,1,1,0,1,1,1;...

    连通域分析(connected component analysis)的目的是在二值图像中,利用像素之间的连接关系,获得分割不同的区域。

    详细解释,参见wiki

    下面是two-pass方法的Matlab实现,这里采用的是4邻域:

    image = [0,0,1,0,0,1,0;
             1,1,1,0,1,1,1;
             0,0,1,0,0,1,0;
             0,1,1,0,1,1,0];
             
    [row, col] = size(image);
    
    map_label_first = zeros(size(image)); % first pass
    map_label_second = zeros(size(image)); % second pass
    
    label_ID = 1;
    label_set = [];
    
    %% First pass for temporary labels.
    for i = 1:1:row
        for j = 1:1:col
            tmp_neighbors = [];
            if(1==image(i,j)) % foreground
                if(i-1>0 && 1==image(i-1,j) && map_label_first(i-1,j)~=0) % up
                    tmp_neighbors(1, length(tmp_neighbors)+1) = map_label_first(i-1,j);
                end
                
                if(j-1>0 && 1==image(i,j-1) && map_label_first(i,j-1)~=0) % left
                    tmp_neighbors(1, length(tmp_neighbors)+1) = map_label_first(i,j-1);
                end
                
                label_neighbors = unique(tmp_neighbors);
                
                if(true == isempty(label_neighbors)) % Assign a new label_ID
                    map_label_first(i,j) = label_ID;
                    
                    label_set(1, label_ID) = label_ID;
                    label_ID = label_ID + 1;
                    
                else % Update label_set
                    map_label_first(i,j) = min(label_neighbors);
                    
                    label_set(1, max(label_neighbors)) = min(label_neighbors);               
                end
            end
        end
    end
    
    %% Second pass for merging labels.
    for i = 1:1:row
        for j = 1:1:col
            if(map_label_first(i,j)~=0)
                map_label_second(i,j) = label_set(1, map_label_first(i,j));
            end
        end
    end
    
    展开全文
  • 图像处理——连通域的长宽比

    千次阅读 2018-02-23 21:25:11
    3.对二值图像进行形态学处理,主要任务是去除连通域面积较小的区域以及降低筛选难度。4.利用bwlabel()函数对连通区域进行标记5.得到连通域的长宽比matlab实现程序:clear all;close all;clc I= imr...
  • MATLAB中图像连通域操作

    千次阅读 2017-09-19 10:53:20
    最近在用MATLAB做一个图像处理算法的仿真,其中涉及到了连通域的操作,因为平时对C++比较熟悉,对matlab语言不熟悉,折腾了好久,算是做一个记载吧。1、bwareaopen函数*用法:img = bwareaopen(img,set_noise); %% ...
  • 四连通域与八连通域 1、所谓四连通区域或四邻域,是指对应像素位置的上、下、左、右,是紧邻的位置。共4个方向,所以称之为四连通区域,又叫四邻域。 2、所谓八连通区域或八邻域,是指对应位置的上、下、左、右、...
  • clear; clc; I=imread('rice.png'); s=strel('disk',2); I=imerode(I,s); I=im2bw(I); I=I*255; [m,n]=size(I); %利用队列结构 front=1; rear=1;%指明下一个像素入队的位置 Queue=zeros(m*n,2);... for j=1:n
  • 图像中,已知了某连通域的一个像素点,如何根据该像素点确定像素点所在的连通域(比如图像中有多个连通域,而现在只知一个连通域的像素点,如何根据该点反推像素点所在的连通域,并标记出来)
  • 基本概念在数字图像处理中,有个连通域的概念连通区域(Connected Component)一般是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域(Region,Blob)。在...
  • 实际上估计不是太多的人懂得标记连通域的原理,加上在医学图像处理中,我们常常用到3维图像,而上述工具只解决了2维图像上的情况,并不支持3维图像的标记(目前还不支持),因此有必要对这个连通域标记算法进行进一步...
  • 在实际应用中,很多图像的分析最终都转换为二值图像的分析,比如:医学图像分析、前景检测、字符识别,形状识别。二值化+数学形态学能解决很多计算机识别工程中目标提取的问题。 二值图像分析最重要的方法就是...
  • 图像连通域分析算法处理

    千次阅读 2008-10-22 14:15:00
    1. 算法目的:连通域分析算法的目的就是对二值图像进行分析,计算出在每帧图象上目标(这里是人)的位置。这里主要扩充了游程码的思想,将相互毗邻的值为“1”的像素点归结到同一个连通域中,不相互毗邻的点归结到...
  • #include #include #include //OpenCV包含头文件 #include #include //容器头文件 using namespace std; using namespace cv;...//记录连通域数值对应关系 class colorobj { public: int value; Scalar
  • 提取图像中不同的连通域图像处理中较为常用的方法,例如在车牌识别、文字识别、目标检测等领域对感兴趣区域分割与识别。一般情况下,一个连通域内只包含一个像素值,因此为了防止像素值波动对提取不同连通域的影响...
  • 该源码是VS.NET下采用C#对数字图像进行处理,主要包括对彩色图像的灰度化、以及对图像连通区域进行标记等。
  • OpenCV-二值图像连通域分析

    万次阅读 多人点赞 2017-09-26 16:21:27
    连通域分析对于图像处理后面涉及到模式识别的内容来说是基础 连通区域(Connected Component)一般是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域(Region,Blob)。连通区域分析(Connected ...
  • 二值图像分析 ...什么是连通域 像素周围的邻接点构成的区域 图像中具有相同像素值且位置相邻的前景像素点组成的图像区域 连通区域分析(Connected Component Analysis,Connected Component Labelin
1 2 3 4 5 ... 20
收藏数 2,232
精华内容 892
关键字:

图像处理 连通域