CN105825203B - 基于点对匹配和几何结构匹配的地面箭头标志检测与识别方法 - Google Patents

Abstract

本发明属于计算机视觉领域，涉及到图像处理相关知识，特别涉及形状匹配方法。其特征是从待测视频中提取出地面箭头标志进行识别。首先，利用逆投影映射来获得每一帧图像的俯视图；其次，使用K均值聚类方法在HSV空间进行图像分割，分离出亮度及颜色符合条件的连通区域，并对这些连通区域进行几何尺寸筛选；再次，对候选区域进行边缘提取，对每个边缘点提取局部多尺度HOG特征；最后利用该特征在模板和候选区域之间进行点对匹配，对匹配结果再进行几何结构匹配，识别出该区域的类别。本发明的效果和益处是克服了地面箭头标志检测中出现的遮挡、磨损、形变、旋转，以及其他标志干扰的情况。在以上不理想条件下，本发明仍有较好的识别率。

Description

基于点对匹配和几何结构匹配的地面箭头标志检测与识别 方法

技术领域

本发明属于计算机视觉领域，涉及图像处理中的相关知识，特别涉及一种基于点对匹配和几何结构匹配的地面箭头标志检测与识别方法。

背景技术

在过去的二十多年里，地面交通标志识别作为无人驾驶和智能交通的重要组成部分，吸引了许多计算机视觉领域的研究者。因此，出现了很多高效且实用的技术及方法。在这些标志中，地面箭头标志包含了重要的道路交通信息，所以对这类标志的检测与识别显得尤为重要。下面将从2004年开始陆续发表的具有代表性的文章描述如下。

Rebut,J.等人在“Image segmentation and pattern recognition for roadmarking analysis.In International Symposium on Industrial Electronics,2004”文中通过傅里叶算子来描述提取出的候选区域，并结合KNN分类器来对候选区域进行识别。但是，傅里叶算子对候选区域的轮廓完整性要求很高，所以该方法不适用于有遮挡和候选区域损坏严重的情况。Suchitra，S.等人在文章“A practical system for road markingdetection and recognition.In TIP，2009”首先将候选区域分解成几块，利用在x和y方向上的梯度值大小以及正负将边缘分段。然后对每段边缘分别进行霍夫变换，并对得到的霍夫空间进行峰值分析，得到边缘的角度信息，判断出每段边缘是向左倾斜还是向右倾斜。接下来又将模板分块，对每一块的左边缘和右边缘的倾斜方向进行了总结，并根据总结出的结果对候选区域进行检测，找出满足条件的图像块，并对这些图像块进行组合，判断是否是箭头标志并分类。但是该方法主要依赖于箭头标志边缘的完整性，所以对于出现磨损的箭头标志识别效果不好。

Yuhang He等人在文章“Using edit distance and junction feature todetect and recognize arrow road marking.in Intelligent Transportation Systems(ITSC),2014”中提出了一个节点特征，将每个候选区域表示为一个节点串，并根据每个节点的位置和夹角进行编码。然后利用编码结果计算候选区域与模板图像的相似性。该方法将箭头标志的局部结构与整体结构结合在一起，对磨损和遮挡的鲁棒性较高，但是对于出现整体形变的箭头标志识别率较低。

发明内容

针对现有技术的不足，本发明提供一种基于点对匹配和几何结构匹配的地面箭头标志检测与识别方法，该方法在车载摄像头拍摄的视频有其他车辆对地面箭头标志部分遮挡的情况、地面箭头标志距离汽车过远而发生形变的情况和汽车行驶方向的改变使得提取出的箭头标志发生倾斜的情况下，视频中含有其他地面交通标志时(车道线，斑马线等)，能够正确检测出地面箭头标志，并且对其准确而快速的分类。

为了达到上述目的，本发明的技术方案是：

一种基于点对匹配和几何结构匹配的地面箭头标志检测与识别方法，该方法利用逆投影变换方法对车载视频的每一帧进行处理，来获取道路场景的俯视图。依据地面交通标志与地面的亮度差异，利用K均值聚类方法在俯视图的HSV空间进行聚类来提取亮度及饱和度符合条件的连通区域。利用箭头标志的常规尺寸对连通区域进行筛选，获得箭头标志候选区域，完成箭头标志检测。在识别阶段，本发明提出了一种点对匹配和几何结构匹配相结合的识别方法，充分利用了箭头标志的局部和整体的形状信息。在实际道路上，直行左右转标志和直行左转标志很少存在，而且左转标志和右转标志是对称的，只需对其中之一进行检测与识别，因此本发明只对直行标志(S)，左转标志(L)和直行右转标志(SR)进行检测与识别。图1为本发明的系统框图。具体实现步骤包括：

第一步，逆投影映射

由于车载摄像机拍摄视频的视角问题，获取的地面交通标志存在严重的透视变形，这会影响对箭头标志的识别效果。为了消除这种影响，在本发明中首先对每一帧道路图像进行逆投影映射处理，获取道路场景的俯视图，避免地面交通标志发生严重形变。我们采用三线法实现逆投影映射，首先建立车体坐标系和摄像机坐标系。在世界坐标系中，X_v指向汽车纵轴的前方，Y_v指向垂直于汽车纵轴的右方，Z_v指向垂直于汽车纵轴的上方。设地面平坦，摄像机坐标系原点在摄像机的光心，依次绕X_v、Y_v、Z_v轴的旋转角为ψ、和θ。光心在车体坐标系中的坐标为t＝(l,d,h)。若车体坐标系中有一点为p_v(x_v，y_v,z_v)，它在摄像机坐标系中的坐标为p_c(x_c,y_c,z_c)，二者之间的关系为：

其中，可以看出，如果要实现逆投影映射，需要计算出ψ、θ以及

t＝(l,d,h)六个外参数。

对于平坦地面上任意一条平行于X_v轴，且到其距离为a直线L，其在车体坐标系中的参数方程为x_v＝s,y_v＝a,z_v＝0，其中s为任意实数。根据针孔成像模型，结合公式(1)，直线L在图像平面坐标系上的参数方程为：

其中，d_x，d_y分别为横向和纵向的比例系数(摄像机内参数)；u和v为图像平面坐标系的坐标；i和j为像素坐标系的坐标；f_i和f_j分别为i和j方向的焦距(摄像机内参数)。直线在图像坐标系上存在消失点(u_h,v_h)

若地面上有三条平行于L的直线，那么这三条直线有相同的消失点。我们利用这种等量关系，，在已知摄像机内参数的情况下，就可以得到外参数ψ、θ以及t＝(l,d,h)。将外参数ψ、θ以及t＝(l,d,h)代入公式(3)，找到车体坐标平面上的点在图像坐标上的对应点，实现图像坐标平面向车体坐标平面的转换，完成逆投影映射，获取道路场景的俯视图。

第二步，图像分割

理想情况下，地面箭头标志为白色连通区域且与地面有明显的亮度差。但是，由于遮挡和其他区域的干扰，很难采用设定阈值的二值化方法将这些区域提取出来。为了避免地面箭头标志亮度信息的丢失，本发明采用了在特定颜色空间进行K均值聚类的方法来对图像进行分割。聚类是一种将目标分组的方法。K均值聚类认为每一个目标都有自己的空间位置，对这些目标分区的原则是：离所在聚类中的目标空间位置尽可能近，离其他聚类中的目标空间位置尽可能远。K均值聚类需要提前指定聚类数量和衡量两个目标空间位置远近的距离测度。

由于HSV颜色空间是近似的均匀颜色空间，相对于RGB空间，它更符合人类视觉系统，HSV颜色空间两点的欧氏距离与人的感知程度近似成正比。在HSV颜色空间中，饱和度分量S与亮度分量V能够分别描述图像颜色特征和形状特征，且两个分量是独立的，亮度分量V与图像的色彩信息无关。因此，在本发明中将RGB彩色图像转换到HSV颜色空间，将饱和度分量S和亮度分量V重组，再对重组图像进行K均值聚类对图像进行分割,利用欧式距离测度将图像分割为三层，满足要求的像素点最多的那一层为最终分割结果，并将其中包含的连通区域作为候选区域，其中一层包含了所有颜色饱和度及亮度满足条件的连通区域。

第三步，候选区域筛选

在我国，地面交通标志的尺寸大小需要满足国家统一标准。在本发明中，我们利用几何尺寸参数对候选区域进行筛选。由于箭头长度会受距离影响而产生畸变，我们只选取了箭头宽度，宽高比以及面积来排除非箭头区域。但在实际路况中，箭头标志会由于遮挡等因素而不完整，因而我们没有严格按照国家标准尺寸进行筛选，而是选取标准尺寸附近的一定区间作为筛选准则。

第四步，边缘检测

连通区域的边缘包含了它大部分几何信息，因此我们用边缘来表示上一步筛选出的候选连通区域。由于连通区域的边缘会出现毛刺以及图像中不可避免的噪声会对后续的匹配结果造成影响，所以我们对候选区域进行了膨胀操作，减少边缘毛刺，并选取可以有效抑制噪声且边缘定位精确的Canny边缘检测算法，对候选区域进行Canny边缘检测，获取较为平滑的边缘。该算法对信噪比与定位乘积进行测度，可以得到最优化逼近结果。因此，该边缘检测方法可以很好的解决提取出的候选区域边缘存在毛刺的问题。

第五步，特征提取及构建特征集

边缘点包含的局部形状信息可以通过特征来描述。采用了一个局部多尺度HOG特征来对连通区域边缘进行描述。矩形HOG块的划分：一个图像块(Block)由若干单元(Cell)组成，一个单元由若干个像素点组成。在每个单元中独立地做梯度方向统计，所得的直方图以梯度方向为横轴，梯度方向可取0～180度或0～360度，对于本发明中地面箭头标志检测选取0～180度能够取得更好的结果。再将这个梯度范围平均分成几个方向子区间(orientation bin)，每个方向区间都会对应一个直方柱。本发明中，我们使用9个子区间。

局部多尺度HOG特征是指以上一步提取的边缘点为中心，选取几个尺度的矩形块进行梯度方向统计，得到局部的不同尺度的HOG特征向量，并将这些特征向量组合在一起，这个组合的特征向量包含了边缘点处丰富的局部特征。特征提取及构建特征集具体步骤为：

5.1)在边缘点处进行局部的HOG特征提取，对所有边缘点计算梯度方向，选取任一边缘点A，截取以边缘点A为中心，大小为a×a的图像块，将该图像块平均分成4个单元；将梯度方向取值范围平均分成k个子区间，得到4×k＝4k维局部HOG特征向量；

5.2)取以边缘点A为中心，大小为2a×2a的图像块，将图像块平均分为4个a×a的子块，分别对每个子块按照5.1所述方法计算出4k维特征向量，将四个4k维特征向量串接起来得到4k×4＝16k维局部HOG特征向量；

5.3)截取以边缘点A为中心，大小为4a×4a的图像块，将图像块平均分为16个a×a的子块，分别对每个子块按照5.2所述方法计算出16k维特征向量，将四个16k维特征向量串接起来得到16k×4＝64k维局部HOG特征向量；

5.4)将上述三个尺度下的局部HOG特征向量串接起来，形成边缘点A的4k+16k+64k＝84k维特征向量，并用这个84k维特征向量表示该连通区域；

5.5)构造模板库包含直行标志S，左转标志L和直行右转标志SR；对于模板库中的箭头图像和测试图像中的候选区域，均按照上述步骤得到边缘点及每一个边缘点对应的84k维特征向量；候选区域所有边缘点对应的特征向量构成该候选区域的特征向量集；模板图像的所有边缘点对应的特征向量构成该模板的特征向量集。

为了实现箭头标志匹配，我们构造了一个模板库。这个模板库包含了六种地面箭头标志，包括左转、右转、直行、直行左转、直行右转和直行左右转。对于模板库中的所有箭头标志都需要进行上述边缘检测和特征提取两个步骤，且提取出的特征向量组成特征集，用于后续的匹配过程。

第六步，点对匹配

对于每一个测试图像，都进行了上述步骤来获取候选区域及其边缘，并且对每一个候选区域边缘进行特征提取，得到对应的特征向量。一幅测试图像中的每一个候选区域需要与模板库中所有的模板进行匹配。在本发明中，我们首先利用边缘点的特征向量进行点对匹配，筛选出具有相同局部结构的边缘点，排除异常点，提高进一步匹配的效率。

首先，假设候选区域和某一模板分别提取出了M和N个边缘点，每一个边缘点都对应一个特征向量，我们构造了一个M×N矩阵D存储两组特征向量之间的欧氏距离，欧式距离代表了两个特征向量之间的差异。其中，D矩阵的元素di,j保存着候选区域的第i个边缘点对应的特征向量和模板图像的第j个边缘点对应的特征向量之间的欧氏距离。接下来，利用欧式距离矩阵D来进行点对匹配。假设D_i是矩阵D的第i行，D_i中的元素按照升序排列得到向量D’_i中相邻两个元素之比构成向量R＝[r₁,…,r_j,…,r_N-1]，即如果在R中r_k是第一个大于预设阈值α的值，那么D'_i中前k个值对应的模板图像边缘点即为与候选区域第i个边缘点匹配的点。以此类推，对D的每一行都进行该操作，就可以在测试图像上找到与每一个候选区域边缘点匹配的点，形成从候选区域到模板图像方向的匹配点对。这种匹配方法是双向的，因此我们对D每一列也进行同样处理，得到从模板图像到候选区域方向的匹配点对，这两组匹配点对的交集形成了匹配点对集，这就是点对匹配的最终结果。这个匹配点对集将用于几何结构匹配。

第七步，几何结构匹配

上一步的点对匹配提高了进一步匹配的有效性，但是候选区域可能和模板库中多个模板都具有相同的局部结构，所以点对匹配不能准确的给出识别结果。在本发明中，我们将在点对匹配的基础上进行几何结构匹配，对这些点对构成的整体几何结构进行分析，准确的识别出候选区域的类别。

上一步得到的匹配点对集包含了候选区域和所有模板图像之间的匹配点对，匹配点对中的点一半存在于候选区域，一半存在于模板图像。这两组点分别在测试图像和模板图像中形成了两个散点图。散点图的几何中心为c，由点坐标的均值计算得来。假设p_i和p_j为一个散点图上的任意两点，d(p_i,c)和d(p_j,c)分别代表向量和的长度，θ_ij是两个向量的夹角(θ_ij∈[0,π])。我们利用两个K₀×K₀下三角矩阵来代表包含K₀个点的散点图，这两个矩阵定义为：

G＝{g_ij|i∈[1,K₀-1]；j∈[0,i-1]} (6)

Θ＝{θ_ij|i∈[1,K₀-1]；j∈[0,i-1]} (7)

其中，g_ij＝min(d(p_i,c)/d(p_j,c),d(p_j,c)/d(p_i,c))。显然，两个矩阵对于旋转和尺度具有不变性，只受散点图的几何结构影响。

G_c和G_t分别为候选区域和模板图像的G矩阵，Θ_c和Θ_t分别为候选区域和模板图像的Θ矩阵。我们利用Θ_c和Θ_t中元素的差值来对G_c和G_t进行滤波，使得一些异常的匹配点对可以被排除。滤波原则如下：

其中，γ为通过实验设定的阈值。在本发明中采用了欧式距离来衡量和的差异：

其中，s为矩阵非零元素的个数。假设在模板库中有K个模板图像，任一候选区域都与这K个模板图像计算得到一个e值，这些值中的最小值如果小于预设的阈值，则这个最小值对应的模板图像就认为和候选区域是相同类别。阈值的设定对不同模板是不同的，均是通过实验得到的。

本发明的有益效果为：克服了在地面箭头标志检测与识别过程中经常出现的遮挡，形变和旋转等情况，且识别率较高。

附图说明

图1是系统框图；

图2(a)是初始图像；图2(b)是逆投影变换后的俯视图；图2(c)K均值聚类后的二值图像；

图3(a)多个箭头同时出现时检测与识别结果图；图3(b)箭头磨损时检测与识别结果图；图3(c)箭头严重形变时检测与识别结果图；图3(d)箭头倾斜时检测与识别结果图；图3(e)其他地面标志干扰时检测与识别结果图。

具体实施方式

步骤一：在实际道路上，直行左右转标志和直行左转标志很少存在，而且左转标志和右转标志是对称的，只需对其中之一进行检测与识别，因此本发明只对直行标志(S)，左转标志(L)和直行右转标志(SR)进行检测与识别。

步骤二：假设摄像机前方的道路是平坦的，I＝{(u,v)}∈E²代表获取的初始图像，V＝{(x_v,y_v,z_v)}∈E³代表逆投影变换后的图像。我们想要得到的场景俯视图为W＝{(x,y,0)}∈V。逆投影映射的过程可以看做从图像坐标平面向车体坐标平面的转换，即不同的坐标位置表示同一场景。在本发明中，我们设置了一个感兴趣区域(车体坐标系近车1/2区域)，由公式(1)和(2)可以得到变换后的图像W。W中像素点的像素值等于I中相关像素点的像素值，如果W中像素点在I中对应位置超出了获取的图像范围，那么W中该像素点将设置为黑色。如图2(b)所示，逆投影变换后可以获得原图像的俯视图。

步骤三：HSV颜色空间两点的欧氏距离与人的感知程度近似成正比，并且其有个重要的特征：亮度分量V与图像的色彩信息无关，即HSV颜色空间的图像的饱和度和亮度之间具有相对独立的特征，因此在本发明中首先将RGB彩色图像转换到HSV颜色空间上，取出其中的V层和S层重组成一个两通道图像，对这个重组图像进行K均值聚类。本发明中，我们将分割层数设置为3，采用欧式距离测度进行3次聚类得到了最优的聚类效果。最后选取了像素值大于200的像素点最多的那一层为最终分割结果，并将其中包含的连通区域作为候选区域。该方法充分利用了地面箭头标志与地面的亮度差异以及颜色信息来检测视频每一帧图像中的候选区域。

步骤三：分割后的图像里包含了许多连通区域，为了对这些连通区域进行筛选，我们求取了每个连通区域的宽度，宽高比以及面积，然后按表1的步骤对这三个量进行初步的筛选。如图2(c)所示，经过K均值聚类及几何尺寸参数筛选后，得到了包含所有候选区域的二值图像。

表1候选区域筛选

步骤四：为了使提取出的边缘更加平滑，我们对候选区域进行了膨胀操作，减少了毛刺等干扰。然后对候选区域进行了Canny边缘检测，获取了较为平滑的边缘。

步骤五：对上一步检测出的所有边缘点计算梯度方向，选取任一边缘点A，首先截取以边缘点A为中心，大小为16×16的图像块，将该图像块平均分成4个单元，将梯度方向平均划分为9个子区间，这样就会得到4×9＝36维HOG特征向量。然后再截取以边缘点A为中心，大小为32×32的图像块，再将图像块平均分为4个16×16的子块，每个子块再分为4个单元，计算每个单元的4×9＝36维局部特征向量，将四个特征向量串接起来，这样可以得到36×4＝144维特征向量。以边缘点A为中心选取64×64的图像块，将图像块平均分为4个32×32的子块，分别对每个子块按照上述方法计算出36×4＝144维特征向量，将四个144维特征向量串接起来得到36×4×4＝576。最后将这三个尺度下的局部HOG特征串接起来，形成该边缘点的756维特征向量。

步骤六：对于模板库中的箭头图像和测试图像中的候选区域，均需要按照上述步骤得到边缘点及每一个边缘点对应的756维特征向量。候选区域所有边缘点对应的特征向量构成了该候选区域的特征向量集，同样地，一个模板图像的所有边缘点对应的特征向量构成了该模板的特征向量集。接下来，每一个候选区域都需要与模板库中的所有模板进行点对匹配，来选取模板集中与候选区域具有相同局部结构的边缘点。我们按照表2的步骤进行点对匹配。

表2点对匹配

步骤七：上一步得到的匹配点有一半属于候选区域，并在候选区域处形成散点图，同样地，另一半边缘点在模板图像上形成了散点图。接下来，我们将对候选区域处的散点图和每个模板的散点图进行几何结构匹配。计算散点图上任意两点的夹角θ_ij和到中心的距离比g_ij，并根据公式(6)和(7)构造矩阵G和Θ。这样我们可以分别得到候选区域的两个矩阵G_c和Θ_c，以及模板图像的G_t和Θ_t。然后，我们利用Θ_c和Θ_t中元素的差值按照公式(8)和(9)对G_c和G_t中的元素进行筛选，若夹角之差大于90度，就认为这两组匹配点对异常。最后对经过筛选的G_c和G_t矩阵求取欧式距离，这一步操作在候选区域和每一个模板图像之间进行，欧氏距离最小值若小于阈值，该距离对应的模板认为与候选区域类别相同，否则候选区域为非箭头标志。

图3为本发明中在不同情况下对地面箭头标志检测和识别的结果，我们的方法可以处理多箭头同时出现的情况、箭头标志磨损、箭头标志整体形变、箭头标志旋转，以及其他地面标志干扰的情况。同时，在以上不理想条件下，本发明仍有较好的识别率。

Claims (1)

1.一种基于点对匹配和几何结构匹配的地面箭头标志检测与识别方法，其特征在于，该地面箭头标志检测与识别方法只对直行标志S，左转标志L和直行右转标志SR进行检测与识别，包括如下步骤：

第一步，逆投影映射

1.1)在世界坐标系中，X_v指向汽车纵轴的前方，Y_v指向垂直于汽车纵轴的右方，Z_v指向垂直于汽车纵轴的上方；设地面平坦，摄像机坐标系原点在摄像机的光心，依次绕X_v、Y_v、Z_v轴的旋转角为ψ、和θ；光心在车体坐标系中的坐标为t＝(l,d,h)；若车体坐标系中有一点为p_v(x_v,y_v,z_v)，它在摄像机坐标系中的坐标为p_c(x_c,y_c,z_c)，二者之间的关系为：

其中，

1.2)对于平坦地面上任意一条平行于X_v轴，且到X_v轴距离为a的直线L，其在车体坐标系中的参数方程为x_v＝s,y_v＝a,z_v＝0，其中s为任意实数；在已知摄像机内参数的情况下，直线L在图像平面坐标系上的参数方程为：

其中，d_x、d_y、f_i和f_j为摄像机内参数，d_x为横向比例系数，d_y纵向比例系数，f_i为i方向焦距，f_j为j方向焦距；u和v为图像平面坐标系的坐标；i和j为像素坐标系的坐标；

1.3)在路面上再选取两条直线，使其平行于直线L，分别根据公式(4)(5)计算直线L和这两条直线在图像坐标系上的消失点(u_h,v_h)：

这三条直线有相同的消失点，利用等量关系，计算外参数ψ、θ以及t＝(l,d,h)；

1.4)将外参数ψ、θ以及t＝(l,d,h)代入公式(3)，得到车体坐标平面上的点在图像坐标上的对应点，实现图像坐标平面向车体坐标平面的转换，完成逆投影映射，获取道路场景的俯视图；

第二步，图像分割

将RGB彩色图像转换到HSV颜色空间，将饱和度分量S和亮度分量V重组进行K均值聚类，利用欧式距离测度将图像分割为三层，满足要求的像素点最多的那一层为最终分割结果，并将其中包含的连通区域作为候选区域；

第三步，筛选候选区域

采用箭头标志标准尺寸对候选区域进行筛选，采用箭头宽度，宽高比以及面积排除非箭头区域；

第四步，边缘检测

对候选区域进行膨胀操作，减少边缘毛刺；对候选区域进行Canny边缘检测，获取较为平滑的边缘；

第五步，特征提取及构建特征集

5.1)在边缘点处进行局部的HOG特征提取，对所有边缘点计算梯度方向，选取任一边缘点A，截取以边缘点A为中心，大小为a×a的图像块，将该图像块平均分成4个单元；将梯度方向取值范围平均分成k个子区间，得到4×k＝4k维局部HOG特征向量；

5.2)取以边缘点A为中心，大小为2a×2a的图像块，将图像块平均分为4个a×a的子块，分别对每个子块按照5.1所述方法计算4k维特征向量，将四个4k维特征向量串接起来得到4k×4＝16k维局部HOG特征向量；

5.3)截取以边缘点A为中心，大小为4a×4a的图像块，将图像块平均分为16个a×a的子块，分别对每个子块按照5.2所述方法计算出16k维特征向量，将四个16k维特征向量串接起来得到16k×4＝64k维局部HOG特征向量；

5.4)将上述三个尺度下的局部HOG特征向量串接起来，形成边缘点A的4k+16k+64k＝84k维特征向量，并用这个84k维特征向量表示该连通区域；

5.5)构造模板库包含直行标志S，左转标志L和直行右转标志SR；对于模板库中的箭头图像和测试图像中的候选区域，均依次按照上述步骤5.1)、5.2)、5.3)、5.4)得到边缘点及每一个边缘点对应的84k维特征向量；候选区域所有边缘点对应的特征向量构成该候选区域的特征向量集；模板图像的所有边缘点对应的特征向量构成该模板的特征向量集；

第六步，点对匹配

6.1)候选区域和某一模板分别提取出了M和N个边缘点，构造一个M×N矩阵D，存储候选区域和模板图像特征向量之间的欧氏距离；D_i是矩阵D的第i行；D_i中的元素按照升序排列得到D'_i中相邻元素之比构成R＝[r₁,…,r_j,…,r_N-1]，即如果在R中r_k是第一个大于预设阈值α的值，那么D'_i中前k个值对应的模板图像边缘点即为与候选区域第i个边缘点匹配的点；

6.2)对矩阵D的每一行都按照步骤6.1)进行处理，得到模板图像上与每一个候选区域边缘点匹配的点，形成从候选区域到模板图像方向的匹配点对；

6.3)对矩阵D的每一列都按照步骤6.1)进行处理，得到从模板图像到候选区域方向的匹配点对；对行和列的匹配结果取交集，完成模板图像与候选区域的点对匹配；

第七步，几何结构匹配

点对匹配结果分别在模板图像和测试图像上形成散点图，计算散点图上任意两点的夹角θ_ij和到中心的距离比g_ij，构造两个K₀×K₀下三角矩阵来代表包含K₀个点的散点图：

G＝{g_ij|i∈[1,K₀-1]；j∈[0,i-1]} (6)

Θ＝{θ_ij|i∈[1,K₀-1]；j∈[0,i-1]} (7)

G_c和G_t分别为候选区域和模板图像的G矩阵，Θ_c和Θ_t分别为候选区域和模板图像的Θ矩阵；我们利用Θ_c和Θ_t中元素的差值来对G_c和G_t进行滤波，排除异常点，得到和

采用欧式距离来衡量候选区域的矩阵与所有模板图像的矩阵的差异性，其中若欧式距离最小值小于预设的阈值γ，则对应的模板图像就认为和候选区域是相同类别。