FYI: Sikuli's template matching

[David Röthlisberger]

It looks like Sikuli uses "pyramid template matching"[1] to find the
region-of-interest more quickly than the standard OpenCV matchTemplate
function, and at the last stage it just uses matchTemplate to
confirm.[2]

Sikuli's matchTemplate uses CCOEFF_NORMED[3], while we found that
SQDIFF_NORMED usually gives better results. Sikuli switches to
SQDIFF_NORMED if it detects that the template is a solid block of the
same color, presumably because telling colours apart is a weakness of
CCOEFF_NORMED?


"Pyramid template matching" is an extremely simple concept and it only
improves the speed, not the accuracy, of the basic matchTemplate
algorithm. It would be worth implementing though; I'm going to have a
stab at it.

[1] http://opencv-code.com/tutorials/fast-template-matching-with-image-pyramid/
[2] https://answers.launchpad.net/sikuli/+question/224151
[3] https://github.com/sikuli/sikuli/blob/293c0171/sikuli-script/src/main/native/pyramid-template-matcher.cpp#L98

[David Röthlisberger]

On 30 Oct 2013, at 18:04, David Röthlisberger wrote:
> It looks like Sikuli uses "pyramid template matching"[1] to find the
> region-of-interest more quickly than the standard OpenCV matchTemplate
> function, and at the last stage it just uses matchTemplate to
> confirm.[2]

I've done a prototype of "pyramid template matching" (i.e. running
OpenCV's matchTemplate function against downscaled versions of the
template & source images to identify the likely match region, and
then only process that region in the full-size image):
https://github.com/drothlis/stb-tester/commits/templatematch-performance

It doesn't work 100% yet; it doesn't pass all "make check" unit tests,
and when run against a collection of templates + screenshots from the
YouView UI it provides the wrong result for 6% of them (out of 141).

However, the performance figures are encouraging:

tests/run-performance-test.sh reports 36fps (up from 4.0fps).

(Measured on my laptop's 1.8GHz Intel Core i7, using a 720p mpeg file on
disk as the video source).

With this video, every frame was a "no match", which means that the
match algorithm exits early, after the first `matchTemplate` at the
smallest level of the "pyramid". However, I believe that that
`matchTemplate` is the most expensive part of the algorithm; subsequent
passes are only performed on the area of interest identified by the
initial pass.

Testing the afore-mentioned collection of real screenshots (90% of which
do match, 10% don't) went from 32s to 6s (a 5x improvement, compared
with the 9x improvement measured by run-performance-test.sh).

[David Röthlisberger]

Stb-tester's implementation of "pyramid template matching" (a
performance optimisation for `stbt.wait_for_match` and
`stbt.detect_match`) is ready for review:

https://github.com/drothlis/stb-tester/pull/70

It passes all the stb-tester unit tests, as well as a private collection
of template images + screenshots taken from the YouView UI.

The performance improvement seems to be around 7 to 12 times faster,
depending on the size of the video frame, the size of the template
image, and whether or not the template image is present in the video
frame. This means that we can process more frames per second, which
means that:
* We can get more precise measurements like "how long did it take for
the button to appear".
* We can test more devices simultaneously on the same PC.

This new algorithm will be enabled by default. I don't expect it to
cause any problems, but you can disable it by setting
`match.pyramid_levels = 1` in your `stbt.conf` configuration file.

Thanks,
Dave.

[David Röthlisberger]

On 22 Nov 2013, at 12:03, David Röthlisberger wrote:
> Stb-tester's implementation of "pyramid template matching" (a
> performance optimisation for `stbt.wait_for_match` and
> `stbt.detect_match`) is ready for review:

This optimisation is now merged to master:
https://github.com/drothlis/stb-tester/commit/c0b42f0f

It is on by default; you shouldn't see any differences in behaviour
other than much faster image matching. You can disable it in your
configuration file by setting "match.pyramid_levels" to 1.

Cheers,
Dave.