图像表示与描述课件.ppt

1、第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述数字图像处理北京大学计算机研究所 陈晓鸥第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述第三节 表示与描述3.3.1 表示与描述的基本概念3.3.2 表示法设计3.3.3 边界描述子3.3.4 关系描述子第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.1 表示与描述的基本概念 基本概念在用前一章的方法，把图像分割后，为了进一步的处理，分割后的图像一般要进行形式化的表达和描述解决形式化表达问题一般有两种选择：1）根据区域的外部特征来进行形式化表示2）根据区域的内部

2、特征（比较区域内部的象素值）来来进行形式化表示第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.1表示与描述的基本概念 基本概念选择表达方式，要本着使数据变得更有利于下一步的计算工作。下一步工作是基于所选的表达方式描述这个区域，一般情况下：1）如果关注的焦点是形状特性，选择外部表示方式2）如果关注的焦点是反射率特性，如颜色、文理时，选择内部表示方式。3）所选表示方式，应该对尺寸、变换、旋转等变量尽可能的不敏感第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 表示法设计链码多边形逼近外形特征边界分段区域骨

3、架第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 链码定义：1）链码是一种边界的编码表示法。2）用边界的方向作为编码依据。为简化边界的描述。一般描述的是边界点集。0123014672354-链码8-链码第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 链码算法：给每一个线段一个方向编码。有4-链码和8-链码两种编码方法。从起点开始，沿边界编码，至起点被重新碰到，结束一个对象的编码。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描

4、述:表示法设计 链码举例：4-链码：000033333322222211110011第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 链码问题1：1）链码相当长。2）噪音会产生不必要的链码。改进1：1）加大网格空间。2）依据原始边界与结果的接近程度，来确定新点的位置。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 链码举例：4-链码：003332221101第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 链码问题

5、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=12-3=-1(3)0-1=-1(3)2-2=0第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表

6、示法设计 链码应用背景：如果边界的本身对于旋转和比例修改来说是无变化的，使用链码才是正确的。一般来说这是不可能的，实际应用时还需要改进。用链码后，对象只要用1)起点坐标，2)周长（边界点数）3)链码，4)对象编号，就可以描述。链码一般用于一幅图像中有多个对象的情况，对单个对象不适用。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 多边形逼近基本思想：用最少的多边形线段，获取边界形状的本质。寻找最小基本多边形的方法一般有两种：点合成法和边分裂法第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与

7、描述:表示法设计 多边形逼近点合成算法思想举例：第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 多边形逼近合成点算法：1）沿着边界选两个相邻的点对，计算首尾连接直线段与原始折线段的误差。2）如果误差小于预先设置的阈值。去掉中间点，选新点对与下一相邻点对，重复1）；否则，存储线段的参数，置误差为0，选被存储线段的终点为起点，重复1）2）。3）当程序的第一个起点被遇到，程序结束。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 多边形逼近合成点算法的问题：顶点一般不对应于边界的

8、拐点（如拐角）。因为新的线段直到超过误差的阈值才开始。下面讲到的分裂法可用于缓解这个问题第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 多边形逼近边分裂算法思想举例：第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 多边形逼近分裂边算法：（1）连接边界线段的两个端点（如果是封闭边界，连接最远点）；（2）如果最大正交距离大于阈值，将边界分为两段，最大值点定位一个顶点。重复（1）；（3）如果没有超过阈值的正交距离，结束。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示

9、与描述表示与描述3.3.2 表示与描述:表示法设计 外形特征基本思想：外形特征是一种用一维函数表达边界的方法。基本思想是把边界的表示降到一维函数第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 外形特征函数定义质心角函数：边上的点到质心的距离r，作为夹角的 的函数。A r r()2 A第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 外形特征举例：A r r()2 A第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计

10、外形特征问题：函数过分依赖于旋转和比例的变化改进：对于旋转两种改进：a.选择离质心最远的点作为起点b.选择从质心到主轴最远的点作为起点 对于比例变换：对函数进行正则化，使函数值总是分布在相同的值域里，比如说0，1第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 边界分段基本概念：一个任意集合S（区域）的凸起外缘H是：包含S的最小凸起的集合 H-S的差的集合被称为集合S的凸起补集DSSDS+D=H第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 边界分段分段算法：给进入和离开凸

11、起补集的变换点打标记来划分边界段。优点：不依赖于方向和比例的变化S第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 边界分段问题：噪音的影响，导致出现零碎的划分。解决的方法：先平滑边界，或用多边形逼近边界，然后再分段第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架基本思想 表示一个平面区域结构形状的重要方法是把它削减成图形。这种削减可以通过细化（也称为抽骨架）算法，获取区域的骨架来实现 Blum的中轴变换方法（MAT）设:R是一个区域，B为R的边界点，对于R中的点p

12、，找p在B上“最近”的邻居。如果p有多于一个的邻居，称它属于R的中轴（骨架）第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架基本思想问题：计算量大pRB第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架算法改进思想 在保证产生正确的骨架的同时，改进算法的效率。比较典型的是一类细化算法，它们不断删去边缘，但保证删除满足：（1）不移去端点（2）不破坏连通性（3）不引起区域的过度腐蚀第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.

13、2 表示与描述:表示法设计 区域骨架一种细化二值区域的算法 假设区域内的点值为1，背景值为0 这个方法由对给定区域的边界点连续进行两个基本操作构成 这里边界点是指任何值为1且至少有一个8邻域上的点为0的象素第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架基本操作1对于满足以下四个条件的边界点打标记准备删除：(a)2 N(p1)6 其中N(p1)是点p1的邻域中1的个数，即：N(p1)=p2+p3+p9(b)S(p1)=1 其中S(p1)是按p2,p3,p9顺序，0-1转换的个数(c)p2*p4*p6=0 （p2、p4、p6

14、至少有一个0）(d)p4*p6*p8=0 （p4、p6、p8 至少有一个0）p9 p2p1p8p3p4p7 p6 p5p9 p2p1p8p3p4p7 p6 p5p9 p2p1p8p3p4p7 p6 p5第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架 所有条件都满足，才打删除标记。删除并不立即进行，而是等到对所有边界点都打完标记后，再把作了标记的点一起删除。举例:N(p1)=4S(p1)=3p2*p4*p6=0p4*p6*p8=0 第2个条件没满足不打标记00p1110101p9 p2p1p8p3p4p7 p6 p5p9 p

15、2p1p8p3p4p7 p6 p5第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架基本操作2条件(a)、(b)与操作1相同 条件(c)、(d)改为：c)p2*p4*p8=0d)p2*p6*p8=0p9 p2p1p8p3p4p7 p6 p5p9 p2p1p8p3p4p7 p6 p5第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架细化算法细化算法的一轮操作包括：按操作1，给边界点打标记删除点 按操作2，给边界点打标记删除点 这个基本过程反复进行，直至没有点可以

16、删除为止。此时算法终止。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架算法分析：（1）条件a)的分析：当轮廓点p1的8邻域上有1个或7个值为1的点时，不满足条件a。有1个点说明：p1是骨架上的终点，显然不能删除 有7个点说明：如果删除p1会引起区域的腐蚀（2）条件b)的分析：当p1在宽度为1的笔划上时，不满足条件b。因而该条件保证了骨架的连续性。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架算法分析：（3）当(p4=0 or p6=0)or(p2=0

17、and p8=0)时，条件c,d同时满足。满足这个条件的点可能是右边、下边、左上角的边界点。任何一种情况下，p1都不是骨架的一部分，应被删除。当(p4=0 and p6=0)or(p2=0 or p8=0)时，条件c,d同时满足。满足这个条件的点可能是左边、上边、右下角的边界点，应被删除。p9 p2p1p8p3p4p7 p6 p5p9 p2p1p8p3p4p7 p6 p5第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.2 表示与描述:表示法设计 区域骨架例:第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描

18、述子 边界描述子简单描述子形状数傅立叶描述子矩量第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 简单描述子边界的周长：是最简单的描述符之一。沿轮廓线计算象素的个数，给出了一个长度的近似估计边界的直径：边界B的直径是：Diam(B)=maxD(pi,pj)D是欧氏距离或几何距离，pi,pj是边界上的点。直径的长度和直径的两个端点连线（这条线被称为边界的主轴）的方向，是关于边界的有用的描述符。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 简单描述子边界的直径举例第三章第三章

19、 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 简单描述子边界的曲率：曲率被描述为斜率的变化率。近似：用相邻边界线段（描述为直线）的斜率差作为在边界线交点处的曲率描述子。交点a处的曲率为 dk=k1 k2 其中k1、k2 为相邻线段的斜率ak1k2第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 简单描述子边界的凸线段点：当顶点p上的斜率是非负时，称其为凸线段上的点边界的凹线段点：当顶点p上的斜率为负时，称其为凹线段上的点第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述

20、表示与描述3.3.3 表示与描述：边界描述子 简单描述子边界的凸线段点P1：边界的凹线段点P2：P1P2第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述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 表示与描述：边界描述子 形状数形状数定义

21、：例如：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 表示与描述：边界描

22、述子 形状数形状数例如：序号6链码：033211首差：330330形状：033033序号6链码：003221首差：303303形状：033033第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 形状数问题：虽然链码的首差是不依赖于旋转的，但一般情况下边界的编码依赖于网格的方向。改进：规整化网格方向，具体方法如下：第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 形状数几个基本概念：边界最大轴a:是连接距离最远的两个点的线段 边界最小轴b:与最大轴垂直，且其长度确定的包围盒刚好

23、包围边界。边界离心率c：最大轴长度与最小轴长度的比c=a/b 基本矩形:包围边界的矩形。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 形状数基本概念举例边界最大轴a边界最小轴b基本矩形第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 形状数 规整化网格方向算法的思想：大多数情况下，将链码网格与基本矩形对齐，即可得到一个唯一的形状数。对一个给定的形状序号，处理步骤如下：（1）我们找出一个序号为n的矩形，它的离心率最接近于给定形状的基本矩形的离心率。第三章第三章 数字图像分析

24、数字图像分析 第三节第三节 表示与描述表示与描述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形状：00030300313

25、30123第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 傅立叶描述子1）基本思想：（1）对于XY平面上的每个边界点，将其坐标用复数表示为：s(k)=x(k)+jy(k)k=0,1,N-1y0y1x0 x1jyxx(k)=xky(k)=yk第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 傅立叶描述子1）基本思想：（2）进行离散傅立叶变换 N-1a(u)=1/N s(k)exp(-j2 uk/N)u=0,1,N-1 u=0 N-1s(k)=a(u)exp(j2 uk/N)k

26、=0,1,N-1 u=0a(u)被称为边界的傅立叶描述子第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 傅立叶描述子1）基本思想：（3）选取整数 MN-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的选取与描述符的关系 在上述方

27、法中，相当于对于u M-1的部分舍去不予计算。由于傅立叶变换中高频部分对应于图像的细节描述，因此M取得越小，细节部分丢失得越多。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 傅立叶描述符3）优点（1）使用复数作为描述符，对于旋转、平移、放缩等操作和起始点的选取不十分敏感。（2）以上几何变换均可以通过对描述子函数作简单变换来获得。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 矩量基本思想：将描述形状的任务减少至描述一个一维函数，边界段和特征的形状可以用矩量来量化地描述矩

28、量的定义：把边界当作直方图函数：g(r)rg(r)第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 矩量矩量的定义：L n(r)=(ri-m)ng(ri)i=1 L其中 m=rig(ri)i=1这里L是边界上点的数目,n(r)是边界的矩量第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：边界描述子 矩量矩量的优点：实现是直接的 附带了一种关于边界形状的“物理”解释 对于旋转的不敏感性 为了使大小比例不敏感，可以通过伸缩r的范围来将大小正则化。第三章第三章 数字图像分析数字图像分析 第三节

29、第三节 表示与描述表示与描述3.3.3 表示与描述：关系描述子 关系描述子基本思想阶梯关系编码骨架关系编码方向关系编码内角关系编码树结构关系编码第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.3 表示与描述：关系描述子 基本思想：通过挖掘各个成分之间的结构关系来描述边界图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串主导思想是考虑物体各个部分的连接线段第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.4 表示与描述：关系描述子 阶梯关系编码对于如下阶梯形边界，定义两个基本元素a,baba

30、aabbb第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述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)aaabbbaabbab第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.4 表示与描述：关系描述子 骨架关系编码用有向线段来描述一个图像的各个部分（例如同构区域），这个线段是通过头尾连接等方法得到的。线段之间的不同运算代表了区域的不同组合。当图像的连通性可以通过首尾相接或其它连续的方式描述的时候，最

31、适于使用这种串来描述。第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.4 表示与描述：关系描述子 骨架关系编码a+ba-ba ba*baaaabbbb编码第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.4 表示与描述：关系描述子 方向关系编码 跟踪对象的边界，将跟踪得到的线段按照方向或长度来编码a1a2a5a7a8a3a4a6a1a8a7a6a5a4a3a2第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.4 表示与描述：关系描述子 内角关系编码根据角度范围不同，编码为8个符号即:a1:0-45;a2:45-90;a3:90-135;a8:315-360举例：a3a3a3a3a3a3a3a3a2a2a3a3第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述3.3.4 表示与描述：关系描述子 树结构关系树结构中每个结点的意义和结点之间的关系最为重要举例：abcd$abcdefef$第三章第三章 数字图像分析数字图像分析 第三节第三节 表示与描述表示与描述请提问