第三章数字图像分析第三节特征表示与描述数字图像处理北京大学计算机研究所 陈晓鸥第三章数字图像分析第三节特征表示与描述
图像分析系统的构成知识库特征表示与描述预处理分割低级处理 高级处理中级处理识别与解释结果图像获取问题第三章 数字图像分析第三章数字图像分析第三节特征表示与描述第三节 特征表示与描述
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） 用边界的方向作为编码依据 。为简化边界的描述。 一般描述的是边界点集 。
0
1
2
3
0
1
4
6
7
23
5
4-链码 8-链码第三章数字图像分析第三节特征表示与描述
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 特征表示与描述,表示法设计
多边形逼近
– 点合成算法：
1） 沿着边界选两个相邻的点对,计算 首尾连接直线段 与 原始折线段 的误差 R。
2） 如果误差 R小于预先设置的阈值 T。 去掉中间点,
选新点对与下一相邻点对,重复 1） ；否则,存储线段的参数,置误差为 0,选被存储线段的终点为起点,重复 1） 2） 。
3） 当程序的第一个起点被遇到,程序结束 。
R
R < T
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
多边形逼近
– 点合成算法的问题：
顶点一般不对应于边界的拐点 （ 如拐角 ） 。 因为新的线段直到超过误差的阈值才开始 。
下面讲到的 分裂法 可用于缓解这个问题第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
多边形逼近
– 边分裂算法思想举例：
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
多边形逼近
– 分裂边算法：
（ 1） 连接边界线段的两个端点 （ 如果是封闭边界,连接最远点 ） ；
（ 2） 如果最大正交距离大于阈值,将边界分为两段,最大值点定位一个顶点 。 重复 （ 1） ；
（ 3） 如果没有超过阈值的正交距离,结束 。
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
外形特征
– 基本思想：
外形特征是一种用一维函数表达边界的方法 。 基本思想是把边界的表示降到一维函数第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
外形特征
– 函数定义 ——质心角函数：边上的点到质心的距离 r,作为夹角的?的函数 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 特征表示与描述,表示法设计
边界分段
– 分段算法：
给进入和离开 凸起补集 D的变换点打标记来划分边界段 。
优点：不依赖于方向和比例的变化
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(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）
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
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
p11
1
0
1 0 1
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
区域骨架
– 基本操作 2
条件 (a),(b)与操作 1相同条件 (c),(d)改为：
c’) p2* p4* p8= 0
d’) p2* p6* p8= 0
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
区域骨架
– 细化算法细化算法的一轮操作包括：
按操作 1,给边界点打标记 ——删除点
按操作 2,给边界点打标记 ——删除点
这个基本过程反复进行,直至没有点可以删除为止 。 此时算法终止 。
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
区域骨架
– 例,
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
边界描述子
– 简单描述子
– 形状数
– 傅立叶描述子
– 矩量第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的周长,
是最简单的描述符之一 。 沿轮廓线计算象素的个数,给出了一个长度的近似估计
– 边界的直径,边界 B的直径是：
Diam(B) = max[D(pi,pj)]
D是欧氏距离或几何距离,pi,pj是边界上的点 。
直径的长度和直径的两个端点连线 （ 这条线被称为 边界的主轴 ） 的方向,是关于边界的有用的描述符 。
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的直径 举例第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的曲率,
曲率被描述为斜率的变化率 。 近似：
用相邻边界线段 （ 描述为直线 ） 的 斜率差 作为在边界线交点处的 曲率描述子 。
交点 a处的曲率为 dk = k1 – k2
其中 k1,k2 为相邻线段的斜率
a
k1
k2
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的凸线段点,
当顶点 p上的斜率是非负时,称其为凸线段上的点
– 边界的凹线段点,
当顶点 p上的斜率为负时,称其为凹线段上的点
P1
P2
第三章数字图像分析第三节特征表示与描述
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,6、
8。
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
形状数
– 序号为 4,6,8的形状数举例：
序号 4
链码,0321
首差,3333
形状,3333
序号 6
链码,003221
首差,303303
形状,033033
序号 8
链码,00032221
首差,30033003
形状,00330033
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
形状数
– 序号为 6的形状数举例,序号 6
链码,033211
首差,330330
形状,033033
序号 6
链码,003221
首差,303303
形状,033033
形状数与方向无关第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
形状数
– 序号为 8的形状数举例：
序号 8
链码,03032211
首差,33133030
形状,03033133
序号 8
链码,00332211
首差,30303030
形状,03030303
序号 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 特征表示与描述：边界描述子
形状数
（ 3） 然后再用这个矩形与基本矩形对齐,构造网格 。
（ 4） 用获得链码的方法得到链码；
（ 5） 再得到循环首差；
（ 6） 首差中的最小循环数即为形状数 。
例如,如果 n=12,所有序号为 12的矩形 （ 即周长为 12）
为 2*4,3*3,1*5。 如果 2*4矩形的离心率最接近于给定边界的基本矩形的离心率,我们建立一个 2*4的网格 。
第三章数字图像分析第三节特征表示与描述
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
y0
y1
x0 x1
jy
x
x(k) = xk
y(k) = yk
第三章数字图像分析第三节特征表示与描述
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取得越小，细节部分丢失得越多。
M=4 M=61 M=62N=64
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
傅立叶描述符
– 3）使用价值
（ 1）较少的傅立叶描述子（如 4个），就可以获取边界本质的整体轮廓
（ 2）这些带有边界信息的描述子，可以用来区分明显不同的边界第三章数字图像分析第三节特征表示与描述
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
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
矩量
– 基本思想：
将描述形状的任务减少至描述一个一维函数,
边界段和特征的形状可以用矩量来量化地描述
– 矩量的定义：
把边界当作直方图函数,g(r)
r
g(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的范围来将大小正则化 。
第三章数字图像分析第三节特征表示与描述
3.3.4 特征表示与描述：关系描述子
关系描述子
– 基本思想
– 阶梯关系编码
– 骨架关系编码
– 方向关系编码
– 内角关系编码
– 树结构关系编码第三章数字图像分析第三节特征表示与描述
3.3.4 特征表示与描述：关系描述子
基本思想：
– 通过挖掘各个成分之间的结构关系来描述边界
– 图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串
– 主导思想是考虑物体各个部分的连接线段第三章数字图像分析第三节特征表示与描述
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
ab
b
a
b
第三章数字图像分析第三节特征表示与描述
3.3.4 特征表示与描述：关系描述子
骨架关系编码
– 用有向线段来描述一个图像的各个部分（例如同构区域），这个线段是通过头尾连接等方法得到的。线段之间的不同运算代表了区域的不同组合。
– 当图像的连通性可以通过首尾相接或其它连续的方式描述的时候，最适于使用这种串来描述。
第三章数字图像分析第三节特征表示与描述
3.3.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.3.4 特征表示与描述：关系描述子
方向关系编码
– 跟踪对象的边界，将跟踪得到的线段按照方向或长度来编码
a1
a2
a5
a7
a8
a3
a4
a6a1a8a7a6a5a4a3a2
第三章数字图像分析第三节特征表示与描述
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
ef
e
f
$
第三章数字图像分析第三节特征表示与描述请提问第三章数字图像分析第三节特征表示与描述
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 and p8=0)时,条件
c,d同时满足 。 满足这个条件的点可能是右边,下边,
左上角的边界点 。 任何一种情况下,p1都不是骨架的一部分,应被删除 。
当 (p4=0 and p6=0)or(p2=0 or p8=0)时,条件
c’,d’同时满足 。 满足这个条件的点可能是左边,上边,右下角的边界点,应被删除 。
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
图像分析系统的构成知识库特征表示与描述预处理分割低级处理 高级处理中级处理识别与解释结果图像获取问题第三章 数字图像分析第三章数字图像分析第三节特征表示与描述第三节 特征表示与描述
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） 用边界的方向作为编码依据 。为简化边界的描述。 一般描述的是边界点集 。
0
1
2
3
0
1
4
6
7
23
5
4-链码 8-链码第三章数字图像分析第三节特征表示与描述
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 特征表示与描述,表示法设计
多边形逼近
– 点合成算法：
1） 沿着边界选两个相邻的点对,计算 首尾连接直线段 与 原始折线段 的误差 R。
2） 如果误差 R小于预先设置的阈值 T。 去掉中间点,
选新点对与下一相邻点对,重复 1） ；否则,存储线段的参数,置误差为 0,选被存储线段的终点为起点,重复 1） 2） 。
3） 当程序的第一个起点被遇到,程序结束 。
R
R < T
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
多边形逼近
– 点合成算法的问题：
顶点一般不对应于边界的拐点 （ 如拐角 ） 。 因为新的线段直到超过误差的阈值才开始 。
下面讲到的 分裂法 可用于缓解这个问题第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
多边形逼近
– 边分裂算法思想举例：
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
多边形逼近
– 分裂边算法：
（ 1） 连接边界线段的两个端点 （ 如果是封闭边界,连接最远点 ） ；
（ 2） 如果最大正交距离大于阈值,将边界分为两段,最大值点定位一个顶点 。 重复 （ 1） ；
（ 3） 如果没有超过阈值的正交距离,结束 。
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
外形特征
– 基本思想：
外形特征是一种用一维函数表达边界的方法 。 基本思想是把边界的表示降到一维函数第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
外形特征
– 函数定义 ——质心角函数：边上的点到质心的距离 r,作为夹角的?的函数 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 特征表示与描述,表示法设计
边界分段
– 分段算法：
给进入和离开 凸起补集 D的变换点打标记来划分边界段 。
优点：不依赖于方向和比例的变化
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(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）
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
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
p11
1
0
1 0 1
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
区域骨架
– 基本操作 2
条件 (a),(b)与操作 1相同条件 (c),(d)改为：
c’) p2* p4* p8= 0
d’) p2* p6* p8= 0
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
区域骨架
– 细化算法细化算法的一轮操作包括：
按操作 1,给边界点打标记 ——删除点
按操作 2,给边界点打标记 ——删除点
这个基本过程反复进行,直至没有点可以删除为止 。 此时算法终止 。
第三章数字图像分析第三节特征表示与描述
3.3.2 特征表示与描述,表示法设计
区域骨架
– 例,
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
边界描述子
– 简单描述子
– 形状数
– 傅立叶描述子
– 矩量第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的周长,
是最简单的描述符之一 。 沿轮廓线计算象素的个数,给出了一个长度的近似估计
– 边界的直径,边界 B的直径是：
Diam(B) = max[D(pi,pj)]
D是欧氏距离或几何距离,pi,pj是边界上的点 。
直径的长度和直径的两个端点连线 （ 这条线被称为 边界的主轴 ） 的方向,是关于边界的有用的描述符 。
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的直径 举例第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的曲率,
曲率被描述为斜率的变化率 。 近似：
用相邻边界线段 （ 描述为直线 ） 的 斜率差 作为在边界线交点处的 曲率描述子 。
交点 a处的曲率为 dk = k1 – k2
其中 k1,k2 为相邻线段的斜率
a
k1
k2
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
简单描述子
– 边界的凸线段点,
当顶点 p上的斜率是非负时,称其为凸线段上的点
– 边界的凹线段点,
当顶点 p上的斜率为负时,称其为凹线段上的点
P1
P2
第三章数字图像分析第三节特征表示与描述
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,6、
8。
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
形状数
– 序号为 4,6,8的形状数举例：
序号 4
链码,0321
首差,3333
形状,3333
序号 6
链码,003221
首差,303303
形状,033033
序号 8
链码,00032221
首差,30033003
形状,00330033
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
形状数
– 序号为 6的形状数举例,序号 6
链码,033211
首差,330330
形状,033033
序号 6
链码,003221
首差,303303
形状,033033
形状数与方向无关第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
形状数
– 序号为 8的形状数举例：
序号 8
链码,03032211
首差,33133030
形状,03033133
序号 8
链码,00332211
首差,30303030
形状,03030303
序号 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 特征表示与描述：边界描述子
形状数
（ 3） 然后再用这个矩形与基本矩形对齐,构造网格 。
（ 4） 用获得链码的方法得到链码；
（ 5） 再得到循环首差；
（ 6） 首差中的最小循环数即为形状数 。
例如,如果 n=12,所有序号为 12的矩形 （ 即周长为 12）
为 2*4,3*3,1*5。 如果 2*4矩形的离心率最接近于给定边界的基本矩形的离心率,我们建立一个 2*4的网格 。
第三章数字图像分析第三节特征表示与描述
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
y0
y1
x0 x1
jy
x
x(k) = xk
y(k) = yk
第三章数字图像分析第三节特征表示与描述
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取得越小，细节部分丢失得越多。
M=4 M=61 M=62N=64
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
傅立叶描述符
– 3）使用价值
（ 1）较少的傅立叶描述子（如 4个），就可以获取边界本质的整体轮廓
（ 2）这些带有边界信息的描述子，可以用来区分明显不同的边界第三章数字图像分析第三节特征表示与描述
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
第三章数字图像分析第三节特征表示与描述
3.3.3 特征表示与描述：边界描述子
矩量
– 基本思想：
将描述形状的任务减少至描述一个一维函数,
边界段和特征的形状可以用矩量来量化地描述
– 矩量的定义：
把边界当作直方图函数,g(r)
r
g(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的范围来将大小正则化 。
第三章数字图像分析第三节特征表示与描述
3.3.4 特征表示与描述：关系描述子
关系描述子
– 基本思想
– 阶梯关系编码
– 骨架关系编码
– 方向关系编码
– 内角关系编码
– 树结构关系编码第三章数字图像分析第三节特征表示与描述
3.3.4 特征表示与描述：关系描述子
基本思想：
– 通过挖掘各个成分之间的结构关系来描述边界
– 图像中各个部分间的结构关系是二维的，而串是一维的，期望找到一种方法把二维关系转化为一维的串
– 主导思想是考虑物体各个部分的连接线段第三章数字图像分析第三节特征表示与描述
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
ab
b
a
b
第三章数字图像分析第三节特征表示与描述
3.3.4 特征表示与描述：关系描述子
骨架关系编码
– 用有向线段来描述一个图像的各个部分（例如同构区域），这个线段是通过头尾连接等方法得到的。线段之间的不同运算代表了区域的不同组合。
– 当图像的连通性可以通过首尾相接或其它连续的方式描述的时候，最适于使用这种串来描述。
第三章数字图像分析第三节特征表示与描述
3.3.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.3.4 特征表示与描述：关系描述子
方向关系编码
– 跟踪对象的边界，将跟踪得到的线段按照方向或长度来编码
a1
a2
a5
a7
a8
a3
a4
a6a1a8a7a6a5a4a3a2
第三章数字图像分析第三节特征表示与描述
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
ef
e
f
$
第三章数字图像分析第三节特征表示与描述请提问第三章数字图像分析第三节特征表示与描述
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 and p8=0)时,条件
c,d同时满足 。 满足这个条件的点可能是右边,下边,
左上角的边界点 。 任何一种情况下,p1都不是骨架的一部分,应被删除 。
当 (p4=0 and p6=0)or(p2=0 or p8=0)时,条件
c’,d’同时满足 。 满足这个条件的点可能是左边,上边,右下角的边界点,应被删除 。
p9 p2
p1p8
p3
p4
p7 p6 p5
p9 p2
p1p8
p3
p4
p7 p6 p5
