《图像匹配与识别实用教案》由会员分享，可在线阅读，更多相关《图像匹配与识别实用教案（64页珍藏版）》请在金锄头文库上搜索。
1、9.1基本概念模式，模式类，模式识别系统9.2基于统计(tngj)决策的模式识别匹配法，贝叶斯分类器，线性分类器，k近邻分类器9.3基于结构句法的模式识别形状数匹配，串匹配，串句法识别9.4基于智能计算方法的模式识别模糊模式识别，人工神经网络，统计(tngj)学习理论，支撑向量机第九章图像匹配与识别(shbi)第1页/共63页第一页，共64页。9.1基本概念引言(ynyn)模式识别是一切生物的认知能力的基础。在图像处理以及计算机视觉技术中，模式识别是实现(shxin)图像理解的必由之路。在人工智能领域，模式识别是一切基于传感信息的智能技术的必要模块。第2页/共63页第二页，共64页。9.1基本
2、概念模式(msh)模 式 的 广 义 定 义存 在 于 时 间 和 空 间 中 的 可 观 察 ， 可 区 分 的 事 物 的 信 息 形 式模 式 的 狭 义 定 义用 于 进 行 事 物 分 类 的 特 征 描 绘 ( m i o h u ) 子 的 有 序 组 合 。图 像 信 号 中 的 模 式能 够 用 以 区 分 物 体 的 光 学 信 息 的 有 效 表 达 形 式第3页/共63页第三页，共64页。9.1基本概念模式(msh)模 式 的 数 学 表 达 形 式常 用 的 三 种 ： 矢 量 、 串 和 树例 子 ： I r i s 数 据 库 ( F i s h e r , 1
3、9 3 6 )I r i s 数 据 库 是 对 鸢 尾 属 的 三 种 花 的 数 据 测 量 结 果 ， 其 中 每 朵 花 的 模 式 由 4 个 数 据 表 示 ， 分 别 是 萼 片 ( p i n ) 长 度 、 萼 片 ( p i n ) 宽度 、 花 瓣 长 度 和 花 瓣 宽 度 ， 这 样 一 朵 花 的 模 式 可 以 用 一 个 4 维 矢 量 来 表 示 。第4页/共63页第四页，共64页。9.1基本概念模式(msh)类模式类是具有共同性质的模式族，模式类是对事物分类结果的一种变相描述，它反映了同类(tngli)事物的相似性与不同事物的区别性。第5页/共63页第五页，
4、共64页。9.1基本概念模式分类(fnli)与识别将 不 同 的 模 式 通 过 归 纳 的 方 法 分 成 不 同 的 模 式 类 即 为 模 式 分 类 ； 对 于 一 个 未 知 其 类 别 的 模 式 ， 找 到 它 所 从 属 ( c n g s h ) 的 模 式 类 即为 模 式 识 别 （ 狭 义 ） 。模 式 识 别 ( 广 义 ) 的 主 要 内 容（ 1 ） 特 征 提 取 和 选 择 （ 建 立 模 式 ）（ 2 ） 决 策 分 类 （ 建 立 模 式 到 模 式 类 的 映 射 ）第6页/共63页第六页，共64页。9.1基本概念模式识别(mshshbi)系统模 式 识
5、 别 的 两 个 基 本 过 程 ( g u c h n g ) ： 设 计 与 实 现模 式 识 别 系 统 的 基 本 构 成信息获取数据预处理特征提取和选择分类器设计分类决策训练过程输出结果第7页/共63页第七页，共64页。9.1基本概念模式识别(mshshbi)的分类两 种 基 本 的 模 式 识 别 方 法统 计 识 别 方 法 ：建 立 特 征 ( t z h n g ) 空 间 ， 利 用 统 计 决 策 理 论贝 叶 斯 决 策 ， 判 别 函 数 法 ， k 近 邻 法 ， 风 险 最 小 化 ， 非 线 性 映 射 ， 特 征 ( t z h n g ) 分 析 ， 主 元
6、 分 析 等结 构 （ 句 法 ） 识 别 方 法 ：着 眼 于 对 待 识 别 对 象 的 结 构 特 征 ( t z h n g ) 的 描 述 。 将 一 个 识 别 对 象 看 成 是 一 个 语 言 结 构 ， 例 如 一 个 句 子 是 由 单 词 和 标 点 符 号 按 照一 定 的 语 法 规 则 生 成 的 ， 同 样 ， 一 幅 图 像 是 由 点 、 线 、 面 等 基 本 元 素 按 照 一 定 的 规 则 构 成 的 。 第8页/共63页第八页，共64页。9.1基本概念模式识别(mshshbi)的分类统 计 识 别 方 法 中 的 新 发 展模 糊 模 式 识 别 ：
7、 以 模 糊 数 学 ( f u z z y m a t h ) 为 理 论 基 础 ， 将 计 算 机 中 常 用 的 二 值 逻 辑 转 化 为 连 续 逻 辑 。 模 糊 识 别 的 结 果 是 用 被 识 别 对象 隶 属 于 某 一 类 别 的 程 度 。基 于 人 工 神 经 网 络 的 模 式 识 别 ： 人 工 神 经 网 络 研 究 源 于 对 生 物 神 经 系 统 的 研 究 。 它 将 若 干 个 处 理 单 元 ( 即 神 经 元 ) 通 过 一 定 的 互 连 模 型连 结 成 一 个 网 络 ， 这 个 网 络 通 过 一 定 的 机 制 ( 如 误 差 后 向
8、传 播 ) 可 以 模 仿 人 的 神 经 系 统 的 动 作 过 程 ， 以 达 到 识 别 分 类 的 目 的 。统 计 学 习 理 论 与 支 撑 向 量 机 ： 将 统 计 模 式 识 别 看 作 是 机 器 学 习 理 论 的 一 个 特 例 ( t l ) ， 通 过 系 统 的 自 主 学 习 建 立 模 式 分 类 规 则 ， 其 中的 支 撑 向 量 机 是 目 前 研 究 的 热 点 ， 主 要 解 决 小 样 本 ， 非 线 性 以 及 高 维 度 的 模 式 识 别 问 题 。第9页/共63页第九页，共64页。9.1基本(jbn)概念模式识别的基本(jbn)问题模 式
9、类 的 紧 致 性对 比 于 图 形 学 中 的 凸 集 概 念模 式 的 相 似 性非 负 性 、 最 大 性 、 对 称 性 、 单 调 性 。空 间 距 离 是 度 量 模 式 相 似 性 的 最 佳 手 段 之 一 。特 征 与 分 类 的 关 系面 向 模 式 识 别 ( m s h s h b i ) 的 特 征 的 产 生 应 考 虑 到 分 类 的 需 要 ， 同 一 个 目 标 在 不 同 的 分 类 需 求 下 的 特 征 可 能 是 不 同 的第10页/共63页第十页，共64页。9.1基本概念模式识别(mshshbi)系统的应用模 式 识 别 系 统 在 图 像 处 理
10、领 域 的 应 用 ( 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、医 学 诊 断第11页/共63页第十一页，共64页。9.2统计(tngj)决策模式识别基本概念统 计 决 策 模 式 识 别 方 法设 模 式 的 数 学 ( 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 的 边 界 称 为 决 策 边
12、界 b i j ， 由 于 该 边 界 通 常 以 高 维 空 间 中 的 超 曲 面 形 式 存 在 ， 因 此 也 被 称 为 决 策 平 面 。 b i j 由 符合 以 下 条 件 的 点 组 成 。统计(tngj)决策方法的关键是找到合适决策函数第12页/共63页第十二页，共64页。9.2统计决策(juc)模式识别匹配匹 配 方 法 ( f n g f ) 的 基 本 思 路 是 为 每 一 个 模 式 类 建 立 一 个 模 板 ， 将 衡 量 待 识 别 模 式 与 模 板 的 相 似 性 作 为 该 模 式 类 的 决 策 方 程 。最 常 用 的 模 板 产 生 方 法 (
13、f n g f ) 就 是 计 算 每 一 个 模 式 类 内 部 所 有 训 练 模 式 的 均 值 。常 用 的 匹 配 方 法 ( f n g f )最 小 距 离 匹 配 法最 大 相 关 性 匹 配 法第13页/共63页第十三页，共64页。9.2统计决策模式识别(mshshbi)匹配最 小 距 离 匹 配 法 （ 又 称 最 小 距 离 分 类 器 ）用 高 维 空 间 中 两 点 之 间 的 欧 氏 距 离 衡 量 待 识 别 模 式 与 每 个 模 式 类 模 板 的 相 似 性模 式 到 模 板 的 欧 氏 距 离 越 小 ， 则 相 似 性 越 大 ， 对 应 的 决 策 (
14、 j u c ) 方 程 的 值 也 越 大 。第14页/共63页第十四页，共64页。9.2统计决策模式识别(mshshbi)匹配最小距离(jl)匹配法示意图第15页/共63页第十五页，共64页。9.2统计决策模式识别(mshshbi)匹配最大相关性匹配法利用待识别模式与模板(mbn)的归一化相关系数作为其相似性度量二维情况下：归一化相关性衡量的是两个矢量的夹角余弦值，与矢量长度无关。相关系数越大，相似性越大。第16页/共63页第十六页，共64页。9.2统计(tngj)决策模式识别匹配基 于 模 板 窗 口 的 匹 配 模 式 识 别 方 法将 模 式 类 的 模 板 作 为 一 个 操 作
15、窗 口 ， 令 其 在 包 含 待 识 别 目 标 的 图 像 上 滑 动 ， 并 在 每 个 位 置 上 计 算 模 板 与 对 应 图 像 区 域 的 相 似 性 ， 得 到相 似 性 最 大 的 某 个 点 ， 若 该 点 相 似 性 大 于 设 定 的 阈 值 ， 则 认 为 该 点 对 应 的 区 域 内 包 含 了 属 于 ( s h y ) 该 模 式 类 的 某 个 模 式基 于 模 板 窗 口 的 匹 配 方 法 的 实 际 上 同 时 包 含 了 图 像 分 析 ， 特 征 提 取 与 模 式 识 别 的 内 容 ， 是 基 于 图 像 这 一 信 号 模 式 所 特 有
16、的 一 种 模 式 识别 算 法 。第17页/共63页第十七页，共64页。9.2统计(tngj)决策模式识别匹配模板窗口操作步骤下图给出了模板匹配的示意图，其中(qzhng)假设原图像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
17、ngj)决策模式识别匹配基于相关性的模板(mbn)窗口操作示例（a a）图像；）图像；（b b）子图；）子图；（c c） （a a）和（）和（b b）的相关系数。当子图和原图中的字母）的相关系数。当子图和原图中的字母(zm)“D”(zm)“D”一致时，一致时， （c c） 中出现最高值（亮点）；中出现最高值（亮点）；第19页/共63页第十九页，共64页。9.2统计决策(juc)模式识别匹配用 归 一 化 互 相 关 ( x i n g g u n ) 求 匹 配 的 计 算 工 作 量 非 常 大 ， 因 为 模 板 要 在 ( M J 1 ) ( N K 1 ) 个 参 考 位 置 上 做
18、相 关 ( x i n g g u n ) 计 算 ， 其 中 ， 除 最 佳 匹 配 点 外 ， 其 余 做 的 都 是 无 效 运 算 ， 所 以 有 必 要 对 其 进 行 改 进 ， 以 提 高 运 算 速 度 。常 用 的 方 法 有 ： 序 贯 相 似 性 检 测 算 法 、 幅 度 排 序 相 关 ( x i n g g u n ) 算 法 、 F F T 相 关( x i n g g u n ) 算 法 、 分 层 搜 索 序 贯 判 决 算 法 等 。模 板 窗 口 匹 配 的 主 要 局 限 性 在 于 它 只 能 进 行 平 行 移 动 ， 如 原 图 像 中 要 匹 配
19、 的 目 标 发 生 旋 转 或 大 小 变化 ， 该 算 法 无 效 。 另 外 ， 如 原 图 像 中 要 匹 配 的 目 标 只 有 部 分 可 见 ， 该 算 法 也 无 法 完 成 匹 配 。 （ 即 模板 窗 口 匹 配 法 只 有 平 移 不 变 性 ， 不 具 备 尺 度 和 旋 转 不 变 性 ）第20页/共63页第二十页，共64页。9.2统计决策(juc)模式识别最优统计分类器最 优 统 计 分 类 是 一 种 基 于 概 率 ( g i l ) 的 分 类 器 ， 其 基 本 思 想 是 选 择 错 分 损 失 最 小 的 模 式 类 作 为 当 前 模 式 的 分 类
20、结 果 ， 对 应 的 决 策 方程 与 错 误 分 类 损 失 函 数 成 反 比 。将 模 式 x 分 给 模 式 类 j 的 平 均 损 失 为 ：当 i 满 足 以 下 条 件 时 ， x 被 分 类 为 模 式 类 i 。第21页/共63页第二十一页，共64页。9.2统计(tngj)决策模式识别最优统计(tngj)分类器当 各 类 的 误 分 损 失 均 等 时 ：当 每 个 模 式 类 的 误 分 损 失 均 等 时 ， 最 优 统 计 分 类 器 的 决 策 方 程 ( f n g c h n g ) 即 为 模 式 与 模 式 类 的 联 合 概 率第22页/共63页第二十二页
21、，共64页。9.2统计(tngj)决策模式识别最优统计(tngj)分类器Gaussian模式(msh)分类的贝叶斯分类器假设每一个模式(msh)类内的模式(msh)概率分布服从高斯分布，则最优统计分类器第23页/共63页第二十三页，共64页。9.2统计决策(juc)模式识别最优统计分类器G a u s s i a n 模 式 分 类 的 贝 叶 斯 分 类 器设 每 个 模 式 类 自 身 ( z s h n ) 概 率 相 同 ， 且 每 个 模 式 类 的 协 方 差 矩 阵 为 单 位 阵 ， 则 决 策 方 程 等 价 于 ：即 等 价 于 最 小 距 离 分 类 器 ， 也 就 是
22、说 ， 最 小 距 离 分 类 器 是 高 斯 模 型 下 的 最 优 分 类 器 的 一 个 特 例 。基 于 高 斯 模 型 的 贝 叶 斯 分 类 器 为 我 们 估 计 每 个 模 式 类 的 概 率 密 度 函 数 提 供 了 平 台 ， 将 概 率 密 度 函 数 构 建 问 题 转 换 为 参 数 估 计 问 题 。第24页/共63页第二十四页，共64页。9.2统计决策(juc)模式识别最优统计分类器高 斯 贝 叶 斯 分 类 器 应 用 实 例对 遥 感 ( y o g n ) 多 光 谱 图 像 进 行 处 理 ，1 ） 获 取 训 练 模 式 集 ， 可 采 用 交 互 方
23、 式 在 图 像 中 不 同 区 域 选 择 不 同 地 理 类 型 ， 并 根 据 对 应 的 像 素 的 多 光谱 灰 度 建 立 训 练 模 式 向 量 x ， x 的 维 度 与 多 光 谱 的 子 代 数 相 同 。2 ） 根 据 训 练 模 式 集 获 取 每 个 模 式 类 的 均 值 与 方 差 。3 ） 根 据 高 斯 贝 叶 斯 分 类 器 ， 对 图 像 中 每 个 像 素 对 应 的 模 式 进 行 分 类 。第25页/共63页第二十五页，共64页。9.2统计(tngj)决策模式识别最优统计(tngj)分类器高斯贝叶斯分类(fn li)器分类(fn li)结果第26页/
24、共63页第二十六页，共64页。9.2统计(tngj)决策模式识别线性分类器线 性 分 类 器 就 是 采 用 线 性 决 策 ( j u c )函 数 的 分 类 器 ， 其 决 策 ( j u c )边 界 是 高 维 空 间 中 的 一 个 超 平 面 。 其 表 达式 为 ：决 策 ( j u c )分 类 过 程 可 以 由 下 式 判 定 ：如 何 得 到 决 策 ( j u c )函 数 的 参 数 w i ？通 过 学 习 ， 即 选 择 一 部 分 训 练 样 本 ， 并 基 于 分 类 正 确 的 约 束 条 件 建 立 一 个 评 价 函 数 （ 通 常 两 类 的 区 分
25、 情 况 ） ， 并在 该 约 束 条 件 下 对 评 价 函 数 进 行 优 化 ， 得 到 最 优 的 参 数 。第27页/共63页第二十七页，共64页。9.2统计决策模式识别(mshshbi)k近邻分类器基 本 思 想选 择 一 部 分 训 练 样 本 ， 并 记 录 每 个 样 本 的 类 别 标 号 。计 算 待 识 别 样 本 到 所 有 训 练 样 本 的 距 离 （ 绝 对 距 离 ， 欧 式 距 离 或 马 氏 距 离 ） ， 找 到 距 离 待 识 别 样 本 最 近 的 k 个 训 练 样 本 。对 照 k 个 最 近 邻 样 本 的 模 式 类 ， 找 出 其 中 占
26、比 例 最 大 的 模 式 类 对 应 的 类 别 标 号 ， 如 出 现 两 个 模 式 类 所 占 比 例 相 同 ， 则 进 一 步 参 考 每 类 内包 含 的 样 本 到 待 识 别 样 本 的 最 近 距 离 作 为 附 件 决 策 条 件 。根 据 占 比 例 最 大 并 且 距 离 最 近 的 类 别 标 号 ， 将 待 识 别 样 本 判 决 为 该 类 别 标 号 对 应 的 模 式 类 。特 点K 近 邻 法 效 果 一 般 较 好 ， 并 且 提 供 了 相 当 多 的 算 法 ( s u n f ) 改 进 可 能 性 ， 但 计 算 量 极 大 。第28页/共63页
27、第二十八页，共64页。9.2统计决策(juc)模式识别k近邻分类器第29页/共63页第二十九页，共64页。9.3结构(jigu)句法模式识别引言统 计 决 策 模 式 识 别 方 法 不 考 虑 模 式 本 身 的 结 构 或 语 法 特 征 ， 而 只 把 模 式 看 做 一 个 高 维 空 间 中 点 。结 构 句 法 模 式 识 别 方 法 则 将 模 式 看 做 是 一 个 结 构 体 ， 模 式 涉 及 的 每 一 个 特 征 都 有 各 自 的 作 用 和 所 处 的 位 置 。 因 此 特 征 的 组 合 形 式( x n g s h ) 对 于 结 构 句 法 模 式 识 别
28、方 法 而 言 ， 是 非 常 重 要 的 。结 构 句 法 模 式 识 别 方 法 需 要 特 别 重 视 每 种 模 式 的 结 构 特 点 ， 不 同 结 构 的 模 式 ， 可 能 需 要 不 同 的 模 式 识 别 方 法 进 行 处 理 。第30页/共63页第三十页，共64页。9.3结构句法模式识别(mshshbi)形状数匹配目 标 a 和 目 标 b 的 形 状 的 相 似 度 k 被 定 义 为 使 得 这 两 个 目 标 的 形 状 数 相 同 的 最 大 阶 数 。此 时 ( c s h ) ， a 和 b 的 形 状 距 离 可 以 为 相 似 度 k 的 倒 数第31页
29、/共63页第三十一页，共64页。9.3结构句法(jf)模式识别形状数匹配第32页/共63页第三十二页，共64页。9.3结构(jigu)句法模式识别串匹配两 个 目 标 的 边 界 被 编 码 成 字 符 串 ， 分 别 表 示 为 a 和 b ， 若 a k = b k ， 则 成 两 个 字 符 串 在 第 k 位 上 匹 配 ， 两 个 字 符 串 之间 发 生 匹 配 的 次 数 ， 称 为 匹 配 数 目 ， 记 为 。 则 无 法 匹 配 的 字 符 数 目 为 ：判 断 ( p n d u n ) 字 符 串 相 似 性 的 方 法 即 定 义 相 似 性 R 为 ：当 两 个 字
30、 符 串 完 全 一 致 时 ， R = ， 当 两 个 字 符 串 之 间 不 发 生 匹 配 时 ， R = 0 ；第33页/共63页第三十三页，共64页。9.3结构句法(jf)模式识别句法(jf)识别基本概念所 谓 句 法 ， 是 描 述 语 言 规 则 的 一 种 法 则 。 一 个 完 整 的 句 子 一 定 是 主 语 + 谓 语 或 主 语 + 谓 语 + 宾 语 ( 或 表 语 ) 的 基 本 结构 构 成 。 一 种 特 定 的 语 言 ， 定 类 型 的 句 子 之 间 是 有 定 的 结 构 顺 序 的 。 无 规 则 的 任 意 组 合 ， 必 然 达 不 到 正 确
31、的 思 想 交 流 。 形 容 词 、 副 词 、 冠 词 等 可 以 与 名 词 、 动 词 构 成 “ 短 语 ” ， 丰 富句 子 要 表 达 的 思 想 内 容 。 而 这 些 ( z h x i ) 短 语 的 构 成 也 是 有 特 定 规 律 的 。 句法(jf)层次结构第34页/共63页第三十四页，共64页。9.3结构句法(jf)模式识别句法(jf)识别基本概念句法( jf)到图像理解的映射一座房子由内屋顶和墙面构成。组成屋顶的几何图形，可以是三角形、四边形、圆形等，组成墙平面的几何图形也是由矩形、平行四边形(透视效果)等构成，至少一个墙面应该有门，而窗的高度不低于门等等。进一
32、步，还可以提出一些用来刻画构成一所房子的规则，如屋顶一定在墙面之上，且由墙面支撑。一所房子这些规则就像构成一个句子的句法( jf)规则一样，是不能改变的。如果将描述房子的规则(它构成个房子的模式)存于计算机，而我们的任务是要在一张风景照片上去识别有无房子，那么就可按照片上所有景物的外形匹配是否符合房子的模式(房子构成规则)。符合房子模式的就输出为“有房子”，否则，输出“无房子”。第35页/共63页第三十五页，共64页。9.3结构句法(jf)模式识别句法(jf)识别基本概念句 法 模 式 识 别 是 将 一 个 复 杂 的 模 式 不 断 分 解 为 子 模 式 ， 最 终 得 到 ( d d
33、o ) 最 简 单 的 子 模 式 ( 或 称 基 元 ) ， 借 助 于一 种 形 式 语 言 对 模 式 的 结 构 进 行 描 述 的 方 法 。 这 种 识 别 方 法 类 似 语 言 的 句 法 结 构 分 析 。 因 此 称 为 句 法 模 式 识 别 。 句法(jf)模式识别系统模块图第36页/共63页第三十六页，共64页。9.3结构(jigu)句法模式识别串的句法识别句 法 识 别 的 基 本 思 路设 两 个 模 式 类 1 ， 2 。 他 们 内 部 的 模 式 分 别 由 句 法 G 1 和 G 2 产 生 得 到 。 对 一 个 待 识 别 的 模 式 而 言 ， 其
34、模 式 识 别 问 题 转 化 为 判 断 该 模式 所 服 从 的 句 法 属 于 句 法 1 还 是 句 法 2 。 若 只 属 于 其 中 之 一 ， 则 完 成 识 别 ； 如 同 时 属 于 G 1 和 G 2 ， 则 判 定 为 无 法 识 别 ； 如 不 属 于 G 1 和G 2 的 任 何 一 个 ， 则 拒 绝 识 别 。由 句 法 G 产 生 的 所 有 可 能 的 句 子 的 合 集 成 为 基 于 句 法 G 的 语 言 ， 记 为 L ( G ) ； 这 里 ( z h l ) 句 子 对 应 于 符 号 串 ( 模 式 ) ， 语 言 L 对 应 于 模式 类 。第
35、37页/共63页第三十七页，共64页。9.3结构句法(jf)模式识别串的句法(jf)识别句 法 的 定 义 ( d n g y )句 法 是 描 述 模 式 类 中 模 式 符 号 连 接 规 则 的 集 合 ， 定 义 ( d n g y ) 如 下 ：其 中 ：N 为 有 限 变 量 集 合 ， 称 为 非 终 止 符 （ A , B , C ）T 为 有 限 常 量 集 合 ， 称 为 终 止 符 （ a , b , c ）混 合 符 号 串 用 （ , , ） 表 示P 为 产 生 （ 造 句 ） 规 则 集 合 ， 称 为 产 生 式S 为 起 始 符 ， 属 于 集 合 N例 子
36、: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结构句法模式识别(mshshbi)串的句法识别语义信息对产生规则的约束基于模式基元特征的句法(jf)分类：程序文法：当前产生式结果会影响下一次产生式的选择。属性文法：产生式与符号都受到相应的附加属性的限制。基于产生式形式的句法(jf)分类无限制文法： 上下文敏感文法： 1A2 12上下文无关文法：A 正则文法(有限状态文法)： AaB，或Ab第39页/共63页第三十九页，共64页。9.3结构句法(jf)模式识别串的句法(j
37、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 ,
38、: ( 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结构(jigu)句法模式识别串的句法识别有 限 状 态 自 动 机 映 射 规 则 与 正 则 句 法 的 映 射G = N , T , P, X 0 ； 这 里 X 0 = S ， 为 起 始 符 ；N = X 0 , X 1 , X 2 ,
39、 , 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 ) 出 全 部 合 理 的 文 法 。 大 部 分 情 况 下 ， 需 要 人 工 设
40、 计 或 人 机 互 动 设 计 。第41页/共63页第四十一页，共64页。9.4智能(zhnn)模式识别方法引言这 里 的 智 能 模 式 识 别 方 法 主 要 指 基 于 新 兴 的 智 能 计 算 手 段 或 其 他 软 计 算 方 法 设 计 的 基 于 统 计 信 息 与 学 习 能 力 ( n n g l ) 的 智 能 识 别 方法 。主 要 包 括 ：模 糊 模 式 识 别人 工 神 经 网 络 模 式 识 别统 计 学 习 理 论支 撑 （ 支 持 ） 向 量 机特 点不 确 定 性 ， 高 维 度 ， 极 大 数 据 库 或 极 小 数 据 库 ， 非 线 性第42页/共
41、63页第四十二页，共64页。9.4智能模式识别(mshshbi)方法模糊模式识别(mshshbi)模 糊 模 式 识 别 是 模 糊 集 理 论 在 模 式 识 别 中 的 一 种 应 用 ， 其 基 本 思 想 是 用 模 式 对 模 式 类 的 隶 属 ( l s h ) 度 函 数 作 为 决 策 函 数 ， 该 方 法 适用 于 类 边 界 复 杂 ， 不 确 定 性 较 高 的 问 题基 本 概 念 ：1 ） 隶 属 ( l s h ) 度 函 数 A ( x ) 0 1 2 ） 模 糊 集 A = ( A ( x i ) , x i ) 3 ） 模 糊 集 的 运 算 ， 交 ，
42、并 ， 补4 ） 模 糊 度5 ） 模 糊 集 的 熵6 ） 度第43页/共63页第四十三页，共64页。9.4智能模式识别方法(fngf)模糊模式识别常 用 的 模 糊 模 式 识 别 方 法模 糊 C 均 值 ( j n z h ) 聚 类 法模 糊 k 近 邻基 于 句 法 结 构 的 模 糊 推 理模 糊 专 家 系 统第44页/共63页第四十四页，共64页。9.4智能(zhnn)模式识别方法人工神经网络基 本 概 念 ：神 经 元生 物 ( s h n g w ) 神 经 元人 工 神 经 元第45页/共63页第四十五页，共64页。9.4智能模式识别(mshshbi)方法人工神经网络基
43、 本 概 念权 值输 入 ( s h r ) 权 值输 出 权 值侧 向 权 值反 馈 权 值第46页/共63页第四十六页，共64页。9.4智能模式识别(mshshbi)方法人工神经网络基 本 概 念学 习 算 法H e b b 规 则 1 9 4 9 ： 若 神 经 元 C i 接 收 到 另 一 神 经 元 C j 的 输 出 ， 则 当 两 个 神 经 元 同 时 兴 奋 时 ， 从 C i 到 C j 的 突 触 权 值 就 得 到 加 强 。其 中 ， 是 对 第 i 个 输 入 权 值 的 修 正 ( x i z h n g ) 量 ， 是 学 习 速 度 系 数 ， 也 称 为
44、学 习 率几 乎 所 有 的 神 经 网 络 的 学 习 算 法 都 是 由 H e b b 规 则 衍 生 得 到 的第47页/共63页第四十七页，共64页。9.4智能(zhnn)模式识别方法人工神经网络常 见 的 人 工 神 经 网 络 类 型 ( 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智能模式识别(mshshbi)方法人工神经网络(BP)B P 神 经 网 络 是 反 向 传 播 ( B a c k P r o p a g a t i o
45、n ) 法 的 简 称 。 其 实 质 是 把 一 组 样 本 输 入 、 输 出 问 题 转 化 为 一 个 非线 性 优 化 问 题 ， 并 通 过 梯 度 ( t d ) 算 法 利 用 迭 代 运 算 求 解 权 值 问 题 的 一 种 学 习 算 法 。B P 网 络 模 型BP网络(wnglu)的神经元响应函数通常设为Sigmoid函数第49页/共63页第四十九页，共64页。9.4智能(zhnn)模式识别方法人工神经网络(BP)B P 算 法 的 学 习 过 程 由 正 向 传 播 和 反 向 传 播 组 成 。在 正 向 传 播 过 程 中 ， 输 入 信 息 从 输 入 层 经
46、 隐 含 层 逐 层 处 理 ， 并 传 向 输 出 层 。 每 一 层 神 经 元 的 状 态 只 影 响 下 一 层 神经 元 的 状 态 。如 果 输 出 层 得 不 到 期 望 的 输 出 ， 则 转 入 反 向 传 播 ， 将 误 差 信 号 沿 原 来 的 连 接 通 道 返 回 ， 通 过 修 改 ( x i g i ) 各 层 神经 元 的 权 值 ， 使 得 误 差 信 号 最 小 。B P 神 经 网 络 模 式 识 别 包 括 学 习 和 分 类 两 个 阶 段 。1 ） 网 络 结 构 确 定 ： 层 数 ， 各 层 节 点 数 ，2 ） 样 本 数 据 及 控 制 参
47、 数 输 入 ： 准 备 输 入 数 据 模 式 ， 神 经 元 响 应 参 数 ， 循 环 次 数 ， 分 类 精度 ， 学 习 率 等3 ） 网 络 权 值 初 始 化 。4 ） 通 过 训 练 调 整 网 络 各 层 权 值 。5 ） 判 断 学 习 过 程 是 否 完 毕 。6 ） 对 待 识 别 模 式 进 行 分 类 识 别 。第50页/共63页第五十页，共64页。9.4智能(zhnn)模式识别方法人工神经网络(BP)B P 网 络 的 应 用 实 例 ( s h l ) 手 写 体 字 符 识 别用 B P 神 经 网 络 进 行 手 写 体 数 字 识 别 时 ， 整 个 过
48、程 由 输 入 环 节 、 预 处 理 环 节 、 识 别 环 节 等 三 部 分 组 成 。1 ） 输 入 环 节 ： 通 过 扫 描 仪 获 得 字 符 的 数 字 图 像 文 件2 ） 预 处 理 ： 去 噪 、 标 准 化 、 特 征 提 取去 噪 ： 主 要 是 去 除 污 点 ， 与 无 意 义 的 线 段 形 状 噪 声标 准 化 ： 主 要 是 压 缩 变 换 ， 将 字 符 标 准 化 为 3 2 3 2 大 小 的 二 值 图 像 。特 征 提 取 ： 通 过 对 图 像 分 块 扫 描 获 取 每 个 字 块 的 细 化 结 果 的 点 的 数 量 来 表 征 图 像第5
49、1页/共63页第五十一页，共64页。9.4智能(zhnn)模式识别方法人工神经网络(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 j ( i j
50、) 时 ， 则 y i 为 有 效 输 出 结 果 。 3 ） 训 练用 1 0 0 个 样 本 ， 根 据 B P 算 法 进 行 训 练 ， 当 输 出 误 差 小 于 阈 值 时 停 止第53页/共63页第五十三页，共64页。9.4智能模式识别(mshshbi)方法统计学习理论机 器 学 习 的 基 本 概 念根 据 给 定 的 训 练 样 本 对 系 统 的 输 入 输 出 关 系 进 行 估 计 ， 进 而 得 到 对 其 他 未 知 输 出 的 预 测 。理 想 ( l x i n g ) 原 则 ： 预 测 的 期 望 风 险 最 小 化实 际 原 则 ： 预 测 的 经 验 风
51、 险 最 小 化第54页/共63页第五十四页，共64页。9.4智能模式识别方法统计(tngj)学习理论传统的统计学的缺陷主要体现在：在有限样本(yngbn)条件下：1）经验风险最小不等于期望风险最小2）学习机的复杂性不但取决于系统，而且要适应有限的学习样本(yngbn)统计学习理论的核心内容经验风险最小化原则下的统计学习一致性的条件；该条件下的统计学习方法的推广性的界的结论；在这些界的基础上建立小样本(yngbn)归纳推理原则；实现这些原则的实际可行的方法；第55页/共63页第五十五页，共64页。9.4智能(zhnn)模式识别方法最优分类平面基本概念训练样本集：xi,yi,yi-1，1,i=1
52、,2,l分类平面H的方程支持向量：距离分类平面最近的训练样本点的向量支持平面：经过支持向量点与分类平面平行的平面（H1，H2）分类间隔：分类平两侧(linc)的支持平面的距离。线性最优分类面：在对有限训练样本分类正确的情况下，使得分类间隔最大的分类平面平面。第56页/共63页第五十六页，共64页。9.4智能模式识别方法最优分类(fnli)平面基 本 思 路对 支 持 平 面 和 分 类 平 面 进 行 归 一 化 使 其 满 足 :可 以 推 导 证 明 ， 此 时 ( c s h ) 的 分 类 间 隔 为 2 / | | w | | ， 因 此 寻 找 最 优 分 类 面 的 问 题 可
53、以 转 化 为 以 下 的 带 有 约 束 条 件 的 最 小 化 问 题 ：通 过 建 立 L a g r a n g e 优 化 函 数 ， 经 推 导 可 以 得 到 下 面 的 结 论 ， 即 最 优 分 类 函 数 为 ：利用样本对该函数进行训练，找到使得所有样本分类(fn li)正确的最优的a*，b*第57页/共63页第五十七页，共64页。9.4智能(zhnn)模式识别方法支持向量机支 持 向 量 机 是 对 最 优 分 类 平 面 法 在 处 理 非 线 性 问 题 时 的 一 种 延 伸 和 深 化 。支 持 向 量 机 利 用 一 个 内 积 函 数 替 换 最 优 分 类
54、平 面 法 中 的 决 策 方 程 里 的 ， 进 而 ( j n r )将决 策 方 程 变 形 为 ：需 要 注 意 的 是 ， 在 推 导 过 程 可 以 知 道 ， 非 支 持 向 量 点 x i 对 应 的 参 数 a i 为 0 ， 也 就 是 说 决 策 方 程 将 仅 由 支 持 向 量 点决 定 。 即 算 法 复 杂 度 仅 由 支 持 向 量 点 所 决 定 。第58页/共63页第五十八页，共64页。9.4智能模式识别(mshshbi)方法支持向量机内 积 函 数 的 选 择 ( x u n z )多 项 式 形 式 ：核 函 数 形 式 ：S 形 函 数 形 式 ：支持
55、向量(xingling)机的令一大优势是识别率对于内积函数的选择并不十分敏感。这节省了很多模型设计方面的工作第59页/共63页第五十九页，共64页。9.4智能模式识别方法支持(zhch)向量机支 持 ( z h c h ) 向 量 机 在 图 像 处 理 中 的 应 用支 持 ( z h c h ) 矢 量 机 算 法 对 于 复 杂 图 像 ， 即 信 息 包 含 较 多 的 图 像 具 有 优 势 ， 更 能 把 握 待 分 地 物 的 特 征 ， 适 合 于 遥 感 图 像 分 类 。 （a）原始图像 （b）SVM算法 灰度图像及分类(fn li)结果图第60页/共63页第六十页，共64
56、页。9.4智能模式识别方法支持(zhch)向量机（a）原始图像(txin)（b）SVM算法RGB彩色图像(txin)及分类结果图第61页/共63页第六十一页，共64页。第九章图像匹配与识别(shbi)总结篇9 . 1 基 本 概 念模 式 ， 模 式 类 ， 模 式 识 别 系 统9 . 2 基 于 统 计 决 策 的 模 式 识 别匹 配 法 ， 贝 叶 斯 分 类 器 ， 线 性 分 类 器 ， k 近 邻 分 类 器9 . 3 基 于 结 构 句 法 ( j f ) 的 模 式 识 别形 状 数 匹 配 ， 串 匹 配 ， 串 句 法 ( j f ) 识 别9 . 4 基 于 智 能 计 算 方 法 的 模 式 识 别模 糊 模 式 识 别 ， 人 工 神 经 网 络 ，统 计 学 习 理 论 ， 支 撑 向 量 机第62页/共63页第六十二页，共64页。感谢您的欣赏(xnshng)第63页/共63页第六十三页，共64页。内容(nirng)总结9.1 基本概念。相关系数越大，相似性越大。当i满足以下(yxi)条件时，x被分类为模式类i。大部分情况下，需要人工设计或人机互动设计。BP算法的学习过程由正向传播和反向传播组成。标准化：主要是压缩变换，将字符标准化为3232大小的二值图像。y1y2y3。输出层No=10对应09共10类字符。感谢您的欣赏第六十四页，共64页。
