3.3识别与解释.ppt

1、图像分析技术分类的三种基本范畴,知识库,分割,表示与描述,识别 与 解释,预处理,图像获取,低级处理,高级处理,中级处理,结果,问题,3.图像处理与分析,3.3 识别与解释,3.3.1 模式与模式类 3.3.2 统计模式识别 3.3.3 神经网络与支持向量机 3.3.4 结构模式识别,图像识别与解释的基本方法 统计模式识别：用向量形式表达模式；分派模式向量到不同的模式类 结构模式识别：用符号匹配，模式被表示为符号形式（如形状数、串和树） 图像解释的方法：图像解释技术是基于谓词逻辑、语义网络和特定产品的系统,3.3 识别与解释,3.3.1 模式与模式类,1.模式的定义 2.模式类的定义 3.模式

2、识别的定义 4.常用的模式序列 模式特征向量 模式串 模式树,3.3.1 模式与模式类,1.模式的定义 模式是：图像中的一个对象或某些感兴趣本质的数量或结构的描述 模式是：由一个或多个描述子来组成，换句话说，模式是一个描述子的序列（名词“特征”经常被用来代指描述子） 模式是：一组特征或一组描述子,2.模式类的定义 模式类是具有某些公共特征的模式的系列 模式类用w1,w2,wM表示，M是类的个数 3.模式识别的定义 根据图像中对象的特征组成的模式，确定对象是属于那一个模式类，即为模式识别,3.3.1 模式与模式类,模式与模式类举例 1）汽车的长、宽、高（L,W,H）模式 2）大客车： （L,W,

3、H）大 小轿车： （L,W,H）小 卡 车： （L,W,H）卡 从而有模式类（w大, w小, w卡） 3）从图像中发现一个对象模式实例。 希望识别出该对象（L1,W1,H1），是大客车、小轿车、还是卡车模式识别,3.3.1 模式与模式类,4.常用的模式序列 三种模式序列: 1)模式特征向量 2)模式串 3)模式树 1)模式特征向量 定义 举例 特征的选择,3.3.1 模式与模式类,常用的模式序列 1)模式特征向量的定义描述子构成的向量 模式特征向量用粗体小写字母表示，如x,y形式如下： 其中每一个xi代表第i个描述子，n是这种描述子的数量。模式特征向量被表示为一列或表示成 x = (x1, x

4、2, , xn)T， 其中T指出是转秩,3.3.1 模式与模式类,模式特征向量举例 假设我们想描述三种蝴蝶花（多毛的、维吉尼亚、多色的）通过测量它们花瓣的宽度和长度。这里涉及一个两维的模式特征向量： 其中x1、x2分别对应花瓣的长和宽 三种模式类用w1、w2、w3表示,x =,x1 x2,3.3.1 模式与模式类,由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式特征向量也将有变化，不仅在不同的类之间，而且也在类的内部 在这种情况下每一种花变成二维欧几里德空间的一个点,3.3.1 模式与模式类,3.3.1 模式与模式类,模式特征向量举例：分析 对花瓣长宽的测量，成功地将多毛的蝴

5、蝶花与其它两种分离，但对于分离维吉尼亚和多色的是失败的。 这个结论说明了分类的特征选择问题，在这个问题中，类的可区别性的程度，完全依赖于对模式尺寸测量的选择,3.3.1 模式与模式类,模式特征的选择 良好的特征应具备四个特点 可区别性：对不同类别对象特征值差异明显 可靠性 ：对同类对象特征值比较接近 独立性 ：所用的各特征之间彼此统计独立 数量少 ：过多的特征数，会使系统复杂度提高 一般特征向量的选择方法 尽量不选择带噪声和相关度高的特征 先选择一组直觉上合理的特征，然后逐渐减少到最佳,3.3.1 模式与模式类,2)模式串 用于以对象特征的结构或空间关系作为模式的识别 模式串举例：梯状的模式,

6、3.3.1 模式与模式类,a,b,(1) S-aA (2) A-bS (3) A-b,3)模式树 以分层目录结构排序的模式类，一般多采用树结构 模式树举例,3.3.1 模式与模式类,图像,3.3.2 统计模式识别,1.分类器的设计和训练 2.决策论法的基本概念 3.分类器 最小距离分类器 相关匹配分类器,3.3.2统计模式识别,1.分类器的设计与训练 分类器一般设计方法 分类器对每一模式类，给出一个典型模板 对每一个遇到的待分类对象,计算该对象与个典型模板之间的相似程度 相似值是对象的函数 函数取值的不同，决定对象属于那一模式类,3.3.2统计模式识别,-分类器一般设计规则 分类器规则都转换为

7、阈值规则 将测量空间划分成互不重叠的区域 每一个模式类对应一个区域（或多个） 对象的分类函数值落在哪个区域，对象就属那类 某些情况，某些区域为“无法确定”类,3.3.2统计模式识别,-分类器的训练 决策规则决定后，需要确定分类器的阈值 实现的方法是用一组已知对象训练分类器 训练对象集由每类已被正确识别的部分对象组成 通过对这些对象的度量，定出能够将决策面划分成不同区域的合理阈值 使分类器对训练对象样本集分类准确性最高,3.3.2统计模式识别,2.统计模式识别的基本概念 统计模式识别的定义 设：模式特征向量：x = (x1, x2, ,xn)T， 对于：M个模式类 w1,w2,wM， 寻找M个决

8、策函数d1(x), d2(x), , dM(x)，具有这 样的特性：如果模式实例x属于模式类wi,那么： di(x) dj(x) j = 1, 2, , M; j i换句话说，如果一个未知模式对象x属于第i个模式类， 把x代入所有的决策函数，di(x)的取值最大。,3.3.2统计模式识别,-决策边界的定义 对于模式特征向量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

9、 属于类wj,3.3.2统计模式识别,3. 分类器 最小距离分类器 以蝴蝶花的例子为例： （1）为多色（w1）和多毛（w2 ）的两种蝴蝶花，确定两个原形（或称模板）m1和m2 （2）对于一个未知模式向量x，判断x与m1和m2的距离，如果与m1的距离小于与m2的距离，则x属于w1，否则属于w2 。,3.3.2统计模式识别,1,2,3,4,5,6,7,x1 花瓣长,0.5,1.0,1.5,2.0,2.5,3.0,x2 花瓣宽,多毛的,多色的,m1,m2,3.3.2统计模式识别,-最小距离分类器 1）算法思想： 对于M个模式类 wi i = 1,2,.,M 为每一个模式类确定一个原形模式特征向量mi

10、 对于一个未知模式特征向量x，如果x与mi的距离最小，就称，x属于wi,3.3.2统计模式识别,-最小距离分类器 2）最小距离分类器定义（训练）： 1计算模式类wj的原形向量： mj = 1/Nj x j = 1,2, , M xwj 其中Nj是属于模式类wj的模式向量的个数。 通过计算已知属于wj的模式特征向量的各分量的 均值得到原形模式特征向量mj,3.3.2统计模式识别,2计算x 与 mi的距离 dj(x) = | x mj | j = 1, 2, , M 其中 | a | = (aTa)1/2是欧几里德范式（平方和开方） dj(x) = (x mj )T (x mj ) 1/2 j =

11、 1, 2, , M 3决策 如果，di(x) = min(dj(x) j = 1, 2, , M 就说：x 属于wi,3.3.2统计模式识别,为便于计算，改写成求最大的标准形式，决策函数为： dj(x) = xTmj 1/2mjTmj j = 1,2, , M 如果，di(x) = max(dj(x) j = 1, 2, , 就说：x 属于wi 4用上式得到的类wi和wj之间的决策边界是： dij(x) = di(x) - dj(x) = xT（mi mj） 1/2(mi mj)T(mi mj) = 0,3.3.2统计模式识别,3）举例： 多色的和多毛的蝴蝶花，用w1和w2分别表示， 有简单

12、的原形向量 m1 = (4.4, 1.3)T m2 = (1.5, 0.3)T 决策函数是： d1(x) = xTm1 1/2m1Tm1 = 4.3x1 + 1.3x2 10.1 d2(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.3.2统计模式识别,1,2,3,4,5,6,7,x1 花瓣长,0.5,1.0,1.5,2.0,2.5,3.0,x2 花瓣宽,多毛的,多色的,3.3.2统计模式识别,分类器 相关匹配分类器 (1) 相关匹配的基本思想: a.

13、用样板子图像直接作为模式特征（不是用描述子） b. 通过子图像与原图像直接进行相关计算，把相关计算作为决策函数 c. 相关计算获得最大值的位置，就被认为匹配成功,3.3.2统计模式识别,相关匹配分类器 (1) 相关匹配基本思想,3.3.2统计模式识别,分类器 相关匹配分类器,M,x,原点,N,y,f(x,y),(s,t),J,s,w(x+s,y+t),K,t,3.3.2统计模式识别,分类器 相关匹配分类器 (2) 算法描述 决策函数是相关函数 c(s,t) = f(x,y)w(x+s,y+t) x y 对图像的每一个点进行相关计算，只计算重叠部分 问题：在边界处将失去准确性，其误差与子图像的尺

14、寸成正比,3.3.2统计模式识别,相关匹配分类器 (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)2w(x-s,y-t) w21/2 x y x y (s,t)的值域为（-1，1）,3.3.2统计模式识别,相关匹配分类器 (4) 对旋转和比例变化的分析 问题： 当被匹配图像中，对象的尺寸和角度与模式不一致，此方法将失效。 改进： 尺寸的正则化，解决空间比例的问题。正则化模板与原图。 如果知道原图像的旋转角度，我们可以通过旋转原图像，对齐模式解决。

15、 结论: 如果被匹配的对象的角度任意，此方法不能用于这种问题。,3.3.2统计模式识别,分类器 相关性匹配分类器 (5) 关于空域计算 相关函数，可以在频域计算。 f(x,y)w(x,y) f(s,t)w(s,t) 但无论在何种情况下，都没有更有优势的理论根据。相关系数方式只能在空域进行。,3.3.3神经网络和支持向量机,（1）感知机 （2）支持向量机,（1）感知机,最基本的感知机建立能将两个线性可分训练集分开的线性决策函数,对模式矢量增加第n + 1个元素 构建一个扩充模式矢量y，让yi = xi， i = 1, 2, , n，且后面加一个元素yn+1 = 1 其中y = y1 y2 yn

16、1T是个扩充模式矢量，w = w1 w2 wn wn+1T是个权矢量 关键问题：用模式矢量的给定训练集确定w,（1）感知机,1）.线性可分类 由两个线性可分训练集获取权矢量 令w(1)代表一个任意选定的初始权矢量 如果 y(k) s1，wT(k)y(k) 0 如果 y(k) s2，wT(k)y(k) 0 否则：,（1）感知机,1）.线性可分类 两个训练集，每个包括两个模式 先将模式扩充，对类s1得到训练集0 0 1T, 0 1 1T，对类s2得到训练集1 0 1T, 1 1 1T,（1）感知机,2）.线性不可分类 最小化实际响应和希望响应间的误差 沿J(w)负梯度的方向逐步增加w以寻找上述函数

17、的最小值。最小值应在r = wTy时出现 通用的梯度下降算法可写成：,（1）感知机,2）.线性不可分类 写成德尔塔（Delta）校正算法的形式 权矢量的误差 误差的变化量 改变权重能将误差减少a|y(k)|2，下一轮继续,（1）感知机,（2）支持向量机,1.线性可分类 线性分类器的设计目的：要设计一个超平面 满足条件的超平面 一般不惟一 离开两个类都比较 远的超平面分类的结果 会更好些，可能的错误率 也会更小一些,1.线性可分类 对每个朝向，与两个类距离相等的超平面应该是与两个类都有最大距离的超平面 确定能给出类距离 最大的朝向的超平面 从一个点到一个超 平面的距离,（2）支持向量机,1.线性

18、可分类 对每个类si，记其标号为ti，其中t1 = 1，t2 = 1。现在问题变为：计算超平面的w和w0，在满足下列条件 的情况下最小化 用拉格朗日乘数法来解,（2）支持向量机,1.线性可分类 结果为 最优解的向量参数w是Ns个（Ns N）与li 0相关的特征向量的线性组合（支持向量） 支持向量机：最优的超平面分类器,（2）支持向量机,2.线性不可分类 训练特征向量可以分成以下三类： (1)向量落在分类带之外且被正确地分了类 (2)向量落在分类带之内且被正确地分了类 (3)向量被错误地分了类,（2）支持向量机,3.3.4 结构模式识别,1.匹配形状数 2.匹配串,3.3.4结构模式识别,统计模

19、式识别，通过量化的方法处理模式，最大限度地忽略了模式形状的内在结构关系。 结构模式识别，则力求通过准确地抓住这些不同模式类的内在结构关系来进行模式识别。,3.3.4结构模式识别,1. 匹配形状数 (1) 匹配形状数的基本思想 通过比较两个对象边界的形状数的相似程度，来匹配对象。例如： 未知模式原形模式类,3.3.4结构模式识别,匹配形状数 (2) 基本概念-相似级别 a.两个区域边界的相似级别k的定义： 用相同形状数的最大序号表示：即： 当考虑用4向链码表示的封闭区域边界的形状数时，A和B具有相似级别k，当且仅当满足： s4(A) = s4(B), s6(A) = s6(B), s8(A) =

20、 s8(B), sk(A) = sk(B), sk+2(A) sk+2(B), sk+4(A) sk+4(B), ， 这里s表示形状数,下标表示序号。,3.3.4结构模式识别,匹配形状数 (2) 基本概念-形状数的距离 b.两个区域边界A和B形状数的距离D(A,B) 相似级别的倒数 ：D(A,B) = 1 / k 距离满足如下性质： D(A,B) 0 D(A,B) = 0 iff A=B D(A,C) maxD(A,B),D(B,C),3.3.4结构模式识别,匹配形状数 (3) 算法思想 a. 用不同密度的网格划分边界区域，获得不同序数的形状数。 b. 如果使用相似级别k，k越大说明越相似。

21、c. 如果使用相似距离D，D越小说明越相似 d. 可以利用相似树来进行判别,3.3.4结构模式识别,匹配形状数 （4）举例 假设我们有一个形状F，想在另5个形状（A，B，C，D，E）中找到与其最相似的形状,A,B,C,D,E,F,3.3.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,A B C D E F,A,B,E,D,C,F, 6 6 6 6 6, 8 8 10 8, 8 8 12, 8 8, 8,3.3.4结构模式识别,2.串匹配 （1）串匹配的基本思想 比较两个边界串编码的相似程度，来进行匹配 （2）三个基本概念 设: 两个区域边界A和B已分别被编码 为串a1a2an和b1b2bm。,a3a3a3a3a3a3a3a3,a2a2a3a3,3.3.4结构模式识别,串匹配 a.两个串的匹配数M: 当 ak= bk 时我们说发生了一个匹配。令M代表A、B中匹配的总数。 b.不匹配的符号数量Q： Q = max（|A|，|B|）- M 这里|arg|是字符串的长度。当且仅当A和B完全相同时，Q = 0。,3.