数字图像处理课程北大计算所124m版第03章数字图象分析05m

数字图像处理北京大学计算机研究所陈晓鸥第四节识别与解释3.4.1图像分析引言3.4.2图像分析系统的组成3.4.3模式与模式类3.4.4决策论法3.4.5结构法3.4.1图像分析引言图像分析引言图像分析的定义图像分析的目标自动图像分析系统行为能力的概念化分类自动图像分析系统的现状3.4.1图像分析引言图像分析的定义图像分析是一个：

发现、辨认和理解模式的过程这些模式都与执行和图像相关的任务有关。图像分析的目标计算机图像分析的主要目的之一是，赋予某些具有感觉能力的机器，以类似人的大脑的能力。例如OCR3.4.1图像分析引言自动图像分析系统行为能力的概念化分类分为三类：获取、发现信息：从背景中提取有关信息学习、应用知识：抽象、归纳信息特征的学习过程， 并应用到新的对象中构造、推理知识：从不完整的信息中构造推论出新 的知识，并加以应用3.4.1图像分析引言自动图像分析系统的现状我们可以设计出这种系统，但仍然缺乏理论依据。有待人类视觉认识理论的进一步研究我们可以做出在某一应用上超过人的能力的系统，但缺乏扩展性。过分依赖应用3.4.2图像分析系统组的成图像分析技术分类的三种基本范畴低级处理：图像获取、预处理，不需要智能中级处理：图像分割、表示与描述，需要智能高级处理：图像识别、解释，缺少理论，为降 低难度，设计得更专用。图像分析技术分类的三种基本范畴知识库分割表示与描述识别与解释预处理图像获取低级处理高级处理中级处理结果问题3.4.2图像分析系统组的成图像识别与解释的基本方法识别的统计分类方法：用向量形式表达模式；分派模式向量到不同的模式类识别的结构方法：用符号匹配，模式被表示为符号形式（如形状数、串和树）图像解释的方法：图像解释技术是基于谓词逻辑、语义网络和特定产品的系统3.4.2图像分析系统组的成3.4.3模式与模式类模式的定义模式类的定义模式识别的定义常用的模式序列模式特征向量模式串模式树3.4.3模式与模式类模式的定义模式是：图像中的一个对象或某些感兴趣本质的数量或结构的描述模式是：由一个或多个描述子来组成，换句话说，模式是一个描述子的序列（名词“特征”经常被用来代指描述子）模式是：一组特征或一组描述子模式类的定义模式类是具有某些公共特征的模式的系列 模式类用w1,w2,…wM表示，M是类的个数模式识别的定义根据图像中对象的特征组成的模式，确定对象是属于那一个模式类，即为模式识别3.4.3识别与解释:模式与模式类模式与模式类举例1）汽车的长、宽、高（L,W,H）——模式2）大客车：（L,W,H）大 小轿车：（L,W,H）小 卡车：（L,W,H）卡 从而有模式类（w大,w小,w卡）3）从图像中发现一个对象——模式实例。 希望识别出该对象（L1,W1,H1），是大客车、小轿车、还是卡车——模式识别3.4.3识别与解释:模式与模式类常用的模式序列三种模式序列:模式特征向量模式串模式树模式特征向量定义举例特征的选择3.4.3模式与模式类常用的模式序列模式特征向量的定义——描述子构成的向量模式特征向量用粗体小写字母表示，如x,y形式如下：

其中每一个xi代表第i个描述子，n是这种描述子的数量。模式特征向量被表示为一列或表示成

x=(x1,x2,…,xn)T，

其中T指出是转秩x=

x1x2.xn3.4.3模式与模式类模式特征向量举例

假设我们想描述三种蝴蝶花（多毛的、维吉尼亚、多色的）通过测量它们花瓣的宽度和长度。这里涉及一个两维的模式特征向量：其中x1、x2分别对应花瓣的长和宽三种模式类用w1、w2、w3表示x=

x1x23.4.3模式与模式类

由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式特征向量也将有变化，不仅在不同的类之间，而且也在类的内部 在这种情况下每一种花变成二维欧几里德空间的一个点3.4.3模式与模式类3.4.3模式与模式类1234567x1花瓣长0.51.01.52.02.53.0x2花瓣宽多毛的维吉尼亚多色的模式特征向量举例：分析

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

(1)S->aA (2)A->bS(3)A->b模式树

以分层目录结构排序的模式类，一般多采用树结构模式树举例3.4.3模式与模式类图像城市田园草地森林娱乐区商业区娱乐区商业区城区内城市郊公路3.4.4决策论法决策论法分类器的设计和训练决策论法的基本概念分类器最小距离分类器相关匹配分类器3.4.4决策论法分类器的设计与训练分类器一般设计方法分类器对每一模式类，给出一个典型摸板对每一个遇到的待分类对象计算该对象与个典型摸板之间的相似程度相似值是对象的函数函数取值的不同，决定对象属于那一模式类3.4.4决策论法分类器的设计与训练分类器一般设计规则分类器规则都转换为阈值规则将测量空间划分成互不重叠的区域每一个模式类对应一个区域（或多个）对象的分类函数值落在哪个区域，对象就属那类某些情况，某些区域为“无法确定”类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)>0x属于类wi

如果dij(x)<0x属于类wj3.4.4识别与解释:决策论法分类器最小距离分类器以蝴蝶花的例子为例：（1）为多色（w1）和多毛（w2）的两种蝴蝶花，确定两个原形（或称模板）m1和m2（2）对于一个未知模式向量x，判断x与m1和m2的距离，如果与m1的距离小于与m2的距离，则x属于w1，否则属于w2。3.4.4识别与解释:决策论法1234567x1花瓣长0.51.01.52.02.53.0x2花瓣宽多毛的多色的m1m2x3.4.4识别与解释:决策论法分类器最小距离分类器1）算法思想：对于M个模式类wii=1,2,...,M

为每一个模式类确定一个原形模式特征向量mi对于一个未知模式特征向量x，如果x与mi的距离最小，就称，x属于wi3.4.4识别与解释:决策论法分类器最小距离分类器2）最小距离分类器定义（训练）：〈1〉计算模式类wj的原形向量：

mj=1/Nj

x

j=1,2,…,M

xwj

其中Nj是属于模式类wj的模式向量的个数。通过计算已知属于wj的模式特征向量的各分量的均值得到原形模式特征向量mj3.4.4识别与解释:决策论法分类器最小距离分类器〈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=1,2,…,M〈3〉 决策如果，di(x)=min(dj(x))

j=1,2,…,M

就说：x属于wi3.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)=03.4.4识别与解释:决策论法3）举例：多色的和多毛的蝴蝶花，用w1和w2分别表示，有简单的原形向量m1=(4.4,1.3)T m2=(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.0x2

–8.9=03.4.4识别与解释:决策论法1234567x1花瓣长0.51.01.52.02.53.0x2花瓣宽多毛的多色的3.4.4识别与解释:决策论法分类器相关匹配分类器(1)相关匹配的基本思想:a.用样板子图像直接作为模式特征（不是用描述子）b.通过子图像与原图像直接进行相关计算，把相关计算作为决策函数c.相关计算获得最大值的位置，就被认为匹配成功3.4.4识别与解释:决策论法相关匹配分类器(1)相关匹配基本思想3.4.4识别与解释:决策论法分类器相关匹配分类器Mx原点Nyf(x,y)(s,t)Jsw(x-s,y-t)Kt3.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/2

xy

xy

γ(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)基本概念-相似级别

a.两个区域边界的相似级别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)基本概念-形状数的距离b.两个区域边界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）中找到与其最相似的形状ABCDEF3.4.4识别与解释:结构法

这个问题类似于有五个原型形状，想找出一个给定的尚不确定的形状的最佳匹配的问题。这个问题可以利用相似树和矩阵来可视化468101214ABCDEFABCDEFBCDEFAAAABECFBEDDDCFCFBEABCDEFABEDCF666668810888128883.4.4识别与解释:结构法串匹配（1）串匹配的基本思想比较两个边界串编码的相似程度，来进行匹配（2）三个基本概念 设:两个区域边界A和B已分别被编码为串a1a2…an和b1b2…bm。a3a3a3a3a3a3a3a3a2a2a3a33.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识别与解释:结构法串匹