完整版图像特征表示与描述课件.ppt

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