Resizing Algorithms

In this article I will describe the most common algorithms for resizing images and in particular how to convert images to a smaller size (“Down Rezing.”)

Resizing bitmaps or pixel based images to a smaller dimension consists of a mapping of a larger group of pixels in the original picture to a smaller group of pixels or even a single pixel. This seems pretty obvious; you start with a larger image (more pixels) and end up with a smaller one (less pixels.) The important question is how you go about it. What algorithm will produce the best quality picture?

When you are shrinking an image to half its size you could simply decimate or discard every other pixel. But you end up with a very bad looking picture.

Let’s say that you divide the target image in a grid. Now, each cell in this grid corresponds to one pixel. We’ll assume that the dimensions of the source image are multiples of the target image dimensions to make things easier. You then make the same grid division on the source image so that you end up with the same number of cells in the grid. The cells in the source image grid will now contain more pixels than the target image. (Figure 1)

In nearest neighbor interpolation (Figure 1) you choose the pixel that is closest to the center of the grid without any regard to the other pixels in the grid. The images produced by this algorithm are of very poor quality as much of the detail is lost because none of the surrounding pixels are taken into account when computing pixels for the new image.

Bi-linear is another fast algorithm that is very common that consists of entering four neighboring pixel values into a bi-linear type equation (it computes the weighted average of the four pixels). The result of this equation gives you the value of the pixel in the target image.

Bi-cubic interpolation produces much better quality pictures than bi-linear, but it takes much more processing time as the equations for calculating the value of pixels in the target picture are more complex. It takes into account the values of neighboring pixels and how they change.

There are many other methods such as fractals and super sampling that produce even better quality images. They usually take longer to compute also, but if quality is what you are after, you should consider using them. The link below shows some very good samples of the each method. The samples on the page show enlarging, but I hope you get the idea.

http://www.dpreview.com/learn/?/key=interpolation

Next post will cover the specifics of resizing High Definition content to Standard Definition.