数字图像处理第9章资料

1、本章指导：重点掌握图像匹配与识别技术的基本概念以及常用(chn yn)图像匹配与识别方法，如基于匹配的识别、统计模式识别、句法模式识别等，对模糊模式识别、人工神经网络识别和支持向量机识别等有初步了解。第9章 图像匹配与识别(shbi) 共五十七页9.1 模式(msh)与模式(msh)识别 9.2 基于匹配的识别技术 9.3 统计模式识别 9.4 句法模式识别 9.5 模糊模式识别方法9.6 人工神经网络识别法 9.7 统计学习理论和支持向量机识别方法9.8 小结第9章 图像匹配与识别(shbi) 共五十七页9.1模式(msh)与模式(msh)识别 9.1.1 模式的概念 模式识别(patter

2、n recognition)作为一门学科有其系统的理论基础和技术方法。 模式识别属于图像分析的范畴，它所得到的结果是一幅由明确意义的数值或符号构成的图像或图形文件，而不再是一幅具有随机分布性质的图像 。 模式识别的目的是对图像中的物体进行分类，或者可以说是找出图像中有哪些物体。模式就是存在于时间和空间中，可以区别它们是否相同或相似的可观察的事物。但模式所指的不是事物本身，而是从事物中获取的信息。因此(ync)模式往往表现为具有时间和空间分布的信息。 共五十七页9.1.2 模式识别(m sh sh bi)系统 模式识别技术起源于人类自身对事物的认知分析过程，是依据一定的量度或观测基础把待识别模式

3、划分到各自的模式类中取得过程。模式类是指模式所属的类别或同一类中模式的总体。 模式识别实际上包含了以下(yxi)两个步骤：（1）特征提取和选择（2）决策分类共五十七页模式识别系统(xtng)的基本构成信息获取数据预处理特征提取和选择分类器设计分类决策训练过程输出结果共五十七页信息获取部分 为了使计算机能够对各种现象进行分类识别，首先利用各种输入设备将要识别对象的信息输入计算机。 通过测量(cling)、采样和量化，可以用矩阵或者向量来表示待识别对象的信息，这就是信息获取的过程。 预处理部分 预处理的目的就是去除噪声，加强有用的信息，并对输入测量仪器或其他因素所造成的退化现象进行复原。 对于(d

4、uy)数字图像来说，预处理就是应用前面讲到的图像复原、增强和变换等技术对图像进行处理，提高图像的视觉效果，优化各种统计指标，为特征提取提供高质量的图像。共五十七页特征提取和选择 由于待识别对象的数据量可能是相当大的，为了有效的实现分类识别，就要对原始数据进行某种变换(binhun)，得到最能反映分类本质的特征。这就是特征提取和选择的过程。 决策分类 分类决策就是利用特征空间中获得的信息，对计算机进行训练，从而制定判别标准，用某种方法把待识别对象归为某一类别的过程。 共五十七页9.1.3 模式识别(m sh sh bi)方法的分类 统计(tngj)模式识别方法 基本思想是将提取的特征向量定义在一

5、个特征空间中，不同类别的对象都对应于空间中的一点，在分类阶段，利用统计决策原理对特征空间进行划分，从而识别不同特征的对象。统计模式识别的主要方法有：判别函数法、K近邻分类法、非线性映射法、特征分析法以及主成分分析法等。 共五十七页模糊模式识别 模糊识别的理论基础是模糊数学(fuzzy math)。它根据人辨识事物的思维逻辑，吸取人脑的识别特点(tdin)，将计算机中常用的二值逻辑转向连续逻辑。模糊识别的结果是用被识别对象隶属于某一类别的程度，即隶属度来表示的。人工神经网络模式识别 人工神经网络研究源于对生物神经系统的研究。它将若干个处理单元(即神经元)通过一定的互连模型连结成一个网络，这个网络

6、通过一定的机制(如误差后向传播)可以模仿人的神经系统的动作过程，以达到识别分类的目的。 共五十七页句法结构模式识别 着眼于对待识别对象的结构特征的描述。将一个识别对象看成是一个语言结构，例如一个句子是由单词和标点符号(biodinfho)按照一定的语法规则生成的，同样，一幅图像是由点、线、面等基本元素按照一定的规则构成的。 共五十七页9.1.4 模式识别(m sh sh bi)的应用 模式识别已经在天气预报、卫星航空图片解释、工业产品检测、字符识别、语音识别、指纹识别、医学图像分析等许多方面得到了成功的应用(yngyng)。 具体来讲，模式识别在图像处理与分析中的应用可分为以下几个方面： (1

7、) 字符识别 (2) 生物特征识别 (3) 遥感应用 (4) 医学诊断 共五十七页9.2 基于匹配(ppi)的识别技术9.2.1 全局模板匹配为了从图像中确定出是否存在某一目标，可把某目标从标准图像中预先分割出来作为全局描述的模板，然后在另一幅图像中搜索是否有这种模板目标。 设全图像f(x,y)大小为MN，若目标模板是JK大小的w(x,y)，常用相关(xinggun)度量R(x，y)来表示它们之间的相关性：式中，m=0,1,2,M-1;n=0,1,2,N-1。进一步，规格化相关度： 共五十七页 式中设样板所框出范围(fnwi)都是j,k从到J,K计算，而(m,n)则为f(x,y)的MN小区中任

8、一点，式中f1 (x,y)是f(x,y)在(m,n)点框出JK大小的f(x,y)区，当m,n改变时，可搜索到一个R(m,n)最大值, 即为样板配准或匹配的位置。 若图像和目标样板用f和w1向量表示，则相关计算为： 式中w1为w(j-m,k-n)形成的向量。 共五十七页yMxJ(m,n) w(x,y)K在点(m,n)处的全局(qunj)样本相关 共五十七页9.2.2 模板(mbn)向量匹配 若用向量描述样板，则相关匹配可以用求向量差的方法求相关，如用相似度作为样板与图像某子区域的匹配量度。 把图像被JK框出部分(b fen)用向量表示，样板也用向量表示，这时两个向量相似度可用两个向量的向量差为相

9、似度的一种度量，差值D(m,n) 共五十七页 D(m,n)是被搜索到的图像场f(j,k)和样板w(n,j)差。规定一个最小向量差的阈值，若 则说明在(m,n)位置上匹配，应该指出(zh ch)向量仅为JK维。 SSDA法(Sequent Similiarity Detection A1gorithm)： SSDA法用下式计算图像f(x,y)在点(u,v)的非相似度m(u,v)作为匹配尺度，式中(u,v)表示的不是模板中心坐标，而是它左上角坐标。模板的大小为mn。 共五十七页如果在(u,v)处图像中有和模板一致的图案时，则m(u,v)值很小，相反则较大。 在模板和图像重叠部分完全不一致的场合下，

10、如果在模板内的各像素与图像重合部分对应像素的灰度差的绝对值依次增加下去，其和就会急剧地增大。因此，在做加法(jif)的过程中，如灰度差的绝对值部分和超过某一阈值，就认为这位置上不存在和模板一致的图案，从而转移到下一个位置上计算m(u,v)。还有一种把在图像上的模板移动分为粗检索和细检索两个阶段进行的匹配方法。共五十七页粗检索，它不是让模板每次移动一个像素，而是每隔若干个像素把模板和图像重叠，并计算匹配的尺度，从而求出对象物体大致存在的范围(fnwi)。细检索，在粗检索求出的范围内，让模板每隔一个像素移动一次，根据求出的匹配尺度确定对象物体所在的位置。共五十七页9.2.3 特征(tzhng)匹配

11、若图像待识别部分和样板都用特征向量表示，则向量的维数大为减少。例如用不变矩描述(mio sh)时，则f(j,k)和w(j,k)特征向量只有7维，即： X和W向量差可用差向量的范数来表示：若图像中已分割出个目标物，求其中是否有目标物，则只需求出个 选出其中最小的一个j，即为与w相似的图像。共五十七页最小距离分类器 该分类器基于对模式的采样来估计各类模式的统计(tngj)参数并且完全由各模式类的均值和方差确定。 假定有w个类，并给出w个参考矢量(此处具体为均值量) ，在这里将每一个模式 用均值矢量 表示： 式中Nj的为模式类 中的模式数目。对于 的最小距离(jl)分类就是把输入的新模式x分为 类，

12、遵循的分类规则就是x与参考模型原型 之间的距离，与哪一个最近就属于哪一类。共五十七页可采用欧氏距离来确定两者之间的接近程度： 欧氏距离的最小值代表了模式的最佳匹配，所以只要 达到最小值，就将划为第 类。对此，继续对上式进行(jnxng)推导： 从而可得： 于是，可以将 求最小值的问题转化为求下式最大值的问题： 在 取得最大值时，将此时的x划归到第 类。共五十七页9.3 统计(tngj)模式识别统计模式识别主要是根据模式统计特性，采用(ciyng)一系列自动处理技术对给定模式进行大量统计分析，抓取反映模式本质的特征而进行赋值和分类识别处理。 统计识别认为图像可能包含有一个或若干个不同的物体，对于

13、每一个物体都应当属于若干事先定义的模式类之一。 共五十七页统计(tngj)模式识别的过程 统计模式识别方法最终都要归结为分类的问题。如果从某个模式中共抽取N个模式符图像，可以分为m个模式类，那么就可以对N进行分类，进而决定出未知图像属于这m个模式类中的哪一种。对模式的分类主要建立在统计决策理论之上的，而决策理论方法又要用到决策函数。通常可以把识别模式当作是对一个n维模式矢量进行分类，即： 其中 为描述模式表达方式的第i个描述符。 共五十七页 上式代表了一个n维模式矢量，对于给定的m个模式类1，2，3，m，识别过程就是要确定此n维模式矢量是否属于模式类i，以及模式矢量中的每一个 可以划归到哪一个

14、i模式类。该问题也可以转化为对决策函数 的确定，如果模式属于模式类i，就有 从另一个角度考虑：如果将未知模式代入所有(suyu)的决策函数，得到第i个决策函数的计算结果最大，那么就可以将这个未知模式划归到第i个模式类。 共五十七页 在对决策函数进行计算时，不排除出现 的可能。对于这种情况，实际得到的是第i个模式类与第j个模式类的决策边界(binji)，对于决策边界(binji)上的未知模式，可以通过下式对其进行补充判断： 可见，对模式的识别关键在于找到合适的判别函数。 共五十七页9.4 句法(jf)模式识别 所谓句法，是描述语法规则的一种法则。一个完整的句子一定是由主语+谓语或主语+谓语+宾语

15、(或表语)的基本结构构成。一种特定的语言，定类型的句子之间是有定的结构顺序的。 无规则的任意组合，必然达不到正确的思想交流。形容词、副词(fc)、冠词等可以与名词、动词构成“短语”，丰富句子要表达的思想内容。而这些短语的构成也是有特定规律的。 共五十七页句子(j zi)的层状结构 共五十七页自然句法规则的思想可以移植到图像的模式识别中。尽管自然界的景物组合是千变万化的，但仔细分析可以看出(kn ch)：某一对象的结构，也存在一些不变的规则。一座房子由内屋顶和墙面构成。组成屋顶的几何图形，可以是三角形、四边形、圆形等，组成墙平面的几何图形也是由矩形、平行四边形(透视效果)等构成，至少每一个墙面应

16、该有门，而窗的高度不低于门等等。进一步，还可以提出一些用来刻画构成一所房子的规则，如屋顶一定在墙面之上，且由墙面支撑。一所房子这些规则就像构成一个句子的句法规则一样，是不能改变的。共五十七页如果将描述房子的规则(它构成个房子的模式)存于计算机，而我们的任务是要在一张风景照片上去识别有无房子，那么就可按照片上所有景物的外形匹配是否符合房子的模式(房子构成规则)。符合房子模式的就输出为“有房子”，否则(fuz)，输出“无房子”。 句法模式识别是将一个复杂的模式分解成一系列更简单的模式(子模式)，对子模式继续分解，最后分解成最简单的子模式(或称基元)，借助于一种形式语言对模式的结构进行描述，从而识别

17、图像。模式、子模式、基元类似于英文句子的短语、单词、字母，这种识别方法类似语言的句法结构分析。因此称为句法模式识别。 共五十七页句法(jf)模式识别系统框图 共五十七页9.5 模糊(m hu)模式识别方法 常规的分类方法规定一个像素只能属于一个类别，也称为硬分类。 但是在物体的交界处，由于成像过程和数字化过程中分辨率及其他因素的影响(yngxing)，图像中物体边缘处的一个像素可能包含了两个物体的信息。换句话而言，就是这个像素既可能属于类别i，也可能属于类别j，也就是常说的混合像素。 共五十七页模糊模式识别(m sh sh bi)是模糊集理论在模式识别(m sh sh bi)中的一种应用，它认

18、为一个像素是可分的，即一个像素可以在某种程度上属于一个类别，而在另一种程度上属于另一个类别。这种程度通过模糊数学中的隶属函数来表示。具体而言，在进行模糊模式识别时，多根据相似系数和距离来确定各样本之间存在的关系。相似系数越接近于1，则说明样本越接近，距离越小，样本也就越接近，可以将这些比较接近的样本归为一类。 共五十七页对样本间距离的计算可以采用绝对值距离(式1)、欧氏距离(式2)和马氏距离(式3)等几种不同的定义方式：模糊模式识别方法对图像(t xin)进行分类的关键是确定每一个类别的隶属函数。不同类型的图像(t xin)，其隶属函数的计算也不尽相同。一般需要根据具体的应用目的和专业知识来确

19、定。通常在类别隶属度方面选用最大隶属度原则，即以模式的描述属性作为模糊子集，分别计算场景中所有模式隶属于该模糊子集的隶属度，选择其中的最大者作为分类。在实际中，也可以灵活地修改判决规则，使一个像素在分类时可以被同时划分为多个类别。共五十七页9.6 人工神经网络识别(shbi)法9.6.1 BP神经网络图像识别 BP神经网络是反向(fn xin)传播(BackPropagation)法的简称。 其实质是把一组样本输入、输出问题转化为一个非线性优化问题，并通过梯度算法利用迭代运算求解权值问题的一种学习算法。BP神经网络模型 共五十七页BP算法不仅有输入层节点、输出(shch)层节点，还可有1个或多

20、个隐含层节点。对于输入信号，要先向前传播到隐含层节点，经作用函数后，再把隐节点的输出信号传播到输出节点，最后给出输出结果。节点的作用的激励函数通常选取S型函数，如 式中Q为调整激励函数形式的Sigmoid参数。该算法的学习过程由正向传播和反向传播组成。在正向传播过程中，输入信息从输入层经隐含层逐层处理，并传向输出层。每一层神经元的状态只影响下一层神经元的状态。如果输出层得不到期望的输出，则转入反向传播，将误差信号沿原来的连接通道返回，通过修改各层神经元的权值，使得误差信号最小。这一过程实际上就是前向传播和误差后向传播。共五十七页 BP神经网络模式识别包括学习和分类两个阶段，将其用于图像模式识别

21、需要实现步骤如下： （1）网络系统的确定 主要是输入层、隐含层、输出层结点数目的确定，输入层结点数目一般与待分类图像的数据维数或特征向量的元素个数相同，输出层结点数目则与待分的类别数目相同，隐含层结点数目的个数选取则一般依据经验选取。（2）样本数据及控制参数的输入 样本数据中的输入模式一般是图像上各个类别典型区域的灰度值或其他统计特征值，输出模式则是一个二值向量，相应(xingyng)类别的值为1，其他类别的值为0，如假定有4个类别，则第2个类别样本的输出模式为0100。控制参数包括最大循环次数、分类精度、学习因子等。（3）为网络分配内存并初始化权值矩阵 初始权值矩阵可由计算机的随机函数产生，

22、每一矩阵元素的值限定在0，1区间。共五十七页（4）计算各层之间的权系数 应该注意输出层和隐含层的误差和权值调整公式有所不同。（5）判断精度是否达到要求 首先判断单类样本输出层的输出值是否达到了给定的精度要求，如果没有则返回步骤(4)进行权值调整；如果单类精度已满足要求，则判断总的分类精度是否达到要求，若没有则返回步骤4；如果精度达到要求，则继续向下执行。若循环次数巳超过最大循环次数，表明学习没有达到顶期设想，可重新设置参数。（6）分类阶段 网络根据在学习过程中所得到(d do)的网络的权系数矩阵，依次对图像的各个像元进行计算，根据输出结果与每类期望值的对比，将图像的各个像素归为误差最小的一类。

23、 共五十七页一个实例手写体字符识别 用BP神经网络进行手写体数字识别时，整个过程由输入环节、预处理环节、输出环节等三部分组成 1.输入环节及预处理环节输入环节通过扫描仪将数字扫描输入到计算机内部，并以点阵的形式做成数据文件，供处理程序随时调用和处理。预处理环节由数字分离与去污点、压缩变换、细化与特征抽取三部分组成。数字分离与去污点部分相对来说比较(bjio)容易，因为每个数字都是写在一个方框内的，所以采用一般常规方法，即可进行数字分离与去污点。 压缩变换部分是把输入的点阵图形压缩成固定的(3232)点阵形式。因为输入的点阵图形有大有小，所以首先应该去掉多余的信息，而保留有用的信息，使处理后的图

24、形处于一个正方形内，以便于从该正方形变换到另一规格化正方形(3232)时，使畸变达到最小。 最后一步是细化与特征抽取。共五十七页特征提取算法（1） 将(3232)的正方形点阵划分成44的16个子正方形，每个正方形都是(88)点阵，对每个子正方形，从左至右，从上到下的扫描，统计每个子正方形内横向为“1”的点数注意：若(x,y1)=1，(x,y2)=1，(x,y3)=； y1y2y3Yj(ij)时，则Yi为有效(yuxio)输出结果。 各结点的非线性作用函数为S型函数： 共五十七页 隐含层 ： 输出层 ： 以上两式中的 值是不一样(yyng)的，Xi，Xhi分别是输入层和输出层的输入，Wij是第i

25、个结点与第j个结点之间的联接权值， 是第j个结点的阈值，Xj是隐含层的输出，Yj是输出层的输出。 本系统采用的学习规则为delta规则： 式中，ti(t)是期望输出值，ai(t)是实际输出值，Oj(t)为第j个结点的输出值，为学习系数(01)。共五十七页权的修正算法为： 当Opi为输出(shch)层结点输出(shch)时， 当Opi为隐含层结点输出时， 这里(zhl)Wji是某层的第i个结点与上一层第j个结点间的连接权，Opi是第i个结点的输出， 是第j个结点接收到的信息总和， 是第j个结点的输出误差，0是学习系数，yj是输出结点实际计算得到的输出值，tpj是期望的输出值，xj是隐含层结点的输

26、出值。 为了抑制振荡的发生，友增加了一个动量项 ， 即为： ，一般取经验值。在本例中，取=0.9，=0.3时，学习与收敛速度为最佳。共五十七页9.6.2 自组织神经网络的图像识别BP神经网络属于监督学习，在网络训练过程中需要同时(tngsh)提供输入样本和相应的理想输出。自组织神经网络(Self-Organizing Feature Map)是一种基于自组织竞争学习的无监督神经网络。Kohonen神经网络是一种具有侧向联想能力的两层结构自组织神经网络。网络的第一层为输入层，第二层为输出层，也称为竞争层，其神经元的排列可以是一维的，也可以是二维阵列。在每个输入节点与输出节点之间以可变权值进行全连

27、接。在网络中，每个输出节点都有一个拓扑邻域，常用的有正方形和六边形等。邻域的大小与其所包含(bohn)的节点数有关，没有特定的形状，可按实际情况的不同而不同，并随着算法的进程而改变。共五十七页自组织(zzh)神经网络结构以节点(ji din)C为中心的两种形式的邻域共五十七页假设样本空间 是RN中的N维子集。 ， 称为输入矢量，Xkj称为Xk的第j个特征。其中N表示输入空间模式(msh)矢量的维数或特征数，也就是神经网络输入层的神经元个数。输出层由个神经元组成，每个神经元连接权矢量的维数与输入空间模式的特征维数一致。两层之间的动态连接权矢量为： 输入矢量聚类是将X分成C个子域。 为了找到输入空

28、间模式矢量与连接权矢量间的最佳匹配，则对输出空间中所有神经元权矢量与输入空间模式间的距离进行比较，并选择一个最小距离作为最佳匹配的输出神经元。最佳匹配的输出神经元j，也即胜者神经元定义为： 共五十七页 由于胜者神经元对于它周围最近的神经元也会产生(chnshng)一定的兴奋作用，也即在胜者神经元周围存在一个拓扑邻域。在这个拓扑邻域中，胜者神经元本身是这个拓扑邻域中刺激最大的数值点，以它为中心，离它越远的神经元侧抑制作用越强。 一个最简单的核函数为： 上式中 为学习率，其范围为0 1。它和Nj邻域中的半径的形式均定义(dngy)为一个随时间增加而逐渐减小的线性变换。 其中t，T分别为当前和最大迭

29、代次数， 分别为学习率和邻域半径的初始值。共五十七页网络(wnglu)中输出层节点的连接权值要求根据输入矢量进行相应的修改。基于输出层胜者神经元与其周围的兴奋神经元间的邻域关系，其连接权值的修正公式为： 当训练正常结束时，赋予每个输出节点一个连接权值，并确定Kohonen神经网络的网络结构，即建立了一个分类器。然后用该训练好的Kohonen神经网络分类器根据公式 进行图像数据的分类，并根据下式获得待分类模式k属于第j类的可能性程度。 这表示输入模式属于j类的可能性程度为 。其中 。全局最小距离的类别(libi)将有一个可能性程度为1的值，也就是这个可能性程度越高，输入模式就更有可能属于该类。

30、共五十七页9.7 统计(tngj)学习理论和支持向量机识别方法9.7.1 SVM算法(sun f)的基本思想对于两类的情况，假设训练集可被一个超平面线性划分，该超平面集为 。H1、H2分别为过各类中离分类超平面最近的样本且平行于分类超平面的平面，它们之间的距离叫做分类间隔。对于线性可分的情况，可假定 上式可归一化得： H1和H2到H的距离为 , 分类间隔为 。使分类间隔最大，即使 最小的分类面就叫最优分类超平面。而H1和H2上的训练样本点就称作支持矢量(Support Vector)。因此，求最佳(w,b)可归结为二次规划问题：共五十七页最优分类(fn li)超平面共五十七页 上述规划问题的对

31、偶问题，即最大化目标函数： 其解可通过引入Lagrange优化函数求得。 上式中 为与每个样本对应的Lagrange乘子。解中只有一部分(通常是少部分) 不为零，对应的样本就是(jish)支持矢量。 这样， 相应(xingyng)的分类决策函数为：共五十七页对于非线性情况，SVM的基本思想是通过事先确定的非线性映射将输入向量x映射到一个高维特征空间中，然后在此高维空间中构建最优超平面。由于目标函数和决策函数中的向量之间都只涉及点积运算，因此只要采用满足Mercer条件的核函数(Kernel Function), 它就对应某一变换空间中的内积。相应(xingyng)的二次规划问题的目标函数变为： 通常并不需要明确知道 ，只需要选择合适的核函数K就可以确定一个支持(zhch)矢量机。共五十七页9.7.2 SVM算法的分类过程SVM算法的分类过程