第10章 模板匹配与模式识别

第10章模板匹配和模式识别技术1基本概念：模式模式识别模式：存在于时间和空间中可观察的物体相同或相似性；它指的不是事物本身，而是从事物获得的信息，因此表现为具有时间和空间分布的信息。模式的直观特性:

可观察性可区分性相似性模式识别是人和动物的一种特性：周围物体的认知：桌子、椅子人的识别：张三、李四声音的辨别：汽车、火车，狗叫、人语气味的分辨：炸带鱼、红烧肉模式识别:又称作模式分类，就是确认一个事物是什么，或者不是什么，其本质是事物的分类。从处理问题的性质和解决问题的方法等角度，模式识别分为有监督的分类和非监督的分类两种。模式识别的研究目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。如下所表示：Y=F(X)X的定义域取自特征集Y的值域为类别的标号集F是模式识别的判别方法模式识别简史1929年G.Tauschek发明阅读机,能够阅读0-9的数字。30年代Fisher提出统计分类理论,奠定了统计模式识别的基础。50年代傅京荪提出句法结构模式识别。60年代L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用。80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。模式识别系统的目标：在特征空间和解释空间之间找到一种映射关系，这种映射也称之为假说。特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。解释空间：模式识别的依据是相似性可以识别从未见过的事物；可以识别变形的事物；根据事物的特征来识别它识别时抓住分类的主要特征，而忽略其他细节差异（只考虑相似不考虑相同）模式识别的基本过程：学习、分类（1）学习过程读取样本特征建立分类规则进行分类检验（2）分类过程读取事物信息选取特征按规则分类对分类结果进行评估模式识别的方法（1）模版匹配（2）统计方法（3）结构方法（句法方法）（4）模糊模式识别（5）神经网络2模板匹配模板匹配：当对象图案以图象的形式表现时，根据该图案与一幅图象的各个部分相似度判断其是否存在，并求得对象物在图象中位置操作。ab模板匹配过程：建立模板：对每个类别建立一个或多个模版，模板比较：输入样本和数据库中每个类别的模版进行比较，判断是否有相似的对象模板匹配的用途：几何变换中检测图象和地图之间对应点；不同光谱或者不同摄影时间所得的图象之间的位置配准；运动物体的跟踪；图象中对象物位置的检测模板匹配方法图象f(x,y)模板t(x,y)设检测模板为，令其中心与图象中一象素重合，检测和图象重合部分的相似度，对图象所有的象素都进行这样的操作，根据相似度为最大或者超过某一个阈值来确定对象物是否存在。非相似度计算的是模板与图象重合部分的非相似度，该值越小，则匹配程度越好。采用形式：非相似度、相似度相似度：计算的是模板与图象重合部分的相似度，该值越大，表示匹配程度越好模板匹配算法的改进高速模板匹配算法在模板匹配中应用的模板大，因此导致计算量比较大于是Barnea等人提出了序贯相似性检测算法-SSDA法计算图象f(x,y)在像素(u,v)的非相似度m(u,v)作为匹配的尺度。式中的(u,v)表示的不是模板与图像重合部分的中心坐标，而是重合部分的左上角坐标，模板大小为m*n

如果图像和模板在(u,v)处有和模板一致的图案时，则m(u,v)的值很小，相反则较大。特别是模板和图像重叠部分完全不一致的情况下，和就不断的增大。当差的绝对值部分和超过某一个阈值的时就认为在该位置不存在于模板一致的图案，从而转移到下一个位置。还有一种方法：粗检索和细检索两个阶段。模板一次移动若干个像素，计算匹配尺度，先求出大致的范围。然后在大致范围内，在每次移动一个像素，求出匹配尺度，确定对象所在位置。模板的要求：检测对象大小和方向未知的情况下进行模板匹配，需要具备各式各样大小和方向的模板，从而确定对象及其未知。对象形状复杂时，需要把对象分割成几个分图案，把分图案作为模板进行匹配，然后研究分图案之间的位置关系，从而获得图像中对象的位置。模版匹配：优点：直接、简单（早期非智能化方法）缺点：适应性差（可采用形变模版）3统计模式识别统计模式识别是研究每一个模式的各种测量统计数据特性，按照统计决策理论进行分类。三部分组成：分类；特征处理：由已知类别的训练样本求出判别函数以及判别规则，进而用来对未知类别的图像进行分类。自适应学习部分：用训练样本根据某些规则求出一些判别规则之后，再对这些训练样本逐个进行检测，观察是否有误差特征处理：特征提取和特征选择首先对识别对象的性质进行测量；利用测量值作为分类的特征。特征选择：选择有区分性，可靠性，独立性好的特征特征选择的方法：穷举法：从m个测量值里面选取n个特征，然后对每一种选法利用已经知道类别属性的样本进行试分类，获得其正确率，分类误差最小的一组特征便是最好的选择。最大最小类对距离法：基本思想：从K个类别中选取最难分离的一对类别，然后选择不同的特征子集，计算这一类别的可分性，具有最大可分性的特征子集就是该方法所选择的最佳特征子集。这种方法不改变原始观测值的物理意义。特征变换就是将m个测量值的集合通过某种变换，产生n个特征用于分类。分两种情况：从减少原始特征之间相关性和浓缩性信息量的角度出发。另一种方法就是根据观测量所反映的物理现象与待分类别之间的关系的认识，通过数学运算产生一组新的特征值，使得待分类之间的差异在改组特征值里面更加明显。统计分类法监督分类就是根据预先已知类别名的训练样本，求出各类在特征空间的分布，然后利用它对未知数据进行分类。g1g2gc判别函数常用的判别函数距离判别函数线性判别函数该方法一般将m类问题分解成m-1个两类识别的问题。先把特征空间分为一类和其它类。线性判别函数的系数通过样本试验确定。统计决策理论最大似然法该方法为理论上为误差最小的分类法如在一维数特征空间场合，如下图T把特征空间分成两个区域，产生的误分类概率为：这一误分类概率随T的位置而发生变化，在位置上确定T时，PE最小，特征矢量分布函数使用最大似然法，需要预先求出非监督分类无法获得先验知识的情况下根据模式之间的相似度进行分类。将相似性强的模式归为同一类别，该方法又称为聚类分析其中k均值聚类就是一种非监督分类的方法。例：统计模式识别19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：实例：统计模式识别待识别的模式：性别（男或女）测量的特征：身高和体重训练样本：15名已知性别的样本特征目标：希望借助于训练样本的特征建立判别函数（即数学模型）实例：统计模式识别50100150200607080体重kg身高cm实例：统计模式识别从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。只要给出待分类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。根据训练样本，建立决策边界；统计决策理论，根据每一类总体的概率分布决定决策边界优点：理论基础扎实，算法适用面广；缺点：算法复杂、对于统计分类不明确的问题难求解4结构模式识别法识别原理：句法：描述语言规则的一种法则。许多复杂的模式可以分解为简单的子模式，这些子模式组成所谓“基元”，每个模式都可以由基元根据一定的关系来组成，基元可以认为是语言中的字母，每个模式都可以认为是一个句子，关系可以认为是语法。模式的相似性由句子的相似性来决定。句子的层状结构自然句法规则用语模式识别：房子和树结构模式识别以形式语言为基础，将一个复杂的模式分解成一系列子模式，对子模式继续分解，最后分解成最简单的子模式（基元），然后借助于一种形式语言对模式的结构进行描述，从而识别对象。模式，子模式，基元类似于短语，单词，字母。因此该方法类似于语言句法结构分析，因此称句法模式识别。结构模式识别系统框图树分类法树分类法：根据树型分层理论，将未知数据归属于某一类的分类方法，是一种基于二叉树的分类方法。优点：能够利用少量特征，使不同特征在不同判定中起不同作用；每次判定比较简单缺点：容易从树根就产生错误，并且不能够平等的使用所有的特征注意：在靠近树根部必须选择稳定的，抗噪强的特征实例：句法模式识别问题：如何利用对图像的结构信息描述，识别如下所示图片：实例：句法模式识别（续）将整个场景图像结构分解成一些比较简单的子图像的组合；子图像又用一些更为简单的基本图像单元来表示，直至子图像达到了我们认为的最简单的图像单元（基元）；所有这些基元按一定的结构关系来表示，利用多级树结构对其进行描述(这种描述可以采用形式语言理论).实例：句法模式识别（续）多级树描述结构实例：句法模式识别（续）训练过程：用已知结构信息的图像作为训练样本，先识别出基元（比如场景图中的X、Y、Z等简单平面）和它们之间的连接关系（例如长方体E是由X、Y和Z三个面拼接而成），并用字母符号代表之；然后用构造句子的文法来描述生成这幅场景的过程，由此推断出生成该场景的一种文法。实例：句法模式识别（续）识别过程：先对未知结构信息的图像进行基元提取及其相互结构关系的识别；然后用训练过程获得的文法做句法分析；如果能被已知结构信息的文法分析