For my application I am looking for a free, fast and scale-invariant template matching algorithm. The templates can only be scaled within the scene (no skew or rotation) and the scale is unknown. Scale can go up from 400% to 25%. All pictures are noise-free.

I have considered the following:

  • SIFT: Highest accuracy so far. However it is licensed and pretty slow (3sec)
  • ORB: Performance still not fast enough (1.5sec). Accuracy also poor on scaling.

What is the best algorithm in terms of accuracy for this particular problem? And which is the quickest? Are there any algorithms specially designed for this particular problem?

  • $\begingroup$ Can you post some pictures of what you are trying to match or add some details? For instance are you using RGB or grayscale images, what characteristics does your template have, where do you espect to match the template (complete random or located). A bit of context would help! $\endgroup$ – Louis Lac Jul 3 '18 at 11:58
  • $\begingroup$ Cannot post those images (NDA), but they're similar to the icons on your desktop. They are RGB images but I don't care whether the algorithm uses grayscale or not. Just care where in the image the template is. $\endgroup$ – hasdrubal Jul 3 '18 at 12:11
  • $\begingroup$ the most accurate algorithm would be to use a template library that spans all the scales but that is generally infeasible. you really haven’t defined enough to define a trade space. Everyone wants fast algorithms that are near their upper performance bound. $\endgroup$ – Stanley Pawlukiewicz Jul 3 '18 at 14:21
  • $\begingroup$ "similar to the icons on my desktop" – um, I've went from Win3.11 through win95 before starting to use Linux, and if I compare win10 icons to winxp and win95 icons, there's a lot of difference, and use a lot of different icon sets on my Linux machines: Can you actually post an example? Also, the NDA thing really hurts our ability to help you at all. $\endgroup$ – Marcus Müller Jul 3 '18 at 16:51

To increase the speed, I think the dimensionality of the feature descriptors should be reduced. SIFT feature descriptor is of 128 dimensions.

So you can try PCA-SIFT which reduces the descriptor number to 20. It uses Principal Component Analysis to the SIFT descriptors.

You can also try using Speeded Up Robust Features (SURF). The feature descriptors obtained from SURF are invariant to rotation and scale, and it can reduce the dimensions of feature descriptors significantly. it enables faster feature detection as well as template matching. Also, MATLAB has a specific command for SURF i.e. detectSURFFeatures, so if you are using MATLAB for your job you are in luck. I think OpenCV also has the SURF feature command so that you can use it on python too. I have used the SURF features which I think is pretty fast.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.