• 转自:https://en.wikipedia.org/wiki/Connected-component_labelingConnected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region ...

    转自:https://en.wikipedia.org/wiki/Connected-component_labeling


    Connected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction) is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic.  

    连通区域标记(或连通区域分析、blob提取、区域标记、blob发现或区域提取)是图论的算法应用,其中连通区域的子集是基于给定的启发式的唯一标记。

    Connected-component labeling is not to be confused with segmentation. 

    连接元件标签不能与分割混淆。

    Connected-component labeling is used in computer vision to detect connected regions in binary digital images, although color images and data with higher dimensionality can also be processed. 

    在计算机视觉中,连通区域标记用于检测二进制数字图像中的连接区域,即使彩色图像和具有较高维度的数据也可以被处理。

    When integrated into an image recognition system or human-computer interaction interface, connected component labeling can operate on a variety of information. 

    当集成到图像识别系统或人机交互界面时,连通区域标签可以操作各种(各部分)信息。

    Blob extraction is generally performed on the resulting binary image from a thresholding step, but it can be applicable to gray-scale and color images as well.  

    通常在阈值步骤中对产生的二进制图像执行Blob提取,但它也适用于灰度和彩色图像。(Blob在机器视觉中是指图像中的具有相似颜色、纹理等特征所组成的一块连通区域。)

    Blobs may be counted, filtered, and tracked.

     blob可以被计数、过滤和跟踪。

    Blob extraction is related to but distinct from blob detection.

     Blob提取与Blob检测有关联,但与Blob检测不同。

    Contents

      [hide


    overview

    A graph, containing vertices and connecting edges, is constructed from relevant input data.  

    一个包含顶点和连接边的图是由相关的输入数据构造的。

    The vertices contain information required by the comparison heuristic, while the edges indicate connected 'neighbors'.  

    这些顶点包含了比较启发式所要求的信息,而边缘则表示连接的“邻居”。

    An algorithm traverses the graph, labeling the vertices based on the connectivity and relative values of their neighbors.  

    一种算法遍历图像,根据相邻的连通性和相对值对顶点进行标记。

    Connectivity is determined by the medium;  

    连接性是由媒介决定的;

    image graphs, for example, can be 4-connected neighborhood or 8-connected neighborhood. 

    例如,图像图可以是4个连接的社区或8个连接的社区。

    Following the labeling stage, the graph may be partitioned into subsets, after which the original information can be recovered and processed . 

    在标记阶段之后,图表可以被划分为子集,之后原始信息可以被恢复和处理。

    definition

    The usage of the term connected components labeling (CCL) and its definition is quite consistent in the academic literature, whereas connected components analysis (CCA) varies in terms of both, terminology and problem definition. 

    术语连通区域标记(CCL)及其定义在学术文献中是相当一致的,而连通区域分析(CCA)则在术语和问题定义方面各不相同。

    Rosenfeld et al.[8] define connected components labeling as the “[c]reation of a labeled image in which the positions associated with the same connected component of the binary input image have a unique label. 

    罗森菲尔德等人将连通区域标记定义为“标记图像的创建”,在这个图像中,与二进制输入图像中相同的连通区域相关联的位置有一个唯一的标签。”

     Shapiro et al.[9] define CCL as an operator whose “input is a binary image and

     [... 夏比奥等9将CCL定义为一个操作,它的“输入是二进制图像和……”]

     output is a symbolic image in which the label assigned to each pixel is an integer uniquely identifying the connected component to which that pixel belongs.” 

    输出是一个符号图像,其中分配给每个像素的标签是唯一标识该像素所属的连通区域的整数标签。”

    There is no consensus on the definition of connected components analysis in the academic literature. 

    摘要在学术文献中,对连通区域分析(CCA)的定义没有达成共识。

    It is often used interchangeably with CCL. 

    它经常与CCL互换使用。

    [10][11] A more extensive definition is given by Shapiro et al.:[9] “Connected component analysis consists of connected component labeling of the black pixels followed by property measurement of the component regions and decision making. 

    夏比奥等人给出了一个更广泛的定义:9“连通区域分析由黑色像素的连接组件标记,然后是组件区域的属性测量和决策制定。” 

    The definition for connected components analysis presented here is more general, taking the thoughts expressed in [10][11][9] into account. “

    这里给出的连接组件分析的定义更一般,考虑了10 11 9中所表达的思想。

    “Connected components analysis derives one feature vector of each connected component in a binary 2-D input image.  

    “互联组件分析在二进制2-D输入图像中派生出每个连接组件的一个特征向量。

    A feature vector of a connected component is an n-tuple composed of functions of the component’s pattern.” 

    连接组件的一个特征向量是由组件模式的函数组成的n元组。”

    algorithm

    The algorithms discussed can be generalized to arbitrary dimensions, albeit with increased time and space complexity. 

    讨论的算法可以被推广到任意维度,尽管时间和空间的复杂性增加了。

    One component at a time 

    一次一个组件

    This is a fast and very simple method to implement and understand.  

    这是一个快速且非常简单的实现和理解的方法。

    It is based on graph traversal methods in graph theory.  

    它是基于图论中的图形遍历方法。

    In short, once the first pixel of a connected component is found, all the connected pixels of that connected component are labelled before going onto the next pixel in the image.  

    简而言之,一旦找到连接组件的第一个像素,连接组件的所有连接像素都会在进入图像的下一个像素之前被标记。

    This algorithm is part of Vincent and Soille's watershed segmentation algorithm,[12] other implementations also exist.[13] 

    该算法是Vincent和Soille的分水岭分割算法的一部分,其他12种实现也存在。

    In order to do that a linked list is formed that will keep the indexes of the pixels that are connected to each other, steps (2) and (3) below.  

    为了做到这一点,形成了一个链表,它将保持相互连接的像素的索引,下面的步骤(2)和(3)。

    The method of defining the linked list specifies the use of a depth or a breadth first search. 

     定义链表的方法指定了深度或广度优先搜索的使用。

    For this particular application, there is no difference which strategy to use.  

    对于这个特殊的应用程序,使用哪种策略没有区别。

    The simplest kind of a last in first out queue implemented as a singly linked list will result in a depth first search strategy. 

    最简单的一种最后的队列是作为单链表实现的,这将导致深度优先搜索策略。

    It is assumed that the input image is a binary image, with pixels being either background or foreground and that the connected components in the foreground pixels are desired.  

    假设输入图像是一个二进制图像,像素是背景或前景,并且前景像素中的连接组件是需要的。

    The algorithm steps can be written as: 

    算法步骤可以写成:

    1.Start from the first pixel in the image.  

    从图像的第一个像素开始。

    Set current label to 1.  

    将当前标签设置为1。

    Go to (2). (2)。

    2.If this pixel is a foreground pixel and it is not already labelled, give it the current label and add it as the first element in a queue, then go to (3). If it is a background pixel or it was already labelled, then repeat (2) for the next pixel in the image. 

    如果这是一个前景像素并没有贴上标签,给它当前的标签并将它添加作为一个队列的第一个元素,然后去(3)。如果是一个背景像素或者它已经贴上标签,然后重复(2)像素的图像。

    3.Pop out an element from the queue, and look at its neighbours (based on any type of connectivity).  

    从队列中取出一个元素,然后查看它的邻居(基于任何类型的连接)。

    If a neighbour is a foreground pixel and is not already labelled, give it the current label and add it to the queue. 

     如果一个邻居是一个前台像素,并且没有被标记,那么给它当前的标签并将其添加到队列中。

    Repeat (3) until there are no more elements in the queue. 

    重复(3)直到队列中没有更多的元素。

    4.Go to (2) for the next pixel in the image and increment current label by 1. 

    转到(2)图像中的下一个像素,并将当前标签增加1。

    Note that the pixels are labelled before being put into the queue.  

    注意,在放入队列之前,像素被标记为标记。

    The queue will only keep a pixel to check its neighbours and add them to the queue if necessary. 

     队列只会保留一个像素来检查其邻居,并在必要时将其添加到队列中

    This algorithm only needs to check the neighbours of each foreground pixel once and doesn't check the neighbours of background pixels. 

    这个算法只需要检查每个前景像素的邻居一次,并且不检查背景像素的邻居。

    Two-pass 

    双行程

    Relatively simple to implement and understand, the two-pass algorithm,[14] (also known as the Hoshen–Kopelman algorithm) iterates through 2-dimensional binary data.  

    相对简单的实现和理解,双程算法,14(也称为Hoshen——Kopelman算法)迭代2维二进制数据。

    The algorithm makes two passes over the image.  

    该算法对图像进行了两次传递。

    The first pass to assign temporary labels and record equivalences and the second pass to replace each temporary label by the smallest label of its equivalence class. 

    第一次通过分配临时标签和记录相等性,第二次传递用等价类的最小标签替换每个临时标签。

    The input data can be modified in situ (which carries the risk of data corruption), or labeling information can be maintained in an additional data structure. 

    输入数据可以就地修改(这可能会带来数据损坏的风险),或者可以在额外的数据结构中维护标签信息。

    Connectivity checks are carried out by checking neighbor pixels' labels (neighbor elements whose labels are not assigned yet are ignored), or say, the North-East, the North, the North-West and the West of the current pixel (assuming 8-connectivity). 

     连接检查是通过检查邻居像素的标签(标签未被分配的邻居元素被忽略),或者说是东北、北部、西北和当前像素的西部(假设8个连接)。

    4-connectivity uses only North and West neighbors of the current pixel.  

    4-连通性只使用当前像素的北和西邻居。

    The following conditions are checked to determine the value of the label to be assigned to the current pixel (4-connectivity is assumed) 

    检查以下条件,以确定被分配给当前像素的标签的值(假定4-连通性)

    Conditions to check: 条件检查:

    1. Does the pixel to the left (West) have the same value as the current pixel? 

    左边(西方)的像素是否与当前像素有相同的值?

    Yes – We are in the same region.  

    是的——我们在同一个地区。

    Assign the same label to the current pixel 

    将相同的标签分配给当前像素

    No – Check next condition

     不——检查下一个条件

    2.Do both pixels to the North and West of the current pixel have the same value as the current pixel but not the same label?

     在当前像素的北部和西部,两个像素都有与当前像素相同的值,但不是相同的标签吗?

    Yes – We know that the North and West pixels belong to the same region and must be merged.  

    是的——我们知道,北部和西部的像素属于同一地区,必须合并。

    Assign the current pixel the minimum of the North and West labels, and record their equivalence relationship 

    将当前的像素分配给北部和西部的最小值,并记录它们的等价关系

    No – Check next condition

     不——检查下一个条件

    3.Does the pixel to the left (West) have a different value and the one to the North the same value as the current pixel? 

    左边(西方)的像素有不同的值,而向北的像素与当前像素的值相同吗?

    Yes – Assign the label of the North pixel to the current pixel 

    是的——将北部像素的标签分配给当前像素

    No – Check next condition

     不——检查下一个条件

    4.Do the pixel's North and West neighbors have different pixel values than current pixel? 

    像素的北部和西部邻居的像素值是否与当前像素不同?

    Yes – Create a new label id and assign it to the current pixel 

    是的——创建一个新的label id并将其分配给当前像素

    The algorithm continues this way, and creates new region labels whenever necessary.

      该算法以这种方式继续进行,并在必要时创建新的区域标签。

    The key to a fast algorithm, however, is how this merging is done.  

    然而,快速算法的关键在于如何实现这种合并。

    This algorithm uses the union-find data structure which provides excellent performance for keeping track of equivalence relationships.

    该算法使用了联合查找的数据结构,为跟踪等价关系提供了良好的性能。

    [15] Union-find essentially stores labels which correspond to the same blob in a disjoint-set data structure, making it easy to remember the equivalence of two labels by the use of an interface method E.g.: findSet(l).  

    15个工会发现本质上是在一个分离的数据结构中存储与相同的blob对应的标签,这样就可以很容易地记住两个标签的等价性,例如:


    findSet(l)。findSet(l) returns the minimum label value that is equivalent to the function argument 'l'. 

    findSet(l)返回等价于函数参数'l'的最小标签值。

    Once the initial labeling and equivalence recording is completed, the second pass merely replaces each pixel label with its equivalent disjoint-set representative element.

     一旦初始标记和等效记录完成,第二次传递仅仅用等效的dis联合集合代表元素替换每个像素标签。

     A faster-scanning algorithm for connected-region extraction is presented below.[16] 

    下面给出了一种用于连接区域提取的快速扫描算法。

     On the first pass: 

    第一遍:

    1.Iterate through each element of the data by column, then by row (Raster Scanning) 

    逐列遍历数据的每个元素,然后逐行(光栅扫描)

    2.If the element is not the background

     如果元素不是背景

    2.1 Get the neighboring elements of the current element 

    获取当前元素的相邻元素

    2.2 If there are no neighbors, uniquely label the current element and continue 

    如果没有邻居,唯一的标签是当前元素并继续

    2.3 Otherwise, find the neighbor with the smallest label and assign it to the current element

     否则,找到最小标签的邻居并将其分配给当前元素

    2.4 Store the equivalence between neighboring labels 

    存储相邻标签之间的等价性

    On the second pass: 

    第二步: 

    1.Iterate through each element of the data by column, then by row 

    遍历数据的每个元素,逐列,然后逐行遍历

    2.If the element is not the background 

    如果元素不是背景

    2.1 Relabel the element with the lowest equivalent label 

    将元素与最低的等价标签进行重新标记


    Here, the background is a classification, specific to the data, used to distinguish salient elements from the foreground.

      在这里,背景是一种特定于数据的分类,用于区分突出的元素和前景。

    If the background variable is omitted, then the two-pass algorithm will treat the background as another region.

     如果省略了背景变量,那么双程算法将把背景作为另一个区域来处理。


    Graphical example of two-pass algorithm 

    双程算法的图形示例

    The array from which connected regions are to be extracted is given below (8-connectivity based). 

    下面给出了要提取连接区域的阵列(基于8个连接)。 

    We first assign different binary values to elements in the graph.  

    我们首先将不同的二进制值分配给图中的元素。

    Attention should be paid that the "0~1" values written on the center of the elements in the following graph are elements' values.

      应该注意的是,在下面的图中,在元素的中心写的“0 1”值是元素的值。

    While, the "1,2,... ……,7" values in the next two graphs are the elements' labels. 

    同时,“1、2、.... 7“下两个图中的值是元素的标签。

    The two concepts should not be confused. 

    这两个概念不应该被混淆。


    2.  After the first pass, the following labels are generated. 

     在第一次通过之后,会生成下列标签。

    A total of 7 labels are generated in accordance with the conditions highlighted above. 

    根据上面提到的条件,总共生成了7个标签。

    The label equivalence relationships generated are, 

    生成的标签等价关系是,

    Set IDEquivalent Labels
    11,2
    21,2
    33,4,5,6,7
    43,4,5,6,7
    53,4,5,6,7
    63,4,5,6,7
    73,4,5,6,7

    3.  Array generated after the merging of labels is carried out.  

    在标签合并后生成的数组被执行。

    Here, the label value that was the smallest for a given region "floods" throughout the connected region and gives two distinct labels, and hence two distinct labels.

     在这里,给定区域中最小的标签值“洪水”贯穿整个连接区域,并给出两个不同的标签,因此有两个不同的标签。


    4.  所示。

    Final result in color to clearly see two different regions that have been found in the array. 

    最后的结果是颜色,清楚地看到在数组中找到的两个不同的区域。

    The pseudocode is as follows: 

    伪代码如下:

    algorithm TwoPass(data)
       linked = []
       labels = structure with dimensions of data, initialized with the value of Background
    
       First pass
    
       for row in data:
           for column in row:
               if data[row][column] is not Background
    
                   neighbors = connected elements with the current element's value
    
                   if neighbors is empty
                       linked[NextLabel] = set containing NextLabel
                       labels[row][column] = NextLabel
                       NextLabel += 1
    
                   else
    
                       Find the smallest label
    
                       L = neighbors labels
                       labels[row][column] = min(L)
                       for label in L
                           linked[label] = union(linked[label], L)
    
       Second pass
    
       for row in data
           for column in row
               if data[row][column] is not Background
                   labels[row][column] = find(labels[row][column])
    
       return label

    Sequential algorithm 

    序贯算法

    Create a region counter 

    创建一个地区计数器

     Scan the image (in the following example, it is assumed that scanning is done from left to right and from top to bottom): 

    扫描图像(在下面的例子中,假设扫描是从左到右,从上到下): 

    For every pixel check the north and west pixel (when considering 4-connectivity) or the northeast, north, northwest, and west pixel for 8-connectivity for a given region criterion (i.e. intensity value of 1 in binary image, or similar intensity to connected pixels in gray-scale image). 

    对于每个像素,检查北部和西部的像素(在考虑4-连通性)或东北、北、西北和西像素,为一个给定区域的标准(即二进制图像的强度值为1,或灰度图像中与连接像素相似的强度)。

    If none of the neighbors fit the criterion then assign to region value of the region counter.  

    如果没有一个邻居符合这个标准,那么就分配区域计数器的区域值。

    Increment region counter. 

    增加地区计数器。

    If only one neighbor fits the criterion assign pixel to that region.

     如果只有一个邻居符合这个标准,那么就把像素分配给那个区域。

    If multiple neighbors match and are all members of the same region, assign pixel to their region. 

    如果多个邻居匹配并且都是同一区域的成员,那么将像素分配给他们的区域。

    If multiple neighbors match and are members of different regions, assign pixel to one of the regions (it doesn't matter which one). 

     如果多个邻居匹配并且是不同区域的成员,那么将像素分配给其中一个区域(这并不重要)。

    Indicate that all of these regions are equivalent. 

    表示所有这些区域都是等价的。

    Scan image again, assigning all equivalent regions the same region value.

     再次扫描图像,将相同区域的值分配给相同的区域。

    Others 

    其他

    Some of the steps present in the two-pass algorithm can be merged for efficiency, allowing for a single sweep through the image.  

    双程算法中的一些步骤可以合并为效率,允许对图像进行一次扫描。

    Multi-pass algorithms also exist, some of which run in linear time relative to the number of image pixels.[17] 

    多通道算法也存在,其中一些算法在线性时间内运行,相对于图像像素的数量。 

    In the early 1990s, there was considerable interest in parallelizing connected-component algorithms in image analysis applications, due to the bottleneck of sequentially processing each pixel.[18] 

    在20世纪90年代早期,由于顺序处理每个像素的瓶颈,在图像分析应用程序中有相当大的兴趣在图像分析应用程序中并行化连接组件算法。

     The interest to the algorithm arises again with an extensive use of CUDA.

     对该算法的兴趣再次出现,广泛使用了CUDA。

    One-pass version 

    一次通过的版本  

    A one pass (also referred to as single pass) version of the connected-component-labeling algorithm is given as follows.  

    摘要给出了一种基于连接件标记算法的递进(也称为单通)版本。

    The algorithm identifies and marks the connected components in a single pass. 

     该算法在一次传递中识别并标记连接的组件。

    The run time of the algorithm depends on the size of the image and the number of connected components (which create an overhead).  

    该算法的运行时间取决于图像的大小和连接组件的数量(这会产生开销)。

    The run time is comparable to the two pass algorithm if there are a lot of small objects distributed over the entire image such that they cover a significant number of pixels from it.  

    如果在整个图像上分布了大量的小对象,那么运行时间就可以与两种传递算法相媲美,这样它们就可以覆盖大量的像素。Otherwise the algorithm runs fairly fast.

     否则,算法运行得相当快。 

    Algorithm: 

    算法:

    1.Connected-component matrix is initialized to size of image matrix. 

    连接组件矩阵被初始化为图像矩阵的大小。

    2.A mark is initialized and incremented for every detected object in the image. 

    对图像中每个检测到的对象都初始化并增加一个标记。

    3.A counter is initialized to count the number of objects. 

    一个计数器被初始化以计算对象的数量。

    4.A row-major scan is started for the entire image. 

    对整个图像进行了一次大的扫描。

    5.If an object pixel is detected, then following steps are repeated while (Index !=0) 

    如果检测到一个对象像素,则重复执行下列步骤(index!=0)

    5.1 Set the corresponding pixel to 0 in Image. 

    在图像中设置相应的像素为0。

    5.2 A vector (Index) is updated with all the neighboring pixels of the currently set pixels. 

    一个矢量(索引)被更新为当前设置的像素的所有相邻像素。

    5.3 Unique pixels are retained and repeated pixels are removed. 

    独特的像素被保留,重复的像素被删除。

    5.4 Set the pixels indicated by Index to mark in the connected-component matrix. 

    在连接组件矩阵中设置由索引标记的像素。

    6. Increment the marker for another object in the image.

     增加图像中另一个物体的标记。

    The source code is as follows(4-connectivity based): 

    源代码如下(4-连通性):

    One-Pass(Image)
                [M, N]=size(Image);
                Connected = zeros(M,N);
                Mark = Value;
                Difference = Increment;
                Offsets = [-1; M; 1; -M];
                Index = [];
                No_of_Objects = 0;
    
       for i: 1:M :
           for j: 1:N:
                if(Image(i,j)==1)
                     No_of_Objects = No_of_Objects +1;
                     Index = [((j-1)*M + i)];
                     Connected(Index)=Mark;
                     while ~isempty(Index)
                          Image(Index)=0;
                          Neighbors = bsxfun(@plus, Index, Offsets');
                          Neighbors = unique(Neighbors(:));
                          Index = Neighbors(find(Image(Neighbors)));
                          Connected(Index)=Mark;
                     end
                     Mark = Mark + Difference;
                end
          end
      end

    展开全文
  • 连通区域(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;
    }
    
    
    
    
    展开全文
  • 在matlab中有对图像连通区域进行求解的函数,即bwlabel。但是opencv里好像没有,所以这里自己实现一下,方便以后使用。   首先,我回顾一下bwlabel的参数和用法:  L =bwlabel(BW,n)  返回一个和BW大小相同的L...

    在matlab中有对图像的连通区域进行求解的函数,即bwlabel。但是opencv里好像没有,所以这里自己实现一下,方便以后使用。

     

    首先,我回顾一下bwlabel的参数和用法:

     L =bwlabel(BW,n)
       
    返回一个和BW大小相同的L矩阵,包含了标记了BW中每个连通区域的类别标签,这些标签的值为12num(连通区域的个数)。n的值为48,表示是按4连通寻找区域,还是8连通寻找,默认为8

    [L,num] = bwlabel(BW,n)这里num返回的就是BW中连通区域的个数。

     

     

    实现步骤:

    (1)将输入图像阈值化,若输入图像为彩色图像,则先灰度化后再阈值化为二值图像。

    (2)给二值图像添加一个是否已访问的属性,类型为Bool(避免死循环)

    (3)找到第一个非零的像素点,将其入栈并将其是否已访问的属性置为真。

    (4)以栈的大小是否为0作为结束条件,寻找栈顶元素相邻的八邻域非零像素点,并将它们入栈,结束后将栈顶元素删除。

    (5)当栈为空时,表明一个连通区域已经遍历完成,需继续找到下一个非空且未访问过的像素点作为起点,重复4步骤,直到所有的非零像素点都被访问完成。

    (6)当所有的连通区域求解完成之后,将像素点个数最大的连通区域标记出来即可。

     

    用到的数据结构

    typedef struct{

             boolvSign;//像素点是否被访问过的标记,ture已访问,false表示未访问,给图片添加的一个属性

             intpixelValue;//像素值

    }isVisit;

     

     

    typedef struct{

             CvPointregionPoint;//该连通区域起点的坐标

             intregionId;//第i个连通区域的标号

             intpointNum;//第i个连通区域的像素点的总个数

    }connectRegionNumSet;

    输入图像:

     

    求解的连通区域:


    类似于bwlabel的标记


    提取出最大的连通区域:

























    --------------------------------------------------------------------------------------------------分割线-----------------------------------------------------------------------------------------------------

    别急,代码在最下哦。

    只有一个文件main.cpp。


    #include<cv.h>

    #include<highgui.h>

    #include<iostream>

    usingnamespace std;

    typedefstruct{

             bool vSign;//像素点是否被访问过的标记,ture已访问,false表示未访问,给图片添加的一个属性

             int pixelValue;//像素值

    }isVisit;

    typedefstruct{

             CvPoint regionPoint;//该连通区域起点的坐标

             int regionId;//第i个连通区域的标号

             int pointNum;//第i个连通区域的像素点的总个数

    }connectRegionNumSet;

     

    intcalConnectRegionNums(IplImage *srcGray,vector<vector<isVisit>>& validPicture,vector<connectRegionNumSet> &regionSet);

     

    intmain(){

             IplImage * src =cvLoadImage("useConnectImage.jpg");//F:/MasterHomeWork/ImageProcess/ConnectNumProgramMy/

             IplImage * srcGray = NULL;

     

             if(src->nChannels==1)

                       goto next;

             srcGray = cvCreateImage(cvSize(src->width,src->height),8,1);

             cvCvtColor(src,srcGray,CV_RGB2GRAY);

    next:

             if(!srcGray)

                       cvThreshold(src,srcGray,66,255,CV_THRESH_BINARY);

             else

                       cvThreshold(srcGray,srcGray,66,255,CV_THRESH_BINARY);

     

             cvNamedWindow("srcBinaryGray");

             cvShowImage("srcBinaryGray",srcGray);

            

     

            

             //按照以下方法,申请的是堆heap内存空间,相对而言较大,足够一般用户使用,而且可以动态分配。

             vector<vector<isVisit> >validPoint;//此种申请发放只要电脑内存足够大,图片的尺寸也可足够大

             validPoint.resize(srcGray->height);

             for(int i =0;i<validPoint.size();i++)

                       validPoint[i].resize(srcGray->width);

     

             vector<connectRegionNumSet>regionSet;//存放找到的各个连通区域

             //regionSet.size()为连通区域的个数。

     

             cout<<"连通区域的数目:"<<calConnectRegionNums(srcGray,validPoint,regionSet)<<endl<<endl;//计算连通区域数目

            

             char text[3];//设置连通区域的编号,最小标号为0,最大编号为99

             CvFont font;//设置字体

             //参数从左到右:字体初始化,字体格式,字体宽度,字体高度,字体倾斜度,字体粗细,字体笔画类型

             cvInitFont(&font,CV_FONT_HERSHEY_COMPLEX, 0.6, 0.6, 0, 1, 8);

             for(int i=0;i<regionSet.size();i++){

     

                       cout<<"第"<<i<<"个连通区域的起点坐标 =("<<regionSet[i].regionPoint.x<<","<<regionSet[i].regionPoint.y<<")"<<",像素总点数="<<regionSet[i].pointNum<<endl;

     

                       if(i < 10){//连通区域的个数为个位数

                                text[0] = '0';

                                text[1] = '0'+i;

                       }

                       else{//连通区域的个数为十位数

                                text[0] ='0'+(i)/10;

                                text[1] ='0'+(i)%10;

                       }

                       text[2] = '\0';

                       cvPutText(src,text,regionSet[i].regionPoint,&font,cvScalar(0,0,255));

             }

     

             cvNamedWindow("src");

             cvShowImage("src",src);

             cvShowImage("srcGray",srcGray);

     

             cvWaitKey(0);

             cvReleaseImage(&src);

             cvReleaseImage(&srcGray);

             cvDestroyAllWindows();

    }

     

    intcalConnectRegionNums(IplImage *srcGray, vector<vector<isVisit>>& validPicture,vector<connectRegionNumSet> &regionSet)

    {

             int regionId = 1;//管理连通区域标号的便令

             connectRegionNumSet regionSetTemp;//临时用到的regionSetTemp类型中间变量

             uchar * ptr = (uchar*)(srcGray->imageData);

             for(int y=0; y<srcGray->height;y++){//给图片加上一个是否已访问的属性

                       ptr = (uchar*)(srcGray->imageData+y*srcGray->widthStep);

                       for(int x=0;x<srcGray->width; x++){

                                validPicture[y][x].pixelValue= (int)ptr[x];

                                validPicture[y][x].vSign= false;//开始时默认都未访问

                       }

             }

             vector<CvPoint> stack;//stack(栈),heap(堆)

             CvPoint foundValidPoint;

             for(int y=0; y<srcGray->height;y++){//给图片加上一个是否已访问的属性

                       for(int x=0;x<srcGray->width; x++){

                                if(validPicture[y][x].pixelValue&& !validPicture[y][x].vSign){//找到下一个连通区域的起点,即像素值非零且未被访问过的点

                                         inteachRegionAcc = 1;//表示即将要寻找的连通区域的总像素点个数;

                                         //将validPicture[y][x]点默认为即将生成的连通区域的起点

                                         regionSetTemp.regionPoint= cvPoint(x,y);//x表示列,y表示行

                                         regionSetTemp.regionId= regionId++;

                                         regionSetTemp.pointNum= 1;

                                         regionSet.push_back(regionSetTemp);

                                         //将该点设置为已访问,并对其执行入栈操作

                                         validPicture[y][x].vSign= true;

                                         stack.push_back(cvPoint(x,y));

                                         while(stack.size()){//当栈内为元素时,表示该连通区域的点已经全部访问

                                                   foundValidPoint= stack.back();//从栈尾开始寻找八连通的相邻点

                                                   stack.pop_back();//上一句已得到栈尾像素点,该点可以出栈了

                                                   inti = foundValidPoint.x;//t

                                                   intj = foundValidPoint.y;//k

                                                   intminY = (j-1<0?0:j-1);

                                                   intmaxY = ((j+1>srcGray->height-1?srcGray->height-1:j+1));

                                                   intminX = (i-1<0?0:i-1);

                                                   intmaxX = (i+1>srcGray->width-1?srcGray->width-1:i+1);

                                                   for(intk=minY; k<=maxY; k++){//在八连通范围内(两点之间距离小于根号2的点),表示其相邻点,入栈c

                                                            for(intt=minX; t<=maxX; t++){

                                                                     if(validPicture[k][t].pixelValue&& !validPicture[k][t].vSign){//validPicture[k][t]如果没有访问过

                                                                               validPicture[k][t].vSign= true;//标志为已访问,防止死循环

                                                                               stack.push_back(cvPoint(t,k));//入栈,以便再次迭代

                                                                               eachRegionAcc++;//相邻点的数目加1                                                        

                                                                     }

                                                            }

                                                   }

                                         }

                                         if(eachRegionAcc> 1){//要求:连通区域的点数至少要有两个

                                                   regionSet[regionSet.size()-1].pointNum= eachRegionAcc;

                                         }

                                         else{//单个像素点不算,如果单个像素点也算,去掉该else语句即可

                                                   regionSet.pop_back();//上述默认的即将生成的连通区域不符合要求,出栈

                                                   regionId--;

                                         }

                                }

                       }

             }

     

             //找到最大连通区域,并标记-----------------------------------------------

             int max_pointNum = 0; //最大连通区域的像素点个数

             int max_regionId = 0;  //最大连通区域的标号

             for(int i=0;i<regionSet.size();i++)

             {

                       if(max_pointNum <regionSet[i].pointNum)

                       {        max_pointNum = regionSet[i].pointNum;

                                max_regionId =i;

                       }

             }

     

             for(int i=0;i<regionSet.size();i++)

                       if(i!=max_regionId)

             {

                      

                                //标记

                       int x = regionSet[i].regionPoint.x;

                       int y =regionSet[i].regionPoint.y;

     

                       //重置每个像素点为未访问

                       for(int y=0;y<srcGray->height; y++){//给图片加上一个是否已访问的属性

                                for(int x=0;x<srcGray->width; x++){

                                         validPicture[y][x].vSign= false;//开始时默认都未访问

                                }

                       }

     

                       //将该点设置为已访问,并对其执行入栈操作

                       validPicture[y][x].vSign =true;

                       cvSet2D(srcGray,y,x,CV_RGB(0,0,0));

                       stack.push_back(cvPoint(x,y));

                       while(stack.size()){//当栈内为元素时,表示该连通区域的点已经全部访问

                                foundValidPoint =stack.back();//从栈尾开始寻找八连通的相邻点

                                stack.pop_back();//上一句已得到栈尾像素点,该点可以出栈了

                                int i = foundValidPoint.x;//t

                                int j =foundValidPoint.y;//k

                                int minY =(j-1<0?0:j-1);

                                int maxY =((j+1>srcGray->height-1?srcGray->height-1:j+1));

                                int minX =(i-1<0?0:i-1);

                                int maxX =(i+1>srcGray->width-1?srcGray->width-1:i+1);

                                for(int k=minY;k<=maxY; k++){//在八连通范围内(两点之间距离小于根号2的点),表示其相邻点,入栈c

                                         for(intt=minX; t<=maxX; t++){

                                                   if(validPicture[k][t].pixelValue&& !validPicture[k][t].vSign){//validPicture[k][t]如果没有访问过

                                                            validPicture[k][t].vSign= true;//标志为已访问,防止死循环

                                                            stack.push_back(cvPoint(t,k));//入栈,以便再次迭代

                                                            cvSet2D(srcGray,k,t,CV_RGB(0,0,0));             

                                                   }

                                         }

                                }

                       }

             }

            

             //找到最大连通区域,并标记-----------------------------------------------

     

             return regionSet.size();

     

     

    }
    展开全文
  • 图像连通域分析

    2018-05-30 16:19:06
    一、前言二值图像图像的亮度值只有两个状态:黑(0)和白(255)。二值图像图像分析与识别中有着举足轻重的...在实际应用中,很多图像的分析最终都转换为二值图像的分析,比如:医学图像分析、前景检测、字符识别...
    转自:https://blog.csdn.net/tiandijun/article/details/51279643,转载仅为方便学习。

    一、前言

    二值图像的图像的亮度值只有两个状态:黑(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以内时,两者几乎无差别,当连通区域个数到了数量级时,上面的算法会比该算法快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)

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

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

    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所示,如果遇到已经标记过的外轮廓点,则从向右,将它右边的点都标记为的标号,直到遇到黑色像素为止。

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

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

    6,结束。

     

    image

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

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

    情况1:如果点是一个白色像素,在图像上这个位置没有被标记过,而且点的上方为黑色,则P是一个新的外轮廓的点,这时候我们将C的标签值标记给L图像上P点的位置,即,接着我们沿着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号(右上角)位置开始,看7号是不是白色点,如果是,则把这个点加入外轮廓点中,并将它标记与P点相同,如果7号点是黑色点,则按顺时针7-0-1-2-3-4-5-6这个顺序搜索直到遇到白点为止,把那个点确定为,加入外轮廓,并把这个点的标号设置与P点相同。这里很重要一步就是,假设我们2号点才是白点,那么7,0,1这三个位置我们都搜索过,所以我们要把这些点在L上标记为一个负值。如下图所示,其中右图像标记的结果。

    image    image

    2)那么如果P是不是外轮廓的起点,即P是外轮廓路径上的一个点,那么它肯定是由一个点进入的,我们设置为点,点的位置为,那么P点从这个位置开始寻找下一步的路径,是加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]不使用。

    实现代码如下:

    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

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

    展开全文
  • 图像处理之计算连通区域的角度方向 一:基本原理 基于空间Moment算法在图像处理与分析中寻找连通区域计算连通区域的中心与角度方 向Moment的一阶可以用来计算区域的中心质点,二阶可以用来证明图像的几个不变性 ...

    图像处理之计算连通区域的角度方向

    一:基本原理

    基于空间Moment算法在图像处理与分析中寻找连通区域计算连通区域的中心与角度方

    Moment的一阶可以用来计算区域的中心质点,二阶可以用来证明图像的几个不变性

    如旋转不变行,放缩不变性等。基于Moment的二阶计算结果,根据如下公式:


    可以得到区域的方向角度。

    二:算法流程

    1.      读入图像数据

    2.      根据连通组件标记算法得到区域

    3.      根据中心化Moment算法计算角度

    4.      根据中心离心值画出渲染黄色线条

    三:算法演示效果


    四:算法主要源代码

    package com.gloomyfish.image.moments;
    
    import java.awt.image.BufferedImage;
    
    import com.gloomyfish.filter.study.AbstractBufferedImageOp;
    import com.gloomyfish.rice.analysis.FastConnectedComponentLabelAlg;
    
    public class DirectionRegionMoments extends AbstractBufferedImageOp {
    
    	@Override
    	public BufferedImage filter(BufferedImage src, BufferedImage dest) {
    		int width = src.getWidth();
            int height = src.getHeight();
    
            if ( dest == null )
            	dest = createCompatibleDestImage( src, null );
    
            // first step - make it as binary image output pixel
            int[] inPixels = new int[width*height];
            int[] outPixels = new int[width*height];
            getRGB( src, 0, 0, width, height, inPixels );
            int index = 0;
            for(int row=0; row<height; row++) {
            	int tr = 0;
            	for(int col=0; col<width; col++) {
            		index = row * width + col;
                    tr = (inPixels[index] >> 16) & 0xff;
                    if(tr > 127)
                    {
                    	 outPixels[index] = 1;
                    }
                    else
                    {
                    	outPixels[index] = 0;
                    }
            	}
            }
            
            // second step, connected component labeling algorithm
            FastConnectedComponentLabelAlg ccLabelAlg = new FastConnectedComponentLabelAlg();
            ccLabelAlg.setBgColor(0);
            int[] labels = ccLabelAlg.doLabel(outPixels, width, height);
            int max = 0;
            for(int i=0; i<labels.length; i++)
            {
            	if(max < labels[i])
            	{
            		System.out.println("Label Index = " + labels[i]);
            		max = labels[i];
            	}
            }
            
            // third step, calculate the orientation of the region
            int[] input = new int[labels.length];
            GeometricMomentsAlg momentsAlg = new GeometricMomentsAlg();
            momentsAlg.setBACKGROUND(0);
            double[][] labelCenterPos = new double[max][2];
            double[][] centerAngles = new double[max][3];
            for(int i=1; i<=max; i++)
            {
            	int numberOfLabel = 0;
            	for(int p=0; p<input.length; p++)
            	{
            		if(labels[p] == i)
            		{
            			input[p] = labels[p];  
            			numberOfLabel++;
            		}
            		else
            		{
            			input[p] = 0;
            		}
            	}
            	labelCenterPos[i-1] = momentsAlg.getGeometricCenterCoordinate(input, width, height);
            	double m11 = momentsAlg.centralMoments(input, width, height, 1, 1);
            	double m02 = momentsAlg.centralMoments(input, width, height, 0, 2);
            	double m20 = momentsAlg.centralMoments(input, width, height, 2, 0);
            	double m112 = m11 * m11;
            	double dd = Math.pow((m20-m02), 2);
            	double sum1 = Math.sqrt(dd + 4*m112);
            	double sum2 = m02 + m20;
            	double a1 = sum2 + sum1;
            	double a2 = sum2 - sum1;
            	// double ecc = a1 / a2;
            	
            	double ra = Math.sqrt((2*a1)/Math.abs(numberOfLabel));
            	double rb = Math.sqrt((2*a2)/Math.abs(numberOfLabel));
            	double angle = Math.atan((2*m11)/(m20 - m02))/2.0;
            	centerAngles[i-1][0] = angle;
            	centerAngles[i-1][1] = ra;
            	centerAngles[i-1][2] = rb;
            }
            
            
            // render the angle/orientation info for each region
            // render the each connected component center position
            for(int row=0; row<height; row++) {
            	for(int col=0; col<width; col++) {
            		index = row * width + col;
            		if(labels[index] == 0)
            		{
            			outPixels[index] = (255 << 24) | (0 << 16) | (0 << 8) | 0; // make it as black for background
            		}
            		else
            		{
            			outPixels[index] = (255 << 24) | (0 << 16) | (0 << 8) | 100; // make it as blue for each region area
            		}
            	}
            }
            
            int labelCount = centerAngles.length;
            for(int i=0; i<labelCount; i++)
            {
            	System.out.println("Region " + i + "'s angle = " + centerAngles[i][0]);
            	System.out.println("Region " + i + " ra = " + centerAngles[i][1]);
            	System.out.println("Region " + i + " rb = " + centerAngles[i][2]);
            	double sin = Math.sin(centerAngles[i][0]);
            	double cos = Math.cos(centerAngles[i][0]);
            	System.out.println("sin = " + sin);
            	System.out.println("cos = " + cos);
            	System.out.println();
            	int crow = (int)labelCenterPos[i][0];
            	int ccol = (int)labelCenterPos[i][1];
            	int radius = (int)centerAngles[i][1]; // ra
            	for(int j=0; j<radius; j++)
            	{
            		int drow = (int)(crow - j * sin); // it is trick, display correct angle as you see!!!
            		int dcol = (int)(ccol + j * cos);
            		if(drow >= height) continue;
            		if(dcol >= width) continue;
            		index = drow * width + dcol;
                	outPixels[index] = (255 << 24) | (255 << 16) | (255 << 8) | 0; 
            	}
            }
            
            // make it as white color for each center position
            for(int i=0; i<max; i++)
            {
            	int crow = (int)labelCenterPos[i][0];
            	int ccol = (int)labelCenterPos[i][1];
            	index = crow * width + ccol;
            	outPixels[index] = (255 << 24) | (255 << 16) | (255 << 8) | 255; 
            }
            
            setRGB( dest, 0, 0, width, height, outPixels );
    		return dest;
    	}
    
    }
    用到的其它JAVA类代码请参见这里:

    http://blog.csdn.net/jia20003/article/details/17596645

    转载于:https://my.oschina.net/abcijkxyz/blog/721197

    展开全文
  • Matlab形态学图像处理:二值图像分割 标记连通区域和重心位置 删除连通区域 Matlab中可以使用graythresh(Img)函数设置二值化的阈值,再用im2bw转化为二值图像。在Matlab中,可以使用bwlabel()和bwlabeln()函数来...
  • ●标记分割后图像(为二值图像)中各区域的简单而有效的方法是检查各像素与其相邻像素的连通性(四、八连通方法)。 1、像素标记: ●假设对一幅二值图像从左到右、从上向下进行扫描(起点在图像的左下方)。 ●...
  • 该源码是VS.NET下采用C#对数字图像进行处理,主要包括对彩色图像的灰度化、以及对图像连通区域进行标记等。
  • http://www.bkjia.com/Javabc/771817.html连通区标记是最基本的图像处理算法之一。该算法中,按从左至右、从上至下的顺序,对整幅图像进行扫描,通过比较每个前景像素的邻域进行连通区标记,并创建等效标记列表。...
  • java图像处理之图的联通计数 图的联通分量计数,根据连通区域可分为八连通和四连通 (1)八连通:上左,上,上右,左,右,下左,下,下右 1 1 1 1 0 1 1 1 1 0和周围的1都视为连通关系 (2)四连通:上,下,...
  • 标记图像连通区域,求连通区域个数,进而可以计算连通区域面积 ,用于去噪等。
  • 本篇是第一篇,只涉及到一些基本的操作,涉及到的知识点如下: 1、二值化 2、开操作 ...3、连通区域提取 ...4、连通区域的重心提取 ...图像处理,第一步一般是进行二值化,而二值化最常用的方法就是o
  • DATE: 2019-7-29【Tags:图像处理基础】 【CV系列】数字图像处理基础:邻域、连通
  • 这篇文章最初发表在http://blog.csdn.net/j56754gefge/article/details/38777267,均是我原创,他人转载请注明出处! ...因为需要做连通区域标记,Matlab里有现成的算法,但在C++编程的时候发现没
  • 这是非常实用的VC代码,用于二值图像连通区域的标记,请大家参考
  • 本文主要介绍在CVPR和图像处理领域中较为常用的一种图像区域(Blob)提取的方法——连通性分析法(连通区域标记法)。文中介绍了两种常见的连通性分析的算法:1)Two-pass;2)Seed-Filling种子填充,并给出了两个...
  • 一张图: 本代码的功能描述是这样的,当两个同类的物体被隔开,但是由于标签一样,所以在lground truth的label上标注的是一样的。比如第一张图片同一颜色的是一类。而第二张图片由于很多物体被隔开,所以成为了...
  • 基于联通区域的matlab图像分割,对提取树叶上的害虫等的轮廓或纹理特征有独到的效果
  • 数字图像处理c#如何标记连通区域即去除小区域,要代码,希望过路的大侠帮帮忙,拜托各位了!
  • 图像连通区域标记

    2018-10-25 16:07:36
    由于最近做实验用到二值图像连通区域(八连通)标记,刚开始的时候为了验证算法有效性,用了递归的方法(太慢了,而且图像一大就容易栈溢出),最后查看了opencv和MATLAB的实现,做个记录。(为了简单说明,以下说明...
1 2 3 4 5 ... 20
收藏数 8,634
精华内容 3,453