模式识别

模式识别(PatternRecognition)武汉大学计算机学院2007级本科生课程Email:[e-mail]第一讲引言●教材李弼程,邵美珍,黄洁.模式识别原理与应用.西安电子科技大学出版社,2008.●参考著作杨光正等.模式识别.中国科学科技大学出版社,2003.Sergios等.PatternRecognition(英文影印版,第二版),机械工业出版社,2004.引言•课程主要内容统计识别的基本理论(Bayes决策理论,概率密度估计)统计识别的基本方法(判别函数,聚类分析)特征提取模式特征的集成方法(模糊模式识别方法,神经网络模式识别方法)模式识别应用举例(数字识别或人脸识别)●考核成绩=平时成绩30%+笔试70%其中：平时成绩=听课+课堂讨论+作业（含上机作业）引言国内外相关重要期刊和会议•IEEETransactionsonPatternAnalysisandMachineIntelligence(PAMI)•NeuralNetworks•PatternRecognition•PatternRecognitionLetter•MachineLearning•NeuralComputation•《模式识别与人工智能》•IEEEInternationalConferenceonComputerVisionandPatternRecognition(CVPR)•IEEEInternationalConferenceonMachineLearning(ICML)……引言•人脸跟踪与识别引言第1章概论1.1模式识别的基本概念1.2模式识别系统1.3模式识别的基本方法1.4模式识别的应用1.5模式识别的基本问题1.1模式识别的基本概念•定义(Definition)Patternrecognitionisthestudyofhowmachinescanobservetheenvironment,learntodistinguishpatternsofinterestfromtheirbackground,andmakesoundandreasonabledecisionsaboutthecategoriesofthepatterns.(AnilK.Jain)1.1模式识别的基本概念模式(pattern)：具有某种特定性质的观察对象。广义地，存在于时间、空间中可观察的事物，具有时间或空间分布的信息。观察对象举例：一个数字、一句话、一张照片等都是观察对象，都能成为模式识别中的识别对象。模式识别(PatternRecognition)：用计算机实现人对各种事物或现象的分析、描述、判断、识别。模式类：具有相似特性的模式的集合。（模式与模式类的关系相当于集合论中的元素与集合的关系）1.1模式识别的基本概念模式识别与图像处理、图像识别的关系：模式识别是模拟人的某些功能。模拟人的视觉：计算机+图像传感器模拟人的听觉：计算机+声音传感器模拟人的嗅觉和触觉：计算机+嗅觉/触觉传感器模式识别技术当前主要是对视觉和听觉能力的模拟。模拟人的视觉能力就是用计算机来做图像识别和理解工作；模拟人的听觉就是用计算机来做语音（或者各种声音）识别和理解方面的工作。1.1模式识别的基本概念模式识别是一种智能活动，包括分析和判断两个过程。分析过程：确定用于划分模式类的特征及其表达方法；判断过程：依据待识别对象的特征，将其判属于某一个模式类。•发展历史1.1模式识别的基本概念----1929年G.Tauschek发明阅读机，能够阅读0-9的数字。----20世纪30年代Fisher提出统计分类理论，奠定了统计模式识别的基础。在60～70年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。----50年代NoamChemsky提出形式语言理论，美籍华人付京荪提出句法结构模式识别。----60年代L.A.Zadeh提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。----80年代Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。----90年代小样本学习理论，支持向量机也受到了很大的重视。1.1模式识别的基本概念1.2模式识别系统信息获取：对于人脑识别而言,人脑通过感觉器官获取模式信息。对于机器识别来说,由于计算机只能处理数字信号,计算机获取模式信息意味着实现观察对象的数字化表达。信息获取是通过传感器，将光或声音等信息转化为电信息。信息可以是二维的图像如文字、图像等；可以是一维的波形如声波、心电图、脑电图；也可以是物理量与逻辑值。统计模式识别系统组成框图1.2模式识别系统预处理：在得到模式的数字化表达后,往往需要对它进行预处理，以便去除或减少噪声的影响，突出有用信息。对于图像信息，采用数字图像处理技术作为其预处理技术，主要有二值化、图像平滑、变换、增强、恢复、滤波、几何校正等。1.2模式识别系统特征提取和选择：在模式识别中，需要进行特征的抽取和选择，如，一幅6464的灰度图像可以得到4096个数据，这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。1.2模式识别系统特征是用于描述模式性质(特性)的一种定量的概念,通过对模式的分析得到一组特征,称这个过程为特征形成。特征一般有两种表达方法:(1)将特征表达为数值;(2)将特征表达为基元。1.2模式识别系统12(,,,)dxxxx(1)当将特征表达为数值时,一个模式的d个特征值就构成了一个特征向量,记为x,即其中,x的每个分量xi(i=1,2,…,d)对应一个特征。(2)当特征表达为基元时,一个模式表述为一个句子,记为x,即12dxxxx其中，xi(i=1,2,…,d)为基元，反映构成模式的基本要素。1.2模式识别系统通常用于描述模式性质的特征很多,需要从一组特征中挑选出一些最有效的特征以降低特征空间维数,即特征选择。特征提取是指采用变换(或映射)实现由模式测量空间向特征空间的转变,或者将特征空间的维数从高维变成低维。1.2模式识别系统举例：通常遥感成像光谱仪波段数达数百个之多,如果直接用原始数据进行地物分类,会因数据量太大而导致计算复杂,且分类效果不一定好,可通过变换或映射的方法,由原始数据空间变换到特征空间,得到最能反映模式本质的特征,同时降低空间维数。1.2模式识别系统分类器包括分类器设计和分类决策两部分。分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。分类决策：在特征空间中对被识别对象进行分类。1.2模式识别系统说明：(1)基于机器学习的模式识别系统通常由两个过程组成,即分类器设计(简称设计)和分类判决(简称实现)。一般是用一定数量的样本进行分类器设计,这些样本的所属类别已知,称为训练样本。实现是用所设计的分类器对待识别模式进行分类判决(或分类决策)。1.2模式识别系统说明：(2)模式类是指具有相似特性的模式的集合，模式和模式类的关系就是元素和集合的关系。模式的分类过程，事实上就是判定表征观察对象的元素和指定集合的从属关系的过程。当元素只和某个集合具有从属关系时，就将该对象判属于该集合对应的类；当元素和多个集合具有从属关系时，既可以任选一类进行判决，也可以拒绝判决；当元素和任何一个集合都不具有从属关系时，不作分类判决，即拒绝判决。1.3模式识别的基本方法1.模板匹配法(1)首先对每个类别建立一个或多个模板；(2)输入样本和数据库中每个类别的模板进行比较，求相关或距离；(3)根据相关性或距离大小进行决策。优点：直接、简单缺点：适应性差1.3模式识别的基本方法2.统计模式识别法统计模式识别把观察对象表达为一个随机向量(即特征向量),将模式类表达为由有穷或无穷个具有相似数值特性的模式组成的集合。识别是从模式中提取一组特性的度量,构成特征向量来表示模式,然后通过划分特征空间的方式进行分类。统计模式识别系统构成：主要由信息获取、预处理、特征提取和选择以及分类器4部分组成；其中，分类器包括分类器设计和分类决策。优点：理论较成熟，适用于用较少特征就能描述观察对象的场合，能考虑干扰、噪声等的影响缺点：对于结构复杂模式的特征提取较为困难，不能反映模式的结构特征1.3模式识别的基本方法3.句法模式识别法(1)许多复杂的模式可以分解为简单的子模式，这些子模式组成所谓“基元”(2)每个模式都可以由基元根据一定的关系来组成(3)基元可以认为是语言中的字母，每个模式都可以认为是一个句子，关系可以认为是语法或句法(4)模式的相似性由句子的相似性来决定(5)用已知类别的训练样本进行学习，产生该类或至少是这些样本的方法，该学习和训练过程称为文法推断。􀁺优点：适合结构性强的模式􀁺缺点：抗噪声能力差，计算复杂度高1.3模式识别的基本方法信息获取预处理模式表达文法推断句法分析图句法模式识别系统组成其中，模式表达包括两部分：模式分割和基元及关系的识别。对于一个模式，经过预处理并对模式分解提取基元后，得到表征模式的句子，然后进行句法分析，判断它是否能被代表某个模式类的文法所接受，最终给出模式结构描述和识别结果。训练过程识别过程1.3模式识别的基本方法4.神经网络模式识别(1)神经网络模式识别主要利用人工神经网络的学习、记忆和归纳功能,先根据训练样本训练分类器，再利用分类器对待识别对象进行分类决策(2)大规模并行计算(3)学习、推广、自适应、容错、分布表达和计算优点：可以有效的解决一些复杂的非线性问题􀁺缺点：模型还在不断完善之中，目前能识别的模式类还不够多1.3模式识别的基本方法方法表达识别函数主要理论支撑模板匹配样本、像元、曲线相关、距离度量几何学统计方法特征决策函数概率论与数理统计句法方法基元规则、语法形式语言、自动机技术神经网络样本、像元、特征网络函数神经生理学、心理学表几种基本模式识别方法的比较1.4模式识别的应用1.字符识别：包括印刷体字符的识别；手写体字符的识别（脱机），各种OCR设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入；在线手写字符的识别（联机），各种书写输入板。2.医疗诊断：心电图，脑电图，染色体，癌细胞识别，疾病诊断。3.遥感：资源卫星照片，气象卫星照片处理，数字地球，图像分辨率可以达到0.3米。1.4模式识别的应用4.指纹识别，人脸识别5.检测污染分析，大气，水源，环境监测。6.自动检测：产品质量自动检测7.语声识别，机器翻译，电话号码自动查询，侦听，机器故障判断。8.军事应用1.5模式识别的基本问题一.模式(样本)表示方法1.向量表示:假设一个样本有n个变量(特征)Ⅹ=(X1,X2,…,Xn)T2.矩阵表示:N个样本，n个变量(特征)变量样本x1x2…xnX1X11X12…X1nX2X21X22…X2n……………XNXN1XN2…XNn1.5模式识别的基本问题3.几何表示1D表示X1=0.5X2=32D表示X1=(x1,x2)T=(1,2)TX2=(x1,x2)T=(2,1)T3D表示X1=(x1,x2,x3)T=(1,1,0)TX2=(x1,x2,x3)T=(1,0,1)T1.5模式识别的基本问题4.基元（链码）表示：在右侧的图中八个基元分别表示0，1，2，3，4，5，6，7，八个方向和基元线段长度。则右侧样本可以表示为X1=006666该方法在句法模式识别中用到。1.5模式识别的基本问题二.模式类的紧致性1.紧致集同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。1.5模式识别的基本问题2.临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。3.紧致集的性质①要求临界点很少②集合内的任意两点的连线，在线上的点属于同一集合③集合内的每一个点都有足够大的邻域，在邻域内只包含同一集合的点4.模