特征表示与描述.ppt

图像分析系统的构成,知识库,3.图像处理与分析,3.2 特征表示与描述,3.2.1 特征表示与描述的基本概念3.2.2 表示法设计3.2.3 边界描述子3.2.4 区域描述子3.2.5 关系描述子,3.2.1 特征表示与描述的基本概念,基本概念特征表示与描述的定义：把图像分割后，为了进一步的处理，分割后的图像一般要进行形式化的表达和描述解决形式化表达问题一般有两种选择：1）根据区域的外部特征来进行形式化表示2）根据区域的内部特征（比较区域内部的象素值）来来进行形式化表示,3.2.1 特征表示与描述的基本概念,基本概念选择表达方式，要本着使数据变得更有利于下一步的计算工作。下一步工作是基于所选的表达方式描述这个区域，一般情况下：1）如果关注的焦点是形状特性，选择外部表示方式2）如果关注的焦点是反射率特性，如颜色、纹理时，选择内部表示方式3）所选表示方式，应该对尺寸、变换、旋转等变量尽可能的不敏感,3.2.1 特征表示与描述的基本概念,(1)参数边界：将目标的轮廓线表示为参数曲线(2)边界点集合：各点间没有顺序(3)曲线逼近：用几何基元近似地逼近,3.2.2 表示法设计,基于边界的表示法设计1.链码2.多边形逼近3.外形特征4.边界分段5.区域骨架,3.2.2 表示法设计,1.链码定义：1）链码是一种边界的编码表示法。2）用边界的方向作为编码依据。为简化边界的描述。一般描述的是边界点集。,0,1,2,3,0,1,4,6,7,2,3,5,4-链码,8-链码,3.2.2 表示法设计,链码举例：,4-链码：000033333322222211110011,3.2.2 表示法设计,1.链码算法：给每一个线段边界一个方向编码。有4-链码和8-链码两种编码方法。从起点开始，沿边界编码，至起点被重新碰到，结束一个对象的编码。,3.2.2 表示法设计,1.链码问题1：1）链码相当长。2）噪音会产生不必要的链码。改进1：1）加大网格空间。2）依据原始边界与结果的接近程度，来确定新点的位置。,3.2.2 表示法设计,链码举例：,4-链码：003332221101,3.2.2 表示法设计,1.链码问题2：1）由于起点的不同，造成编码的不同2）由于角度的不同，造成编码的不同改进2：1）从固定位置作为起点(最左最上)开始编码2）通过使用链码的首差代替码子本身的方式,3.2.2 表示法设计,1.链码循环首差链码：用相邻链码的差代替链码例如：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.2.2 表示法设计,链码平滑将原始的链码序列用较简单的序列代替虚线箭头：原始的在象素p和q之间的8-连通链码实线箭头：用来替换原始序列的新序列,3.2.2 表示法设计,3.2.2 表示法设计,链码平滑示例空心圆：平滑后被除去的原轮廓点,3.2.2 表示法设计,2.多边形逼近基本思想：用最少的多边形线段，获取边界形状的本质。寻找最小基本多边形的方法一般有两种：1）点合成法2）边分裂法,3.2.2 表示法设计,2.多边形逼近点合成算法思想举例：,R,R T,3.2.2 表示法设计,2.多边形逼近点合成算法：1）沿着边界选两个相邻的点对，计算首尾连接直线段与原始折线段的误差R。2）如果误差R小于预先设置的阈值T。去掉中间点，选新点对与下一相邻点对，重复1）；否则，存储线段的参数，置误差为0，选被存储线段的终点为起点，重复1）2）。3）当程序的第一个起点被遇到，程序结束。,R,R T,3.2.2 表示法设计,2.多边形逼近点合成算法的问题：顶点一般不对应于边界的拐点（如拐角）。因为新的线段直到超过误差的阈值才开始。下面讲到的分裂法可用于缓解这个问题,3.2.2 表示法设计,2.多边形逼近边分裂算法思想举例：,3.2.2 表示法设计,2.多边形逼近边分裂算法：（1）连接边界线段的两个端点（如果是封闭边界，连接最远点）；（2）如果最大正交距离大于阈值，将边界分为两段，最大值点定位一个顶点。重复（1）；（3）如果没有超过阈值的正交距离，结束。,3.2.2 表示法设计,3.外形特征基本思想：外形特征是一种用一维函数表达边界的方法。基本思想是把边界的表示降到一维函数,3.2.2 表示法设计,3.外形特征函数定义(1)质心角函数：边上的点到质心的距离r，作为夹角的的函数r(),A,r,r(),2,A,3.2.2 表示法设计,3.外形特征举例：,A,r,r(),2,A,3.2.2 表示法设计,3.外形特征问题：函数过分依赖于旋转和比例的变化改进：对于旋转两种改进：a.选择离质心最远的点作为起点b.选择从质心到主轴最远的点作为起点对于比例变换：对函数进行正则化，使函数值总是分布在相同的值域里，比如说0，1,3.2.2 表示法设计,(2)y-s曲线（切线角为弧长的函数）沿边界围绕目标一周，在每个位置作出该点切线与一个参考方向（如横轴）的角度值 水平直线段对应边界上的直线段（y不变）,3.2.2 表示法设计,(3).斜率密度函数 将y-s曲线沿 y 轴投影 切线角的直方图h(q)切线角有较快变化的边界段对应较深的谷,3.2.2 表示法设计,4.边界分段基本概念：一个任意集合S（区域）的凸起外缘H是：包含S的最小凸起的集合H-S的差的集合被称为集合S的凸起补集D,S,S,D,S+D=H,3.2.2 表示法设计,4.边界分段分段算法：给进入和离开凸起补集D的变换点打标记来划分边界段。优点：不依赖于方向和比例的变化,S,3.2.2 表示法设计,4.边界分段问题：噪音的影响，导致出现零碎的划分。解决的方法：先平滑边界，或用多边形逼近边界，然后再分段,3.2.2 表示法设计,(1)区域分解：简单的单元形式(2)围绕区域：外接圆，外包围矩形(3)内部特征：内部象素集合,3.2.2 表示法设计,基于区域的表示法设计1.空间占有数组2.四叉树3.围绕区域4.骨架,3.2.2 表示法设计,1.空间占有数组对图象 f(x,y)中任一点(x,y)：如果它在给定的区域内，就取 f(x,y)为1否则就取 f(x,y)为0所有f(x,y)为1的点组成的集合就代表了所要表示的区域,3.2.2 表示法设计,2.四叉树基本思路分层分解图象利用金字塔式的数据结构四叉树表达法每次将图象一分为四树结构 T=N,A结点集n1,.弧集ai,.,3.2.2 表示法设计,四叉树表达图示表达优点：“粗略信息优先”显示结点数目,3.2.2 表示法设计,3.围绕区域(1)外接盒（Feret box）：包含目标区域的最小的长方形（朝向特定的参考方向）(2)围盒（minimum enclosing rectangle，MER）：包含目标区域的（可朝向任何方向）最小长方形(3)凸包：,3.2.2 表示法设计,4.区域骨架基本思想表示一个平面区域结构形状的重要方法是把它削减成图形。这种削减可以通过细化（也称为抽骨架）算法，获取区域的骨架来实现Blum的中轴变换方法（MAT）设:R是一个区域，B为R的边界点，对于R中的点p，找p在B上“最近”的邻居。如果p有多于一个的邻居，称它属于R的中轴（骨架）,3.2.2 表示法设计,4.区域骨架基本思想问题：计算量大,p,R,B,3.2.2 表示法设计,4.区域骨架算法改进思想在保证产生正确的骨架的同时，改进算法的效率。比较典型的是一类细化算法，通过查找表不断删去边缘，但保证删除满足：（1）不移去端点（2）不破坏连通性（3）不引起区域的过度腐蚀,2.2 特征表示与描述:表示法设计,区域骨架一种细化二值区域的算法假设区域内的点值为1，背景值为0这个方法由对给定区域的边界点连续进行两个基本操作构成这里边界点是指任何值为1且至少有一个8邻域上的点为0的象素,2.2 特征表示与描述:表示法设计,基本操作1对于满足以下四个条件的边界点打标记准备(1)2N(p1)6 其中N(p1)是点p1的邻域中1的个数，即：N(p1)=p2+p3+p9(2)S(p1)=1 其中S(p1)是按p2,p3,p9顺序，0-1转换的个数(3)p2*p4*p6=0 p2、p4、p6 至少有一个0）(4)p4*p6*p8=0（p4、p6、p8 至少有一个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,2.2 特征表示与描述:表示法设计,区域骨架 所有条件都满足，才打删除标记。删除并不立即进行，而是等到对所有边界点都打完标记后，再把作了标记的点一起删除举例:N(p1)=4S(p1)=3p2*p4*p6=0p4*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,2.2 特征表示与描述:表示法设计,区域骨架基本操作2条件(a)、(b)与操作1相同 条件(c)、(d)改为：c)p2*p4*p8=0d)p2*p6*p8=0,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,2.2 特征表示与描述:表示法设计,区域骨架细化算法细化算法的一轮操作包括：按操作1，给边界点打标记删除点按操作2，给边界点打标记删除点这个基本过程反复进行，直至没有点可以删除为止。此时算法终止。,3.2.2 表示法设计,4.区域骨架例:,4.区域骨架,由骨架可恢复出原始区域沿骨架作相切圆，取包络,3.2.2 表示法设计,傅立叶变换表达,1）基本思想：（1）对于XY平面上的每个边界点，将其坐标用复数表示为：s(k)=x(k)+jy(k)k=0,1,N-1,y0,y1,x0,x1,jy,x,x(k)=xky(k)=yk,傅立叶变换表达,1）基本思想：（2）进行离散傅立叶变换 N-1a(u)=1/N s(k)exp(-j2uk/N)u=0,1,N-1 u=0 N-1s(k)=a(u)exp(j2uk/N)k=0,1,N-1 u=0系数a(u)被称为边界的傅立叶描述子,傅立叶变换表达,1）基本思想：（3）选取整数 MN-1，进行逆傅立叶变换（重构）M-1 s(k)=a(u)exp(j2uk/N)k=0,1,N-1 u=0 这时，对应于边界的点数没有改变，但在重构每一个点所需要的计算项大大减少了。如果边界点数很大，M一般选为2的指数次方的整数。,傅立叶变换表达,2）M的选取与描述符的关系 在上述方法中，相当于对于u M-1的部分舍去不予计算。由于傅立叶变换中高频部分对应于图像的细节描述，因此M取得越小，细节部分丢失得越多。,M=4,M=61,M=62,N=64,傅立叶变换表达,3）使用价值1）较少的傅立叶描述子（如4个），就可以获取边界本质的整体轮廓2）这些带有边界信息的描述子，可以用来区分明显不同的边界,傅立叶变换表达,4）优点1）使用复数作为描述符，对于旋转、平移、放缩等操作和起始点的选取不十分敏感。2）几何变换的描述子可通过对函数作简单变换来获得,3.2.3 边界描述子,1.简单描述子2.形状数3.边界矩,3.2.3 边界描述子,1.）边界的长度边界/轮廓长度（区域周长）对区域 R，轮廓点 P：P本身属于 R P的邻域中有象素不属于 R,1.简单描述子,3.2.3 边界描述子,1）边界的长度!区域的轮廓点和内部点要采用不同的连通性来定义(1)内部点8-方向连通，轮廓为4-方向连通(2)内部点4-方向连通，轮廓为8-方向连通,3.2.3 边界描述子,1）边界的长度(1)4-方向连通轮廓B4(2)8-方向连通轮廓B8使用单位长链码2个象素间直线段 2个象素间对角线段,3.2.3 边界描述子,2）边界的直径边界上相隔最远2点之间的距离 距离度量：DE()，D4()，D8(),3.2.3 边界描述子,3.）曲率斜率、曲率、角点（局部特性）斜率：轮廓点的（切线）指向曲率：斜率的改变率曲率大于零，曲线凹向朝着法线正向曲率小于零，曲线凹向朝着法线负向角点：曲率的局部极值点,3.2.3 边界描述子,边界的曲率：曲率被描述为斜率的变化率。近似用相邻边界线段（描述为直线）的斜率差作为在边界线交点处的曲率描述子。交点a处的曲率为 dk=k1 k2 其中k1、k2 为相邻线段的斜率,a,k1,k2,3.2.3 边界描述子,边界的凸线段点：当顶点p上的曲率是非负时，称其为凸线段上的点边界的凹线段点：当顶点p上的曲率为负时，称其为凹线段上的点,P1,P2,3.2.3 边界描述子,2.形状数链码的实用化形状数定义：最小循环首差链码。循环首差链码：用相邻链码的差代替链码例如：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.2.3 边界描述子,2.形状数形状数定义：例如：4-链码：10103322 循环首差：33133|030形状数：03033133形状数序号n的定义：形状数中阿拉伯数字的个数。上例序数为8 对于封闭边界序号一定是偶数。如order4、6、8。,3.2.3 边界描述子,2.形状数序号为4、6、8的形状数举例：,序号4,链码：0321首差：3333形状：3333,序号6,链码：003221首差：303303形状：033033,序号8,链码：00032221首差：30033003形状：00330033,3.2.3 边界描述子,2.形状数序号为6的形状数举例：,序号6,链码：033211首差：330330形状：033033,序号6,链码：003221首差：303303形状：033033,形状数与方向无关,3.2.3 边界描述子,2.形状数序号为8的形状数举例：,序号8,链码：03032211首差：33133030形状：03033133,序号8,链码：00332211首差：30303030形状：03030303,序号8,链码：00323211首差：30331330形状：03033133,边界描述子,2.形状数问题：虽然链码的首差是不依赖于旋转的，但一般情况下边界的编码依赖于网格的方向。改进：规整化网格方向，具体方法如下：,2.3 特征表示与描述：边界描述子,2.形状数几个基本概念：边界最大轴a:是连接距离最远的两个点的线段边界最小轴b:与最大轴垂直，且其长度确定的包围盒刚好包围边界。边界离心率c：最大轴长度与最小轴长度的比c=a/b基本矩形:包围边界的矩形。,2.3 特征表示与描述：边界描述子,2.形状数基本概念举例,2.3 特征表示与描述：边界描述子,2.形状数规整化网格方向算法的思想：大多数情况下，将链码网格与基本矩形对齐，即可得到一个唯一的形状数。规整化网格方向的一种算法如下：（1）首先确定形状数的序号n；（2）在序号为n的矩形形状数中，找出一个与给定形状的基本矩形的离心率最接近的形状数,2.3 特征表示与描述：边界描述子,2.形状数（3）然后再用这个矩形与基本矩形对齐，构造网格。（4）用获得链码的方法得到链码；（5）再得到循环首差；（6）首差中的最小循环数即为形状数。例如:如果n=12，所有序号为12的矩形（即周长为12）为2*4，3*3，1*5。如果2*4矩形的离心率最接近于给定边界的基本矩形的离心率，我们建立一个2*4的网格。,2.3 特征表示与描述：边界描述子,2.形状数规整化网格方向算法举例：,链码：000033222121首差：300030300313形状：000303003133,0,1,2,3,3.2.3 边界描述子,形状数的阶形状数序列的长度闭合曲线阶是偶数凸形区域形状数的 阶对应区域边界 外包矩形的周长,3.2.3 边界描述子,3.边界矩基本思想：将描述形状的任务减少至描述一个一维函数，边界段和特征的形状可以用矩量来量化地描述矩量的定义：把边界当作直方图函数：g(r),r,g(r),3.2.3 边界描述子,3.边界矩矩量的定义：Ln(r)=(ri-m)ng(ri)i=1 L其中 m=rig(ri)i=12描述了曲线相对于均值的分布3描述了曲线相对于均值的对称性 这里L是边界上点的数目,n(r)是边界的矩量,3.2.3 边界描述子,矩量的优点：实现是直接的附带了一种关于边界形状的“物理”解释对于旋转的不敏感性为了使大小比例不敏感，可以通过伸缩r的范围来将大小正则化。,3.2.4 区域描述子,利用处在目标区域内的象素集合来描述区域的特点/特性1.简单区域描述符2.拓扑描述符 3.不变矩,3.2.4 区域描述子,1)区域面积基于对象素个数的计数 2)区域重心基于区域所有象素计算 3)区域密度需结合灰度图和分割图,1.简单区域描述符,1)区域面积区域面积的不同计算方法利用对象素记数求区域面积，最简单合理,区域描述子,1)区域面积多边形区域面积？NB是正好处在Q的轮廓上离散点的个数NI是Q的内部点的个数 令R为Q中所包含点的集合|R|=NB+NI,区域描述子,1)区域面积多边形区域面积计算示例NI=71，NB=10，A(Q)=75 多边形Q所定义的面积轮廓（点集）所定义的面积,区域描述子,2)区域重心对非规则物体，其重心坐标和几何中心坐标常不相同,重心,几何中心,密度加权的目标重心,区域描述子,3)区域密度(1)透射率（transmission）T=穿透目标的光/入射的光(2)光密度（optical density）入射的光与穿透目标的光的比（透射率的倒数），取以10为底的对数OD=log(1/T)=logT,区域描述子,3)区域密度(3)积分光密度（integrated optical density）积分光密度是直方图中各灰度的加权和,区域描述子,2.拓扑描述子 拓扑学研究图形不受畸变变形（不包括撕裂或粘贴）影响的性质拓扑性质：全局性质，与距离无关欧拉数 1，2，1，0 欧拉数描述了区域的连通性 H：区域内的孔数 C：区域内的连通组元个数,区域描述子,对一幅二值图象A，可以定义两个欧拉数(1)4-连通欧拉数E4(A)4-连通的目标个数减去8-连通的孔数(2)8-连通欧拉数E8(A)8-连通的目标个数减去4-连通的孔数,区域描述子,多边形网全由直线段（包围）构成的区域集合 欧拉公式 V：顶点数 B：边线数 F：面数,区域描述子,5.不变矩：用所有属于区域内的点计算f(x,y)的 p+q 阶矩f(x,y)的 p+q 阶中心矩f(x,y)的归一化的中心矩,区域描述子,3.2.5 关系描述子,1.目标标记和计数2.点目标的分布3.阶梯关系编码4.边界关系编码5.树结构关系编码,1、目标标记和计数1）象素标记：检查当前象素与之前若干近邻象素的连通性考虑4-连通的情况 新的标记 标记为A 标记为B 标记为A/B 第1次被扫描到 与A连通 与B连通 A和B等价,3.2.5 关系描述子,2）游程连通性分析,3.2.5 关系描述子,当图象中有许多个同类的目标时，为方便研究它们之间的关系，常将各个目标抽象为点目标对点目标集合，目标间相互关系常比单个目标在图象中的位置或单个目标本身的性质更重要 随机分布 聚类分布 规则分布,3.2.5 关系描述子,2.点目标的分布,根据分布的统计来区分不同分布 将视场分成一些子区域m：子区域内目标数的均值s 2：子区域内目标数的方差(1)s 2=m：泊松分布(2)s 2 m：聚类分布(3)s 2 m：均匀分布,3.2.5 关系描述子,3.2.4 关系描述子,基本思想：通过挖掘各个成分之间的结构关系来描述边界图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串主导思想是考虑物体各个部分的连接线段,3.2.4 关系描述子,3.阶梯关系编码对于如下阶梯形边界，定义两个基本元素a,b,a,b,a,a,a,b,b,b,3.2.4 关系描述子,3.阶梯结构关系定义如下产生规则：(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.2.4 关系描述子,4.边界关系编码用有向线段来描述一个图像的各个部分（例如同构区域），这个线段是通过头尾连接等方法得到的。线段之间的不同运算代表了区域的不同组合。当图像的连通性可以通过首尾相接或其它连续的方式描述的时候，最适于使用这种串来描述。,3.2.4 关系描述子,c+b,c-a,a b,a*b,c,c,a,a,a,a,b,b,编码,a,b,c,d,a+a+b+e+e+e+a,e,f,3.2.4 关系描述子,利用有向线段描述复杂结构,3.2.4 关系描述子,5.树结构关系树结构中每个结点的意义和结点之间的关系最为重要举例：,a,b,c,d,$,a,b,c,d,e,f,e,f,$,