任明武_数字图象处理第4章_图像分割(imagesegmentation)

2002,Ver1.0任明武，南京理工大学计算机系74第四章图象分割(ImageSegmentation)定义：所谓图象分割就是按一定的规则将图象划分成若干有意义的区域。研究重点：(1)按什么样的规则。(2)什么叫有意义。一般是符合特定场合的应用的才称为有意义。因此图像分割是个病态问题(ill-posedproblem)，一种方法可能非常符合甲的需求，但与乙的需求矛盾。说明：规则和需求的多样性导致了图像分割方法的多样性，到目前为止，有人说有1800多种方法，可见其方法之多。同时也说明不存在通用的图像分割方法。在本章中，我们讲述边缘提取和基于直方图的图像分割，希望大家能够掌握一些基本的概念和处理问题的手段。2002,Ver1.0任明武，南京理工大学计算机系754.1边缘检测(EdgeExtraction,Edgedetection)定义：边缘点是指其周围象素的灰度有阶跃变化(stepedge)或屋顶状变化(roofedge)的象素、常存在于目标与背景之间、目标与目标之间、目标与其影子之间。分析手段：因为灰度的变化，可以反映为导数；因此，根据边缘的形状，可以通过求导的方法来寻求边缘。边缘的参数包括：边缘强度(edgeintensity)和边缘方向(edgedirection)比如：由此，可以看出求导和边缘检测的关系。窗口中象素的灰度值窗口中象素的梯度值2002,Ver1.0任明武，南京理工大学计算机系76g(i)g(i)ii一阶导数二阶导数极值点屋顶状边缘：一阶导数过零点，二阶导数最小值阶跃边缘：一阶导数最大值，二阶导数过零点2002,Ver1.0任明武，南京理工大学计算机系77说明：在实际应用中，一般仅考虑阶跃边缘，因为只要采样分辨率足够或者说窗口足够小，边缘都可以看成是阶跃边缘。分析手段：边缘是指图象中灰度发生急剧变化的区域。图象灰度的变化情况可以用灰度分布的梯度来反映，给定连续图象f(x,y)，其方向导数在边缘法线方向上取得局部最大值。因此，边缘的检测转化为求f(x,y)在(x,y)处的方向导数问题。f(x,y)沿任意方向r的方向导数为：其中，θ为x轴到方向r的转角。fx和fy为f(x,y)的偏导数。与方向导数有关联的一个概念是函数的梯度，对于平面的每一个点p(x,y)都可定出一个向量(包括幅值和方向)，该向量称为(x,y)处的梯度。向量为：梯度为：可以证明，当方向r与梯度方向一致时，方向导数达到最大值，该最大值即为梯度的模。sincosyxffryyfrxxfrfjyfixfjyfixfyxfgrad),(2002,Ver1.0任明武，南京理工大学计算机系78梯度的模为：x轴到梯度的转角的正切为：因此，(x,y)处的边缘强度取其方向导数的最大值，即梯度的模;边缘方向取x轴到梯度的方向θ。实际上也可以直接从方向导数的公式直接推导得到：22),(yfxfyxfgradxfyftag0rfrf取最大值的条件是0cossinyxff)/(tan)/(tan11xyxyffff或即：得到：22maxyxffgrad2002,Ver1.0任明武，南京理工大学计算机系79注1：对各向同性的说明假设图像f(x,y)的所有导数都存在并且连续，那么在对f(x,y)求导数时只依赖于点(x,y)附近的一个任意小的邻域内的像素的值，因此可以将这种运算认为是位移不变运算。为了能得到图像中间任意方向伸展的边缘，还希望对图像的某种导数运算是各向同性。可以证明偏导数的平方和是各向同性，即：式中(x,y)是某个象素图像旋转前的坐标，(x’,y’)是该向素图像旋转后的坐标。梯度运算符合位移和旋转不变性。注2：数字图像中的导数运算在图象中，导数的计算有两种方式：(1)先将数字图像通过曲面拟合的方法得到连续空间中的描述，然后在连续空间中，自然可以求导。222'2'yfxfyfxf2002,Ver1.0任明武，南京理工大学计算机系80通过研究边缘类型及其导数的表现，可以设计不同的检测算法。下面，我们讲述几种常用的边缘检测算法。(2)用差分代替求导，如下：xf(i,j)=f(i+1,j)-f(i,j)yf(i,j)=f(i,j+1)-f(i,j)αf(i,j)=xf(i,j)cosα+yf(i,j)sinα4.1.1梯度算子(Gradient)定义梯度为：22),(),(),(jiyfjixfjiG若G(i,j)Threshold,则(i,j)点为边缘点。缺点：时间复杂度高。改进：令G(i,j)=|xf(i,j)|+|yf(i,j)|2002,Ver1.0任明武，南京理工大学计算机系81例：11111111111111111888888111111888888111111888888111111111111100000077777000000700007000000700007000000777771000000000000001得到4.1.2罗伯特算子(Roberts)定义为：R(i,j)=max{|f(i,j)-f(i+1,j+1)|,|f(i+1,j)-f(i-1,j+1)|}i,ji+1,ji,j+1i+1,j+1100-101-10例：111111111111111118888881111118888881000007777770000007000070111111888880得到2002,Ver1.0任明武，南京理工大学计算机系824.1.3索伯算子(Sobel)定义为：S(i,j)=|(P3+2*P2+P1)-(P5+2*P6-P7)|+|(P3+2*p4+p5)-(P1+2*P0+P7)|10-120-210-1121000-1-2-1i-1,j-1i,j-1i+1,j-1i-1,ji,ji+1,ji-1,j+1i,j+1i+1,j+1P3P2P1P4i,jP0P5P6P72002,Ver1.0任明武，南京理工大学计算机系83缺点：得到双线宽的边缘，因为该算子涉及到3*3的邻域。优点：(1)加权（距离越近，贡献越大）(2)实质上是平滑去噪，后求差分。在边缘检测可以说是通用模式，即：在用Gradient或Robert等其他算子求边缘象素前，最好先对图象进行平滑，因为噪声的灰度值一样是变化很大。思考1：在图像平滑时，模板中各系数之和1且都不小于0；在边缘检测算子中，各系数之和是0且有正有负。思考2：对图像I使用模板l，等价于对I先使用模板2再使用模板3吗?121-1-2-1I@121@10-1I@模板l模板2模板32002,Ver1.0任明武，南京理工大学计算机系844.1.4方向模板(Prewitt)111-1-1-11-11-11-1111-1-1-111-11-1-10090045013502002,Ver1.0任明武，南京理工大学计算机系854.1.5小结一般性原则：给定图象f(x,y)在两个正交方向H1、H2上的梯度g1(x,y)和g2(x,y)定义如下：则边缘的强度和方向由下式给出：为了加快速度，有时：),(2*),(),(2),(1*),(),(1yxHyxfyxgyxHyxfyxg)),(1),(2tan),().(2),(1),(122yxgyxgyxyxgyxgyxgrad|),(2||),(1||}),(2||,),(1max{|),(yxgyxgyxgyxgyxgrad或2002,Ver1.0任明武，南京理工大学计算机系86OriginalImage(Lena)PrewittImageSobelImage2002,Ver1.0任明武，南京理工大学计算机系87注：PrewittImage和SobelImage都是GradientImage，从中看不到具体的有何明显改进。实际上，GradientImage仅是中间结果，而且各种算子得到的梯度图像相差不大，即可能都不能满足你实际的需要，或直接满足你的需要。这需要在边缘检测完成后，使用相关的约束条件得到目标的位置或尺寸。而梯度图像还需要一个阈值(如何取阈值是一个值得研究的问题)，才能判断一个像素是否是边缘点。4.1.6二阶微分算子前面讲过，对阶跃边缘边缘而言，边缘点处的二阶导数过0点，或二阶导数在边缘点处出现零交叉(Zero-Crossing)，即边缘点两旁的二阶导数异号。因此下面我们讲述基于该原理的边缘点检测，即拉普拉斯(Laplacian)算子。对数字图像的每个象素f(x,y)，取它的二阶导数为关于x轴方向和y轴方向的二阶导数之和，得到：2xf(i,j)+2yf(i,j)=f(i+1,j)+f(i-1,j)+f(i,j+1)+f(i,j-1)-4f(i,j)2002,Ver1.0任明武，南京理工大学计算机系88写成模板形式就是：使用Laplacian，在某种尺度(下面会讲何为尺度)下得到的边缘点0-10-14-10-10-1-1-1-18-1-1-1-1或2002,Ver1.0任明武，南京理工大学计算机系89补充内容1：过零点检测（Marr-Hildreth算子）(马尔-希尔德累思算子)根据图象边缘处的一阶微分（梯度）应该是极值点的事实，图象边缘处的二阶微分应为零，确定过零点的位置要比确定极值点容易得多也比较精确。但是显然二阶微分对噪声更为敏感。算法：为抑制噪声，可先作平滑滤波然后再作二次微分，通常采用高斯函数作平滑滤波，故有LoG(LaplacianofGaussian)算子。在实现时一般用两个不同参数的高斯函数的差DoG（DifferenceofGaussians）对图象作卷积来近似，这样检测出来的边缘点称为f(x,y)的过零点（Zero-crossing）。理论：过零点的理论是Marr,Hildreth提出来的，是计算视觉理论中的有关早期视觉的重要内容。将高斯函数G(x,y;)与图像f(x,y)进行卷积，可以得到一个平滑的图像fs(x,y)，由于感兴趣的是图像的边缘，于是需要对fs(x,y)进行拉普拉斯运算。而图像f(x,y)与高斯函数G(x,y;)相卷积的拉普拉斯运算可以表示为G(x,y;)的拉普拉斯变换与f(x,y)的卷积，因此，有算子如下：2002,Ver1.0任明武，南京理工大学计算机系90);,(),(),(2yxGyxfyxMH)2)(exp(21);,(2222yxyxG))(21exp()12(1);,(222222422222yxyxyGxGyxG其中：根据LOG函数的特点，已经有专用的硬件，使用DOG函数来近似实现LOG函数。即：)2)(exp(21)2)(exp(21),(22222221222121yxyxDOG2002,Ver1.0任明武，南京理工大学计算机系91从工程的观点来看，当时，DOG逼近LOG。另外，在软件实现中，考虑到LOG算子的对称性，可采取分解的方法来提高运算速度，即把一个二维的滤波器分解为独立的行列滤波器。有：6.1/21),(),();,(21122yxHyxHyxG)()(),(2112yhxhyxH)()(),(1221yhxhyxH)2exp()1()(22221xxkxh)2exp()(222xkxh)2exp()(222ykyh)2exp()1()(22221yykyh其中：2002,Ver1.0任明武，南京理工大学计算机系92高斯函数的标准差是一个尺度参数，它越小，则相当于邻域越小，即在一个很小的局部范围内平滑，边缘定位越准确；反之，则表示在较大的范围内平滑，边缘定位越不准。LOG算子的优点是：边缘定位精度高，连续性好；缺点是：在抗干扰和检测出复杂形状的边缘之间仍存在较尖锐的矛盾，平