Template matching

Wait… PowerPoint had templates!!!

Those aren’t the templates we’re talking about. Template matching is an algorithm that can help you locate certain features in a given image. But the condition is, you need to know exactly what you’re looking for.

An example might make it clearer. Lets say you have the image below:
A random image

Lets say we’re looking for a “p” in the image. So, we’re looking for the following image:
The template
Thats’ the “template” we’re looking for in the original image. I hope that takes care of the template part of the title. Now for the matching part…

Matching

Template matching works by “sliding” the template across the original image. As it slides, it compares or matches the template to the portion of the image directly under it.

The technique

It does this matching by calculating a number. This number denotes the extent to which the template and the portion of the original are equal. The actual number depends on the calculation used. Some denote a complete match by a 0 (indicating no difference between the template and the portion of original) or a 1 (indicating a complete match).

How OpenCV does template matching

When you perform template matching in OpenCV, you get an image that shows the degree of “equality” or correlation between the template and the portion under the template.

The technique

The template is compared against its background, and the result of the calculation (a number) is stored at the top left pixel. Here’s what the actual “correlation map” looks like:
The result of template matching

The greater the intensity, the greater the correlation between the template and the portion. As you can see, the two “t” in the side in the original image don’t really match with the p, so you get a relatively darker region there.

To find out where the P lies in the image, you simply find the location where you have the greatest correlation (or, minimum difference) and that would be your answer.

On with the code

Enough of theory, now we begin with the code. Create a new Win32 console project, name it whatever you want and accept the default settings. You’ll get an empty project with a main function. First, add these header files to the code:

#include "cv.h"
#include "highgui.h"

Next, add the library files to the project. Go to Project > Properties > Configuration > Linker > Input and write cv.lib cxcore.lib cvaux.lib highgui.lib in Additional Dependencies.

If you have any problems with setting this up, I suggest you go through Installing and Getting OpenCV running and “Hello, world!” with images!

Now we get into the main function:

int main()
{

Next, we load the original image and the template:

    IplImage* imgOriginal = cvLoadImage("technophilia.jpg", 0);
    IplImage* imgTemplate = cvLoadImage("template.jpg", 0);

Note that I force loading as grayscale image, just to keep things simple. Next, we create a blank image the will hold the correlation map:

    IplImage* imgResult = cvCreateImage(cvSize(imgOriginal->width-imgTemplate->width+1, imgOriginal->height-imgTemplate->height+1), IPL_DEPTH_32F, 1);
    cvZero(imgResult);

See the weird size we’re giving this image? That has a perfectly sane explanation. Have a look at the picture below:

Boundary limits of the template

The correlation map can only extend from the top left corner to the big black dot on the lower right corner. Thats because if the template were to slide any further, you’d get a partial template image… and that would be absurd. So you subtract the height and width of the template from the original image’s height and width, and add one.

Now for the instruction-of-the-tutorial:

    cvMatchTemplate(imgOriginal, imgTemplate, imgResult, CV_TM_CCORR_NORMED);

This instruction does all the sliding and correlation mathematics using imgOriginal (the source), imgTemplate (the template) and puts the correlation map into imgResult. The calculations used for determining the correlation map is the last parameter, CV_TM_CCORR_NORMED.

OpenCV offers six different calculation methods:

  • CV_TM_SQDIFF
  • CV_TM_SQDIFF_NORMED
  • CV_TM_CCORR
  • CV_TM_CCORR_NORMED
  • CV_TM_CCOEFF
  • CV_TM_CCOEFF_NORMED

The NORMED calculations give values upto 1.0… the other ones return huge values. SQDIFF is a difference based calculation that gives a 0 at a perfect match. The other two (CCORR and CCOEFF) are correlation based, and return a 1.0 for a perfect match.

To determine the maximum point in the correlation, we use another OpenCV function: cvMinMaxLoc. This function returns the minimum and maximum values and their locations. So, we use it:

    double min_val=0, max_val=0;
    CvPoint min_loc, max_loc;
    cvMinMaxLoc(imgResult, &min_val, &max_val, &min_loc, &max_loc);

Now max_loc holds the point we’re interested in: the point with maximum correlation. We’ll just put a rectangle there, and also print out the actual value of correlation… just for the sake of demonstration:

    cvRectangle(imgOriginal, max_loc, cvPoint(max_loc.x+imgTemplate->width, max_loc.y+imgTemplate->height), cvScalar(0), 1);
    printf("%f", max_val);

And we finally display the modified original image, and exit:

    cvNamedWindow("result");
    cvShowImage("result", imgOriginal);
    cvWaitKey(0);
    return 0;
}

Here’s the result I got:

The final output

That seems very accurate. I got a correlation of 0.98. That’s because of the little R. It isn’t present in the template, so it takes its toll. That, and the fact that JPEG images put a little noise around the edges, combined reduce the correlation.

Disadvantages of template matching

Well, the first disadvantage is that you need to know what you’re looking for. If you’re looking for dynamic features, you’ll be better off using some other techniques.

Secondly, template matching provided by OpenCV doesn’t let you check for rotations and scalings. If the P in our example was rotated by 90 degrees, the current program would never find it. You could write code for it though. A brute force algorithm would be to generate all possible rotations, all possible scales and then do the matching. But that would be extremely slow. So again, use some other techniques.

We’re done!

Hope you learned something from this tutorial. I tried to be as clear and precise as I could. If you got any questions? Criticism? Suggestions? Leave a comment, or contact me.

Issues? Suggestions? Visit the Github issue tracker for AI Shack

Back to top

55 Comments

  1. Jason
    Posted July 16, 2010 at 9:23 pm | Permalink

    Hey thanks a lot for the tutorial! But I ran across a problem. After typing up this code, it compiled fine. But when I run it, I get a segmentation fault on the line

    cvMatchTemplate(imgOriginal, imgTemplate, imgResult, CV_TM_CCOEFF_NORMED);

    I thought it might be a problem with the different calculation methods so I tried changing to the square coefficients and the square coefficients normalized, etc. but that didn’t change anything.

    Any ideas on what might be going on? Thanks again!

    • Posted July 16, 2010 at 9:41 pm | Permalink

      Hmm.. did you check if the image and the template have loaded?

      • Jason
        Posted July 16, 2010 at 10:21 pm | Permalink

        Yeah, I am able to display them both. I am on a mac and so I wasn’t able to add those library files. Do I need to do that using a mac or are those dependencies already taken care of?

        Thanks a lot.

        • Posted July 17, 2010 at 8:35 am | Permalink

          I just checked the code on my system and its working…

          I’ve never used a mac, but I’m sure you need to take care of dependencies on a Mac too. But because you’re getting a segmentation fault, you’re probably doing this part correct.

          Did you initialize the resultant image properly? With the width+1 and height+1 size, 32F type and 1 channel?

  2. SJ
    Posted July 22, 2010 at 7:32 pm | Permalink

    Link not working above:
    “When you perform template matching in OpenCV, you get an image that shows the degree of “equality” or correlation between the template and the portion under the template.

    The technique <———- This link is not working!!

    • Posted July 22, 2010 at 8:01 pm | Permalink

      Hi! Fixed it! It looks like the old articles have got a lot of bad links. Thanks for pointing out!

  3. sundowatch
    Posted July 23, 2010 at 2:10 pm | Permalink

    Well. We find the best match in the Image by using cvMinMaxLoc(). But I want to find other matches.
    How can I do it?

    • Posted July 23, 2010 at 4:24 pm | Permalink

      You can iterate over each pixel of the result image. Check the value at each pixel (its a floating point number). Then you can decide which all positions you want.

      • sundowatch
        Posted July 23, 2010 at 7:49 pm | Permalink

        So, I won’t use cvMinMaxLoc();

        Thanks.

  4. Deepak
    Posted August 28, 2010 at 10:26 pm | Permalink

    will the template match work with slight variation in sizes??

  5. lambk89
    Posted November 3, 2010 at 12:19 pm | Permalink

    Hi every one! I’m studying image processing. can you help me about OCR using template matching?
    Thank you!

    • Posted November 12, 2010 at 1:39 am | Permalink

      The OCR should be simple – you take each character’s template. Template match it through the image. Wherever you get a high match, you “mark” that character! This should be simple enough to get you started!

  6. Manik Singhal
    Posted December 23, 2010 at 4:04 pm | Permalink

    hi utkarsh,

    i want to know how can i create templates for hand gestures?

    What size should it be?

    Plz reply

    thanks

    • Posted January 7, 2011 at 2:31 pm | Permalink

      Um… I doubt if you’ll get good results with template matching.

  7. AceGhatge
    Posted January 27, 2011 at 8:17 am | Permalink

    What if there are multiple template matches? Which will it return? and if we want it to iterate through the resulting set of template matches how will we achieve this?

  8. Pramukh
    Posted February 3, 2011 at 4:01 pm | Permalink

    HI!! we are working on a real time template matching project, the template isa coloured cap attached to our finger and it is getting matched real time right now, but the template should be selected everytime we start the application using mouse click n mouse handle function, is there any way that we can store the template in harddrive and give that template as the input to the app and get it matched….? Can you please let me know the procedure…?

    • Posted February 8, 2011 at 1:42 pm | Permalink

      If you have coloured caps attached to your fingers, you have a much faster way of recognizing them – Tracking colored objects in OpenCV

      • Pramukh
        Posted February 9, 2011 at 10:59 pm | Permalink

        cool…! we r using the same but v’ve got to match 3 template in a single search window(ROI) wer one among the templates is responsible of the movement of the search window.. is der any othr technique to match othr den template matching

        • Posted February 10, 2011 at 12:29 am | Permalink

          Hmm… you could trying using some kind of features (SIFT, SURF, corners, etc). Then you’d be able to check the displacement of each template within the window.

      • pramukh
        Posted February 10, 2011 at 10:50 pm | Permalink

        it doesn’t take the coloured caps as the input from harddisk… cvLoadImage(“path”); i want input from this command… and ive got three templates to match

        • Posted February 10, 2011 at 10:56 pm | Permalink

          What doesn’t take input from the cvLoadImage function?

  9. Pramukh
    Posted February 11, 2011 at 9:20 pm | Permalink

    i mean it takes the pic but doesn’t match that template in realtime video.. thats my query

    • Posted February 11, 2011 at 9:22 pm | Permalink

      Yes, template matching is slow. Try the color tracking method above… that is quite fast.

  10. Pramukh
    Posted February 11, 2011 at 9:49 pm | Permalink

    yea… that is just for one color at a time right ??? is it possible to match different color in the same frame simultaneously??? if so how to set the HSV?? threshold??? and to get the position of matching template??

    • Posted February 11, 2011 at 9:54 pm | Permalink

      Yes, it’s possible. Just do the same thing again for the other colors. For checking thresholds, try MS Paint. I’ve dealt with finding the position in the article.

  11. Pramukh
    Posted February 11, 2011 at 10:02 pm | Permalink

    cool… thanks a lot for your time and quick reply…and tutorials as well… ill try and reply back the results… thank you so much

  12. Malav
    Posted February 28, 2011 at 3:28 pm | Permalink

    Hi,
    I am using cvMatchTemplate() function for my application. But it is quite slow.
    I want real time application. How can i optimise this function to match template in 100 to 200 ms.

    Thank You!

    • Posted March 3, 2011 at 12:57 pm | Permalink

      Template matching is slow. I doubt if you can do it faster (the OpenCV functions are already optimized). Try using smaller images – that will speed it up real fast.

  13. Ashish
    Posted March 8, 2011 at 12:01 am | Permalink

    The code doesn’t match the eyes if it is given a template eye that is other than the eye of the face in the image.Can u tell us how to generalize it ?

    • Posted March 9, 2011 at 9:40 am | Permalink

      I’ve seen HAAR classifiers work quite well for detecting eyes.

  14. Posted March 17, 2011 at 9:41 am | Permalink

    Hi Utkarsh, I read ur tutorials, they so good and thanks for that.
    I work now with robotics project, my goal is to make the hixa robot navigate by using camera. My robot now followes the red, green or belue object goal. I used BGR color but I face some problems when the robot navigate in colored place. please, can you help me to find procedure petter than this. I tried to use hsi color but I can’t find the values for each color.

  15. Janice
    Posted March 27, 2011 at 9:50 pm | Permalink

    Hey! Thanks for your tutorial! It helps me a lots in my project!
    I got a question, can I use “cvMatchTemplate” function to match a motion with a picture?
    let say I want to detect a hand gesture whether it is correct or not (in real time).

    I hope you can help me!
    thank you so much!

  16. KB
    Posted March 31, 2011 at 10:20 am | Permalink

    Thank you. I compared your code with others, found that there is one point mis-match.
    You are using cvMinMaxLoc() BUT the other sample code I have will scan thru each pixel and compare threshold.
    Result : your code is faster (as you did not scan and compare threshold for each pixel) but one mis-matching. Any idea ?
    Please advise.

    • Posted April 29, 2011 at 9:41 pm | Permalink

      If you compare against a threshold, you can get multiple points. With MinMax, you get exactly one point for the minimum and one point for the maximum. Maybe that’s why the mismatch happened.

  17. richmond
    Posted April 10, 2011 at 4:24 pm | Permalink

    yo utkarsh im using match template in a real time project the problem is it always find the best match and draw the rectangle in any locations. how can we declare that the objct is not found and found if it is detected?
    thank you in advance ^^

    • Posted April 29, 2011 at 8:04 pm | Permalink

      What do you mean declare? You could use printf’s. Or maybe render a rectangle around the detected region.

  18. Ahmed
    Posted April 13, 2011 at 11:22 am | Permalink

    Great job Utkarsh,
    please, Could you help me to make webcam pcture smaller?
    I use camera with 640, and 480 pixel and want my image with 180, 120 pixels is that posible with opencv or I use other techniques?. If I use smaller picture, can I use other processes such as template matching or SIFT to detect object?.

    with my regards
    Ahmed

  19. Venu Gandhe
    Posted April 19, 2011 at 12:12 am | Permalink

    Hi Utkarsh,
    My name is Venu. I am doing my thesis on image processing but i am very new to image processing. The goal of my project is to detect objects(vehicles, buildings and persons) in images (that are taken by UAVs). For this i wanted to use Haar classifier but i have very limited data set that is not enough to train the classifier. Then i wanted to use template matching but i read in your tutorial it doesn’t support rotations and scaling (so we cant generalize the template). Is there any other method to detect and classify objects in image.Could you please help me?

    Thanks & Regards
    Venu Gandhe

    • Posted April 29, 2011 at 9:20 pm | Permalink

      Try using some object detection algorithms like SIFT or SURF. Might be helpful.

      • Venu Gandhe
        Posted June 3, 2011 at 4:39 pm | Permalink

        Hi Uthkarsh,
        I found a method called ” Training free object detection using LARK” http://users.soe.ucsc.edu/~rokaf/ObjectDetectionFromSingleImage.html#OpenCV
        I found it is a very good method as it need only one image as training sample. But the openCv implementation he gave uses som ROS (Robot operating system) libraries. I have installed it and gone through some tutorials but i couldn’t run it. Do you know any thing about ROS. Could you please help me.
        Thanks & Regards
        Venu Gande

  20. hema lak
    Posted May 5, 2011 at 3:08 pm | Permalink

    Hese tutorials are very much helpful man.

    Thanks a lot

  21. Anastasia
    Posted May 20, 2011 at 5:55 pm | Permalink

    Very good work and really helpful tutorial!
    Congrats and thank you! :-)

  22. Wilson Talaugon
    Posted June 24, 2011 at 3:46 am | Permalink

    Hi Uthkarsh,

    I got the template matching code your provided working. How do I modify the code to template match all occurrences within the same image? Let’s say I have 4 identical patterns within the same image file.

    Thanks,
    Wilson

    • Posted June 25, 2011 at 12:10 am | Permalink

      For that you need to find the four highest values in imgResult. Those will be the best four matches in the image.

  23. oanhvo
    Posted July 11, 2011 at 12:33 am | Permalink

    hi, i’m used template matching, but I do not understand the operation, the advantages and disadvantages of each methods.who can help me? thank

  24. AraZZ
    Posted August 20, 2011 at 7:11 pm | Permalink

    Hi Utkarsh!
    Can I write template matching in pure java with openCV?

    • Posted September 2, 2011 at 12:24 pm | Permalink

      Of course you can. You just need to calculate one value for each pixel. There’s a formula to calculate it.

  25. erum
    Posted January 13, 2012 at 6:08 pm | Permalink

    can anyone tell me how to create a loop to find all the possible matches in an image if there’s more than one match?

  26. salva
    Posted January 14, 2012 at 12:56 am | Permalink

    Hellooo all, just FYI, there is a ‘fastmatchtemplate’ function, if you need more speeeeed.
    But it doesn’t work well with rotations or scales, as cvMatchTemplate. To solve this in both cases you can take a look for a document called:
    FT-Based Technique for Translation,Rotation, and Scale-Invariant Image Registration
    I hope this helps somebody

  27. nilaf
    Posted January 19, 2012 at 1:24 am | Permalink

    what technique you recommend for comparing for dynamic features

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>