数字图像处理- chap7PPT学习课件

第七章图像分割,讲解内容1.图像分割的概念与方法分类2.边缘检测3.Hough变换检测法4.区域分割5.区域生长6.分裂合并法目的1.掌握图像分割的概念和边缘检测的原理与方法2.掌握Hough变换检测直线原理,了解Hough变换检测曲线方法；3.掌握最简单图像区域分割,了解区域生长和分裂合并法,1,7.1概述,图像分析的概念对图像中感兴趣的目标进行检测和测量，以获得它们的客观信息，从而建立对图像的描述图像分析系统的基本构成,预处理,图像分割,特征提取,对象识别,2,7.1概述,图像分析的步骤把图像分割成不同的区域或把不同的对象分开找出分开的各区域的特征识别图像中要找的对象或对图像进行分类对不同区域进行描述或寻找出不同区域的相互联系，进而找出相似结构或将相关区域连成一个有意义的结构,3,7.1概述,图像分割的概念把图像分成互不重叠的区域并提取感兴趣目标的技术,4,图像分割的定义:令集合R代表整个图像区域，对R的分割可看作将R分成N个满足以下五个条件的非空子集（子区域）R1，R2，RN：；对所有的i和j，ij，有RiRj=；对i=1,2,N，有P(Ri)=TRUE；对ij,有P(RiRj)=FALSE；对i=1,2,N，Ri是连通的区域。其中P(Ri)是对所有在集合Ri中元素的逻辑谓词,代表空集。,5,7.1概述,图像分割的基本策略分割算法基于灰度值的两个基本特性：不连续性和相似性检测图像像素灰度级的不连续性，找到点、线（宽度为1）、边（不定宽度）。先找边，后确定区域。,6,7.1概述,图像分割的基本策略检测图像像素的灰度值的相似性，通过选择阈值，找到灰度值相似的区域，区域的外轮廓就是对象的边,7,7.1概述,图像分割的方法基于边缘的分割方法先提取区域边界，再确定边界限定的区域。区域分割确定每个像素的归属区域，从而形成一个区域图。区域生长将属性接近的连通像素聚集成区域分裂合并分割综合利用前两种方法，既存在图像的划分，又有图像的合并。,8,分割对象,分割对象,9,7.2边缘检测算子,边缘的定义：图像中像素灰度有阶跃变化或屋顶变化的那些像素的集合边缘的分类阶跃状屋顶状,10,阶跃状,屋顶状,11,12,7.2边缘检测算子,基本思想：计算局部微分算子,一阶微分,截面图,边界图像,13,7.2边缘检测算子,一阶微分：用梯度算子来计算特点：对于亮的边，边的变化起点是正的，结束是负的（值由大-小）。对于暗边，结论相反（值由小-大）。常数部分为零。用途：用于检测图像中边的存在,14,7.2边缘检测算子,二阶微分：通过拉普拉斯来计算特点：二阶微分在亮的一边是负的，在暗的一边是正的。常数部分为零。用途：1）二次导数的符号，用于确定边上的像素是在亮的一边，还是暗的一边。2）0跨越，确定边的准确位置,15,7.2边缘检测算子,几种常用的边缘检测算子梯度算子Roberts算子Prewitt算子Sobel算子Kirsch算子Laplacian算子Marr算子,16,梯度算子,函数f(x,y)在(x,y)处的梯度为一个向量：f=f/x,f/y计算这个向量的大小为：G=(f/x)2+(f/y)21/2近似为:G|fx|+|fy|或Gmax(|fx|,|fy|)梯度的方向角为：(x,y)=tan-1(fy/fx)可用下图所示的模板表示,17,为了检测边缘点，选取适当的阈值T，对梯度图像进行二值化，则有：这样形成了一幅边缘二值图像g(x,y)特点：仅计算相邻像素的灰度差，对噪声比较敏感，无法抑止噪声的影响。,18,Roberts算子,公式：模板：特点：与梯度算子检测边缘的方法类似，对噪声敏感，但效果较梯度算子略好,19,Prewitt算子,公式模板：特点：在检测边缘的同时，能抑止噪声的影响,20,Sobel算子,公式模板特点：对4邻域采用带权方法计算差分能进一步抑止噪声但检测的边缘较宽,21,Sobel算子,Sobel梯度算子的使用与分析1.直接计算y、x可以检测到边的存在，以及从暗到亮，从亮到暗的变化2.仅计算|x|，产生最强的响应是正交于x轴的边；|y|则是正交于y轴的边。3.由于微分增强了噪音，平滑效果是Sobel算子特别引人注意的特性,22,Kirsch算子（方向算子）,模板,23,特点在计算边缘强度的同时可以得到边缘的方向各方向间的夹角为45分析取其中最大的值作为边缘强度，而将与之对应的方向作为边缘方向；如果取最大值的绝对值为边缘强度，并用考虑最大值符号的方法来确定相应的边缘方向，则考虑到各模板的对称性，只要有前四个模板就可以了。,24,Nevitia算子,25,拉普拉斯算子,定义：二维函数f(x,y)的拉普拉斯是一个二阶的微分定义为：2f=2f/x2,2f/y2离散形式：模板：可以用多种方式被表示为数字形式。对于一个3x3的区域，经验上被推荐最多的形式是：,26,拉普拉斯算子,定义数字形式的拉普拉斯的基本要求是，作用于中心像素的系数是一个负数，而且其周围像素的系数为正数，系数之和必为0。,27,拉普拉斯算子,拉普拉斯算子的分析：优点：各向同性、线性和位移不变的；对细线和孤立点检测效果较好。缺点：对噪音的敏感，对噪声有双倍加强作用；不能检测出边的方向；常产生双像素的边缘。,由于梯度算子和Laplace算子都对噪声敏感，因此一般在用它们检测边缘前要先对图像进行平滑。,28,Marr算子,Marr算子是在Laplacian算子的基础上实现的，它得益于对人的视觉机理的研究，有一定的生物学和生理学意义。由于Laplacian算子对噪声比较敏感，为了减少噪声影响，可先对图像进行平滑，然后再用Laplacian算子检测边缘。平滑函数应能反映不同远近的周围点对给定像素具有不同的平滑作用，因此，平滑函数采用正态分布的高斯函数，即：,29,其中是方差。用h(x,y)对图像f(x,y)的平滑可表示为：*代表卷积。令r是离原点的径向距离，即r2=x2+y2。对图像g(x,y)采用Laplacian算子进行边缘检测，可得：这样，利用二阶导数算子过零点的性质，可确定图像中阶跃边缘的位置。称为高斯拉普拉斯滤波算子，也称为LOG滤波器，或“墨西哥草帽”。,Marr算子,30,一维LOG函数及其变换函数,二维LOG函数,Marr算子,31,由于的平滑性质能减少噪声的影响，所以当边缘模糊或噪声较大时，利用检测过零点能提供较可靠的边缘位置。在该算子中，的选择很重要，小时边缘位置精度高，但边缘细节变化多；大时平滑作用大，但细节损失大，边缘点定位精度低。应根据噪声水平和边缘点定位精度要求适当选取。下面是10时，Marr算子的模板：,Marr算子,32,33,(a)原图(b)2h结果(c)正值为黑，负值为白(d)过零点,利用2h检测过零点,34,曲面拟合法,出发点基于差分检测图像边缘的算子往往对噪声敏感。因此对一些噪声比较严重的图像就难以取得满意的效果。若用平面或高阶曲面来拟合图像中某一小区域的灰度表面，求这个拟合平面或曲面的外法线方向的微分或二阶微分检测边缘，可减少噪声影响。四点拟合灰度表面法用一平面p(x,y)=ax+by+c来拟合空间四邻像素的灰度值f(x,y)、f(x,y+1)、f(x+1,y)、f(x+1,y+1)。定义均方差为：,35,按均方差最小准则,令可解出参数a,b,c。可推导出：按梯度的定义，由平面p(x,y)=ax+by+c的偏导数很容易求得梯度。a为两行像元平均值的差分，b为两列像元平均值的差分。,36,这种运算可简化为模板求卷积进行，计算a和b对应的模板如下：,特点其过程是求平均后再求差分，因而对噪声有抑制作用。,37,梯度算子,Roberts算子,Prewitt算子,Sobel算子,Kirsch算子,原始图像,例子,38,Laplacian算子,Marr算子,曲面拟合法,39,例子,梯度算子,Roberts算子,Prewitt算子,Sobel算子,Kirsch算子,原始图像,40,Laplacian算子,Marr算子,曲面拟合法,41,线的检测,通过比较典型模板的计算值，确定一个点是否在某个方向的线上,42,线的检测,R1=-6+30=24R2=-14+14=0R3=-14+14=0R4=-14+14=0,43,7.3边缘跟踪,出发点由于噪音的原因，边界的特征很少能够被完整地描述，在亮度不一致的地方会中断。因此典型的边检测算法后面总要跟随着连接过程和其它边界检测过程，用来归整边像素，成为有意义的边。,44,边缘跟踪的概念将检测的边缘点连接成线就是边缘跟踪线是图像的一种中层符号描述由边缘形成线特征的两个过程可构成线特征的边缘提取将边缘连接成线连接边缘的方法光栅跟踪全向跟踪,45,光栅扫描跟踪,概念是一种采用电视光栅行扫描顺序，结合门限检测，对遇到的像素进行分析，从而确定是否为边缘的跟踪方法。,46,光栅扫描跟踪,具体步骤：(1)确定一个比较高的阈值d，把高于该阈值的像素作为对象点。称该阈值为“检测阈值”。(2)用检测阈值d对图像第一行像素进行检测，凡超过d的点都接受为对象点，并作为下一步跟踪的起始点。(3)选取一个比较低的阈值作为跟踪阈值，该阈值可以根据不同准则来选择。例如，取相邻对象点之灰度差的最大值作为跟踪阈值，有时还利用其他参考准则，如梯度方向、对比度等。(4)确定跟踪邻域。取像素(i，j)的下一行像素(i+1，j-1)，(i+1，j)，(i+1，j+1)为跟踪邻域。,47,光栅扫描跟踪,(5)扫描下一行像素，凡和上一行已检测出来的对像点相邻接的像素，其灰度差小于等于跟踪阈值的，都接受为对象点，反之去除。(6)对于已检测出的某一对象点，如果在下一行跟踪领域中，没有任何一个像素被接受为对象点，那么，这一条曲线的跟踪便可结束。如果同时有两个，甚至三个邻域点均被接受为对象点，则说明曲线发生分支，跟踪将对各分支同时进行。如果若干分支曲线合并成一条曲线，则跟踪可集中于一条曲线上进行。一曲线跟踪结束后，采用类似上述步骤从第一行的其他检出点开始下一条曲线的跟踪。,48,光栅扫描跟踪,(7)对于未被接受为对象点的其他各行像素，再次用检测阈值进行检测，并以新检出的点为起始点，重新使用跟踪阈值程序，以检测出不是从第一行开始的其他曲线。(8)当扫描完最后一行时，跟踪便可结束。,49,光栅扫描跟踪,50,光栅扫描跟踪,由结果可以看出，本例原图像中存在着三条曲线，两条从顶端开始，一条从中间开始。然而，如果不用跟踪法，只用一种阈值d或t检测均不能得到满意的结果。,51,光栅扫描跟踪,检测和跟踪所选择的特征可以不是灰度级，而是其他反映局部性质的量，例如对比度、梯度等。此外，每个点所对应的邻域也可以取其他的定义，不一定是紧邻的下一行像素，稍远一些的领域也许对于弥合曲线的间隙更有好处。跟踪准则也可以不仅仅针对每个已检测出的点，而是针对已检出的一组点。这时，可以对先后检出的点赋予不同的权，如后检出的点给以较大的权，而早先检出的点赋予相对小一些的权，利用被检测点性质和已检出点性质的加权均值进行比较，以决定接收或拒绝。总之，应根据具体问题灵活加以运用。,52,光栅扫描跟踪,光栅扫描跟踪和扫描方向有关，因此最好沿其他方向再跟踪一次，例如逆向跟踪，并将两种跟踪的结合综合起来能得到更好的结果。另外，若边缘和光栅扫描方向平行时效果不好，则最好在垂直扫描方向跟踪一次，它相当于把图像转置90o后再进行光栅扫描跟踪。,53,全向跟踪,如果能使跟踪方向不仅局限于逐行(或列)的光栅式扫描，譬如说，在从上而下(或自左而右)的扫描过程中，也可以向上(或向左)跟踪，那么就会克服光栅跟踪依赖于扫描方向的缺点。这可以通过定义不同邻域的方法来实现。同样，如果我们选取的跟踪准则能够辨别远非紧邻的像素，那么光栅跟踪会漏掉平行于扫描方向曲线的缺点也能得到适当地克服。全向跟踪就是跟踪方向可以是任意方向，并且有足够大的跟踪距离的跟踪方法。显然，全向跟踪是改变了邻域定义和跟踪准则的一种光栅跟踪法。,54,全向跟踪,具体步骤：(1)按光栅扫描方式对图像进行扫描，用检测阈值找出一个起始跟踪的流动点(沿被检测曲线流动)。(2)选取一个适当的、能进行全向跟踪的邻域定义(例如八邻域)和一个适当的跟踪准则(例如灰度阈值、对比度和相对流动点的距离等)，对流动点进行跟踪。在跟踪过程中，若：,55,全向跟踪,(a)遇到了分支点或者若干曲线的交点(即同时有几个点都跟踪一个流动点)，则先取其中和当前流动点性质最接近的作为新的流动点，继续进行跟踪。而把其余诸点存储起来，以备后面继续跟踪。如果在跟踪过程中又遇到了新的分支或交叉点，则重复上面的处理步骤。当按照跟踪准则没有未被检测过的点可接受为对象点时，一个分支曲线的跟踪便已结束。(b)在一个分支曲线跟踪完毕以后，回到最近的一个分支点处，取出另一个性质最接近该分支点的像素作为新的流动点，重复上述跟踪程序。,56,全向跟踪,(c)当全部分支点处的全部待跟踪点均已跟踪完毕，便返回第一步，继续扫描，以选取新的流动点(不应是已接收为对象的点)。(3)当整幅图像扫描完成时，跟踪程序便结束。,57,全向跟踪,特点：全向跟踪改进了光栅扫描跟踪法，跟踪时把初始点的八邻点全部考虑进行跟踪。,58,7.4Hough变换检测法,问题的提出Hough变换的基本思想算法实现Hough变换的扩展,59,7.4Hough变换检测法,问题的提出在找出边界点集之后，需要连接，形成完整的边界图形描述,60,基本思想对于边界上的n个点的点集，找出共线的点集和直线方程。对于直角坐标系中的一条直线l，可用、来表示该直线，且直线方程为：其中，为原点到该直线的垂直距离，为垂线与x轴的夹角，这条直线是唯一的。构造一个参数的平面，从而有如下结论：,7.4Hough变换检测法,对应一条直线,直角坐标系中的一条直线对应极坐标系中的一点，这种线到点的变换就是Hough变换,61,7.4Hough变换检测法,基本思想,62,7.4Hough变换检测法,算法实现：使用交点累加器，或交点统计直方图，找出相交线段最多的参数空间的点，然后找出该点对应的xy平面的直线线段。,63,算法步骤：1在、的极值范围内对其分别进行m，n等分，设一个二维数组的下标与i、j的取值对应；2对图像上的所有边缘点作Hough变换，求每个点在j(j0，1，n)Hough变换后的i，判断(i、j)与哪个数组元素对应，则让该数组元素值加1；3比较数组元素值的大小，最大值所对应的(i、j)就是这些共线点对应的直线方程的参数。,64,7.4Hough变换检测法,算法特点：对、量化过粗，直线参数就不精确，过细则计算量增加。因此，对、量化要兼顾参数量化精度和计算量。Hough变换检测直线的抗噪性能强，能将断开的边缘连接起来。此外Hough变换也可用来检测曲线。,65,7.4Hough变换检测法,Hough变换的扩展Hough变换不只对直线，也可以用于圆：（xa）2+(y-b)2=R2这时需要三个参数(a,b,R)的参数空间。如像找直线那样直接计算，计算量增大，不合适。,66,解决途径若已知圆的边缘元(当然图中还有其它非圆的边沿点混在一起)，而且边缘方向已知，则可减少一维处理，把上式对x取导数，有这表示参数a和b不独立，只需用二个参数(例如a和R)组成参数空间，计算量就缩减很多。,67,对于椭圆设椭圆方程为取导数有只有三个独立参数。只需要从(a,b,x0,y0)中选择三个参数，进行检测。,68,对于任意曲线在形状物中可确定一个任意点(xc,yc)为参考点，从边界上任一点(x,y)到参考点(xc,yc)的长度为r,它是的函数，是(x,y)边界点上的梯度方向。通常是把r表为的参数r(),(xc,yc)到边界连线的角度为()，则(xc,yc)应满足下式：设某已知特殊边界R，可按的大小列成一个二维表格，即i(a,r)表，i确定后可查出a和r，经上式计算可得到(xc,yc)。,69,对已知形状建立了R表格后，开辟一个二维存储区，对未知图像各点都来查已建立的R表，然后计算(xc,yc)，若未知图像各点计算出的(xc,yc)很集中，就表示已找到该形状的边界。集中的程度就是找最大值。具体步骤如下：(1)对将要找寻的某物边界建立一R表，这是一个二维表，以i的步进值求r和；(2)在需要判断被测图像中有无已知某物时，也可对该图某物各点在内存中建立一存储区，存储内容是累加的。把xc,yc从最小到最大用步进表示，并作为地址，记作A(xcminmax,ycminmax),存储阵列内容初始化为零；,70,(3)对图像边界上每一点(xi,yi)，计算(x)，查原来的R计算(xc,yc)，；(4)使相应的存储阵列A(xc,yc)加1，即(5)在阵列中找一最大值，就找出了图像中符合要找的某物体边界。,71,3.2.4图像分割:阈值分割法,阈值分割法通过交互方式得到阈值通过直方图得到阈值通过边界特性选择阈值简单全局阈值分割分割连通区域基于多个变量的阈值,72,3.2.4图像分割:阈值分割法,阈值分割法阈值分割法的基本思想：确定一个合适的阈值T（阈值选定的好坏是此方法成败的关键）。将大于等于阈值的像素作为物体或背景，生成一个二值图像。Iff(x,y)Tset255Elseset0在四邻域中有背景的像素，既是边界像素。,0,255,255,0,255,0,255,255,255,73,3.2.4图像分割:阈值分割法,阈值分割法阈值分割法的特点：适用于物体与背景有较强对比的情况，重要的是背景或物体的灰度比较单一。（可通过先求背景，然后求反得到物体）这种方法总可以得到封闭且连通区域的边界。,灰度值,f(x0,y0),T,74,3.2.4图像分割:阈值分割法,通过交互方式得到阈值基本思想：在通过交互方式下，得到对象（或背景）的灰度值，比得到阈值T容易得多。假设：对象的灰度值(也称样点值)为f(x0,y0),且：T=f(x0,y0)R有：f(x,y)Tf(x,y)f(x0,y0)R|f(x,y)f(x0,y0)|R其中R是容忍度，可通过试探获得。,75,3.2.4图像分割:阈值分割法,通过交互方式得到阈值实施方法：（1）通过光标获得样点值f(x0,y0)（2）选取容忍度R（3）if|f(x,y)f(x0,y0)|Rset255elseset0,76,3.2.4图像分割:阈值分割法,通过直方图得到阈值基本思想边界上的点的灰度值出现次数较少,T,77,3.2.4图像分割:阈值分割法,通过直方图得到阈值取值的方法：取直方图谷底，为最小值的灰度值为阈值T缺点：会受到噪音的干扰，最小值不是预期的阈值，而偏离期望的值；改进：取两个峰值之间某个固定位置，如中间位置上。由于峰值代表的是区域内外的典型值，一般情况下，比选谷底更可靠，可排除噪音的干扰,78,3.2.4图像分割:阈值分割法,通过直方图得到阈值,T,79,3.2.4图像分割:阈值分割法,通过直方图得到阈值对噪音的处理对直方图进行平滑处理，如最小二乘法，等不过点插值。,80,3.2.4图像分割:阈值分割法,通过边界特性选择阈值基本思想：如果直方图的各个波峰很高、很窄、对称，且被很深的波谷分开时，有利于选择阈值。为了改善直方图的波峰形状，我们只把区域边缘的像素绘入直方图，而不考虑区域中间的像素。用微分算子，处理图像，使图像只剩下边界中心两边的值。,81,3.2.4图像分割:阈值分割法,通过边界特性选择阈值基本思想：这种方法有以下优点：1)在前景和背景所占区域面积差别很大时，不会造一个灰度级的波峰过高，而另一个过低2)边缘上的点在区域内还是区域外的概率是相等的，因此可以增加波峰的对称性3)基于梯度和拉普拉斯算子选择的像素，可以增加波峰的高度,82,3.2.4图像分割:阈值分割法,通过边界特性选择阈值算法的实现：1）对图像进行梯度计算，得到梯度图像。2）得到梯度值最大的那一部分（比如10%）的像素直方图3）通过直方图的谷底，得到阈值T。如果用拉普拉斯算子，不通过直方图，直接得到阈值，方法是使用拉普拉斯算子过滤图像，将0跨越点对应的灰度值为阈值T.,83,3.2.4图像分割:阈值分割法,简单全局阈值分割基本思想：用前述方法获得阈值T，并产生一个二值图，区分出前景对象和背景算法实现：规定一个阈值T，逐行扫描图像。凡灰度级大于T的，颜色置为255；凡灰度级小于T的，颜色置为0。适用场合：明度图像是可以控制的情况，例如用于工业监测系统中。,84,3.2.4图像分割:阈值分割法,分割连通区域基本思想：用前述方法获得阈值T，并产生一个二值图，区分出单独的连通前景对象和背景区域算法实现：规定一个阈值T，上下左右4个方向进行逐行扫描图像凡灰度级大于T的，颜色置为255；凡灰度级小于T的，颜色置为0。,85,3.2.4图像分割:阈值分割法,分割连通区域适用场合：印前等。先左后右，先上半部分、后下半部分,86,3.2.4图像分割:阈值分割法,基于多个变量的阈值基本思想：把前面的方法扩展到多维空间，则寻找波谷的过程，变为寻找点簇的过程。算法实现：各维分量波谷之间进行逻辑与运算，从波谷重合的点，得到实际的阈值T。应用场合：有多个分量的颜色模型，如RGB模型、CMYK模型、HSI模型,87,3.2.5图像分割:面向区域的分割,面向区域的分割基本概念通过像素集合的区域增长区域分裂与合并,88,3.2.5图像分割:面向区域的分割,基本概念目标：将区域R划分为若干个子区域R1,R2,Rn，这些子区域满足5个条件：1)完备性：2)连通性：每个Ri都是一个连通区域3)独立性：对于任意ij，RiRj=,89,3.2.5图像分割:面向区域的分割,基本概念4)单一性：每个区域内的灰度级相等，P（Ri）=TRUE，i=1,2,n5)互斥性：任两个区域的灰度级不等，P（RiRj）=FALSE，ij,90,3.2.5图像分割:面向区域的分割,通过像素集合的区域增长算法实现：1）根据图像的不同应用选择一个或一组种子，它或者是最亮或最暗的点，或者是位于点簇中心的点。2）选择一个描述符（条件）3）从该种子开始向外扩张，首先把种子像素加入集合，然后不断将与集合中各个像素连通、且满足描述符的像素加入集合4）上一过程进行到不再有满足条件的新结点加入集合为止。,91,3.2.5图像分割:面向区域的分割,通过像素集合的区域增长算法实现：,区域A,区域B,种子像素,种子像素,92,3.2.5图像分割:面向区域的分割,区域分裂与合并算法实现：1）对于图像中灰度级不同的区域，均分为四个子区域。2）如果相邻的子区域所有像素的灰度级相同，则将其合并。3）反复进行上两步操作，直至不再有新的分裂与合并为止。,93,3.2.5图像分割:面向区域的分割,区域分裂与合并算法实现：,94,3.2.5图像分割:面向区域的分割,区域分裂与合并算法实现：实际应用中还可作以下修改：P(Ri)的定义为：1）区域内多于80%的像素满足不等式|zj-mi|=2i，其中：zj是区域Ri中第j个点的灰度级，mi是该区域的平均灰度级，i是区域的灰度级的标准方差。2）当P(Ri)=TRUE时，将区域内所有像素的灰度级置为mi。,95,3.2.6图像分割:数学形态学图像处理,数学形态学图像处理基本概念腐蚀与膨胀开-闭运算变体,96,3.2.6图像分割:数学形态学图像处理,基本概念结构元素与图像进行逻辑运算，产生新的图像的图像处理方法。集合概念上