Page 148 -

3.5 Pyramids and wavelets 127

Exercises 3.11, 3.16, 3.17, 3.21, and 3.28 have you implement some of these operations
and compare their effectiveness. More sophisticated techniques for blur removal and the
related task of super-resolution are discussed in Section 10.3.

3.5 Pyramids and wavelets

So far in this chapter, all of the image transformations we have studied produce output images
of the same size as the inputs. Often, however, we may wish to change the resolution of an
image before proceeding further. For example, we may need to interpolate a small image to
make its resolution match that of the output printer or computer screen. Alternatively, we
may want to reduce the size of an image to speed up the execution of an algorithm or to save
on storage space or transmission time.
Sometimes, we do not even know what the appropriate resolution for the image should
be. Consider, for example, the task of finding a face in an image (Section 14.1.1). Since we
do not know the scale at which the face will appear, we need to generate a whole pyramid
of differently sized images and scan each one for possible faces. (Biological visual systems
also operate on a hierarchy of scales (Marr 1982).) Such a pyramid can also be very helpful
in accelerating the search for an object by first finding a smaller instance of that object at a
coarser level of the pyramid and then looking for the full resolution object only in the vicinity
of coarse-level detections (Section 8.1.1). Finally, image pyramids are extremely useful for
performing multi-scale editing operations such as blending images while maintaining details.
In this section, we first discuss good filters for changing image resolution, i.e., upsampling
(interpolation, Section 3.5.1) and downsampling (decimation, Section 3.5.2). We then present
the concept of multi-resolution pyramids, which can be used to create a complete hierarchy
of differently sized images and to enable a variety of applications (Section 3.5.3). A closely
related concept is that of wavelets, which are a special kind of pyramid with higher frequency
selectivity and other useful properties (Section 3.5.4). Finally, we present a useful application
of pyramids, namely the blending of different images in a way that hides the seams between
the image boundaries (Section 3.5.5).

3.5.1 Interpolation

In order to interpolate (or upsample) an image to a higher resolution, we need to select some
interpolation kernel with which to convolve the image,

g(i, j)= f(k, l)h(i − rk, j − rl). (3.78)
k,l
This formula is related to the discrete convolution formula (3.14), except that we replace k
and l in h() with rk and rl, where r is the upsampling rate. Figure 3.27a shows how to think
of this process as the superposition of sample weighted interpolation kernels, one centered
at each input sample k. An alternative mental model is shown in Figure 3.27b, where the
kernel is centered at the output pixel value i (the two forms are equivalent). The latter form
is sometimes called the polyphase filter form, since the kernel values h(i) can be stored as r
separate kernels, each of which is selected for convolution with the input samples depending
on the phase of i relative to the upsampled grid.