Fast Match Template
For my undergrad thesis at SFU I created a vision system for a robotic helicopter using OpenCV. One of the tasks was recognition of a simple sign (white X on a black circle). I initially used the cvMatchTemplate function but found it to be slow (when searching 640x480 images) so I created a new function that made use of the cvMatchTemplate function in a much more efficient way, with identical results. I originally placed this code on the OpenCV Yahoo! group but have decided to place it here in order to better explain it.
The following algorithm bolds the variables that are used in the example code.
Both target and source image are down sampled numDownPyrs times
cvMatchTemplate function is called on shrunken images (uses CCOEFF_NORMED algorithm, also works with CCORR_NORMED but I have found better results with the former)
The numMaxima best locations are found
- For each point where a maxima was located:
Original source image is searched at point +/- searchExpansion pixels in both x and y direction
If match score is above matchPercentage then the location and score is saved in the foundPointsList and confidencesList, respectively
If findMultipleTargets is true, an attempt will be made to find up to numMaxima targets
(Optional) The targets can be drawn to a color version of the source image using the DrawFoundTargets function
Download the source here:FastMatchTemplate.tar.gz; see below for source code compatible with the new C++ interface for 2.0.
This archive includes a sample source and target bitmap to test with as well as a sample program. If you have installed OpenCV correctly and are using a Linux system, you should be able to simply run make in order to compile the program. I have tested this on Ubuntu 8.04 and some people that have emailed for help have compiled it on Windows.
Source for OpenCV 2.0+
I have updated the code to conform with the new C++ interface introduce in OpenCV 2.0. The functions below still apply except all IplImage structures are now replaced with Mat, CvPoint with Point, and CvSize with size.
The following is an overview of the additional functions and their parameters (C++):
/*============================================================================= FastMatchTemplate Performs a fast match template Returns: true on success, false on failure Parameters: source - source image (where we are searching) target - target image (what we are searching for) foundPointsList - contains a list of the points where the target was found confidencesList - contains a list of the confidence value (0-100) for each found target matchPercentage - the minimum required match score to consider the target found findMultipleTargets - if set to true, the function will attempt to find a maximum of numMaxima targets numMaxima - the maximum number of search locations to try before exiting (i.e. when image is down-sampled and searched, we collect the best numMaxima locations - those with the highest confidence - and search the original image at these locations) numDownPyrs - the number of times to down-sample the image (only increase this number if your images are really large) searchExpansion - The original source image is searched at the top locations with +/- searchExpansion pixels in both the x and y directions */ bool FastMatchTemplate( const IplImage& source, const IplImage& target, vector<CvPoint>* foundPointsList, vector<double>* confidencesList, int matchPercentage = 70, bool findMultipleTargets = true, int numMaxima = 5, int numDownPyrs = 2, int searchExpansion = 15 ); /*============================================================================= MultipleMaxLoc Searches an image for multiple maxima Assumes a single channel, floating point image Parameters: image - the input image, generally the result from a cvMatchTemplate call locations - array of CvPoint (pass in a NULL point) numMaxima - the maximum number of best match maxima to locate */ void MultipleMaxLoc( const IplImage& image, CvPoint** locations, int numMaxima ); /*============================================================================= DrawFoundTargets Draws a rectangle of dimension size, at the given positions in the list, in the given RGB color space Parameters: image - a color image to draw on size - the size of the rectangle to draw pointsList - a list of points where a rectangle should be drawn confidencesList - a list of the confidences associated with the points red - the red value (0-255) green - the green value (0-255) blue - the blue value (0-255) */ void DrawFoundTargets( IplImage* image, const CvSize& size, const vector<CvPoint>& pointsList, const vector<double>& confidencesList, int red = 0, int green = 255, int blue = 0 );