模式识别导论.ppt

《模式识别导论.ppt》由会员分享，可在线阅读，更多相关《模式识别导论.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别导论2022-9-7现在学习的是第1页，共47页第一章第一章 概论概论 1-1 模式识别的基本概念模式识别的基本概念一.模式识别的基本定义 模式(pattern)-存在于时间，空间中可观察的事 物,具有时间或空间分布的信息。模式识别(Pattern Recognition)-用计算机实现 人对各种事物或现象的分析,描述,判断,识别。模式识别与图象识别，图象处理的关系 模式识别是模拟人的某些功能 模拟人的视觉:计算机+光学系统 模拟人的听觉:计算机+声音传感器 模拟人的嗅觉和触觉:计算机+传感器2022-9-7现在学习的是第2页，共47页二.模式识别的发展史 1929年 G.Tausch

2、ek发明阅读机，能够阅读0-9的数字。30年代 Fisher提出统计分类理论,奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。50年代 Noam Chemsky 提出形式语言理论,美籍华人付京荪 提出句法结构模式识别。60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。2022-9-7现在学习的是第3页，共47页 80年代 Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别

3、和人工智能上得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。2022-9-7现在学习的是第4页，共47页三.关于模式识别的国内、国际学术组织 1973年 IEEE发起了第一次关于模式识别的国际会议“ICPR”，成立了国际模式识别协会-“IAPR”，每2年召开一次国际学术会议。1977年 IEEE的计算机学会成立了模式分析与机器智能（PAMI）委员会，每2年召开一次模式识别与图象处理学术会议。国内的组织有电子学会，通信学会，自动化协会，中文信息学会.。2022-9-7现在学习的是第5页，共47页1-2 模式识别系统模式识别系统 信息获取：是通过传感器，将光或声音等信息转化

4、为电信息。信息可以是二维的图象,如文字，图象等；也可以是一维的波形，如声波，心电图，脑电图；还可以是物理量与逻辑值。预处理：包括AD,二值化，图象的平滑，变换，增强，恢复，滤波等,主要指图象处理。2022-9-7现在学习的是第6页，共47页 特征抽取和选择：在模式识别中，需要进行特征的抽取和选择。例如，一幅64x64的图象可以得到4096个数据，这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。分类决策：在特征空间中对被识别对象进

5、行分类。2022-9-7现在学习的是第7页，共47页1-3 模式识别的应用模式识别的应用u字符识别：包括印刷体字符的识别；手写体字符的识别（脱机），各种OCR设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入；在线手写字符的识别（联机），各种书写输入板。u医疗诊断：心电图，脑电图，染色体，癌细胞识别，疾病诊断，例如关幼波肝炎专家系统。u遥感：资源卫星照片，气象卫星照片处理，数字化地球，图象分辨率可以达到1米。u指纹识别与脸形识别。u检测污染分析，大气，水源，环境监测。2022-9-7现在学习的是第8页，共47页u自动检测：产品质量自动检测u语声识别，机器翻译，电话号码

6、自动查询，侦 听，机器故障判断。u军事应用2022-9-7现在学习的是第9页，共47页1-4 模式识别的基本问题模式识别的基本问题一.模式(样本)表示方法向量表示:假设一个样本有n个变量(特征)=(X1,X2,Xn)T2.矩阵表示:N个样本，n个变量(特征)变 量 样 本 x1 x2 xn X1 X11 X12 X1n X2 X21 X22 X2n XN XN1 XN2 XNn 2022-9-7现在学习的是第10页，共47页几何表示 一维表示 X1=1.5 X2=3 二维表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T 三维表示 X1=(x1,x2,x3)T=(

7、1,1,0)T X2=(x1,x2,x3)T=(1,0,1)T2022-9-7现在学习的是第11页，共47页基元（链码）表示：在右侧的图中八个基元分别表0,1,2,3,4,5,6,7,八个方向和基元线段长度。则右侧样本可以表示为X1=006666。这种方法将在句法模式识别中用到。2022-9-7现在学习的是第12页，共47页二二.模式类的紧致性模式类的紧致性紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。2022-9-7现在学习的是第13页，共47页紧致集的性质要求临界点

8、很少集合内的任意两点的连线,在线上的点属于同 一集合集合内的每一个点都有足够大的邻域,在邻域内只包含同一集合的点模式识别的要求:满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法,满足紧致集.2022-9-7现在学习的是第14页，共47页三三.相似与分类相似与分类两个样本xi，xj 之间的相似度量满足以下要求：应为非负值样本本身相似性度量应最大度量应满足对称性在满足紧致性的条件下，相似性应该是点间距离的 单调函数用各种距离表示相似性：绝对值距离 已知两个样本 Xi=(xi1,xi2,xi3,xin)T Xj=(xj1,xj2,xj3,xjn)T 2022-9-7现在学习的是第15

9、页，共47页 欧几里德距离明考夫斯基距离 其中当q=1时为绝对值距离，当q=2时为欧氏距离nkjkikijXXd1|nkjkikijXXd12nkjkikqijXXqqd1|1)(2022-9-7现在学习的是第16页，共47页切比雪夫距离 q趋向无穷大时是明氏距离的极限情况马哈拉诺比斯距离 其中xi，xj为特征向量，为协方差。使用的条件是 样本符合正态分布|max)(1jkiknkijXXd1)(jijiTijXXXXMd2022-9-7现在学习的是第17页，共47页夹角余弦 即样本间夹角小的为一类。例：x1,x2,x3的夹角如图：因为x1,x2 的夹角小，所以x1,x2 最相似。nkjknk

10、iknkjkikijXXXXC12121x1x2x32022-9-7现在学习的是第18页，共47页 相关系数 为xi xj的均值 注意：在求相关系数之前，要将数据标准化分类的主 观性和客观性 分类带有主观性：目的不同，分类不同。例如：鲸鱼，牛，马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。分类的客观性：科学性判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类的复杂性。nknkjkjikinkjkjikiXXXXXXXXrij11221jiXX,2022-9-7现在学习的是第19页，共47页四.特征的生成 低层特征：无序尺度：有

11、明确的数量和数值。有序尺度：有先后、好坏的次序关系，如酒分为上，中，下三个等级。名义尺度：无数量、无次序关系，如有红，黄两种颜色中层特征：经过计算，变换得到的特征高层特征：在中层特征的基础上有目的的经过运 算形成例如：椅子的重量=体积*比重其中体积与长，宽，高有关；比重与材料，纹 理，颜色有关。这里低、中、高三层特征都有了。2022-9-7现在学习的是第20页，共47页五.数据的标准化 极差标准化，一批样本中，每个特征的最大值与最小值之差。极差 极差标准化 方差标准化 Si 为方差标准化的方法很多，原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。ijijiXXRminmax

12、iiijRXXXijiiijSXXXij2022-9-7现在学习的是第21页，共47页1-5 1-5 模式识别应用举例模式识别应用举例邮政编码是十个手写数字组成，属于比较简单的手写体字符识别。但由于邮政编码的广泛书写者及书写习惯大不相同，书写工具不同及书写时的随机变化，同一数字的字形是多种多样的。在个别情况下，某一数字的字形变化会逐渐接近别的数字，如下图：不同数字之间字形的连续变化2022-9-7现在学习的是第22页，共47页 这种由量变到质变的过程给识别带来极大的困难。下面我们简单介绍一种邮政编码的识别方法，对模式识别系统有初步了解。2022-9-7现在学习的是第23页，共47页 一一.二值

13、化处理二值化处理 对于字符识别，字符图象不需要256个灰度级，只要黑白两级即可。因此图象的存贮量可以大大压缩，加快处理速度。二值化的方法是建立直方图如下。0IB:背景灰度IW:图象灰度IT:直方图谷点IB ITIWf(I)灰度 一一.二值化处理二值化处理 对于字符识别，字符图象不需要256个灰度级，只要黑白两级即可。因此图象的存贮量可以大大压缩，加快处理速度。二值化的方法是建立直方图如下：1-5 模式识别应用举例模式识别应用举例2022-9-7现在学习的是第24页，共47页若取谷点IT作为阈值，则 这样就可以把一个多灰度级的图象变成二值图象。但实际上谷点IT常常是不明显的，而且是变化的，因此阀

14、值IT的选择是非常重要的。根据图象的复杂程度，我们可以选取固定阀值和自动阀值。固定阀值：取 IT为固定值。手动阀值：用人工调节IT的大小。自动阀值：根据图象变化，可自动调整二值化的阀值的大小，使图象最好。01)(IfI ITI IT2022-9-7现在学习的是第25页，共47页 阀值IT的数学表示为：I IT T=T=T（X X，Y Y），），N N（X X，Y Y），），g g（X X，Y Y）其中(X，Y)为象素坐标，N（X，Y）为象素周围局部灰度特征，g(X，Y)为灰度。整体阀值选择：整体阀值选择：IT=Tg（X，Y），只由直方图谷点象素的灰度决定阀值，效果较差。局部阀值选择局部阀值选择

15、：IT=Tg（X，Y），N（X，Y）这种方法主要根据一点与其周围各点的平均关系来定阀值，所以只适合于噪声变化平缓的图象。动态阀值选择动态阀值选择：IT=T（X，Y），N（X，Y），g（X，Y）该方法的要点是通过对象素的灰度的反复调整，修改直方图，使谷点清晰或单峰变双峰。2022-9-7现在学习的是第26页，共47页二二.平滑处理平滑处理 对于二值化后的图象，由于噪声的干扰，会存在一些黑白的孤立点和边缘上的凹凸点。1.除孤立点外，用九点窗扫描，用逻辑式：若周围若周围8 8个点为个点为“0 0”,扫描点为扫描点为“1 1”则把扫描点由则把扫描点由“1 1”“0 0”。若周围若周围8 8个点为个点为

16、“1 1”,扫描点为扫描点为“0 0”则把扫描点由则把扫描点由“0 0”“1 1”。)()(ihfdcbaeihgfdcbaeeabcdefghi2022-9-7现在学习的是第27页，共47页2.2.除边缘凹凸点除边缘凹凸点：除凸点的四种情况逻辑式:中心点由“1”“0”1111fdcbaefihcbefihgdehgdbae00 01 00 010000 00 10 00000010 2022-9-7现在学习的是第28页，共47页补凹点：四种情况 1 10 1 101 1 1 01 1 1 101 1fdbefhbefhdehdbe逻辑式：2022-9-7现在学习的是第29页，共47页三三.细

17、化处理细化处理 因为各种字符笔画粗细不同为抽取特征方便和减小信息量，希望把笔画宽度减小到一个象素的宽度，这样字符笔画就变成一个骨架，消除了笔画粗细对识别的影响。细化的方法很多，我们介绍的方法是逐渐去掉文字的边缘点。方法：用3X3辅助矩阵去顺序扫描文字点阵的每个点，应用细化逻辑来判断所扫描的每个点应除掉还是保留。2022-9-7现在学习的是第30页，共47页细化逻辑设计规则细化逻辑设计规则:（1）按上-下-左-右顺序去掉边缘点 第一次扫描只去掉上边缘点 第二次扫描只去掉下边缘点 第三次扫描只去掉左边缘点 第四次扫描只去掉右边缘点 上边缘点 下边缘点 左边缘点 右边缘点 0 1 1 0 01 10

18、 2022-9-7现在学习的是第31页，共47页（2）不能使笔画断线，应保留连点（3）保留端点 0 1 1 1 0 1 010 1 0 111 0 1 0 1 0 10000100100100100000000110000001100000000101000000100010010100001000100002022-9-7现在学习的是第32页，共47页（4）保留节点（三叉点，四叉点）010111 0 01 11001 0 111010 10011 100101110101010101012022-9-7现在学习的是第33页，共47页（5）保留左右角点（6）保留上下角点 00011010000

19、001100110011000000101100 0000101100000100110110100001100100002022-9-7现在学习的是第34页，共47页 根据以上规则，可以编制软件程序也可以设计硬件逻辑电路，经多次扫描细化就只剩下字符骨架了。如图1-4所示。图1-4 文字经过平滑和细化变化情况2022-9-7现在学习的是第35页，共47页四四.跟踪和抽取特征跟踪和抽取特征 1.跟踪规则（1）跟踪从任一端点开始每个端点只抽一次特征（2）按逆时针方向（）沿骨架移动一 周，直到重新回到原端点。（3）跟踪方向的先后顺序由下列办法确定。上次跟踪方向，检查下次跟踪方向的先后次序 abdbc

20、ba6312825312781:dddddfddddddf2022-9-7现在学习的是第36页，共47页 例如。上次跟踪方向是f7，下次跟踪次序为：8534247534123:dddddfddddddf2756461756345:dddddfddddddf4178683178567:dddddfddddddf D6D5D8D7D1D300000111111f6 f5f8 f7 f1 f3 d5d4d3d6d9d2d7d8d1f1 f2 f3 f4 f5 f6 f7 f82022-9-7现在学习的是第37页，共47页2.抽特征：每跟踪一步就要抽取方向特征，凹凸特征和分支特征。下面对这三种特征详细

21、讨论。（1）方向特征：按f1 f8 共8个跟踪方向可获得8个方向特征。（2）线特征：包括凹凸平三种特征 方向增量f 定义如下：x x x x x x x x x x x x x x x f=0 f=+1f=+2f=-1f=-22022-9-7现在学习的是第38页，共47页 凹凸平定义状态图：凹：f=-2 连续两个f=-1 凸：f=+2 连续两个f=+1 平：f=0+1，+2凸 +2凸 0平 0+0平+1平 0平+1平+2凸 -1平-2凹-1平-2凹-1，-2凹2022-9-7现在学习的是第39页，共47页（3）分支特征（点特征）包括端点，三叉点，四叉点，连点 X=1时，d9 为端点 X=2时，

22、d9 为三叉点 X=3时，d9 为四叉点 X=4时，d9 为连点 811921kkkdddX82,1 k101011101三叉点 规定8112022-9-7现在学习的是第40页，共47页例如：d1=d2=d3=d5=d7=d9=13)11111100(121X2022-9-7现在学习的是第41页，共47页四.分类判决 采用序贯分类方法：跟踪一步抽取方向特征，点特征，线特征三种特征，用这三种特征进行分类判决，若不能确定，再跟踪一步抽取三种特征，再进行分类判决，直到确定类别为止。判决跟踪一步抽取特征判决跟踪一步抽取特征2022-9-7现在学习的是第42页，共47页 1.建立训练样本标准库：假设有K

23、个已知类别的训练样本，抽取特征序列L1，L2LK代表K个数字，用它建立训练样本标准库。2.顺序逻辑判决：假设输入字符为X，它共有个端点，因此字符X由S1，S2，S条特征序列组成，而每一个特征序列又是由若干按一定顺序出现的特征组成：（由方向，分支和线特征组成）eeeTTTSTTTSTTTSX21222212112111,2022-9-7现在学习的是第43页，共47页（1）S1=L1？（2）X=L1？T11符合L1？T12符合L1？T1e符合L1？S1不符合L1S1符合L1否否否是是是S1符合L1？S2符合L1？S2符合L1？X符合L1是是是否否否X不符合L12022-9-7现在学习的是第44页，

24、共47页（3）X=？X符合L1？X符合L2？X符合LK？识别结束是是是否拒识否否2022-9-7现在学习的是第45页，共47页参考书参考书 模式识别模式识别 人民邮电出版社人民邮电出版社 罗耀光罗耀光 盛立东盛立东 模式识别模式识别 清华大学出版社清华大学出版社 边肇祺边肇祺 模式识别及应用模式识别及应用 科学出版社科学出版社 付京荪付京荪 Syntactic Pattern Recognition and Application K.S.Fu Pattern Recognition Principles J.T.Tom R.C.Gouzales2022-9-7现在学习的是第46页，共47页 作业：大型上机作业题 考试：开卷考试2022-9-7现在学习的是第47页，共47页