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.