文后代码，优化效果图结尾处，最快3ms得到匹配结果
NCC，全称为Normalized Cross Correlation，即归一化互相关系数， 在模板匹配中使用的非常非常广泛，也是众多模板匹配方法中非常耀眼的存在， 这个匹配的理论核心基础公式如下：
其实Opencv的matchTemplate函数使用的就是这个公式，实测直接使用这个公式实现无旋转角度的、单目标的模板匹配时用时大概26ms（其实这个结果已经满足大部分使用需求了），但是本博主响应国家号召，秉着自强不息、实事求是、勇于钻研的心态，决定从公式层面重写该算法，毕竟opencv的函数优化起来很难，想要达到10ms之内更是几乎不可能，而重新实现公式可以继续优化，最终实现10ms内实现带旋转的、单目标检测（其实目标数量并不重要，无论是单目标还是多目标，都要检测整张图像，而单目标无非就是只在乎那个得分最高的，对于算法来说，二者并无差别）
他的理论匹配度范围是[-1，1]，为-1时表示2副图像的极性完全相反（原图和反色后的图），为1则表示两幅图完全一样。一般我们在计算NCC的时候都是取的绝对值，因此，通常NCC的取值为[0,1]，值越大，表示两幅图像越相似。
但是实际编程实现时，一眼可以看出，这个公式不合适，因为模板匹配的模板在大多数检测中都是固定的，所以关于模板的数值可以提前计算好，不放在整个公式里，所以改进成用下面的式子实现编码。
这个式子看上去更为复杂，我们可以把他拆解为7个部分，11道来。
- 这个留到最后在说。
- T代表的是模板，那么②对于固定的模板来说就是一个定值，在匹配前可以直接计算好，无需担忧耗时问题。
- I 表示的搜索图像中的和模板一样大的一个子块，很明显这个累加有多重方法可以快速的实现，比如积分图的遍历，这一项也是和参数无关的。
- 第四项处理方式同 ②项，无需多言。
- 第五项完全同第二项，同时四和五项作为一个整体也可以提前计算好，不参与匹配过程的计算。
- 第六项处理方式同第三项，也无需多言。
- 第七项完全同第三项，直接使用。
前面的分析表明，第二至第七项要买可以作为常量提前计算好，要么就可以通过某种技术实现O(1)的快速计算，那么现在我们再回过头来在看第①项，他是模板图像和搜索图像同面积区域像素的一个卷积，这个是无法用某种优化技巧去实现和模板大小无关的快速实现的，注定了他就是NCC计算式中最为耗时的部分。
那么到这里开始，咱们已经可以开始霸王硬上弓了，千里之行始于足下嘛，先看看效果再说！
很好，四秒多，基于O(n2)实现的不带旋转角度的匹配，速度还算在预料之中吧，下面先把这个代码拿出来讲讲，（本文就是讲到实现公式，提速部分会简单讲讲，但是由于种种原因，不会放出代码哦）。
首先就是界面的搭建！忽略谢谢，本博主还是个平平无奇的小学生，打上马赛克了我就安全啦。
重点就是模板的训练和模板的计算，所谓模板的训练就是把模板的数据，就是公式里包含T的部分优先计算出来。
首先定义一个存数据的结构体（代码讲解直接写注释里了）
typedef struct picture
{
Mat Template_gray ;
int cols =0;//模板图像行列数
int rows =0;
int x =0;//匹配目标像素点坐标
int y =0;
double one =0;//1234567顾名思义喽
double two =0;
double three =0;
double four =0;
double five =0;
double six =0;
double seven =0;
double sum =0;//灰度和
double mean =0;//均值
double stddev =0;//均差
int minpiex =1;//像素精度1-10
int angle_start =0;
int angle_end =0;
int angle_step =0;
double minscare =0;
double NCC_Result =0;
double temp =0;//用来比较得分大小，最终得分取最小值设为1，取最大值设为0
}picture;
然后训练模板：
void train(Mat Template,picture &src)//输入RGB图像
{
picture_init(src);//初始化定义的结构体，防止变量值被二次累加出错
cvtColor(Template,src.Template_gray,CV_BGR2GRAY);
tep_sum(src.Template_gray,src);
// qDebug()<< "src.two:" <<src.two <<endl;
// qDebug()<< "src.mean:" << src.mean <<endl;
}
void tep_sum(Mat src_gray , picture &src)//输入灰度图的灰度值和、均值、均方差
{
for(int i=0;i<src_gray.rows;i++)
{
for(int j=0;j<src_gray.cols ;j++)
{
src.sum += src_gray.ptr<uchar>(i)[j];//i行j列
src.four += (src_gray.ptr<uchar>(i)[j])^2;
}
}
// Mat mat_mean, mat_stddev;
// meanStdDev(src_gray, mat_mean, mat_stddev);//求灰度图像的均值、均方差，这是opencv自带的函数，我用它的结果和我的结果做对比，验证我自己的算法结果是否正确
// src.mean = mat_mean.at<double>(0, 0);
// src.stddev = mat_stddev.at<double>(0, 0);
src.two = src.sum/(src_gray.cols*src_gray.rows);//two理应等于mean，相等则表示算法没出错
src.five=src.two*src.sum;
// qDebug()<< "2:"<<src.two <<endl;
// qDebug()<< "mean:"<<src.mean <<endl;
}
然后就可以开始计算了：
void NCC_Match(Mat image_in , picture &src)
{
for(int x=0; x< image_in.cols - src.cols - src.minpiex; x = x + src.minpiex)
{
for(int y=0; y< image_in.rows - src.rows - src.minpiex; y = y + src.minpiex)//注意防止溢出
{
NCC_sum(x , y , image_in , src );
src.NCC_Result = fabs(src.one - src.two*src.three) / ( sqrt(fabs(src.four-src.five)) * sqrt(fabs(src.six-src.seven)));//最终得分
if(src.NCC_Result > 0)
{
// qDebug()<< "x:" << x << " y:" << y << " score:"<< src.NCC_Result <<endl;
if(src.NCC_Result > src.temp)
{
src.temp = src.NCC_Result;
src.x = x;
src.y = y;
}
}
src.one =0;//数字清零，不然下面会重复累加，这里很重要！博主含泪分享
src.three =0;
src.six =0;
}
}
}
void NCC_sum(int x,int y,Mat NCC_Picture,picture &src)
{
Mat NCC_Picture_gray;
cvtColor(NCC_Picture,NCC_Picture_gray,CV_BGR2GRAY);
Mat aoi = getaoi(NCC_Picture_gray,x,y,src.Template_gray.cols,src.Template_gray.rows);//自定义函数，矩形抠图
for(int i=0; i<aoi.rows; i++)
{
for(int j=0;j<aoi.cols;j++)
{
src.three += aoi.ptr<uchar>(i)[j];
src.six +=(aoi.ptr<uchar>(i)[j])^2;
src.one +=src.Template_gray.ptr<uchar>(i)[j] * aoi.ptr<uchar>(i)[j];
}
}
// Mat NCC_mean, NCC_stddev;
// meanStdDev(aoi, NCC_mean, NCC_stddev);//同上，用来检验算法正确性
// int NCCmean = NCC_mean.at<double>(0, 0);
// int temp1 = src.three/(aoi.cols * aoi.rows);
// qDebug()<< "3_average:"<<temp1 <<endl;
// qDebug()<< "3_mean:"<<NCCmean <<endl;
src.seven = (src.three*src.three)/(src.cols*src.rows);
}
这样匹配的整个流程算是结束了，这是最耗时的算法，大家可以根据自己的需要进行改进，下面展示一下自定义函数部分：
void picture_init(picture &src)//初始化
{
src.one =0;
src.two =0;
src.three =0;
src.four =0;
src.five =0;
src.six =0;
src.seven =0;
src.sum =0;
src.stddev =0;
src.mean =0;
src.NCC_Result =0;
src.Template_gray.release();
src.x =0;//匹配目标像素点坐标
src.y =0;
src.temp =0;//用来比较得分大小，最终得分取最小值设为1，取最大值设为0
}
Mat getaoi(Mat img,int x,int y,int cols,int rows)//x、y为左上角坐标，矩形抠图
{
Rect m_select = Rect(x,y,cols,rows);
img = img(m_select);
return img;
}
到这，就可以将结果显示在ui中，借助代码可以更好的理解公式，而不是供大家抄袭，这段代码本身并不值得抄袭，价值意义不大，只是单纯的实现，大佬们自然能想出O(1)的算法去解决，至于带旋转角度的只需要将模板旋转后多次带入函数中计算即可。
下面简单讲讲加速的思路
为了得到更快的搜索速度，一个最容易想到的策略就是图像金字塔，图像金字塔每增加一层，图像的点数和模板的点数救减少4倍（理论数据，实际由于非2的宽度和高度，不一定正好是4倍），那么不考虑Cache等其他的因素，理论上每增加一层金字塔救可以提速16倍，因此，如果我们构建了一个4层的金字塔，那么在第4层金字塔上的一次完整匹配，其计算的次数和原始的数据相比，就能减少4096倍。
我们先以无旋转单目标为例进行简单的说明，当我们在金字塔最高层进行一次完整的匹配后，我们可以找一个全局的极值点，这就是在顶层匹配时的最佳匹配位置，此时，我们可以将顶层匹配的结果映射到金字塔的下一层中，简单的说就是将找到的匹配点坐标的X/Y值乘以2，那么为了保证在下一层中的精度，此时的搜索区域需要适当的增大，比如选择匹配点周围55或者77的一个区域，然后在这感兴趣的区域中再进行一个局部的匹配计算，此时只需要计算25或者49次小匹配的计算，当计算完毕后，再次提取出这个小区域的极值，作为本层的最终种子点，重复这个过程，直到金字塔的最底层（即原始搜索图像）为止。（自学金字塔算法即可，各种插值方法也不在这里赘述。）
除了改进算法本身时间复杂度以外（学过数据结构的都知道，无非是空间换时间），还有一个方法就是加速包，大家自行搜索SIMD指令实现算法提速，学习一下使用即可，大概可以有十倍运算能力的提高。
有人说卷积可以有FFT实现优化，没错，非常同意你的观点，但是，FFT虽然其第一个F代表了Fast，但是呢他在傅里叶的世界是快的，在我们模板匹配的空间内他受到了一种无形的压迫，在实际检测应用中还是无法接受的。
还有需要考虑的问题大概有：金字塔层数如何控制、角度离散化的间距如何设置、模板的旋转如何让处理、旋转后产生的无效部分如何处理等等
最后巴拉巴拉巴拉巴拉优化，有一定的效果，但是也是在特定的情况下初步实现了10ms内匹配成功，效果如下：其中的优化方法均是我前文提到过的，对于简单背景的单目标识别，10ms内绰绰有余了吧。
其实到这里还有大量细节没处理好，也没加上旋转角度，所以时间再次压缩也不是不可能，再优化一波图像处理的细节，就又有提升，3ms也不是不可能吧，但是此时定位准确度降低，日后优化吧，再加上旋转匹配，搭配SIMD加速指令，最终的匹配时间应该也相对来说比较可观的。（其实也是哗众取宠吧，这个结果并不能代表什么，只是阶段性的，特定条件下的处理结果，真正应用还是远远不够的，还需要大量的工作）
我也是大量阅读了网络上的资料，并通过大量尝试才有这么一点点的理解和看法，就写点东西算是回馈网络吧，只供大家入门模板匹配使用，博主本人也是刚入门小菜鸡一枚，就像我在前面的文章里说的，我们都是入门人文章来源：https://www.toymoban.com/news/detail-474417.html
博主本人也在努力研究这些算法，奈何博主要学习，实在是力不从心，每天抽空研究算法竟成了休闲娱乐，计算机类越来越卷，但本博主仍不会轻言放弃，两者齐头并进，只是这研究进度自然也就缓慢了下来，后面有时间有精力，博主再慢慢更新。能看到这里的大概都是真想学点东西的人吧，等博主真正实现到10ms内后一定不会忘了大家的！文章来源地址https://www.toymoban.com/news/detail-474417.html
到了这里，关于基于 NCC/灰度信息 的模板匹配算法（QT + Opencv + C++），10ms内获取匹配结果，部分源码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
