计算机视觉教程（第3版）第12章

计算机视觉教程（第3版）●章毓晋

模式识别是人类的重要功能之一。现在常用模式识别指用计算机就人类对周围世界的客体、过程和现象的识别功能进行自动模拟的学科

对目标的识别工作可分为4种：①

验证，对一个事先见过的目标的识别；②

推广，识别一个目标，尽管由于某些变换已使得它的外观发生了变化；③

分类，将目标分到一组类似形状的目标中去；④

类似，发现不同目标变换后的相似之处

图像模式识别是对特殊对象的模式识别第12章

景物识别目录contents12.1

统计模式分类12.2

感知机12.3 支持向量机12.4

结构模式识别12.1统计模式分类

一个n维的模式矢量可写成

如果一个模式x属于类si，那么有

对一个未知模式x来说，如果将它代入所有决策函数算得di(x)值最大，则x属于第i类。如果对x的值，有di(x)=dj(x)，则得到将类i与类j分开的决策边界12.1统计模式分类

每个模式类用一

个均值矢量表示

计算

并且在dj(x)给出最大值时将x赋给类sj

类si和sj之间的决策边界最小距离分类器12.1统计模式分类

在平均意义上产生最小可能分类误差

条件平均风险损失

贝叶斯分类器最优统计分类原理12.1统计模式分类

损失函数

贝叶斯分类器在满足下面的条件时将x赋给类si

对0-1损失函数，贝叶斯分类器相当于实现了如下的判决函数最优统计分类原理12.1统计模式分类

贝叶斯决策函数

对类sj的贝叶斯决策函数是dj(x)=p(x|sj)P(sj)

采用自然对数形式来表达决策函数用于高斯模式类的贝叶斯分类器12.1统计模式分类例12.1.2模式在3-D空间的分布12.2感知机

两个模式类的感知机模型12.2感知机

感知机（学习机器）的决策边界

系统的输出12.2感知机

由两个线性可分训练集获取权矢量的迭代算法

校正增量c设为正的

如果机器正确地划分了模式，给它的奖励就是不改变w；但如果机器错误地划分了模式，给它的惩罚就是改变w线性可分类12.2感知机线性不可分类准则函数梯度下降算法12.2感知机

如将权矢量的变化，即德尔塔写成如下的形式

德尔塔（Delta）校正算法

当模式y(k)出现时，权矢量w(k)的误差为线性不可分类12.3支持向量机

设计目的就是要获得一个超平面其中，w=[w1,w2,…,wl]T为权向量，w0为阈值线性可分类12.3支持向量机

朝向A为所求，而朝向B给出了一个其他朝向

从一个点到一个超平面的距离线性可分类12.3支持向量机

用拉格朗日乘数法来解

最优解的向量参数w是Ns个（Ns

N）与li

0相关的特征向量的线性组合

这些向量就称为支持向量，而最优的超平面分类器就称为支持向量机线性可分类12.3支持向量机

此时的目标是在保持具有ri>0的点数尽可能小的条件下，使最近点到超平面的距离尽可能小。此时要最小化的代价函数为线性不可分类12.4结构模式识别

文法是一组句法规则，它们能控制字符集中符号产生句子的过程

由一个文法G所产生的一组句子称为语言，并记为L(G)。所以句子是符号的串，这些串代表了模式，而语言对应模式类

四元组：G=(N,T,P,S)

N：非终结符号集；T：终结符号集；P：一组称为产生式的重写规则集；S：起始符号，在N中字符串文法12.4结构模式识别

例12.4.1字符串结构示例

考虑文法G=(N,T,P,S)，其中N={A,B,C}，T={a,b,c}，P={S

aA,A

bA,

A

bB,B

c}字符串文法12.4结构模式识别

句法确定目标结构，语义主要与其正确性有关语义应用12.4结构模式识别

如何识别一个模式是否属于由文法G产生的语言L(G)。结构识别法的基本概念可借助称为自动机（计算机器）的数学模型来解释

有限自动机是由规则语法产生的语言识别器，可定义为一个五元组用自动机作为字符串识别器12.4结构模式识别

Q={q0,q1,q2}，T={a,b}，F={q0}。映射规则是d(q0,a)={q2}，d(q0,b)={q1}，d(q1,a)={q2}，d(q1,b)={q0}，d(q2,a)={q0}，d(q2,b)={q1}

能识别字符串abbabb，但不能识别字符串aabab用自动机作为字符串识别器12.4结构模式识别

树文法是由如下五元组所定义

扩展树文法

X1,X2,…,Xn

为非终结符号，k

是一个终结符号，r(k)={n}r为排序函数树文法Ti

Tj12.4结构模式识别

在这个树文法中，N={X1,X2,X3,S}，T

={a,b,c,d,e}，其中终结符号表示图12.4.4(b)所示的基元树文法12.4结构模式识别

排序函数：r(a)={0,1}，r(b)=r(d)=r(e)={1}，r(c)={2}

对产生式规则(2)、(4)、(6)使用相同的次数，则将会产生一个其中所有3段腿长度都相同的结构树文法12.4结构模式识别

一个从树叶向树根扫描的树自动机其中，Q为一组状态有限集；F为一组终结状态集，且是Q的一个子集；fk是Qm

Q中的关系，其中m为k的秩，Qm代表Q的自身m次笛卡尔乘积，即Qm

=

Q

Q

Q

…

Q

。根据笛卡尔积的定义，上述表达代表所有排序的m元组（其元素源于Q）的集合树自动机12.4结构模式识别树自动机教程作者（章毓晋）联系信息通信地址：北京清华大学电子工程系邮