Algorithm for Scale Invariant Template Matching

Question

I am using opencv for finding template images in a video stream. The elements I am trying to find are UI elements of android apps.

Classic template matching is working quite well. But only as long as the scene and the template share the same resolution. My requirement is to have this working for different scene resolutions (different devices).

What I tried so far is:

1. Rescaling the template at different resolutions in a loop and checking. As soon as my result increases above a certain threshold, I consider it a match. Problem: Not very robust, extremely slow
2. AKAZE and ORB: Don't really provide the expected results. I don't know if I am missing something, but it doesn't look like those algorithms are made for what I am trying to do. I am getting results like this:

Any help or ideas are highly appreciated!

A couple of examples:

Scene: Template:

Scene2: Template2:

Scene3: Template3:

Answer 1

If your templates are all based on some kind of text you may use some kind of OCR to match the text itself and not only by features.

Regarding features, you may read: A Comparative Analysis of SIFT, SURF, KAZE, AKAZE, ORB, and BRISK.
Specifically have a look at the following sections:

It seems your feature extractor usually use corners while you need more general purpose features.

It seems SURF and SIFT will be better suit for your case. Since your search should be not care about rotations (At least according to your examples) what you can do is a template matching over the features and not the image. Namely you are after a scaling of the feature location of your template in the image.

Answer 2

Just wanted to give a little bit of modern answer to this question. In the 'machine learning' sense. Such matching problems are (maybe a little unfortunately) rebranded as one-shot object detection or if you like to estimate the orientation as well, I would go for one-shot pose estimation. People also use single-shot, in a similar vein. As such, there many attempts, which adopt an end-to-end deep learning framework to quickly do the job. Examples include:

Siamese Neural Networks for One-shot Image Recognition Koch, Gregory, Richard Zemel, and Ruslan Salakhutdinov ICML deep learning workshop 2015, https://www.cs.cmu.edu/~rsalakhu/papers/oneshot1.pdf

One-Shot Object Detection with Co-Attention and Co-Excitation Ting-I Hsieh, Yi-Chen Lo, Hwann-Tzong Chen, Tyng-Luh Liu Neural Information Processing Systems (NeurIPS), 2019, https://github.com/timy90022/One-Shot-Object-Detection

OnePose: One-Shot Object Pose Estimation without CAD Models Jiaming Sun, Zihao Wang, Siyu Zhang, Xingyi He, Hongcheng Zhao, Guofeng Zhang, Xiaowei Zhou CVPR 2022, https://zju3dv.github.io/onepose/

Not sure about OpenCV, but the works above provide source codes and there are several tutorials online, which describe these modern solutions. All of those should be very easy to integrate into your current framework but casting the opencv images to pytorch tensors.

Answer 3

I believe Haar Cascades(used by Viola-Jones) are inherently scale-invariant. Also severely deprecated by modern Neural Networks, but I know nothing about those. It also doesn't do any OCR - if you need that you would need to run a separate algorithm on the extracted sub-image.

Answer 4

You may want to try something initially supervised.

For example, https://docs.opencv.org/3.4/d1/d2d/classcv_1_1ml_1_1SVM.html

would work if you have data to train it against.

Answer 5

A brute force method might be to «sweep» the parameters

• horizontal shift
• vertical shift
• scale

Do some «similarity metric» (eg sum of squared error) and report any that exceed some threshold. It seems that you are (in effect) doing something like this but finding it too slow?

Next, you might try to optimize the above algorithm by various domain specific shortcuts. Doing an initial search on video downsampled in space and time (and colorspace - i.e. luminance, perhaps also number of bits/primary) might allow you to avoid wasting cycles on bad candidates.

How large is your set of templates? 10s, 100s, 1000s?

Answer 6

Why not try to program it by percentage from the beginning? Like this, it's scalable in any resolution. Loop and checking would only generate more work and consume more resources. If there is a way to display the elements by percentage, you get the result in any resolution.