《基元检测》PPT课件.ppt

《《基元检测》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《基元检测》PPT课件.ppt（89页珍藏版）》请在三一办公上搜索。

1、第5章背景知识,1965年，Roberts通过计算机程序从数字图像中提取出诸如立方体、楔形体、棱柱体等多面体的三维结构，并对物体形状及物体的空间关系进行描述。即将现实世界分解为由积木所构造的世界。在之后类似的研究中，Huffman、Clowes以及Waltz等人对积木世界进行了研究并分别解决了由线段解释景物和处理阴影等问题。此后的研究范围从边缘、角点等待征提取，到线条、平面、曲面等几何要素分析，直到图像明暗、纹理、运动以及成像几何等，并建立了各种数据结构和推理规则。到了70 年代，已经出现了一些视觉应用系统。积木世界的研究是从简化的世界出发进行研究，这也是视觉早期研究中的特点。这些工作对视觉研

2、究的发展起了促进作用，但对于稍微复杂的景物便难以奏效,第5章基元检测,基元泛指图像中有特点的基本单元，比如，边缘、角点、直线段、圆、孔等。,边缘是图像中比较低层的基元，是组成许多其他基元的基础，所以一直得到较多的关注。角点可以看做由两个边缘以接近直角相结合而构成的基元。直线段可看做是两个邻近又互相平行的边缘相结合而构成的基元。圆是一种常见的几何形状，圆周可看做是将直线段弯曲。头尾相接得到的。孔的形状与圆相同，但一般用孔来表示比较小的圆。,第5章基元检测,第5章基元检测,5.1边缘检测5.2SUSAN算子5.3哈夫变换5.4位置直方图技术,5.1边缘检测,图像中的边缘是像素灰度值发生剧烈变化而不

3、连续的结果。边缘检测是常见的图像基元检测的基础，也是所有基于边界的图像分割方法的第一步。,5.1边缘检测,5.1.1检测原理5.1.2一阶导数算子5.1.3二阶导数算子5.1.4边界闭合,5.1.1检测原理,像素灰度值的变化可利用求导数的方法来检测，一般常用一阶和二阶导数来检测边缘。下面介绍不同边缘的一些特点记忆对他们进行检测的原理。,5.1.1检测原理,阶梯状边缘，脉冲状边缘，屋顶状边缘,5.1.2一阶导数算子,一阶微分算子给出梯度，所以也称梯度算子它分别计算沿X和Y方向的两个偏导分量。对偏导分量的计算需对每个像素位置进行，在实际中常用小区域模版卷积来近似计算。,5.1.2一阶导数算子,对于

4、水平方向和垂直方向各用一个模版，将两个模版组合起来以构成一个梯度算子。罗伯特交叉算子，蒲瑞维特算子，索贝尔算子,5.1.2一阶导数算子,Roberts交叉梯度算子 f|z5-z9|+|z6-z8|梯度计算由两个模板组成，第一个求得梯度的第一项，第二个求得梯度的第二项，然后求和，得到梯度。两个模板称为Roberts 交叉梯度算子,z2,z8,z5,z3,z9,z6,z1,z7,z4,0,1,-1,0,-1,0,0,1,5.1.2一阶导数算子,Prewitt梯度算子3x3的梯度模板 f|(z7+z8+z9)-(z1+z2+z3)|+|(z3+z6+z9)-(z1+z4+z7)|,z2,z8,z5,

5、z3,z9,z6,z1,z7,z4,-1,1,0,-1,1,0,-1,1,0,0,0,0,-1,-1,-1,1,1,1,(a)原图，(b)|Gy|,y方向上的梯度分量，(c)|Gx|,y方向上的梯度分量，(d)梯度图像|Gx|+|Gy|,可以看到(b)(c)中两个分量的方向性是很明显的。(b)中屋瓦、砖块的水平接缝和窗户的水平分段的图像非常清晰。(c)中表现出了垂直部分，诸如墙附近的拐角、窗户的垂直部分等的。,5.1.2一阶导数算子,Sobel梯度算子3x3的梯度模板 f|(z7+2z8+z9)-(z1+2z2+z3)|+|(z3+2z6+z9)-(z1+2z4+z7)|,z2,z8,z5,z

6、3,z9,z6,z1,z7,z4,-2,2,0,-1,1,0,-1,1,0,0,0,0,-1,-1,-2,1,1,2,5.1.2一阶导数算子,5.1.3二阶导数算子,用二阶导数算子检测阶梯状边缘需将算子模版与图像卷积，并确定算子输出值的过零点。,5.1.3二阶导数算子,1.拉普拉斯算子拉普拉斯算子 2f=2f/x2+2f/y2对于离散图像 f(x,y)/x=x f(x,y)=f(x,y)-f(x-1,y)f(x,y)/y=y f(x,y)=f(x,y)-f(x,y-1),z2,z8,z5,z3,z9,z6,z1,z7,z4,2f(x,y)/x2=x f(x+1,y)-xf(x,y)=f(x+1

7、,y)+f(x-1,y)-2f(x,y)2f(x,y)/y2=y f(x,y+1)-yf(x,y)=f(x,y+1)+f(x,y-1)-2f(x,y)2f=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y),5.1.3二阶导数算子,5.1.3二阶导数算子,在图像中，计算函数的拉普拉斯值也可借助各种模板实现。模板的基本要求是对应中心像素的系数应是正的，而对应中心像素邻近像素的系数应是负的，且所有系数的总和应该是零。,5.1.3二阶导数算子,拉普拉斯算子边缘检测示例：,5.1.3二阶导数算子,拉普拉斯算子一般不以其原始形式用于边缘检测，原因在于：(1)它是一个二

8、阶导数，对噪声非常敏感。(2)拉普拉斯算子的幅值产生双边缘。(最大负值和最大正值)(2)不能检测边缘的方向。（无方向模版）那么它在分割中所起的作用:(1)利用它的零交叉性质进行边缘定位-该算子与平滑过程一起利用零交叉作为找到边缘的前兆。(2)确定一个象素在边缘暗的一边还是亮的一边。,5.1.3二阶导数算子,2.马尔算子马尔算子是在拉普拉斯算子的基础上实现的边缘检测算子。马尔边缘检测是高斯加权平滑运算与拉普拉斯运算的结合体。,5.1.3二阶导数算子,马尔算子在每个分辨率上进行如下计算(1)用一个2-D的高斯平滑模板与原图像卷积(2)计算卷积后图像的拉普拉斯值(3)检测拉普拉斯图像中的过零点作为边

9、缘点,5.1.3二阶导数算子,高斯加权平滑函数：,5.1.3二阶导数算子,对平滑后的图像再运用拉普拉斯算子：,为离原点的径向距离，,5.1.3二阶导数算子,3.坎尼算子 坎尼(Canny)把边缘检测问题转换为检测单位函数极大值问题来考虑，利用高斯模型，借助图像滤波的概念之处一个好的边缘检测算子应具有三个指标：（1）低失误概率（要少将真正的边缘丢失和少将非边缘判断为边缘）（2）高位置精度（检测出的边缘应在真正的边界上）（3）单像素边缘（对每个边缘有唯一的响应）,5.1.3二阶导数算子,根据上述指标，坎尼提出判定边缘检测算子三个准则：(1)信噪比准则(2)定位精度准则(3)单边缘响应准则,5.1.

10、3二阶导数算子,3.坎尼算子检测效果,5.1.4边界闭合,用各种算子得到的边缘像素常是孤立的或仅分小段连续的，为组成区域的封闭边界以使将不同区域分开，需要将边缘像素连接起来。下面介绍一种利用像素梯度的幅度和方向进行边界闭合的方法。,5.1.4边界闭合,边缘像素连接的基础是它们之间有相似性梯度幅度梯度方向如果像素(s,t)在像素(x,y)的邻域且它们的梯度幅度和梯度方向分别满足以上两个条件（T是幅度阈值，A是角度阈值），那么可将(s,t)处的像素与在(x,y)处的像素连接起来。,5.1.4边界闭合,对所有边缘像素都进行这样的判断和连接就有希望的到闭合边界。,第5章基元检测,5.1边缘检测5.2S

11、USAN算子5.3哈夫变换5.4位置直方图技术,5.2SUSAN算子,SUSAN算子是一种很有特色的检测算子，只使用一个圆形模版来得到各向同性的响应。它不仅可以检测出图像中目标的边缘点，而且能鲁棒地检测出图像中目标的角点（局部曲率较大的点）。,5.2SUSAN算子,5.2.1USAN原理5.2.2角点和边缘检测,5.2.1USAN原理（Univalve Segment Assimilating Nucleus）,如图5.21所示，图中图像的上部分为亮区域，下部分为暗区域，分别代表目标和背景。将圆形的模板放在6个典型位置如下所示。,5.2.1USAN原理,从左边数过去，第1个模板全部在亮区域，第

12、2个模板大部在亮区域，第3个模板一半在亮区域，第4个模板大部分在暗区域，第5个模板全部在暗区域，第6个模板的1/4在暗区域。,5.2.1USAN原理,如果将模版中各个像素的灰度都与模版中心的核像素的灰度进行比较，发现总有一部分模版区域像素的灰度与核像素的灰度相同或相似。这部分区域称为核同值区域（uni-value segment assimilating nucleus，USAN），即与核有相同值的区域，可简称为核同值区。USNA区域包含了很多与图像结构有关的信息。,5.2.1USAN原理,利用这种区域的尺寸、重心等统计量可以帮助检测图像中的边缘和角点。从图5.2.1可见，当核像素处在图像中的

13、灰度一致区域时，USAN的面积会超过一半，第1个模板和第5个模板以及第2个模板和第4个模板都属于这种情况。当核处在直边缘处USAN的面积约为最大值的一半，第3个模板就属于这种情况。当核位于角点处时USAN的面积更小，约为最大值的1/4，第6个模板就属于这种情况。,5.2.1USAN原理,利用USAN面积的变化可检测边缘或角点，具体来说，USAN面积较大时表明核像素处在图像中的灰度一致区域，在模板核接近边缘时该面积减少，而在接近角点时减少的更多，即在角点处面积取得最小值。,5.2.2角点和边缘检测,在USAN区域的基础上可讨论SUSAN算子（最小核同值算子），并进行角点和边缘检测。1.角点检测圆

14、形模板,5.2.2角点和边缘检测,1.角点检测设模板函数为M(x,y)，将其依次放在图像中每个点的位置，在每个位置，将模板内每个像素的灰度值与核的灰度值进行比较。,5.2.2角点和边缘检测,1.角点检测输出的游程和这个总和其实就是USAN区域的像素个数，或者说它给出了USAN区域的面积。如前面所讨论的，这个面积在角点处会达到最小。,5.2.2角点和边缘检测,阈值T既可用来帮助检测USAN区域面积的最小值，也可以确定所能消除的噪声的最大值。当图像中没有噪声时，仅用灰度差阈值T就可以了。但当图像中有噪声时，需要将游程和与一个固定的几何阈值进行比较做出判断。该阈值设为以给出最优的噪声消除性能，其中是

15、所能取得的最大值,5.2.2角点和边缘检测,1.角点检测边缘响应R(x0,y0)将游程和S与一个固定的几何阈值G进行比较上式是根据USAN原理获得，USAN的面积越小，边缘的响应越大。,5.2.2角点和边缘检测,1.角点检测更稳定的计算C(.;.)的公式此式更为平滑，它允许像素灰度有一定的变化，而不会对C(.;.)造成太大的影响。,5.2.2角点和边缘检测,1.角点检测角点检测示例：下图为两个用SUSAN算子检测图像中的角点而得到的结果。,5.2.2角点和边缘检测,2.边缘方向检测在很多情况下，不仅需要考虑边缘的强度，也需要考虑边缘的方向。首先，如果要除去非最大的边缘值，就必须要借助边缘的方向

16、。另外，如果需要确定边缘的位置到亚像素精度，也常需要利用边缘方向的信息，最后，许多应用中常把边缘的位置。强度和方向结合使用。,5.2.2角点和边缘检测,2.边缘方向检测对大多数现有的边缘检测算子，边缘方向是借助边缘强度来确定的。根据USAN的原来确定边缘方向需根据边缘点的不同种类采用不同的方法。考虑USAN区域的特点，将边缘分成两类来讨论,5.2.2角点和边缘检测,2.边缘方向检测边缘分两类区域A和B都对应边缘都通过USAN区域的重心,5.2.2角点和边缘检测,2.边缘方向检测在区域A和B中，边缘落在像素之间，从USAN区域的重心到模板核的矢量与边缘的局部方向（几乎）垂直。在区域C中，边缘通过

17、像素的重心而不是像素之间，而且边缘两边有较高的反差，这种情况可称为像素内部边缘情况。在这种情况下，所获得的USAN区域时沿边缘方向的细条。,5.2.2角点和边缘检测,2.边缘方向检测通过寻找边缘区域最长的对称轴就可以发现边缘方向。具体可通过以下求和所得到的结果来估计。,5.2.2角点和边缘检测,2.边缘方向检测为确定边缘点额朝向，可以使用Fy(x0,y0)和Fx(x0,y0)的比值，而用Fxy(x0,y0)的符号可帮助区别对角方向的边缘具有正的或负的梯度。,5.2.2角点和边缘检测,2.边缘方向检测如何自动确定哪个图像点属于哪种情况？首先，如果USAN区域的面积比模板的直径小，那么就应该是像素

18、内边边缘的情况，如果USAN的面积比模板的直径大，那么就可以确定出USAN区域的重心，并可根据像素之间的边缘情况来计算边缘的方向。,5.2.2角点和边缘检测,3.SUSAN算子的特点进行检测时不需要计算微分，这可帮助解释为什么在有噪声时SUSAN算子的性能会较好对边缘的响应将随着边缘的平滑或模糊而增强SUSAN检测算子能提供不依赖于模板尺寸的边缘精度控制参数的选择很简单，且任意性较小,第5章基元检测,5.1边缘检测5.2SUSAN算子5.3哈夫变换5.4位置直方图技术,5.3哈夫变换,哈夫变换是利用图像全局特性性针对各种基元或目标进行检测的一种方法。,5.3哈夫变换,5.3.1基本哈夫变换原理

19、5.3.2广义哈夫变换原理5.3.3完整广义哈夫变换,5.3.1基本哈夫变换原理,哈夫变换的原理：点线对偶性。在图像空间XY里，所有过点（x,y）的直线满足如下所示：其中参数p代表斜率，q代表截距。,5.3.1基本哈夫变换原理,如果对p和q建立一个参数空间，则(p,q)表示参数空间PQ中的一个点。这个点和上式所表示的直线是一一对应的，即XY空间中的一条直线对应PQ空间中的一个点。,霍夫变换的基本原理 基本思想是点-线的对偶性(duality)。图像变换前在图像空间，变换后在参数空间。在图像空间XY里，所有过点(x,y)的直线都满足方程：y=ax+b，也可以写成：b=-ax+y,那么该式就可看作

20、是参数空间ab中过点(a,b)的一条直线。如下图所示。(a)为图像空间，(b)为参数空间。在图像空间中，过点(xj,yj)的通用直线方程可以写为：yi=axi+b,也可写成b=-axi+yi，后者表示在参数空间里的一条直线。同理，过点(xj,yj)有yj=axj+b,也可写成b=-axj+bj,它表示参数空间里的另一条直线。设参数空间中两线相交于点(a,b)，那么点(a,b)对应于图像空间中一条过(xi,yi)，(xj,yj)的直线。因为它满足 yi=axi+b 和yj=axj+b。,由此可见图像空间XY中过点(xi,yi)和(xj,yj)的直线上的每个点都对应参数空间ab里的一条直线，且这些

21、直线相交于点(a,b).由此可知，在图像空间中共线的点对应在参数空间里的相交的线。反过来，在参数空间中相交于同一个点的所有直线在图像空间里都有共线的点与之对应。这就是点-线对偶性。根据点-线对偶性，当给定图像空间中的一些边缘点，就可通过霍夫变换确定连接这些点的直线方程。霍夫变换把在图像空间中的直线检测问题转换成参数空间里对点的检测问题，通过在参数空间里进行简单的累加统计完成检测任务。,(amax,amin)和(bmax,bmin)分别为斜率和截距值期望的范围。位于坐标(i,j)的单元具有累加值A(i,j)，并对应于参数空间坐标(ai,bj)相关的矩形。初始值全为0。然后对图像平面中的每个点(x

22、k,yk),令参数a等于a轴上每个允许的细分值，同时使用等式得到相应的b.然后对得到的b值进行舍入得到b轴上允许的近似的值。,使用等式y=ax+b表示一条直线带来的一个问题是，当直线接近垂直时，斜率接近无穷大。也就是说a的最大接近于无穷。解决的方法是采用直线的标准式：与直线不同，这个公式的轨迹是平面上的正玄曲线。的取值为正负90度。,霍夫变换的说明,(a)显示了一幅带有5个标记点的图像。(b)显示了每个点映射到平面上的结果。(c)说明了霍夫变换的共性检测性质。(d)说明了霍夫变换展示了参数空间左右边缘的反射式的邻接关系。点A代表xy图像平面上内对应于点1、3、5的曲线的交点。点A的位置表示这三

23、个点在一条过原点且方向为-45度的直线上。,霍夫变换的说明,例题：使用哈夫变换进行边缘连接,图(a)显示了一幅航拍的红外线图像。(b)是设置了门限的梯度图像。(c)显示了梯度图像的霍夫变换。(d)显示了依据一定准则判断为相连的像素集合。,5.3.1基本哈夫变换原理,对上述两个式子所给出的图像空间和参数空间中点和线的对应性就是点-线对偶性。根据点-线对偶性可将在XY空间中对直线的检测转化为在PQ空间中对点的检测，例如，设已知XY空间的一些点，利用哈夫变换检测它们是否共线的具体步骤如下：,5.3.1基本哈夫变换原理,(1)对参数空间中参数p和q的可能取值范围进行量化，根据量化结果构造一个累加数组A

24、(pmin:pmax,qmin:qmax)，并初始化为零(2)对每个XY空间中的给定点让p取遍所有可能值，用式(5.3.2)计算出q，根据p和q的值累加A，即A(p,q)=A(p,q)+1。(3)根据累加后A中最大值所对应的p和q，由式(5.3.1)确定出XY中的一条直线,5.3.1基本哈夫变换原理,由此可见哈夫变换技术的基本策略是根据对偶性由图像空间里的点计算参数空间里的线，再由参数空间里的线的交点确定图像空间里的线。哈夫变换可用来检测各种能以解析式f(x,c)=0表示的曲线或目标轮廓，这里x为图像点坐标矢量，c为参数矢量。哈夫变换检测的计算量随c维数的增加而指数地增加，为了减少计算量可利用

25、图像点的梯度信息。下面以检测椭圆为例来说明。,5.3.1基本哈夫变换原理,如果直接利用哈夫变换进行检测，设椭圆方程为则参数共有4个：椭圆中心坐标(p,q)，椭圆长短半轴的长度a和b。由于4个参数，所以要建立一个4-D累加数组A(p,q,a,b)，对每个p都要遍历q，a和b的所有取值。,5.3.1基本哈夫变换原理,如果利用梯度信息，将上式对x求导，并利用 可得将上述两式联立可解得,5.3.1基本哈夫变换原理,以上两式中，每个方程只有3个参数，所以可建立2个3-D累加数组Ax(p,a,b)和Ay(q,a,b),对每个(x,y)让a和b依次变化并分别算出对应的p和q，再对Ax和Ay进行累加:Ax(p

26、,a,b)=Ax(p,a,b)+1，Ay(q,a,b)=Ay(q,a,b)+1。这样，所需的计算量约只有直接发的2/M，M为q所有取值的个数。,5.3.1基本哈夫变换原理,霍夫变换也适用于任何形式为g(v,c)=0的函数，这里v是坐标向量，c是系数向量。基于霍夫变换的边缘连接方法：1.计算图像的梯度并对其设置门限得到一幅二值图像。2.在平面内确定再细分。3.对像素高度集中的地方检验其累加器单元的数目。4.检验选择的单元中像素之间的关系（主要针对连续性）,5.3.2广义哈夫变换原理,广义哈夫变换：从对椭圆的检测可知，利用梯度信息可将累加数组的维数减少一个。另外还可知，相对于椭圆上的点的(x,y)

27、来说，椭圆的中心坐标(p,q)是一个参考点，所有(x,y)点都是以a和b为参数与(p,q)联系起来的。如果将参数确定了（检测出来了），椭圆就确定了。根据这个道理，在所需检测的曲线或目标轮廓没有货不已用解析式表达时，可以利用表格来建立曲线或轮廓点与参考点间的关系，从而可继续利用哈夫变换进行检测。,5.3.2广义哈夫变换原理,利用表格建立曲线或轮廓点与参考点间的关系参考点的坐标可由轮廓点的坐标算出来,5.3.2广义哈夫变换原理,广义哈夫变换计算示例设正方形的中点为参考点，则从各轮廓点向参考点所引矢量的矢径和矢角如表5.3.2所示,5.3.2广义哈夫变换原理,5.3.2广义哈夫变换原理,对图5.3.

28、2所示的正方形上的8个轮廓点分别判断他们对应的可能参考点，每个轮廓点分别有两个可能的参考点，结果如表5.3.4,5.3.2广义哈夫变换原理,因为每条边上2个点的 相同，所以对每个 有2个 和2个。由表5.3.4可见，从参考点出现的频率来看，点O出现最多，所以如对它进行累加将得到最大值，即检测到的参考点为点O。,5.3.3完整广义哈夫变换,完整广义哈夫变换：不仅要考虑轮廓的平移，而且要考虑轮廓的放缩、旋转，此时参数空间会从2-D增加到4-D,5.3.3完整广义哈夫变换,完整广义哈夫变换计算示例,现将例5.3.1中的正方形绕点a逆时针旋转，得到的图像如右图所示，求此时的参考点位置,5.3.3完整广

29、义哈夫变换,第5章基元检测,5.1边缘检测5.2SUSAN算子5.3哈夫变换5.4位置直方图技术,5.4位置直方图技术,1.检测原理位置直方图是将图像向多个轴投影，并对像素灰度求和而得到的直方图，也称横向直方图从这两个直方图向目标区域进行反投影，就可方便地确定出各个目标的位置,Computer Vision,投影 投影能表现图像的某种特征信息 给定一条直线，用垂直该直线的一簇等间距直线将一幅二值图像分割成若干条，每一条内像素值为1的像素个数为该条二值图像在给定直线上的投影定义给定直线为水平或垂直直线时，二值图像列或行上,像素值为1的像素数量之和为该图像的水平或垂直投影,Computer Vision,二值图像及其对角线上的投影图,Computer Vision,5.4位置直方图技术,2.计算量分析完整的检测算法所需的操作数为直接使用模板匹配使用位置直方图的提速约为20倍,5.4位置直方图技术,3.使用子图像 当图像数据满足Nnp时，需要将图像分解为子图像，再使用位置直方图技术。,