1 Template Matching {#tutorial_template_matching} 2 ================= 3 4 Goal 5 ---- 6 7 In this tutorial you will learn how to: 8 9 - Use the OpenCV function @ref cv::matchTemplate to search for matches between an image patch and 10 an input image 11 - Use the OpenCV function @ref cv::minMaxLoc to find the maximum and minimum values (as well as 12 their positions) in a given array. 13 14 Theory 15 ------ 16 17 ### What is template matching? 18 19 Template matching is a technique for finding areas of an image that match (are similar) to a 20 template image (patch). 21 22 ### How does it work? 23 24 - We need two primary components: 25 26 -# **Source image (I):** The image in which we expect to find a match to the template image 27 -# **Template image (T):** The patch image which will be compared to the template image 28 29 our goal is to detect the highest matching area: 30 31  32 33 - To identify the matching area, we have to *compare* the template image against the source image 34 by sliding it: 35 36  37 38 - By **sliding**, we mean moving the patch one pixel at a time (left to right, up to down). At 39 each location, a metric is calculated so it represents how "good" or "bad" the match at that 40 location is (or how similar the patch is to that particular area of the source image). 41 - For each location of **T** over **I**, you *store* the metric in the *result matrix* **(R)**. 42 Each location \f$(x,y)\f$ in **R** contains the match metric: 43 44  45 46 the image above is the result **R** of sliding the patch with a metric **TM_CCORR_NORMED**. 47 The brightest locations indicate the highest matches. As you can see, the location marked by the 48 red circle is probably the one with the highest value, so that location (the rectangle formed by 49 that point as a corner and width and height equal to the patch image) is considered the match. 50 51 - In practice, we use the function @ref cv::minMaxLoc to locate the highest value (or lower, 52 depending of the type of matching method) in the *R* matrix. 53 54 ### Which are the matching methods available in OpenCV? 55 56 Good question. OpenCV implements Template matching in the function @ref cv::matchTemplate . The 57 available methods are 6: 58 59 -# **method=CV_TM_SQDIFF** 60 61 \f[R(x,y)= \sum _{x',y'} (T(x',y')-I(x+x',y+y'))^2\f] 62 63 -# **method=CV_TM_SQDIFF_NORMED** 64 65 \f[R(x,y)= \frac{\sum_{x',y'} (T(x',y')-I(x+x',y+y'))^2}{\sqrt{\sum_{x',y'}T(x',y')^2 \cdot \sum_{x',y'} I(x+x',y+y')^2}}\f] 66 67 -# **method=CV_TM_CCORR** 68 69 \f[R(x,y)= \sum _{x',y'} (T(x',y') \cdot I(x+x',y+y'))\f] 70 71 -# **method=CV_TM_CCORR_NORMED** 72 73 \f[R(x,y)= \frac{\sum_{x',y'} (T(x',y') \cdot I(x+x',y+y'))}{\sqrt{\sum_{x',y'}T(x',y')^2 \cdot \sum_{x',y'} I(x+x',y+y')^2}}\f] 74 75 -# **method=CV_TM_CCOEFF** 76 77 \f[R(x,y)= \sum _{x',y'} (T'(x',y') \cdot I'(x+x',y+y'))\f] 78 79 where 80 81 \f[\begin{array}{l} T'(x',y')=T(x',y') - 1/(w \cdot h) \cdot \sum _{x'',y''} T(x'',y'') \\ I'(x+x',y+y')=I(x+x',y+y') - 1/(w \cdot h) \cdot \sum _{x'',y''} I(x+x'',y+y'') \end{array}\f] 82 83 -# **method=CV_TM_CCOEFF_NORMED** 84 85 \f[R(x,y)= \frac{ \sum_{x',y'} (T'(x',y') \cdot I'(x+x',y+y')) }{ \sqrt{\sum_{x',y'}T'(x',y')^2 \cdot \sum_{x',y'} I'(x+x',y+y')^2} }\f] 86 87 Code 88 ---- 89 90 - **What does this program do?** 91 - Loads an input image and a image patch (*template*) 92 - Perform a template matching procedure by using the OpenCV function @ref cv::matchTemplate 93 with any of the 6 matching methods described before. The user can choose the method by 94 entering its selection in the Trackbar. 95 - Normalize the output of the matching procedure 96 - Localize the location with higher matching probability 97 - Draw a rectangle around the area corresponding to the highest match 98 - **Downloadable code**: Click 99 [here](https://github.com/Itseez/opencv/tree/master/samples/cpp/tutorial_code/Histograms_Matching/MatchTemplate_Demo.cpp) 100 - **Code at glance:** 101 @include samples/cpp/tutorial_code/Histograms_Matching/MatchTemplate_Demo.cpp 102 103 Explanation 104 ----------- 105 106 -# Declare some global variables, such as the image, template and result matrices, as well as the 107 match method and the window names: 108 @code{.cpp} 109 Mat img; Mat templ; Mat result; 110 char* image_window = "Source Image"; 111 char* result_window = "Result window"; 112 113 int match_method; 114 int max_Trackbar = 5; 115 @endcode 116 -# Load the source image and template: 117 @code{.cpp} 118 img = imread( argv[1], 1 ); 119 templ = imread( argv[2], 1 ); 120 @endcode 121 -# Create the windows to show the results: 122 @code{.cpp} 123 namedWindow( image_window, WINDOW_AUTOSIZE ); 124 namedWindow( result_window, WINDOW_AUTOSIZE ); 125 @endcode 126 -# Create the Trackbar to enter the kind of matching method to be used. When a change is detected 127 the callback function **MatchingMethod** is called. 128 @code{.cpp} 129 char* trackbar_label = "Method: \n 0: SQDIFF \n 1: SQDIFF NORMED \n 2: TM CCORR \n 3: TM CCORR NORMED \n 4: TM COEFF \n 5: TM COEFF NORMED"; 130 createTrackbar( trackbar_label, image_window, &match_method, max_Trackbar, MatchingMethod ); 131 @endcode 132 -# Wait until user exits the program. 133 @code{.cpp} 134 waitKey(0); 135 return 0; 136 @endcode 137 -# Let's check out the callback function. First, it makes a copy of the source image: 138 @code{.cpp} 139 Mat img_display; 140 img.copyTo( img_display ); 141 @endcode 142 -# Next, it creates the result matrix that will store the matching results for each template 143 location. Observe in detail the size of the result matrix (which matches all possible locations 144 for it) 145 @code{.cpp} 146 int result_cols = img.cols - templ.cols + 1; 147 int result_rows = img.rows - templ.rows + 1; 148 149 result.create( result_rows, result_cols, CV_32FC1 ); 150 @endcode 151 -# Perform the template matching operation: 152 @code{.cpp} 153 matchTemplate( img, templ, result, match_method ); 154 @endcode 155 the arguments are naturally the input image **I**, the template **T**, the result **R** and the 156 match_method (given by the Trackbar) 157 158 -# We normalize the results: 159 @code{.cpp} 160 normalize( result, result, 0, 1, NORM_MINMAX, -1, Mat() ); 161 @endcode 162 -# We localize the minimum and maximum values in the result matrix **R** by using @ref 163 cv::minMaxLoc . 164 @code{.cpp} 165 double minVal; double maxVal; Point minLoc; Point maxLoc; 166 Point matchLoc; 167 168 minMaxLoc( result, &minVal, &maxVal, &minLoc, &maxLoc, Mat() ); 169 @endcode 170 the function calls as arguments: 171 172 - **result:** The source array 173 - **&minVal** and **&maxVal:** Variables to save the minimum and maximum values in **result** 174 - **&minLoc** and **&maxLoc:** The Point locations of the minimum and maximum values in the 175 array. 176 - **Mat():** Optional mask 177 178 -# For the first two methods ( TM_SQDIFF and MT_SQDIFF_NORMED ) the best match are the lowest 179 values. For all the others, higher values represent better matches. So, we save the 180 corresponding value in the **matchLoc** variable: 181 @code{.cpp} 182 if( match_method == TM_SQDIFF || match_method == TM_SQDIFF_NORMED ) 183 { matchLoc = minLoc; } 184 else 185 { matchLoc = maxLoc; } 186 @endcode 187 -# Display the source image and the result matrix. Draw a rectangle around the highest possible 188 matching area: 189 @code{.cpp} 190 rectangle( img_display, matchLoc, Point( matchLoc.x + templ.cols , matchLoc.y + templ.rows ), Scalar::all(0), 2, 8, 0 ); 191 rectangle( result, matchLoc, Point( matchLoc.x + templ.cols , matchLoc.y + templ.rows ), Scalar::all(0), 2, 8, 0 ); 192 193 imshow( image_window, img_display ); 194 imshow( result_window, result ); 195 @endcode 196 197 Results 198 ------- 199 200 -# Testing our program with an input image such as: 201 202  203 204 and a template image: 205 206  207 208 -# Generate the following result matrices (first row are the standard methods SQDIFF, CCORR and 209 CCOEFF, second row are the same methods in its normalized version). In the first column, the 210 darkest is the better match, for the other two columns, the brighter a location, the higher the 211 match. 212  213  214  215  216  217  218 219 -# The right match is shown below (black rectangle around the face of the guy at the right). Notice 220 that CCORR and CCDEFF gave erroneous best matches, however their normalized version did it 221 right, this may be due to the fact that we are only considering the "highest match" and not the 222 other possible high matches. 223 224  225
