• FastMatchTemplate

Fast Match Template

Background

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 Algorithm

The following algorithm bolds the variables that are used in the example code.

1. Both target and source image are down sampled numDownPyrs times

2. 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)

3. The numMaxima best locations are found

4. For each point where a maxima was located:

   1. Original source image is searched at point +/- searchExpansion pixels in both x and y direction

5. If match score is above matchPercentage then the location and score is saved in the foundPointsList and confidencesList, respectively

6. If findMultipleTargets is true, an attempt will be made to find up to numMaxima targets

7. (Optional) The targets can be drawn to a color version of the source image using the DrawFoundTargets function

The Code

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.

FastMatchTemplate_OCV21.tar.gz

Functions

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 );