模式识别与图像.ppt

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

1、模式识别与图像处理模式识别与图像处理 熊卫华 15#222 引引 言言 与模式识别相关的学科与模式识别相关的学科n n统计学统计学n n概率论概率论n n线性代数（矩阵计算）线性代数（矩阵计算）n n形式语言形式语言n n机器学习机器学习n n人工智能人工智能n n图像处理图像处理n n计算机视觉计算机视觉n n教学方法教学方法n n着重讲述模式识别的基本概念、基本方法。n n介绍图像处理的相关知识。教学目标教学目标n n掌握模式识别的基本概念和方法n n为研究新的模式识别的理论和方法打下基础 参考文献参考文献n nR.Duda,P.Hart,D.Stork,Pattern Classific

2、ation,second edition,2000（有中译本）.n n边肇祺，模式识别（第二版），清华大学出版社，2000。n n蔡元龙，模式识别，西北电讯工程学院出版社，1986。机构、会议、刊物机构、会议、刊物n n1973年 IEEE发起了第一次关于模式识别的国际会议“ICPR”（此后两年一次），成立了国际模式识别协会-“IAPR”n n1977年IEEE成立PAMI委员会，创立IEEE Trans.on PAMI，并支持ICCV,CVPR两个会议n n世界计算机视觉和模式识别领域顶尖期刊IEEE PAMI，全称IEEE Transactions on Pattern Analysis

3、and Machine Intelligencen n国际计算机视觉大会ICCV，全称International Conference on Computer Visionn n世界计算机视觉和模式识别领域顶级国际会议CVPR全称IEEE Conference on Computer Vision and Pattern Recognitionn n其它刊物n nPattern Recognition(PR)Pattern Recognition(PR)n nPattern Recognition Letters(PRL)Pattern Recognition Letters(PRL)n nP

4、attern Analysis and Application(PAA)Pattern Analysis and Application(PAA)n nInternational Journal of Pattern Recognition and International Journal of Pattern Recognition and Artificial Intelligence(IJPRAI)Artificial Intelligence(IJPRAI)模式识别的国内学术组织模式识别的国内学术组织模式识别的国内学术组织模式识别的国内学术组织n n国内的组织有电子学会，通信学会，自

5、动化协会，中文信国内的组织有电子学会，通信学会，自动化协会，中文信息学会息学会.。第第 1 章章 绪论绪论1.1 模式识别和模式的概念模式识别和模式的概念什么是模式（什么是模式（什么是模式（什么是模式（PatternPattern）？）？）？）？什么是模式？什么是模式？n n广义地说，存在于时间和空间中可观察的物体，广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都如果我们可以区别它们是否相同或是否相似，都可以称之为模式。可以称之为模式。n n模式所指的不是事物本身，而是从事物获得的信模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和

6、空间分布息，因此，模式往往表现为具有时间和空间分布的信息。的信息。n n模式的直观特性模式的直观特性:n n可观察性可观察性n n可区分性可区分性n n相似性相似性模式识别的概念模式识别的概念n n模式识别（模式识别（Pattern Recognition Pattern Recognition）直观，无所直观，无所不在，不在，“人以类聚，物以群分人以类聚，物以群分”n n周围物体的认知：桌子、椅子周围物体的认知：桌子、椅子n n人的识别：张三、李四人的识别：张三、李四n n声音的辨别：汽车、火车，狗叫、人语声音的辨别：汽车、火车，狗叫、人语n n气味的分辨：炸带鱼、红烧肉气味的分辨：炸带鱼、

7、红烧肉n n用计算机实现人对各种事物或现象的分析用计算机实现人对各种事物或现象的分析,描述描述,判断判断,识别。识别。n n人和动物的模式识别能力是极其平常的，但对计人和动物的模式识别能力是极其平常的，但对计算机来说却是非常困难的。算机来说却是非常困难的。模式识别的研究模式识别的研究n n目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。n nY=F(X)n nX X的定义域取自特征集的定义域取自特征集n nY Y的值域为类别的标号集的值域为类别的标号集n nF F是模式识别的判别方法是模式识别的判别方法模式识别简史模式识别简史n n1929年 G.

8、Tauschek发明阅读机，能够阅读0-9的数字。n n30年代 Fisher（Ronald Aylmer Fisher）提出统计分类理论，奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。n n50年代 Noam Chemsky 提出形式语言理论 美籍华人傅京荪 提出句法结构模式识别。n n60年代 提出了模糊集理论，模糊模式识别方法得以发展和应用。n n80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经

9、元网络复活，并在模式识别得到较广泛的应用。n n90年代小样本学习理论，支持向量机也受到了很大的重视。模式识别的应用模式识别的应用n n1.1.字符识别：包括印刷体字符的识别；手写体字字符识别：包括印刷体字符的识别；手写体字符的识别（脱机），各种符的识别（脱机），各种OCROCR设备例如信函分拣、设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入；在线手写字符的识别（联机）刊阅读、稿件输入；在线手写字符的识别（联机），各种书写输入板。，各种书写输入板。n n2.2.医疗诊断：心电图，脑电图，染色体，癌细胞医疗诊断：心电图，脑电

10、图，染色体，癌细胞识别，疾病诊断，例如关幼波肝炎专家系统。识别，疾病诊断，例如关幼波肝炎专家系统。n n3.3.遥感：资源卫星照片，气象卫星照片处理，数遥感：资源卫星照片，气象卫星照片处理，数字化地球，图象分辨率可以达到字化地球，图象分辨率可以达到1 1米。米。模式识别的应用模式识别的应用n n4.指纹识别 脸形识别n n5.检测污染分析，大气，水源，环境监测。n n6.自动检测：产品质量自动检测n n7.语声识别，机器翻译，电话号码自动查询，侦听，机器故障判断。n n8.军事应用模式识别方法模式识别方法n n模式识别系统的目标：在特征空间和解释空间之间找到一种映射关系，这种映射也称之为假说。

11、n n特征空间：从模式得到的对分类有用的度特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。量、属性或基元构成的空间。n n解释空间：将解释空间：将c c个类别表示为个类别表示为其中其中 为所属类别的集合，称为解释空间。为所属类别的集合，称为解释空间。假说的两种获得方法假说的两种获得方法n n监督学习、概念驱动或归纳假说：在特征空间中监督学习、概念驱动或归纳假说：在特征空间中找到一个与解释空间的结构相对应的假说。在给找到一个与解释空间的结构相对应的假说。在给定模式下假定一个解决方案，任何在训练集中接定模式下假定一个解决方案，任何在训练集中接近目标的假说也都必须在近目标的假说也都必须

12、在“未知未知”的样本上得到的样本上得到近似的结果。近似的结果。n n依靠已知所属类别的的训练样本集，按它们特征向量依靠已知所属类别的的训练样本集，按它们特征向量的分布来确定假说的分布来确定假说 （通常为一个判别函数），只有在（通常为一个判别函数），只有在判别函数确定之后才能用它对未知的模式进行分类；判别函数确定之后才能用它对未知的模式进行分类；n n对分类的模式要有足够的先验知识，通常需要采集足对分类的模式要有足够的先验知识，通常需要采集足够数量的具有典型性的样本进行训练。够数量的具有典型性的样本进行训练。假说的两种获得方法（续）假说的两种获得方法（续）n n非监督学习、数据驱动或演绎假说：在

13、解释空间非监督学习、数据驱动或演绎假说：在解释空间中找到一个与特征空间的结构相对应的假说。这中找到一个与特征空间的结构相对应的假说。这种方法试图找到一种只以特征空间中的相似关系种方法试图找到一种只以特征空间中的相似关系为基础的有效假说。为基础的有效假说。n n在没有先验知识的情况下，通常采用聚类分析方法，在没有先验知识的情况下，通常采用聚类分析方法，基于基于“物以类聚物以类聚”的观点，用数学方法分析各特征向的观点，用数学方法分析各特征向量之间的距离及分散情况；量之间的距离及分散情况；n n如果特征向量集聚集若干个群，可按群间距离远近把如果特征向量集聚集若干个群，可按群间距离远近把它们划分成类；

14、它们划分成类；n n这种按各类之间的亲疏程度的划分，若事先能知道应这种按各类之间的亲疏程度的划分，若事先能知道应划分成几类，则可获得更好的分类结果。划分成几类，则可获得更好的分类结果。模式分类的主要方法模式分类的主要方法n n数据聚类n n统计分类n n结构模式识别n n神经网络数据聚类数据聚类n n目标：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。n n是一种非监督学习的方法，解决方案是数据驱动的。统计分类统计分类n n基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。n n特征向量分布的获得是基于一个类别已知的训练样本集。n n是一种监督分类的方法，分类器

15、是概念驱动的。结构模式识别结构模式识别n n该方法通过考虑识别对象的各部分之间的联该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。系来达到识别分类的目的。n n识别采用结构匹配的形式，通过计算一个匹识别采用结构匹配的形式，通过计算一个匹配程度值（配程度值（matching scorematching score）来评估一个未知的）来评估一个未知的对象或未知对象某些部分与某种典型模式的对象或未知对象某些部分与某种典型模式的关系如何。关系如何。n n当成功地制定出了一组可以描述对象部分之当成功地制定出了一组可以描述对象部分之间关系的规则后，可以应用一种特殊的结构间关系的规则后，可以应

16、用一种特殊的结构模式识别方法模式识别方法 句法模式识别，来检查一个句法模式识别，来检查一个模式基元的序列是否遵守某种规则，即句法模式基元的序列是否遵守某种规则，即句法规则或语法。规则或语法。神经网络神经网络n n神经网络是受人脑组织的生理学启发而创立的。神经网络是受人脑组织的生理学启发而创立的。n n由一系列互相联系的、相同的单元（神经元）组由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制信号。n n增强或抑制是通过调整神经元相互间联系的权重增强或抑制是通过调整神经元相互间联系的权重系数来（

17、系数来（weightweight）实现。）实现。n n神经网络可以实现监督和非监督学习条件下的分神经网络可以实现监督和非监督学习条件下的分类。类。1.2 模式识别系统模式识别系统n n模式识别系统的基本构成数据获取特征提取和选择预处理分类决策分类器设计模式识别系统组成单元模式识别系统组成单元n n数据获取：用计算机可以运算的符号来表示所研究的对象n n二维图像：文字、指纹、地图、照片等二维图像：文字、指纹、地图、照片等n n一维波形：脑电图、心电图、季节震动波形等一维波形：脑电图、心电图、季节震动波形等n n物理参量和逻辑值：体温、化验数据、参量正常与物理参量和逻辑值：体温、化验数据、参量正常

18、与否的描述否的描述n n预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原模式识别系统组成单元模式识别系统组成单元n n特征提取和选择：对原始数据进行变换，得到特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征最能反映分类本质的特征n n测量空间：原始数据组成的空间测量空间：原始数据组成的空间n n特征空间：分类识别赖以进行的空间特征空间：分类识别赖以进行的空间n n模式表示：维数较高的测量空间模式表示：维数较高的测量空间-维数较低的特征维数较低的特征空间空间n n分类决策：在特征空间中用模式识别方法把被分类决策：在特征空间中用模式识别方法把被识别

19、对象归为某一类别识别对象归为某一类别n n基本做法：在样本训练集基础上确定某个判决规则，基本做法：在样本训练集基础上确定某个判决规则，使得按这种规则对被识别对象进行分类所造成的错使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小误识别率最小或引起的损失最小模式识别过程实例模式识别过程实例n n在传送带上用光学传感器件对鱼按品种分类鲈鱼(Seabass)品种鲑鱼(Salmon)识别过程识别过程n n数据获取：架设一个摄像机，采集一些样本图像，获取样本数据n n预处理：去噪声，用一个分割操作把鱼和鱼之间以及鱼和背景之间分开识别过程识别过程n n特征提取和选择：对单个鱼的信息进

20、行特征选择，特征提取和选择：对单个鱼的信息进行特征选择，从而通过测量某些特征来减少信息量从而通过测量某些特征来减少信息量n n长度长度n n亮度亮度n n宽度宽度n n鱼翅的数量和形状鱼翅的数量和形状n n嘴的位置，等等嘴的位置，等等 n n分类决策：把特征送入决策分类器分类决策：把特征送入决策分类器1.3 模式识别的基本问题模式识别的基本问题一一.模式模式(样本样本)表示方法表示方法1.1.向量表示向量表示 :假设一个样本有假设一个样本有n n个变量个变量(特征特征)2.2.=(X=(X1 1,X,X2 2,Xn)Xn)T T2.2.矩阵表示矩阵表示:N:N个样本，个样本，n n个变量个变量

21、(特征特征)3.3.几何表示几何表示 一维表示一维表示 X X1 1=1.5 X=1.5 X2 2=3=3 二维表示二维表示 X X1 1=(x=(x1 1,x,x2 2)T T=(1,2)=(1,2)T T X X2 2=(x=(x1 1,x,x2 2)T T=(2,1)=(2,1)T T 三维表示三维表示 X X1 1=(x=(x1 1,x,x2 2,x x3 3)T T=(1,1,0)=(1,1,0)T T X X2 2=(x=(x1 1,x,x2 2,x x3 3)T T=(1,0,1)=(1,0,1)T T4.4.基元（链码）表示：基元（链码）表示：在右侧的图中八个基元在右侧的图中八

22、个基元分别表示分别表示0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，八个方向，八个方向和基元线段长度。和基元线段长度。则右侧样本可以表示为则右侧样本可以表示为 X X1 1=006666=006666这种方法将在句法模式识这种方法将在句法模式识别中用到。别中用到。二.模式类的紧致性1.紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。2.2.临界点临界点(样本样本)：在多类样本中，某些样本的值：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本有微小变化时就变成另一类样本称为临界样本（点）。（点）。3.3.紧致集的性质紧致集的性

23、质 要求临界点很少要求临界点很少 集合内的任意两点的连线集合内的任意两点的连线,在线上的点属于在线上的点属于同同 一集合一集合 集合内的每一个点都有足够大的邻域集合内的每一个点都有足够大的邻域,在邻在邻域内只包含同一集合的点域内只包含同一集合的点4.4.模式识别的要求模式识别的要求:满足紧致集，才能很好的分满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法类；如果不满足紧致集，就要采取变换的方法,满足紧致集满足紧致集.三.相似与分类 1.1.两个样本两个样本x xi i，x xj j之间的相似度量满足以下要求：之间的相似度量满足以下要求：应为非负值应为非负值 样本本身相似性度量应

24、最大样本本身相似性度量应最大 度量应满足对称性度量应满足对称性 在满足紧致性的条件下，相似性应该是点间距离的在满足紧致性的条件下，相似性应该是点间距离的 单调函数单调函数 2.2.用各种距离表示相似性：用各种距离表示相似性：绝对值距离绝对值距离 已知两个样本已知两个样本 x xi i=(x=(xi1 i1,x,xi2 i2,x,xi3 i3,x,xin in)T T x xj j=(x=(xj1 j1,x,xj2 j2,x,xj3 j3,x,xjn jn)T T 欧几里德距离欧几里德距离明考夫斯基距离明考夫斯基距离 其中当q=1时为绝对值距离，当q=2时为欧氏距离 切比雪夫距离切比雪夫距离 q

25、 q趋向无穷大时明氏距离的极限情况趋向无穷大时明氏距离的极限情况 马哈拉诺比斯距离马哈拉诺比斯距离 其中其中x xi i，x xj j为特征向量，为特征向量，为协方差。使用的条件是为协方差。使用的条件是 样样 本符合正态分布本符合正态分布 夹角余弦夹角余弦 为为x xi i x xj j的均值的均值 即样本间夹角小的为一类，具有相似性即样本间夹角小的为一类，具有相似性例：例：x x1,1,x x2,2,x x3 3的夹角如图：的夹角如图：因为因为x x1,1,x x2 2 的夹角小的夹角小，所以所以x x1,1,x x2 2 最相似。最相似。x1x2x1x2x3 相关系数相关系数 为为x xi

26、 i x xj j的均值的均值注意：在求相关系数之前，要将数据标准化注意：在求相关系数之前，要将数据标准化3.3.分类的主观性和客观性分类的主观性和客观性 分类带有主观性：目的不同，分类不同。例如：鲸鱼，分类带有主观性：目的不同，分类不同。例如：鲸鱼，牛，马从生物学的角度来讲都属于哺乳类，但是从产业角牛，马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。度来讲鲸鱼属于水产业，牛和马属于畜牧业。分类的客观性：科学性分类的客观性：科学性 判断分类必须有客观标准，因此分类是追求客观性的，判断分类必须有客观标准，因此分类是追求客观性的，但主观性也很难避免，这就是分类

27、的复杂性。但主观性也很难避免，这就是分类的复杂性。四四.特征的生成特征的生成 1.1.低层特征：低层特征：无序尺度：有明确的数量和数值。无序尺度：有明确的数量和数值。有序尺度：有先后、好坏的次序关系，如酒有序尺度：有先后、好坏的次序关系，如酒 分为上，中，下三个等级。分为上，中，下三个等级。名义尺度：无数量、无次序关系，如有红，名义尺度：无数量、无次序关系，如有红，黄两种颜色黄两种颜色 2.2.中层特征：经过计算，变换得到的特征中层特征：经过计算，变换得到的特征 3.3.高层特征：在中层特征的基础上有目的的经过运高层特征：在中层特征的基础上有目的的经过运 算形成算形成例如：椅子的重量例如：椅子

28、的重量=体积体积*比重比重 体积与长，宽，高有关；比重与材料，纹理，颜体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。色有关。这里低、中、高三层特征都有了。五.数据的标准化 1.1.极差标准化，一批样本中，每个特征的最大值极差标准化，一批样本中，每个特征的最大值与最小值之差。与最小值之差。极差极差 极差标准化极差标准化 2.2.方差标准化方差标准化 S Si i 为方差为方差标准化的方法很多，原始数据是否应该标准化，应采用标准化的方法很多，原始数据是否应该标准化，应采用什么方法标准化，都要根据具体情况来定。什么方法标准化，都要根据具体情况来定。1.4 本门课程的

29、主要内容本门课程的主要内容n n第一章 绪论n n第二章 统计判别n n第三章 判别函数n n第四章 特征选择和提取n n第五章神经网络n n第六章图像处理相关数学概念相关数学概念n n随机向量及其分布n n随机向量随机向量n n如果一个对象的特征观察值为如果一个对象的特征观察值为xx1 1,x,x2 2,x,xn n，它可，它可构成一个构成一个n n维的特征向量值维的特征向量值x x，即，即 x x=(x=(x1 1,x,x2 2,x,xn n)T T 式中，式中，x x1 1,x,x2 2,x,xn n为特征向量为特征向量x x的各个分量。的各个分量。n n一个特征可以看作一个特征可以看作

30、n n维空间中的向量或点，此空间称维空间中的向量或点，此空间称为模式的特征空间为模式的特征空间R Rn n。相关数学概念相关数学概念n n随机向量及其分布n n随机向量随机向量n n在模式识别过程中，要对许多具体对象进行测量，在模式识别过程中，要对许多具体对象进行测量，以获得许多次观测值。以获得许多次观测值。n n每次观测值不一定相同，所以对许多对象而言，各每次观测值不一定相同，所以对许多对象而言，各个特征分量都是随机变量，即许多对象的特征向量个特征分量都是随机变量，即许多对象的特征向量在在n n维空间中呈随机性分布，称为随机向量。维空间中呈随机性分布，称为随机向量。相关数学概念相关数学概念n n随机向量及其分布n n随机向量的参数随机向量的参数n n数学期望和方差数学期望和方差n n协方差矩阵协方差矩阵n n 例：求随机变量的数学期望和协方差矩阵例：求随机变量的数学期望和协方差矩阵 相关数学概念相关数学概念n n正态分布n n一维正态密度函数一维正态密度函数相关数学概念相关数学概念n n正态分布n n多维正态密度函数多维正态密度函数小结小结n n模式和模式识别的概念n n模式识别的发展简史和应用n n模式识别的主要方法n n模式识别的系统n n几个相关的数学概念 谢 谢！