介绍
模板匹配是一个图像处理问题，当其姿态（X，Y，θ）未知时，使用另一张搜索图像中的模板图像找到对象的位置。在本文中，我们实现了一种算法，该算法使用对象的边缘信息来识别搜索图像中的对象。
背景
由于其速度和可靠性问题，模板匹配本质上是一个棘手的问题。当对象部分可见或与其他对象混合时，该解决方案应对亮度变化具有鲁棒性，最重要的是，该算法应具有计算效率。解决这个问题主要有两种方法，基于灰度值的匹配（或基于区域的匹配）和基于特征的匹配（非基于区域的匹配）。
基于灰度值的方法：在基于灰度值的匹配中，归一化互相关 (NCC) 算法早在过去就已为人所知。这通常在每一步通过减去平均值并除以标准偏差来完成。模板 t(x, y) 与子图像 f(x, y) 的互相关为：
其中 n 是 t(x, y) 和 f(x, y) 中的像素数。[维基]
尽管该方法对线性光照变化具有鲁棒性，但当对象部分可见或对象与其他对象混合时，该算法将失败。此外，该算法的计算成本很高，因为它需要计算模板图像中所有像素与搜索图像之间的相关性。
基于特征的方法：在图像处理领域中使用了几种基于特征的模板匹配方法。与基于边缘的物体识别一样，物体边缘是用于匹配的特征，在广义霍夫变换中，物体的几何特征将用于匹配。
在本文中，我们实现了一种算法，该算法使用对象的边缘信息来识别搜索图像中的对象。此实现使用开源计算机视觉库作为平台。
编译示例代码
我们使用 OpenCV 2.0 和 Visual Studio 2008 来开发此代码。要编译示例代码，我们需要安装 OpenCV。
OpenCV 可以从这里免费下载。OpenCV的（开放源码ç动态数值V ision）是一种用于实时计算机视觉编程功能的库。下载 OpenCV 并将其安装在您的系统中。安装信息可以从这里阅读。
我们需要配置我们的 Visual Studio 环境。可以从此处阅读此信息。
算法
在这里，我们将解释基于边缘的模板匹配技术。边缘可以定义为数字图像中图像亮度急剧变化或具有不连续性的点。从技术上讲，它是一种离散微分运算，计算图像强度函数的梯度近似值。
边缘检测的方法有很多，但大多数可以分为两类：基于搜索的和基于过零的。基于搜索的方法通过首先计算边缘强度的度量来检测边缘，通常是一阶导数表达式，例如梯度幅度，然后使用计算的局部方向的估计来搜索梯度幅度的局部方向最大值边缘，通常是梯度方向。在这里，我们使用了一种由 Sobel 实现的方法，称为 Sobel 算子。操作员计算每个点的图像强度梯度，给出从明到暗的最大可能增加方向以及该方向的变化率。
我们在 X 方向和 Y 方向使用这些梯度或导数进行匹配。
该算法包括两个步骤。首先，我们需要为模板图像创建一个基于边缘的模型，然后我们使用这个模型在搜索图像中进行搜索。
创建基于边缘的模板模型
我们首先从模板图像的边缘创建一个数据集或模板模型，用于在搜索图像中查找该对象的姿态。
在这里，我们使用 Canny 边缘检测方法的变体来查找边缘。您可以在此处阅读有关 Canny 边缘检测的更多信息。对于边缘提取，Canny 使用以下步骤：
第一步：求图像的强度梯度
在模板图像上使用 Sobel 过滤器，它返回 X (Gx) 和 Y (Gy) 方向的梯度。根据这个梯度，我们将使用以下公式计算边缘大小和方向：
我们正在使用 OpenCV 函数来查找这些值。
代码语言：javascript复制cvSobel( src, gx, 1,0, 3 ); //gradient in X direction
cvSobel( src, gy, 0, 1, 3 ); //gradient in Y direction
for( i = 1; i < Ssize.height-1; i )
{
for( j = 1; j < Ssize.width-1; j )
{
_sdx = (short*)(gx->data.ptr gx->step*i);
_sdy = (short*)(gy->data.ptr gy->step*i);
fdx = _sdx[j]; fdy = _sdy[j];
// read x, y derivatives
//Magnitude = Sqrt(gx^2 gy^2)
MagG = sqrt((float)(fdx*fdx) (float)(fdy*fdy));
//Direction = invtan (Gy / Gx)
direction =cvFastArctan((float)fdy,(float)fdx);
magMat[i][j] = MagG;
if(MagG>MaxGradient)
MaxGradient=MagG;
// get maximum gradient value for normalizing.
// get closest angle from 0, 45, 90, 135 set
if ( (direction>0 && direction < 22.5) ||
(direction >157.5 && direction < 202.5) ||
(direction>337.5 && direction<360) )
direction = 0;
else if ( (direction>22.5 && direction < 67.5) ||
(direction >202.5 && direction <247.5) )
direction = 45;
else if ( (direction >67.5 && direction < 112.5)||
(direction>247.5 && direction<292.5) )
direction = 90;
else if ( (direction >112.5 && direction < 157.5)||
(direction>292.5 && direction<337.5) )
direction = 135;
else
direction = 0;
orients[count] = (int)direction;
count ;
}
}一旦找到边缘方向，下一步就是关联图像中可以追踪的边缘方向。有四种可能的方向来描述周围的像素：0 度、45 度、90 度和 135 度。我们将所有方向分配给这些角度中的任何一个。
步骤 2：应用非极大值抑制
找到边缘方向后，我们会做一个非极大值抑制算法。非极大值抑制沿边缘方向跟踪左右像素，如果当前像素幅度小于左右像素幅度，则抑制当前像素幅度。这将导致图像变薄。
代码语言：javascript复制for( i = 1; i < Ssize.height-1; i )
{
for( j = 1; j < Ssize.width-1; j )
{
switch ( orients[count] )
{
case 0:
leftPixel = magMat[i][j-1];
rightPixel = magMat[i][j 1];
break;
case 45:
leftPixel = magMat[i-1][j 1];
rightPixel = magMat[i 1][j-1];
break;
case 90:
leftPixel = magMat[i-1][j];
rightPixel = magMat[i 1][j];
break;
case 135:
leftPixel = magMat[i-1][j-1];
rightPixel = magMat[i 1][j 1];
break;
}
// compare current pixels value with adjacent pixels
if (( magMat[i][j] < leftPixel ) || (magMat[i][j] < rightPixel ) )
(nmsEdges->data.ptr nmsEdges->step*i)[j]=0;
Else
(nmsEdges->data.ptr nmsEdges->step*i)[j]=
(uchar)(magMat[i][j]/MaxGradient*255);
count ;
}
}第三步：做滞后阈值
用滞后做阈值需要两个阈值：高和低。我们应用高阈值来标记那些我们可以相当确定是真实的边缘。从这些开始，使用先前导出的方向信息，可以通过图像追踪其他边缘。在跟踪边缘时，我们应用较低的阈值，只要我们找到一个起点，我们就可以跟踪边缘的微弱部分。
代码语言：javascript复制_sdx = (short*)(gx->data.ptr gx->step*i);
_sdy = (short*)(gy->data.ptr gy->step*i);
fdx = _sdx[j]; fdy = _sdy[j];
MagG = sqrt(fdx*fdx fdy*fdy); //Magnitude = Sqrt(gx^2 gy^2)
DirG =cvFastArctan((float)fdy,(float)fdx); //Direction = tan(y/x)
////((uchar*)(imgGDir->imageData imgGDir->widthStep*i))[j]= MagG;
flag=1;
if(((double)((nmsEdges->data.ptr nmsEdges->step*i))[j]) < maxContrast)
{
if(((double)((nmsEdges->data.ptr nmsEdges->step*i))[j])< minContrast)
{
(nmsEdges->data.ptr nmsEdges->step*i)[j]=0;
flag=0; // remove from edge
////((uchar*)(imgGDir->imageData imgGDir->widthStep*i))[j]=0;
}
else
{ // if any of 8 neighboring pixel is not greater than max contraxt remove from edge
if( (((double)((nmsEdges->data.ptr nmsEdges->step*(i-1)))[j-1]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*(i-1)))[j]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*(i-1)))[j 1]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*i))[j-1]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*i))[j 1]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*(i 1)))[j-1]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*(i 1)))[j]) < maxContrast) &&
(((double)((nmsEdges->data.ptr nmsEdges->step*(i 1)))[j 1]) < maxContrast))
{
(nmsEdges->data.ptr nmsEdges->step*i)[j]=0;
flag=0;
////((uchar*)(imgGDir->imageData imgGDir->widthStep*i))[j]=0;
}
}
}第 4 步：保存数据集
提取边缘后，我们将所选边缘的 X 和 Y 导数与坐标信息一起保存为模板模型。这些坐标将重新排列以反映作为重心的起点。
找到基于边的模板模型
算法中的下一个任务是使用模板模型在搜索图像中找到对象。我们可以看到我们从包含一组点的模板图像创建的模型：
，以及它在 X 和 Y 方向上的梯度
，其中i = 1…n，n是模板 (T) 数据集中的元素数。
我们还可以在搜索图像 (S) 中找到梯度
，其中 u = 1...搜索图像中的行数，v = 1...搜索图像中的列数。
在匹配过程中，应使用相似性度量将模板模型与所有位置的搜索图像进行比较。相似性度量背后的思想是取模板图像梯度向量的所有归一化点积之和，并在模型数据集中的所有点上搜索图像。这会导致搜索图像中每个点的分数。这可以表述如下：
如果模板模型和搜索图像之间存在完美匹配，则此函数将返回分数 1。该分数对应于搜索图像中可见的对象部分。如果搜索图像中不存在对象，则分数将为 0。
代码语言：javascript复制cvSobel( src, Sdx, 1, 0, 3 ); // find X derivatives
cvSobel( src, Sdy, 0, 1, 3 ); // find Y derivatives
for( i = 0; i < Ssize.height; i )
{
for( j = 0; j < Ssize.width; j )
{
partialSum = 0; // initilize partialSum measure
for(m=0;m<noOfCordinates;m )
{
curX = i cordinates[m].x ; // template X coordinate
curY = j cordinates[m].y ; // template Y coordinate
iTx = edgeDerivativeX[m]; // template X derivative
iTy = edgeDerivativeY[m]; // template Y derivative
if(curX<0 ||curY<0||curX>Ssize.height-1 ||curY>Ssize.width-1)
continue;
_Sdx = (short*)(Sdx->data.ptr Sdx->step*(curX));
_Sdy = (short*)(Sdy->data.ptr Sdy->step*(curX));
iSx=_Sdx[curY]; // get curresponding X derivative from source image
iSy=_Sdy[curY];// get curresponding Y derivative from source image
if((iSx!=0 || iSy!=0) && (iTx!=0 || iTy!=0))
{
//partial Sum = Sum of(((Source X derivative* Template X drivative)
// Source Y derivative * Template Y derivative)) / Edge
//magnitude of(Template)* edge magnitude of(Source))
partialSum = partialSum ((iSx*iTx) (iSy*iTy))*
(edgeMagnitude[m] * matGradMag[curX][curY]);
}在实际情况下，我们需要加快搜索过程。这可以使用各种方法来实现。第一种方法是使用平均的属性。在寻找相似性度量时，如果我们可以为相似性度量设置一个最小分数（S min），我们就不需要评估模板模型中的所有点。为了检查特定点 J 处的部分分数 S u,v，我们必须找到部分总和 Sm。点 m 处的 Sm 可以定义如下：
很明显，和的剩余项小于或等于 1。因此，如果 ，我们可以停止评估
。
另一个标准可以是任何点的部分分数应大于最低分数。即，
。使用此条件时，匹配将非常快。但问题是，如果先检查对象的缺失部分，部分和会很低。在这种情况下，对象的该实例不会被视为匹配项。我们可以用另一个标准修改它，我们用安全停止标准检查模板模型的第一部分，用硬标准检查其余部分，
. 用户可以指定贪婪参数 (g)，其中使用硬标准检查模板模型的部分。所以如果g=1，模板模型中的所有点都用硬标准检查，如果g=0，所有点将只用安全标准检查。我们可以将这个过程表述如下。
部分分数的评估可以在以下位置停止：
// stoping criterias to search for model
double normMinScore = minScore /noOfCordinates; // precompute minumum score
double normGreediness = ((1- greediness * minScore)/(1-greediness)) /noOfCordinates;
// precompute greedniness
sumOfCoords = m 1;
partialScore = partialSum /sumOfCoords ;
// check termination criteria
// if partial score score is less than the score than
// needed to make the required score at that position
// break serching at that coordinate.
if( partialScore < (MIN((minScore -1)
normGreediness*sumOfCoords,normMinScore* sumOfCoords)))
break;这种相似性度量有几个优点：相似性度量对非线性光照变化是不变的，因为所有梯度向量都是归一化的。由于边缘过滤没有分割，它将显示对光照任意变化的真实不变性。更重要的是，当对象部分可见或与其他对象混合时，这种相似性度量是稳健的。
增强功能
该算法有多种可能的增强。为了进一步加快搜索过程，可以使用金字塔方法。在这种情况下，搜索以低分辨率和小图像尺寸开始。这对应于金字塔的顶部。如果在此阶段搜索成功，则在金字塔的下一层继续搜索，该层代表更高分辨率的图像。以这种方式，继续搜索，从而细化结果，直到达到原始图像大小，即到达金字塔底部。
通过扩展旋转和缩放算法，可以实现另一种增强。这可以通过创建用于旋转和缩放的模板模型并使用所有这些模板模型执行搜索来完成。
参考
- 机器视觉算法和应用 [Carsten Steger、Markus Ulrich、Christian Wiedemann]
- 数字图像处理 [Rafael C. Gonzalez, Richard Eugene Woods]
- http://dasl.mem.drexel.edu/alumni/bGreen/www.pages.drexel.edu/_weg22/can_tut.html
源码与测试Demo
1. 源码下载链接：https://www.codeproject.com/KB/graphics/Edge_Based_template_match/GeoMatch_src.zip
2. 测试Demo下载链接：
https://www.codeproject.com/KB/graphics/Edge_Based_template_match/GeoMatch_demo.zip
【后记】
- 上面代码使用的是OpenCV2版本，安装包可以在下面交流群获取；
- 代码适用部分遮挡和亮度变化情况的匹配；
- 算法测试时间较长，还需优化，可用作学习。
- 不适用旋转和缩放匹配；
- 和Halcon的匹配相比还有较大差距(如果有人拿这个说实现了Halcon匹配算法，那估计是自己根本没用过Halcon吧)。
