2017-05-12 13:34:22 qq826309057 阅读数 752

前言

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

算法原理

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;
}

结果

这里写图片描述

这里写图片描述

2018-03-18 17:25:56 lijjianqing 阅读数 1267

图像处理中连通域指由前景相同像素,并且相同像素邻接的像素组成的域。图像处理中一般都是对二值图像(1白色,0为黑色,一般前景为0黑色)做连通域分析。连通域分析指把连通域找出来并且标记出来。

连通域标记方法:(1)两次遍历实现;(2)深度优先搜索遍历

1.第一次遍历

如果当前元素为0则赋值一个label,lebel从大于1开始,如果像素的邻接像素的标签有大于1的,则当前元素赋值为大于1的最小的label。记录等价标签。

第二次遍历

遍历找到等价标签,标记等价标签的最小值为label。

如果只求连通域的数量则只需循环一次就够了,连通域数等于label-等价标签的个数-label起始值。

如:起始标记为label = 1,等价标签存放在列表中,list=[(2,6),(3,7)],即等价标签个数有len(list),则连通域个数为label -1-len(list).

如果需要将连通区域标记的的话需要循环两次。

import numpy
a = [[1 for i in range(10)] for j in range(10)]
a = [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
     [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
     [1, 1, 1, 0, 0, 0, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]]
a = numpy.array(a)
#cv2.imwrite('/home/lijq/IdeaProjects/AnimalRecognition_Demo/demo/person3.jpg',a)
label = 1
list = []
if a[0][0]<1:
    label +=1
    a[0][0] = label
for j in range(1,len(a[0])):
    if a[0][j]<1:
        if a[0][j-1]>1:
            a[0][j]=a[0][j-1]
        else:
            label +=1
            a[0][j] = label
for i in range(1,len(a)):
    if a[i][0]<1:
        if a[i-1][0]>1:
            a[i][0]=a[i-1][0]
        else:
            label +=1
            a[i][0] = label
for i in range(1,len(a)):
    for j in range(1,len(a[0])):
        if a[i][j]<1:
            if a[i][j-1]>1 and a[i-1][j]>1:
                a[i][j] = min(a[i][j-1],a[i-1][j])
                if a[i][j-1]!=a[i-1][j]:
                    list.append((a[i][j-1],a[i-1][j]))
            elif a[i][j-1]>1 and a[i-1][j]==1:
                a[i][j] = a[i][j-1]
            elif a[i-1][j]>1 and a[i][j-1] ==1:
                a[i][j] = a[i-1][j]
            else:
                label += 1
                a[i][j] = label
nums_lt = label-1-len(list)
print label,list,nums_lt
print a


2.深度遍历标记

通过深度优先把所有连通的找出来标记完,再继续遍历下一个连通区域。连通域数量为 label-1.(设置的label默认值为1,歧视标记为2,如果从1标记的话会和图像值里的1混淆,所以为了方便起始值可以是任意大于1的数)

a = [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
     [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
     [1, 1, 1, 0, 0, 0, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]]
a = numpy.array(a)
def dfs(nums,i,j,label):
    if i >=len(nums) or j>=len(nums[0]) or i<0 or j<0:
        return
    if nums[i][j]<1:
        nums[i][j]=label
        dfs(nums,i,j+1,label)
        dfs(nums,i+1,j,label)
        dfs(nums,i-1,j,label)
        dfs(nums,i,j-1,label)
        dfs(nums,i-1,j-1,label)

label = 1
for i in range(len(a)):
    for j in range(len(a[0])):
        if a[i][j]<1:
            label +=1
            a[i][j] = label
            dfs(a,i,j+1,label)
            dfs(a,i+1,j,label)
print a

2019-11-21 23:27:17 weixin_43373833 阅读数 59

图像连通域分析

1、连通域的基本概念

连通域一般是指图像中具有相同像素值且位置相邻的像素点组成的图像区域。连通域分析是指将图像中的各个连通区域找出并标记。连通区域分析在图像分析处理的众多应用领域非常常用。连通区域分析处理的对象一般是一张二值化后的图像。像素邻域关系一般有四邻域和八邻域两种,下面是以四邻域做介绍。

2、图像灰度化

(1)最大类间方差法原理

上面说到连通域分析处理的一般是二值化后的图像,那么灰度图像怎么二值化呢?我们可以用到otsu算法,即最大类间方差法。下面简单介绍一下最大类间方差法。
最大类间方差法最重要的是这个公式:
在这里插入图片描述
可以看到原理非常简单,类间方差和方差的原理差不多,方差反应所有数据的偏差情况,而类间方差反应的是数据分成两部分之后两部分的偏差情况。举个简单例子来说:
假设有5个数据1、2、3、4、5,那么它们的平均值为3,那么方差就是1/5{(1-3)2+(2-3)2+(3-3)2+(4-3)2+(5-3)2}。那么类方差呢?假设我们设置阈值T为3,小于等于3的作为A部分,大于3的作为B部分,那么A部分的均值为2,概率为3/5;B部分的均值为4.5,概率为2/5;类方差就是3/5(2-3)2+2/5(4.5-3)2

(2)最大类间方差法实现

matlab实现最大类间方差法:

close;clear;clc;
[filename,pathname]=uigetfile({'*.jpg';'*.bmp';'*.gif'},'选择原图片');
img = imread([pathname,filename]);
img = rgb2gray(img);
level=graythresh(img);
img =double(img);
[M,N]=size(img);                     %得到图像行列像素
number_all=M*N;                    %总像素值
hui_all=0.0;                         %预设图像总灰度值为0
ICV_t=0.0;                           %预设最大方差为0
k=0;
%得到图像总灰度值
for i=1:M
    for j=1:N
        hui_all=hui_all+img(i,j);
    end
end
all_ave=hui_all/number_all;   %图像灰度值的总平均值
 
 
%t为某个阈值,把原图像分为A部分(每个像素值>=t)与B部分(每个像素值<t)
for t=0:255                       %不断试探最优t值
    hui_A=0.0;                      %不断重置A部分总灰度值
    hui_B=0.0;                      %不断重置B部分总灰度值
    number_A=0.0;                   %不断重置A部分总像素
    number_B=0.0;                   %不断重置B部分总像素
    for i=1:M                     %遍历原图像每个像素的灰度值
        for j=1:N
            if (img(i,j)>=t)    %分割出灰度值>=t的像素
                number_A=number_A+1;  %得到A部分总像素
                hui_A=hui_A+img(i,j);   %得到A部分总灰度值
            elseif (img(i,j)<t) %分割出灰度值《t的像素
                number_B=number_B+1;  %得到B部分总像素
                hui_B=hui_B+img(i,j);   %得到B部分总灰度值
            end
        end
    end
    PA=number_A/number_all;            %得到A部分像素总数与图像总像素的比列
    PB=number_B/number_all;            %得到B部分像素总数与图像总像素的比列
    A_ave=hui_A/number_A;          %得到A部分总灰度值与A部分总像素的比例
    B_ave=hui_B/number_B;          %得到B部分总灰度值与B部分总像素的比例
    ICV=PA*((A_ave-all_ave)^2)+PB*((B_ave-all_ave)^2);  %Otsu算法
    if (ICV>ICV_t)                     %不断判断,得到最大方差
        ICV_t=ICV;
        k=t;                           %得到最大方差的最优阈值
    end
end
k                                      %显示阈值 



(3)优缺点分析

优点:(1)原理简单,速度较快。
(2)数学上可以证明取最佳阈值时,两部分之间差别最大。

缺点:(1)受噪声影响大(解决方法二维otsu算法
(2)类间方差准则函数可能呈现双峰或多峰,此时效果不好(解决方法局部阈值法
原图一维otsu二值图
可以看到一维最大类间方差方法实现的效果不理想,有很多噪声点。

(4)二维最大类间方差法

二维最大类间方差法相比一维otsu算法抗噪声能力更强,基本原理可以参考这篇博客,也可以找相关论文进行学习,这里用matlab实现了快速二维最大类间方差法。

matlab实现的二维最大类间方差法

clear; 
clc;
[filename,pathname]=uigetfile({'*.jpg';'*.bmp';'*.gif'},'选择原图片');
I = imread([pathname,filename]);
Igray=rgb2gray(I); 
imageBinary=Igray;
% Igray32=uint32(Igray); %强制类型转换
[Height,Width]=size(Igray); 
Igray_ex=[zeros(1,Width+2);zeros(Height,1),Igray,zeros(Height,1);zeros(1,Width+2)];%扩展图像
Igray_ex32=uint32(Igray_ex); %强制类型转换
%%定义变量
xsumm=0;    %行像素和
xsumn=0;    %
summ=0;
sumn=0;
flag=1;  %while循环标志位
graygrade=zeros(256,256);
possiblity=zeros(256,256);
%%求初始阈值
for m = 2:(Height)   %每行循环,从第二行第二列开始
        xsumm=0;    %行像素和清零
        xsumn=0;    %
        for n = 2:(Width)   %每列循环
                xsumm=xsumm+Igray_ex32(m,n);
                temp=Igray_ex32(m-1,n-1)+Igray_ex32(m-1,n)+Igray_ex32(m-1,n+1)...
                    +Igray_ex32(m,n-1)+Igray_ex32(m,n)+Igray_ex32(m,n+1)...
                    +Igray_ex32(m+1,n-1)+Igray_ex32(m+1,n)+Igray_ex32(m+1,n+1);
                xsumn=xsumn+temp/9;
                temp=0;
        end
        xsumm=xsumm/(Width);
        xsumn=xsumn/(Width);
        summ=summ+xsumm;
        sumn=sumn+xsumn;
end
%%求初始阈值
t0=summ/(Height);   %灰度域值邻域平均值
s0=sumn/(Height);   %灰度域值

t=t0;
s=s0;
%%求最终阈值
 while(flag~=0)
        for m=1:256
                for n=1:256
                    graygrade(m,n)=0;
                    possiblity(m,n)=0;
                end
        end
%%目标类区域和背景类区域清零
        w0a=0;
        w1a=0;
        w0b=0;
        w1b=0;
        
        u0m=0;
        u1m=0;
        u0n=0;
        u1n=0;
%%        
        for m = 2:(Height)   %每行循环,从第二行第二列开始
                for n = 2:(Width)   %每列循环
                        f=Igray_ex32(m,n);%像素灰度值
                        temp=Igray_ex32(m-1,n-1)+Igray_ex32(m-1,n)+Igray_ex32(m-1,n+1)...
                        +Igray_ex32(m,n-1)+Igray_ex32(m,n)+Igray_ex32(m,n+1)...
                        +Igray_ex32(m+1,n-1)+Igray_ex32(m+1,n)+Igray_ex32(m+1,n+1);
                        g=temp/9;  % 像素邻域灰度平均值
                        if(f~=0 && g~=0) %防止下标为0越界
                                 graygrade(f,g)=graygrade(f,g)+1;
                        end
                end
        end
%%
        for m = 1:256   %每行循环,从第二行第二列开始
                for n = 1:256   %每列循环
                        possiblity(m,n)=graygrade(m,n)/((Width)*(Height));
                        if(m<=t)
                                w0a=possiblity(m,n)+w0a;
                        else
                                w1a=possiblity(m,n)+w1a;
                        end
                        
                         if(n<=s)
                                w0b=possiblity(m,n)+w0b;
                        else
                                w1b=possiblity(m,n)+w1b;
                        end
                end
        end
%%
        for m = 1:256   %每行循环,从第二行第二列开始
                for n = 1:256   %每列循环
                        if(m<=t)
                                u0m=m*possiblity(m,n)+u0m;
                        else
                                u1m=m*possiblity(m,n)+u1m;
                        end
                        
                         if(n<=s)
                                u0n=n*possiblity(m,n)+u0n;
                        else
                                u1n=n*graygrade(m,n)+u1n;
                        end
                end
        end
%%
       u0m=u0m/w0a;
       u0n=u0n/w0b;
       u1m=u1m/w1a;
       u1n=u1n/(w1b*(Width)*(Height));
       
       tfinal = (u0m+u1m)/2;
       sfinal = (u0n+u1n)/2;
       
       if(tfinal>256 || sfinal>256 || tfinal<0 || sfinal<0)
          
               t = t+1;
               s = s+1;
       else
           if (abs(tfinal-t)>1 || abs(sfinal-s)>1)
               t = tfinal;
               s=sfinal;
           else
               flag=0;
           end
       end     
 end
 %%强制类型转换
 t=uint8(t);
 s=uint8(s);
 tfinal=uint8(tfinal);
 sfinal=uint8(sfinal);
%%二值分割
for m=1:Height
    for n=1:Width
        if imageBinary(m,n) >tfinal
            imageBinary(m,n) = 255;
        else
            imageBinary(m,n) = 0;
        end
    end
end
%%画图
level=graythresh(Igray);
BW=im2bw(Igray,level);
level=uint8(level*256);
subplot(2,2,1),imshow(Igray);title(' 原图')
subplot(2,2,2);imshow(imageBinary);title(' Ostu二值图')
subplot(2,2,4);imshow(BW);title(' 自带函数二值图')

在这里插入图片描述
可以看到二维otsu实现的效果相比一维otsu以及matlab自带的阈值分割函数graythresh来说效果更好。但是我们发现二维的otsu算法实现的阈值分割二值图像仍然有很多噪声,我们可以通过开运算进行消除,开运算就是图像先进行腐蚀运算在进行膨胀运算实现,具体原理这里不详细介绍,可以通过matlab自带的函数imopen进行实现。效果图如下:
在这里插入图片描述
可以看到开运算能够除去孤立的小点,毛刺,而总的位置和形状不变。

3、连通域标记算法

将图像二值化后我们就可以进行连通域标记了,这里讲解两种连通域标记算法的实现,一个是Two-Pass算法,也叫两步法,另一个是Seed-Filling算法,也叫种子填充法。

(1)Two-Pass算法

1)Two-Pass算法原理

两遍扫描法,指的是通过扫描两遍图像,就可以将图像中存在的所有连通区域找出并标记。思路:第一遍扫描时赋予每个像素位置一个label,扫描过程中同一个连通区域内的像素集合中可能会被赋予一个或多个不同label,因此需要将这些属于同一个连通区域但具有不同值的label合并,也就是记录它们之间的连通关系;第二遍扫描就是将具有连通关系的标记的像素归为一个连通区域并赋予一个相同的label。

下面给出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)同属同一个连通区域;

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

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

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

算法图解如下:
在这里插入图片描述

2)Two-Pass算法实现

两步法的matlab代码如下

function [ outImg, labels ] = MyBwLabel( inputImg )
%MyBwLabel 自制的连通区域分析函数
%   [ outImg, labels ] = MyBwLabel( inputImg )
%   inputImg: 输入的图像,要求是二值化图像,且最大值为1
%   outputImg: 输出的图像,不同的连通区域的;label不同
%   labels:连通区域的个数
%
%   example : a = false(400);
%             a(rand(400) > 0.5) = true;
%             [b , l] = MyBwLabel(a);
%             imshow(b , [])
    if ~islogical(inputImg)
        error( '========do not support the data type!!============' )
    end
    labels = 1;
    outImg = double( inputImg );
    markFlag = false( size(inputImg) );
    [height , width] = size( inputImg );

    %% first pass
    for ii = 1:height
        for jj = 1:width
            if inputImg(ii,jj) > 0  % 若是前景点,则进行统计处理
                neighbors = [];  % 记录符合要求的邻域中的前景点,三列依次是行、列、值
                if (ii-1 > 0)
                    if (jj-1 > 0 && inputImg(ii-1,jj-1) > 0)
                        neighbors = [neighbors ; ii-1 , jj-1 , outImg(ii-1,jj-1)];
                    end
                    if inputImg(ii-1,jj) > 0
                        neighbors = [neighbors ; ii-1 , jj , outImg(ii-1,jj)];
                    end
                elseif (jj-1) > 0 && inputImg(ii,jj-1) > 0
                    neighbors = [neighbors ; ii , jj-1 , outImg(ii,jj-1)];
                end

                if isempty(neighbors)
                    labels = labels + 1;
                    outImg(ii , jj) = labels;
                else
                    outImg(ii ,jj) = min(neighbors(:,3));
                end

            end
        end
    end

    %% second pass
    [r , c] = find( outImg ~= 0 );
    for ii = 1:length( r )
        if r(ii)-1 > 0
            up = r(ii)-1;
        else
            up = r(ii);
        end
        if r(ii)+1 <= height
            down = r(ii)+1;
        else
            down = r(ii);
        end
        if c(ii)-1 > 0
            left = c(ii)-1;
        else
            left = c(ii);
        end
        if c(ii)+1 <= width
            right = c(ii)+1;
        else
            right = c(ii);
        end

        tmpM = outImg(up:down , left:right);
        [r1 , c1] = find( tmpM ~= 0 );
        if ~isempty(r1)
            tmpM = tmpM(:);
            tmpM( tmpM == 0 ) = [];

            minV = min(tmpM);
            tmpM( tmpM == minV ) = [];
            for kk = 1:1:length(tmpM)
                outImg( outImg == tmpM(kk) ) = minV;
            end

        end
    end

    u = unique(outImg);
    for ii = 2:1:length(u)
        outImg(outImg == u(ii)) = ii-1;
    end
    labels = length( u ) - 1;
end

(2)Seed-Filling算法

1)Seed-Filling算法原理

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

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

a、将B(x,y)作为种子(像素位置),并赋予其一个label,然后将该种子相邻的所有前景像素都压入栈中;
b、弹出栈顶像素,赋予其相同的label,然后再将与该栈顶像素相邻的所有前景像素都压入栈中;
c、重复b步骤,直到栈为空;
此时,便找到了图像B中的一个连通区域,该区域内的像素值被标记为label;

(2)重复第(1)步,直到扫描结束;
扫描结束后,就可以得到图像B中所有的连通区域;

算法图解如下:
在这里插入图片描述

2)Seed-Filling算法实现

种子填充法的matlab代码如下:

clear;
clc;
img=imread('5.4元.jpg');
imgGray=rgb2gray(img);
figure;
imshow(imgGray);
level=graythresh(imgGray);
imBW=imbinarize(imgGray,level);%二值化
figure;
imshow(imBW);
se=strel('disk',6);
imBW = imopen(imBW,se); %开运算

figure('NumberTitle', 'off', 'Name', '二值图像');
imshow(imBW);
outImg=uint8(imBW);
label=1;        %标记
flag=0;         %看是上下左右哪一个
num=0;          %用于计算连通域的个数
[Height,Width]=size(imBW); 
arr = [];%模拟堆栈
for m = 2:(Height-1)
    for n = 2:(Width-1)
        x=m;
        y=n;
        if(outImg(x,y)==0)   
            label=label+1;
            arr(end+1)=x;%记录坐标
            arr(end+1)=y;
            num=num+1;
            while(~isempty(arr))                   
                x=arr(end-1);
                y=arr(end);
                arr(end)=[];
                arr(end)=[];
                outImg(x,y)=label;
                if(outImg(x,y-1)==0)
                    arr(end+1)=x;%记录坐标
                    arr(end+1)=y-1;
%                     flag=1;%左
                end
                
                if(outImg(x,y+1)==0)
                    arr(end+1)=x;%记录坐标
                    arr(end+1)=y+1;
%                     flag=2;%右
                end
                
                if(outImg(x+1,y)==0)
                    arr(end+1)=x+1;%记录坐标
                    arr(end+1)=y;
%                     flag=3;%下
                end
                
                if(outImg(x-1,y)==0)
                    arr(end+1)=x-1;%记录坐标
                    arr(end+1)=y;
%                     flag=4;%上
                end
                
            end
        end
    end
end


figure('NumberTitle', 'off', 'Name', 'outImg');
imshow(outImg);


%%着色
R=img(:,:,1); %red
G=img(:,:,2); %green
B=img(:,:,3); %blue
for m=2:label   
    [O,P]=find(outImg==m);
    for q=1:size(O,1)
        R(O(q),P(q))=255;
        G(O(q),P(q))=0;
        B(O(q),P(q))=0;
    end
end

img(:,:,1)=R; %red
img(:,:,2)=G; %green
img(:,:,3)=B; %blue
figure('NumberTitle', 'off', 'Name', 'RGB');
imshow(img);

(3)两种算法实现结果

在这里插入图片描述
可以看出两种算法和matlab自带的连通域标记函数bwlabel函数标记的结果相同。

2015-05-11 20:59:21 oHanTanYanYing 阅读数 4361

    本文参考自这篇文章,由于其贴出来的代码运行效率较低而且不太符合本人的想法和习惯,所以对其进行了算法的重新设计和代码的重写。

 所谓图像的连通域,指的是图像上像素点值相同或者相近的点两两相邻接所组成的一块区域。而对于邻接,有四邻接和八邻接两种,如下:


四邻接          八邻接

 上图所示的'O'与‘X’相邻接,本文采取的是4邻接方式。

 在查找图像连通域的时候,一般都需要经过一个二值化的过程,将图像的像素值简化成非此即彼的情况,然后通过遍历图像来查找其中一个值是由几个连通域所组成的。如下图所示:

    

    该图像经过二值化处理之后,剩下两个值:黑色->255,白色->0,我们可以通过算法来找出其中黑色是由多少个连通域所组成,并且给各个连通域分别上色。该图也作为本文的示例图。

    连通域搜索算法是本文的核心,本文参照上面文章提到的二次搜索算法,提出了一个可以一次遍历出结果的算法,该算法的流程如下(单看流程可能会感觉很混乱,建议主要看代码,并以此为提纲):

    1.遍历图像,一旦碰到像素值不为0的像素进入第2步

    2.判断该像素是不是属于一个连通域,如果不属于任何已知连通域进入第3(a)步,如果属于一个已知连通域进入第3(b)步

    3(a).将连通域计数加1,并将该计数值赋给此像素点作为连通域的标志,同时把该值记录到一个映射关系数组的相应位置,如a[3]=3。回到第1步继续。

    3(b).将该像素值和其上下左右的像素值不为0的像素的值进行比较,找其中的最小值赋值给所有非零的像素作为连通域标志,并调整映射关系数组。回到第1步继续。

    4.经过上面的遍历,映射关系数组记录了修改过的图像的连通域信息,然而该信息比较杂乱,同一个连通域可能分别被几个值所标志,通过遍历该数组可以调整这个情况,将同一个连通域的映射值用其最小值进行标志。

    5.遍历图像结合映射关系数组对连通域值进行调整,经过这一步同一连通域将据有相同的像素值

    6.根据相同的像素值对同一连通域进行上色工作

    实现代码如下(为了方便使用了OPENCV,然而并没有用到其很多复杂的功能,只要稍作修改便可以用来直接处理图像的RGB数据区):

#include <time.h>
#include <opencv2/opencv.hpp>
#include <opencv2/core/core.hpp>//OpenCV包含头文件  
#include <opencv2/highgui/highgui.hpp>
#include <vector>//容器头文件 
using namespace std;
using namespace cv;

int valuearray[200000000] = { 0 };//记录连通域数值对应关系

class colorobj
{
public:
	int value;
	Scalar mycolor;
};

vector<colorobj> setcolor;//收集需要上色的灰度对象

bool equal255or0(int &value)//判断元素是否等于255或者0
{
	if (value == 255 || value == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void setvalue(int &value, int &minimun)//设置配对值
{
	if (value != 0)
	{
		if (valuearray[value] > minimun && valuearray[value]!=255)
		{
			int savemidvalue = valuearray[value];
			while (true)//将映射表调整
			{
				if (valuearray[savemidvalue] > minimun)
				{
					int mid = valuearray[savemidvalue];
					valuearray[savemidvalue] = minimun;
					savemidvalue = mid;
				}
				else
				{
					break;
				}
			}
			valuearray[value] = minimun;
		}
		value = minimun;
	}
}

void compare(int &value, int &minimun)//比较大小
{
	if (value != 0 && value!=255)
	{
		if (minimun >= value)
		{
			minimun = value;
		}
	}
}

Scalar GetRandomColor()//彩色显示
{
	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 main()
{
	long time = clock();//记录计算时间
	Mat Image = cv::imread("test.bmp", 0);//读入图像,并将图像灰度化
	threshold(Image, Image, 50, 255, CV_THRESH_BINARY_INV);//二值化图像
	imshow("a", Image);
	
	int contourmark = 1; //连通域标志

	Mat IntImage;//图片对象,用以将图像的像素变量从uchar转为int,以防止后面标志位大于255程序无法工作的情况
	Image.convertTo(IntImage, CV_32SC1);//将图像像素变量转为int

	//遍历图像,搜索连通域
	for (int Y = 1; Y < IntImage.rows - 1; Y++)//遍历图像,Y为行,X为列
	for (int X = 1; X < IntImage.cols - 1; X++)
	{
		if (IntImage.at<int>(Y, X) != 0)//记住这里是先行后列
		{
			//如果不属于任何一个连通域
			if (IntImage.at<int>(Y, X) == 255 && //本元素
				equal255or0(IntImage.at<int>(Y - 1, X)) && //上方元素
				equal255or0(IntImage.at<int>(Y + 1, X)) && //下方元素
				equal255or0(IntImage.at<int>(Y, X - 1)) && //左方元素
				equal255or0(IntImage.at<int>(Y, X + 1)))//右方元素
			{
				valuearray[contourmark] = contourmark;
				IntImage.at<int>(Y, X) = contourmark;
				if (IntImage.at<int>(Y - 1, X) == 255)
				{
					IntImage.at<int>(Y - 1, X) = contourmark;
				}
				if (IntImage.at<int>(Y + 1, X) == 255)
				{
					IntImage.at<int>(Y + 1, X) = contourmark;
				}
				if (IntImage.at<int>(Y, X - 1) == 255)
				{
					IntImage.at<int>(Y, X - 1) = contourmark;
				}
				if (IntImage.at<int>(Y, X + 1) == 255)
				{
					IntImage.at<int>(Y, X + 1) = contourmark;
				}
				contourmark++;
				if (contourmark==255)//防止冲突
				{
					valuearray[contourmark] = 255;
					contourmark = 256;
				}
			}
			else//已经属于某一个连通域
			{
				int getminimum = 200000000;
				//取得上下左右最小的标志位
				compare(IntImage.at<int>(Y, X), getminimum);
				compare(IntImage.at<int>(Y - 1, X), getminimum);
				compare(IntImage.at<int>(Y + 1, X), getminimum);
				compare(IntImage.at<int>(Y, X - 1), getminimum);
				compare(IntImage.at<int>(Y, X + 1), getminimum);
				//将最小的标志位赋值给目标
				setvalue(IntImage.at<int>(Y, X), getminimum);
				setvalue(IntImage.at<int>(Y - 1, X), getminimum);
				setvalue(IntImage.at<int>(Y + 1, X), getminimum);
				setvalue(IntImage.at<int>(Y, X - 1), getminimum);
				setvalue(IntImage.at<int>(Y, X + 1), getminimum);
			}
		}
	}

	for (size_t i = 1; i <= contourmark; i++)//将同一个连通域的对象映射表调整好,做完这一步映射表制作完成
	{
		valuearray[i] = valuearray[valuearray[i]];
	}

	for (int Y = 1; Y < IntImage.rows; Y++)//根据映射表对图像像素进行重新赋值
	for (int X = 1; X < IntImage.cols; X++)
	{
		if (IntImage.at<int>(Y, X) != 0)
		{
			IntImage.at<int>(Y, X) = valuearray[IntImage.at<int>(Y, X)];
		}
	}

	for (int j = 1; j < contourmark; j++)//获得需要上色的对象值
	{
		if (j==255)//跳过无意义值
		{
			continue;
		}
		bool dopush = true;
		for (int i = 0; i < setcolor.size(); i++)
		{
			if (setcolor[i].value == valuearray[j])
			{
				dopush = false;
				break;
			}
		}
		if (dopush == true)
		{
			colorobj mycolorobj;
			mycolorobj.value = valuearray[j];
			mycolorobj.mycolor = GetRandomColor();
			setcolor.push_back(mycolorobj);
		}
	}

	//彩色显示
	Mat colorLabelImg;
	colorLabelImg.create(IntImage.rows, IntImage.cols, CV_8UC3);
	colorLabelImg = Scalar::all(255);//初始化,将待显示图片的背景设置为白色

	for (int Y = 0; Y < IntImage.rows; Y++)//颜色填充
	for (int X = 0; X < IntImage.cols; X++)
	{
		if (IntImage.at<int>(Y, X) != 0)
		{
			for (int i = 0; i < setcolor.size(); i++)
			{
				if (IntImage.at<int>(Y, X) == setcolor[i].value)
				{
					colorLabelImg.at<Vec3b>(Y, X)[0] = setcolor[i].mycolor[0];
					colorLabelImg.at<Vec3b>(Y, X)[1] = setcolor[i].mycolor[1];
					colorLabelImg.at<Vec3b>(Y, X)[2] = setcolor[i].mycolor[2];
					break;
				}
			}
		}
	}
	printf("标志位值%d\n", contourmark);
	printf("花费时间%dms\n", clock() - time);
	imwrite("a.bmp", colorLabelImg);
	imshow("colorLabelImg", colorLabelImg);
	waitKey(0);
}


    处理的结果如下:


    OK,大功告成,转载记得指明出处:原文地址



    




2015-10-31 15:35:02 robin1987z 阅读数 1849

最大稳定极值区域(MSER)常用来提取图像二值化后稳定的联通区域,特别在OCR项目中的文字提取运用广泛。

MSER的基本思想就是,在灰度空间(0-255)内取一段连续阈值分别对图像进行二值化处理,接着在分别求取二值化后图像的灰度连通区域,并找出随阈值变化连通区域不发生显著变化的连通域。

阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会被淹没,如果从天空往下看,则大地分为陆地和水域两个部分,这类似于二值图像。在得到的所有二值图像中,图像中的某些连通区域变化很小,甚至没有变化,则该区域就被称为最大稳定极值区域。这类似于当水面持续上升的时候,有些被水淹没的地方的面积没有变化。它的数学定义为:

q(i)=|Qi+△-Qi-△|/|Qi|            (1)

其中,Qi表示阈值为i时的某一连通区域,△为灰度阈值的微小变化量,q(i)为阈值是i时的区域Qi的变化率。当q(i)为局部极小值时,则Qi为最大稳定极值区域。

显然,实现MSER最直接的方式是以不同阈值对图像进行二值化,求取各个阈值下二值化图像的联通域,同一块位置的连通域在一段阈值区域内公式1的值为局部最小值即为MSERs。但是这样的计算方式过程繁复、计算量大,OpenCV里的MSER实现是采用了组件树的方法,采用的也不是公式1,而是以下公式:

q(i)=|Qi-Qi-|/|Qi-|            (2)

Component Tree原理
当前元素和所有周围邻近当前区域的元素并且小于当前元素的区域都属于该区域
从最小值Xi像素开始建立一个region,如果Xi的邻域亮度值等于该像素的亮度值,则将Xi合并进邻域像素所在的region(且父节点是邻域像素父节点),如果Xi邻域的像素值小于Xi的像素值,则将邻域像素归入当前region,并将当前region作为邻域像素region的根节点(且邻域像素父节点指向当前像素的父节点),直到遍历完所有像素为止。


具体OPENCV的实现方式可以参考以下博文,非常详细:

http://blog.csdn.net/zhaocj/article/details/40742191




连通域提取

阅读数 2399

没有更多推荐了,返回首页