姚敏图像处理一DIP.pptVIP

Digital Image Processing 数字图像处理 第十一章 图像识别 11.1 概 述 图像识别系统 识别方法 统计模式表示 统计模式表示 统计模式识别系统 图像模式的特征 特征的分布状态 特征的分布状态 特征的分布状态 特征的分布状态 特征的分布状态 特征抽取 特征选择 特征选择 特征选择 特征选择 特征选择 线性分类器 线性分类器 线性分类器 线性分类器 线性分类器 线性分类器 线性分类器 线性分类器 线性分类器 Bayes分类器 11.3 句法识别 自动机识别 有限状态自动机 自动机识别 有限状态自动机 自动机识别 有限状态自动机 自动机识别 有限状态自动机 由有限状态文法构造对应的自动机 自动机识别 有限状态自动机 自动机识别 下推自动机 自动机识别 下推自动机 图11.18下推自动机示意图 下推存贮 ? 有限控制 a b a 输入带 ? z 栈顶 自动机识别 下推自动机 由终止状态接受的语言 对于来自?+的输入串x，M从q0开始，下推表顶上的符号为z0，按照映射的序列，扫描完整个符号串x，若机器停止在终态，则串x为M所接受。 由下推表变空接受的语言 对于来自?+的输入串x，M从q0开始，下推表顶上的符号为z0，按照映射的序列，扫描完整个符号串x，若下推表变空，则串x为M所接受 自动机识别 下推自动机 由上下文无关文法构造对应的自动机 自动机识别 下推自动机 有噪声、畸变模式的句法识别 识别方法 ? 用相似性和误差校正剖析 ? 采用随机语言与随机自动机 ? 运用模糊技术 相似性测度 符号串 转换 代换误差转换TS 删除误差转换TD 插入误差转换TI 相似性测度 符号串 Levenshtein距离定义为从x导出y所需的最小转换数目 J是从导出过程所用到的转换序列 分别表示J中的代换、删除和插入转换的数目 加权Levenshtein距离 相似性测度 例 11.10 x=cbabdbb，y=cbbabbdb，求 误差校正剖析 则称x是y的最小距离校正 L(G)是一个给定的语言（描述一类模式），y是一个待剖析的句子（待识别模式），最小距离误差校正剖析的实质就是在L(G)中寻找一个句子x ?L(G)，使其满足下述最小距离准则 误差校正剖析 设y是一个句子（一个模式），L(G)是一类语言（一类模式） y与L(G)之间的距离 就是y与其在L(G)中的最小距离校正之间的距离 k=1 误差校正剖析 最小距离分类准则 模式 描述文法 对于未知模式y，计算 如果 随机语言 ? VN和VT分别是非终止符和终止符的有限集 ? S?VN是起始符， ? Ps是随机产生式的有限集，每个产生式的形式 随机语言 以概率 随机语言 如果对于输入串x有nx条推导路径，其生成概率分别为 生成x的概率为 随机文法Gs产生的随机语言 略 概 述 句法法又称为结构法（Structural Approach） ? 结构法的识别过程不仅能够把模式分类，而且还可以描述模式的结构形态，而统计法只有模式分类的能力 ? 句法法特别适合用来解决图片识别（Picture Recognition）和景物分析（Scene Analysis）问题 ? 结构法以形式语言理论为基础 基本思想 一个复杂的模式可以由一些简单的模式递归地描述。换言之，对于每个复杂的模式，可以用一些较简单的子模式来描述，而每一个比较简单的子模式再用一些更为简单的子模式来描述，?，最后用一些最简单的识别起来比模式本身容易得多的称为模式基元（Pattern Primitive）的子模式来表示 基本思想 基本思想 基本思想 ? 自然语言：单词由语法规则连接起来构成短语，短语最后再根据语法规则构成一个完整的句子。 ? 模式的多级结构描述：模式基元按一定的规则构成子模式，子模式再按照一定的规则构成一个完整的模式。 ? 在句法模式识别中，模式是用一种类似于自然语言的“模式描述语言” 来描述的。由基元组成模式所遵循的那些规则则称为模式文法或简称文法。 模式的多级结构描述与日常所用的句子分析有明显的相似之处 系统结构 图11.9句法模式识别系统结构图 系统结构 ? 基元选择（Primitive Selection）是对所考虑的模式集选取那些能够通过一定的结构关系紧凑而方便地对模式结构加以描述，并且容易用统计方法加以抽取和识别的基本元素作为模式基元。 ? 基元抽取（Primitive Extraction）由两部分组成：模式分割和基元及关系识别 ? 文法推断（Grammar Inference）是根据相当数量的已知结构信息的模式样本，推论出分类的文法规则。然后，再用训练样本对获得的分类文法进