第八章 高层理解--目标识别.ppt

ZhangXingming TheInstituteofComputerScienceandEngineering Chapter8ObjectRecognition 8 1知识表示 描述和特征描述 物体的标量特性 称为特征 特征矢量 几个描述组合起来 例如 2结构描述基元 形成物体的基本单元 由他们的类型信息表示 结构描述 基元和它们之间的关系生成 通过符号构成的链 树和图来描述 语法 字生成器的数学模型 语言 字的集合 a a b b c c abcabc 谓词逻辑它为从旧知识中通过演绎得到新知识提供了一种数学形式 处理对象是逻辑变量和量词和逻辑运算符 产生式规则If条件X处理then采取动作Y 模糊逻辑克服数值和精确知识表示的明显局限 可以用模糊规则表示知识 ifXisAthenYisB 6语义网络为一个有向图 她的节点表示物体 弧表示物体之间的关系 框架 8 2图象识别系统的基本原理 模式是对某些感兴趣客体的定量或结构描述 模式类就是具有某些共同特性的模式的集合 模式识别就是研究一种自动技术 依靠这种技术 机器将自动 或尽可能少的人工干预 把待识模式分配到各自的模式类中去 这就需要把人们的知识和经验教给机器 为机器制定一些规则和方法 并且让机器能够完成自动识别的任务 这就是模式识别的研究目标 1 预处理它主要完成模式的采集 模数转换 滤波 消除模糊 减少噪声 纠正几何失真等预处理操作 因此也要求相应的设备来实现 2 特征或基元提取特征提取实现由模式空间向特征空间的转换 有效地压缩维数 一般地说 它该是在一定分类准则下的最佳或次最佳变换器 模式识别中 分类器的分类规则固然重要 但是 如果所基于的模式特征没有包含足够的待识客体的信息或未能提取反映客体特征的信息 那么 识别的结果将面目全非 所以说 在设计分类器之前 能够快速 有效地进行特征提取是模式识别的关键 不幸的是 直到目前为止还没有形成特征提取的一般理论 随着识别任务的不同 特征提取的方法也不一样 此外 如果待识别的模式样本本身携带反映不同模式本质特性的特征 则特征提取也不一定需要 归纳起来 一般常用的方法主要包括 傅立叶分析 FourierTransformation 梅林变换 MeilinTransformation 小波变换 WaveletTransformation 矢量量化 VectorQuantization 神经网络 NeuralNetwork 高阶矩 HigherMoment 3 分类训练为了能使分类器有效地进行分类判决 还必须对分类器进行训练 学习 分类器的训练 学习是模式识别的一个重要概念 由于我们研究机器的自动识别 对分类器进行训练 使它学会识别 具有自动识别的能力 尤为重要 众所周知 一个孩子认字尚需一个反复学习过程 何况一部机器要掌握某种判决规则 学习过程更必不可少 当然 对于不同的分类方法 其学习规则也不一样 4 分类在完成训练的基础上 分类器根据已经确定的判决规则 对未知类别属性的样本执行判决过程 就是说 分类器具有了自动识别的能力 这是模式识别 出成果 的阶段 直接以其分类结果表明本次识别的结束 显然 这是举足轻重的阶段 弄得不好 会使前几阶段的工作付诸东流 8 3统计模式识别 在经典模式识别中 根据用来解决模式识别问题的数学技巧 可以将它分成两种一般的方法 统计模式识别和句法模式识别 原则上讲 聚类分析属统计模式识别的范畴 但其无监督训练的特点 所以将它单独列出 在经典模式识别中 统计模式识别在模式识别技术的发展中一直起着显著的作用 统计决策论和有关领域已成为一个固定的领域 其中实质性的理论进展和创造不断发生 这些发展强有力地冲击于模式识别的应用 按确定论和随机论来分 可分为几何分类法和概率分类法 1 几何分类法1 模板匹配法它是模式识别中的一个最原始 最基本的方法 它将待识模式分别与各标准模板进行匹配 若某一模板与待识模式的绝大多数单元均相匹配 则称该模板与待识模式 匹配得好 反之则称 匹配得不好 并取匹配最好的作为识别结果 2 距离分类法距离是一种重要的相似性度量 通常认为空间中两点距离越近 表示实际上两样本越相似 大约有十余种作为相似性度量的距离函数 其中使用最广泛的是欧氏距离 它是使用最为广泛的方法 常用的有平均样本法 平均距离法 最近邻法和 近邻法 最近邻分离器 K近邻分离器 3 线性判别函数和上述的方法不同 判决函数法是以判决边界的函数形式的假定为其特性的 而上述的方法都是以所考虑的分布的假定为其特性的 假如我们有理由相信一个线性判决边界取成 是合适的话 那么剩下的问题就是要确定它的权系数 权系数可通过感知器算法或最小平方误差算法来实现 但作为一条规则 应用此方法必须注意两点 第一就是方法的可适性问题 第二就是应用判决函数后的误差准则 4 非线性判别函数线性判决函数的特点是简单易行 实际应用中许多问题往往是非线性的 一种处理的办法将非线性函数转换为线性判决函数 所以又称为广义线性判决函数 另一种方法借助电场的概念 引入非线性的势函数 它经过训练后即可用来解决模式的分类问题 2概率分类法 几何分类法是以模式类几何可分为前提条件的 在某些分类问题中这种条件能得到满足 但这种条件并不经常能得到满足 模式的分布常常不是几何可分的 即在同一区域中可能出现不同的模式 这时 必须借助概率统计这一数学工具 可以说 概率分类法的基石是贝叶斯决策理论 设有R类样本 分别为w1 w2 wR 若每类的先验概率为P wii i 1 2 3 R 对于一随机矢量 每类的条件概率为 又称类概率密度 P X Wii 则根据Bayes公式 后验概率为 从后验概率出发 有Bayes法则 以贝叶斯法则为基础 在考虑错误判决和判决风险的情况下 就可以得到最小错误率判决 最小风险判决和最大似然判决等规则 当然 如果先验概率和损失函数没有提供 或没有全部被提供 上述最基本的贝叶斯分类方法就发生了困难 为此 可应用聂曼 皮尔逊判决规则和最小最大判决规则 上述方法都可统称为贝叶斯分类器 分类器训练的主要任务是完全确定类概率密度函数 如果训练样本的类别属性是已知的 则称为有监督训练 否则称为无监督训练 对于有监督训练的情况 当已知类概率密度的函数形式时 就要选用参数估计方法 否则就要选用非参数估计的方法 常用的参数估计方法有最大似然估计 贝叶斯估计和贝叶斯学习 非参数估计的任务就是利用已知的训练样本集来估计概率分布密度 常用的方法有Parzen窗法 Kn 近邻法和正交级数展开逼近法 对于无监督训练 也有相应的参数估计方法 此处就不详述 1 分类器学习定义 从样本集合中设置分类器参数的方法 训练集 模式和带有类别信息的集合 分类器设置应该是最优或次优的 能够识别那些它没有 见过 的对象 训练集的大小一般逐步增加几次 直到可以取得正确的分类器设置 2 基本性质学习 系统优化的过程 学习目标 使优化准则最小 训练集合有限 学习过程应该具有归纳的特点 学习无法一步完成 是一个循序渐进的过程物体描述实际上是在允许分类错误率 分类时间和分类器构造复杂度之间的折中 3 分类器学习 两个常用方法 概率密度估计和直接损失最小化概率密度估计若概率密度的形式未知 则必须估计概率密度 若已知 则必须估计参数 a 已知 未知 b 未知 已知 c 和 均未知 算法学习 计算平均向量 和协方差 计算概率密度 计算先验概率 分类 3聚类分析 硬C均值聚类算法HCM 设为一模式集 C为聚类的类别数 2 c n 是模式归类分布矩阵 大小为nXc 它满足 1 任意选择初始类中心 2 根据任一个样本与类中心之间距离的最小化 将该模式分配到相应的模式类中 即计算 矩阵 3 更新类中心 4 若类中心的变化 则停止聚类 否则转 2 8 4句法模式识别 1 基本思想对于较复杂的模式 如采用统计模式识别的方法 所面临的一个困难就是特征提取的问题 它所要求的特征量十分巨大 要把某一个复杂模式准确分类很困难 从而很自然地就想到这样的一种设计 即努力地把一个复杂模式分化为若干较简单子模式的组合 而子模式又分为若干基元 通过对基元的识别 进而识别子模式 最终识别该复杂模式 正如英文句子由一些短语 短语又由单词 单词又由字母构成一样 用一组模式基元和它们的组成来描述模式的结构的语言 称为模式描述语言 支配基元组成模式的规则称为文法 当每个基元被识别后 利用句法分析就可以作出整个的模式识别 即以这个句子是否符合某特定文法 以判别它是否属于某一类别 这就是句法模式识别的基本思想 2 几个定义 1 文法一个串文法是一个四元组 其中为非终止符集合或中间模式集合 为终止符集合或模式基元集合 S为初始符或初始模式 P为产生式集合或规则集合 2 形式语言就是由文法所形成的终止符串的集合 由文法所产生的形式语言L G 表示为 3 文法的类型 a 上下文有关文法 若 表示 的符号个数 b 上下文无关文法 若 c 正则文法 若 a 或 a 3句法模式识别系统的组成 句法模式识别系统主要由预处理 基元提取 句法分析和文法推断等几部分组成 由预处理分割的模式 经基元提取形成描述模式的基元串 即字符串 句法分析根据文法推理所推断的文法 判决有序字符串所描述的模式类别 得到判决结果 问题在于句法分析所依据的文法 不同的模式类对应着不同的文法 描述不同的目标 为了得到于模式类相适应的文法 类似于统计模式识别的训练过程 必须事先采集足够多的训练模式样本 经基元提取 把相应的文法推断出来 实际应用还有一定的困难 8 5神经网络模式识别 我们完全有理由认为 模式识别理论与神经网络 NeuralNetwork 理论是相互渗透 互相映射的 人们在最初研究模式识别问题时 也是从智能信息处理的角度入手 这是因为模式识别与人的视觉有着千丝万缕的联系 人的视觉神经系统是人脑神经中枢最丰富的神经分布区域之一 它是人与外界事物交流的 窗口 担负着 繁重 的 辩识 与分类任务 所以 如果揭示了人的视觉模式信息处理的机制 那么 基于视觉模型的神经网络识别系统将因此大受裨益 并会得到长足的发展 1 发展史 目前 以视觉神经系统为中心的神经网络理论的研究正取得迅猛的发展 这一领域所取得的些许进步 都会给模式识别带来新的希望 所以 人们普遍认为 神经网络在模式识别中的成功应用是神经网络应用最成功的一个方面 几乎所有的神经网络模型均可用于模式识别 因此 可以认为神经网络的发展史就是神经网络模式识别的发展史 大约可分为兴起 萧条和复兴三个阶段 神经网络的兴起 1943 1969 早在1943年 心理学家McCulloch和数学家Pitts提出了形式神经元的数学描述与结构方法 即MP模型 虽然MP模型功能较弱 也没有做任何模拟工作 但却建立了那个时代关于大脑的最基本概念 对后来的各种神经元及其网络模型的建立有很大的启发作用 可以说 MP模型的提出兴起了对神经网络的研究 1949年心理学家 D O Hebb提出神经元之间突融联系强度可变的假说 他认为学习过程随其前后神经元的活动而变化 根据这一假设提出的学习率为神经网络的学习算法奠定了基础 据此 人们可通过调节神经元之间的连接强度来实现神经网络的学习功能 50年代未 Rosenblatt提出的感知器 第一次把神经网络的研究付诸工程实践 这种模型显然有可能应用于模式识别 联想记忆等方面 因此 当时有上百家实验室投入这项研究 美国军方也投入了巨额资金 当时神经网络在声纳信号识别等领域的应用取得了一定的成绩 神经网络的萧条 1969 1982 第一次研究热潮未能持续很久 自60年代未至80年代初 神经网络研究经历了低潮时期 究其原因 主要是当时传统的计算机技术正处于迅速发展阶段 并在众多领域取得了很大成功 因此暂时掩盖了发展神经网理论的必要性和迫切性 其次 明斯基 M Minsky 在1969年出版了 Perceptron 一书 该书对感知器功能得出的悲观结论 在当时学术界产生了较大影响 以至使不少学者从神经网络转向其它研究领域 然而 即使在低潮时期 仍有一些学者坚持着他们的研究 并获得许多有意义的成果 神经网络的复兴 1982 现在 1982年至1986年 美国物理学家Hopfield陆续发表了几篇有影响的神经网络研究论文 他采用互连神经网络模型 引入能量函数概念 成功地求解了目前数字计算机难以解决的旅行商问题 1986年 Rumelhart Werbos分别提出了多层馈网络的反向传播学习算法 即BP算法 利用该算法可以求解感知器所不能解决的问题 从而否定了Minsky等人的错误结论 这些突破性进展 使人们再次认识到神经网络的巨大潜力 随后几年 许多国家纷纷成立专门研究机构 政府和企业投入大量资金 应用领域不断扩大 标志着世界范围内第二次神经网络研究热潮的全面掀起和蓬勃发展 2 神经网络模式识别与统计模式识别的关系 人工神经网络模式识别与传统模式识别都是在50年代后期被人们提出来的 可以说 它们分别代表模式识别的两个不同的分支 但是 它们却是紧密相关的 理解它们的关系会帮助我们更好地理解人工神经网络理论 而传统的模式识别方法又为设计神经网络分类器提供更好的指导 反过来 神经网络分类器又将使传统的统计分类器的性能得到明显的改进 一般来说 神经网络方法最大的特点是网络是有自适应能力 此外 一般的神经网络分类器还兼有模式变换和模式特征提取的作用 所以 一般的神经网络分类器不需要对输入的模式做明显的特征提取 网络的隐层本身就具有特征提取的功能 最后一点是 神经网络分类器一般对输入模式信息的不完备或特征的缺损不太敏感 和传统的模式识别方法比较起来 神经网络分类器在背景噪声统计特性未知的情况下 其性能更好 3 神经网络模式分类器的学习 与经典模式识相类似 神经网络必须经过学习 训练 才具有分类能力 已出现的一些训练方法已显示出和人类智力发展过程有许多相似之处 由于神经网络的学习还是非常有限的 因此 不容过分乐观 本节首先讨论学习的目的 然后讨论学习的二种方式 最后简单讨论一下学习算法 学习的目的网络训练的目的就是使一组模式入集产生相应的输出集 训练过程中 对每一个输入模式 根据事先编好的程序调节权值 通过迭代使网络权集趋于稳定 从而以突触权的形式将分类信息存储于网络中 一旦给定某一待识模式 网络将根据已存储的信息回忆识别待识模式 有教师学习有教师学习 又称监督学习 它要求对训练集中每一输入向量配上一个模式类别属性 外在的教师或理想输出 对于每次模式样本的输入 网络输出端都有一个对应的指导 监督 信号与其属性相匹配 基于网络输出端监督信号与实际输出的某种目标函数准则 通过不断调整网络的连接权值 使得网络输出端的输出与监督信号的误差逐惭减小至预定的要求 无教师 自组织 学习对无教师学习或自组织学习 是不存在外在的教师或指导进行监督的学习过程 即训练模式集中无模式类别属性标记 网络结构和连接权值根据某种聚类法则 自动对周围环境的模式样本进行学习调整 直至网络的结构和连接分布能合理地反映训练样本的统计分布 学习算法今天的大多数训练算法都是受D O Hebb启发 关于神经元突触权的变化 心理学家Hibb的假设是著名的 这个假设的基本内容是 只有当神经元兴奋时 神经元的突触结合权才被强化而增大 根据Habb原理 可按下式进行权值调整 虽然已有一些运用Hebb学习的网络被构造出来 但都不十分有效 Hebb的贡献并不在于其学习算法的有效性而在于其思想性和启蒙作用 今天的神经网络常用的学习算法有 错误一正确学习竞争学习相关学习正交学习 4 BP神经网络分类器分析 BP算法 又称广义 规则 是一种训练多层前馈 feed frrward 网络的方法 它对人工神经网络的复兴起了重要的作用 无数成功的应用 显示出了它的威力 BP算法主要用于解决多层前馈网络的训练 其思想是基于感知器的 规则 并且传输函数采用非线性的Sigmoid函数 但应用 规则时 却遇到隐层节点输出误差无法计算的困难 于是Rumelhart将输出层产生的误差反向传播到隐层 从而解决这一矛盾 因而BP算法又称为广义 规则 尽管BP算法有许多成功实例 但在实际应用中存在以下几个问题 BP算法的学习率 以及角动量因子 很难事先选定 过小的 会引起收敛速度过慢 过大的 又会引起振荡 过小的 起不到平滑作用 过大的 会使修正远离梯度最大方向 BP算法是LMS 规则 算法的推广 因而存在LMS算法的局部极小值问题 初始权值的选择也影响算法的收敛速度 有时甚至会导致算法收敛于局部极小值 隐含层的层数及各隐层神经元个数也难以确定 虽有一些定量分析 但明显带有经验色彩 无普适性 针对BP算法的缺陷 人们做了大量的研究工作 发表了近百篇研究论文 1987年Chan和Fallside等人给出一种选择最佳和 的自适应训练方法 为解决局部极小问题 1992年Sadjadi提出了一种基于误差梯度为零的递推最小二乘方法 1993年Hush等人给出了一种训练样本数与输入 输出及隐含层神经元个数的经验计算公式 1994年 A G Parlos提出了加速收敛速度的批处理算法 所有这些改进 给人的印象是带有明显的修修补补的色彩 无统一的理论柜架 显然 这是一个组合优化的问题 遗传算法有可能成为解决上述缺陷的一条途径 8 6模糊模式识别 1 问题的提出模式识别是一门边缘学科 它和许多技术学科有着密切的联系 它本身就是人工智能的重要组成部分 因此 从本质上来说 模式识别所要讨论的核心问题 就是如何使机器能模拟人脑的思维方法 来对客观事物进行有效的识别和分类 一方面现有的广为运用的统计模式识别方法与人脑进行模式识别相比 其差别还很大 另一方面待识别的客观事物又往往具有不同程度的模糊性 例如 当你在街上碰到十多年未见面的老同学时 虽然时间使他发生了很大变化 诸如变老 变高 变胖等 但只要不是 面目全非 或故意伪装 你基本上可以认出他来 这一过程若让机器去完成就相当困难 问题在于你识别一个人时 采用的全是模糊概念的比较 如口音 相貌 举止特点 对方对自己的反应等等 你用当前看到的这些模糊特征同脑中已有的该人以前的对应特征相对比 进行综合取舍后就会得出结论 因此 不少学者试图运用模糊数学的方法来解决式识别问题 形成一个专门的研究领域 模糊模式识别 FuzzyPatternRecognition 比较成熟的理论和方法有最大来属原则 基于模糊等价关系的模式分类 基于模糊相似关系的模式分类和模糊聚类 其中模糊聚类方法的研究和应用尤为成功和广泛 目前 模糊模式识别方法已广泛应用图形识别 染色体和白血球识别 图象目标的形状分析 手写体文字识别等 但其中也遇到不少困难 其中一个典型的例子就是隶属函数的确定往往带有经验色彩 2 模式分类的隶属原则与择近原则 1 最大隶属原则设论域U有几个模糊子集A1 A2 An 对每一个Ai均有隶属函数 则对任一待识模式 若有则认为Xo隶属于Ai 最大隶属原则简单明了 易于公认 但其效果如何 却十分依赖于建立已知模式类隶属函数的技巧 2 择近原则在实际问题中 有时要考虑两个Fuzzy集的靠近程度 即贴近度N 这时模式分类问题就变成根据贴近度作模式分类 常用的贴近度的计算方法有距离法 最小最大比及内积外积函数法等 3模糊聚类分析 由于客观事物之间的界限往往不一定很清晰 因此把模糊数学引入聚类分析的研究 用以处理具有模糊性的事物的聚类问题 无疑是十分合适的 事实上 模糊聚类 FuzzyCluster 分析是近年来 应用模糊集方法 中 发展最为迅速的一种方法 也是收效最为显著的一个领域 把模糊集论作为聚类分析理论的思想首先由Bellman等人1966年提出来的 但真正第一次系统阐述模糊聚类分析问题的 应该首推Ruspini 1970 的著作 它对模糊聚类分析的研究起了巨大的推动作用 1973年Woodury提出了模糊统计混合聚类算法 真正最有影响应用最广泛的当属Dunn 1973 首先提出来的第一个模糊C一均值算法 FCM 此后Gustafson 1979 Bezdek等人 1981 分别对此算法作了改进 目前 模糊聚类算法已成功运用于雷达目标识别 图象分割和石油地质等领域 模糊C均值算法FCM 1 任意选择初始类中心C为总类别数 2 计算 3 计算类隶属矩阵 4 更新聚类中心 5 检查 则转 3 否则停止 8 7SVM支持向量机 1 理论基础SVM系列是基于结构风险最小化的原则 目标是最小化期望 实际 风险的上界 这种风险定义如下 是定义训练集的参数集合 是与训练样本x相关的类别号 是一个从训练样本影射成为类别号的函数 而是一个类别与每一个样本相关的未知的概率分布 表示样本数量并选择使 是训练集得到的经验风险安定h是VC维 最右边式子的另外一个术语是VC置信度 有两种办法最小化上边界 第一种是保持VC置信度而最小化经验风险 第二种是保持经验风险 到一个较小的值 而最小化VC置信度 后者是SVM系列的基础 2 最优分类面 考虑线性可分情况 H为把两类没有错误地分开的分类线 H1和H2分别为过各类样本中离分类线最近的点且平行于分类线的直线 H1和H2之间的距离叫做两类的分类空隙或分类间隔 所谓最优分类线就是要求不但能将两类无错误地分开 经验风险最小 而且要使两类的分类空隙最大 实际风险最小 推广到高维空间 最优分类线就成为最优分类面 在可以分开训练样本的超平面集合里找最优超平面 这个超平面最小化VC置信度并提供最好的扩展能力 给一个几何解释 最优超平面最大化最近的正样本和负样本之间的距离总和 这个总和称为可分超平面的分类空隙 3 支持向量 设线性可分样本集是类别标号 D维空间中线性判别函数的一般形式 分类面方程为 将判别函数归一化 使两类所有样本都满足也就是使离分类面最近的样本的 这样分类间隔就等于 因此使间隔最大等价于使最小 而要求分类线对所有样本正确分类 就要求 过两类样本中离分类面最近的点且平行于最优分类面的超平面H1和H2上的训练样本就是使上式等式成立的那些样本 称为支持矢量 1 4 最优分类面的求解 在 1 式的约束下 求下面函数的最小值 为此 可以定义Lagrange函数 若为最优解 则 可以证明 支持向量的不等于零 而其它样本的均等于零 由此 可以得到最优分类函数 上式求和实际上是对支持向量来进行的 5 支持向量机 这些观念可以扩展到非线性可分的情况下 可以增加一个松弛项到式子中 这个式子是非线性可分训练样本到分类空隙的方差总和 这个总和是通过控制最小错分的参数来权衡的 第二个问题是怎样处理非线性分类边界 这可以通过用核函数影射训练样本到高维特性空间来完成 在高维空间里 分类边界是线性的 常用的核函数是径向基函数 定义如下 和表示两个样本 值是用户控制的参数用来决定高斯核的宽度 支持向量机的基本思想 首先通过非线性变换将输入空间变换到一个高维空间 然后在这个空间中求取最优线性分类面 而这种非线性变换是通过定义适当的内积函数实现的 8 8GeneticAlgorithms Geneticalgorithms useanaturalevolutionmechanismstosearchforthemaximumofanobjectfunction Generation ThreebasicoperationReproduction isresponsibleforthesurvivalofthefittestandforthedeathofothersbasedonaprobabilistictreatment itcopiesstringswithhighestfitnessintothenextgenerationofstrings Crossover randomlychoosingapositionfortheborderofeachpairofstrings andtoproducenewstringsbysallcharactersbetweenthebeginningofthestringpairsandtheborderposition Mutation israndomlytochangeonecharaterofsomestringofthepopulationfromtimetotime algorithm Createastartingpopulationofcodestrings andfinethevalueoftheirobjectivefunction Probabilisticallyreproducehighfitnessstringinthenewpopulation removepoorfitnessstrings Constructnewstringscombiningreproducedcodestringsfromthepreviouspopulation Fromtimetotime changonecharacterofsomestrin