模板匹配与模式识别.pptx

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

1、1 基本概念：模式 模式识别模式：存在于时间和空间中可观察的物体相同或相似性；它指的不是事物本身，而是从事物获得的信息，因此表现为具有时间和空间分布的信息。模式的直观特性:可观察性 可区分性 相似性第1页/共62页模式识别的研究目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。如下所表示：Y=F(X X)X的定义域取自特征集Y的值域为类别的标号集F是模式识别的判别方法第2页/共62页模式识别简史1929年G.Tauschek发明阅读机,能够阅读0-9的数字。30年代Fisher提出统计分类理论,奠定了统计模式识别的基础。50年代傅京荪提出句法结构模式

2、识别。60年代提出了模糊集理论，模糊模式识别方法得以发展和应用。80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。第3页/共62页模式识别系统的目标：在特征空间和解释空间之间找到一种映射关系，这种映射也称之为假说。特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。解释空间：模式识别的依据是相似性 可以识别从未见过的事物；可以识别变形的事物；根据事物的特征来识别它识别时抓住分类的主要特征，而忽略其他细节差异（只考虑相似不考虑相同）第4页/共62页模式识别的基本过程：学习、

3、分类（1）学习过程 读取样本特征 建立分类规则 进行分类检验（2）分类过程 读取事物信息 选取特征 按规则分类 对分类结果进行评估第5页/共62页2 模板匹配模板匹配：当对象图案以图象的形式表现时，根据该图案与一幅图象的各个部分相似度判断其是否存在，并求得对象物在图象中位置操作。ab第6页/共62页模板匹配过程：建立模板：对每个类别建立一个或多个模版，模板比较：输入样本和数据库中每个类别的模版进行比较，判断是否有相似的对象模板匹配的用途：几何变换中检测图象和地图之间对应点；不同光谱或者不同摄影时间所得的图象之间的位置配准；运动物体的跟踪；图象中对象物位置的检测第7页/共62页模板匹配方法图象f

4、(x,y)模板t(x,y)设检测模板为 ，令其中心与图象 中一象素重合，检测 和图象重合部分的相似度，对图象所有的象素都进行这样的操作，根据相似度为最大或者超过某一个阈值来确定对象物是否存在。第8页/共62页非相似度计算的是模板与图象重合部分的非相似度，该值越小，则匹配程度越好。采用形式：非相似度、相似度第9页/共62页相似度：计算的是模板与图象重合部分的相似度，该值越大，表示匹配程度越好第10页/共62页模板匹配算法的改进高速模板匹配算法 在模板匹配中应用的模板大，因此导致计算量比较大于是Barnea等人提出了序贯相似性检测算法-SSDA法 计算图象f(x,y)在像素(u,v)的非相似度m(

5、u,v)作为匹配的尺度。式中的(u,v)表示的不是模板与图像重合部分的中心坐标，而是重合部分的左上角坐标，模板大小为m*n 第11页/共62页 如果图像和模板在(u,v)处有和模板一致的图案时，则m(u,v)的值很小，相反则较大。特别是模板和图像重叠部分完全不一致的情况下，和就不断的增大。当差的绝对值部分和超过某一个阈值的时就认为在该位置不存在于模板一致的图案，从而转移到下一个位置。还有一种方法：粗检索和细检索两个阶段。模板一次移动若干个像素，计算匹配尺度，先求出大致的范围。然后在大致范围内，在每次移动一个像素，求出匹配尺度，确定对象所在位置。第12页/共62页模板的要求：检测对象大小和方向未

6、知的情况下进行模板匹配，需要具备各式各样大小和方向的模板，从而确定对象及其未知。对象形状复杂时，需要把对象分割成几个分图案，把分图案作为模板进行匹配，然后研究分图案之间的位置关系，从而获得图像中对象的位置。模版匹配：优点：直接、简单（早期非智能化方法）缺点：适应性差（可采用形变模版）第13页/共62页3 统计模式识别统计模式识别是研究每一个模式的各种测量统计数据特性，按照统计决策理论进行分类。三部分组成：分类；特征处理：由已知类别的训练样本求出判别函数以及判别规则，进而用来对未知类别的图像进行分类。自适应学习部分：用训练样本根据某些规则求出一些判别规则之后，再对这些训练样本逐个进行检测，观察是

7、否有误差第14页/共62页特征处理：特征提取和特征选择首先对识别对象的性质进行测量；利用测量值作为分类的特征。特征选择：选择有区分性，可靠性，独立性好的特征第15页/共62页特征选择的方法：穷举法：从m个测量值里面选取n个特征，然后对每一种选法利用已经知道类别属性的样本进行试分类，获得其正确率，分类误差最小的一组特征便是最好的选择。最大最小类对距离法：基本思想：从K个类别中选取最难分离的一对类别，然后选择不同的特征子集，计算这一类别的可分性，具有最大可分性的特征子集就是该方法所选择的最佳特征子集。这种方法不改变原始观测值的物理意义。第16页/共62页特征变换就是将m个测量值的集合通过某种变换，

8、产生n个特征用于分类。分两种情况：从减少原始特征之间相关性和浓缩性信息量的角度出发。另一种方法就是根据观测量所反映的物理现象与待分类别之间的关系的认识，通过数学运算产生一组新的特征值，使得待分类之间的差异在改组特征值里面更加明显。第17页/共62页统计分类法监督分类 就是根据预先已知类别名的训练样本，求出各类在特征空间的分布，然后利用它对未知数据进行分类。g1 g2 gc判别函数第18页/共62页第19页/共62页常用的判别函数距离判别函数线性判别函数 该方法一般将m类问题分解成m-1个两类识别的问题。先把特征空间分为一类和其它类。线性判别函数的系数通过样本试验确定。统计决策理论第20页/共6

9、2页最大似然法 该方法为理论上为误差最小的分类法第21页/共62页如在一维数特征空间场合，如下图T把特征空间分成两个区域，产生的误分类概率为：这一误分类概率随T的位置而发生变化，在位置上确定T时，PE最小，特征矢量分布函数第22页/共62页使用最大似然法，需要预先求出第23页/共62页第24页/共62页非监督分类 无法获得先验知识的情况下根据模式之间的相似度进行分类。将相似性强的模式归为同一类别，该方法又称为聚类分析其中k均值聚类就是一种非监督分类的方法。第25页/共62页例：统计模式识别19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4

10、人是男是女？体检数值如下：第26页/共62页实例：统计模式识别n待识别的模式：性别（男或女）n测量的特征：身高和体重n训练样本：15名已知性别的样本特征n目标：希望借助于训练样本的特征建立判别函数（即数学模型）第27页/共62页实例：统计模式识别50100150200607080体重 kg身高cm第28页/共62页实例：统计模式识别 从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。根据训练样本，建立决策边界；统计决策理论，根据每一类总体的概率分布决定决策

11、边界优点：理论基础扎实，算法适用面广；缺点：算法复杂、对于统计分类不明确的问题难求解第29页/共62页句子的层状结构第30页/共62页自然句法规则用语模式识别：房子和树第31页/共62页 结构模式识别以形式语言为基础，将一个复杂的模式分解成一系列子模式，对子模式继续分解，最后分解成最简单的子模式（基元），然后借助于一种形式语言对模式的结构进行描述，从而识别对象。模式，子模式，基元类似于短语，单词，字母。因此该方法类似于语言句法结构分析，因此称句法模式识别。第32页/共62页结构模式识别系统框图第33页/共62页树分类法 树分类法：根据树型分层理论，将未知数据归属于某一类的分类方法，是一种基于二

12、叉树的分类方法。第34页/共62页优点：能够利用少量特征，使不同特征在不同判定中起不同作用；每次判定比较简单缺点：容易从树根就产生错误，并且不能够平等的使用所有的特征注意：在靠近树根部必须选择稳定的，抗噪强的特征第35页/共62页实例：句法模式识别问题：如何利用对图像的结构信息描述，识别如下所示图片：第36页/共62页实例：句法模式识别（续）将整个场景图像结构分解成一些比较简单的子图像的组合；子图像又用一些更为简单的基本图像单元来表示，直至子图像达到了我们认为的最简单的图像单元（基元）；所有这些基元按一定的结构关系来表示，利用多级树结构对其进行描述(这种描述可以采用形式语言理论).第37页/共

13、62页实例：句法模式识别（续）多级树描述结构第38页/共62页实例：句法模式识别（续）训练过程：用已知结构信息的图像作为训练样本，先识别出基元（比如场景图中的X、Y、Z等简单平面）和它们之间的连接关系（例如长方体E是由X、Y和Z三个面拼接而成），并用字母符号代表之；然后用构造句子的文法来描述生成这幅场景的过程，由此推断出生成该场景的一种文法。第39页/共62页实例：句法模式识别（续）识别过程：先对未知结构信息的图像进行基元提取及其相互结构关系的识别；然后用训练过程获得的文法做句法分析；如果能被已知结构信息的文法分析出来，则该幅未知图像与训练样本具有相同的结构（识别成功）,否则就不是这种结构（识

14、别失败）。第40页/共62页5 人工神经网络识别法 人工神经网络是集脑科学、神经心理学和信息科学等多学科的交叉研究领域，是近年来高科技领域的一个研究热点。它的研究目标是通过研究人脑的组成机理和思维方式，探索人类智能的奥秘，进而通过模拟人脑的结构和工作模式，使机器具有类似人类的智能。它已在模式识别、机器学习、专家系统等多个方面得到应用，成为人工智能研究中的活跃领域。第41页/共62页生物神经元结构1.1.生物神经元的结构 神经细胞是构成神经系统的基本单元，称之为生物神经元，简称神经元。神经元主要由三部分构成：（1）细胞体;（2）轴突;（3）树突;第42页/共62页 突触是神经元之间相互连接的接口

15、部分，即一个神经元的神经末梢与另一个神经元的树突相接触的交界面，位于神经元的神经末梢尾端。突触是轴突的终端。2.2.神经元的功能特性 时空整合功能。神经元的动态极化性。兴奋与抑制状态。结构的可塑性。脉冲与电位信号的转换。突触延期和不应期。学习、遗忘和疲劳。第43页/共62页人工神经网络研究的兴起与发展人工神经网络的研究大体上可分为四个阶段:产生时期(20世纪50年代中期之前)高潮时期(20世纪50年代中期到20世纪60年代末期)低潮时期(20世纪60年代末到20世纪80年代初期)蓬勃发展时期(20世纪80年代以后)第44页/共62页 3 3 人工神经网络的组成 人工神经网络（简称ANN）是由大

16、量处理单元经广泛互连而组成的人工网络，用来模拟脑神经系统的结构和功能。而这些处理单元我们把它称作人工神经元。人工神经网络（ANN）可看成是以人工神经元为节点，用有向加权弧连接起来的有向图。在此有向图中，人工神经元就是对生物神经元的模拟，而有向弧则是轴突-突触-树突对的模拟。有向弧的权值表示相互连接的两个人工神经元间相互作用的强弱。第45页/共62页MP神经元模型人工神经网络的组成第46页/共62页 4 人工神经元的工作过程 对于某个处理单元（神经元）来说，假设来自其他处理单元（神经元）i的信息为xi，它们与本处理单元的互相作用强度即连接权值为wi,i=0,1,n-1,处理单元的内部阈值为。那么

17、本处理单元（神经元）的输入为第47页/共62页处理单元的输出为 式中，xi为第i个元素的输入，wi为第i个处理单元与本处理单元的互联权重。f称为激发函数或作用函数，它决定节点（神经元）的输出。第48页/共62页 激发函数一般具有非线性特性,常用的非线性激发函数如图所示这里 称为激活值(a)阈值型 (b)分段线性型 (c)Sigmoid函数型 (d)双曲正切型 图 常用的激发函数第49页/共62页 阈值型函数又称阶跃函数，它表示激活值和其输出f()之间的关系。阈值型函数为激发函数的神经元是一种最简单的人工神经元，也是M-P模型。线性分段函数可以看作是一种最简单的非线性函数，它的特点是将函数的值域

18、限制在一定的范围内，其输入、输出之间在一定范围内满足线性关系，一直延续到输出为最大域值为止。但当达到最大值后，输出就不再增大。S型函数是一个有最大输出值的非线性函数，其输出值是在某个范围内连续取值的。双曲正切型函数实际只是一种特殊的S型函数，其饱和值是-1和1。第50页/共62页 5 5 人工神经网络的结构 人工神经网络中，各神经元的不同连接方式就构成了网络的不同连接模型。常见的连接模型有:前向网络。从输入层到输出层有反馈的网络。层内有互联的网络。互联网络。第51页/共62页6 人工神经网络的分类及其主要特征 按性能分：连续型和离散型网络，或确定型和随机型网络。按拓扑结构分：有反馈网络和无反馈

19、网络。按学习方法分：有教师的学习网络和无教师的学习网络。按连接突触性质分：一阶线性关联网络和高阶非线性关联网络第52页/共62页人工神经网络主要特征优点在于：能较好的模拟人的形象思维。具有大规模并行协同处理能力。具有较强的学习能力。具有较强的容错能力和联想能力。是一个大规模自组织、自适应的非线性动力系统。弱点在于：需要更多的训练数据；在计算机上实现模拟运行比较慢无法透彻理解所使用的过程。第53页/共62页7 BP神经网络1 1 反向传播模型及其网络结构B-P模型也称反向传播模型，是一种用于前向多层的反向传播学习算法。它可以对组成前向多层网络的各人工神经元之间的连接权值进行不断的修改，从而使该前

20、向多层网络能够将输入它的信息变换成所期望的输出信息;在修改各人工神经元的连接权值时，所依据的是该网络的实际输出与其期望的输出之差，将这一差值反向一层一层的向回传播，来决定连接权值的修改。第54页/共62页B-P算法的网络结构是一个前向多层网络，如图所示:第55页/共62页反向传播网络的学习算法B-P算法的学习目的是对网络的连接权值进行调整，使得调整后的网络对任一输入都能得到所期望的输出。学习过程由正向传播和反向传播组成。正向传播用于对前向网络进行计算，即对某一输入信息，经过网络计算后求出它的输出结果。反向传播用于逐层传递误差，修改神经元间的连接权值，以使网络对输入信息经过计算后所得到的输出能达

21、到期望的误差要求。第56页/共62页B-P算法的学习过程如下：选择一组训练样例，每一个样例由输入信息和期望的输出结果两部分组成。从训练样例集中取一样例，把输入信息输入到网络中。分别计算经神经元处理后的各层节点的输出。计算网络的实际输出和期望输出的误差。从输出层反向计算到第一个隐层，并按照某种能使误差向减小方向发展的原则，调整网络中各神经元的连接权值。对训练样例集中的每一个样例重复（3）-（5）的步骤，直到对整个训练样例集的误差达到要求时为止。第57页/共62页B-P算法的优缺点：优点：理论基础牢固，推导过程严谨，物理概念清晰，通用性好等。所以，它是目前用来训练前向多层网络较好的算法。缺点：该学

22、习算法的收敛速度慢；网络中隐节点个数的选取尚无理论上的指导；从数学角度看，B-P算法是一种梯度最速下降法，这就可能出现局部极小的问题。当出现局部极小时，从表面上看，误差符合要求，但这时所得到的解并不一定是问题的真正解。所以B-P算法是不完备的。第58页/共62页第59页/共62页这三个点正处在两个区间的中间，数学方程式无法判断。为此用人工神经网络判断。输入信号为x,y.但要求取值都在0,1之间。由于x,y均在1.1-2.1，所有数都减去1.1，归一化就完成。处理的基本思路是：自15个已知样品中找出规律，将此规律用于处理三个未确认的样本。解决实际问题时要根据具体情况确定隐含层的层数和输入层、隐含层、输出层各自的结点数，以使构成的网络达到最优效果。本例中，隐含层取1，输入结点数为2，分别代表触角与翼长；中间隐含层的结点数取3个就够了。输出的结点数取2，设Af样品的输出是（1，0）；Apf的输出是（0，1）时为理想输出。由15个已知样品进行训练，选出合适的权值。对于任一未知样品，输出元后，和靠近（1，0）还是靠近（0，1）对比，就可以判断其归属了。第60页/共62页输入信号为x-1.1,y-1.1Af样品的输出是(1,0)；Apf的输出是(0,1)学习,检验,预测 第61页/共62页感谢您的观看。第62页/共62页