2017-02-11 11:30:41 zhuason 阅读数 10404
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4187 人正在学习 去看看 佟刚

在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();

 

 

}
2017-05-19 19:46:21 guyuealian 阅读数 17220
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4187 人正在学习 去看看 佟刚

Matlab形态学图像处理:二值图像分割 标记连通区域和重心位置 删除连通区域

尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/71440949
    Matlab中可以使用graythresh(Img)函数设置二值化的阈值,再用im2bw转化为二值图像。在Matlab中,可以使用bwlabel()和bwlabeln()函数来标记二值图像的连通区域。需要注意的是:所谓的连通区域标记是指对二值图像中白色像色而言,即值为1的像素进行标记,而黑色像素看作是背景颜色。当然,Matlab中还有个regionprops()函数可以用于统计图像区域的属性,如面积大小,重心位置。关于bwlabel()、bwlabeln()和regionprops()的用法,请查看相关博客吧

    本博客Matlab代码将实现的功能:将图像转为二值图像,分割出感兴趣的区域,并用“红色矩形线框”标记连通区域的面积,用蓝色点标记连通区域的重心位置,为了减少噪声的干扰,代码中将连通区域面积(像素个数)不足100的区域认为是噪声点,并将其删除(即置为背景黑色)。本人用PS制作了一个GIF动画图,以便大家观看效果图:

clc;clear all;close all
%% 清空变量,读取图像,并显示其属性
clear;close all
src = imread('rice.jpg');
%显示原始图像
figure,
subplot(2,2,1),imshow(src),title('原图')

%用ostu方法获取二值化阈值,进行二值化并进行显示
level=graythresh(src);
bw=im2bw(src,level);
subplot(2,2,2),imshow(bw),title('二值图像')

%运用开操作消去噪点
se = strel('disk',2);
openbw=imopen(bw,se);%对白色点而言
subplot(2,2,3),imshow(openbw),title('开运算后的效果图')

%获取连通区域,并进行显示
% L = bwlabel(openbw,8);
[L,num] = bwlabel(openbw,8);
RGB = label2rgb(L);
subplot(2,2,4),imshow(RGB),title('用rgb颜色标记不同区域')

%获取区域的'basic'属性, 'Area', 'Centroid', and 'BoundingBox' 
% stats = regionprops(openbw, 'basic');
 stats = regionprops(openbw, 'BoundingBox' ,'Area','Centroid' ,'PixelList' ); %统计白色的连通区域
centroids = cat(1, stats.Centroid);

%%
noiseArea=100;
figure,imshow(openbw),title('2')  
hold on
for i=1:size(stats)
    imshow(openbw)
    rectangle('Position',[stats(i).BoundingBox],'LineWidth',2,'LineStyle','--','EdgeColor','r'),
    plot(centroids(i,1), centroids(i,2), 'b*');             %每个连通区域的重心位置
    area = stats(i).Area;                                   %连通区域的面积
    if area<noiseArea                                       %若当前连通区域面积小于噪声点的面积,则该区域设置为0
        pointList = stats(i).PixelList;                     %每个连通区域的像素位置
        rIndex=pointList(:,2);cIndex=pointList(:,1);
        pointList = stats(i).PixelList;                     %连通区域的像素坐标
        openbw(rIndex,cIndex)=0;                            %连通区域的面积不足100,置为背景颜色
    end
    pause(1);
    saveas(gcf,sprintf('img/%d',i),'jpg')                   %保存图片
end
hold off





2018-11-07 22:35:33 Godsolve 阅读数 3601
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4187 人正在学习 去看看 佟刚

连通区域(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;
}



2018-07-06 16:01:34 qq_34447388 阅读数 5866
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4187 人正在学习 去看看 佟刚

转自: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

2019-10-21 21:39:04 Hazel928 阅读数 65
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4187 人正在学习 去看看 佟刚
I= imread('pic3.jpg');
I=rgb2gray(I);
figure(1);
imshow(I);
I=imbinarize(I);
[L, num] = bwlabel(I);
STATS1=regionprops(L,'Perimeter'); 
ahe=size(STATS1);
figure(2);
imshow(I);
m1=ahe(1,1);
m=zeros(2,m1); 
for i=1:m1
 % 计算目标区域中心,用于显示编号的位置
   [p,q]=find(L==i);
    temp=[p,q]; 
   [x,y]=size(temp);
   m(1,i)=sum(p)/x;
   m(2,i)=sum(q)/x;
end
for i=1:m1
      figure(2);
      text(m(2,i),m(1,i),int2str(i),'color','red')
end
L(L~=3&L~=2)=0; %%这边进行区域的选择,例如只保留2、3.

————————————————
版权声明:本文为CSDN博主「Literature668」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/Literature668/article/details/51187475

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