1

When I say template matching, I'm referring to finding occurrences of a small image (the template) in a larger image.

The OpenCV library provides the trivial solution, that slides the template over every possible location of the image. While this implementation provides translation invariance, it provides no stretching/scaling invariance. To get stretch *and* translation invariance, one would need to stretch the template (or shrink the main image) until iteratively, running the original template check over the image. This increases complexity to $O(S * n^2)$ where S is the number of different resolutions one checks - if one want's to check every possible resolution, the overall complexity is $O(n^4)$. Effectively, you generate $O(n^4)$ subsections and check if they're equal to the template.

From what I was taught, Image Segmentation Networks do just this - however, instead of using the basic template matching (i.e. checking the pixels match) the generated subsection is put through a classifier network - so this would be more expensive than standard templating.

My question is, are my calculations correct - for complete subsection generation, is the complexity $O(n^4)$ and is there really no better algorithm for generating these subsections - used by both image detection algorithms?

Hi and welcome to AI SE! OpenCV also provides other tools to perform template matching (such as a combination of SIFT, FLANN and findHomography), which, in theory, should be translation and scale-invariant. – nbro – 2020-06-07T22:33:48.853