数字图像处理学：第10章 模式识别的理论与方法（第10-1讲）.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理学,第,10,章 模式识别的理论和方法,（第一讲）,10.,1,概述,模式识别是随着计算机的发展而兴起的一门新的技术科学。自,50,年代末期开始来，至今已得到了迅速的发展和广泛的应用。模式识别对我们每个人来说，每时每刻都在进行着，用计算机进行模式识别就是研究让计算机处理哪些信息和怎样处理这些信息。因此，它是信息处理中的又一个研究领域。,例如，,根据气象观测数据或气象卫星拍照的照片如何准确地预报天气；,根据石油勘探的人工地震波如何提供存油的岩层结构；,从遥感图片中如何区别出农作物、湖泊、森林、导弹基地等；,在高能物理实验中怎样识别粒子经迹；,在医疗诊断中如何从,X,光片中发现病灶；,如何根据信函上的邮政编码自动分拣信件；,在繁华的交通中心根据车辆的流量如何决定开放红灯或绿灯,等诸如此类的问题都是模式识别研究的课题。,这些课题看上去名目繁多，但总起来看主要是研究分类问题。,模式识别研究的对象基本上可概括为二类：,一是有直觉形象的如图片、相片、图案、文字等等,;,一种是无直觉形象而只有数据或信号波形如言、声音、心电脉冲、地震波等等。,但对模式识别来说，无论是数据、信号还是平面图形和物体，都是除掉它们的物理内容找出它们的共性，把具有同一共性的归为一类，有另一种共性者则归为另一类。,例如：,10,个阿拉伯数字分为,10,类；,26,个英文字母分成,26,类；白血球有,5,种就分为,5,类；肺部,X,光片可分为异常和正常,2,类等等。,模式识别研究的目的是构造自动处理某些信息的机器系统，以代替人完成分类和辨识的任务。特别是有直觉形象的一类图像识别问题同人或其它动物的感知活动尤其同人脑的智力活动联系密切。因此，根据人的大脑识别的机理，在工程上用计算机模拟，从而研究识别方法是有现实意义的。,尽管这种模拟同人的意识和思维活动有本质的差别，但若从人类识别图像的过程及认识规律中得到启发，在某些环节上得到借鉴，从而采用现代技术解决实际问题这是十分有益的。,在具有视觉形象的图像识别中，许多方法和概念就是从人类认识图像的过程中直接移植过来的。人类在现实生活中要区别各种现象、物体及声音，一般总是首先抓住它们的特征进行比较、分析、判断，从而将它们分类或识别。特别是数理统计和模糊数学的发展，总结了人们的认识逻辑，从而也使图像识别有了理论基础。,一个图像识别系统可分为三个主要部分。,图,101,图像识别系统框图,被识图像,图像获取,信息处理,特征抽取,判决,结果,(1),图像信息的获取；,(2),信息的加工和处理，抽取特征；,(3),判断或分类。,第一部分,相当于对被研究对象的调查和了解，从中得到数据和材料；对图像识别来说，就是把图片，底片，文字图形等用光电扫描设备变换为电信号，而对语音来说就可用话筒等设备把声音变成电信号以备后序处理。,第二部分,相当于人们把调查了解到的数据材料进行加工、整理、分析、归纳，以去伪存真，去粗取精，抽出能反映事物本质的东西。当然，抽取什么特征，保留多少特征与采用何种判决有很大关系。,第三部分,是判决和分类，这相当与人们从感性认识上升到理性认识而做出结论的过程。,第三部分与抽取特征的方式密切相关。它的复杂程度依赖于特征的抽取方式，例如：类似度、相关性、最小距离等。,模式识别的主要方法可分为两大类,：,统计学方法,语言学方法。,统计学方法是建立在被研究对象的统计知识上，也就是对图像进行大量的统计分析，抽出图像中本质的特征而进行识别。,这统计学方法是一种数学方法，它是受数学中的决策理论的启发而产生的识别方法。在这种方法中很大的力量用在抽取图像特征方面，也就是把图像大量的原始信息减缩为少数特征，然后再提取这些特征，把它作为识别的依据。,语言学法或句法结构识别法是立足于分析图像结构。把一个图像看成语言构造。例如一个英文句子，它是词和短语组成的并按一定的语法表达出来，其中最基本元素是单词。与此类似，图像是由一些直线、斜线、点、弯曲线及环等组成。,剖析这些基本原素，看它们是以什么规则构成图像，这就是结构分析的课题。这些基本元素相当于句子中的单词，那些直线，曲线的组合相当于短语，它们全体如何构成图像就相当于语法规则。,此时，图像识别就相当于检查图像所代表的某一类句型是否符合事先规定的语法，如果语法正确就识别出结果。由此可见，这种方法主要是利用了图像结构上的关系，这和统计学方法不同。,两类方法的不足,：,第一种方法没有利用图像本身的结构关系，,第二类方法没有考虑图像在环境中受噪声的干扰。,如果两者结合起来考虑可能会有新的识别方法，目前这方面的研究还不多。除此之之外，其于模糊数学的发展，目前正在发展一种模糊识别法。这种方法较多地考虑了人的逻辑思维方法，方法较为独特，这种方法的研究得到了人们的关注。,模糊识别的应用较广，大致可有如下几个方面：,(1),字符识别,(Character recognition),；,(2),医学诊断,(Medical diagnosis),；,(3),遥感,(Remote Sensing),；,(4),人脸和指纹鉴别,(Identification of human faces,and fingerprints),；,(5),污染,(Pollution),；,(6),自动检查和自动化,(Automatic inspection,and Automation),；,(7),可靠性,(Reliability),；,(8),社会经济,(Socio-economics),；,(9),语音识别和理解,(Speech understanding and,recognition),；,(10),考古,(Archaeology),。,目前世界上已有一些较为完善的图像识别系统。这些系统无论从识别分析的功能来讲还是从处理速度上来说都较初期有很大的发展。例如，美国的,OLPARS(,联机图像分析识别系统,),能识别数字、字母及分析识别航空照片。,英国新产品,QUANTIMET 720,高速多功能图像分析系统可以观察由光学和显微镜获得的图像、照片、底片、电影、幻灯片及,X,光照片。能对图像进行各种测量及单独实时测量特征，数据由微计算机处理。日本的,OCR-ASPET/71,型识别系统能识别多种字体，每秒钟可识别,2000,字。,英国的,IBM 1287,光学文字阅读机能识别,10,个阿拉伯数字，在邮局推广应用，误识率为,0.4,，拒识率为,1.4,。日本,NEC,公司研制的邮区编码信函分拣机能识别印刷体数字、字母、速度达,30000,件,/,小时。,在医学中也有较多应用，如一种,5,类白血球分类器可做到,95,的正确分类，每分钟,100,个细胞。另外还有染色体自动分类，医学管理等方面也多有应用。,随着计算机技术的发展，模式识别的理论和方法得到进一步发展特别是图像识别这个领域近年来兴旺活跃，发展蓬勃。在某种意义上来说，图像识别已发展成为人同机器，自然科学和社会科学基础理论同技术应用之间的接口领域。,目前，不仅研究单一功能的识别系统，而且在研制多功能的综合识别系统。如北方交通大学信息科学研究所会同清华大学、上海交通大学研究的“超级智能视听信息处理系统”就是一种多信息融合的处理系统，它的目的是利用多信息的融合技术，在模式识别中互相补充、互相借鉴，从而克服过去单一识别所面临的难以克服的困难，试图在模式识别领域有较大的突破。,同时，该系统在当今颇为热门的人,机通过自然手段进行交互的领域也进行了有益的尝试。近年来国际上在这一领域给予了极大的重视，微软、,Intel,、,IBM,等大公司纷纷提出研究计划，所谓的“,Multimodel,”,研究已形成了新的研究热点。,与此同时，对有关图像识别的图像处理软件及新算法也受到极大的重视，如人工神经元网络、遗传算法等在模式识别研究中已取得了可喜的结果。现在，研制高性能、多用途的图像分析识别系统乃是有待我们努力解决的课题，随着生产与科学技术的发展，这一技术必将在我国的现代化建设中发挥作用。,10.2,统计模式识别法,统计模式识别的过程如下图所示。,这是计算机识别的基本过程。,数字化的任务是把图像信号变成计算机能够接受的数字信号。预处理的目的是去除干扰、噪声及差异，将原始信号变成适合于进行特征抽取的形式，,然后，对经过预处理的信号进行特征抽取。,最后进行判决分类，得到识别结果。,为了进行分类，必须有图像样本。对样本图像进行特征选择及学习是识别处理中所必要的分析工作。,10.2.3,特征的抽取与选择,10.2.,1,决策理论方法,10.2.2,统计分类法,2,1,决策理论方法,统计模式识别方法最终归结为分类问题。假如已抽取出,N,个特征，而图像可分为,m,类，那么就可以对,N,进行分类，从而决定未知图像属于,m,类中的哪一类。一般把识别模式看成是对,N,维空间中的向量,X,进行分类，即：,(10,1),模式类别为 。识别就是要判断,X,是否属于 以及 属于 中的哪一类。在这个过程中主要解决两个问题：,一是如何抽取特征，要求特征数,N,尽可能小,而且对分类判断有效；,二是假设已有了代表模式的向量，如何决定,它属于哪一类，这就需要判别函数。,例如，模式有 共,m,个类别，则应有 ，共,m,个判别函数。如果,X,属于第,i,类，则有：,(10,2),在两类的分界线上，则有,(10,3),这时,X,既属于第,i,类，也属于第,j,类，因此这种判别失效。为了进行识别就必须重新考虑其他特征，再进行判别。问题的关键是找到合适的判别函数。,1,常用的决策规则,1,）、基于最小错误率的贝叶斯决策,在图像识别中，我们总希望尽量减少分类错误，利用贝叶斯（,Bayes,）公式能够得到错误率最小的分类规则，这就是基于最小错误率的贝叶斯决策。,为解决两类事务,X,的分类问题，设模式类别为,和 ，其中类别状态是一个随机变量，状态的概率是可以估计的。状态 的概率为 ，状态 的概率为 。显然，,设,:,为 状态下观察,X,类的条件概率密度；,为 状态下观察,X,类的条件概率密度；,利用贝叶斯公式：,得到的条件概率 称为状态的后验概率,。,贝叶斯公式实质上是通过观察,x,，把状态的先验概率 转化为状态的后验概率 。这样基于最小错误率的贝叶斯决策规则为,：,如果 ，则把,X,归类为 ；,如果 ，则把,X,归类为 。,上面的规则也可以写成下式形式：,则 。,2,）、基于最小风险的贝叶斯决策,最小风险的贝叶斯决策是考虑各种错误造成损失而提出的决策规则。,设：观察是,n,维随机向量，,（,10,6,）,状态空间 由,c,个自然状态组成，,决策空间由 个决策 组成。,损失函数为 。它表示当真实状态为 ，而所采取的决策为时所带来的损失。,已知条件概率 及类条件概率密度 ，这里 。,后验概率为,这里引入了“损失”的概念，就必须考虑所采取的决策是否能使损失最小。对于给定的,X,，如果采用决策 ，可以在 中任选一个，在这种情况下，条件期望损失为：,这里条件期望损失 也称为条件风险。,由于,X,是观察值，采取不同的决策 时，条件风险的大小不同，因此，采用的决策与,X,有关，,这样决策 可以看成是,X,的函数，即，,，,因此，可定义期望风险为：,这里 是采取 的平均风险，是对某一,X,的取值采取决策 所带来的风险。,因此，最小风险贝叶斯决策为：,则,2,线性判别函数,线性判别函数是应用较广的一种判别函数。所谓线性判别函数是指判别函数是图像所有特征量的线性组合，即,:,(10,4),式中 代表第,i,个判别函数；是系数或权；为常数项或称为阈值。在两类之间的判决界处有下式的形式。,(10,5),可以写成下式形式：,(10,6),该方程在二度空间中是直线，在三度空间中是平面，在,N,度空间中则是超平面。,其判决过程可如下进行：,如果 或,则 ；,如果 或,则 。,用线性判别函数进行分类的是线性分类器。任何,m,类问题都可以分解为,(,m,-1),个,2,类识别问题。方法是先把模式空间分为,1,类和其他类，如此进行下去即可。因此，最简单和最基本的是两类线性分类器。,分离两类的判决界由,D,1,D,2,=0,表示。对于任何特定的输入模式必须判定,D,1,大还是,D,2,大。若考虑某个函数,D,=,D,1,-,D,2,，对于类模式,D,为正，对于类模式,D,为负。于是，只要处理与,D,相应的一组权的输入模式并判断输出符号即可进行分类。,在线性分类器中要找到合适的系数，以便使分类尽可能不出差错，唯一的办法就是试验法。例如，先设所有的系数为,1,，送进每一个模式，如果分类有错就调整系数，这个过程就叫做线性分类器的训练或学习。例如，我们把,N,个特征,X,和,1,放在一起叫做,Y,，,N+1,个系数为,W,，即：,(10,7),考虑分别属于两个不同模式类，,m,=2,，此时，有两个训练集,T,1,和,T,2,。两个训练集合是线性可分的，这意味着存在一个加权向量,W,，使得,(10,8),式中,Y,T,是,Y,的转置。,如果分类器的输出不能满足式,(108),的条件,可以通过“误差校正”的训练步骤对系数加以调整。例如，如果第一类模式 不大于零，则说明系数不够大，可用加大系数的方法进行误差修正。,具体修正方法如下,:,对于任一个,若,则使,(10,9),对于任一个,若,则使,(10,10),通常使用的误差修正方法有固定增量规则，绝对修正规则及部分修正规则。固定增量规则是选择 为一个固定的非负数。绝对修正规则是取 为一个最小整数，它可使 的值刚好大于零，即,的最小整数,(10,11,),部分修正规则可取 为下式所决定的值,(10,12),3,Fisher,线性判别,Fisher,线性判别起源于,1936,年,R.A.Fisher,的研究工作。在统计模式识别方法中，遇到的主要问题之一就是维数问题。在低维中可行的方法在高维上往往行不通。因此，降低维数是识别的关键问题。,考虑把一个,d,维空间样本投影到一条直线上，形成一维空间，在数学上并非难事。但是，在原有的,d,维空间中紧凑可分的集群，当投影到一维时，有可能使几类样本混在一起而无法识别。因此，如何找到最好的，易于分类的投影线就是,Fisher,法要解决的基本问题。,设有一个集合 包含,N,个,d,维样本 ，其中 个属于 类的样本子集为 ，属于 的 个样本为 。对 的分量作线性组合有：,（,10,21,）,由此可得到 个一维样本 组成的集合。从几何上看，如果 ，则每个 就是相对应的 到方向为 直线上的投影。这里 方向的选择是很重要的，它将影响投影后的可分离程度，进而影响识别结果。,设,：,在,d,维,X,空间，各类样本的均值向量为,m,i,（,10,22,）,样本类内离散度矩阵为,S,i,，总类内离散度矩阵为,S,W,（,10,23,）,样本类间离散度,S,b,（,10,24,）,在一维,Y,空间,各类样本均值为,（,10,25,）,样本类内离散度矩阵为 ，总类内离散度矩阵为,（,10,26,）,我们希望投影后在一维,Y,空间,中各类样本都能分得开，也就是两类均值之差 越大越好，而且希望类内散度越小越好。因此，定义,Fisher,准则为：,（,10,27,）,显然，应选择 尽可能大的作为投影方向。,由于,（,10,28,）,（,10,29,）,所以,（,10,30,）,为了求取 使取极大值的 ，采用,Lagrange,乘数法求解，令分母为非零常数，即：,定义,Lagrange,函数为：,（,10,31,）,为,Lagrange,乘数。上式对 求导，则,令：,是 的极值解。左乘 ，得到：,由 的定义，,因此，,忽略比例因子，有：,（,10,32,）,就是使,Fisher,准则函数 取得极大值的解，也就是,d,维,X,空间到一维,Y,空间的最好投影方向。由此也就把,d,维分类问题转化为一维分类问题了。,