參考論文：Template Matching Techniques in Computer Vision: Theory and Practice, 2009

Template matching 的技術已經發展得很成熟，上面只是列出其中一個參考資料

概念

模板匹配，是一種在給定的目標影像中尋找給定的模板影像的技術，原理很簡單，就是利用一些計算相似度的公式來判斷兩張影像之間有多相似

模板影像小於目標影像的話，就需要用 sliding window 的方式來得到多個匹配的結果，可以選擇取最佳匹配

或是設定一個門檻值，只要比這個門檻值好的結果都認為是有效的匹配

sliding window 示意：

TemplateMatching1

常用的相似度的公式

Square difference 平方差

這是最常見的數學公式

Correlation 相關性

計算 dot product (內積)，可以想成是計算兩個向量在空間中的距離有多近，就是用 cosine 去算夾角，cosine 值越大代表夾角越小，代表越接近

(假設模板影像是10*10的影像，可以被看作是100維的向量，每一維是像素的值)

Correlation coefficient

與 Correlation 差別只在於計算內積時還要減去各個向量的平均值，如此一來相關性就會被放大

流程

  1. 先從目標影像的左上角開始，與模板影像一樣的長寬開始做sliding

  2. 利用相似度公式計算區域內模板與目標影像的每一個像素的相似度，然後加總

  3. 更新目前記錄的最佳位置

  4. 移動模板影像到下一個位置 (x + template.width, y + template.height)

  5. 重複 2~4 步驟，直到 run 完目標影像中所有位置 (x, y)

Template matching 需要花費的計算時間還不少，因為模板中的每個像素都要跟目標影像上所有像素比對一遍，找到最相似的模板位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Template matching的大概程式流程
float minSSD = FLOAT_MAX;
point p;
for(int x = 0; x < Target.width; x++){
    for(int y = 0; y < Target.height; y++){
        float curSSD = 0;
        for(int m = 0; m < Template.width; m++){
            for(int n = 0; n < Template.height; n++){
                curSSD = curSSD + mathSSD(Target(x + m,y + n), Template(m, n));
            }
        }
        if(curSSD < minSSD) {
            minSSD = curSSD;
            p = (x, y);
        }
    }
}
// 最後p的值為目標影像上最相似的位置(右上角)

上面的程式碼只是大概流程，細節操作(例如取出像素值、SSD 函式等等)並沒有寫進去

因為 Template matching 在 OpenCV中也有函式庫 能直接使用，實作的算很完整，有把不同的比較方法都涵蓋，這邊就不多說明，

比較需要知道的大概是因為 Template matching 速度不快，後續有些論文主要是在加速 Template maching，有些論文則是在研究不同需求下要使用怎麼樣的比較準則會較好

比如用在一連串的影片中找到某個物體，為了減少影像亮度變化對計算的影響，會做Normalization (正規化)

模板匹配優點是實作簡單且穩定，缺點是如果兩個比對的影像有一點旋轉或歪斜的情況發生時，就會造成比對錯誤

Code

利用 OpneCV 的 matchTemplate 實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Point Matching(Mat& templ, Mat& target) {
	Mat display_img;
	target.copyTo(display_img);

	int result_cols = target.cols - templ.cols + 1;
	int result_rows = target.rows - templ.rows + 1;

	Mat result(result_rows, result_cols, CV_32FC1);

	/* 0 = CV_TM_SQDIFF       平方差
	1 = CV_TM_SQDIFF_NORMED
	2 = CV_TM_CCORR           相關性
	3 = CV_TM_CCORR_NORMED
	4 = CV_TM_CCOEFF          相關係數
	5 = CV_TM_CCOEFF_NORMED
	*/
	matchTemplate(target, templ, result, CV_TM_SQDIFF_NORMED);
	normalize(result, result, 0, 1, NORM_MINMAX, -1, Mat());

	// Localizing the best match with minMaxLoc
	double minVal; double maxVal; Point minLoc; Point maxLoc;
	Point matchLoc;

	// use the function minMaxLoc to locate the highest value(or lower, depending of the type of matching method) in the R matrix.
	// The functions *minMaxLoc* do not work with multi-channel arrays.
	minMaxLoc(result, &minVal, &maxVal, &minLoc, &maxLoc, Mat());

	matchLoc = minLoc;

	// Show me what you got
	rectangle(display_img, matchLoc, Point(matchLoc.x + templ.cols, matchLoc.y + templ.rows), Scalar(0, 0, 255), 1, 8, 0);
	rectangle(result, matchLoc, Point(matchLoc.x + templ.cols, matchLoc.y + templ.rows), Scalar(0, 0, 255), 1, 8, 0);

	imshow("target", display_img);
	//waitKey(0);

	return matchLoc;
}