A Comparative Analysis of Image Scaling Algorithms

Image scaling is a geometric transformation used to resize digital images and finds widespread use in computer graphics, medical image processing, military surveillance, and quality control [1]. It plays a key role in many applications [2] including pyramid construction [3]-[4], super-sampling, multi-grid solutions [5], and geometric normalization [6].

In surveillance-based applications, images have to be monitored at a high frame rate. Since, the images need not be of the same size, image scaling is necessary for comparison and manipulation of images. However, image scaling is a computationally intensive process due to the convolution operation, which is necessary to band-limit the discrete input and thereby diminishes undesirable aliasing artifacts [2].

Various image scaling algorithms are available in literature and employ different interpolation techniques to the same input image. Some of the common interpolation algorithms are the nearest neighbour, bilinear [7], and bicubic [8]-[9]. Lanczos algorithm utilizes the 3-lobed Lanczos window function to implement interpolation [10].

There are many other higher order interpolators which take more surrounding pixels into consideration, and thus also require more computations. These algorithms include spline [11] and sinc interpolation [12], and retain the most of image details after an interpolation. They are extremely useful when the image requires multiple rotations/distortions in separate steps. However, for single-step enlargements or rotations, these higher-order algorithms provide diminishing visual improvement and processing time increases significantly.

Novel interpolation algorithms have also been proposed such as auto-regression based method [13], fuzzy area-based scaling [14], interpolation using classification and stitching [15], isophote-based interpolation [16], and even interpolation scheme combined with Artificial Neural Networks [17]. Although these algorithms perform well, they require a lengthy processing time due to their complexity. This is intolerable for real-time image scaling in video surveillance system. Hence, these algorithms have not been considered for the comparative analysis in this paper.

In this paper, firstly, image interpolation algorithms are classified and reviewed; then evaluation and comparison of five image interpolation algorithms are discussed in depth based on the reason that evaluation of image interpolation is essential in the aspect of designing a realtime video surveillance system. Analysis results of the five interpolation algorithms are summarized and presented.

• II.    Image Scaling

Image scaling is obtained by performing interpolation over one or two directions to approximate a pixel’s colour and intensity based on the values at neighbouring pixels. More the adjacent pixels used for interpolation, better the quality of interpolated output image.

Digital image interpolation is the process of generating a continuous intensity surface from discrete image data samples. Generally, almost every geometric transformation like translating, rotating, scaling, and warping requires interpolation to be performed on an image [18]. Such transformations are essential to any commercial digital image processing software. The perceived quality of the interpolated images is affected by several issues such as sharpness of edges, freedom from artifacts and reconstruction of high frequency details [18].

Interpolation algorithms attempt to generate continuous data from a set of discrete data samples through an interpolation function. These interpolation methods aim to minimize the visual defects arising from the inevitable resampling error and improve the quality of re-sampled images [19]. Interpolation function is performed by convolution operation which involves a large number of addition and multiplication operations. Hence, a trade-off is required between computation complexity and quality of the scaled image.

Based on the content awareness of the algorithm, image scaling algorithms can be classified as Adaptive image scaling and Non-adaptive image scaling.

Adaptive image scaling algorithms modify their interpolation technique based on the image content being a smooth texture [20] or a sharp edge [21]-[22]. As the interpolation method changes in real-time, these algorithms are complex and computationally intensive. They find widespread use in image editing software as they ensure a high quality scaled image. As the focus is on analysing image scaling algorithms for real-time applications, these algorithms are beyond the scope of the paper.

Non-adaptive image scaling algorithms like nearest neighbour, bilinear, bicubic and Lanczos algorithms have a fixed interpolation method irrespective of the image content.

• III.    Comparative Analysis of Image Scaling Algorithms

This section discusses the Non-adaptive Image scaling algorithms like nearest neighbour, bilinear, bicubic, modified bicubic, and Lanczos. Let P(x,y) represent the pixel in input image of MxN dimensions and U(i,j) represents the pixel in scaled/resized output image of size M’xN’. Let T be the transformation used for scaling. The each pixel of output image is computed by applying the transformation T on input image pixels as shown in Fig. 1.

Figure 1. Image scaling procedure

A. Nearest Neighbour Image Scaling

The simplest image interpolation method is to select the value of the nearest input image pixel and assigning the same value to scaled image pixel. The nearest neighbour algorithm (Fig. 2) selects the value of the nearest known pixel and does not consider the values of other neighbouring pixels, yielding a piecewise constant function [23].

For nearest neighbour algorithm the level of complexity is low leading to a fast computation time. But the scaled image quality is low and high aliasing effect is observed.

float tx = width_source/widthdst;

float ty = heightso urce/ height_dst:

for(i=0: i for(j=O; j^widthdst; j++)

{ x = ceil(j*tx);

у = ceil(i*ty);

U(ij) = P(y.x);

}

Figure 2. Nearest neighbour image scaling algorithm

B.    Bilinear Image Scaling

Another simple interpolation method is linear interpolation, a slight improvement over the nearest neighbour interpolation algorithm. In linear interpolation, the interpolated value is computed based on the weighted average of two data points. The weights are inversely proportional to the distance of the end points from the interpolated data point.

Bilinear interpolation algorithm [7] performs linear interpolation in one direction followed by linear interpolation of the interpolated values in the other direction. The algorithm uses 4 diagonal pixels surrounding the corresponding source image pixel for interpolation (Fig. 3). It computes a weighted average depending on the nearness and brightness of the 4 diagonal pixels and assigns that value to the pixel in the output image.

float tx = (width _source)/width_dst: float ty = (heightsowee)/ height_dst; float x_dijj, y_d№ for(i=0; i /or(j=0: j<.width_dst: j++)

x = (int)(tx *j); у = (int)(ty * i);

x_dtff- ((tx *j) -x);

У_<ЩГ- ((ty *«) -y );

U(iJ) = P(y.x) *(l-x_difl)*(l -y_dV)) + P(y,x+П *(j -y_di® *(x_dijjf) -P(y*l.x)*(y_dtg)*(l-x_difl) + P(y-vi,x*l) *(y_diff)*(x_dyi);

}

Figure 3. Bilinear image scaling algorithm

Bilinear offers considerable improvement in image quality with a slightly increased complexity. The aliasing effect is reduced though blurring is observed.

C.    Bicubic Image Scaling

Bicubic interpolation algorithm [8]-[9] performs cubic interpolation in one direction followed by cubic interpolation of the interpolated values in the other direction (Fig. 4).

float tx = (width_source)/width_dst;

float tv = (heightsource)/ height dst;

for(i=0; i for(i=0: j

у =(int)(ty*i);

dx=(float)(tx *j-x);

dy=(float)(ty 4 у);

jbr(jj=O;ji<=3;jj—t

{ dO = P(y-1 —jj,x-l) - P(y-1 ~jj,x);

d2 = P(y-l-jj,x-I) - Pfyl-jj.x);

d3 = Р(у-1-дд-2) - Pfy-l+jjy);

aO = Р(у-1+вд);

al = (-1.0/3*d0 - d2 -1.0/6*d3);

a2 = (1.0(2*d0 + L0'2*d2);

a3 = ( L0/6*d0 - 1.0!2*d2 - 1.0/6*d3);

CBj] =(a0 - al *dx - a2 *dx *dx + a3 *dx *dx *dx);

dO = (C[0]-C[l]);

d2 = (C[2]-C[l]);

d3 = (C[3] C[1J);

aO = C[l];

al = (-1.0/3*d0 + d2-1.0/6*d3);

a2 = (1.0/2*d0 - 1.0/2*d2);

a3 = (1.0/6*d0 - 1.0/2*d2 - 1.0/6*d3);

Cc = (aO + al *dy + a2*dy*dy + a3 *dy *dy *dy);

^(Cc>255) Cc=255;

if(Cc<0) Cc=O;

U(ij) = Cc

;

• Figure 4.    Bicubic image scaling algorithm

The bicubic interpolation approximates a sinc interpolation by using cubic polynomial waveforms instead of linear waveforms when computing an output pixel value. The algorithm uses 16 nearest pixels surrounding the closest corresponding pixel in the source image for interpolation.

Bicubic offers high scaled image quality at the cost of considerably high complexity. Edge halo effect is observed though aliasing and blurring are reduced.

D. Lanczos Image Scaling

The Lanczos interpolation algorithm [10] uses a windowed form of sinc filter (an ideal low-pass filter) to perform interpolation on a 2-D grid. Sinc function of a variable can be mathematically obtained by dividing the sine function of the variable by itself [9]. Sinc function theoretically never goes to zero. Hence, a practical filter can be implemented by multiplying the sinc function with a window operator such as Hamming [24]-[25] and Hann [26] to obtain a filter with a finite size.

The Lanczos filter can be obtained by multiplying the sinc function with the Lanczos window which is truncated to zero outside of the main lobe [27]. The size of the Lanczos window is defined by the order of the convolution kernel.

float tx = (width_source)/width_dst;

float ty = (height_source)/ height_dst;

fbr^=O; i

for(j=0; j

x =(int)(tx*j); у =(int)(ty*i):

dx = tx ^ - x; dy = ty*i - v;

aO = sin(pi*(dx+2)) *sin(pi*(dx-2)/3)/(pi*pi*(dx+2) *(dx-2)/3);

al = sinfpi *(dx+I))*sin(pi *(dx+l)/3)/(pi*piJf(dx+l) *(dx+l)/3);

a2 = sinfpi *(dx))*sin(pi *(dx)/3)!(pi*pi *(dx)*(dx)/3);

a3 = sin(pi*(dx-l))*sin(pi*(dx -l)/3)/(pi*pi*(dx-l)*(dx-I)/3);

a4 = sin(pi*(dx-2))*sin(pi *(dx-2)/3)/(pi*pi*(dx-2) *(dx-2)/3);

aS = sinfpi *(dx-3))*sin(pi *(dx-3)/3)/fpi*pi*(dx-3) *fdx-3)/3);

bO = sinfpi *(dy+2)) *sinfpi*fdy-2)/3)/fpi*pi*fdy+2) *(dy-2)/3);

bl = sinfpi*fdy+I))*sinfpi *(dy+l)/3)/(pi*pi*(dy+l) *(dy+l)/3);

b2 = sin(pi*(

b3 = sinfpi*fdy-l))*sin(pi*fdy-l)/3)/(pi*pi*(dy-l)*fdy-l)/3);

b4 = sinfpi*fch-2))*sin(pi *fdy-2)/3)/fpi*pi*(dy-2) *fdy-2)/3);

bS = sinfpi *fdy-3))*sinfpi *(dy-3)/3)/(pi*pi*(dy-3) *fdy-3)/3);

forfy=0;jj<=5;y—)

{ dO = Pfy-2+jj,x-2); di = P(y-2-ij,x-l);

d2 = P(y-2+jj,x); d3 = Pfy-2+jj,x~J);

d4 = Pfy-2+jj,x-2); d5 = P(y-2+jj,x-3);

C[jj]= aO*dO + al *dl + a2*d2 + a3*d3 + a4*d4 A-a5*d5;

;

Cc = a0*C[0j-al *C[l]-a2*C[2]-a3*C[3]+a4*C[4]+a5*C[5];

1ДСс>255) Cc=255; if(Cc<0) Cc=0;

Ufij) = Cc;

• Figure 5.    Lanczos image scaling algorithm

The number of neighbouring pixels considered varies as the order of the kernel. If the order is chosen to be 2, 16 pixels are considered while if the order is 3, 36 neighbouring pixels are utilized for interpolation. For sufficient image quality, the order is chosen to be 3 in the implementation (Fig. 5).

The Lanczos algorithm gives an output scaled image of the same quality as bicubic but at the cost of higher number of computations as 36 pixels is used for interpolating the value of each output pixel compared to 16 for bicubic. The Lanczos algorithm is comparatively more efficient for multiple scaling operations.

E. Modified Bicubic Image Scaling

According to the bicubic convolution kernel equation, massive calculations of four spots bicubic interpolation algorithm include large cubic and floating point multiplication operation. The bicubic interpolation algorithm discussed above can be slightly modified as shown below (Fig. 6). The co-efficients a0, a1, a2, a3, b0, b1, b2, and b3 are now a function of dx and dy (the difference between the interpolated co-ordinate and nearest integer source co-ordinate lower than it) instead of the interpolating pixels. This allows us to compute and store the values of the co-efficients for predetermined values of dx and dy. This avoids the large number of cubic and floating point operations involved in bicubic interpolation.

C[jj] = a0*d0+a1*d1 +a2*d2 +a3*d3

Cc = b0*C[0] +b1*C[1] +b2*C[2] +b3*C[3] Where, a0 = -dx /3 + dx * dx /2 - dx* dx* dx/6;

a1 = 1 - dx/2 - dx* dx/2 + dx* dx* dx/2;

a2 = dx + dx* dx/2 -dx* dx* dx/2;

a3 = - dx/6 + dx* dx* dx/6;

b0 = -dy /3 + dy *dy /2 - dy*dy*dy/6;

b1 = 1 - dy/2 - dy*dy/2 + dy*dy*dy/2;

b2 = dy + dy* dy/2 -dy*dy*dy/2;

b3 = - dy/6 + dy* dy* dy/6;

Although the algorithm result has been influenced slightly, computation load is largely simplified. It mainly overcomes the disadvantage that hardware implementation of the algorithm is difficult due to many floating point computations.

The search table modification to the bicubic interpolation algorithm is discussed in [28]. The distance, which the image regards as the unit length l, between two neighbouring pixels in the source image is divided equally into 16 sub-intervals. They are [0,1/16), [1/16,2/16), [2/16,3/16), [3/16,4/16), [4/16,5/16), [5/16,6/16), [6/16,7/16), [7/16,8/16), [8/16,9/16), [9/16,10/16),       [10/16,11/16),       [11/16,12/16),

[12/16,13/16),   [13/16,14/16),   [14/16,15/16) and

[15/16,1). The co-efficients for all 16 values of dx and dy can be computed beforehand and stored in memory. This reduces the computationally intensive process of determining the co-efficients in real-time. The value of dx and dy is compared to lie within one of the 16 subintervals and the values of coefficients a0, a1, a2, a2, b1, b2, b3, and b4 are chosen accordingly from precomputed values.

float tx = (width_source)/width_dst;

float ty = (height source)/ height_dst;

fbr(i=O; i

for(j=O; j

{

.x =(int)(tx*j);

у =(int)(ty*i);

dx=(float)(tx ^j-x);

dy=(float) (ty *i-y);

{ dO = P(y-1 +jj.x-l);

dl = Р(у-1+Цд);

d2 = P(y-1 +и„х+1);

d3 = P(y-l+jj,x+2);

C[jj]= aO*dO + al*dl + a2*d2 - a3*d3;

}

Cc = ( bO*C[O] + bl *C[1) + b2*C[2] - b3*C[3]);

i/(Cc>255) Cc=255;

iJ(Cc

U(i,j) = Cc;

• Figure 6.    Modified bicubic image scaling algorithm

• IV.    result analysis

All five algorithms are implemented in C/C++ language. OpenCV libraries are used for image read and write/display only. Dev-C++ (4.9.9.2) software installed on a standard Window XP machine is used for compilation and execution of C/C++ programs. Comparison of computational complexity of all five image scaling algorithms is shown in Table 1. Input test image of size 627x462 and corresponding scaled output images of size 150x150 produced by five implementations are shown in Fig. 7. Fig. 8 shows the input test image of size 609x594 and corresponding scaled output images of size 150x150 produced by five implementations.

Non-adaptive algorithms always face a trade-off between the three image scaling artifacts – edge halo, blurring and aliasing. Nearest neighbour interpolation produces a high aliasing effect resulting in jagged edges. Bilinear interpolation reduces the aliasing effect but causes a moderate blurring of the edges. Bicubic interpolation produces a moderate aliasing, blurring and an edge halo effect. Lanczos interpolation delivers an image quality very similar to that of bicubic. Modified bicubic produces an output of slightly lesser quality as compared to bicubic as the co-efficients are approximated to reduce computational complexity.

Computationally, nearest neighbour interpolation is the least intensive as it considers only one pixel for interpolation. Bilinear uses 4 diagonal pixels for interpolation and therefore, requires more computation than the nearest neighbour method. Bicubic and Lanczos interpolation are computationally very intensive as they require 16 and 36 pixels respectively for interpolating an output pixel value. Lanczos interpolation also utilizes the sine function repeatedly which itself requires a large number of addition and multiplication operations according to Taylor series approximation. Modified bicubic interpolation reduces the number of computations significantly as the co-efficients are computed using search table.

Table 1 : Computational Complexity Comparison

Algorithm	Addition/ Subtractions	Multiplications/Divisions	Sin
Nearest Neighbour	0	2	0
Bilinear	9	12	0
Bicubic	57	69	0
Lanczos	47	118	24
Modified Bicubic	17	24	0

Input Image

Figure 7. Input test image and corresponding output image for each algorithm

Nearest Neighbour           Bilinear                Bicubic                Lanczos           Modified Bicubic

Figure 8. Input test image and corresponding output image for each algorithm

• V.    Conclusion

Image scaling has become a fundamental processing task and plays an important role in video surveillance applications. Although there are a myriad of interpolation algorithms are available in literature, not all of them are suitable for implementing real-time image scaling. In this paper, we discussed the main non-adaptive image interpolation algorithms suitable for realtime applications. A comparative analysis of five image interpolation algorithms is presented based on the results of their software implementation. Of the five image interpolation algorithms evaluated, the modified bicubic algorithm offers the best trade-off between image quality and computational complexity for real-time image scaling in surveillance applications.

Acknowledgment

The authors express their deep sense of gratitude to Dr. Chandra Shekhar, Director CSIR-CEERI for encouraging research and development activities. Authors would like to thanks Dr. AS Mandal and Raj Singh, Group Leader, IC Design Group, CSIR-CEERI, for their constructive suggestions throughout the year.