数字图像处理 北京大学计算机研究所 陈晓鸥.

Presentation on theme: "数字图像处理 北京大学计算机研究所 陈晓鸥."— Presentation transcript:

1 数字图像处理 北京大学计算机研究所 陈晓鸥

2 第三章 数字图像分析 知识库 图像分析系统的构成 分割 预处理 识别 与 解释 中级处理 特征表示与描述 结果 低级处理 高级处理 图像获取
问题

3 第三节 特征表示与描述 3.3.1 特征表示与描述的基本概念 3.3.2 表示法设计 3.3.3 边界描述子 3.3.4 关系描述子

4 3.3.1 特征表示与描述的基本概念 基本概念 特征表示与描述的定义：
把图像分割后，为了进一步的处理，分割后的图像一般要进行形式化的表达和描述 解决形式化表达问题一般有两种选择： 1）根据区域的外部特征来进行形式化表示 2）根据区域的内部特征（比较区域内部的象素值）来来进行形式化表示

5 3.3.1 特征表示与描述的基本概念 基本概念 外部特征来进行形式化表示举例：

6 3.3.1 特征表示与描述的基本概念 基本概念 选择表达方式，要本着使数据变得更有利于下一步的计算工作。下一步工作是基于所选的表达方式描述这个区域，一般情况下： 1）如果关注的焦点是形状特性，选择外部表示方式 2）如果关注的焦点是反射率特性，如颜色、纹理时，选择内部表示方式 3）所选表示方式，应该对尺寸、变换、旋转等变量尽可能的不敏感

7 3.3.2 特征表示与描述:表示法设计 表示法设计 链码 多边形逼近 外形特征 边界分段 区域骨架

8 3.3.2 特征表示与描述:表示法设计 链码 定义：1）链码是一种边界的编码表示法。
2）用边界的方向作为编码依据。为简化边界的描述。一般描述的是边界点集。 1 2 3 1 4-链码 8-链码 2 4 5 7 3 6

9 3.3.2 特征表示与描述:表示法设计 链码举例： 4-链码：

10 3.3.2 特征表示与描述:表示法设计 链码 算法： 给每一个线段边界一个方向编码。 有4-链码和8-链码两种编码方法。
从起点开始，沿边界编码，至起点被重新碰到，结束一个对象的编码。

11 3.3.2 特征表示与描述:表示法设计 链码 问题1： 1）链码相当长。 2）噪音会产生不必要的链码。 改进1： 1）加大网格空间。
2）依据原始边界与结果的接近程度，来确定新点的位置。

12 3.3.2 特征表示与描述:表示法设计 链码举例： 4-链码：

13 3.3.2 特征表示与描述:表示法设计 链码 问题2： 1）由于起点的不同，造成编码的不同 2）由于角度的不同，造成编码的不同 改进2：
1）从固定位置作为起点(最左最上)开始编码 2）通过使用链码的首差代替码子本身的方式

14 3.3.2 特征表示与描述:表示法设计 链码 循环首差链码：用相邻链码的差代替链码
例如：4-链码 循环首差为： 循环首差：1 - 2 = -1(3) = 3 0 - 1 = -1(3) = 0 1 - 0 = = -1(3) 0 - 1 = -1(3) = 0

15 3.3.2 特征表示与描述:表示法设计 链码 应用背景：
如果边界的本身对于旋转和比例修改来说是无变化的，使用链码才是正确的。一般来说这是不可能的，实际应用时还需要改进。 用链码后，对象只要用1)起点坐标，2)周长（边界点数）3)链码，4)对象编号，就可以描述。 链码一般用于一幅图像中有多个对象的情况，对单个对象不适用。

16 3.3.2 特征表示与描述:表示法设计 多边形逼近 基本思想：用最少的多边形线段，获取边界形状的本质。 寻找最小基本多边形的方法一般有两种：
1）点合成法 2）边分裂法

17 3.3.2 特征表示与描述:表示法设计 多边形逼近 点合成算法思想举例： R R < T

18 3.3.2 特征表示与描述:表示法设计 多边形逼近 点合成算法： R 1）沿着边界选两个相邻的点对，计算首尾连接直线段与原始折线段的误差R。
2）如果误差R小于预先设置的阈值T。去掉中间点，选新点对与下一相邻点对，重复1）；否则，存储线段的参数，置误差为0，选被存储线段的终点为起点，重复1）2）。 3）当程序的第一个起点被遇到，程序结束。 R < T

19 3.3.2 特征表示与描述:表示法设计 多边形逼近 点合成算法的问题：
顶点一般不对应于边界的拐点（如拐角）。因为新的线段直到超过误差的阈值才开始。 下面讲到的分裂法可用于缓解这个问题

20 3.3.2 特征表示与描述:表示法设计 多边形逼近 边分裂算法思想举例：

21 3.3.2 特征表示与描述:表示法设计 多边形逼近 分裂边算法： （1）连接边界线段的两个端点（如果是封闭边界，连接最远点）；
（2）如果最大正交距离大于阈值，将边界分为两段，最大值点定位一个顶点。重复（1）； （3）如果没有超过阈值的正交距离，结束。

22 3.3.2 特征表示与描述:表示法设计 外形特征 基本思想： 外形特征是一种用一维函数表达边界的方法。基本思想是把边界的表示降到一维函数

23 3.3.2 特征表示与描述:表示法设计 外形特征 A A 函数定义——质心角函数：边上的点到质心的距离r，作为夹角的的函数r()
2

24 3.3.2 特征表示与描述:表示法设计 外形特征 举例： r  r() A A  2

25 3.3.2 特征表示与描述:表示法设计 外形特征 问题：函数过分依赖于旋转和比例的变化 改进： 对于旋转——两种改进：
a.选择离质心最远的点作为起点 b.选择从质心到主轴最远的点作为起点 对于比例变换： 对函数进行正则化，使函数值总是分布在相同的值域里，比如说[0，1]

26 3.3.2 特征表示与描述:表示法设计 边界分段 基本概念： 一个任意集合S（区域）的凸起外缘H是：包含S的最小凸起的集合
H-S的差的集合被称为集合S的凸起补集D S S D S + D = H

27 3.3.2 特征表示与描述:表示法设计 边界分段 分段算法： 给进入和离开凸起补集D的变换点打标记来划分边界段。
优点：不依赖于方向和比例的变化 S

28 3.3.2 特征表示与描述:表示法设计 边界分段 问题： 解决的方法： 噪音的影响，导致出现零碎的划分。
先平滑边界，或用多边形逼近边界，然后再分段

29 3.3.2 特征表示与描述:表示法设计 区域骨架 基本思想
表示一个平面区域结构形状的重要方法是把它削减成图形。这种削减可以通过细化（也称为抽骨架）算法，获取区域的骨架来实现 Blum的中轴变换方法（MAT） 设:R是一个区域，B为R的边界点，对于R中的点p，找p在B上“最近”的邻居。如果p有多于一个的邻居，称它属于R的中轴（骨架）

30 3.3.2 特征表示与描述:表示法设计 p 区域骨架 基本思想 问题：计算量大 B R

31 3.3.2 特征表示与描述:表示法设计 区域骨架 算法改进思想
在保证产生正确的骨架的同时，改进算法的效率。比较典型的是一类细化算法，它们不断删去边缘，但保证删除满足： （1）不移去端点 （2）不破坏连通性 （3）不引起区域的过度腐蚀

32 3.3.2 特征表示与描述:表示法设计 区域骨架 一种细化二值区域的算法 假设区域内的点值为1，背景值为0
这个方法由对给定区域的边界点连续进行两个基本操作构成 这里边界点是指任何值为1且至少有一个8邻域上的点为0的象素

33 3.3.2 特征表示与描述:表示法设计 区域骨架 基本操作1 p9 p2 p3 p9 p2 p3 p9 p2 p3 p8 p1 p4 p8
对于满足以下四个条件的边界点打标记准备删除： (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 至少有一个0） (d) p4 * p6 * p8 = 0 （p4 、p6 、p8 至少有一个0） p7 p6 p5 p7 p6 p5 p7 p6 p5

34 3.3.2 特征表示与描述:表示法设计 区域骨架 举例: N(p1) = 4 S(p1) = 3 p2*p4*p6 = 0
所有条件都满足，才打删除标记。删除并不立即进行，而是等到对所有边界点都打完标记后，再把作了标记的点一起删除 举例: N(p1) = 4 S(p1) = 3 p2*p4*p6 = 0 p4*p6*p8 = 0 第2个条件没满足不打标记 1 p9 p2 p3 p9 p2 p3 1 p1 p8 p1 p4 p8 p1 p4 1 1 p7 p6 p5 p7 p6 p5

35 3.3.2 特征表示与描述:表示法设计 区域骨架 基本操作2 条件(a)、(b)与操作1相同 条件(c)、(d)改为：
p9 p2 p3 p9 p2 p3 p8 p1 p4 p8 p1 p4 区域骨架 基本操作2 条件(a)、(b)与操作1相同 条件(c)、(d)改为： c’) p2* p4* p8= 0 d’) p2* p6* p8= 0 p7 p6 p5 p7 p6 p5

36 3.3.2 特征表示与描述:表示法设计 区域骨架 细化算法 细化算法的一轮操作包括： 按操作1，给边界点打标记——删除点
按操作2，给边界点打标记——删除点 这个基本过程反复进行，直至没有点可以删除为止。此时算法终止。

37 3.3.2 特征表示与描述:表示法设计 区域骨架 例:

38 3.3.3 特征表示与描述：边界描述子 边界描述子 简单描述子 形状数 傅立叶描述子 矩量

39 3.3.3 特征表示与描述：边界描述子 简单描述子 边界的周长： 是最简单的描述符之一。沿轮廓线计算象素的个数，给出了一个长度的近似估计
边界的直径：边界B的直径是： Diam(B) = max[D(pi, pj)] D是欧氏距离或几何距离，pi, pj是边界上的点。直径的长度和直径的两个端点连线（这条线被称为边界的主轴）的方向，是关于边界的有用的描述符。

40 3.3.3 特征表示与描述：边界描述子 简单描述子 边界的直径举例

41 3.3.3 特征表示与描述：边界描述子 简单描述子 a k2 边界的曲率： k1 曲率被描述为斜率的变化率。近似：
用相邻边界线段（描述为直线）的斜率差作为在边界线交点处的曲率描述子。 交点a处的曲率为 dk = k1 – k2 其中k1、k2 为相邻线段的斜率 a k1

42 3.3.3 特征表示与描述：边界描述子 简单描述子 P1 P2 边界的凸线段点： 当顶点p上的斜率是非负时，称其为凸线段上的点
边界的凹线段点： 当顶点p上的斜率为负时，称其为凹线段上的点

43 3.3.3 特征表示与描述：边界描述子 形状数——链码的实用化 形状数定义：最小循环首差链码。 循环首差链码：用相邻链码的差代替链码
例如：4-链码 循环首差为： 循环首差:1 - 2 = -1(3) = 3 0 - 1 = -1(3) = 0 1 - 0 = = -1(3) 0 - 1 = -1(3) = 0

44 3.3.3 特征表示与描述：边界描述子 形状数 形状数定义： 例如： 4-链码 ：10103322 循环首差 ：33133|030
例如： 链码 ： 循环首差 ：33133|030 形状数 ： 形状数序号n的定义： 形状数中阿拉伯数字的个数。上例序数为8 对于封闭边界序号一定是偶数。如order4、6、8。

45 3.3.3 特征表示与描述：边界描述子 形状数 序号为4、6、8的形状数举例： 序号4 序号6 序号8 链码：0321 首差：3333
形状：3333 链码：003221 首差：303303 形状：033033 链码： 首差： 形状：

46 3.3.3 特征表示与描述：边界描述子 形状数 序号为6的形状数举例： 序号6 序号6 形状数与方向无关 链码：003221
首差：303303 形状：033033 链码：033211 首差：330330 形状：033033 形状数与方向无关

47 3.3.3 特征表示与描述：边界描述子 形状数 序号为8的形状数举例： 序号8 序号8 序号8 链码：00332211
首差： 形状： 链码： 首差： 形状： 链码： 首差： 形状：

48 3.3.3 特征表示与描述：边界描述子 形状数 问题： 虽然链码的首差是不依赖于旋转的，但一般情况下边界的编码依赖于网格的方向。 改进：
规整化网格方向，具体方法如下：

49 3.3.3 特征表示与描述：边界描述子 形状数 几个基本概念： 边界最大轴a:是连接距离最远的两个点的线段
边界最小轴b:与最大轴垂直，且其长度确定的包围盒刚好包围边界。 边界离心率c：最大轴长度与最小轴长度的比 c = a / b 基本矩形: 包围边界的矩形。

50 3.3.3 特征表示与描述：边界描述子 形状数 基本概念举例 基本矩形 边界最大轴a 边界最小轴b

51 3.3.3 特征表示与描述：边界描述子 形状数 规整化网格方向算法的思想：
大多数情况下，将链码网格与基本矩形对齐，即可得到一个唯一的形状数。 规整化网格方向的一种算法如下 ： （1）首先确定形状数的序号n； （2）在序号为n的矩形形状数中，找出一个与给定形状的基本矩形的离心率最接近的形状数

52 3.3.3 特征表示与描述：边界描述子 形状数 （3）然后再用这个矩形与基本矩形对齐，构造网格。 （4）用获得链码的方法得到链码；
（5）再得到循环首差； （6）首差中的最小循环数即为形状数。 例如: 如果n=12，所有序号为12的矩形（即周长为12）为2*4，3*3，1*5。如果2*4矩形的离心率最接近于给定边界的基本矩形的离心率，我们建立一个2*4的网格。

53 3.3.3 特征表示与描述：边界描述子 形状数 规整化网格方向算法举例： 1 链码：000033222121 2
2 链码： 首差： 形状： 3

54 3.3.3 特征表示与描述：边界描述子 傅立叶描述子 1）基本思想： x(k) = xk y(k) = yk
（1）对于XY平面上的每个边界点，将其坐标用复数表示为： s(k) = x(k) + jy(k) k=0,1,…,N-1 jy x(k) = xk y(k) = yk y0 y1 x x0 x1

55 3.3.3 特征表示与描述：边界描述子 傅立叶描述子 1）基本思想： 系数a(u)被称为边界的傅立叶描述子 （2）进行离散傅立叶变换
N-1 a(u) =1/N ∑s(k)exp(-j2uk/N) u=0,1,…,N-1 u=0 s(k) = ∑a(u)exp(j2uk/N) k=0,1,…,N-1 系数a(u)被称为边界的傅立叶描述子

56 3.3.3 特征表示与描述：边界描述子 傅立叶描述子 1）基本思想： （3）选取整数 MN-1，进行逆傅立叶变换（重构）
s’(k) = ∑a(u)exp(j2uk/N) k=0,1,…,N-1 u=0 这时，对应于边界的点数没有改变，但在重构每一个点所需要的计算项大大减少了。如果边界点数很大，M一般选为2的指数次方的整数。

57 3.3.3 特征表示与描述：边界描述子 傅立叶描述符 2）M的选取与描述符的关系
在上述方法中，相当于对于u > M-1的部分舍去不予计算。由于傅立叶变换中高频部分对应于图像的细节描述，因此M取得越小，细节部分丢失得越多。 N=64 M=4 M=61 M=62

58 3.3.3 特征表示与描述：边界描述子 傅立叶描述符 3）使用价值 1）较少的傅立叶描述子（如4个），就可以获取边界本质的整体轮廓
2）这些带有边界信息的描述子，可以用来区分明显不同的边界

59 3.3.3 特征表示与描述：边界描述子 傅立叶描述符 4）优点 1）使用复数作为描述符，对于旋转、平移、放缩等操作和起始点的选取不十分敏感。
2）几何变换的描述子可通过对函数作简单变换来获得 几何变换 傅立叶描述子 原形 a(u) 旋转 a(u) = a(u) ej 平移 a(u) = a(u) + xy(u) 放缩 a(u) = a(u) 起点 a(u) = a(u) e-j2k0u/N

60 3.3.3 特征表示与描述：边界描述子 矩量 基本思想： 矩量的定义： g(r) r
将描述形状的任务减少至描述一个一维函数，边界段和特征的形状可以用矩量来量化地描述 矩量的定义： 把边界当作直方图函数：g(r) g(r) r

61 3.3.3 特征表示与描述：边界描述子 矩量 矩量的定义： n(r) = ∑(ri- m)ng(ri) 其中 m = ∑rig(ri)
L n(r) = ∑(ri- m)ng(ri) i=1 L 其中 m = ∑rig(ri) i=1 这里L是边界上点的数目, n(r)是边界的矩量

62 3.3.3 特征表示与描述：边界描述子 矩量 矩量的优点： 实现是直接的 附带了一种关于边界形状的“物理”解释 对于旋转的不敏感性
为了使大小比例不敏感，可以通过伸缩r的范围来将大小正则化。

63 3.3.4 特征表示与描述：关系描述子 关系描述子 基本思想 阶梯关系编码 骨架关系编码 方向关系编码 内角关系编码 树结构关系编码

64 3.3.4 特征表示与描述：关系描述子 基本思想： 通过挖掘各个成分之间的结构关系来描述边界
图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串 主导思想是考虑物体各个部分的连接线段

65 3.3.4 特征表示与描述：关系描述子 阶梯关系编码 对于如下阶梯形边界，定义两个基本元素a,b a a b a b b a b

66 3.3.4 特征表示与描述：关系描述子 阶梯结构关系 定义如下产生规则： (1) S->aA (2) A->bS
举例： a b a a b b a a a b b b (1,3) (1,2,1,3) (1,2,12,1,3)

67 3.3.4 特征表示与描述：关系描述子 骨架关系编码 用有向线段来描述一个图像的各个部分（例如同构区域），这个线段是通过头尾连接等方法得到的。线段之间的不同运算代表了区域的不同组合。 当图像的连通性可以通过首尾相接或其它连续的方式描述的时候，最适于使用这种串来描述。

68 3.3.4 特征表示与描述：关系描述子 骨架关系编码 b a e c f d c a a a a c b b 编码 c + b c - a
a × b a * b a + a + b + e + e + e + a

69 3.3.4 特征表示与描述：关系描述子 方向关系编码 a1a8a7a6a5a4a3a2 跟踪对象的边界，将跟踪得到的线段按照方向或长度来编码

70 3.3.4 特征表示与描述：关系描述子 内角关系编码 a3a3a3a3a3a3a3a3 a2a2a3a3 根据角度范围不同，编码为8个符号
举例： a3a3a3a3a3a3a3a3 a2a2a3a3

71 3.3.4 特征表示与描述：关系描述子 树结构关系 树结构中每个结点的意义和结点之间的关系最为重要 举例： $ a c e b d f $

72 请提问

73 3.3.2 特征表示与描述:表示法设计 区域骨架 算法分析：
1）条件a)的分析：当轮廓点p1的8邻域上有1个或7个值为1的点时，不满足条件a。 有1个点说明：p1是骨架上的终点，显然不能删除 有7个点说明：如果删除p1会引起区域的腐蚀 2）条件b)的分析：当p1在宽度为1的笔划上时，不满足条件b。因而该条件保证了骨架的连续性。

74 3.3.2 特征表示与描述:表示法设计 区域骨架 算法分析：
p9 p2 p3 p9 p2 p3 p8 p1 p4 p8 p1 p4 区域骨架 算法分析： （3）当(p4=0 or p6=0)or(p2=0 and p8=0)时，条件c,d同时满足。满足这个条件的点可能是右边、下边、左上角的边界点。任何一种情况下，p1都不是骨架的一部分，应被删除。 当(p4=0 and p6=0)or(p2=0 or p8=0)时，条件c’,d’同时满足。满足这个条件的点可能是左边、上边、右下角的边界点，应被删除。 p7 p6 p5 p7 p6 p5