Computer Vision - Gaussian Pyramid, Scale Space and Pattern Matching

Question

I am planning to implement a pattern matching algorithm using something like correlation as a matching metric.

I know that the template I am going to use will, if present, have different sizes in the target images. The interval of sizes might be something like : x 0.5 , x 0.75 , x 1.0 , x 1.25 , x 1.5 , x 2.0 of the original template size.

To speed up the search it is suggested in various articles to build a gaussian pyramid of both the template and the target search image.

However I am not able to relate in any meaningful way the number of pyramid levels to create (for model and for target) , the object scales as described above, and the gaussian filter sigmas (used when creating the pyramid) !

Could someone shed any light on this ?

For example 1 level of the pyramid reduces the resolution of the image by 2 (is this the same as saying that the image has been scaled by 0.5 ) ?

Than what about a pyramid level of -1 (which should make the image bigger x 2.0) : with what gaussian filter should it be treated before upsampling ?

What about object scales (e.g. x 1.25) which fall in-between pyramid levels ?

Thanks to anyone who could provide some insight/references, Todor

Answer 1

Template matching is related to finding the maximum correlation between two signals, where one of the signals (the image being explored) is usually much bigger than the reference signal (the object being searched for). Obviously, the best correlation score can only be obtained when the size of the object in the image is equal to its size in the template (intuitively, both shapes will superpose).

However I am not able to relate in any meaningful way the number of pyramid levels to create (for model and for target)

The number of scales is related to two things:

• the size of the object of interest in the explored image
• the computation time reduction that you want to obtain.

To have the best localization accuracy, you need to have one template image that matches exactly the size of the object in the explored image. Thus, if you don't know a priori this size, but you have instead a range of sizes, your template pyramid should include each of these sizes.

Since the template matching part can be expensive (one correlation computation for each possible position of the template in the image), you want to reduce the number of pixels explored. Thus, you create a pyramid of the image to explore, start by looking for the object at the coarsest scale to get a rough position that gets refined at the next scale, etc. Again, since the size of the object needs to match between the template and the explored image, you need to rescale appropriately each of the images from the pyramid that you built for the template (previous paragraph).

For example 1 level of the pyramid reduces the resolution of the image by 2 (is this the same as saying that the image has been scaled by 0.5 ) ?

It depends... Reducing the resolution by two along each dimension divides the number of pixels by 4. This is usually referred to as scaling by 0.5 but as an image resolution reduction by 4.

A common practice is to divide the number of pixels by 2, yielding a $\sqrt{2}$ factor along each dimension.

Than what about a pyramid level of -1 (which should make the image bigger x 2.0) : with what gaussian filter should it be treated before upsampling ?

You need to use image interpolation techniques here. OpenCV uses (in optical flow methods) a gaussian upsampling by injecting $0$'s along the odd lines/columns then applying a gaussian blur.

Answer 2

Generating pyramids and searching for different scales are two different things.

Pyramid generation is commonly referred as a technique to speed up, where each level of the template is sought in each corresponding level of the search image. If you satisfy a sufficient match score in the higher levels of the pyramid, then you could stop searching further, propagate to the next level. On the lower level of the pyramid (bigger image), you could restrict the domain of search. In other words, you could hypothesize a range within which the template should lie. In the finest level, you just apply a brute for search but in a really small area.

Scale is a different story. To search for multiple scales, you have to generate the template in multiple scales and search them. Note that only the template should be generated in multiple scales. And if you are using a pyramidal matching, then separate pyramids should be built for these scales too. Searching over a variety of scales might seem insane, but if you extract a sparse set of meaningful features from the image (such as strong gradients), this search can in fact be made feasible.

Generally, it is a good idea to choose the number of levels of pyramids as large as possible because it significantly reduces the time necessary to find the object. On the other hand, number of levels must be chosen such that the model is still recognizable and contains a sufficient number of points of interest on the highest pyramid level. If the number of pyramid levels is chosen too small, the time required to find the model may increase. Typically $4$ is a descent value.

Still if you need more accuracy, you could always go for a sub-pixel registration as a final refinement stage.

If implemented in a very naive fashion, template matching is very exhaustive. However, there are many efficient ways to speed it up. For further reading, I would for example recommend:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.221.7835&rep=rep1&type=pdf