图像表示与描述.ppt

单击此处编辑母版标题样式,0,单击此处编辑母版文本样式,1,第二级,2,第三级,3,第四级,4,第五级,5,*,第三章 数字图像分析 第三节 表示与描述,数字图像处理,北京大学计算机研究所 陈晓鸥,第三节 表示与描述,3.3.1,表示与描述的基本概念,3.3.2,表示法设计,3.3.3,边界描述子,3.3.4,关系描述子,3.3.1,表示与描述的基本概念,基本概念,在用前一章的方法，把图像分割后，为了进一步的处理，,分割后的图像一般要进行形式化的表达和描述,解决形式化表达问题一般有两种选择：,1,）根据区域的,外部特征,来进行形式化表示,2,）根据区域的,内部特征,（比较区域内部的象素值）来来进行形式化表示,3.3.1,表示与描述的基本概念,基本概念,选择表达方式，要本着使数据变得更有利于下一步的计算工作。下一步工作是基于所选的表达方式描述这个区域，一般情况下：,1,）如果关注的焦点是形状特性，选择,外部表示方式,2,）如果关注的焦点是反射率特性，如颜色、文理时，选择,内部表示方式,。,3,）所选表示方式，应该对尺寸、变换、旋转等变量尽可能的不敏感,3.3.2,表示与描述,:,表示法设计,表示法设计,链码,多边形逼近,外形特征,边界分段,区域骨架,3.3.2,表示与描述,:,表示法设计,链码,定义：,1,）链码是一种,边界的编码表示法,。,2,）,用边界的方向作为编码依据,。为简化边界的描述。,一般描述的是边界点集,。,0,1,2,3,0,1,4,6,7,2,3,5,4-,链码,8-,链码,3.3.2,表示与描述,:,表示法设计,链码,算法：,给每一个线段一个方向编码。,有,4-,链码和,8-,链码两种编码方法。,从起点开始，沿边界编码，至起点被重新碰到，结束一个对象的编码。,3.3.2,表示与描述,:,表示法设计,链码举例：,4-,链码：,000033333322222211110011,3.3.2,表示与描述,:,表示法设计,链码,问题,1,：,1,）链码相当长。,2,）噪音会产生不必要的链码。,改进,1,：,1,）加大网格空间。,2,）依据原始边界与结果的接近程度来确定新点的位置。,3.3.2,表示与描述,:,表示法设计,链码举例：,4-,链码：,003332221101,3.3.2,表示与描述,:,表示法设计,链码,问题,2,：,1,）由于起点的不同，造成编码的不同,2,）由于角度的不同，造成编码的不同,改进,2,：,1,）从固定位置作为起点,(,最左最上,),开始编码,2,）通过使用链码的首差代替码子本身的方式,3.3.2,表示与描述,:,表示法设计,链码,循环首差链码：用相邻链码的差代替链码,例如：,4-,链码,10103322,循环首差为：,33133030,循环首差：,1-2=-1(3)3-0=3,0-1=-1(3)3-3=0,1-0=123=-1(3),0-1=-1(3)2-2=0,3.3.2,表示与描述,:,表示法设计,链码,应用背景：,如果边界的本身对于旋转和比例修改来说是无变化的，使用链码才是正确的。一般来说这是不可能的，实际应用时还需要改进。,用链码后，对象只要用,1),起点坐标，,2),周长（边界点数）,3),链码，,4),对象编号，就可以,描述,。,链码一般用于一幅图像中有多个对象的情况，对单个对象不适用。,3.3.2,表示与描述,:,表示法设计,多边形逼近,基本思想：用最少的多边形线段，获取边界形状的本质。,寻找最小基本多边形的方法一般有两种：,点合成法,和,边分裂法,3.3.2,表示与描述,:,表示法设计,多边形逼近,点合成算法思想举例：,3.3.2,表示与描述,:,表示法设计,多边形逼近,合成点算法：,1,）沿着边界选两个相邻的点对，计算,首尾连接直线段,与,原始折线段,的误差。,2,）如果误差小于预先设置的阈值。去掉中间点，选新点对与下一相邻点对，重复,1,）；否则，存储线段的参数，置误差为,0,，选被存储线段的终点为起点，重复,1,）,2,）。,3,）当程序的第一个起点被遇到，程序结束。,3.3.2,表示与描述,:,表示法设计,多边形逼近,合成点算法的问题：,顶点一般不对应于边界的拐点,（如拐角）。因为新的线段直到超过误差的阈值才开始。,下面讲到的,分裂法,可用于缓解这个问题,3.3.2,表示与描述,:,表示法设计,多边形逼近,边分裂算法思想举例：,3.3.2,表示与描述,:,表示法设计,多边形逼近,分裂边算法：,（,1,）连接边界线段的两个端点（如果是封闭边界，连接最远点）；,（,2,）如果最大正交距离大于阈值，将边界分为两段，最大值点定位一个顶点。重复（,1,）；,（,3,）如果没有超过阈值的正交距离，结束。,3.3.2,表示与描述,:,表示法设计,外形特征,基本思想：,外形特征是一种用一维函数表达边界的方法。基本思想是把边界的表示降到一维函数,3.3.2,表示与描述,:,表示法设计,外形特征,函数定义,质心角函数：边上的点到质心的距离,r,，作为夹角的,的函数。,A,r,r),2,A,3.3.2,表示与描述,:,表示法设计,外形特征,举例：,A,r,r(),2,A,3.3.2,表示与描述,:,表示法设计,外形特征,问题：函数过分依赖于旋转和比例的变化,改进：,对于旋转,两种改进：,a.,选择离质心最远的点作为起点,b.,选择从质心到主轴最远的点作为起点,对于比例变换：,对函数进行正则化，使函数值总是分布在相同的值域里，比如说,0,，,1,3.3.2,表示与描述,:,表示法设计,边界分段,基本概念：,一个任意集合,S,（区域）的,凸起外缘,H,是：包含,S,的最小凸起的集合,H-S,的差的集合被称为集合,S,的,凸起补集,D,S,S,D,S+D=H,3.3.2,表示与描述,:,表示法设计,边界分段,分段算法：,给进入和离开凸起补集的变换点打标记来划分边界段。,优点：不依赖于方向和比例的变化,S,3.3.2,表示与描述,:,表示法设计,边界分段,问题：,噪音的影响，导致出现零碎的划分。,解决的方法：,先平滑边界，或用多边形逼近边界，然后再分段,3.3.2,表示与描述,:,表示法设计,区域骨架,基本思想,表示一个平面区域结构形状的重要方法是把它削减成图形。这种削减可以通过细化（也称为抽骨架）算法，获取区域的骨架来实现,Blum,的,中轴变换方法,（,MAT,）,设,:R,是一个区域，,B,为,R,的边界点，对于,R,中的点,p,，找,p,在,B,上,“,最近,”,的邻居。如果,p,有多于一个的邻居，称它属于,R,的中轴（骨架）,3.3.2,表示与描述,:,表示法设计,区域骨架,基本思想,问题：计算量大,p,R,B,3.3.2,表示与描述,:,表示法设计,区域骨架,算法改进思想,在保证产生正确的骨架的同时，改进算法的效率。比较典型的是一类细化算法，它们不断删去边缘，但保证删除满足：,（,1,）不移去端点,（,2,）不破坏连通性,（,3,）不引起区域的过度腐蚀,3.3.2,表示与描述,:,表示法设计,区域骨架,一种细化二值区域的算法,假设区域内的点值为,1,，背景值为,0,这个方法由对给定区域的边界点连续进行,两个基本操作,构成,这里边界点是指任何值为,1,且至少有一个,8,邻域上的点为,0,的象素,3.3.2,表示与描述,:,表示法设计,区域骨架,基本操作,1,对于满足以下四个条件的边界点打标记准备删除：,(a),2,N(p,1,),6,其中,N(p,1,),是点,p,1,的邻域中,1,的个数，即：,N(p,1,)=p,2,+p,3,+,+p,9,(b),S(p,1,)=1,其中,S(p,1,),是按,p,2,p,3,p,9,顺序，,0-1,转换,的个数,(c),p,2,*p,4,*p,6,=0,（,p,2,、,p,4,、,p,6,至少有一个,0,）,(d),p,4,*p,6,*p,8,=0,（,p,4,、,p,6,、,p,8,至少有一个,0,）,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2,表示与描述,:,表示法设计,区域骨架,所有条件都满足，才打删除标记。删除并不立即进行，而是等到对所有边界点都打完标记后，再把作了标记的点一起删除。,举例,:,N(p1)=4,S(p1)=3,p2*p4*p6=0,p4*p6*p8=0,第,2,个条件没满足不打标记,0,0,p1,1,1,0,1,0,1,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2,表示与描述,:,表示法设计,区域骨架,基本操作,2,条件,(a),、,(b),与操作,1,相同,条件,(c),、,(d),改为：,c,),p,2,*p,4,*p,8,=0,d,),p,2,*p,6,*p,8,=0,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2,表示与描述,:,表示法设计,区域骨架,细化算法,细化算法的一轮操作包括：,按操作,1,，给边界点打标记,删除点,按操作,2,，给边界点打标记,删除点,这个基本过程反复进行，直至没有点可以删除为止。此时算法终止,。,3.3.2,表示与描述,:,表示法设计,区域骨架,算法分析：,1,）条件,a),的分析：当轮廓点,p,1,的,8,邻域上有,1,个或,7,个值为,1,的点时，不满足条件,a,。,有,1,个点说明：,p,1,是骨架上的终点，显然不能删除,有,7,个点说明：如果删除,p,1,会引起区域的腐蚀,2,）条件,b),的分析：当,p,1,在宽度为,1,的笔划上时，不满足条件,b,。因而该条件保证了骨架的连续性。,3.3.2,表示与描述,:,表示法设计,区域骨架,算法分析：,（,3,）当,(p,4,=0 or p,6,=0)or(p,2,=0 and p,8,=0),时，条件,c,d,同时满足。满足这个条件的点可能是右边、下边、左上角的边界点。任何一种情况下，,p,1,都不是骨架的一部分，应被删除。,当,(p,4,=0 and p,6,=0)or(p,2,=0 or p,8,=0),时，条件,c,d,同时满足。满足这个条件的点可能是左边、上边、右下角的边界点，应被删除。,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2,表示与描述,:,表示法设计,区域骨架,例,:,3.3.3,表示与描述：边界描述子,边界描述子,简单描述子,形状数,傅立叶描述子,矩量,3.3.3,表示与描述：边界描述子,简单描述子,边界的周长,：,是最简单的描述符之一。沿轮廓线计算象素的个数，给出了一个长度的近似估计,边界的直径,：边界,B,的直径是：,Diam(B)=maxD(p,i,p,j,),D,是欧氏距离或几何距离，,p,i,p,j,是边界上的点。直径的长度和直径的两个端点连线（这条线被称为,边界的主轴,）的方向，是关于边界的有用的描述符。,3.3.3,表示与描述：边界描述子,简单描述子,边界的直径,举例,3.3.3,表示与描述：边界描述子,简单描述子,边界的曲率,：,曲率被描述为斜率的变化率。近似：用相邻边界线段（描述为直线）的斜率差作为在边界线交点处的曲率描述子。,交点,a,处的曲率为,dk=k1,k2,其中,k1,、,k2,为相邻线段的斜率,a,k1,k2,3.3.3,表示与描述：边界描述子,简单描述子,边界的凸线段点,：,当顶点,p,上的斜率是非负时，称其为凸线段上的点,边界的凹线段点,：,当顶点,p,上的斜率为负时，称其为凹线段上的点,3.3.3,表示与描述：边界描述子,简单描述子,边界的凸线段点,P1,：,边界的凹线段点,P2,：,P1,P2,3.3.3,表示与描述：边界描述子,形状数,形状数定义：,最小循环首差链码,。,循环首差链码：用相邻链码的差代替链码,例如：,4-,链码,10103322,循环首差为：,33133030,循环首差,:,1-2=-1(3)3-0=3,0-1=-1(3)3-3=0,1-0=12-3=-1(3),0-1=-1(3)2-2=0,3.3.3,表示与描述：边界描述子,形状数,形状数定义：,例如：,4-,链码 ：,10103322,循环首差 ：,33133,|,030,形状数 ：,03033133,形状数序号,n,的定义：,形状数中阿拉伯数字的个数，对于封闭边界序号是偶数。如,order4,、,6,、,8,。,3.3.3,表示与描述：边界描述子,形状数,形状数例如：,序号,4,链码：,0321,首差：,3333,形状：,3333,序号,6,链码：,003221,首差：,303303,形状：,033033,序号,8,链码：,00032221,首差：,30033003,形状：,00330033,3.3.3,表示与描述：边界描述子,形状数,形状数例如：,序号,6,链码：,033211,首差：,330330,形状：,033033,序号,6,链码：,003221,首差：,303303,形状：,033033,3.3.3,表示与描述：边界描述子,形状数,问题：,虽然链码的首差是不依赖于旋转的，但一般情况下边界的编码依赖于网格的方向。,改进：,规整化网格方向，具体方法如下：,3.3.3,表示与描述：边界描述子,形状数,几个基本概念：,边界,最大轴,a:,是连接距离最远的两个点的线段,边界,最小轴,b:,与最大轴垂直，且其长度确定的包围盒刚好包围边界。,边界,离心率,c,：最大轴长度与最小轴长度的比,c=a/b,基本矩形,:包围边界的矩形。,3.3.3,表示与描述：边界描述子,形状数,基本概念举例,边界,最大轴,a,边界,最小轴,b,基本矩形,3.3.3,表示与描述：边界描述子,形状数,规整化网格方向,算法的思想：,大多数情况下，将链码网格与基本矩形对齐，即可得到一个唯一的形状数。,对一个给定的形状序号，处理步骤如下：,（,1,）我们找出一个序号为,n,的矩形，,它的离心率最接近于给定形状的基本矩形的离心率,。,3.3.3,表示与描述：边界描述子,形状数,（,2,）然后再用这个矩形构造网格。,例如,:,如果,n=12,，所有序号为,12,的矩形（即周长为,12,）为,2*4,，,3*3,，,1*5,。如果,2*4,矩形的离心率最接近于给定边界的基本矩形的离心率，我们建立一个,2*4,的网格。,（,3,）再得到链码。,（,4,）最后，再得到循环首差。,（,5,）首差中的最小循环数即为形状数。,3.3.3,表示与描述：边界描述子,形状数,规整化网格方向算法,举例：,链码：,000033222121,首差：,300030300313,形状：,000303003133,0,1,2,3,3.3.3,表示与描述：边界描述子,傅立叶描述子,1,）基本思想：,（,1,）对于,XY,平面上的每个边界点，将其坐标用复数表示为：,s(k)=x(k)+jy(k)k=0,1,N-1,y,0,y,1,x,0,x,1,jy,x,x(k)=x,k,y(k)=y,k,3.3.3,表示与描述：边界描述子,傅立叶描述子,1,）基本思想：,（,2,）进行离散傅立叶变换,N-1,a(u)=1/N,s(k)exp(-j2,uk/N)u=0,1,N-1,u=0,N-1,s(k)=,a(u)exp(j2,uk/N)k=0,1,N-1,u=0,a(u),被称为边界的,傅立叶描述子,3.3.3,表示与描述：边界描述子,傅立叶描述子,1,）基本思想：,（,3,）选取整数,M,N-1,，进行逆傅立叶变换（重构）,M-1,s,(k)=,a(u)exp(j2,uk/N)k=0,1,N-1,u=0,这时，对应于边界的点数没有改变，但在重构每一个点所需要的计算项大大减少了。如果边界点数很大，,M,一般选为,2,的指数次方的整数。,3.3.3,表示与描述：边界描述子,傅立叶描述符,2,）,M,的选取与描述符的关系,在上述方法中，相当于对于,u M-1,的部分舍去不予计算。由于傅立叶变换中高频部分对应于图像的细节描述，因此,M,取得越小，细节部分丢失得越多。,3.3.3,表示与描述：边界描述子,傅立叶描述符,3,）优点,1,）使用复数作为描述符，对于旋转、平移、放缩等操作和起始点的选取不十分敏感。,2,）以上几何变换均可以通过对描述子函数作简单变换来获得。,3.3.3,表示与描述：边界描述子,矩量,基本思想：,将描述形状的任务减少至描述一个一维函数，边界段和特征的形状可以用矩量来量化地描述,矩量的定义：,把边界当作直方图函数：,g(r),r,g(r),3.3.3,表示与描述：边界描述子,矩量,矩量的定义：,L,n,(r)=,(r,i,-m),n,g(r,i,),i=1,L,其中,m=,r,i,g(r,i,),i=1,这里,L,是边界上点的数目,n,(r),是边界的矩量,3.3.3,表示与描述：边界描述子,矩量,矩量的优点：,实现是直接的,附带了一种关于边界形状的,“,物理,”,解释,对于旋转的不敏感性,为了使大小比例不敏感，可以通过伸缩,r,的范围来将大小正则化。,3.3.3,表示与描述：关系描述子,关系描述子,基本思想,阶梯关系编码,骨架关系编码,方向关系编码,内角关系编码,树结构关系编码,3.3.3,表示与描述：关系描述子,基本思想：,通过挖掘各个成分之间的结构关系来描述边界,图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串,主导思想是考虑物体各个部分的连接线段,3.3.4,表示与描述：关系描述子,阶梯关系编码,对于如下阶梯形边界，定义两个基本元素,a,b,a,b,a,a,a,b,b,b,3.3.4,表示与描述：关系描述子,阶梯结构关系,定义如下产生规则：,(1)S-aA,(2)A-bS,(3)A-b,其中,S,、,A,是变量,举例：,(1,3),(1,2,1,3),(1,2,12,1,3),a,a,a,b,b,b,a,a,b,b,a,b,3.3.4,表示与描述：关系描述子,骨架关系编码,用有向线段来描述一个图像的各个部分（例如同构区域），这个线段是通过头尾连接等方法得到的。线段之间的不同运算代表了区域的不同组合。,当图像的连通性可以通过首尾相接或其它连续的方式描述的时候，最适于使用这种串来描述。,3.3.4,表示与描述：关系描述子,骨架关系编码,a+b,a-b,a b,a*b,a,a,a,a,b,b,b,b,编码,3.3.4,表示与描述：关系描述子,方向关系编码,跟踪对象的边界，将跟踪得到的线段按照方向或长度来编码,a1,a2,a5,a7,a8,a3,a4,a6,a1a8a7a6a5a4a3a2,3.3.4,表示与描述：关系描述子,内角关系编码,根据角度范围不同，编码为,8,个符号,即,:,a1:0-45;a2:45-90;a3:90-135;,;,a8:315-360,举例：,a3a3a3a3a3a3a3a3,a2a2a3a3,3.3.4,表示与描述：关系描述子,树结构关系,树结构中每个结点的意义和结点之间的关系最为重要,举例：,a,b,c,d,$,a,b,c,d,e,f,e,f,$,请提问,