第10章-模板匹配与模式识别.ppt

第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 分类过程读取事物信息选取特征按规则分类对分类结果进行评估 2模板匹配 模板匹配 当对象图案以图象的形式表现时 根据该图案与一幅图象的各个部分相似度判断其是否存在 并求得对象物在图象中位置操作 模板匹配过程 建立模板 对每个类别建立一个或多个模版 模板比较 输入样本和数据库中每个类别的模版进行比较 判断是否有相似的对象模板匹配的用途 几何变换中检测图象和地图之间对应点 不同光谱或者不同摄影时间所得的图象之间的位置配准 运动物体的跟踪 图象中对象物位置的检测 模板匹配方法 设检测模板为 令其中心与图象中一象素重合 检测和图象重合部分的相似度 对图象所有的象素都进行这样的操作 根据相似度为最大或者超过某一个阈值来确定对象物是否存在 非相似度计算的是模板与图象重合部分的非相似度 该值越小 则匹配程度越好 采用形式 非相似度 相似度 相似度 计算的是模板与图象重合部分的相似度 该值越大 表示匹配程度越好 模板匹配算法的改进 高速模板匹配算法在模板匹配中应用的模板大 因此导致计算量比较大于是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名已知性别的样本特征目标 希望借助于训练样本的特征建立判别函数 即数学模型 实例 统计模式识别 50 100 150 200 60 70 80 体重kg 身高cm 实例 统计模式识别 从图中训练样本的分布情况 找出男 女两类特征各自的聚类特点 从而求取一个判别函数 直线或曲线 只要给出待分类的模式特征的数值 看它在特征平面上落在判别函数的哪一侧 就可以判别是男还是女了 根据训练样本 建立决策边界 统计决策理论 根据每一类总体的概率分布决定决策边界优点 理论基础扎实 算法适用面广 缺点 算法复杂 对于统计分类不明确的问题难求解 句子的层状结构 自然句法规则用语模式识别 房子和树 结构模式识别以形式语言为基础 将一个复杂的模式分解成一系列子模式 对子模式继续分解 最后分解成最简单的子模式 基元 然后借助于一种形式语言对模式的结构进行描述 从而识别对象 模式 子模式 基元类似于短语 单词 字母 因此该方法类似于语言句法结构分析 因此称句法模式识别 结构模式识别系统框图 树分类法 树分类法 根据树型分层理论 将未知数据归属于某一类的分类方法 是一种基于二叉树的分类方法 优点 能够利用少量特征 使不同特征在不同判定中起不同作用 每次判定比较简单缺点 容易从树根就产生错误 并且不能够平等的使用所有的特征注意 在靠近树根部必须选择稳定的 抗噪强的特征 实例 句法模式识别 问题 如何利用对图像的结构信息描述 识别如下所示图片 实例 句法模式识别 续 将整个场景图像结构分解成一些比较简单的子图像的组合 子图像又用一些更为简单的基本图像单元来表示 直至子图像达到了我们认为的最简单的图像单元 基元 所有这些基元按一定的结构关系来表示 利用多级树结构对其进行描述 这种描述可以采用形式语言理论 实例 句法模式识别 续 多级树描述结构 实例 句法模式识别 续 训练过程 用已知结构信息的图像作为训练样本 先识别出基元 比如场景图中的X Y Z等简单平面 和它们之间的连接关系 例如长方体E是由X Y和Z三个面拼接而成 并用字母符号代表之 然后用构造句子的文法来描述生成这幅场景的过程 由此推断出生成该场景的一种文法 实例 句法模式识别 续 识别过程 先对未知结构信息的图像进行基元提取及其相互结构关系的识别 然后用训练过程获得的文法做句法分析 如果能被已知结构信息的文法分析出来 则该幅未知图像与训练样本具有相同的结构 识别成功 否则就不是这种结构 识别失败 5人工神经网络识别法 人工神经网络是集脑科学 神经心理学和信息科学等多学科的交叉研究领域 是近年来高科技领域的一个研究热点 它的研究目标是通过研究人脑的组成机理和思维方式 探索人类智能的奥秘 进而通过模拟人脑的结构和工作模式 使机器具有类似人类的智能 它已在模式识别 机器学习 专家系统等多个方面得到应用 成为人工智能研究中的活跃领域 生物神经元结构 1 生物神经元的结构神经细胞是构成神经系统的基本单元 称之为生物神经元 简称神经元 神经元主要由三部分构成 1 细胞体 2 轴突 3 树突 突触是神经元之间相互连接的接口部分 即一个神经元的神经末梢与另一个神经元的树突相接触的交界面 位于神经元的神经末梢尾端 突触是轴突的终端 2 神经元的功能特性时空整合功能 神经元的动态极化性 兴奋与抑制状态 结构的可塑性 脉冲与电位信号的转换 突触延期和不应期 学习 遗忘和疲劳 人工神经网络研究的兴起与发展人工神经网络的研究大体上可分为四个阶段 产生时期 20世纪50年代中期之前 高潮时期 20世纪50年代中期到20世纪60年代末期 低潮时期 20世纪60年代末到20世纪80年代初期 蓬勃发展时期 20世纪80年代以后 3人工神经网络的组成人工神经网络 简称ANN 是由大量处理单元经广泛互连而组成的人工网络 用来模拟脑神经系统的结构和功能 而这些处理单元我们把它称作人工神经元 人工神经网络 ANN 可看成是以人工神经元为节点 用有向加权弧连接起来的有向图 在此有向图中 人工神经元就是对生物神经元的模拟 而有向弧则是轴突 突触 树突对的模拟 有向弧的权值表示相互连接的两个人工神经元间相互作用的强弱 M P神经元模型 人工神经网络的组成 4人工神经元的工作过程对于某个处理单元 神经元 来说 假设来自其他处理单元 神经元 i的信息为xi 它们与本处理单元的互相作用强度即连接权值为wi i 0 1 n 1 处理单元的内部阈值为 那么本处理单元 神经元 的输入为 处理单元的输出为 式中 xi为第i个元素的输入 wi为第i个处理单元与本处理单元的互联权重 f称为激发函数或作用函数 它决定节点 神经元 的输出 激发函数一般具有非线性特性 常用的非线性激发函数如图所示这里称为激活值 a 阈值型 b 分段线性型 c Sigmoid函数型 d 双曲正切型图常用的激发函数 阈值型函数又称阶跃函数 它表示激活值 和其输出f 之间的关系 阈值型函数为激发函数的神经元是一种最简单的人工神经元 也是M P模型 线性分段函数可以看作是一种最简单的非线性函数 它的特点是将函数的值域限制在一定的范围内 其输入 输出之间在一定范围内满足线性关系 一直延续到输出为最大域值为止 但当达到最大值后 输出就不再增大 S型函数是一个有最大输出值的非线性函数 其输出值是在某个范围内连续取值的 双曲正切型函数实际只是一种特殊的S型函数 其饱和值是 1和1 5人工神经网络的结构人工神经网络中 各神经元的不同连接方式就构成了网络的不同连接模型 常见的连接模型有 前向网络 从输入层到输出层有反馈的网络 层内有互联的网络 互联网络 6人工神经网络的分类及其主要特征按性能分 连续型和离散型网络 或确定型和随机型网络 按拓扑结构分 有反馈网络和无反馈网络 按学习方法分 有教师的学习网络和无教师的学习网络 按连接突触性质分 一阶线性关联网络和高阶非线性关联网络 人工神经网络主要特征优点在于 能较好的模拟人的形象思维 具有大规模并行协同处理能力 具有较强的学习能力 具有较强的容错能力和联想能力 是一个大规模自组织 自适应的非线性动力系统 弱点在于 需要更多的训练数据 在计算机上实现模拟运行比较慢无法透彻理解所使用的过程 7BP神经网络 1反向传播模型及其网络结构B P模型也称反向传播模型 是一种用于前向多层的反向传播学习算法 它可以对组成前向多层网络的各人工神经元之间的连接权值进行不断的修改 从而使该前向多层网络能够将输入它的信息变换成所期望的输出信息 在修改各人工神经元的连接权值时 所依据的是该网络的实际输出与其期望的输出之差 将这一差值反向一层一层的向回传播 来决定连接权值的修改 B P算法的网络结构是一个前向多层网络 如图所示 反向传播网络的学习算法B P算法的学习目的是对网络的连接权值进行调整 使得调整后的网络对任一输入都能得到所期望的输出 学习过程由正向传播和反向传播组成 正向传播用于对前向网络进行计算 即对某一输入信息 经过网络计算后求出它的输出结果 反向传播用于逐层传递误差 修改神经元间的连接权值 以使网络对输入信息经过计算后所得到的输出能达到期望的误差要求 B P算法的学习过程如下 选择一组训练样例 每一个样例由输入信息和期望的输出结果两部分组成 从训练样例集中取一样例 把输入信息输入到网络中 分别计算经神经元处理后的各层节点的输出 计算网络的实际输出和期望输出的误差 从输出层反向计算到第一个隐层 并按照某种能使误差向减小方向发展的原则 调整网络中各神经元