数字图像识别与解释.ppt

数字图像处理 北京大学计算机研究所陈晓鸥 第四节识别与解释 3 4 1图像分析引言3 4 2图像分析系统的组成3 4 3模式与模式类3 4 4决策论法3 4 5结构法 3 4 1识别与解释 图像分析引言 图像分析引言图像分析的定义图像分析的目标自动图像分析系统行为能力的概念化分类自动图像分析系统的现状 3 4 1识别与解释 图像分析引言 图像分析的定义图像分析是一个发现 辨认和理解模式的过程 这些模式都与执行与图像相关的任务有关 图像分析的目标计算机图像分析的主要目的之一是 赋予某些具有感觉能力的机器 以类似人的大脑的能力 例如OCR 3 4 1识别与解释 图像分析引言 自动图像分析系统行为能力的概念化分类获取 发现信息 从背景中提取有关信息学习 应用知识 抽象 归纳信息特征的学习过程 并应用到新的对象中 构造 推理知识 从不完整的信息中构造推论出新的知识 并加以应用 3 4 1识别与解释 图像分析引言 自动图像分析系统的现状我们可以设计出这种系统 但仍然缺乏理论依据 有待人类视觉认识理论的进一步研究 我们可以做出在某一应用上超过人的能力的系统 但缺乏扩展性 过分依赖应用 3 4 2识别与解释 图像分析系统组的成 图像分析技术分类的三种基本范畴低级处理 图像获取 预处理 不需要智能中级处理 图像分割 表示与描述 需要智能高级处理 图像识别 解释 缺少理论 为降低难度 设计得更专用 图像分析技术分类的三种基本范畴 知识库 分割 表示与描述 识别与解释 预处理 图像获取 低级处理 高级处理 中级处理 结果 问题 3 4 2识别与解释 图像分析系统组的成 图像识别与解释的基本方法识别的统计分类方法 用向量形式表达模式 分派模式向量到不同的模式类 识别的结构方法 用符号匹配 模式被表示为符号形式 如形状数 串和树 图像解释的方法 图像解释技术是基于谓词逻辑 语义网络和特定产品的系统 3 4 2识别与解释 图像分析系统组的成 3 4 3识别与解释 模式与模式类 模式与模式类模式的定义模式类的定义模式识别的定义常用的模式序列模式向量模式串模式树 3 4 3识别与解释 模式与模式类 模式的定义模式是图像中的一个对象或某些感兴趣本质的数量或结构的描述模式是由一个或多个描述子来组成 换句话说 模式是一个描述子的序列 名词 特征 经常被用来代指描述子 模式是一组特征或一组描述子 模式类的定义模式类是具有某些公共特征的模式的系列模式类用w1 w2 wM表示 M是类的个数模式识别的定义根据图像中对象的特征组成的模式 确定对象是属于那一个模式类 即为模式识别模式与模式类举例已知汽车的长 宽 高 x1 x2 x3 希望识别出 大客车 小轿车 卡车 w1 w2 w3 3 4 3识别与解释 模式与模式类 常用的模式序列模式向量 模式串 模式树模式向量模式向量用粗体的小写字母表示 如x y形式如下 其中每一个xi代表第i个描述子 n是这种描述子的数量 模式向量被表示为一列或表示成x x1 x2 xn T 其中T指出是转秩 x x1x2 xn 3 4 3识别与解释 模式与模式类 模式向量举例假设我们想描述三种蝴蝶花 多毛的 维吉尼亚 多色的 通过测量它们花瓣的宽度和长度 这里涉及一个两维的模式向量 其中x1 x2分别对应花瓣的长和宽三种模式类用w1 w2 w3表示 x x1x2 3 4 3识别与解释 模式与模式类 由于所有的花瓣在宽和长上都有某种程度的变化 所以描述这些花瓣的模式向量也将有变化 不仅在不同的类之间 而且也在类的内部在这种情况下每一种花变成二维欧几里德空间的一个点 3 4 3识别与解释 模式与模式类 3 4 3识别与解释 模式与模式类 1 2 3 4 5 6 7 x1花瓣长 0 5 1 0 1 5 2 0 2 5 3 0 x2花瓣宽 多毛的 维吉尼亚 多色的 对结果的分析对花瓣长宽的测量 成功地将多毛的蝴蝶花与其它两种分离 但对于分离维吉尼亚和多色的是失败的 这个结论说明了分类的特性选择问题 在这个问题中 类的可分离性的程度 完全依赖于对模式尺寸测量的选择 3 4 3识别与解释 模式与模式类 模式串用于以对象特征的结构或空间关系作为模式的识别模式串举例 梯状的模式 3 4 3识别与解释 模式与模式类 a b a a a b b b 1 S aA 2 A bS 3 A b 模式树以分层目录结构排序的模式类 一般多采用树结构模式树举例 3 4 3识别与解释 模式与模式类 图像 城市 田园 城区 内城 市郊 公路 草地 森林 娱乐区 商业区 娱乐区 商业区 3 4 4识别与解释 决策论法 决策论法决策论法的基本概念匹配最小距离分类器相关匹配 3 4 4识别与解释 决策论法 决策论法的基本概念决策论识别法的定义设 模式向量 x x1 x2 xn T 对于 M个模式类w1 w2 wM 寻找M个决策函数d1 x d2 x dM x 具有这样的特性 如果模式x属于模式类wi 那么 di x dj x j 1 2 M j i换句话说 如果一个未知模式x属于第i个模式类 把x代入所有的决策函数 di x 的数值最大 3 4 4识别与解释 决策论法 决策论法的基本概念决策边界的定义对于模式x 如果决策函数值有 di x dj x 0此x值 被称为wi与wj的决策边界 通常用一个单一的函数标识两个类之间的决策边界 定义为 dij x di x dj x 0如果dij x 0 x属于类wi如果dij x 0 x属于类wj 3 4 4识别与解释 决策论法 匹配最小距离分类器以蝴蝶花的例子为例 1 为多色 w1 和多毛 w2 的两种蝴蝶花 确定两个原形 或称模板 m1和m2 2 对于一个未知模式向量x 判断x与m1和m2的距离 如果与m1的距离小于与m2的距离 则x属于w1 否则属于w2 3 4 4识别与解释 决策论法 1 2 3 4 5 6 7 x1花瓣长 0 5 1 0 1 5 2 0 2 5 3 0 x2花瓣宽 多毛的 多色的 m1 m2 x 3 4 4识别与解释 决策论法 匹配最小距离分类器1 算法思想 对于M个模式类wjj 1 2 M为每一个模式类确定一个原形模式向量mj对于一个未知模式向量x 如果x与mi的距离最小 就称 x属于wi 3 4 4识别与解释 决策论法 匹配最小距离分类器2 最小距离分类器定义 1 计算模式类wj的原形向量 mj 1 Nj xj 1 2 Mx wj其中Nj是属于模式类wj的模式向量的个数 通过计算已知属于wj的模式向量的各分量的均值得到原形模式向量mj 3 4 4识别与解释 决策论法 匹配最小距离分类器 2 计算x与mi的距离dj x x mj j 1 2 M其中 a aTa 1 2是欧几里德范式 平方和开方 3 决策如果 di x min dj x j 1 2 M就说 x属于wi 3 4 4识别与解释 决策论法 匹配最小距离分类器改写成求最大的标准形式 决策函数为 dj x xTmj 1 2mjTmjj 1 2 M如果 di x max dj x j 1 2 M就说 x属于wi 4 类wi和wj之间的决策边界是 dij x di x dj x xT mi mj 1 2 mi mj T mi mj 0 3 4 4识别与解释 决策论法 3 举例 多色的和多毛的蝴蝶花 用w1和w2分别表示 有简单的原形向量m1 4 4 1 3 Tm2 1 5 0 3 T决策函数是 d1 x xTm1 1 2m1Tm1 4 3x1 1 3x2 10 1d2 x xTm2 1 2m2Tm2 1 5x1 0 3x2 1 17决策边界的等式 d12 x d1 x d2 x 2 8x1 1 0 x2 8 9 0 3 4 4识别与解释 决策论法 1 2 3 4 5 6 7 x1花瓣长 0 5 1 0 1 5 2 0 2 5 3 0 x2花瓣宽 多毛的 多色的 3 4 4识别与解释 决策论法 匹配相关匹配 1 相关匹配的基本思想 a 用样板子图像直接作为模式 不是用描述子 b 通过子图像与原图像直接进行相关计算 把相关计算作为决策函数 c 相关计算获得最大值的位置 就被认为匹配成功 3 4 4识别与解释 决策论法 相关匹配 1 相关匹配基本思想 3 4 4识别与解释 决策论法 匹配相关性匹配 M x 原点 N y f x y s t J s w x s y t K t 3 4 4识别与解释 决策论法 匹配相关匹配 2 算法描述决策函数是相关函数c s t f x y w x s y t xy对图像的每一个点进行相关计算 只计算重叠部分 问题 在边界处将失去准确性 其误差与子图像的尺寸成正比 3 4 4识别与解释 决策论法 相关性匹配 3 改进相关函数对振幅的变化太敏感 f x y 加倍 c s t 也加倍 用相关系数函数代替相关函数 f x y f x y w x s y t w s t f x y f x y 2 w x s y t w 2 1 2xyxy s t 的值域为 1 1 3 4 4识别与解释 决策论法 相关性匹配 4 对旋转和比例变化的分析当被匹配图像中 对象的尺寸和角度与模式不一致 此方法将失效 尺寸的正则化 解决空间比例的问题 正则化模板与原图 如果知道原图像的旋转角度 我们可以通过旋转原图像 对齐模式解决 如果被匹配的对象的角度任意 有结论 此方法不能用于这种问题 3 4 4识别与解释 决策论法 匹配相关性匹配 5 关于空域计算相关函数 可以在频域计算 f x y w x y f s t w s t 但在何种情况下 没有更有优势的理论根据 相关系数方式只能在空域进行 3 4 4识别与解释 结构法 结构法匹配形状数匹配串 3 4 4识别与解释 结构法 结构法决策法 通过量化的方法处理模式 最大限度地忽略了模式形状的内在结构关系 结构法 则力求通过准确地抓住这些不同模式类的内在结构关系来进行模式识别 3 4 4识别与解释 结构法 匹配形状数 1 匹配形状数的基本思想通过比较两个对象边界的形状数的相似程度 来匹配对象 例如 未知模式原形模式类 3 4 4识别与解释 结构法 匹配形状数 2 基本概念 aa 两个区域边界的相似级别k的定义 相同形状数的最大序号 即 当考虑用4向链码表示的封闭区域边界的形状数时 A和B具有相似级别k 如果满足s4 A s4 B s6 A s6 B s8 A s8 B sk A sk B sk 2 A sk 2 B sk 4 A sk 4 B 这里s表示形状数 下标表示序号 3 4 4识别与解释 结构法 匹配形状数 2 基本概念 bb 两个区域边界A和B形状数的距离D A B 相似级别的倒数 D A B 1 k距离满足如下性质 D A B 0D A B 0iffA BD A C max D A B D B C 3 4 4识别与解释 结构法 匹配形状数 3 算法思想a 用不同密度的网格划分边界区域 获得不同序数的形状数 b 如果使用相似级别k k越大说明越相似 c 如果使用相似距离D D越小说明越相似d 可以利用相似树来进行判别 3 4 4识别与解释 结构法 匹配形状数 4 举例假设我们有一个形状F 想在另5个形状 A B C D E 中找到与其最相似的形状 A B C D E F 3 4 4识别与解释 结构法 这个问题类似于有五个原型形状 想找出一个给定的尚不确定的形状的最佳匹配的问题 这个问题可以利用相似树和矩阵来可视化 4 6 8 10 12 14 ABCDEF ABCDEF BCDEF A A A A BE CF B E D D D CF C F B E ABCDEF A B E D C F 66666 88108 8812 88 8 3 4 4识别与解释 结构法 串匹配 1 串匹配的基本思想比较两个边界的串编码的相似程度 来进行匹配 2 三个基本概念设 两个区域边界A和B已分别被编码为串a1a2 an和b1b2 bm 3 4 4识别与解释 结构法 串匹配a 两个串的匹配数M 当ak bk时我们说发生了一个匹配 令M代表A B中匹配的总数 b 不匹配的符号数量Q Q max A B M这里 arg 是字符串的长度 当且仅当A和B完全相同时 Q 0 3 4 4识别与解释 结构法 串匹配c A和B相似度的简便衡量R R M Q M max A B M 因此 当A和B完全匹配时 R 当A和B中任何字符都不匹配时 M 0 R 0 3 4 4识别与解释 结构法 串匹配 3 算法思想a 由于匹配是逐字符进行的 b 选择一个好的开始点 可以大大减少计算量 任何将两个串规则化为相同字符开头的方法都是有效的 只要这种方法不是穷举起点 c 最大的R给出了最好的匹配 3 4 4识别与解释 结构法 串匹配 4 举例 模式1 a 模式2 a 3 4 4识别与解释 结构法 串匹配现有两个模式类 模式类1 有1 b 1 c 1 d 1 e 1 f5个样例模式类2 有2 b 2 c 2 d 2 e 2 f5个样例 3 4 4识别与解释 结构法 串匹配现将模式1 a与模式类1的5个样例做串匹配 有R值的结果表 1 b1