网络多媒体技术复习第4章图像分割

1,第4章图像分割,多媒体信息处理,2,主要内容,图像分割图像分割引言间断检测边缘连接和边界检测门限处理基于区域的分割,3,图像分割引言,计算机处理图像的两个目的产生更适合人观察和识别的图像由计算机自动识别和理解图像图像分割是图像识别和图像理解的基础,图像分析系统的基本构成如下图：,在该系统中，图像的增强和恢复可以看作预处理，其输入、输出均是图像，它是传统的图像处理的内容。而图像分割、特征提取及结构分析等称为图像识别，其输入是图像，输出是描述或解释。,图像分割引言,5,图像分割引言,图像分割的定义图像分割是把图像分割成互不交叠的有意义区域，以便进一步的分析，分开的区域一般是图像中我们感兴趣的目标图像分割是基于目标或区域的特征进行的每个目标或区域由于某些特征的不同与其它区域区别开来，边缘、纹理、形状、颜色等都是重要的特征,6,图像分割引言,图像分割算法一般是基于亮度值的不连续性和相似性不连续性是基于亮度的不连续变化分割图像，称为基于边界的技术，如边缘检测相似性是指根据不同的准则将图像分割成相似的区域，称为基于区域的技术，如阈值分割、区域生长、区域分裂和合并,图像分割的目的把图像分解成构成它的部件和对象；有选择性地定位感兴趣对象在图像中的位置和范围。,从简到难，逐级分割控制背景环境，降低分割难度注意力集中在感兴趣的对象，缩小不相干图像成分的干扰。,图像分割的基本思路,提取轮廓,车牌定位,车牌识别,图像分割的基本策略：,把像素按灰度划分到各个物体对应的区域中去；,确定存在于区域间的边界；,先确定边缘像素点，然后将它们连接起来构成所需的边界；,4.图像分割的方法1)基于边缘的分割方法:先提取区域边界，再确定边界限定的区域。2)区域分割:确定每个像素的归属区域，从而形成一个区域图。3)区域生长:将属性接近的连通像素聚集成区域。4)分裂合并分割:综合利用前两种方法，既存在图像的划分，又有图像的合并。,11,图像分割引言,12,间断检测,间断检测是基于图像像素灰度值的不连续性进行图像分割点检测线检测边界检测寻找间断最一般的方法是模板检测,13,间断检测,点检测使用空域的高通滤波器来检测孤立点，如果，则认为在模板中心的位置检测到一个点，T是非负门限孤立点：该点的灰度级与其背景的差异相当大，并且它所在的位置是一个均匀的或者近似均匀的区域基本思想：如果一个孤立点与它周围的点很不相同，则很容易被上述模板检测到。在灰度级为常数的区域，模板响应R为0,14,间断检测,点检测R=(-1*10*8+8*100)/9=720/9=80可以设置阈值T=50若R=0，则说明检测点与周围点像素值相同若RT，则说明检测点与周围点像素值非常的不同，为孤立点,10,10,10,10,100,10,10,10,10,图像,-1,-1,-1,-1,8,-1,-1,-1,-1,模板,15,间断检测,16,间断检测,线检测第一个模板对水平方向的线条（单像素宽）有更强的响应第二个模板对于45度方向线有最佳响应第三个模板对垂直线有最佳响应第四个模板对于-45度线有最佳响应每个模板系数相加总和为0，保证了在灰度级恒定的区域，模板响应为0,17,间断检测,线检测通过典型模板计算值的比较，确定一个点是否在某个方向的线上，以及当前图像的线性特征用四种模板分别计算R1=24R2=0R3=0R4=0,18,间断检测,图一为原图像，图二为使用负45度检测器处理后的结果（取绝对值），图三为满足阈值条件的所有点，阈值条件为大于等于原图像中的最大值,19,间断检测,边缘检测边缘是位于两个区域的边界线上的相连像素的集合边缘可以通过计算局部微分算子来检测一阶导数：通过梯度来计算二阶导数：通过拉普拉斯算子来计算,理想数字边缘,该模型生成的图像边缘是一组相连的的象素集合（垂直方向上），每个象素都处在灰度跃变的一个垂直的台阶上。,间断检测,斜坡的斜率与边缘的模糊程度成正比。,斜坡数字边缘,间断检测,可用一阶导数的幅度值来检测边缘的存在。,二阶导数在一阶导数的阶跃上升区有一个向上的脉冲，而在一阶导数的阶跃下降区有一个向下的脉冲。这2个阶跃之间的过零点正对应原图像中的边缘位置。,一阶导数的幅度峰值对应边缘位置，二阶导数的过零点对应边缘位置，二阶导数在过零点附近的符号确定边缘象素在图像边缘的暗区或明区。,间断检测,23,间断检测,左图第一列为原图像及其灰度级第二列为一阶导数的图像显示及其值第三列为二阶导数的图像显示及其值从上向下的四行分别是无噪声、轻微噪声、中等噪声和严重噪声的情况一阶、二阶导数对噪声比较敏感，因此图像受到噪声的干扰时，通过求导数不能准确的检测边缘,间断检测,上图中第1列的图像分割显示了分割左右黑白区域的4个斜坡边缘的特写图。左上角的图像分割是无噪声的.第1列的其他3幅图分别被附加的零均值且标准差伟0.1,1.0和10.0灰度级的高斯噪声污染。每幅图像下面显示的图是穿过图像的水平扫描线的灰度级剖面线。第2列图像是左边图像的一阶导数图像,在恒定的黑色和白色区域导数为零。这是在导数图像中的两个黑色区域。不变化的斜坡导数是常量,大小等于斜坡的斜率。这个在导数图像中不变的区域用灰色表示。当我们将中心列向下移时,导数变得与无噪声情况时越来越不相同。这些例子很好地说明了导数对于噪声的敏感性。第3列图像显示二阶导数对于噪声甚至更为敏感。二阶导数图像和剖面线清楚地说明了,实际检测这些图像中为正和为负的分量很困难,而这些分量是在边缘检测中非常有用的二阶导数特性。,24,25,间断检测,边缘检测梯度算子函数f(x,y)在(x,y)处的梯度为一个向量：向量的大小：近似为：向量的方向,边缘在点(x,y)处的方向与此点的梯度向量方向垂直,26,间断检测,边缘检测Robert交叉梯度算子特点：与梯度算子检测边缘的方法类似，对噪声敏感，但效果较梯度算子略好。,27,间断检测,边缘检测Prewitt算子特点：在检测边缘的同时，能抑止噪声的影响.,28,间断检测,边缘检测Sobel算子特点：对4邻域采用带权方法计算差分；能进一步抑止噪声；但检测的边缘较宽。,Sobel算子与Prewitt算子相比有较好的噪声抑制功能,29,间断检测,边缘检测用于检测对角线方向上突变的Prewitt和Sobel模板,30,间断检测,图a原图像，图b为x方向梯度图Gx，图c为y方向梯度图Gy，图d为完整梯度图Gx+Gy,间断检测,上图说明了梯度的两个分量|Gx|和|Gy|的响应与这两个分量之和生成的梯度图像。(b)和(c)中两个分量的方向性是很明显的。特别注意,(b)中屋瓦,砖块的水平接缝和窗户的水平分段的图像是非常清晰的.与之形成对照的是(c)中表现出的垂直部分,诸如墙附近的拐角,窗户的垂直部分,砖块的垂直接缝和图片右侧的街灯柱子。原图分辨率相当高(12001600像素),且在图片摄取的距离上,墙砖对图像细节的影响仍十分显著。这种程度的细节通常是不符合要求的。减少这种影响的一种方法是对图像进行平滑处理。,31,32,间断检测,图e经过5X5均值滤波后的原图像，图f为x方向梯度图Gx，图g为y方向梯度图Gy，图h为完整梯度图Gx+Gy,间断检测,图像e为对原图像a使用了一个55的均值滤波器进行平滑处理后结果。现在每个模板的相应几乎未显示出由砖块造成的影响,得到的结果几乎都是主要的边缘。注意取均值造成所有的边缘相应都被削弱。a-h中明显显示出,水平和垂直Sobel模板对正负450方向边缘的反映几乎一样好。图i和j显示的是对角Sobel模板的绝对响应。在这幅图中,这些模板更强的对角响应是很明显的。两个对角模板对水平和垂直的边缘具有相似的相应,但正如所期望的那样,它们在这些方向上的响应比图(b)和图(c)中显示的Sobel模板在水平和垂直方向上的响应要弱。,33,34,间断检测,图i为使用用于检测45度对角线方向上突变的Sobel模板的结果图j为用于检测负45度对角线方向上突变的Sobel模板,35,间断检测,边缘检测拉普拉斯算子图像函数f(x,y)的拉普拉斯变换为,36,间断检测,边缘检测拉普拉斯算子一般不以其原始形式用于边缘检测的原因是拉普拉斯算子对噪声非常敏感拉普拉斯算子的幅值产生双边缘不能检测边缘的方向拉普拉斯算子在分割中的作用利用它的零交叉性质进行边缘定位确定一个像素在边缘暗的一边还是亮的一边,37,间断检测,边缘检测Laplacian算子和平滑Gaussian滤波器进行结合来进行边缘检测,38,间断检测,边缘检测高斯型拉普拉斯算子高斯函数的目的是对图像进行平滑拉普拉斯算子的目的是提供一幅用零交叉确定边缘位置的图像图像的平滑处理减少了噪声的影响,39,间断检测,LoG检测结果,Sobel算子检测结果,LoG图像阈值分割的结果,零交叉点,40,间断检测,边缘检测拉普拉斯算子和Sobel算子比较缺点边缘由许多闭合环的零交叉点决定零交叉点的计算比较复杂优点零交叉点图像中的边缘比梯度边缘细抑制噪声的能力和抗干扰能力比梯度算子强结论：梯度算子用的更多,41,间断检测,边缘检测边缘检测的Matlab函数BW=edge(I,sobel)BW=edge(I,prewitt)BW=edge(I,roberts)BW=edge(I,log)BW=edge(I,zerocross,thresh,h),间断检测,Canny算子1986年，Canny提出了边缘检测算子应满足以下3个判断准则：信噪比准则，定位精确度准则，单边缘响应准则，并推导出了Canny算子。实现步骤有四个子过程：第一步首先用二维高斯函数的一阶导数对图像进行平滑第二步用22邻域一阶偏导的有限方差来计算平滑后的数据阵列I(x,y)的梯度幅值和梯度方向第三步，为了精确定位边缘，必须细化梯度幅值图像M(i,j)中的屋脊带，只保留幅值局部变化最大的点，这一过程称为非极大值抑制最后在第四步，对经过非极大值抑制的数据阵列N(i,j)分别使用高、低2个阈值h和l分割图像，得到两个阈值边缘图像,42,间断检测,Canny算子的优缺点该算法有较好的抑制噪声的能力，可以较完整的检测出边缘。但比传统边缘微分算子复杂，运算速度慢。另外，Canny算子的双阈值是根据全局特征信息来决定的，这导致了一方面无法消除局部噪声干扰，另一方面又会丢失灰度值变化缓慢的局部边缘。可以通过改进双阈值的选取算法提高Canny算子的边缘检测性能。,43,间断检测,44,间断检测,45,46,边缘连接和边界检测,边缘连接由于噪声、不均匀照明等原因产生边缘间断，使得到的一组像素很少能完整地描绘一条边缘典型的做法是在使用边缘检测算法之后，使用连接过程将边缘像素组合成有意义的边缘局部处理,47,边缘连接和边界检测,局部处理分析图像中每个边缘点(x,y)的一个邻域内的像素，根据某种准则将所有相似点进行连接，由满足该准则的像素连接组成的一条边缘，称为边缘连接，又称为边缘跟踪。连接原则比较两个边缘点梯度算子的响应强度和梯度方向来确定两个点是否属于一条边,48,边缘连接和边界检测,局部处理比较边缘像素的梯度算子的响应强度比较边缘像素的梯度方向比较梯度向量的方向角当梯度值和方向角都是相似的，则点(x,y)，与边点界(x,y)是连接的。,如果,，则点(x,y)与其邻域内的点,如果,，则点(x,y)与其邻域内的点,(x,y)的梯度响应强度相似,(x,y)的梯度方向相似,连接算法步骤,49,1）设定A、T的阈值大小，确定邻域的大小；2）对图像上每一个像素的邻域点进行分析，判断是否需要连接；3）记录像素连接的情况，另开一个空间，给不同的边以不同的标记；4）删除孤立线段，连接断开的线段。,50,边缘连接和边界检测,局部处理如果梯度算子的响应强度和梯度方向都是相似的，则边缘点(x,y)和(x,y)是连接的,边缘连接光栅扫描跟踪,边缘跟踪的方法很多，常见的有光栅跟踪和轮廓跟踪光栅扫描跟踪光栅扫描跟踪是一种采用电视光栅行扫描顺序对遇到的像素进行分析，从而确定是否为边缘的跟踪方法。光栅跟踪方法的基本思想是先利用检测准则确定和接受对象点，然后根据被接受的对象点和跟踪准则确定并接受新的对象点，最后将所有标记为1且相邻的对象点联接起来就得到了检测到的细曲线。,51,边缘连接光栅扫描跟踪,使用光栅跟踪方法，需要遵循下面的三个准则参数准则：需要事先确定检测阈值d、跟踪阈值t，且要求dt；检测准则：对图像逐行扫描，将每一行中灰度值大于或等于检测阈值d的所有点（称为接受对象点）记为1；跟踪准则：设置位于第i行的点(i,j)为已接受的对象点，如果位于第i+1行上的相邻点(i+1,j1)、(i+1,j)和(i+1,j+1)的灰度值大于或等于跟踪阈值t，就将其接受为新的对象点，并记为1。,52,边缘连接光栅扫描跟踪,具体步骤(1)确定一个较大的阈值d为检测阈值，把高于该阈值的像素作为对象点。(2)选择一个较低的阈值t作为跟踪阈值，且要求td，该阈值可以根据不同准则来选择；可选择灰度差、梯度方向、对比度等作为跟踪阈值。(3)从第一行起用检测阈值d逐行对图像进行扫描，依次将灰度值大于或等于检测阈值d的点的位置记为1。(4)确定跟踪邻域，如下图中选取的(i+1,j1)、(i+1,j)、(i+1,j+1)。(5)从第二行起逐行扫描图像，若图像中的(i,j)点为对象点，则在第i+1行上找该点跟踪邻域中灰度差小于或等于跟踪阈值t的邻点，并确定为新的对象点，将相应位置记为1。(6)对于已检测出来的某个对象点，进行跟踪结束、分支和合并的处理。如果某个对象点（由于步骤(3)的原因产生的对象点）在上一行的对应邻域中没有对象点，则说明一条新的曲线可开始。(7)重复(5)、(6)这两个步骤，直至图像中最末一行被扫描完为止。,53,54,边缘连接光栅扫描跟踪,55,边缘连接光栅扫描跟踪,光栅跟踪的优缺点光栅扫描跟踪法是一种简单的利用局部信息、通过扫描的方式将边缘点连接起来的方法。该跟踪算法采用电视光栅行扫描顺序对遇到的像素进行分析，从而确定其是否为边缘。由于光栅扫描跟踪和扫描方向有关，因此最好沿其他方向再跟踪一次。,56,边缘连接轮廓跟踪法,一种适用于黑白二值图像的图像分割方法，而且轮廓跟踪改变了光栅跟踪中扫描方向的单一的缺点，跟踪方向可以是任意方向，并且有足够大的跟踪距离。轮廓跟踪是改变了邻域定义和跟踪准则的一种二值图像的光栅跟踪法。算法的具体步骤(1)在靠近边缘处任取一起始点，然后按照每次只前进一步，步距为一个象素的原则开始跟踪；(2)当跟踪中的某步是由白区进入黑区时，以后各步向左转，直到穿出黑区为止；(3)当跟踪中的某步是由黑区进入白区时，以后各步向右转，直到穿出白区为止；(4)当围绕目标边界循环跟踪一周回到起点时，则所跟踪的轨迹便是目标的轮廓；否则，应继续按(2)和(3)的原则进行跟踪。,57,边缘连接轮廓跟踪法,58,4图像阈值分割,原理,取阈值是一种广泛使用的图像分割技术，通过对灰度取阈值后得到的图像，各个区域可以分离开，但要将目标提取出来，还需要将各区域识别标记。,图像阈值分割,阈值分割法的基本思想：（边界上的点的灰度值出现次数较少）确定一个合适的阈值T（阈值选定的好坏是此方法成败的关键）。将大于等于阈值的像素作为物体或背景，生成一个二值图像。Iff(x,y)Tset255Elseset0,阈值分割法的特点：适用于物体与背景有较强对比的情况，重要的是背景或物体的灰度比较单一。（可通过先求背景，然后求反得到物体）这种方法总可以得到封闭且连通区域的边界。,61,门限处理,门限处理基础根据门限T的不同，可分为全局门限、局部门限、自适应门限全局门限:T=Tf(x,y)T仅取决于f(x,y)，整幅图像采用单一门限局部门限:T=Tf(x,y),p(x,y)T仅取决于f(x,y)和p(x,y)，p(x,y)表示点(x,y)的局部性质不同局部区域采用不同门限自适应门限:T=Tx,y,f(x,y),p(x,y)T取决于空间坐标x和y每个像素点的门限随像素的点的特性而变化,62,门限处理,基本全局门限通过对图像逐像素扫描，将灰度级大于阈值的像素标记为对象，将灰度级小于阈值的像素标记为背景全局门限的确定试探法自动确定经典的全局阈值分割方法,63,门限处理,64,门限处理,基本全局门限自动确定门限的算法选择一个T的初始估计值用T分割图像，G1由所有灰度值大于T的像素组成，G2由所有小于或等于T的像素组成对区域G1和G2中的所有像素计算平均灰度值1和2计算新的门限值T=(1+2)/2重复步骤2到4，直到逐次迭代得到的T值之差小于事先定义的参数T0,65,门限处理,66,门限处理,基本全局门限,经典全局阈值分割方法,经典全局阈值分割方法p-分位数法迭代法最大类间方差法熵阈值法最小误差法二维Otsu阈值分割法二维熵阈值分割法,67,经典全局阈值分割方法,p-分位数法基本原理是根据先验知识，得到目标与背景像素的先验概率比例，再根据此条件依次累计灰度直方图，直到累计值大于或等于该比例数，此时的灰度值即最佳阈值。该算法简单，有一定的抗噪声能力，但对于一些复杂图像的先验概率比较难求得，不适用于所有图像。迭代法基本原理是选取图像的平均灰度T0为初始阈值，然后用T0将图像的像素点分作两部分，计算两部分各自的平均灰度之间的中点T1，将T1作为新的全局阈值代替T0，重复以上过程，如此迭代，直至阈值收敛。当图像的灰度直方图双峰不明显，图像目标和背景比例差异悬殊时，迭代法的分割效果不理想。,68,经典全局阈值分割方法,最大类间方差法最大类间方差法是Otsu于1978年提出的，是应用最广泛的阈值分割法之一。其中o为目标的概率，o为目标的平均灰度值，b为背景的概率，b为背景的平均灰度值。熵阈值法基本思想都是利用图像的灰度分布密度函数定义图像的信息熵，根据假设或者视角的不同提出不同的熵准则，最后通过优化该准则得到最佳阈值，其中以Kapur等人提出的熵准则最为有名，又称为KSW熵法。最小误差法最小误差法来源于Bayes的最小误差分类方法，其原理是选择一个合适的阈值，使目标错分到背景和背景错分到目标的误差概率总和达到最小，此时的阈值即为最佳阈值。,69,设图像由目标和背景两部分组成，目标的灰度分布概率密度为po(r)，而背景的灰度分布概率密度为pb(r)，同时设目标占整个画面的百分比为q，则背景占1-q。若取阈值为t，则：,将背景点误判为物体点的误判概率为：,将物体点误判为背景点的误判概率为：,注意到上式右端第二项恰好是灰度小于t的背景点出现的总概率Pb(t)，故：,因此总的误判概率为：,最小误差法,最佳阈值,我们的目标是求出最佳阈值t，使总的误判概率最小，可以将上述误判函数对t求导，并令其为零，故有：,或写成：,若已知背景和目标的灰度概率密度，可以利用数值方法求出最佳阈值。,设目标区和背景区灰度的均值分别为mo和mb，均方差分别为so和sb，则：,代入上述总误判概率表达式，并取对数得：,经化简，此方程具有以下形式：,其中：,因此可以通过求解二次方程，求出两个根t1和t2，并选取合理的结果。,73,基于区域的分割,基本公式分割的目标是将图像划分为不同的区域令R表示整幅图像，可以将分割看成是将R划分为n个子区域的过程，n个子区域满足以下条件完备性：连通性：每个Ri都是一个连通区域独立性：单一性：互斥性：,区域增长法,通过象素聚合的区域增长法是最基本的区域分割技术。根据事先定义的准则将象素或子区域聚合成更大区域的过程。,区域生长的三个问题：种子：进行生长的起点。相似性准则：确定增长的规则。终止规则：考虑区域大小、形状、相似性等因素。,75,基于区域的分割,区域生长算法实现根据图像的不同应用选择一个或一组种子选择一个条件从该种子开始向外扩张，首先把种子像素加入集合，然后不断将与集合中各个像素连通、且满足给定条件的像素加入集合上一过程进行到不再有满足条件的新像素点加入集合为止,76,基于区域的分割,单连接区域增长方法：,对图像进行光栅扫描，求出不属于任何区域的象素（根据图像的不同应用选择一个或一组种子，它或者是最亮或最暗的点，或者是位于点簇中心的点。）；,2.将该点的灰度值与其邻域内不属于任何一个区域的象素灰度值比较，如果其差的绝对值小于某个设定的门限值，就把它们合并为同一区域；,3.对新合并的象素，重复（2）的操作；,4.反复进行（2）（3）的操作，直到不能再增加为止；,5.返回至（1），重新寻找能为新区域出发点的象素。,例：设有一数字图像，如图所示。检测灰度为9，平均灰度均匀测度度量的阈值为2，采用区域增长技术对图像进行分割。,(8988)/4=8.25,(8+8+9+7+7+8+7+8)/8=7.