第10章-模板匹配与模式识别技术

第10章模板匹配与模式识别技术10.1模板匹配10.2统计模式识别10.3结构模式识别法10.4人工神经网络识别法10.1模板匹配10.1.1模板匹配的原理模板：待识别目标的标准图像，也称为样板。例如：汽车牌照识别中使用的部分模板图像：模板匹配：将模板放在图像上滑动；每滑动一个像素点，求重合区域的相关度（相似程度）；当相关度达到最大时，模板下面的图像就是待识别的目标。模板t(i,j)相关度：设：原图像为f(x,y)，尺寸为M×N。模板图像为t(i,j)，－m≤i≤m,－n≤j≤n。定义：t(i,j)与f(x,y)在(x,y)处的相关度R(x,y)为：mminnjmminnjmminnjjitjyixfjitjyixfyxR22),(),()(),(),(相关度的值在0~1.0之间。相关度为1.0表示完全相同.ijn－n－mm为消除平均灰度的影响，应先作如下处理：Fyxf),(从f(x,y)中减去平均灰度:从t(i,j)中减去平均灰度:Tyxt),(其中，F为模板下面图像的平均灰度;T为模板图像的平均灰度。于是，相关度公式变为：mminnjmminnjmminnjTjitFjyixfTjitFjyixfyxR22]),([]),([])([]),([),(对目标图像灰度规范化mminnjmminnjmminnjmminnjTjitTjitFjyixfFjyixfyxR22]),([])([]),([]),([),(或写为：对样板图像灰度规范化),(),(),(jitjyixfyxR简写为：滑动模板匹配算法：将各个模板规范化；Rm=0；for(x=m;xM-m;x++){//遍历图像上有效区域的所有像素for(y=n;yN-n;y++){对模板下面的图像规范化；计算各个模板在(x,y)点的相关度R；if(RmR){Rm=R;//总是保存较大的相关度xc=x;yc=y;Temp=取得最大相关度的模板编号；}}}结果：Rm为最大相关度；(xc,yc)为最大相关度发生的位置；Temp为取得最大相关度的模板编号。模板匹配识别目标的特点：（1）与目标的大小、旋转、错切有关。解决办法：方法1：匹配前，先矫正目标的大小、旋转、错切；目标的定位、大小、旋转、错切检测必须准确。方法2：准备各种大小、旋转角、错切角的模板，一一进行匹配；模板的数量极大，实际中难以应用。（2）具有较强的抗干扰能力。若匹配前目标的大小、旋转、错切矫正良好，则对模糊、污损字符也能较好地识别。10.1.2模板匹配方法的改进问题：模板匹配计算量很大：模板数量多。例如：汽车牌照识别中，有上百个（字符、汉字）；在每一像素位置都要计算一个相关度。解决办法：（1）SSDA方法——序贯相似性检测法在求相关度之前，先求模板与图像之间的灰度差：mminnjjitjyixfyxD|),(),(|),(若D(x,y)较大，则该位置不可能是目标。否则，该位置可能是目标，再进一步计算相关度。因为差值计算量较小，且大部分位置不存在目标，故速度大大提高。（2）两步检测法——先粗检测，再精检测。每隔几个像素检测一次，目标一般在相关度较高的位置附近。再在相关度较高的位置附近进行精检测。（3）边缘匹配法应采用边缘型模板。先抽取图像的边缘。在相关度计算时，仅考虑边缘点。因边缘点较少，故计算量大大减少。（4）局部匹配法先对模板上的一部分作匹配。当匹配程度较高时，再考虑全部模板匹配。否则放弃。10.2统计模式识别10.2.1统计模式识别的基本思想（1）生成样本库特征参数提取输入样板图像特征参数优化得到样本库，备用。每个样板图像都有一组特征参数。（2）对待识别的目标图像，按同样的算法，得到优化后的特征参数特征参数提取输入待识别图像特征参数优化得到一组特征参数提取特征参数输入样板图像特征参数优化（3）设计一个分类器，对待识别图像分类，判别待识别图像的特征参数属于样本库中的哪一个。提取特征参数输入待识别图像特征参数优化分类器识别结果特征参数是表征图像的一组参数，例如，下列参数可作为特征参数：Hu矩组：(M1,M2,M3,M4,M5,M6,M5)对图像作傅立叶变换得到的主要系数：(F00,F01,F02,F03,F10,F11,F12,F13,F20,F21,F22,F23,F30,F31,F32)图像的傅立叶描述子：(a0,a1,a2,a3,a4,a5,b1,b2,b3,b4,b5)……样板图像的特征参数称为样本。不同的样板图像有不同的样本值。通过提取特征参数，使表示图像的数据大大减少。10.2.2特征参数提取10.2.3特征参数优化（1）特征参数选择从m个特征参数中，选出n(nm)个区分性、独立性、可靠性好的特征。例：以直线穿越字符笔画的次数作为特征参数，如下表。l12121111122l22111221112l32121122121l42133233233l51000101021l1l2l3l4在5个特征中选择4个，有5种选法。究竟选哪种好？从独立性看——去掉l2或l3均可；从区分性看——去掉l2较好。因l3中的数据有较大的熵。l5是孔数（2）特征参数变换特征参量实际上是一个多维空间的矢量。记为例：上例中，剩下的4个特征参量记为：),,,(5431llllX这是4维空间的矢量。每个样本对应此4维空间的一个矢量。对于字符“0”，X=（2,2,2,2,1)由线性代数可知，可以通过线性空间的线性变换，使这10个样本矢量之间的相关性减少。),...,,(21nxxxX10.2.4统计分类1统计分类的基本概念找到一个判别函数a(X)，能有效地将待识别目标的特征矢量X划分为几类。即：当输入特征矢量X时，a(X)的输出为X所属的类。……x1x2xn样本输入判别函数a(X)输出类号统计分类分为监督分类和非监督分类。2监督分类法利用现有的样本矢量，对各种判别函数进行试验，当某判别函数能将各样本在特征空间划分开来，且各类样本之间的距离最大时，该函数就是希望的判别函数，可作为实际识别中采用的判别函数。上述试验过程称为“学习”，学习的目的是选择一个最佳的判别函数。g1g2gn…………x1x2xn输入样本X判别函数集max选择a(x)a(x)特征空间类别3类别1类别2常用判别函数（1）距离函数设两矢量分别为：),...,,(),,...,,(2121nnyyyYxxxX则X和Y之间的距离为：niiiyx1||欧几里德距离：L距离：2/112)(niiiyx相关度：YXYX距离越大（或相关度越小），表示两矢量的差别越大。用距离函数可计算样本类之间的距离。有两种计算方法。最小距离各类之间的距离最近邻距离各类中最靠近的样本之间的距离类别3类别1类别2d12d13d23最小距离类别3类别1类别2d12d13d23最近邻距离（2）线性判别函数g(X)=a·X+b是多维空间的平面。只能将各样本划分为两类，用于2类识别问题。类别1类别2线性判别a·X+b3统计决策理论——贝叶斯(Bayes)决策引例：设在模板匹配的汽车牌照识别中，因字符模糊，求得第1字符为“湘”的相关度为0.79；为“浙”的相关度为0.80。因相关度接近，不能判定是二者中的哪一个。但是，如果在湖南，判定为“湘”的正确度要远远高于“浙”；反之，如果在浙江，判定为“浙”的正确度要远远高于“湘”；贝叶斯决策的基本思路：设要将目标X分成m类，类的编号为：由大量统计知，X属于第i类的概率由计算求出，X属于第i类的概率则将X划分为第i类的正确度(似然度)取似然度值最大的划分作为分类结果。m,...,,21miPi,...,2,1),(miXpi,...,2,1),|()()|(iiPXp在引例中，假设在湖南长沙统计知：出现“湘”的概率出现“浙”的概率计算出：X属于“湘”的概率X属于“浙”的概率则：将X划分为“湘”的似然度将X划分为“浙”的似然度分类结果：X属于“湘”6.0)(1P05.0)(2P79.0)|(1Xp80.0)|(2Xp0.47479.06.00.0480.005.0要使用似然法，必须先求出和)(iP)|(iXp)(iP可由大量统计数据获得，称为先验概率；)|(iXp问题：函数是什么函数？假定：为正态分布函数：计算概率的函数。算出待识别目标X属于第i类的概率。)]()()(21exp[||1)2()|(12/iiTiiniUXUXXp其中：Ui是第i类样本矢量的平均矢量。是第i类样本的协方差矩阵，是的逆矩阵，是的行列式值。i1)(ii||ii)|(iXp)|(iXpT(...)是矢量或矩阵的转置运算。Bayes分类操作步骤：①由大量实际数据统计出各类目标出现的概率；②采集一批样本，提取各样本的特征，由特征求出计算实际目标属于样本中的哪一类的概率函数；③对实际目标进行分类：计算似然度：分类判别式：取似然度最大者。)(iP)|(iXp)()|(iiPXp似然法的特点：要求各类样本的特征矢量形成正态分布。否则将产生分类错误。10.3结构模式识别法当我们提取到目标的特征矢量后：按上面讨论的分类方法，是让特征矢量的各个分量一齐参加分类。结构模式分类法，研究组成特征矢量的各个分量的构造机制，按结构层次逐步推理，最后实现将目标归到某一类。结构模式分类法内容丰富，本节介绍文法（句法）和树分类法。10.3.1文法（句法）用形式语言（数理语言）来描述目标。引例：用形式语言描述字符“A”和“4”定义符号集{a,b,c,d}abcd重写规则集（产生式集）P={p1,p2,p3,p4}p1：S→cdAorcbBp3：B→aBp2：A→acdp4：B→b其中，S称为起始符，A、B称为中间符。用产生式生成句子（描述目标）产生“A”：{p1,p2}S→cdA→cdacd产生“4”：{p1,p3,p3,p4}S→cbB→cbaB→cbaaB→cbaabaccddcaabb产生式系列就描述了目标。（1）文法识别目标的操作步骤：①提取样本的特征矢量，定义符号集。如{a,b,c,d}②由特征矢量制订描述各个样本的产生式系列制订重写规则集。完备性，可行性。优化重写规则集。删除、合并某些规则，使中间符最少。对每个样本写出产生式系列③识别目标提取待识别目标的特征矢量由重写规则写出产生式系列由产生式系列判定目标（2）文法识别目标的特点：由于干扰（如笔画断裂、粘连等），待识别目标的产生式系列中可能出现缺少、多余的项，甚至超出重写规则范围。（例如：不存在的单词）研究重写规则的抗异常能力、如何分辨和处理产生式系列中的非正常项，是当前的关键问题。10.3.2树分类法用树描述目标。引例：用树描述字符分类l12121111122l32121122121l42133233233l5100010102121n1n3122n21n4n5n6n7l1l3l4n8n9l51n122“0”“1”2“9”n113n18n1720“2”“8”3n13n100“7”“4”n141“3”n15n1601“5”“6”（2）树分类法的操作步骤：①提取样本的特征矢量，定义符号集。如{l1,l2,l4,l5}②由特征矢量构造分类树③识别目标树分类法识别目标的特点：由于干扰（如笔画断裂、粘连等），待识别目标可能出现缺少、多余的项，以至在树中无对应的路径，造成无法识别研究分类树的抗异常能力、如何分辨和处理非正常路径，是当前的关键问题。10.4人工神经网络识别法人工神经网络是一种特殊构造分类器，其输入为待识别目标的特征矢量，输出为分类号。人工神经网络x1x2xny……输入输出待识别目标X=（x1,x2,…,xn)分类结果y=f(X)当输入X后，在网络内部进行计算，计算结果为分类号。因此，人工神经