数字图像识别与解释课件

单击此处编辑母版标题样式0,单击此处编辑母版文本样式1,第二级2,第三级3,第四级4,第五级5,*,第三章 数字图像分析 第四节 识别与解释,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数字图像处理,北京大学计算机研究所 陈晓鸥,第四节 识别与解释,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,识别与解释,:,模式与模式类,模式,的定义,模式,是图像中的一个,对象,或某些,感兴趣本质,的,数量,或,结构,的描述,模式,是由一个或多个描述子来组成，换句话说，模式是一个描述子的序列（名词“特征”经常被用来代指描述子）,模式,是一组特征或一组描述子,模式类,的定义,模式类,是具有某些公共特征的模式的系列,模式类用,w,1,w,2,w,M,表示，,M,是类的个数,模式识别,的定义,根据图像中对象的特征组成的模式，确定对象是属于那一个模式类，即为模式识别,模式与模式类举例,已知汽车的长、宽、高（,x,1,x,2,x,3,）,希望识别出，大客车、小轿车、卡车（,w,1,w,2,w,3,）,3.4.3,识别与解释,:,模式与模式类,常用的模式序列,模式向量、模式串、模式树,模式向量,模式向量用粗体的小写字母表示，如,x,y,形式如下：,其中每一个,x,i,代表第,i,个描述子，,n,是这种描述子的数量。模式向量被表示为一列或表示成,x = (x,1, x,2, x,n,),T,，,其中,T,指出是转秩,x,=,x,1,x,2,.,x,n,3.4.3,识别与解释,:,模式与模式类,模式向量举例,假设我们想描述三种蝴蝶花（多毛的、维吉尼亚、多色的）通过测量它们花瓣的宽度和长度。这里涉及一个两维的模式向量：,其中,x,1,、,x,2,分别对应花瓣的长和宽,三种模式类用,w,1,、,w,2,、,w,3,表示,x =,x,1,x,2,3.4.3,识别与解释,:,模式与模式类,由于所有的花瓣在宽和长上都有某种程度的变化，所以描述这些花瓣的模式向量也将有变化，不仅在不同的类之间，而且也在类的内部,在这种情况下每一种花变成二维欧几里德空间的一个点,3.4.3,识别与解释,:,模式与模式类,3.4.3,识别与解释,:,模式与模式类,1,2,3,4,5,6,7,x,1,花瓣长,0.5,1.0,1.5,2.0,2.5,3.0,x,2,花瓣宽,多毛的,维吉尼亚,多色的,对结果的分析,对花瓣长宽的测量，成功地将多毛的蝴蝶花与其它两种分离，但对于分离维吉尼亚和多色的是失败的。,这个结论说明了分类的特性选择问题，在这个问题中，类的可分离性的程度，完全依赖于对模式尺寸测量的选择,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 = (x,1, x,2,x,n,),T,，,对于：,M,个模式类,w,1,w,2,w,M,，,寻找,M,个,决策函数,d,1,(x), d,2,(x), d,M,(x),具有这,样的特性：如果模式,x,属于模式类,w,i,那么：,d,i,(x) d,j,(x) j = 1, 2, M; j,i,换句话说，如果一个未知模式,x,属于第,i,个模式类，,把,x,代入所有的决策函数，,d,i,(x),的数值最大。,3.4.4,识别与解释,:,决策论法,决策论法的基本概念,决策边界,的定义,对于模式,x,，如果决策函数值有：,d,i,(x) - d,j,(x) = 0,此,x,值，被称为,w,i,与,w,j,的决策边界。,通常用一个单一的函数标识两个类之间的,决策,边界,，定义为：,d,ij,(x) = d,i,(x) - d,j,(x) = 0,如果,d,ij,(x) 0,x,属于类,w,i,如果,d,ij,(x) 0,x,属于类,w,j,3.4.4,识别与解释,:,决策论法,匹配,最小距离分类器,以蝴蝶花的例子为例：,1,为多色（,w,1,）和多毛（,w,2,）的两种蝴蝶花，确定两个,原形,（或称模板）,m,1,和,m,2,2,对于一个未知模式向量,x,，判断,x,与,m,1,和,m,2,的距离，如果与,m,1,的距离小于与,m,2,的距离，则,x,属于,w,1,，否则属于,w,2,。,3.4.4,识别与解释,:,决策论法,1,2,3,4,5,6,7,x,1,花瓣长,0.5,1.0,1.5,2.0,2.5,3.0,x,2,花瓣宽,多毛的,多色的,m1,m2,x,3.4.4,识别与解释,:,决策论法,匹配,最小距离分类器,1,）算法思想：,对于,M,个模式类,w,j,j = 1,2,.,M,为每一个模式类确定一个原形模式向量,m,j,对于一个未知模式向量,x,，如果,x,与,m,i,的距离最小，就称，,x,属于,w,i,。,3.4.4,识别与解释,:,决策论法,匹配,最小距离分类器,2,）最小距离分类器定义：,1,计算模式类,w,j,的原形向量：,m,j,=,1/N,j,x,j = 1,2, M,x,wj,其中,N,j,是属于模式类,w,j,的模式向量的个数。,通过计算已知属于,w,j,的模式向量的各分量的,均值,得到原形模式向量,m,j,3.4.4,识别与解释,:,决策论法,匹配,最小距离分类器,2,计算,x,与,m,i,的距离,d,j,(x) =,| x,m,j,|,j = 1, 2, M,其中,| a | = (a,T,a),1/2,是欧几里德范式,（平方和开方）,3,决策,如果，,d,i,(x),=,min(d,j,(x),j = 1, 2, M,就说：,x,属于,w,i,3.4.4,识别与解释,:,决策论法,匹配,最小距离分类器,改写成求最大的标准形式，决策函数为：,d,j,(x) = x,T,m,j,1/2m,j,T,m,j,j = 1,2, M,如果，,d,i,(x) = max(d,j,(x) j = 1, 2, M,就说：,x,属于,w,i,4,类,w,i,和,w,j,之间的,决策边界,是：,d,ij,(x) = d,i,(x) - d,j,(x),= x,T,（,m,i,m,j,）,1/2(m,i,m,j,),T,(m,i,m,j,) = 0,3.4.4,识别与解释,:,决策论法,3,）举例：,多色的和多毛的蝴蝶花，用,w1,和,w2,分别表示，,有简单的原形向量,m,1,= (4.4, 1.3),T,m,2,= (1.5, 0.3),T,决策函数是：,d,1,(x) = x,T,m,1,1/2m,1,T,m,1,= 4.3x,1,+ 1.3x,2,10.1,d,2,(x) = x,T,m,2,1/2m,2,T,m,2,= 1.5x,1,+ 0.3x,2,1.17,决策边界的等式：,d,12,(x) = d,1,(x),d,2,(x) = 2.8x,1,1.0x,2,8.9 = 0,3.4.4,识别与解释,:,决策论法,1,2,3,4,5,6,7,x,1,花瓣长,0.5,1.0,1.5,2.0,2.5,3.0,x,2,花瓣宽,多毛的,多色的,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),x y,对图像的每一个点进行相关计算，只计算重叠部分。,问题：在边界处将失去准确性，其误差与子图像的尺寸成正比,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,x y,x y,(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,a.,两个区域边界的,相似级别,k,的定义：,相同形状数的,最大序号,：即：,当考虑用,4,向链码表示的封闭区域边界的形状数时，,A,和,B,具有相似级别,k,，如果满足,s,4,(A) = s,4,(B), s,6,(A) = s,6,(B), s,8,(A) = s,8,(B), s,k,(A) = s,k,(B), s,k+2,(A),s,k+2,(B), s,k+4,(A),s,k+4,(B),，这里,s,表示形状数,下标表示序号。,3.4.4,识别与解释,:,结构法,匹配形状数,(2),基本概念,-b,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.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,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.4.4,识别与解释,:,结构法,串匹配,（,1,）串匹配的基本思想,比较两个边界的串编码的相似程度，来进行匹配,（,2,）三个基本概念,设,:,两个区域边界,A,和,B,已分别被编码,为串,a,1,a,2,a,n,和,b,1,b,2,b,m,。,3.4.4,识别与解释,:,结构法,串匹配,a.,两个串的,匹配数,M:,当,a,k,= b,k,时我们说发生了一个匹配。令,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.f,5,个样例,模式类,2,：有,2.b,、,2.c,、,2.d,、,2.e,、,2.f,5,个样例,3.4.4,识别与解释,:,结构法,串匹配,现将模式,1.a,与,模式类,1,的,5,个样例做串匹配，有,R,值的结果表：,1.b 1.c 1.d 1.e 1.f,1.a,16.0 9.6 5.07 4.67 4.67,3.4.4,识别与解释,:,结构法,串匹配,现将模式,2.a,与,模式类,2,的,5,个样例做串匹配，有,R,值的结果表：,2.b 2.c 2.d 2.e 2.f,2.a,33.5 4.75 3.6 2.83 2.63,3.4.4,识别与解释,:,结构法,将模式,1.a,与,模式类,2,的,5,个样例做串匹配，有,R,值的结果表,：,2.a 2.b 2.c 2.d 2.e 2.f,1.a,1.24,1.18 1.02 1.02 0.93 .89,将模式,2.a,与,模式类,1,的,5,个样例做串匹配有,R,值的结果表：,1.a 1.b 1.c 1.d 1.e 1.f,2.a,1.24,1.50 1.32 1.47 1.55 1.48,请提问,