Skip to content

About subsampling (image pyramid)🔗

For all matching approaches except the descriptor-based matching, a so-called image pyramid can be used to speed up the search. In some approaches, the image pyramid is created for the search image as well as for the template image.

The pyramid consists of the original, full-sized image and a set of downsampled images. For example, if the original image (first pyramid level) is of the size 600x400, the second level image is of the size 300x200, the third level 150x100, and so on. The object is then searched first on the highest pyramid level, that is, in the smallest image. The results of this fast search are then used to limit the search in the next pyramid image, whose results are used on the next lower level until the lowest level is reached.

Using this iterative method, the search is both fast and accurate.

In case of noise it can even improve the robustness of the search, but for artificial images ringing artifacts may appear.

Figure 1 depicts four levels of an example image pyramid together with the corresponding model regions.

Figure 1: The image and the model region at four pyramid levels (original size and zoomed to equal size).

Note that when images are downsampled, different “events” occur. Primarily, specific structures disappear in higher pyramid levels. As shown in Figure 1, thin structures disappear sooner than thick ones.

“Thin structures” includes the different structures of the actual model but also the distances between them. Thus, small structures of the model may disappear, but they can just as well be merged if the distances between them are small.

Additionally, the boundaries of structures blur in higher pyramid levels and their contrast decreases. In and , this effect is shown for a one pixel wide line.

One pixel wide high contrast line Line blurs to a broader line with lower contrast on a higher pyramid level

For more complex patterns, this may lead to the disappearance of a pattern or even to the creation of a new pattern.

Examples for the disappearance of patterns that are caused by the blurring of structures are given for the small characters in Figure 1, for a regular grid of one pixel wide high contrast lines in , and for a pattern that consists of high contrast rectangles with a distance of one pixel in Table 1. The latter example also shows that new patterns can be created within the pyramid. Before the pattern is blurred to a homogeneous area, a different regular pattern is created.

Additionally, it is possible that new structures appear because the region of interest was selected too large and thus, contours that were not part of the model in the first pyramid level become part of the model in a higher level.

One pixel wide high contrast grid Lines blur to a homogeneous gray value area on a higher pyramid level
Table 1: In the pyramid, a regular structure of rectangles with distances of one pixel shows the following behavior: Level 1 and 2 still represent the correct model contours, level 3 and 4 produce new regular patterns, and in level 5 a homogeneous gray-value area is obtained.
White rectangles with one pixel distance
Level 1 Level 2 Level 3 Level 4 Level 5

The blurring of structures induces that besides the size also the contrast determines whether a structure is still contained in a higher pyramid level or not.

After the downsampling, a high contrast structure of sufficient size may still have enough contrast to be recognized, whereas a structure of the same size but with a low contrast can not be distinguished from the background anymore.

For example, in Figure 2 the large but bright ‘V’ of the ‘MVTec’ logo disappears in front of the bright background at a pyramid level in which the large high contrast characters are still contained.

Figure 2: In the pyramid, a part of the model with a low contrast (the ‘V’ of MVTec) disappears.