姚敏 数字图像处理 课件 第十一章 图像识别

Digital Image Processing 数字图像处理 E-MAIL: 姚 敏 1 第十一章第十一章 图像识别图像识别 2 11.1 11.1 概概 述述 3 数据数据 获取获取 判决判决 分类分类 待识待识 图像图像 数据数据 处理处理 结果结果 输出输出 图图11.1 11.1 图像识别系统框图图像识别系统框图 图像识别系统 4 统计法（统计法（Statistical ApproachStatistical Approach） 句法法（句法法（Syntactic ApproachSyntactic Approach） 模糊法（模糊法（Fuzzy ApproachFuzzy Approach） 识别方法 5 11.2 11.2 统计图像识别统计图像识别 6 统计模式表示 特征向量的第特征向量的第i i个分量就是模式的第个分量就是模式的第i i个特征的测量值个特征的测量值 模式的特征向量模式的特征向量 7 统计模式表示 图图11.211.2特征空间划分示意图特征空间划分示意图 8 统计模式识别系统 图图11.311.3统计模式识别系统结构图统计模式识别系统结构图 9 图像模式的特征 图像模式本身自然含有的图像模式本身自然含有的 如图像的象素灰度级、目标的边缘轮廓及纹理区域等。如图像的象素灰度级、目标的边缘轮廓及纹理区域等。 通过某种测量或变换操作人工地得出的通过某种测量或变换操作人工地得出的 如图像象素灰度级分布的直方图，图像的各种变换（如傅里叶如图像象素灰度级分布的直方图，图像的各种变换（如傅里叶 变换、余弦变换、沃什变换、哈达码变换等正交变换）系数特征变换、余弦变换、沃什变换、哈达码变换等正交变换）系数特征 等等 图像模式的图像模式的特征特征是图像模式场明显可分的本原的特性或属性是图像模式场明显可分的本原的特性或属性 10 特征的分布状态 距离距离 向量向量x x与特征集之间与特征集之间 两向量之间两向量之间 11 特征的分布状态 距离距离 类内距离类内距离 类间距离类间距离 特征选择的准则特征选择的准则1 1：类内距离小，类间距离大：类内距离小，类间距离大 12 特征的分布状态 似然比似然比 散度散度 条件概率条件概率 条件概率条件概率 13 特征的分布状态 散度散度 将两类互相将两类互相 区分的平均区分的平均 量度量度 散度散度 特征选择的准则特征选择的准则2 2：最大散度最大散度 14 特征的分布状态 熵熵 特征选择的准则特征选择的准则3 3：总总总总体体熵熵熵熵最小最小 第第i i类的概率密度类的概率密度 类内异样性的总体熵类内异样性的总体熵 向量的各分量统计独立向量的各分量统计独立 第第i i类的总体熵类的总体熵 15 特征抽取 特征抽取就是对图像模式进行物理测量或变换，得到一组反映其特性特征抽取就是对图像模式进行物理测量或变换，得到一组反映其特性 的数字值。特征抽取方法与实际问题是紧密联系的的数字值。特征抽取方法与实际问题是紧密联系的。 特征抽取有两种类型：一种是对识别对象的各个重要特性都有充特征抽取有两种类型：一种是对识别对象的各个重要特性都有充 分的理解，然后把这种特性转换为数字。与此相反，另一种并不需要充分的理解，然后把这种特性转换为数字。与此相反，另一种并不需要充 分了解识别对象的各个重要特性，而是根据某些原理进行特征抽取。分了解识别对象的各个重要特性，而是根据某些原理进行特征抽取。 要得到某类模式的足够的特征，那么来自该模式类的样本数就不要得到某类模式的足够的特征，那么来自该模式类的样本数就不 能太少。能太少。 特征抽取应对识别对象的各种特性加以考虑，但不等于说特征空特征抽取应对识别对象的各种特性加以考虑，但不等于说特征空 间维数越高越好，识别精度并不随着特征数量的增多而提高。在地球资间维数越高越好，识别精度并不随着特征数量的增多而提高。在地球资 源卫星源卫星ERS-1ERS-1可以取得十二个波段的遥感数据，但从识别精度来看，三可以取得十二个波段的遥感数据，但从识别精度来看，三 个或四个波段的组合效果最好。个或四个波段的组合效果最好。 16 特征选择 特征选择特征选择是在特征抽取以后，从中挑选出有代表性的或有效是在特征抽取以后，从中挑选出有代表性的或有效 的成份来，使得分类判决的问题能够更有效地进行。的成份来，使得分类判决的问题能够更有效地进行。 特征选择特征选择可以在前述距离准则，最大散度准则或最小熵准则可以在前述距离准则，最大散度准则或最小熵准则 的指导下进行。的指导下进行。 17 特征选择 特征选择就是决定变换矩阵特征选择就是决定变换矩阵 A A mm mm（ （mm0为有助于收敛的校正系数，或称学习率学习率 J J 的梯度的梯度 28 线性分类器 奖惩算法奖惩算法 令令 29 线性分类器 奖惩算法奖惩算法 有有 即即 30 Bayes分类器 略略 31 11.3 句法识别 32 概 述 句法法句法法又称为又称为结构法结构法（Structural ApproachStructural Approach） 结构法的识别过程不仅能够把模式分类，而且还可以描述结构法的识别过程不仅能够把模式分类，而且还可以描述 模式的结构形态，而统计法只有模式分类的能力模式的结构形态，而统计法只有模式分类的能力 句法法特别适合用来解决图片识别（句法法特别适合用来解决图片识别（Picture RecognitionPicture Recognition） 和景物分析（和景物分析（Scene AnalysisScene Analysis）问题问题 结构法以形式语言理论为基础结构法以形式语言理论为基础 33 基本思想基本思想 一个复杂的模式可以由一些简单的模式递归地描述。一个复杂的模式可以由一些简单的模式递归地描述。 换言之，对于每个复杂的模式，可以用一些较简单的换言之，对于每个复杂的模式，可以用一些较简单的 子模式来描述，而每一个比较简单的子模式再用一些子模式来描述，而每一个比较简单的子模式再用一些 更为简单的子模式来描述，更为简单的子模式来描述，最后用一些最简单的，最后用一些最简单的 识别起来比模式本身容易得多的称为模式基元（识别起来比模式本身容易得多的称为模式基元（ Pattern PrimitivePattern Primitive）的子模式来表示的子模式来表示 34 基本思想基本思想 35 基本思想基本思想 36 基本思想基本思想 自然语言自然语言：单词由语法规则连接起来构成短语，短语最后再根：单词由语法规则连接起来构成短语，短语最后再根 据语法规则构成一个完整的句子。据语法规则构成一个完整的句子。 模式的多级结构描述模式的多级结构描述：模式基元按一定的规则构成子模式，：模式基元按一定的规则构成子模式， 子模式再按照一定的规则构成一个完整的模式。子模式再按照一定的规则构成一个完整的模式。 在句法模式识别中，模式是用一种类似于自然语言的在句法模式识别中，模式是用一种类似于自然语言的“模式描述模式描述 语言语言” ” 来描述的。由基元组成模式所遵循的那些规则则称为来描述的。由基元组成模式所遵循的那些规则则称为模式文模式文 法法或简称文法。或简称文法。 模式的多级结构描述与日常所用的句子分析有明显的相似之处模式的多级结构描述与日常所用的句子分析有明显的相似之处 37 系统结构系统结构 图图11.911.9句法模式识别系统结构图句法模式识别系统结构图 38 系统结构系统结构 基元选择（基元选择（Primitive SelectionPrimitive Selection）是对所考虑的模式集选取那些是对所考虑的模式集选取那些 能够通过一定的结构关系紧凑而方便地对模式结构加以描述，并能够通过一定的结构关系紧凑而方便地对模式结构加以描述，并 且容易用统计方法加以抽取和识别的基本元素作为模式基元。且容易用统计方法加以抽取和识别的基本元素作为模式基元。 基元抽取（基元抽取（Primitive ExtractionPrimitive Extraction）由两部分组成：模式分割和由两部分组成：模式分割和 基元及关系识别基元及关系识别 文法推断（文法推断（Grammar InferenceGrammar Inference）是根据相当数量的已知结构信是根据相当数量的已知结构信 息的模式样本，推论出分类的文法规则。然后，再用训练样本对息的模式样本，推论出分类的文法规则。然后，再用训练样本对 获得的分类文法进行检测，并改进文法规则。获得的分类文法进行检测，并改进文法规则。 句法分析（句法分析（Syntax AnalysisSyntax Analysis）是的任务是判断输入模式是否是的任务是判断输入模式是否 属于给定的文法描述的模式类。属于给定的文法描述的模式类。 39 模式基元模式基元 在句法模式识别中，输入模式用一个句子（字符串）来描述。句在句法模式识别中，输入模式用一个句子（字符串）来描述。句 子的基本单位就是文法中的终止符，而终止符对应模式的基元。子的基本单位就是文法中的终止符，而终止符对应模式的基元。 基元是一个模式的基本成份。所以在用句法法处理模式识别问题基元是一个模式的基本成份。所以在用句法法处理模式识别问题 时，首先要选好基元、抽取基元和识别基元时，首先要选好基元、抽取基元和识别基元。 基元选择注意点基元选择注意点 基元应该是基本的模式元素，能够通过一定的结构关系（如基元应该是基本的模式元素，能够通过一定的结构关系（如 连接关系、位置关系等）紧凑地、方便地对模式加了描述连接关系、位置关系等）紧凑地、方便地对模式加了描述 基元用现有的非句法方法（如统计方法）加以抽取、识别。基元用现有的非句法方法（如统计方法）加以抽取、识别。 40 模式基元模式基元 着眼于着眼于边边界（界（轮轮廓）和骨架的基元，如廓）和骨架的基元，如FreemanFreeman链码链码 着眼于区域的基元，如帕夫里迪斯多着眼于区域的基元，如帕夫里迪斯多边边形形 例如手写汉汉字识别识别 采用笔划作为为基元比较较方便 对对对对于一般的于一般的图图图图像、像、图图图图形模式基元有两种形模式基元有两种类类类类型型 41 程序文法程序文法 一个一个程序文法程序文法 G Gp p 是一个五元组是一个五元组 G Gp p = =（V V N N ，V V T T ，J J，P P，S S） 其中其中V V N N 、V V T T 和和P P分别是非终止符、终止符和产生式的有限集分别是非终止符、终止符和产生式的有限集 ，S S是起始符，是起始符，J J是产生式的标号集。是产生式的标号集。P P中产生式的形式中产生式的形式: : （1 1）r r 是产生式的号是产生式的号 （2 2） 是产生式的核是产生式的核 （3 3）S S( (u u) )表示使用产生式表示使用产生式( (r r) )成功后的去向范围成功后的去向范围 （4 4） F F( (u u) )表示使用产生式表示使用产生式( (r r) )失败后的去向范围失败后的去向范围 42 程序文法程序文法 程序文法的特点程序文法的特点是：在一个导出式中，对中间句型使用了一个产是：在一个导出式中，对中间句型使用了一个产 生式以后，下一次再用什么产生式就要受到限制。生式以后，下一次再用什么产生式就要受到限制。 推导规则推导规则 必须从标号为必须从标号为(1)(1)的产生式开始；的产生式开始； 目前的链目前的链 中包含子链中包含子链 ，如果可以用产生式，如果可以用产生式 来重写子链来重写子链 ，而下一个产生式从，而下一个产生式从中中S S( (u u) )选取；如果目前的链选取；如果目前的链 中不包含子链中不包含子链 ，则，则 不能用产生式不能用产生式 ( (即链即链 不变不变) )，而下一个产生式从，而下一个产生式从F F( (u u) )中选取中选取 如果可用的转移区包含如果可用的转移区包含 ，则导出过程停止。则导出过程停止。 43 程序文法程序文法 44 属性文法属性文法 属性文法属性文法 就是一些属性加给模式基元和关系，从而把语义信息包括就是一些属性加给模式基元和关系，从而把语义信息包括 到模式描述中去。在属性文法中，每一个模式基元都有一个符号名称和到模式描述中去。在属性文法中，每一个模式基元都有一个符号名称和 一个属性向量，而每一条产生式都有一条语义或属性规则与之相联系。一个属性向量，而每一条产生式都有一条语义或属性规则与之相联系。 一个非属性文法可以变换成一个句法复杂性较低的属性文法。这样一一个非属性文法可以变换成一个句法复杂性较低的属性文法。这样一 种句法种句法语义折衷应能使一个模式识别系统具备恰当地调节句法和语义语义折衷应能使一个模式识别系统具备恰当地调节句法和语义 的相对复杂性以获得计算效果的灵活性。此时，句法规则往往十分简单的相对复杂性以获得计算效果的灵活性。此时，句法规则往往十分简单 ，而语义信息或属性规则在一定程度上被用作一种控制策略（或语义约，而语义信息或属性规则在一定程度上被用作一种控制策略（或语义约 束）来选择和解释适用于这种分析的句法规则。束）来选择和解释适用于这种分析的句法规则。 45 文法推断文法推断 文法推断文法推断：通过句子的训练样本集合来学习：通过句子的训练样本集合来学习文法文法 模式类模式类 模式文法模式文法 训练样本集训练样本集 46 文法推断文法推断 文法文法 文法推断 算法 训练样本集训练样本集 图图11.11 11.11 文法推断示意图文法推断示意图 47 文法推断文法推断 写出终止符集写出终止符集V V T T ； 对于每一个句子逐个写出能生成此句子的文法；对于每一个句子逐个写出能生成此句子的文法； 构成文法；构成文法； 合并重复的产生式和非终止符，其合并重复的产生式和非终止符，其规则规则为：为： 如果如果G G中任何产生式出现多次，则保留一个，去除其它；中任何产生式出现多次，则保留一个，去除其它； 找出这样一对变量（即非终止符），如果在找出这样一对变量（即非终止符），如果在G G中到处以其中一个中到处以其中一个 替换另一个，就会使某些产生式多次出现，进行代换并用替换另一个，就会使某些产生式多次出现，进行代换并用进行简化进行简化 找出这样一对变量（找出这样一对变量（A A，a a），），如果在如果在G G中补充产生式，并在某些中补充产生式，并在某些 有选择的情况下以有选择的情况下以A A代替代替a a，将导致产生式的数目由于消去出现多次的将导致产生式的数目由于消去出现多次的 产生式而减少。产生式而减少。 由训练样本集由训练样本集R R推断文法推断文法G G的方法的方法 48 句法分析句法分析 模式类模式类 模式文法模式文法 未知模式由句子未知模式由句子 x x 表示，其识别问题实质上就由表示，其识别问题实质上就由“ “未知模式是否属于未知模式是否属于 句法分析句法分析 自动机识别自动机识别 49 句法分析句法分析 已知一句子（字符串）x和上下文无关文法G，构成一个三角形， 并以一个自身相容的导出树将三角形内部填满。 将三角形内部填满的方法 ： 自上而下的剖析 自下而上的剖析 成功 否则 50 句法分析句法分析 给定给定x x和上下文无关文法和上下文无关文法G G，自上而下的剖析从自上而下的剖析从S S开始，开始， 应用重写最左非终止符的产生式，推导得句型应用重写最左非终止符的产生式，推导得句型y y 自上而下的剖析自上而下的剖析 直到串直到串x x，并找到并找到x x的最左推导。因为上下文无关文法中，的最左推导。因为上下文无关文法中， 因此应用产生式时，句型中的符号数不可能被减少，故而可废弃所有长因此应用产生式时，句型中的符号数不可能被减少，故而可废弃所有长 度超过度超过x x的句型，需要研究的只是长度等于或小于的句型，需要研究的只是长度等于或小于x x的句型的有限集合。的句型的有限集合。 51 句法分析句法分析 自下而上的剖析从串自下而上的剖析从串x x本身开始，应用反向的产生式，试图将本身开始，应用反向的产生式，试图将x x归结归结 到起始符到起始符S S。自下而上的剖析从自下而上的剖析从x x到到S S，以以x x的最右推导反推出产生式序的最右推导反推出产生式序 列。列。 给定和上下文无关文法给定和上下文无关文法G G，从从x x着手构成中的一些符号串，这些符号着手构成中的一些符号串，这些符号 串是应用可能出现在串是应用可能出现在x x的推导过程中的产生式的反向推演而得到的。的推导过程中的产生式的反向推演而得到的。 但在推导过程中不知道哪些序列的串可能是正确的，因此必须同时研但在推导过程中不知道哪些序列的串可能是正确的，因此必须同时研 究所有可能的序列。究所有可能的序列。 自下而上的剖析自下而上的剖析 52 句法分析句法分析 CKYCKY剖析算法剖析算法 采用树结构的剖析算法本质上是穷举试探，它对任意上采用树结构的剖析算法本质上是穷举试探，它对任意上 下文无关文法所需的剖析时间可能按字符串长度作指数增加下文无关文法所需的剖析时间可能按字符串长度作指数增加 CKYCKY剖析算法的时间则正比于输入串长度的三次方剖析算法的时间则正比于输入串长度的三次方 CKY CKY算法要求文法是一个上下文无关文法，其产生式必算法要求文法是一个上下文无关文法，其产生式必 须是乔姆斯基标准形须是乔姆斯基标准形 53 句法分析句法分析 CKYCKY剖析算法剖析算法 54 句法分析句法分析 CKYCKY剖析算法剖析算法 55 句法分析句法分析 CKYCKY剖析算法剖析算法 56 句法分析句法分析 CKYCKY剖析算法剖析算法 57 句法分析句法分析 CKYCKY剖析算法剖析算法 58 句法分析句法分析 CKYCKY剖析算法剖析算法 59 句法分析句法分析 CKYCKY剖析算法剖析算法 60 自动机识别自动机识别 基本方法基本方法：对于文法：对于文法 G G i i 构造一个相应的自动机构造一个相应的自动机 MM i i ， 使自动机使自动机 MM i i 接受的语言等于文法接受的语言等于文法 G G i i 产生的语言产生的语言 T T( (MM i i )=)=L L( (G G i i ) ) 将字符串将字符串x x作为自动机的输入链，如果作为自动机的输入链，如果x x被自动机被自动机 接受 否则 61 自动机识别自动机识别 有限状态自动机有限状态自动机 62 自动机识别自动机识别 有限状态自动机有限状态自动机 63 自动机识别自动机识别 有限状态自动机有限状态自动机 64 自动机识别自动机识别 有限状态自动机有限状态自动机 65 自动机识别自动机识别 有限状态自动机有限状态自动机 由有限状态文法构造对应的自动机由有限状态文法构造对应的自动机 66 自动机识别自动机识别 有限状态自动机有限状态自动机 67 自动机识别自动机识别 下推自动机下推自动机 68 自动机识别自动机识别 下推自动机下推自动机 图图11.1811.18下推自动机示意图下推自动机示意图 下推存贮 有限 控制 a b a 输 入 带 z 栈顶 69 自动机识别自动机识别 下推自动机下推自动机 由终止状态接受的语言由终止状态接受的语言 对于来自对于来自 + + 的输入串的输入串x x，MM从从q q 0 0 开始，下推表顶上的符号为开始，下推表顶上的符号为z z 0 0 ，按照映射按照映射 的序列，扫描完整个符号串的序列，扫描完整个符号串x x，若机器停止在终态，则串若机器停止在终态，则串x x为为MM所接受。所接受。 由下推表变空接受的语言由下推表变空接受的语言 对于来自对于来自 + + 的输入串的输入串x x，MM从从q q 0 0 开始，下推表顶上的符号为开始，下推表顶上的符号为z z 0 0 ，按照映按照映 射的序列，扫描完整个符号串射的序列，扫描完整个符号串x x，若下推表变空，则串若下推表变空，则串x x为为MM所接受所接受 70 自动机识别自动机识别 下推自动机下推自动机 由上下文无关文法构造对应的自动机由上下文无关文法构造对应的自动机 71 自动机识别自动机识别 下推自动机下推自动机 72 有噪声、畸变模式的句法有噪声、畸变模式的句法识别识别 识别方法识别方法 用相似性和误差校正剖析用相似性和误差校正剖析 采用随机语言与随机自动机采用随机语言与随机自动机 运用模糊技术运用模糊技术 73 相似性测度相似性测度 符号串符号串 转换转换 代换误差转换代换误差转换T T S S 删除误差转换删除误差转换T T D D 插入误差转换插入误差转换T T I I 74 相似性测度相似性测度 符号串符号串 LevenshteinLevenshtein距离距离定义为从定义为从x x导出导出y y所需的最小转换数目所需的最小转换数目 J J是从导出过程所用到的转换序列是从导出过程所用到的转换序列 分别表示分别表示J J中的代换、删除和插入转换的数目中的代换、删除和插入转换的数目 加权加权LevenshteinLevenshtein距离距离 75 相似性测度相似性测度 例例 11.10 x x= =cbabdbbcbabdbb，y y= =cbbabbdbcbbabbdb， 求求 76 误差校正剖析误差校正剖析 则称则称x x是是y y的最小距离校正的最小距离校正 L L( (G G) )是一个给定的语言（描述一类模式），是一个给定的语言（描述一类模式），y y是一个待剖析的是一个待剖析的 句子（待识别模式），最小距离误差校正剖析的实质就是在句子（待识别模式），最小距离误差校正剖析的实质就是在 L L( (G G) )中寻找一个句子中寻找一个句子x x L L( (G G) )，使其满足下述最小距离准则使其满足下述最小距离准则 77 误差校正剖析误差校正剖析 设设y y是一个句子（一个模式），是一个句子（一个模式），L L( (G G) )是一类语言（一类模式）是一类语言（一类模式） y y与与L L( (G G) )之间的距离之间的距离 就是就是y y与其在与其在L L( (G G) )中的最小距离校正之间的距离中的