计算机视觉教程CCV12

1、第12章景物识别12.1 统计模式分类12.2 感知机12.3 支持向量机12.4 结构模式识别12.1 统计模式分类12.1.1 模式分类原理12.1.2 最小距离分类器12.1.3 最优统计分类器12.1.1 模式分类原理一个n维的模式矢量可写成如果一个模式x属于类si，那么有对一个未知模式x来说，如果将它代入所有决策函数算得di(x)值最大，则x属于第i类。如果对x的值，有di(x) = dj(x)，则得到将类i与类j分开的决策边界12.1.2 最小距离分类器每个模式类用一个均值矢量表示计算并且在dj(x)给出最大值时将x赋给类sj类si和sj之间的决策边界12.1.3 最优统计分类器1

2、.最优统计分类原理在平均意义上产生最小可能分类误差条件平均风险损失贝叶斯分类器12.1.3 最优统计分类器1.最优统计分类原理损失函数贝叶斯分类器在满足下面的条件时将x赋给类si对0-1损失函数，贝叶斯分类器相当于实现了如下的判决函数12.1.3 最优统计分类器2.用于高斯模式类的贝叶斯分类器贝叶斯决策函数对类sj的贝叶斯决策函数是dj(x) = p(x | sj)P(sj)采用自然对数形式来表达决策函数12.1.3 最优统计分类器例12.1.2模式在3-D空间的分布12.2 感知机两个模式类的感知机模型12.2 感知机感知机的决策边界系统的输出12.2 感知机1.线性可分类由两个线性可分训练

3、集获取权矢量的迭代算法校正增量c设为正的如果机器正确地划分了模式，给它的奖励就是不改变w；但如果机器错误地划分了模式，给它的惩罚就是改变w。根据感知机训练定理12.2 感知机2.线性不可分类准则函数梯度下降算法12.2 感知机2.线性不可分类如将权矢量的变化，即德尔塔写成如下的形式德尔塔（Delta）校正算法当模式y(k)出现时，权矢量w(k)的误差为12.3 支持向量机1.线性可分类设计目的就是要获得一个超平面其中，w = w1, w2, , wlT为权向量，w0为阈值12.3 支持向量机1.线性可分类朝向A为所求，而朝向B给出了一个其他朝向从一个点到一个超平面的距离12.3 支持向量机1.

4、线性可分类用拉格朗日乘数法来解最优解的向量参数w是Ns个（Ns N）与li 0相关的特征向量的线性组合这些向量就称为支持向量，而最优的超平面分类器就称为支持向量机12.3 支持向量机2.线性不可分类(1)向量落在分类带之外且被正确地分了类(2)向量落在分类带之内且被正确地分了类(3)向量被错误地分了类12.3 支持向量机2.线性不可分类此时的目标是在保持具有ri 0的点数尽可能小的条件下，使最近点到超平面的距离尽可能小。此时要最小化的代价函数为12.4 结构模式识别12.4.1 字符串结构识别12.4.2 树结构识别12.4.1 字符串结构识别1.字符串文法文法是一组句法规则，它们能控制字符集

5、中符号产生句子的过程由一个文法G所产生的一组句子称为语言，并记为L(G)。所以句子是符号的串，这些串代表了模 式，而语言对应模式类12.4.1 字符串结构识别1.字符串文法例12.4.1字符串结构示例考虑文法G = (N, T, P, S)，其中N = A, B, C，T = a, b, c，P = S aA, A bA, A bB, B c12.4.1 字符串结构识别2.语义应用句法确定目标结构，语义主要与其正确性有关12.4.1 字符串结构识别3.用自动机作为字符串识别器如何识别一个模式是否属于由文法G产生的语言L(G)。结构识别法的基本概念可借助称为自动机 （计算机器）的数学模型来解释有

6、限自动机是由规则语法产生的语言识别器，可定义为一个五元组12.4.1 字符串结构识别3.用自动机作为字符串识别器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，但不能识别字符串aabab12.4.2 树结构识别1.树文法树文法是由如下五元组所定义扩展树文法X1, X2, , Xn 为非终结符号，k 是一个终结符 号，r(k) = n12.4.2 树结构识别1.树文法在这个树文法中，N = X1, X2, X3, S，S = a, b, c, d, e，其中终结符号表示图12.4.4(b)所示的基元12.4.2 树结构识别2.树自动机一个从树叶向树根扫描的树自动机其中，Q为一组状态有限集；F为一组终结状态集，且是Q的一个子集；fk是Qm Q中的关系，其中m为k的秩，Qm代表Q的自身m次笛卡尔乘积，即Qm = Q Q Q Q12.4.2 树结构识别2.树自动机教程作者（章毓晋）联系信息 通信地址：北京清华大学电子工