第三章数字图像分析第四节识别与解释数字图像处理北京大学计算机研究所 陈晓鸥第三章数字图像分析第四节识别与解释第四节 识别与解释
3.4.1 图像分析引言
3.4.2 图像分析系统的组成
3.4.3 模式与模式类
3.4.4 决策论法
3.4.5 结构法第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
图像分析引言
– 图像分析的定义
– 图像分析的目标
– 自动图像分析系统行为能力的概念化分类
– 自动图像分析系统的现状第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
图像分析的定义
– 图像分析是一个：
发现、辨认和理解 模式 的过程这些模式都与执行和图像相关的 任务 有关。
图像分析的目标
– 计算机图像分析的主要目的之一是，赋予某些具有感觉能力的机器，以类似人的大脑的能力。例如 OCR
第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
自动图像分析系统 行为能力 的概念化分类分为三类：
– 获取、发现信息,从背景中提取有关信息
– 学习、应用知识,抽象、归纳信息特征的学习过程，
并应用到新的对象中
– 构造、推理知识,从不完整的信息中构造推论出新的知识，并加以应用第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
自动图像分析系统的现状
– 我们可以设计出这种系统，但 仍然缺乏理论依据 。有待人类视觉认识理论的进一步研究
– 我们可以做出在某一应用上 超过人的能力 的系统，但缺乏扩展性。过 分依赖应用第三章数字图像分析第四节识别与解释
3.4.2 图像分析系统组的成
图像分析技术分类的三种基本范畴
– 低级处理：图像获取、预处理，不需要智能
– 中级处理：图像分割、表示与描述，需要智能
– 高级处理：图像识别、解释，缺少理论，为降低难度，设计得更专用。
第三章数字图像分析第四节识别与解释
图像分析技术分类的三种基本范畴知识库分割 表示与描述识别与解释预处理图像获取低级处理 高级处理中级处理结果问题
3.4.2 图像分析系统组的成第三章数字图像分析第四节识别与解释
图像识别与解释的基本方法
– 识别的 统计分类方法,用向量形式表达模式；
分派模式向量到不同的模式类
– 识别的 结构方法,用符号匹配，模式被表示为符号形式（如形状数、串和树）
– 图像解释的方法：图像解释技术是基于谓词逻辑、语义网络和特定产品的系统
3.4.2 图像分析系统组的成第三章数字图像分析第四节识别与解释
3.4.3 模式与模式类
模式 的定义
模式类 的定义
模式识别 的定义
常用的模式序列
– 模式特征向量
– 模式串
– 模式树第三章数字图像分析第四节识别与解释
3.4.3 模式与模式类
模式 的定义
– 模式 是：图像中的一个 对象 或某些 感兴趣本质 的 数量或结构的描述
– 模式 是：由一个或多个描述子来组成，换句话说，模式是一个 描述子的序列 （名词“特征”经常被用来代指描述子）
– 模式 是,一组特征或一组描述子第三章数字图像分析第四节识别与解释
模式类 的定义
– 模式类 是具有某些公共特征的模式的系列模式类用 w1,w2,… wM表示,M是类的个数
模式识别 的定义
– 根据图像中对象的特征组成的模式,确定对象是属于那一个模式类,即为模式识别
3.4.3 识别与解释,模式与模式类第三章数字图像分析第四节识别与解释模式与模式类举例
1） 汽车的长,宽,高 （ L,W,H） ——模式
2） 大客车,（ L,W,H） 大小轿车,（ L,W,H） 小卡 车,（ L,W,H） 卡从而有模式类 （ w大,w小,w卡 ）
3） 从图像中发现一个对象 ——模式实例 。
希望识别出该对象 （ L1,W1,H1）,是大客车,小轿车,
还是卡车 ——模式识别
3.4.3 识别与解释,模式与模式类第三章数字图像分析第四节识别与解释
常用的模式序列
– 三种模式序列,
1,模式特征向量
2,模式串
3,模式树
– 模式特征向量
定义
举例
特征的选择
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
常用的模式序列
– 模式特征向量的定义 ——描述子构成的向量
模式特征向量用粗体小写字母表示,如 x,y形式如下：
其中每一个 xi代表第 i个描述子,n是这种描述子的数量。模式特征向量被表示为一列或表示成
x = (x1,x2,…,xn)T,其中 T指出是
x =
x1
x2
.
xn
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
– 模式特征向量举例假设我们想描述三种蝴蝶花 （ 多毛的,维吉尼亚,多色的 ） 通过测量它们花瓣的宽度和长度 。 这里涉及一个两维的模式特征向量：
其中 x1,x2分别对应花瓣的长和宽三种模式类用 w1,w2,w3表示
x =
x1
x2
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式特征向量也将有变化，不仅在不同的类之间，而且也在类的内部在这种情况下每一种花变成二维欧几里德空间的一个点
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
3.4.3 模式与模式类
1 2 3 4 5 6 7 x1 花瓣长
0.5
1.0
1.5
2.0
2.5
3.0
x2 花瓣宽多毛的维吉尼亚多色的第三章数字图像分析第四节识别与解释
– 模式特征向量举例：分析对花瓣长宽的测量,成功地将多毛的蝴蝶花与其它两种分离,但对于分离维吉尼亚和多色的是失败的 。
这个结论说明了分类的特征选择问题,在这个问题中,类的可区别性的程度,完全依赖于对模式尺寸测量的选择
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
– 模式特征的选择
良好的特征应具备四个特点
1,可区别性：对不同类别对象特征值差异明显
2,可靠性,对同类对象特征值比较接近
3,独立性,所用的各特征之间彼此统计独立
4,数量少,过多的特征数,会使系统复杂度提高
一般特征向量的选择方法
– 尽量不选择带噪声和相关度高的特征
– 先选择一组直觉上合理的特征,然后逐渐减少到最佳
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
– 模式串用于以对象特征的结构或空间关系作为模式的识别
– 模式串举例：梯状的模式
3.4.3 模式与模式类
a
b
a
a
a
b
b
b
(1) S->aA
(2) A->bS
(3) A->b
第三章数字图像分析第四节识别与解释
– 模式树以分层目录结构排序的模式类，一般多采用树结构模式树举例
3.4.3 模式与模式类图像城市 田园草地 森林娱乐区 商业区 娱乐区 商业区城区 内城 市郊 公路第三章数字图像分析第四节识别与解释
3.4.4 决策论法
决策论法
– 分类器的设计和训练
– 决策论法的基本概念
– 分类器
最小距离分类器
相关匹配分类器第三章数字图像分析第四节识别与解释
3.4.4 决策论法
分类器的设计与训练
– 分类器一般设计方法
分类器对每一模式类，给出一个典型摸板
对每一个遇到的待分类对象
计算该对象与个典型摸板之间的相似程度
相似值是对象的函数
函数取值的不同，决定对象属于那一模式类第三章数字图像分析第四节识别与解释
3.4.4 决策论法
分类器的设计与训练
– 分类器一般设计规则
分类器规则都转换为阈值规则
将测量空间划分成互不重叠的区域
每一个模式类对应一个区域（或多个）
对象的分类函数值落在哪个区域，对象就属那类
某些情况，某些区域为,无法确定,类第三章数字图像分析第四节识别与解释
3.4.4 决策论法
分类器的设计与训练
– 分类器的训练
决策规则决定后，需要确定分类器的阈值
实现的方法是用一组已知对象训练分类器
训练对象集由每类已被正确识别的部分对象组成
通过对这些对象的度量，定出能够将决策面划分成不同区域的合理阈值
使分类器对训练对象样本集分类准确性最高第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
决策论法的基本概念
– 决策论识别法 的定义设：模式特征向量,x = (x1,x2,…,xn)T，
对于,M个模式类 w1,w2,…,wM，
寻找 M个 决策函数 d1(x),d2(x),…,dM(x),具有这样的特性：如果模式实例 x属于模式类 wi,那么：
di(x) > dj(x) j = 1,2,…,M;
j ≠ i
换句话说,如果一个未知模式对象 x属于第 i个模式类,
把 x代入所有的决策函数,di(x)的取值最大 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
决策论法的基本概念
– 决策边界 的定义
对于模式特征向量 x,如果决策函数值有：
di(x) - dj(x) = 0
此 x向量,被称为 wi与 wj的决策边界 。
通常用一个单一的函数标识两个类之间的 决策边界,定义为,dij(x) = di(x) - dj(x) = 0
如果 dij(x) > 0 x 属于类 wi
如果 dij(x) < 0 x 属于类 wj
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器以蝴蝶花的例子为例：
（ 1） 为多色 （ w1） 和多毛 （ w2 ） 的两种蝴蝶花,
确定两个 原形 （ 或称模板 ） m1和 m2
（ 2） 对于一个未知模式向量 x,判断 x与 m1和 m2的距离,如果与 m1的距离小于与 m2的距离,则 x属于 w1,否则属于 w2 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
1 2 3 4 5 6 7 x1 花瓣长
0.5
1.0
1.5
2.0
2.5
3.0
x2 花瓣宽多毛的多色的
m1
m2
x
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器
（ 1） 算法思想：
对于 M个模式类 wi i = 1,2,...,M
为每一个模式类确定一个原形模式特征向量 mi
对于一个未知模式特征向量 x,如果 x与 mi的距离最小,就称,x属于 wi
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器
（ 2） 最小距离分类器定义 （ 训练 ）,
〈 1〉 计算模式类 wj的原形向量：
mj = 1/Nj? x j = 1,2,…,M
x?wj
其中 Nj是属于模式类 wj的模式向量的个数 。
通过计算已知属于 wj的模式特征向量的各分量的均值 得到原形模式特征向量 mj
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器
〈 2〉 计算 x 与 mi的距离
dj(x) = || x – mj || j = 1,2,…,M
其中 || a || = (aTa)1/2是欧几里德范式 （ 平方和开方 ）
dj(x) = ((x – mj )T (x – mj )) 1/2 j = 1,
2,…,M
〈 3〉 决策如果,di(x) = min(dj(x)) j = 1,2,…,M
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器为便于计算,改写成求最大的标准形式,决策函数为：
dj(x) = xTmj – 1/2mjTmj j = 1,2,…,M
如果,di(x) = max(dj(x)) j = 1,2,…,M
就说,x 属于 wi
〈 4〉 用上式得到的类 wi和 wj之间的 决策边界 是：
dij(x) = di(x) - dj(x)
= xT（ mi – mj） – 1/2(mi – mj)T(mi – mj) = 0
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
（ 3） 举例：
多色的和多毛的蝴蝶花,用 w1和 w2分别表示,
有简单的原形向量
m1 = (4.4,1.3)T m2 = (1.5,0.3)T
决策函数是：
d1(x) = xTm1 – 1/2m1Tm1 = 4.3x1 + 1.3x2 – 10.1
d2(x) = xTm2 – 1/2m2Tm2 = 1.5x1 + 0.3x2 – 1.17
决策边界的等式：
d12(x) = d1(x) – d2(x) = 2.8x1 – 1.0x2 – 8.9 = 0
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
1 2 3 4 5 6 7 x1 花瓣长
0.5
1.0
1.5
2.0
2.5
3.0
x2 花瓣宽多毛的多色的第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关匹配分类器
(1) 相关匹配的基本思想,
a,用样板子图像直接作为模式特征 （ 不是用描述子 ）
b,通过子图像与原图像直接进行 相关 计算,把相关计算作为决策函数
c,相关计算获得最大值的位置,就被认为匹配成功第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
– 相关匹配分类器
(1) 相关匹配基本思想第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关匹配分类器
Mx
原点
N
y
f(x,y)
(s,t)J
s
w(x-s,y-t)
K
t
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关匹配分类器
(2) 算法描述决策函数是相关函数
c(s,t) = ∑∑f(x,y)w(x -s,y-t)
x y
对图像的每一个点进行相关计算,只计算重叠部分问题：在边界处将失去准确性,其误差与子图像的尺寸成正比第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
– 相关匹配分类器
(3) 改进相关函数对振幅的变化太敏感,f(x,y)加倍,
c(s,t)也加倍 。 用 相关系数函数 代替 相关函数
∑∑ [f(x,y) – f(x,y)][w(x-s,y-t) – w]
γ (s,t)=————————————————————
{∑∑[f(x,y) –f(x,y)]2∑∑[w(x -s,y-t)–
w]2}1/2
x y x y
γ (s,t)的值域为 （ -1,1）
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
– 相关匹配分类器
(4) 对旋转和比例变化的分析
问题：
当被匹配图像中,对象的尺寸和角度与模式不一致,此方法将失效 。
改进：
– 尺寸的正则化,解决空间比例的问题 。 正则化模板与原图 。
– 如果知道原图像的旋转角度,我们可以通过旋转原图像,
对齐模式解决 。
结论,
如果被匹配的对象的角度任意,此方法不能用于这种问题 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关性匹配分类器
(5) 关于空域计算
相关函数,可以在频域计算 。
f(x,y)?w(x,y)? f(s,t)w(s,t)
但无论在何种情况下,都没有更有优势的理论根据 。 相关系数方式只能在空域进行 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
结构法
– 匹配形状数
– 匹配串第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
结构法决策法,通过量化的方法处理模式，
最大限度地忽略了模式形状的内在结构关系。
结构法,则力求通过准确地抓住这些不同模式类的内在结构关系来进行模式识别。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(1) 匹配形状数的基本思想通过比较两个对象边界的形状数的相似程度,来匹配对象 。 例如：
未知模式 原形模式类第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(2) 基本概念 -相似级别
a.两个区域边界的 相似级别 k的定义：
用相同形状数的 最大序号 表示：即：
当考虑用 4向链码表示的封闭区域边界的形状数时,A和 B具有相似级别 k,当且仅当满足：
s4(A) = s4(B),s6(A) = s6(B),
s8(A) = s8(B),…,sk(A) = sk(B),
sk+2(A)? sk+2(B),sk+4(A)? sk+4(B),…,
这里 s表示形状数,下标表示序号 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(2) 基本概念 -形状数的距离
b.两个区域边界 A和 B形状数的距离 D(A,B)
相似级别的倒数,D(A,B) = 1 / k
距离满足如下性质,
D(A,B)? 0
D(A,B) = 0 iff A=B
D(A,C)? max[D(A,B),D(B,C)]
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(3) 算法思想
a,用不同密度的网格划分边界区域,获得不同序数的形状数 。
b,如果使用相似级别 k,k越大说明越相似 。
c,如果使用相似距离 D,D越小说明越相似
d,可以利用相似树来进行判别第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
（ 4） 举例假设我们有一个形状 F,想在另 5个形状 （ A,B,C,D，
E） 中找到与其最相似的形状
A B C D E F
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法这个问题类似于有五个原型形状，想找出一个给定的尚不确定的形状的最佳匹配的问题。这个问题可以利用相似树和矩阵来可视化
4
6
8
10
12
14
ABCDEF
ABCDEF
BCDEFA
A
A
A
BECF
B E
D
D
D
CF
C F B E
A B C D E F
A
B
E
D
C
F
6 6 6 6 6
8 8 10 8
8 8 12
8 8
8
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
（ 1）串匹配的基本思想比较两个边界串编码的相似程度,来进行匹配
（ 2）三个基本概念设,两个区域边界 A和 B已分别被编码为串 a1a2… an和 b1b2… bm。
a3a3a3a3a3a3a3a3 a2a2a3a3
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
a.两个串的 匹配数 M:
当 ak= bk 时我们说发生了一个匹配 。 令
M代表 A,B中匹配的总数 。
b.不匹配的符号数量 Q：
Q = max（ |A|,|B|） - M
这里 |arg|是字符串的长度。当且仅当 A
和 B完全相同时,Q = 0。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
c,A和 B相似度的简便衡量 R:
R = M/Q = M / [max(|A|,|B|) - M]
因此,
当 A和 B完全匹配时,R =?；
当 A和 B中任何字符都不匹配时,
M = 0,R = 0。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
（ 3）算法思想
a.由于匹配是逐字符进行的,
b.选择一个好的开始点,可以大大减少计算量 。 任何将两个串规则化为相同字符开头的方法都是有效的,只要这种方法不是穷举起点 。
c.最大的 R给出了最好的匹配 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
（ 4）举例对象 1.a 对象 2.a
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配现有两个模式类：
模式类 1：有 1.b,1.c,1.d,1.e,1.f
5个模板模式类 2：有 2.b,2.c,2.d,2.e,2.f
5个模板第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配现将对象 1.a与 模式类 1的 5个样例做串匹配,
有相似度 R值的结果表：
1.b 1.c 1.d 1.e
1.f
1.a 16.0 9.6 5.07 4.67 4.67
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配现将对象 2.a与 模式类 2的 5个样例做串匹配,
有相似度 R值的结果表：
2.b 2.c 2.d 2.e
2.f
2.a 33.5 4.75 3.6 2.83 2.63
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法将对象 1.a与 模式类 2的 5个样例做串匹配，
有 R值的结果表,
2.a 2.b 2.c 2.d 2.e
2.f
1.a 1.24 1.18 1.02 1.02 0.93,89
将对象 2.a与 模式类 1的 5个样例做串匹配有 R值的结果表：
1.a 1.b 1.c 1.d 1.e
1.f
2.a 1.24 1.50 1.32 1.47 1.55
第三章数字图像分析第四节识别与解释请提问
3.4.1 图像分析引言
3.4.2 图像分析系统的组成
3.4.3 模式与模式类
3.4.4 决策论法
3.4.5 结构法第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
图像分析引言
– 图像分析的定义
– 图像分析的目标
– 自动图像分析系统行为能力的概念化分类
– 自动图像分析系统的现状第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
图像分析的定义
– 图像分析是一个：
发现、辨认和理解 模式 的过程这些模式都与执行和图像相关的 任务 有关。
图像分析的目标
– 计算机图像分析的主要目的之一是，赋予某些具有感觉能力的机器，以类似人的大脑的能力。例如 OCR
第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
自动图像分析系统 行为能力 的概念化分类分为三类：
– 获取、发现信息,从背景中提取有关信息
– 学习、应用知识,抽象、归纳信息特征的学习过程，
并应用到新的对象中
– 构造、推理知识,从不完整的信息中构造推论出新的知识，并加以应用第三章数字图像分析第四节识别与解释
3.4.1 图像分析引言
自动图像分析系统的现状
– 我们可以设计出这种系统，但 仍然缺乏理论依据 。有待人类视觉认识理论的进一步研究
– 我们可以做出在某一应用上 超过人的能力 的系统，但缺乏扩展性。过 分依赖应用第三章数字图像分析第四节识别与解释
3.4.2 图像分析系统组的成
图像分析技术分类的三种基本范畴
– 低级处理：图像获取、预处理，不需要智能
– 中级处理：图像分割、表示与描述，需要智能
– 高级处理：图像识别、解释，缺少理论，为降低难度，设计得更专用。
第三章数字图像分析第四节识别与解释
图像分析技术分类的三种基本范畴知识库分割 表示与描述识别与解释预处理图像获取低级处理 高级处理中级处理结果问题
3.4.2 图像分析系统组的成第三章数字图像分析第四节识别与解释
图像识别与解释的基本方法
– 识别的 统计分类方法,用向量形式表达模式；
分派模式向量到不同的模式类
– 识别的 结构方法,用符号匹配，模式被表示为符号形式（如形状数、串和树）
– 图像解释的方法：图像解释技术是基于谓词逻辑、语义网络和特定产品的系统
3.4.2 图像分析系统组的成第三章数字图像分析第四节识别与解释
3.4.3 模式与模式类
模式 的定义
模式类 的定义
模式识别 的定义
常用的模式序列
– 模式特征向量
– 模式串
– 模式树第三章数字图像分析第四节识别与解释
3.4.3 模式与模式类
模式 的定义
– 模式 是：图像中的一个 对象 或某些 感兴趣本质 的 数量或结构的描述
– 模式 是：由一个或多个描述子来组成，换句话说，模式是一个 描述子的序列 （名词“特征”经常被用来代指描述子）
– 模式 是,一组特征或一组描述子第三章数字图像分析第四节识别与解释
模式类 的定义
– 模式类 是具有某些公共特征的模式的系列模式类用 w1,w2,… wM表示,M是类的个数
模式识别 的定义
– 根据图像中对象的特征组成的模式,确定对象是属于那一个模式类,即为模式识别
3.4.3 识别与解释,模式与模式类第三章数字图像分析第四节识别与解释模式与模式类举例
1） 汽车的长,宽,高 （ L,W,H） ——模式
2） 大客车,（ L,W,H） 大小轿车,（ L,W,H） 小卡 车,（ L,W,H） 卡从而有模式类 （ w大,w小,w卡 ）
3） 从图像中发现一个对象 ——模式实例 。
希望识别出该对象 （ L1,W1,H1）,是大客车,小轿车,
还是卡车 ——模式识别
3.4.3 识别与解释,模式与模式类第三章数字图像分析第四节识别与解释
常用的模式序列
– 三种模式序列,
1,模式特征向量
2,模式串
3,模式树
– 模式特征向量
定义
举例
特征的选择
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
常用的模式序列
– 模式特征向量的定义 ——描述子构成的向量
模式特征向量用粗体小写字母表示,如 x,y形式如下：
其中每一个 xi代表第 i个描述子,n是这种描述子的数量。模式特征向量被表示为一列或表示成
x = (x1,x2,…,xn)T,其中 T指出是
x =
x1
x2
.
xn
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
– 模式特征向量举例假设我们想描述三种蝴蝶花 （ 多毛的,维吉尼亚,多色的 ） 通过测量它们花瓣的宽度和长度 。 这里涉及一个两维的模式特征向量：
其中 x1,x2分别对应花瓣的长和宽三种模式类用 w1,w2,w3表示
x =
x1
x2
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式特征向量也将有变化，不仅在不同的类之间，而且也在类的内部在这种情况下每一种花变成二维欧几里德空间的一个点
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
3.4.3 模式与模式类
1 2 3 4 5 6 7 x1 花瓣长
0.5
1.0
1.5
2.0
2.5
3.0
x2 花瓣宽多毛的维吉尼亚多色的第三章数字图像分析第四节识别与解释
– 模式特征向量举例：分析对花瓣长宽的测量,成功地将多毛的蝴蝶花与其它两种分离,但对于分离维吉尼亚和多色的是失败的 。
这个结论说明了分类的特征选择问题,在这个问题中,类的可区别性的程度,完全依赖于对模式尺寸测量的选择
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
– 模式特征的选择
良好的特征应具备四个特点
1,可区别性：对不同类别对象特征值差异明显
2,可靠性,对同类对象特征值比较接近
3,独立性,所用的各特征之间彼此统计独立
4,数量少,过多的特征数,会使系统复杂度提高
一般特征向量的选择方法
– 尽量不选择带噪声和相关度高的特征
– 先选择一组直觉上合理的特征,然后逐渐减少到最佳
3.4.3 模式与模式类第三章数字图像分析第四节识别与解释
– 模式串用于以对象特征的结构或空间关系作为模式的识别
– 模式串举例：梯状的模式
3.4.3 模式与模式类
a
b
a
a
a
b
b
b
(1) S->aA
(2) A->bS
(3) A->b
第三章数字图像分析第四节识别与解释
– 模式树以分层目录结构排序的模式类，一般多采用树结构模式树举例
3.4.3 模式与模式类图像城市 田园草地 森林娱乐区 商业区 娱乐区 商业区城区 内城 市郊 公路第三章数字图像分析第四节识别与解释
3.4.4 决策论法
决策论法
– 分类器的设计和训练
– 决策论法的基本概念
– 分类器
最小距离分类器
相关匹配分类器第三章数字图像分析第四节识别与解释
3.4.4 决策论法
分类器的设计与训练
– 分类器一般设计方法
分类器对每一模式类，给出一个典型摸板
对每一个遇到的待分类对象
计算该对象与个典型摸板之间的相似程度
相似值是对象的函数
函数取值的不同，决定对象属于那一模式类第三章数字图像分析第四节识别与解释
3.4.4 决策论法
分类器的设计与训练
– 分类器一般设计规则
分类器规则都转换为阈值规则
将测量空间划分成互不重叠的区域
每一个模式类对应一个区域（或多个）
对象的分类函数值落在哪个区域，对象就属那类
某些情况，某些区域为,无法确定,类第三章数字图像分析第四节识别与解释
3.4.4 决策论法
分类器的设计与训练
– 分类器的训练
决策规则决定后，需要确定分类器的阈值
实现的方法是用一组已知对象训练分类器
训练对象集由每类已被正确识别的部分对象组成
通过对这些对象的度量，定出能够将决策面划分成不同区域的合理阈值
使分类器对训练对象样本集分类准确性最高第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
决策论法的基本概念
– 决策论识别法 的定义设：模式特征向量,x = (x1,x2,…,xn)T，
对于,M个模式类 w1,w2,…,wM，
寻找 M个 决策函数 d1(x),d2(x),…,dM(x),具有这样的特性：如果模式实例 x属于模式类 wi,那么：
di(x) > dj(x) j = 1,2,…,M;
j ≠ i
换句话说,如果一个未知模式对象 x属于第 i个模式类,
把 x代入所有的决策函数,di(x)的取值最大 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
决策论法的基本概念
– 决策边界 的定义
对于模式特征向量 x,如果决策函数值有：
di(x) - dj(x) = 0
此 x向量,被称为 wi与 wj的决策边界 。
通常用一个单一的函数标识两个类之间的 决策边界,定义为,dij(x) = di(x) - dj(x) = 0
如果 dij(x) > 0 x 属于类 wi
如果 dij(x) < 0 x 属于类 wj
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器以蝴蝶花的例子为例：
（ 1） 为多色 （ w1） 和多毛 （ w2 ） 的两种蝴蝶花,
确定两个 原形 （ 或称模板 ） m1和 m2
（ 2） 对于一个未知模式向量 x,判断 x与 m1和 m2的距离,如果与 m1的距离小于与 m2的距离,则 x属于 w1,否则属于 w2 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
1 2 3 4 5 6 7 x1 花瓣长
0.5
1.0
1.5
2.0
2.5
3.0
x2 花瓣宽多毛的多色的
m1
m2
x
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器
（ 1） 算法思想：
对于 M个模式类 wi i = 1,2,...,M
为每一个模式类确定一个原形模式特征向量 mi
对于一个未知模式特征向量 x,如果 x与 mi的距离最小,就称,x属于 wi
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器
（ 2） 最小距离分类器定义 （ 训练 ）,
〈 1〉 计算模式类 wj的原形向量：
mj = 1/Nj? x j = 1,2,…,M
x?wj
其中 Nj是属于模式类 wj的模式向量的个数 。
通过计算已知属于 wj的模式特征向量的各分量的均值 得到原形模式特征向量 mj
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器
〈 2〉 计算 x 与 mi的距离
dj(x) = || x – mj || j = 1,2,…,M
其中 || a || = (aTa)1/2是欧几里德范式 （ 平方和开方 ）
dj(x) = ((x – mj )T (x – mj )) 1/2 j = 1,
2,…,M
〈 3〉 决策如果,di(x) = min(dj(x)) j = 1,2,…,M
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 最小距离分类器为便于计算,改写成求最大的标准形式,决策函数为：
dj(x) = xTmj – 1/2mjTmj j = 1,2,…,M
如果,di(x) = max(dj(x)) j = 1,2,…,M
就说,x 属于 wi
〈 4〉 用上式得到的类 wi和 wj之间的 决策边界 是：
dij(x) = di(x) - dj(x)
= xT（ mi – mj） – 1/2(mi – mj)T(mi – mj) = 0
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
（ 3） 举例：
多色的和多毛的蝴蝶花,用 w1和 w2分别表示,
有简单的原形向量
m1 = (4.4,1.3)T m2 = (1.5,0.3)T
决策函数是：
d1(x) = xTm1 – 1/2m1Tm1 = 4.3x1 + 1.3x2 – 10.1
d2(x) = xTm2 – 1/2m2Tm2 = 1.5x1 + 0.3x2 – 1.17
决策边界的等式：
d12(x) = d1(x) – d2(x) = 2.8x1 – 1.0x2 – 8.9 = 0
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
1 2 3 4 5 6 7 x1 花瓣长
0.5
1.0
1.5
2.0
2.5
3.0
x2 花瓣宽多毛的多色的第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关匹配分类器
(1) 相关匹配的基本思想,
a,用样板子图像直接作为模式特征 （ 不是用描述子 ）
b,通过子图像与原图像直接进行 相关 计算,把相关计算作为决策函数
c,相关计算获得最大值的位置,就被认为匹配成功第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
– 相关匹配分类器
(1) 相关匹配基本思想第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关匹配分类器
Mx
原点
N
y
f(x,y)
(s,t)J
s
w(x-s,y-t)
K
t
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关匹配分类器
(2) 算法描述决策函数是相关函数
c(s,t) = ∑∑f(x,y)w(x -s,y-t)
x y
对图像的每一个点进行相关计算,只计算重叠部分问题：在边界处将失去准确性,其误差与子图像的尺寸成正比第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
– 相关匹配分类器
(3) 改进相关函数对振幅的变化太敏感,f(x,y)加倍,
c(s,t)也加倍 。 用 相关系数函数 代替 相关函数
∑∑ [f(x,y) – f(x,y)][w(x-s,y-t) – w]
γ (s,t)=————————————————————
{∑∑[f(x,y) –f(x,y)]2∑∑[w(x -s,y-t)–
w]2}1/2
x y x y
γ (s,t)的值域为 （ -1,1）
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
– 相关匹配分类器
(4) 对旋转和比例变化的分析
问题：
当被匹配图像中,对象的尺寸和角度与模式不一致,此方法将失效 。
改进：
– 尺寸的正则化,解决空间比例的问题 。 正则化模板与原图 。
– 如果知道原图像的旋转角度,我们可以通过旋转原图像,
对齐模式解决 。
结论,
如果被匹配的对象的角度任意,此方法不能用于这种问题 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,决策论法
分类器
– 相关性匹配分类器
(5) 关于空域计算
相关函数,可以在频域计算 。
f(x,y)?w(x,y)? f(s,t)w(s,t)
但无论在何种情况下,都没有更有优势的理论根据 。 相关系数方式只能在空域进行 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
结构法
– 匹配形状数
– 匹配串第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
结构法决策法,通过量化的方法处理模式，
最大限度地忽略了模式形状的内在结构关系。
结构法,则力求通过准确地抓住这些不同模式类的内在结构关系来进行模式识别。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(1) 匹配形状数的基本思想通过比较两个对象边界的形状数的相似程度,来匹配对象 。 例如：
未知模式 原形模式类第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(2) 基本概念 -相似级别
a.两个区域边界的 相似级别 k的定义：
用相同形状数的 最大序号 表示：即：
当考虑用 4向链码表示的封闭区域边界的形状数时,A和 B具有相似级别 k,当且仅当满足：
s4(A) = s4(B),s6(A) = s6(B),
s8(A) = s8(B),…,sk(A) = sk(B),
sk+2(A)? sk+2(B),sk+4(A)? sk+4(B),…,
这里 s表示形状数,下标表示序号 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(2) 基本概念 -形状数的距离
b.两个区域边界 A和 B形状数的距离 D(A,B)
相似级别的倒数,D(A,B) = 1 / k
距离满足如下性质,
D(A,B)? 0
D(A,B) = 0 iff A=B
D(A,C)? max[D(A,B),D(B,C)]
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
(3) 算法思想
a,用不同密度的网格划分边界区域,获得不同序数的形状数 。
b,如果使用相似级别 k,k越大说明越相似 。
c,如果使用相似距离 D,D越小说明越相似
d,可以利用相似树来进行判别第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
匹配形状数
（ 4） 举例假设我们有一个形状 F,想在另 5个形状 （ A,B,C,D，
E） 中找到与其最相似的形状
A B C D E F
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法这个问题类似于有五个原型形状，想找出一个给定的尚不确定的形状的最佳匹配的问题。这个问题可以利用相似树和矩阵来可视化
4
6
8
10
12
14
ABCDEF
ABCDEF
BCDEFA
A
A
A
BECF
B E
D
D
D
CF
C F B E
A B C D E F
A
B
E
D
C
F
6 6 6 6 6
8 8 10 8
8 8 12
8 8
8
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
（ 1）串匹配的基本思想比较两个边界串编码的相似程度,来进行匹配
（ 2）三个基本概念设,两个区域边界 A和 B已分别被编码为串 a1a2… an和 b1b2… bm。
a3a3a3a3a3a3a3a3 a2a2a3a3
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
a.两个串的 匹配数 M:
当 ak= bk 时我们说发生了一个匹配 。 令
M代表 A,B中匹配的总数 。
b.不匹配的符号数量 Q：
Q = max（ |A|,|B|） - M
这里 |arg|是字符串的长度。当且仅当 A
和 B完全相同时,Q = 0。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
c,A和 B相似度的简便衡量 R:
R = M/Q = M / [max(|A|,|B|) - M]
因此,
当 A和 B完全匹配时,R =?；
当 A和 B中任何字符都不匹配时,
M = 0,R = 0。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
（ 3）算法思想
a.由于匹配是逐字符进行的,
b.选择一个好的开始点,可以大大减少计算量 。 任何将两个串规则化为相同字符开头的方法都是有效的,只要这种方法不是穷举起点 。
c.最大的 R给出了最好的匹配 。
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配
（ 4）举例对象 1.a 对象 2.a
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配现有两个模式类：
模式类 1：有 1.b,1.c,1.d,1.e,1.f
5个模板模式类 2：有 2.b,2.c,2.d,2.e,2.f
5个模板第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配现将对象 1.a与 模式类 1的 5个样例做串匹配,
有相似度 R值的结果表：
1.b 1.c 1.d 1.e
1.f
1.a 16.0 9.6 5.07 4.67 4.67
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法
串匹配现将对象 2.a与 模式类 2的 5个样例做串匹配,
有相似度 R值的结果表：
2.b 2.c 2.d 2.e
2.f
2.a 33.5 4.75 3.6 2.83 2.63
第三章数字图像分析第四节识别与解释
3.4.4 识别与解释,结构法将对象 1.a与 模式类 2的 5个样例做串匹配，
有 R值的结果表,
2.a 2.b 2.c 2.d 2.e
2.f
1.a 1.24 1.18 1.02 1.02 0.93,89
将对象 2.a与 模式类 1的 5个样例做串匹配有 R值的结果表：
1.a 1.b 1.c 1.d 1.e
1.f
2.a 1.24 1.50 1.32 1.47 1.55
第三章数字图像分析第四节识别与解释请提问
