图像匹配与识别实用教案.ppt

•9.1￿基本概念•模式，模式类，模式识别系统•9.2￿基于统计(tǒngjì)决策的模式识别•匹配法，贝叶斯分类器，线性分类器，k近邻分类器•9.3￿基于结构句法的模式识别•形状数匹配，串匹配，串句法识别•9.4￿基于智能计算方法的模式识别•模糊模式识别，人工神经网络，•统计(tǒngjì)学习理论，支撑向量机第九章￿图像匹配与识别(shíbié)第1页/共63页第一页，共64页9.1￿基本概念——引言(yǐnyán)模式识别是一切生物的认知能力的基础在图像处理以及计算机视觉技术中，模式识别是实现(shíxiàn)图像理解的必由之路在人工智能领域，模式识别是一切基于传感信息的智能技术的必要模块第2页/共63页第二页，共64页9.1￿基本概念——模式(móshì)模 式 的 广 义 定 义存 在 于 时 间 和 空 间 中 的 可 观 察 ， 可 区 分 的 事 物 的 信 息 形 式模 式 的 狭 义 定 义用 于 进 行 事 物 分 类 的 特 征 描 绘 ( m i á o h u ì ) 子 的 有 序 组 合 图 像 信 号 中 的 模 式能 够 用 以 区 分 物 体 的 光 学 信 息 的 有 效 表 达 形 式第3页/共63页第三页，共64页。

9.1￿基本概念——模式(móshì)模 式 的 数 学 表 达 形 式常 用 的 三 种 ： 矢 量 、 串 和 树例 子 ： I r i s 数 据 库 ( F i s h e r , 1 9 3 6 )I r i s 数 据 库 是 对 鸢 尾 属 的 三 种 花 的 数 据 测 量 结 果 ， 其 中 每 朵 花 的 模 式 由 4 个 数 据 表 示 ， 分 别 是 萼 片 ( è ￿ p i à n ) 长 度 、 萼 片 ( è ￿ p i à n ) 宽度 、 花 瓣 长 度 和 花 瓣 宽 度 ， 这 样 一 朵 花 的 模 式 可 以 用 一 个 4 维 矢 量 来 表 示 第4页/共63页第四页，共64页9.1￿基本概念——模式(móshì)类模式类是具有共同性质的模式族，模式类是对事物分类结果的一种变相描述，它反映了同类(tónglèi)事物的相似性与不同事物的区别性第5页/共63页第五页，共64页9.1￿基本概念——模式分类(fēn￿lèi)与识别将 不 同 的 模 式 通 过 归 纳 的 方 法 分 成 不 同 的 模 式 类 即 为 模 式 分 类 ； 对 于 一 个 未 知 其 类 别 的 模 式 ， 找 到 它 所 从 属 ( c ó n g s h ǔ ) 的 模 式 类 即为 模 式 识 别 （ 狭 义 ） 。

模 式 识 别 ( 广 义 ) 的 主 要 内 容（ 1 ） 特 征 提 取 和 选 择 （ 建 立 模 式 ）（ 2 ） 决 策 分 类 （ 建 立 模 式 到 模 式 类 的 映 射 ）第6页/共63页第六页，共64页9.1￿基本概念——模式识别(mó￿shì￿shí￿bié)系统模 式 识 别 的 两 个 基 本 过 程 ( g u ò c h é n g ) ： 设 计 与 实 现模 式 识 别 系 统 的 基 本 构 成信息获取数据预处理特征提取和选择分类器设计分类决策训练过程输出结果第7页/共63页第七页，共64页9.1￿基本概念——模式识别(mó￿shì￿shí￿bié)的分类两 种 基 本 的 模 式 识 别 方 法统 计 识 别 方 法 ：建 立 特 征 ( t è z h ē n g ) 空 间 ， 利 用 统 计 决 策 理 论贝 叶 斯 决 策 ， 判 别 函 数 法 ， k 近 邻 法 ， 风 险 最 小 化 ， 非 线 性 映 射 ， 特 征 ( t è z h ē n g ) 分 析 ， 主 元 分 析 等结 构 （ 句 法 ） 识 别 方 法 ：着 眼 于 对 待 识 别 对 象 的 结 构 特 征 ( t è z h ē n g ) 的 描 述 。

将 一 个 识 别 对 象 看 成 是 一 个 语 言 结 构 ， 例 如 一 个 句 子 是 由 单 词 和 标 点 符 号 按 照一 定 的 语 法 规 则 生 成 的 ， 同 样 ， 一 幅 图 像 是 由 点 、 线 、 面 等 基 本 元 素 按 照 一 定 的 规 则 构 成 的 ￿第8页/共63页第八页，共64页9.1￿基本概念——模式识别(mó￿shì￿shí￿bié)的分类统 计 识 别 方 法 中 的 新 发 展模 糊 模 式 识 别 ： 以 模 糊 数 学 ( f u z z y ￿ m a t h ) 为 理 论 基 础 ， 将 计 算 机 中 常 用 的 二 值 逻 辑 转 化 为 连 续 逻 辑 模 糊 识 别 的 结 果 是 用 被 识 别 对象 隶 属 于 某 一 类 别 的 程 度 基 于 人 工 神 经 网 络 的 模 式 识 别 ： 人 工 神 经 网 络 研 究 源 于 对 生 物 神 经 系 统 的 研 究 它 将 若 干 个 处 理 单 元 ( 即 神 经 元 ) 通 过 一 定 的 互 连 模 型连 结 成 一 个 网 络 ， 这 个 网 络 通 过 一 定 的 机 制 ( 如 误 差 后 向 传 播 ) 可 以 模 仿 人 的 神 经 系 统 的 动 作 过 程 ， 以 达 到 识 别 分 类 的 目 的 。

统 计 学 习 理 论 与 支 撑 向 量 机 ： 将 统 计 模 式 识 别 看 作 是 机 器 学 习 理 论 的 一 个 特 例 ( t è l ì ) ， 通 过 系 统 的 自 主 学 习 建 立 模 式 分 类 规 则 ， 其 中的 支 撑 向 量 机 是 目 前 研 究 的 热 点 ， 主 要 解 决 小 样 本 ， 非 线 性 以 及 高 维 度 的 模 式 识 别 问 题 第9页/共63页第九页，共64页9.1￿基本(jīběn)概念——模式识别的基本(jīběn)问题模 式 类 的 紧 致 性对 比 于 图 形 学 中 的 凸 集 概 念模 式 的 相 似 性非 负 性 、 最 大 性 、 对 称 性 、 单 调 性 空 间 距 离 是 度 量 模 式 相 似 性 的 最 佳 手 段 之 一 特 征 与 分 类 的 关 系面 向 模 式 识 别 ( m ó ￿ s h ì ￿ s h í ￿ b i é ) 的 特 征 的 产 生 应 考 虑 到 分 类 的 需 要 ， 同 一 个 目 标 在 不 同 的 分 类 需 求 下 的 特 征 可 能 是 不 同 的第10页/共63页第十页，共64页。

9.1￿基本概念——模式识别(mó￿shì￿shí￿bié)系统的应用模 式 识 别 系 统 在 图 像 处 理 领 域 的 应 用 ( y ì n g y ò n g )模 式 识 别 已 经 在 天 气 预 报 、 卫 星 航 空 图 片 解 释 、 工 业 产 品 检 测 、 字 符 识 别 、 语 音 识 别 、 指 纹 识 别 、 医 学 图 像 分 析 等 许 多 方 面 得 到 了 成功 的 应 用 ( y ì n g y ò n g ) ￿具 体 来 讲 ， 模 式 识 别 在 图 像 处 理 与 分 析 中 的 典 型 应 用 ( y ì n g y ò n g ) 有 ：￿ ￿ ￿ ￿ ( 1 ) ￿ 字 符 识 别 ￿ ￿ ￿ ￿￿ ￿ ￿ ￿ ( 2 ) ￿ 生 物 特 征 识 别 ￿ ￿￿ ￿ ￿ ￿ ( 3 ) ￿ 遥 感 应 用 ( y ì n g y ò n g ) ￿ ￿ ￿ ￿( 4 ) ￿ 医 学 诊 断第11页/共63页第十一页，共64页9.2￿统计(tǒngjì)决策模式识别——基本概念统 计 决 策 模 式 识 别 方 法设 模 式 的 数 学 ( s h ù x u é ) 表 达 形 式 为 矢 量 性 ， 记 为 x = ( x 1 , ￿ x 2 , … , ￿ x n ) T 。

统 计 决 策 方 法 的 基 本 思 路 就 是 为 所 有 的 模 式 类 ω 1 , ￿ ω 2 , ￿… , ￿ ω W 建 立 决 策 方 程 d i ( x ) , ￿ ￿ i = 1 , 2 , … , W ， 若 ：则 模 式 x 被 判 决 为 属 于 模 式 类 ω i 区 分 模 式 类 ω i 与 ω j 的 边 界 称 为 决 策 边 界 b i j ， 由 于 该 边 界 通 常 以 高 维 空 间 中 的 超 曲 面 形 式 存 在 ， 因 此 也 ￿ 被 称 为 决 策 平 面 ￿ b i j 由 符合 以 下 条 件 的 点 组 成 统计(tǒngjì)决策方法的关键是找到合适决策函数第12页/共63页第十二页，共64页9.2￿统计决策(juécè)模式识别——匹配匹 配 方 法 ( f ā n g f ǎ ) 的 基 本 思 路 是 为 每 一 个 模 式 类 建 立 一 个 模 板 ， 将 衡 量 待 识 别 模 式 与 模 板 的 相 似 性 作 为 该 模 式 类 的 决 策 方 程 最 常 用 的 模 板 产 生 方 法 ( f ā n g f ǎ ) 就 是 计 算 每 一 个 模 式 类 内 部 所 有 训 练 模 式 的 均 值 。

常 用 的 匹 配 方 法 ( f ā n g f ǎ )最 小 距 离 匹 配 法最 大 相 关 性 匹 配 法第13页/共63页第十三页，共64页9.2￿统计决策模式识别(mó￿shì￿shí￿bié)——匹配最 小 距 离 匹 配 法 （ 又 称 最 小 距 离 分 类 器 ）用 高 维 空 间 中 两 点 之 间 的 欧 氏 距 离 衡 量 待 识 别 模 式 与 每 个 模 式 类 模 板 的 相 似 性模 式 到 模 板 的 欧 氏 距 离 越 小 ， 则 相 似 性 越 大 ， 对 应 的 决 策 ( j u é c è ) 方 程 的 值 也 越 大 第14页/共63页第十四页，共64页9.2￿统计决策模式识别(mó￿shì￿shí￿bié)——匹配•最小距离(jùlí)匹配法示意图第15页/共63页第十五页，共64页9.2￿统计决策模式识别(mó￿shì￿shí￿bié)——匹配最大相关性匹配法利用待识别模式与模板(múbǎn)的归一化相关系数作为其相似性度量二维情况下：归一化相关性衡量的是两个矢量的夹角余弦值，与矢量长度无关相关系数越大，相似性越大第16页/共63页第十六页，共64页。

9.2￿统计(tǒngjì)决策模式识别——匹配基 于 模 板 窗 口 的 匹 配 模 式 识 别 方 法将 模 式 类 的 模 板 作 为 一 个 操 作 窗 口 ， 令 其 在 包 含 待 识 别 目 标 的 图 像 上 滑 动 ， 并 在 每 个 位 置 上 计 算 模 板 与 对 应 图 像 区 域 的 相 似 性 ， 得 到相 似 性 最 大 的 某 个 点 ， 若 该 点 相 似 性 大 于 设 定 的 阈 值 ， 则 认 为 该 点 对 应 的 区 域 内 包 含 了 属 于 ( s h ǔ y ú ) 该 模 式 类 的 某 个 模 式基 于 模 板 窗 口 的 匹 配 方 法 的 实 际 上 同 时 包 含 了 图 像 分 析 ， 特 征 提 取 与 模 式 识 别 的 内 容 ， 是 基 于 图 像 这 一 信 号 模 式 所 特 有 的 一 种 模 式 识别 算 法 第17页/共63页第十七页，共64页9.2￿统计(tǒngjì)决策模式识别——匹配模板窗口操作步骤下图给出了模板匹配的示意图，其中(qízhōng)假设原图像f(x, y)和模板图像t(k, l)的原点都在左上角。

对任何一个f(x, y)中的(x, y)， 根据式（5-2-3）都可以算得一个R(x, y)值当x和y变化时，t(j, k)在原图像区域中移动并得出R(x, y)所有值R(x, y)的最大值便指出了与t(j, k)匹配的最佳位置，若从该位置开始在原图像中取出与模板大小相同的一个区域， 便可得到匹配图像第18页/共63页第十八页，共64页9.2￿统计(tǒngjì)决策模式识别——匹配基于相关性的模板(múbǎn)窗口操作示例（（a a）图像；）图像；（（b b）子图；）子图；（（c c）） （（a a）和（）和（b b）的相关系数当子图和原图中的字母）的相关系数当子图和原图中的字母(zìmǔ)“D”(zìmǔ)“D”一致时，一致时， （（c c）） 中出现最高值（亮点）；中出现最高值（亮点）；第19页/共63页第十九页，共64页9.2￿统计决策(juécè)模式识别——匹配用 归 一 化 互 相 关 ( x i ā n g g u ā n ) 求 匹 配 的 计 算 工 作 量 非 常 大 ， 因 为 模 板 要 在 ( M － J ＋ 1 ) × ( N － K ＋1 ) 个 参 考 位 置 上 做 相 关 ( x i ā n g g u ā n ) 计 算 ， 其 中 ， 除 最 佳 匹 配 点 外 ， 其 余 做 的 都 是 无 效 运 算 ， 所 以 有 必 要 对 其 进 行 改 进 ， 以 提 高 运 算 速 度 。

常 用 的 方 法 有 ： 序 贯 相 似 性 检 测 算 法 、 幅 度 排 序 相 关 ( x i ā n g g u ā n ) 算 法 、 F F T 相 关( x i ā n g g u ā n ) 算 法 、 分 层 搜 索 序 贯 判 决 算 法 等 模 板 窗 口 匹 配 的 主 要 局 限 性 在 于 它 只 能 进 行 平 行 移 动 ， 如 原 图 像 中 要 匹 配 的 目 标 发 生 旋 转 或 大 小 变化 ， 该 算 法 无 效 另 外 ， 如 原 图 像 中 要 匹 配 的 目 标 只 有 部 分 可 见 ， 该 算 法 也 无 法 完 成 匹 配 （ 即 模板 窗 口 匹 配 法 只 有 平 移 不 变 性 ， 不 具 备 尺 度 和 旋 转 不 变 性 ）第20页/共63页第二十页，共64页9.2￿统计决策(juécè)模式识别——最优统计分类器最 优 统 计 分 类 是 一 种 基 于 概 率 ( g à i l ǜ ) 的 分 类 器 ， 其 基 本 思 想 是 选 择 错 分 损 失 最 小 的 模 式 类 作 为 当 前 模 式 的 分 类 结 果 ， 对 应 的 决 策 方程 与 错 误 分 类 损 失 函 数 成 反 比 。

将 模 式 x 分 给 模 式 类 ω j 的 平 均 损 失 为 ：当 i 满 足 以 下 条 件 时 ， x 被 分 类 为 模 式 类 ω i 第21页/共63页第二十一页，共64页9.2￿统计(tǒngjì)决策模式识别——最优统计(tǒngjì)分类器当 各 类 的 误 分 损 失 均 等 时 ：当 每 个 模 式 类 的 误 分 损 失 均 等 时 ， 最 优 统 计 分 类 器 的 决 策 方 程 ( f ā n g c h é n g ) 即 为 模 式 与 模 式 类 的 联 合 概 率第22页/共63页第二十二页，共64页9.2￿统计(tǒngjì)决策模式识别——最优统计(tǒngjì)分类器Gaussian模式(móshì)分类的贝叶斯分类器假设每一个模式(móshì)类内的模式(móshì)概率分布服从高斯分布，则最优统计分类器第23页/共63页第二十三页，共64页9.2￿统计决策(juécè)模式识别——最优统计分类器G a u s s i a n 模 式 分 类 的 贝 叶 斯 分 类 器设 每 个 模 式 类 自 身 ( z ì s h ē n ) 概 率 相 同 ， 且 每 个 模 式 类 的 协 方 差 矩 阵 为 单 位 阵 ， 则 决 策 方 程 等 价 于 ：即 等 价 于 最 小 距 离 分 类 器 ， 也 就 是 说 ， 最 小 距 离 分 类 器 是 高 斯 模 型 下 的 最 优 分 类 器 的 一 个 特 例 。

基 于 高 斯 模 型 的 贝 叶 斯 分 类 器 为 我 们 估 计 每 个 模 式 类 的 概 率 密 度 函 数 提 供 了 平 台 ， 将 概 率 密 度 函 数 构 建 问 题 转 换 为 参 数 估 计 问 题 第24页/共63页第二十四页，共64页9.2￿统计决策(juécè)模式识别——最优统计分类器高 斯 贝 叶 斯 分 类 器 应 用 实 例对 遥 感 ( y á o g ǎ n ) 多 光 谱 图 像 进 行 处 理 ，1 ） 获 取 训 练 模 式 集 ， 可 采 用 交 互 方 式 在 图 像 中 不 同 区 域 选 择 不 同 地 理 类 型 ， 并 根 据 对 应 的 像 素 的 多 光谱 灰 度 建 立 训 练 模 式 向 量 x ， x 的 维 度 与 多 光 谱 的 子 代 数 相 同 2 ） 根 据 训 练 模 式 集 获 取 每 个 模 式 类 的 均 值 与 方 差 3 ） 根 据 高 斯 贝 叶 斯 分 类 器 ， 对 图 像 中 每 个 像 素 对 应 的 模 式 进 行 分 类 第25页/共63页第二十五页，共64页9.2￿统计(tǒngjì)决策模式识别——最优统计(tǒngjì)分类器高斯贝叶斯分类(fēn lèi)器分类(fēn lèi)结果第26页/共63页第二十六页，共64页。

9.2￿统计(tǒngjì)决策模式识别——线性分类器线 性 分 类 器 就 是 采 用 线 性 决 策 ( j u é c è )函 数 的 分 类 器 ， 其 决 策 ( j u é c è )边 界 是 高 维 空 间 中 的 一 个 超 平 面 其 表 达式 为 ：决 策 ( j u é c è )分 类 过 程 可 以 由 下 式 判 定 ：如 何 得 到 决 策 ( j u é c è )函 数 的 参 数 w i ？通 过 学 习 ， 即 选 择 一 部 分 训 练 样 本 ， 并 基 于 分 类 正 确 的 约 束 条 件 建 立 一 个 评 价 函 数 （ 通 常 两 类 的 区 分 情 况 ） ， 并在 该 约 束 条 件 下 对 评 价 函 数 进 行 优 化 ， 得 到 最 优 的 参 数 第27页/共63页第二十七页，共64页9.2￿统计决策模式识别(mó￿shì￿shí￿bié)——k近邻分类器基 本 思 想选 择 一 部 分 训 练 样 本 ， 并 记 录 每 个 样 本 的 类 别 标 号 计 算 待 识 别 样 本 到 所 有 训 练 样 本 的 距 离 （ 绝 对 距 离 ， 欧 式 距 离 或 马 氏 距 离 ） ， 找 到 距 离 待 识 别 样 本 最 近 的 k 个 训 练 样 本 。

对 照 k 个 最 近 邻 样 本 的 模 式 类 ， 找 出 其 中 占 比 例 最 大 的 模 式 类 对 应 的 类 别 标 号 ， 如 出 现 两 个 模 式 类 所 占 比 例 相 同 ， 则 进 一 步 参 考 每 类 内包 含 的 样 本 到 待 识 别 样 本 的 最 近 距 离 作 为 附 件 决 策 条 件 根 据 占 比 例 最 大 并 且 距 离 最 近 的 类 别 标 号 ， 将 待 识 别 样 本 判 决 为 该 类 别 标 号 对 应 的 模 式 类 特 点K 近 邻 法 效 果 一 般 较 好 ， 并 且 提 供 了 相 当 多 的 算 法 ( s u à n ￿ f ǎ ) 改 进 可 能 性 ， 但 计 算 量 极 大 第28页/共63页第二十八页，共64页9.2￿统计决策(juécè)模式识别——k近邻分类器第29页/共63页第二十九页，共64页9.3￿结构(jiégòu)句法模式识别——引言统 计 决 策 模 式 识 别 方 法 不 考 虑 模 式 本 身 的 结 构 或 语 法 特 征 ， 而 只 把 模 式 看 做 一 个 高 维 空 间 中 点 。

结 构 句 法 模 式 识 别 方 法 则 将 模 式 看 做 是 一 个 结 构 体 ， 模 式 涉 及 的 每 一 个 特 征 都 有 各 自 的 作 用 和 所 处 的 位 置 因 此 特 征 的 组 合 形 式( x í n g s h ì ) 对 于 结 构 句 法 模 式 识 别 方 法 而 言 ， 是 非 常 重 要 的 结 构 句 法 模 式 识 别 方 法 需 要 特 别 重 视 每 种 模 式 的 结 构 特 点 ， 不 同 结 构 的 模 式 ， 可 能 需 要 不 同 的 模 式 识 别 方 法 进 行 处 理 第30页/共63页第三十页，共64页9.3￿结构句法模式识别(mó￿shì￿shí￿bié)——形状数匹配目 标 a 和 目 标 b 的 形 状 的 相 似 度 k 被 定 义 为 使 得 这 两 个 目 标 的 形 状 数 相 同 的 最 大 阶 数 此 时 ( c ǐ ￿ s h í ) ， a 和 b 的 形 状 距 离 可 以 为 相 似 度 k 的 倒 数第31页/共63页第三十一页，共64页9.3￿结构句法(jùfǎ)模式识别——形状数匹配第32页/共63页第三十二页，共64页。

9.3￿结构(jiégòu)句法模式识别——串匹配两 个 目 标 的 边 界 被 编 码 成 字 符 串 ， 分 别 表 示 为 a 和 b ， 若 a k = b k ， 则 成 两 个 字 符 串 在 第 k 位 上 匹 配 ， 两 个 字 符 串 之间 发 生 匹 配 的 次 数 ， 称 为 匹 配 数 目 ， 记 为 α 则 无 法 匹 配 的 字 符 数 目 为 ：判 断 ( p à n d u à n ) 字 符 串 相 似 性 的 方 法 即 定 义 相 似 性 R 为 ：当 两 个 字 符 串 完 全 一 致 时 ， R = ∞ ， 当 两 个 字 符 串 之 间 不 发 生 匹 配 时 ， R = 0 ；第33页/共63页第三十三页，共64页9.3￿结构句法(jùfǎ)模式识别——句法(jùfǎ)识别基本概念所 谓 句 法 ， 是 描 述 语 言 规 则 的 一 种 法 则 一 个 完 整 的 句 子 一 定 是 主 语 + 谓 语 或 主 语 + 谓 语 + 宾 语 ( 或 表 语 ) 的 基 本 结构 构 成 一 种 特 定 的 语 言 ， — 定 类 型 的 句 子 之 间 是 有 — 定 的 结 构 顺 序 的 。

￿无 规 则 的 任 意 组 合 ， 必 然 达 不 到 正 确 的 思 想 交 流 形 容 词 、 副 词 、 冠 词 等 可 以 与 名 词 、 动 词 构 成 “ 短 语 ” ， 丰 富句 子 要 表 达 的 思 想 内 容 而 这 些 ( z h è x i ē ) 短 语 的 构 成 也 是 有 特 定 规 律 的 ￿句法(jùfǎ)层次结构第34页/共63页第三十四页，共64页9.3￿结构句法(jùfǎ)模式识别——句法(jùfǎ)识别基本概念句法( jùfǎ)到图像理解的映射一座房子由内屋顶和墙面构成组成屋顶的几何图形，可以是三角形、四边形、圆形等，组成墙平面的几何图形也是由矩形、平行四边形(透视效果)等构成，至少一个墙面应该有门，而窗的高度不低于门等等进一步，还可以提出一些用来刻画构成一所房子的规则，如屋顶一定在墙面之上，且由墙面支撑一所房子这些规则就像构成一个句子的句法( jùfǎ)规则一样，是不能改变的如果将描述房子的规则(它构成—个房子的模式)存于计算机，而我们的任务是要在一张风景照片上去识别有无房子，那么就可按照片上所有景物的外形匹配是否符合房子的模式(房子构成规则)。

符合房子模式的就输出为“有房子”，否则，输出“无房子”￿第35页/共63页第三十五页，共64页9.3￿结构句法(jùfǎ)模式识别——句法(jùfǎ)识别基本概念句 法 模 式 识 别 是 将 一 个 复 杂 的 模 式 不 断 分 解 为 子 模 式 ， 最 终 得 到 ( d é ￿ d à o ) 最 简 单 的 子 模 式 ( 或 称 基 元 ) ， 借 助 于一 种 形 式 语 言 对 模 式 的 结 构 进 行 描 述 的 方 法 这 种 识 别 方 法 类 似 语 言 的 句 法 结 构 分 析 因 此 称 为 句 法 模 式 识 别 ￿句法(jùfǎ)模式识别系统模块图第36页/共63页第三十六页，共64页9.3￿结构(jiégòu)句法模式识别——串的句法识别句 法 识 别 的 基 本 思 路设 两 个 模 式 类 ω 1 ， ω 2 他 们 内 部 的 模 式 分 别 由 句 法 G 1 和 G 2 产 生 得 到 对 一 个 待 识 别 的 模 式 而 言 ， 其 模 式 识 别 问 题 转 化 为 判 断 该 模式 所 服 从 的 句 法 属 于 句 法 1 还 是 句 法 2 。

若 只 属 于 其 中 之 一 ， 则 完 成 识 别 ； 如 同 时 属 于 G 1 和 G 2 ， 则 判 定 为 无 法 识 别 ； 如 不 属 于 G 1 和G 2 的 任 何 一 个 ， 则 拒 绝 识 别 由 句 法 G 产 生 的 所 有 可 能 的 句 子 的 合 集 成 为 基 于 句 法 G 的 语 言 ， 记 为 L ( G ) ； 这 里 ( z h è l ǐ ) 句 子 对 应 于 符 号 串 ( 模 式 ) ， 语 言 L 对 应 于 模式 类 第37页/共63页第三十七页，共64页9.3￿结构句法(jùfǎ)模式识别——串的句法(jùfǎ)识别句 法 的 定 义 ( d ì n g y ì )句 法 是 描 述 模 式 类 中 模 式 符 号 连 接 规 则 的 集 合 ， 定 义 ( d ì n g y ì ) 如 下 ：其 中 ：N 为 有 限 变 量 集 合 ， 称 为 非 终 止 符 （ A , ￿ B , ￿ C ）T 为 有 限 常 量 集 合 ， 称 为 终 止 符 （ a , ￿ b , ￿ c ）混 合 符 号 串 用 （ ￿ α , ￿ β , ￿ γ ￿ … ） 表 示P 为 产 生 （ 造 句 ） 规 则 集 合 ， 称 为 产 生 式S 为 起 始 符 ， 属 于 集 合 N例 子 :N = { A , B , S } , T = { a , b , c } ,P = { S → a A , ￿ ￿ A → b A , ￿ A → b B , ￿ B → c }第38页/共63页第三十八页，共64页。

9.3￿结构句法模式识别(mó￿shì￿shí￿bié)——串的句法识别•语义信息对产生规则的约束•基于模式基元特征的句法(jùfǎ)分类：•程序文法：当前产生式结果会影响下一次产生式的选择•属性文法：产生式与符号都受到相应的附加属性的限制•基于产生式形式的句法(jùfǎ)分类•无限制文法：α → β•上下文敏感文法： α1Aα2→ α1βα2•上下文无关文法：A→ β•正则文法(有限状态文法)： A→aB，或A→b第39页/共63页第三十九页，共64页9.3￿结构句法(jùfǎ)模式识别——串的句法(jùfǎ)识别用 于 串 句 法 识 别 的 自 动 机自 动 机 是 一 个 五 元 集 合 ：其 中 ， Q 为 状 态 集 合 ； T 为 输 入 字 符 集 合 ； δ 为 Q × T 到 Q 的 映 射 关 系 的 集 合 ； q 0 为 起 始 状 态 ； F 为 终 止 ( 接 受 ) 状 态 ， 是 Q 的 子 集 当 一 个 字 符 串 输 入 自 动 机 最 后 ( z u ì h ò u ) 能 够 回 到 终 止 状 态 ， 称 为 该 字 符 串 被 自 动 机 所 识 别 或 接 受 。

例 子 ： Q = { q 0 , q 1 , q 2 } , T = { a , b } , ￿ F = { q 0 } ,￿ δ : ￿δ ( q 0 , ￿ a ) = { q 2 } , ￿ δ ( q 1 , ￿ a ) = { q 2 } , ￿ δ ( q 2 , ￿ a ) = { q 0 } , ￿δ ( q 0 , ￿ a ) = { q 1 } , ￿ δ ( q 1 , ￿ a ) = { q 0 } , ￿ δ ( q 2 , ￿ a ) = { q 1 } , ￿字 符 ： a b b a b b ￿ ￿ ￿ √字 符 ： a a b a b ￿ ￿ ￿ ￿ ￿ ×第40页/共63页第四十页，共64页9.3￿结构(jiégòu)句法模式识别——串的句法识别有 限 状 态 自 动 机 映 射 规 则 与 正 则 句 法 的 映 射G = { N , T , P, X 0 } ； 这 里 X 0 = S ， 为 起 始 符 ；N = { X 0 , ￿ X 1 , ￿ X 2 , … , X n } ， Q = { q 0 , ￿ q 1 , ￿ q 2 , … , q n , q n + 1 } ，q n + 1 为 终 止 状 态 。

对 应 关 系1 ） ￿ X i → a X j ∈ P ， 则 有 ￿ q j ∈ δ ( q i , ￿ a ) ,2 ） ￿ X i → a ∈ P ， 则 有 q n + 1 ∈ δ ( q i , ￿ a ) ,句 法 规 则 的 建 立 是 句 法 识 别 的 基 础 ， 遗 憾 的 是 ， 目 前 还 没 有 一 种 全 自 动 的 训 练 方 法 能 够 从 一 个 句 子 集 合 中 推 论( t u ī l ù n ) 出 全 部 合 理 的 文 法 大 部 分 情 况 下 ， 需 要 人 工 设 计 或 人 机 互 动 设 计 第41页/共63页第四十一页，共64页9.4￿￿智能(zhì￿nénɡ)模式识别方法——引言这 里 的 智 能 模 式 识 别 方 法 主 要 指 基 于 新 兴 的 智 能 计 算 手 段 或 其 他 软 计 算 方 法 设 计 的 基 于 统 计 信 息 与 学 习 能 力 ( n é n g l ì ) 的 智 能 识 别 方法 主 要 包 括 ：模 糊 模 式 识 别人 工 神 经 网 络 模 式 识 别统 计 学 习 理 论支 撑 （ 支 持 ） 向 量 机特 点不 确 定 性 ， 高 维 度 ， 极 大 数 据 库 或 极 小 数 据 库 ， 非 线 性第42页/共63页第四十二页，共64页。

9.4￿￿智能模式识别(mó￿shì￿shí￿bié)方法——模糊模式识别(mó￿shì￿shí￿bié)模 糊 模 式 识 别 是 模 糊 集 理 论 在 模 式 识 别 中 的 一 种 应 用 ， 其 基 本 思 想 是 用 模 式 对 模 式 类 的 隶 属 ( l ì s h ǔ ) 度 函 数 作 为 决 策 函 数 ， 该 方 法 适用 于 类 边 界 复 杂 ， 不 确 定 性 较 高 的 问 题基 本 概 念 ：1 ） 隶 属 ( l ì s h ǔ ) 度 函 数 μ A ( x ) ∈ [ 0 ￿ 1 ]2 ） 模 糊 集 ￿ A = { ( μ A ( x i ) , x i ) }3 ） 模 糊 集 的 运 算 ， 交 ， 并 ， 补4 ） 模 糊 度5 ） 模 糊 集 的 熵6 ） π 度第43页/共63页第四十三页，共64页9.4￿￿智能模式识别方法(fāngfǎ)——模糊模式识别常 用 的 模 糊 模 式 识 别 方 法模 糊 C 均 值 ( j ū n ￿ z h í ) 聚 类 法模 糊 k 近 邻基 于 句 法 结 构 的 模 糊 推 理模 糊 专 家 系 统第44页/共63页第四十四页，共64页。

9.4￿￿智能(zhì￿nénɡ)模式识别方法——人工神经网络基 本 概 念 ：神 经 元生 物 ( s h ē n g w ù ) 神 经 元人 工 神 经 元第45页/共63页第四十五页，共64页9.4￿￿智能模式识别(mó￿shì￿shí￿bié)方法——人工神经网络基 本 概 念权 值输 入 ( s h ū r ù ) 权 值输 出 权 值侧 向 权 值反 馈 权 值第46页/共63页第四十六页，共64页9.4￿￿智能模式识别(mó￿shì￿shí￿bié)方法——人工神经网络基 本 概 念学 习 算 法H e b b 规 则 [ 1 9 4 9 ] ： 若 神 经 元 C i 接 收 到 另 一 神 经 元 C j 的 输 出 ， 则 当 两 个 神 经 元 同 时 兴 奋 时 ， 从 C i 到 C j 的 突 触 权 值 就 得 到 加 强 其 中 ， ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ 是 对 第 i 个 输 入 权 值 的 修 正 ( x i ū z h è n g ) 量 ， η 是 学 习 速 度 系 数 ， 也 称 为 学 习 率几 乎 所 有 的 神 经 网 络 的 学 习 算 法 都 是 由 H e b b 规 则 衍 生 得 到 的第47页/共63页第四十七页，共64页。

9.4￿￿智能(zhì￿nénɡ)模式识别方法——人工神经网络常 见 的 人 工 神 经 网 络 类 型 ( l è i x í n g )前 馈 神 经 网 络感 知 器B P 网 络R B F 网 络S O M 网 络H o p f i e l d 网 络第48页/共63页第四十八页，共64页9.4￿￿智能模式识别(mó￿shì￿shí￿bié)方法——人工神经网络(BP)B P 神 经 网 络 是 反 向 传 播 ( B a c k — P r o p a g a t i o n ) 法 的 简 称 ￿ 其 实 质 是 把 一 组 样 本 输 入 、 输 出 问 题 转 化 为 一 个 非线 性 优 化 问 题 ， 并 通 过 梯 度 ( t ī ￿ d ù ) 算 法 利 用 迭 代 运 算 求 解 权 值 问 题 的 一 种 学 习 算 法 B P 网 络 模 型BP网络(wǎngluò)的神经元响应函数通常设为Sigmoid函数第49页/共63页第四十九页，共64页9.4￿￿智能(zhì￿nénɡ)模式识别方法——人工神经网络(BP)B P 算 法 的 学 习 过 程 由 正 向 传 播 和 反 向 传 播 组 成 。

在 正 向 传 播 过 程 中 ， 输 入 信 息 从 输 入 层 经 隐 含 层 逐 层 处 理 ， 并 传 向 输 出 层 每 一 层 神 经 元 的 状 态 只 影 响 下 一 层 神经 元 的 状 态 如 果 输 出 层 得 不 到 期 望 的 输 出 ， 则 转 入 反 向 传 播 ， 将 误 差 信 号 沿 原 来 的 连 接 通 道 返 回 ， 通 过 修 改 ( x i ū g ǎ i ) 各 层 神经 元 的 权 值 ， 使 得 误 差 信 号 最 小 B P 神 经 网 络 模 式 识 别 包 括 学 习 和 分 类 两 个 阶 段 1 ） 网 络 结 构 确 定 ： 层 数 ， 各 层 节 点 数 ，2 ） 样 本 数 据 及 控 制 参 数 输 入 ： 准 备 输 入 数 据 模 式 ， 神 经 元 响 应 参 数 ， 循 环 次 数 ， 分 类 精度 ， 学 习 率 等3 ） 网 络 权 值 初 始 化 4 ） 通 过 训 练 调 整 网 络 各 层 权 值 5 ） 判 断 学 习 过 程 是 否 完 毕 6 ） 对 待 识 别 模 式 进 行 分 类 识 别 。

第50页/共63页第五十页，共64页9.4￿￿智能(zhì￿nénɡ)模式识别方法——人工神经网络(BP)B P 网 络 的 应 用 实 例 ( s h í l ì ) — — 手 写 体 字 符 识 别用 B P 神 经 网 络 进 行 手 写 体 数 字 识 别 时 ， 整 个 过 程 由 输 入 环 节 、 预 处 理 环 节 、 识 别 环 节 等 三 部 分 组 成 1 ） 输 入 环 节 ： 通 过 扫 描 仪 获 得 字 符 的 数 字 图 像 文 件2 ） 预 处 理 ： 去 噪 、 标 准 化 、 特 征 提 取去 噪 ： 主 要 是 去 除 污 点 ， 与 无 意 义 的 线 段 形 状 噪 声标 准 化 ： 主 要 是 压 缩 变 换 ， 将 字 符 标 准 化 为 3 2 × 3 2 大 小 的 二 值 图 像 特 征 提 取 ： 通 过 对 图 像 分 块 扫 描 获 取 每 个 字 块 的 细 化 结 果 的 点 的 数 量 来 表 征 图 像第51页/共63页第五十一页，共64页9.4￿￿智能(zhì￿nénɡ)模式识别方法——人工神经网络(BP)特 征 提 取 算 法1 ） 将 ( 3 2 × 3 2 ) 的 正 方 形 点 阵 划 分 成 4 × 4 的 1 6 个 子 正 方 形 ， 每 个 正 方 形 都 是 ( 8 × 8 ) 点 阵 ， 对 每 个 子 正 方 形 ， 从左 至 右 ， 从 上 到 下 的 扫 描 ， 统 计 每 个 子 正 方 形 内 横 向 为 “ 1 ” 的 点 数 ［ 注 意 ： 若 ( x , y 1 ) = 1 ， ( x , y 2 ) = 1 ，( x , y 3 ) = １ … … ； ￿ y 1 < y 2 < y 3 … … < y 8 ； 则 此 y 方 向 只 记 一 个 点 数 ] ￿ S i ( 0 ≤ S i ≤ 8 , 0 ≤ i ≤ 1 5 ) ， 这 一 步 对 应( d u ì y ì n g ) 于 细 化 过 程 。

2 ） 将 得 到 的 每 个 S i 再 处 理 成 ： X i = S i / 8 ( 0 ≤ S i ≤ 8 ) ， ( 0 ≤ X i ≤ 8 ) ， 0 ≤ i ≤ 1 5 ) ， 这 一 步 对 应 ( d u ì y ì n g ) 于 特 征抽 取 ￿第52页/共63页第五十二页，共64页9.4￿￿智能(zhì￿nénɡ)模式识别方法——人工神经网络(BP)B P 网 络 的 应 用 实 例 — — 手 写 体 字 符 ( z ì ￿ f ú ) 识 别识 别 环 节1 ） 网 络 结 构 ： 三 层 ， 神 经 元 数 量 [ 1 6 , ￿ 3 , ￿ 1 0 ] 输 入 层 N i ￿ = 1 6 对 应 输 入 模 式 向 量 的 维 度 ；输 出 层 N o = 1 0 对 应 0 ~ 9 共 1 0 类 字 符 ( z ì ￿ f ú ) ；隐 含 层 N h = 3 ， 由 经 验 公 式 得 到 ， N h = l o g 2 ￿ ( N o ) ￿ = l o g 2 1 0 ≈ 3 ;2 ） 神 经 元 及 参 数 设 置神 经 元 响 应 函 数 ：规 定 当 y i ≥ 0 . 5 ( i = 0 , 1 … … 9 ) ￿ 且 y i ￿ > ￿ y j ￿ ( i ￿ ≠ ￿ j ) 时 ， 则 y i 为 有 效 输 出 结 果 。

￿3 ） 训 练用 1 0 0 个 样 本 ， 根 据 B P 算 法 进 行 训 练 ， 当 输 出 误 差 小 于 阈 值 δ 时 停 止第53页/共63页第五十三页，共64页9.4￿￿智能模式识别(mó￿shì￿shí￿bié)方法——统计学习理论机 器 学 习 的 基 本 概 念根 据 给 定 的 训 练 样 本 对 系 统 的 输 入 输 出 关 系 进 行 估 计 ， 进 而 得 到 对 其 他 未 知 输 出 的 预 测 理 想 ( l ǐ x i ǎ n g ) 原 则 ： 预 测 的 期 望 风 险 最 小 化实 际 原 则 ： 预 测 的 经 验 风 险 最 小 化第54页/共63页第五十四页，共64页9.4￿￿智能模式识别方法——统计(tǒngjì)学习理论传统的统计学的缺陷主要体现在：在有限样本(yàngběn)条件下：1）经验风险最小不等于期望风险最小2）学习机的复杂性不但取决于系统，而且要适应有限的学习样本(yàngběn)统计学习理论的核心内容经验风险最小化原则下的统计学习一致性的条件；该条件下的统计学习方法的推广性的界的结论；在这些界的基础上建立小样本(yàngběn)归纳推理原则；实现这些原则的实际可行的方法；第55页/共63页第五十五页，共64页。

9.4￿￿智能(zhì￿nénɡ)模式识别方法——最优分类平面基本概念训练样本集：{xi￿,￿yi},￿yi∈{-1，1},￿i=1,2,…,￿l分类平面H的方程支持向量：距离分类平面最近的训练样本点的向量支持平面：经过支持向量点与分类平面平行的平面（H1，H2）分类间隔：分类平两侧(liǎnɡ￿cè)的支持平面的距离线性最优分类面：在对有限训练样本分类正确的情况下，使得分类间隔最大的分类平面平面第56页/共63页第五十六页，共64页9.4￿￿智能模式识别方法——最优分类(fēn￿lèi)平面基 本 思 路对 支 持 平 面 和 分 类 平 面 进 行 归 一 化 使 其 满 足 :可 以 推 导 证 明 ， 此 时 ( c ǐ ￿ s h í ) 的 分 类 间 隔 为 2 / | | w | | ， 因 此 寻 找 最 优 分 类 面 的 问 题 可 以 转 化 为 以 下 的 带 有 约 束 条 件 的 最 小 化 问 题 ：通 过 建 立 L a g r a n g e 优 化 函 数 ， 经 推 导 可 以 得 到 下 面 的 结 论 ， 即 最 优 分 类 函 数 为 ：利用样本对该函数进行训练，找到使得所有样本分类(fēn lèi)正确的最优的a*，b*第57页/共63页第五十七页，共64页。

9.4￿￿智能(zhì￿nénɡ)模式识别方法——支持向量机支 持 向 量 机 是 对 最 优 分 类 平 面 法 在 处 理 非 线 性 问 题 时 的 一 种 延 伸 和 深 化 支 持 向 量 机 利 用 一 个 内 积 函 数 ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ 替 换 最 优 分 类 平 面 法 中 的 决 策 方 程 里 的 ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ￿ ， 进 而 ( j ì n ￿ é r )将决 策 方 程 变 形 为 ：需 要 注 意 的 是 ， 在 推 导 过 程 可 以 知 道 ， 非 支 持 向 量 点 x i 对 应 的 参 数 a i 为 0 ， 也 就 是 说 决 策 方 程 将 仅 由 支 持 向 量 点决 定 即 算 法 复 杂 度 仅 由 支 持 向 量 点 所 决 定 第58页/共63页第五十八页，共64页9.4￿￿智能模式识别(mó￿shì￿shí￿bié)方法——支持向量机内 积 函 数 的 选 择 ( x u ǎ n z é )多 项 式 形 式 ：核 函 数 形 式 ：S 形 函 数 形 式 ：支持向量(xiàngliàng)机的令一大优势是识别率对于内积函数的选择并不十分敏感。

这节省了很多模型设计方面的工作第59页/共63页第五十九页，共64页9.4￿￿智能模式识别方法——支持(zhīchí)向量机支 持 ( z h ī c h í ) 向 量 机 在 图 像 处 理 中 的 应 用支 持 ( z h ī c h í ) 矢 量 机 算 法 对 于 复 杂 图 像 ， 即 信 息 包 含 较 多 的 图 像 具 有 优 势 ， 更 能 把 握 待 分 地 物 的 特 征 ， 适 合 于 遥 感 图 像 分 类 ￿ （a）原始图像 （b）SVM算法 灰度图像及分类(fēn lèi)结果图第60页/共63页第六十页，共64页9.4￿￿智能模式识别方法——支持(zhīchí)向量机￿￿￿￿￿￿￿（a）原始图像(tú￿xiànɡ)￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿（b）SVM算法￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿RGB彩色图像(tú￿xiànɡ)及分类结果图第61页/共63页第六十一页，共64页第九章￿图像匹配与识别(shíbié)——总结篇9 . 1 ￿ 基 本 概 念模 式 ， 模 式 类 ， 模 式 识 别 系 统9 . 2 ￿ 基 于 统 计 决 策 的 模 式 识 别匹 配 法 ， 贝 叶 斯 分 类 器 ， 线 性 分 类 器 ， k 近 邻 分 类 器9 . 3 ￿ 基 于 结 构 句 法 ( j ù f ǎ ) 的 模 式 识 别形 状 数 匹 配 ， 串 匹 配 ， 串 句 法 ( j ù f ǎ ) 识 别9 . 4 ￿ 基 于 智 能 计 算 方 法 的 模 式 识 别模 糊 模 式 识 别 ， 人 工 神 经 网 络 ，统 计 学 习 理 论 ， 支 撑 向 量 机第62页/共63页第六十二页，共64页。

感谢您的欣赏(xīnshǎng)第63页/共63页第六十三页，共64页内容(nèiróng)总结9.1 基本概念相关系数越大，相似性越大当i满足以下(yǐxià)条件时，x被分类为模式类ωi大部分情况下，需要人工设计或人机互动设计BP算法的学习过程由正向传播和反向传播组成标准化：主要是压缩变换，将字符标准化为32×32大小的二值图像y1