c1 引言 模式识别课程武汉大学

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第一章 模式识别概论,*,模式识别,孙和利,武汉大学,遥感信息工程学院,sunheli,1,引 言,2,课程对象,模式识别学科硕士研究生的专业基础课,3,与模式识别相关的学科,统计学,概率论,线性代数（矩阵计算）,形式语言,机器学习,人工智能,图像处理,计算机视觉,4,教学方法,着重讲述模式识别的基本概念，基本方法和算法原理。,注重理论与实践紧密结合,实例教学：通过大量实例讲述如何将所学知识运用到实际应用之中,避免引用过多的、繁琐的数学推导。,5,教学目标,掌握模式识别的基本概念和方法,有效地运用所学知识和方法解决实际问题,为研究新的模式识别的理论和方法打下基础,6,教学效果,基本：完成课程学习，通过考试，获得学分。,提高：能够将所学知识和内容用于课题研究，解决实际问题。,飞跃：通过模式识别的学习，改进思维方式，为将来的工作打好基础，终身受益。,7,教材/参考文献,舒宁等，模式识别的理论与方法，武汉大学出版社，2004,。.,边肇祺等，,模式识别,（第二版），清华大学出版社，2000。,蔡元龙，,模式识别,，西北电讯工程学院出版社，1986。,8,本门课程的主要内容,第一章 概论,第二章,贝叶斯决策理论,第三章,判别函数与确定性分类器,第四章,聚类分析,第五章,模式特征分析与选取,第六章,模糊集合理论在模式识别中的应用,第七章,句法模式识别,第八章,神经网络在模式识别中的应用,9,第一章 模式识别概论,1-1 模式识别的基本概念,1-2 模式识别系统,1-3 模式识别的应用,1-4 模式识别的基本问题,10,1-1 模式识别的基本概念,一.模式识别的基本定义,模式(,pattern),-,存在于时间，空间中可观察,的事物，具有时间或空间分布的信息。,-,-,识别的对象，是对客体定量的或,结构的描述。,广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。,模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。,11,模式的直观特性:,可观察性,可区分性,相似性,12,模式识别(,Pattern Recognition),-,用计算机实现,人对各种事物或现象的分析,描述,判断,识别。,周围物体的认知：桌子、椅子,人的识别：张三、李四,声音的辨别：汽车、火车，狗叫、人语,气味的分辩：炸带鱼、红烧肉,人和动物的模式识别能力是极其平常的，但对计算机来说却是非常困难的。,模式类,-,具有共同特征的模式的集合。,识别,-,对模式类的分辨，判断，分类。,目的,-,提高计算机的感知能力，开拓计算机的应用。,13,模式识别的研究,目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。,Y = F(,X,),X,的定义域取自特征集,Y,的值域为类别的标号集,F,是模式识别的判别方法,14,模式识别与图象识别，图象处理的关系,模式识别是模拟人的某些功能,模拟人的视觉: 计算机+光学系统,模拟人的听觉: 计算机+声音传感器,模拟人的嗅觉和触觉: 计算机+传感器,15,二.模式识别的发展史,1929年,G.,Tauschek,发明阅读机 ，能够阅读0-9的数字。,30年代,Fisher,提出统计分类理论,奠定了统计模式识别的基础。因此，在6070年代，统计模式识别发展很快，但由于被识别的模式愈来愈复杂，特征也愈多，就出现“维数灾难”。但由于计算机运算速度的迅猛发展，这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。,16,50年代,Noam Chemsky,提出形式语言理论,美籍华人付京荪 提出句法结构模式识别。,60年代,L.A.,Zadeh,提出了模糊集理论，模糊模式识别理论得到了较广泛的应用。,80年代,Hopfield,提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。,90年代 小样本学习理论，支持向量机也受到了很大的重视。,17,三.关于模式识别的国内、国际学术组织,1973年,IEEE,发起了第一次关于模式识别的国际会议“,ICPR”，,成立了国际模式识别协会-“,IAPR”，,每2年召开一次国际学术会议。,1977年,IEEE,的计算机学会成立了模式分析与机器智能（,PAMI）,委员会，每2年召开一次模式识别与图象处理学术会议。,国内的组织有电子学会，通信学会，自动化协会，中文信息学会.。,18,1-2模式识别方法及模式识别系统,模式识别方法,模式识别系统的目标：在特征空间和解释空间之间找到一种映射关系，这种映射也称之为假说。,特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。,解释空间：将,c,个类别表示为,i, i=1,2,c,其中,为所属类别的集合，称为解释空间。,19,假说的两种获得方法,监督学习、概念驱动或归纳假说：在特征空间中找到一个与解释空间的结构相对应的假说。在给定模式下假定一个解决方案，任何在训练集中接近目标的假说也都必须在“未知”的样本上得到近似的结果。,依靠已知所属类别的的训练样本集，按它们特征向量的分布来确定假说 （通常为一个判别函数），只有在判别函数确定之后才能用它对未知的模式进行分类；,对分类的模式要有足够的先验知识，通常需要采集足够数量的具有典型性的样本进行训练。,20,假说的两种获得方法（续）,非监督学习、数据驱动或演绎假说：在解释空间中找到一个与特征空间的结构相对应的假说。这种方法试图找到一种只以特征空间中的相似关系为基础的有效假说。,在没有先验知识的情况下，通常采用聚类分析方法，基于“物以类聚”的观点，用数学方法分析各特征向量之间的距离及分散情况；,如果特征向量集聚集若干个群，可按群间距离远近把它们划分成类；,这种按各类之间的亲疏程度的划分，若事先能知道应划分成几类，则可获得更好的分类结果。,21,模式分类的主要方法,统计模式识别,概率分类法,聚类分析,模糊模式识别,句法（结构）模式识别,人工神经网络方法,22,统计模式识别,基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。,特征向量分布的获得是基于一个类别已知的训练样本集。,是一种监督分类的方法，分类器是概念驱动的。,概率分类法,23,聚类分析,目标：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。,是一种非监督学习的方法，解决方案是数据驱动的。,24,模糊模式识别,基于模糊数学理论，利用隶属函数描述事物的 不确定性。,识别根据研究对象对于某模糊子集的隶属程度采用最大隶属原则识别法、择近原则识别法，模糊聚类分析法对模式进行识别。,25,结构模式识别,该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。,识别采用结构匹配的形式，通过计算一个匹配程度值（,matching score）,来评估一个未知的对象或未知对象某些部分与某种典型模式的关系如何。,当成功地制定出了一组可以描述对象部分之间关系的规则后，可以应用一种特殊的结构模式识别方法 句法模式识别，来检查一个模式基元的序列是否遵守某种规则，即句法规则或语法。,26,人工神经网络方法,神经网络是受人脑组织的生理学启发而创立的。,由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。,增强或抑制是通过调整神经元相互间联系的权重系数来实现。,神经网络可以实现监督和非监督学习条件下的分类。,27,模式识别系统的基本构成,数据获取,特征提取和选择,预处理,分类决策,分类器设计,28,数据获取：用计算机可以运算的符号来表示所研究的对象,二维图像：文字、指纹、地图、照片等,一维波形：脑电图、心电图、季节震动波形等,物理参量和逻辑值：体温、化验数据、参量正常与否的描述,预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原（图像处理）,29,特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征,测量空间：原始数据组成的空间,特征空间：分类识别赖以进行的空间,模式表示：维数较高的测量空间-维数较低的特征空间,分类器设计：分类器设计的主要功能是通过训练确定判决规则，使按此类判决规则分类时，错误率最低。把这些判决规则建成标准库。,分类决策：在特征空间中对被识别对象进行分类。,30,模式识别过程实例,在传送带上用光学传感器件对鱼按品种分类,鲈鱼(,Seabass,),品种,鲑鱼(,Salmon),31,识别过程,数据获取：架设一个摄像机，采集一些样本图像，获取样本数据,预处理：去噪声，用一个分割操作把鱼和鱼之间以及鱼和背景之间分开,32,识别过程,特征提取和选择：对单个鱼的信息进行特征选择，从而通过测量某些特征来减少信息量,长度,亮度,宽度,鱼翅的数量和形状,嘴的位置，等等 ,分类决策：把特征送入决策分类器,33,34,35,36,37,38,39,模式分类器的评测过程,数据采集,特征选取,模型选择,训练和测试,计算结果和复杂度分析，反馈,40,分类器评测,开始,数据采集,结束,训练和测试,计算结果和复杂度分析，反馈,特征选取,模型选择,41,训练和测试,训练集：是一个已知样本集，在监督学习方法中，用它来开发出模式分类器。,测试集：在设计识别和分类系统时没有用过的独立样本集。,系统评价原则：为了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。,42,实例：统计模式识别,19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：,43,实例：统计模式识别（续）,待识别的模式：性别（男或女）,测量的特征：身高和体重,训练样本：15名已知性别的样本特征,目标：希望借助于训练样本的特征建立判别函数（即数学模型）,44,实例：统计模式识别（续）,由训练样本得到的特征空间分布图,45,实例：统计模式识别（续）,从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。,只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。,结论：,1.错误最小。,2.存在错分。,46,实例：句法模式识别,问题：如何利用对图像的结构信息描述，识别如下所示图片：,地板,M,墙壁,N,L,T,B,D,E,X,Z,Y,47,实例：句法模式识别（续）,将整个场景图像结构分解成一些比较简单的子图像的组合；,子图像又用一些更为简单的基本图像单元来表示，直至子图像达到了我们认为的最简单的图像单元（基元）；,所有这些基元按一定的结构关系来表示，利用多级树结构对其进行描述（这种描述可以采用形式语言理论）。,48,实例：句法模式识别（续）,多级树描述结构,地板,M,墙壁,N,L,T,B,D,E,X,Z,Y,景物:,A,景物,A,物体,B,背景,C,三角体,D,长方体,E,三角形,T,面L,面Y,地板,M,墙壁,N,面Z,面X,49,实例：句法模式识别（续）,训练过程：,用已知结构信息的图像作为训练样本，先识别出基元（比如场景图中的,X、Y、Z,等简单平面）和它们之间的连接关系（例如长方体,E,是由,X、Y,和,Z,三个面拼接而成），并用字母符号代表之；,然后用构造句子的文法来描述生成这幅场景的过程，由此推断出生成该场景的一种文法。,50,实例：句法模式识别（续）,识别过程：,先对未知结构信息的图像进行基元提取及其相互结构关系的识别；,然后用训练过程获得的文法做句法分析；,如果能被已知结构信息的文法分析出来，则该幅未知图像与训练样本具有相同的结构（识别成功），否则就不是这种结构（识别失败）。,51,1-3 模式识别的应用,1 .字符识别：包括印刷体字符的识别,、,手写体字符的识别（脱机）,、,各种,OCR,设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入,、,在线手写字符的识别（联机），各种书写输入板。,2. 医疗诊断：心电图分析，脑电图分析，医学图像分析，染色体，癌细胞识别，疾病诊断。,3. 遥感：数字摄影测量，资源卫星照片，气象卫星照片处理。,52,4. 安全：指纹识别、人脸识别、监视和报警系统,5.工程：产品缺陷检测、特征识别、语音识别、机器翻译、电话号码自动查询、自动导航系统、污染分析、大气、水源、环境监测。,6.经济学：股票交易预测、企业行为分析。,7 .天文学：天文望远镜图像分析、自动光谱学。,8.生物学：自动细胞学、染色体特性研究、遗传研究。,9. 军事应用： 航空摄像分析、雷达和声纳信号检测和分类、自动目标识别。,53,1-4 模式识别的基本问题,一.模式(样本)表示方法,向量表示,:,假设一个样本有,n,个变量(特征),= (,x,1,x,2,xn,),T,2.,矩阵表示:,N,个样本，,n,个变量(特征),54,3. 几何表示,一维表示,X,1,=1.5 X,2,=3,二维表示,X,1,=(x,1,x,2,),T,=(1,2),T,X,2,=(x,1,x,2,),T,=(2,1),T,三维表示,X,1,=(x,1,x,2, x,3,),T,=(1,1,0),T,X,2,=(x,1,x,2, x,3,),T,=(1,0,1),T,55,4. 基元（链码）表示,：,在右侧的图中八个基元,分别表示0，1，2，3，,4，5，6，7，八个方向,和基元线段长度。,则右侧样本可以表示为,X,1,=006666,这种方法将在句法模式识别中用到。,56,二.模式类的紧致性,1. 紧致集,：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。,57,2. 临界点(样本)：,在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。,3. 紧致集的性质, 要求临界点很少, 集合内的任意两点的连线,在线上的点属于同 一集合, 集合内的每一个点都有足够大的邻域,在邻域内只包含同一集合的点,4. 模式识别的要求：,满足紧致集，才能很好的分类；如果不满足紧致集，就要采取变换的方法,满足紧致集.,58,三.相似与分类,1. 两个样本,x,i,，,x,j,之间的相似度量满足以下要求：, 应为非负值, 样本本身相似性度量应最大, 度量应满足对称性, 在满足紧致性的条件下，相似性应该,是点间距离的单调函数,59,2. 用各种距离表示相似性：, 绝对值距离,(,“,city block,”,distance ),已知两个样本,x,i,=(x,i1, x,i2, x,i3,x,in,),T,x,j,=(x,j1, x,j2, x,j3,x,jn,),T,又称城市距离，街坊距离。,60, 欧几里德距离（欧氏距离）,明考夫斯基距离（明氏距离）,其中当,m=1,时为绝对值距离，当,m=2,时为欧氏距离,61, 切比雪夫距离,m,趋向无穷大时明氏距离的极限情况, 马哈拉诺比斯距离,其中,m,为特征向量，,C,为协方差矩阵，使用的条件是样本符合正态分布。,62,因为,x,1 ,x,2,的夹角小,，,所以,x,1 ,x,2,最相似。,向量夹角余弦,它反映了几何相似性，在模式向量具有扇形分布时常采用这种测度。,63,3. 分类的主观性和客观性, 分类带有主观性：目的不同，分类不同。例如：鲸鱼，牛，马从生物学的角度来讲都属于哺乳类，但是从产业角度来讲鲸鱼属于水产业，牛和马属于畜牧业。, 分类的客观性：科学性,判断分类必须有客观标准，因此分类是追求客观性的，,但主观性也很难避免，这就是分类的复杂性。,当模式特征向量各分量取,0,、,1,二值时，常采用此式。,Tanimoto,测度,64,四.特征的生成,1.低层特征：,无序尺度：有明确的数量和数值。,有序尺度：有先后、好坏的次序关系，如酒,分为上，中，下三个等级。,名义尺度：无数量、无次序关系，如有红，,黄两种颜色,2. 中层特征：经过计算，变换得到的特征,3. 高层特征：在中层特征的基础上有目的的经过运,算形成,例如：椅子的重量=体积*比重,体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。,65,五.数据的标准化,1.极差标准化，一批样本中，每个特征的最大值与最小值之差。,极差,极差标准化,2. 方差标准化,S,i,为方差,标准化的方法很多，原始数据是否应该标准化，应采用,什么方法标准化，都要根据具体情况来定。,66,