Fast Affine Template Matching

Standard

This is a port of Korman et al implementation of Fast Affine Template Matching in C++.

Here’s roughly how the algorithm works:

  • Create a list of configurations that describes a range of affine transformations for the template.
  • For each of the configuration, calculate the Sum of Absolute Differences (or other scoring method), but only for a certain number of sampled points, rather than for every pixels in the template
  • Filter out the configurations based on the previously calculated scores / distances
  • Expands the remaining configurations for the next round and loop until the best score hits below certain threshold.

Here are some clips showing the result of applying the algorithm:

There are still many details that my eyes might have glazed over, thus you might want to read the original literature over here. Overall, the speed of the algorithm seems to depend on the number of configurations, and some other parameters that might require tweaking. However, I still need to peruse thru the paper to understand the effect of each parameter.

You can find my codes here: https://github.com/subokita/FAsT-Match. It requires OpenCV, Intel TBB, and C++11.

References:

[1] “FAsT-Match: Fast Affine Template Matching”, Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan. CVPR 2013, Portland

 

Advertisements

10 thoughts on “Fast Affine Template Matching

  1. Eduardo Moura

    Hello Saburo, I’m Eduardo, a computer vision student like you, and I’m trying to compile and run our example code in VS2010.

    I’ve made some adjustments to compile your code, but when I run the code I’m receiving the following error at this point:

    /* Convert each configuration to corresponding affine transformation matrix */
    tbb::parallel_for( 0, no_of_configs, 1, [&](int i) {
    Mat affine = configs[i].getAffineMatrix();

    /* Check if our affine transformed rectangle still fits within our boundary */
    Mat affine_corners = (affine * corners).t();
    affine_corners = affine_corners + transl;

    if( WITHIN( affine_corners.at(0), top_left, bottom_right) &&
    WITHIN( affine_corners.at(1), top_left, bottom_right) &&
    WITHIN( affine_corners.at(2), top_left, bottom_right) &&
    WITHIN( affine_corners.at(3), top_left, bottom_right) ) {

    affines[i] = affine;
    insiders[i] = true;
    }
    });

    OpenCV error:

    OpenCV Error: Assertion failed (dims <= 2 && data && (unsigned)i0 < (unsigned)(s
    ize.p[0]*size.p[1]) && elemSize() == (((((DataType::type) & ((512 – 1) <> 3) + 1) <> ((DataType::type)
    & ((1 << 3) – 1))*2) & 3))) in cv::Mat::at, file c:\eduardo\opencv-2.4.9\build3
    2\include\opencv2\core\mat.hpp, line 569

    My environment is Windows 8.1, OpenCV 2.4.9, TBB 4.2 and VS2010 with C++10.

    Could you please give me some help to solve the problem?

    Thank's in advance!
    Regards, Eduardo.

  2. Anonymous

    Hi Saburo, I’m Chunyang, a stats person who happens to have to do some image processing in my research… I don’t quite understand C++ code, so I’ve no idea what’s going on here when I run your matlab code.
    Here are the error messages I got. Could you please give me some advice to try your algorithm for the template matching?
    Thank you!! Appreciate your help!
    Chunyang

    Error using mex
    Configs2Affine_mex.cpp
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(33) : warning C4267: ‘=’ :
    conversion from ‘size_t’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(38) : error C2664:
    ‘mxCreateNumericMatrix_700’ : cannot convert parameter 4 from ‘int’ to ‘mxComplexity’
    Conversion to enumeration type requires an explicit cast (static_cast, C-style cast or function-style cast)
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(44) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(45) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(46) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(47) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(48) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(49) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(50) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data
    C:\Users\Chunyang Li\Documents\PhD\Image Processing\documents\FastMatch_v1\mex\Configs2Affine_mex.cpp(51) : warning C4244: ‘=’ :
    conversion from ‘double’ to ‘int’, possible loss of data

  3. milk

    Hello Saburo,

    I have a question regarding your port.
    Did you port the code from MatLab, or you simply write the code yourself?

    In other words, I would like to know whether the result obtained from your code would be the same as the original MatLab code.

    Thank you.

    • I converted it from Matlab (actually ported halfway to Octave, then realized that Octave doesn’t have enough library to support everything), The original author has the source code on his site. The result should be similar, and there’s a slight error in the original .mex file, which I have notified the author and he did realize that it’s a bug
      .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s