模式识别绪论精要.ppt

,Pattern RecognitionCh.1 绪论贺容波安徽工业大学电气信息学院,相关学科,统计学概率论线性代数（矩阵计算）形式语言人工智能图像处理计算机视觉 等等,教学方法,着重讲述模式识别的基本概念，基本方法和算法原理。注重理论与实践紧密结合 实例教学：通过实例讲述如何将所学知识运用到实际应用之中避免引用过多的、繁琐的数学推导,教学目标,掌握模式识别的基本概念和方法有效地运用所学知识和方法解决实际问题为研究新的模式识别的理论和方法打下基础,基本要求,基本：完成课程学习，通过考试，获得学分。提高：能够将所学知识和内容用于课题研究，解决实际问题。飞跃：通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。,讲授课程内容及安排,第一章 绪论 第二章 线性判别函数第三章 Bayes决策 第四章 概率密度估计 第五章 近邻法 第六章 特征提取与选择 上机实习,出勤：10%实验：4学时，三个上机实验，10大作业：20%，两次作业考试：60，开卷开始,课程要求,11:26,7,教材：张学工等编，模式识别 清华大学出版社，2010年，第3版,Ruchard O.Duda等模式分类（Pattern Classification）机械工业出版社，2004年,参考书（一）,11:26,8,参考书（二）模式识别（杨光正 中国科技大学出版社 2003年）第一章 引论第二章 线性判别函数第三章 Bayes决策理论第四章 概率总体的估计第五章 近邻法则和集群第六章 模式特征的抽取和选择第七章 句法模式识别,模式识别应用 傅京孙著（19301985）第一章 引言第二章 统计模式识别第三章 句法模式识别第四章 模式识别在遥感方面的应用第五章 模式识别在地震波解释中的应用第六章 自动视觉检验第七章 模式识别在非数字系统中的故障检出和分析方面的应用第八章 模式识别对医学数据分析的应用第九章 文字识别的进展第十章 自动语音识别,参考书（二）,主要期刊,IEEE Trans.on PAMI，1978-，IEEE Computer SocietyPattern Recognition，1968-，PR Society,ElsevierPattern Recognition Letter，1980-，IAPR,ElsevierInt.Journal of PR and AI,1988-(World Scientific)Pattern Analysis and Applications,1997-(Springer)Int.J.Document Analysis&Recognition,1998-模式识别与人工智能中国图像与图形学学报,1 模式与模式识别的概念2 模式的概念和描述方法3 模式识别系统的组成,本章重点,第1章 绪论,11:26,12,一、模式识别,1.1 模式与模式识别的概念,直观，无所不在儿童认数字：数字符号的识别读书看报：文字识别汽车、火车，狗叫、人语：声音识别人群中寻找一个人：根据面像、形体或其他特征进行识别人类的模式识别能力是极其平常的，时刻在完成某种模式识别的任务。随着社会活动以及生产科研的发展，需要识别的对象种类越来越多，内容越来越复杂和深入，要求越来越高。为了减轻工作强度，希望计算机代替人来完成识别工作；有些场合环境恶劣、存在危险或人类不能接近，需要借助机器、运用分析算法进行识别。,11:26,13,例子：医生诊病过程1)测量病人的体温和血压，化验血沉，询问临床表现；2)通过综合分析，抓住主要病症；3)医生运用自己的知识、经验，根据主要病症、测量化验结果，作出正确的诊断。在模式识别技术中，常用的术语有：样本、模式、特征、类型等等，对照医生诊病过程，有：,a.样本：医院里的众多患者，每个患者都是一个样本；单一样本：医生诊断的某一患者，就是样本空间中的 一个单一样本；样本值：某一患者的化验、检查结果与表征现象。b.模式：各样本值按一定的数据准则综合的结果；模式样本：具有某种模式的样本；模式采集：获取某样本的测量数值的过程；c.特征：患者某些具有显著特征的化验数据及表征；特征选择与提取：能表征(疾病)特异性的化验结果与 表征；,d.判决：医生运用知识、病例经验综合分析给出诊断；判决准则/规则：医生的知识判决结果：将患者明确(或以概率)确定为某一种病症(或多种/并发病症)的患者(及病患严重程度)事实上，最后的结果也成为分类。因此有预先知道类别(已知病症)与未知类别(未知病症)的区别。模式识别：就是以计算机为工具、各种传感器为信息来源，数据计算与处理为方法，对各种现象、事物、状态等进行准确地分析、判断识别与归类。,11:26,17,1.模式识别(Pattern Recognition):使计算机模仿人的感知能力，从感知数据中提取信息（判别物体和行为）的过程。模式识别作为一门学科，是研究用机器完成自动识别事物的工作；研究内容：使计算机做以前只能由人类才能做的事，具备人所具有的、对各种事物或现象进行分析、描述与判断的部分能力。模式识别学科形成于5060年代，与众多学科有联系，尤其与人工智能和图像处理关系密切。,1.1 模式与模式识别的概念,2.机器与人类识别事物原理的比较,人类：具有提取抽象概念的能力 人们在学习与认识事物中会总结出规律，并把这些规律性的东西抽象成“概念”。人之所以能“抽象出概念”，关键能分析事物中哪些是本质，哪些是表面现象。,机器：缺乏抽象能力 对样本辨别事物的最基本方法是计算：对计算机要分析的事物与作为标准的称之为”模板“的相似程度进行计算。要让机器正确辨别事物，要求人能够研究出好的方法，构造出好的系统，使机器辨别事物的能力更强。,11:26,18,1.1 模式与模式识别的概念,11:26,19,3.模式与模式类：模式：需要识别且可测量的对象的描述。这些对象与实际的应用有关，如：字符识别的模式每个字符图像 人脸识别的模式每幅人脸图像模式类：当用一定的度量来衡量两个模式，而找不出它们之间的差别时，它们在这种度量条件下属于同一等价类，就说它们是同一模式类。例如：数字识别有10个类别，每个数字就是一个类。不同模式类之间是可以区分的，应有明确界限。,1.1 模式与模式识别的概念,4.识别最基本的方法：计算 计算机根据已研制的识别算法，把输入的未知模式划入正确类别中，从而实现自动分类。识别算法中的关键环节就是要对待识别事物与标准（称之为“模板”）的相似程度进行计算。,特征向量表示法：将对事物进行度量的指标排成向量的形式。一维表示 X1=1.5 X2=3 二维表示 X1=(x1,x2)T=(1,2)T X2=(x1,x2)T=(2,1)T 三维表示 X1=(x1,x2,x3)T=(1,1,0)T X2=(x1,x2,x3)T=(1,0,1)T 苹果（重量，直径，颜色）,5.模式描述方法,1.1 模式与模式识别的概念,图像的向量表示方法：在计算机里分析的称为数字图像，它由排列整齐的二维网格组成，分为若干行与若干列，相当于一个二维数组，或称矩阵。我们称每个元素为像素。,左图为57的数字图像；一个数字就用57共35个网格是黑是白来表示；如令是黑为“1”，是白为“0”，那么一个数字就可用35维的二进制向量表示。这就是典型的特征向量表示法,1.1 模式与模式识别的概念,结构表示法：由事物的组成成分与相互关系表示例1：一幅景色图像中的房屋，有屋顶、墙、门窗等组成。各种成分之间有相互关系，如墙在屋顶之下，门与窗都在墙上等。这种由组成成分与相互关系表示的表示方法，最好用结构性的表示。常用的有串、树、图。例2：在右侧的图中八个基元分别表示0，1，2，3，4，5，6，7，八个方向和基元线段长度。则右侧样本可以表示为 X1=006666这种方法将在句法模式识别中用到。,1.1 模式与模式识别的概念,例3：用一组基元来描述图中的图形。该图形由四个基本元素（称为基元）组成。两个圆弧段分别用符号“a”和“c”表示，直线段用符号“b”表示。同样，为了便于用形式语言处理，把这些符号组成字符串：“abcb”，这四个基元不仅分别表示了图形中四个线段的局部特征，而且这些基元之间的连接关系。结构性描述就是用一组基元来描述模式。,6.统计模式识别与结构模式识别(1)统计模式识别 基于特征向量表示方法 模式识别用函数表示：Y=F(X)X的定义域取自特征集Y的值域为类别的标号集F是模式识别的判别方法有监督模式识别分类（classification）类别已知：据先验知识，模式有明确的类别；分类：基于带类别标签的训练样本集的分析，研制识别算法，把输入模式划入正确类别中。无监督模式识别聚类（clustering）类别未知：没有模式所属类别的先验知识；聚类：对未知类别的训练样本集，按相似程度形成模式的类别，实现样本归类。（物以类聚）(2)结构模式识别 基于结构性描述方法,1.1 模式与模式识别的概念,二、模式识别简史1929年 G.Tauschek发明阅读机，能够阅读0-9的数字。30年代 Fisher提出统计分类理论，奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。50年代 Noam Chemsky 提出形式语言理论傅京荪提出句法结构模式识别。60年代 L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用。80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。,1.1 模式与模式识别的概念,三.关于模式识别的国内、国际学术组织,1973年 IEEE发起了第一次关于模式识别的国际会议“ICPR”，成立了国际模式识别协会-“IAPR”，每2年召开一次国际学术会议。1977年 IEEE的计算机学会成立了模式分析与机器智能（PAMI）委员会，每2年召开一次模式识别与图象处理学术会议。国内组织：中国自动化学会：模式识别与机器智能(PRMI)专业委员会，1981年成立，IAPR成员组织；人工智能与模式识别专业委员会；中国人工智能学会国内学术机构：中科院模式识别国家重点实验室，中科院计算所，微软研究院，清华大学等。,11:26,26,1.1 模式与模式识别的概念,模式识别学科位置,模式识别：计算机科学与电子工程交叉学科中国：“控制科学与工程”一级学科二级学科：控制理论与控制工程、模式识别与智能系统、系统工程等西方：没有自动控制系自动控制：电子工程系、机械工程系模式识别：电子工程系、计算机科学系,1.1 模式与模式识别的概念,四、模式识别的应用多媒体数据检索（文档、图像、视频、音乐检索）字符识别（印刷体字符的识别；手写体字符的识别（脱机/联机），信函分拣、支票查对、自动排板、稿件输入等）医疗诊断（心电图，脑电图，染色体，癌细胞识别，疾病诊断等）工程（产品缺陷检测、自动导航系统、污染分析）军事（航空摄像分析、雷达和声纳信号检测和分类、自动目标识别等）安全监控（基于生物特征的身份识别、视频监控、交通监控、音视频监听）,1.1 模式与模式识别的概念,现有生物特征识别类型,11:26,29,1.1 模式与模式识别的概念,1.模式识别系统：执行模式识别的计算机系统。,1.2 模式识别系统,2.模式识别系统组成：数据获取，预处理，特征提取选择、分类器设计以及分类决策五部分。,训练过程：对作为训练样本的量测数据进行特征选择与提取，得到它们在特征空间的分布，依据这些分布决定分类器的具体参数，也就是设计分类器的过程。识别过程：分类决策的过程，则是在特征空间中用统计方法把被识别对象归为某一类别。,第一章 绪论,（1）信息获取：用不同形式的传感器构成，实现信息获取与信息在不同媒体之间的转换，非电信号转换成电信号。,1.2模式识别系统,用话筒将声音信号转换成电信号，表现出电压(电流)随时间变化的复杂波形。景物信息在摄像机靶面成像并转换成二维的象素矩阵，每个像素(矩阵元素)的电信号与物体表面反射的光强或颜色信息呈现函数关系,一般输入对象的信息有三种类型：二维图象，如文字、指纹、地图、照片等 一维波形，如脑电图、心电图、机械震动波形等 物理参量和逻辑值，如疾病诊断中病人体温，各种化验数据；或对症状有无描述，如疼与不疼（0/1）,3.模式识别系统构成及功能,（2）预处理去除所获取信息中的噪声，增强有用的信息，及一切必要的使信息纯化的处理过程。预处理这个环节内容很广泛，与要解决的具体问题有关，例如，从图象中将汽车车牌的号码识别出来，就需要先将车牌从图像中找出来，再对车牌进行划分，将每个数字分别划分开。做到这一步以后，才能对每个数字进行识别。以上工作都应该在预处理阶段完成。,1.2 模式识别系统,3.模式识别系统构成及功能,（3）特征选择和提取功能：对所获取的信息实现从测量空间到特征空间的转换。将所获取的原始量测数据转换成能反映事物本质，并将其最有效分类的特征表示。输入：原始的量测数据(经过必要的预处理)，例如由声波变换成的电信号，表现为电压电流幅度随时间的变化，二维图像每个像素所具有的灰度值等。输出：将原始量测数据转换成有效方式表示的信息，从而使分类器能根据这些信息决定样本的类别。,1.2模式识别系统,3.模式识别系统构成及功能,特征选择和提取:选择什么样的方法来描述事物，从而可以有效、牢靠地把事物正确地区分开。,1.2模式识别系统,如令是黑为“1”，是白为“0”，那么一个数字就可用35维的二进制向量表示。这就是典型的特征向量表示法。,另一种方法则是将数字用笔划表示，也就是将它分成一横加上一斜杠表示。这种表示方法属于结构表示法范畴。这种方法没有前一种方法的缺点，但提取这种结构信息也不是一件容易方便的事。,缺点：这种表示与网格的尺寸有关，与字的笔划粗细有关，更主要的是字在网格中的不同位置与转向有关。这个字在网格中略为偏一点，其特征向量表示就会有很大的不一样。这就说明了这种表示的稳定性差。,例：印刷体数字大多通过扫描仪输入，或从图像中获取。这样，一个数字往往用一个NM的数组表示。如果N5，M7，则一个数字就用57共35个网格是黑是白来表示。,（4）分类器设计与分类决策分类器设计：将该特征空间划分成由各类占据的子空间，确定相应的决策分界和判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。分类决策：分类器在分界形式及其具体参数都确定后，用相应的决策分界对待分类样本进行分类决策的过程。,1.2模式识别系统,4.模式识别系统实例（一）,19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：,11:26,37,1.2模式识别系统,待识别的模式：性别（男或女）测量的特征：身高和体重 训练样本：15名已知性别的样本特征,4.模式识别系统实例（一）,目标：希望借助于训练样本的特征建立判别函数（即数学模型）由训练样本得到的特征空间分布图：,11:26,38,1.2模式识别系统,从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。,11:26,39,1.2模式识别系统,鱼类罐头加工厂：将传送带上的鱼按品种自动分类，即把不同的鱼分开。鱼的分类：鲑鱼（salmon）,鲈鱼（sea bass）,4.模式识别系统实例（二）,数据采集：用光学感知手段，定时拍摄鱼的数字图像，将其传入计算机。预处理：增强图像中感兴趣的部分，抑制图像中的噪声，将不同的鱼、鱼与背景分离开来。特征提取（feature extraction）：待分对象鲑鱼和鲈鱼确实存在一些差异，比如长度、宽度、光泽和形状等。利用类别之间的这些差异来分类。,11:26,40,1.2模式识别系统,4.模式识别系统实例（二）,特征提取（feature extraction）：待分对象鲑鱼和鲈鱼确实存在一些差异，比如长度、宽度、光泽和形状等。利用类别之间的这些差异来分类。特征：从模式中提取的、对分类有用的特征。特征选择是模式识别的核心问题之一。分类判别（classification）单一特征先验知识：鲈鱼一般比鲑鱼长。因此可以选择长度为分类特征；长度l超过预定阈值l*时判定为鲈鱼，否则判定为鲑鱼。如何获得长度阈值l*呢？（预定）,11:26,41,1.2模式识别系统,4.模式识别系统实例（二）,利用特征直方图获得长度阈值l*,直方图表明：无论怎样确定长度阈值l*，都不能将两类鱼截然分开，分类错误比较严重。通常，单一特征不足以很好分类。,11:26,42,1.2模式识别系统,4.模式识别系统实例（二）,尝试利用其他特征：鱼的光泽度，用x表示。,11:26,43,1.2模式识别系统,4.模式识别系统实例（二）,利用多个特征进行分类形成特征空间：以每个特征为坐标轴形成的空间。特征的个数，就是特征空间的维数。特征向量：特征空间中的一个点。X=(x1,x2)T表示一条鱼，x1代表长度，x2代表光泽度。分类器设计：要找到一个判定边界,两类问题判定线判定线把特征空间分为两个区域，识别时特征向量落在那个区域就判定为相应类别。其总分类错误比单一特征分类器好一些，但仍存在一些错误的分类。,11:26,44,1.2模式识别系统,4.模式识别系统实例（二）,分类器的推广能力：即分类器对未知模式的正确分类的能力复杂的分类算法导致复杂的判定边界。判决曲线被过分调谐到这些训练样本上，虽然所有训练样本都被正确分类，但其推广能力却很差。比如：图中的?新模式更像鲑鱼，却被分到鲈鱼类了。,11:26,45,1.2模式识别系统,4.模式识别系统实例（二）,简化分类器设计方案分类器设计无需上面那样复杂，即便对训练样本不能完美识别，只要对新模式有足够的推广能力就可以接受。分类器如何自动产生比较简单的判决边界，使其比上面的直线和复杂边界更优秀？如何预测分类器对新模式的推广能力？这些都是模式识别要研究的问题。,在美国某城市银行门口有一台自动取款机，一个来取款的男子往取款机送入了信用卡后，取款机却迟迟不吐出钞票。很快，一位警察赶到现场将此男子带到警署。原来，这个男子的信用卡是偷来的，而抓住这个小偷的正是取款机上安装的虹膜识别系统。通过发射出的红外线，该系统对取款男子的眼睛中的虹膜进行录像，并将录下的虹膜纤维图案与原存款人虹膜纤维图案相对照，发现信用卡并非这个男子所有，于是系统发出警报唤来了警察。,4 实例（三）虹膜 识别,虹膜识别理论依据虹膜,虹膜中间有一直径2.54mm的圆孔，这就是我们熟悉的瞳孔。眼球前部含色素的环形薄膜，由结缔组织细胞、肌纤维等构成，当中是瞳孔。眼球的颜色是由虹膜所含色素的多少决定的。旧称虹彩。,虹膜识别理论依据虹膜识别系统,虹膜识别通过对比虹膜图像特征之间的相似性来确定人们的身份,其核心是使用模式识别、图像处理等方法对人眼睛的虹膜特征进行描述和匹配,从而实现自动的个人身份认证。这种技术在生物测定行业已经被广泛认为是目前精确度、稳定性、可升级性最高的身份识别系统。,虹膜识别理论依据虹膜识别系统特点,生物活性:虹膜是人眼的可见部分，处在巩膜的保护下，具有极强的生物活性。非接触性:从一定距离即可获得虹膜数字图像,无需用户接触设备,对人身没有侵犯，因而容易被公众接受唯一性:唯一性是指每个虹膜所包含的信息都不相同，出现形态完全相同的虹膜组织的可能性远远低于其他组织。稳定性:虹膜在人的一生中都极其稳定，出生前（胎儿 7个月时）已经形成，出生618个月后定型，此后终身不变.一般性疾病不会对虹膜组织造成损伤，不会因职业等因素造成磨损。防伪性:不可能在对视觉无严重影响的情况下用外科手术改变虹膜特征，更不可能将一个人的虹膜组织特征改变得与某个特定对象的特征相同，用照片、录像、尸体的虹膜代替活体的虹膜图像都可被检验出来。,1.捕捉虹膜数据图像,2.为虹膜的图像分析准备过程,3.从虹膜的纹理或类型创造512字节的iriscode,4.使用iriscode模板用于确认,虹膜识别理论依据工作原理,虹膜识别实现方法虹膜识别流程,图像采集,预处理,虹膜特征分析,虹膜图像库,虹膜特征模板,模式匹配,识别结果,虹膜识别应用各行业的广泛应用,学习人类的学习过程：在日常生活中进行模式识别的活动，从学习过程中掌握了很强的分辨事物的能力。机器的学习过程：使用一批包括各类别的训练样本勾画出各种事物在特征空间分布的规律性确定使用分类的具体数学公式及其参数,1.3 模式识别的若干问题,第一章 绪论,分类器设计：求优化解的过程模式识别中的学习与训练是从训练样本提供的数据中找出某种数学式子的最优解，这个最优解使分类器得到一组参数，按这种参数设计的分类器使人们设计的某种准则达到极值。分类器参数的选择或学习过程得到的结果取决于设计者选择什么样的准则函数。不同准则函数的最优解对应不同的学习结果，得到性能不同的分类器。,例：两类训练样本分布图中两类训练样本的分布体现出近似圆形的分布。因此如能把这两个圆形区域确定下来，将它们的边界用某种数学式子近似，那么落在某一个圆形内的样本就可以用这种数学式子来判断。当不一定非要精确地表达不同类样本分布地聚集区时。用一条直线(线性方程)也许可以达到同样的目的。满足直线的方程是一个线性方程，写成f(x1,x2)=ax1+bx2+c=0，而不在该直线上的点则用f(x1,x2)是否大于零或小于零来分辨。,1.3模式识别的若干问题,分类函数类型的确定：圆形区域与线性方程。一般来说，决定使用什么样的分类函数往往是人为决定的。对一个实际分类问题，快速计算、快速分类是十分重要的。,图中两类别样本在二维特征空间中的分布。其中两类别样本分别用“”与“”表示。,两类样本在二维特征空间中有相互穿插很难用简单的分界线将它们完全分开。直线作为分界线 线性分类器对图中所示的样本分布情况，无论直线参数如何设计，总会有错分类发生。如果以错分类最小为原则分类，则图中A直线可能是最佳的分界线，它使错分类的样本数量为最小。,11:27,55,2.模式的紧致性 分类器设计难易程度与模式在特征空间的分布方式有密切关系。,1.3模式识别的若干问题,(a)(b)(c),例1：(a)、(b)与(c)分别表示了两类在空间分布的三种状况。其中(a)中两类样本存在各自明确的区域，它们之间的分界线(或面，超曲面)具有简单的形式，因而也较易区分，(b)中两类虽有各自不同的区域，但分界面的形式比较复杂，因而设计分类器的难度要大得多，如果遇到(c)类的情况则无法将它们正确分类。,2.模式的紧致性紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。性质：(1)临界点的数量与总的点数相比很少。(2)集合中任意两个内点可以用光滑线连接，在该连线上的点也属于这个集合。(3)每个内点都有一个足够大的邻域，在该邻域中只包含同一集合中的点。,1.3模式识别的若干问题,形象的说法：不要混迭，分解面干净利索,特征提取：改善数据的紧致性,1.3模式识别的若干问题,许多问题在量测空间表示时往往不满足紧致性。但是如果它们的确是可分的话，这就意味着可以通过一种变换，使它们在相应的特征空间中界线分明，也就是具有了紧致性。模式识别系统设计的任务就是要寻找这样一种变换，即选择一种特征空间，使不同类别的样本能正确地分开。因此在讨论模式识别的问题时，通常假设同一类的各个模式在该空间中组成一个紧致集。至于如何找到这种变换还没有一种统一的有效的理论与方法。,3.距离和相似性度量在特征空间中用特征向量描述样本的属性，把相似性度量用距离量表示。给定一个输入样本集合，用D维空间中的一个点表示某个样本，可以选择某个随距离增加而下降的函数f作为两个样本 和 之间相似性度量,1.3模式识别的若干问题,欧式距离的减函数,绝对值偏差的减函数,偏差的夹角,THANK YOU VERY MUCH！,本章到此结束下一章“线性判别函数”,