home | news | contact | about
Nearest Neighbor Image Scaling
6 October 2007, 02:42 AM
Scaling of image is one frequently used task in any decent image processing software. Even if you say you don't, the software does. Ever zoomed your image for a closer look? Or used that convenient thumbnail preview? It all happens there, regardless of what you may be thinking.

Nearest neighbor is the simplest and fastest implementation of image scaling technique. It is very useful when speed is the main concern, for example when zooming image for editing or for a thumbnail preview. More complex variation of scaling algorithms are bilinear, bicubic, spline, sinc, and many others. Unlike simple nearest neighbor, this other variation uses interpolation of neighboring pixels, resulting in smoother image. Commercial implementation may have something called adaptive algorithm, where it has the capability of applying different level of interpolation on different area on an image - but this is beyond the scope of this article.

The principle in image scaling is to have a reference image and using this image as the base to construct a new scaled image. The constructed image will be smaller, larger, or equal in size depending on the scaling ratio. When enlarging an image, we are actually introducing empty spaces in the original base picture. From the image below, an image with dimension (w1 = 4, h1 = 4) is to be enlarged to (w2 = 8, h2 = 8). The black pixels represent empty spaces where interpolation is needed, and the complete picture is the result of nearest neighbor interpolation.

nneighbor01.png

Scaling algorithm is to find appropiate spot to put the empty spaces inside the original image, and to fill all those spaces with livelier colors. For the nearest neighbor technique, the empty spaces will be replaced with the nearest neighboring pixel, hence the name. This results in a sharp but jaggy image, and if the enlarge scale is two, it would seems each pixel has doubled in size. Shrinking, in the other hand involves reduction of pixels and it means lost of irrecoverable information. In this case scaling algorithm is to find the right pixels to throw away.

Good scaling algorithm is one that can do up and down scalling without introducing too many conditions (the ifs) in its implementation code, even better if there is none. Nearest neighbor is a no if, up down scaling algorithm. What information it needs are both the horizontal and vertical ratios between the original image and the (to be) scaled image. Consider again the diagram above, w1 and h1 are the width and height of an image, whereas w2 and h2 are the width and height when enlarged (or shrinked). Calculating the ratio for both horizontal and vertical plane is given by,

nneighbor-equ.gif

Of course the not equal to zero is a condition, and will eventually be translated as ifs in coding implementation. However, to be fair no algorithm is needed if one intend to shrink image to zero size, who the hell wants to do that?

Once ratio has been calculated prepare a buffer, or array, or whatever that can store information for the to be constructed image. The size should be enough to store w2*h2 of pixels. Check on the java code snippet below to find the implementation's simplicity for nearest neighbor algorithm.

public int[] resizePixels(int[] pixels,int w1,int h1,int w2,int h2) {
    int[] temp = new int[w2*h2] ;
    double x_ratio = w1/(double)w2 ;
    double y_ratio = h1/(double)h2 ;
    double px, py ; 
    for (int i=0;i<h2;i++) {
        for (int j=0;j<w2;j++) {
            px = Math.floor(j*x_ratio) ;
            py = Math.floor(i*y_ratio) ;
            temp[(i*w2)+j] = pixels[(int)((py*w1)+px)] ;
        }
    }
    return temp ;
}


While this will work just fine, most of us are anxious with the slightest presence of floating point variables. Above function can be improved to deal with integer only variables without noticeable lost of precision - pixel wise :D

public int[] resizePixels(int[] pixels,int w1,int h1,int w2,int h2) {
    int[] temp = new int[w2*h2] ;
    // EDIT: added +1 to account for an early rounding problem
    int x_ratio = (int)((w1<<16)/w2) +1;
    int y_ratio = (int)((h1<<16)/h2) +1;
    //int x_ratio = (int)((w1<<16)/w2) ;
    //int y_ratio = (int)((h1<<16)/h2) ;
    int x2, y2 ;
    for (int i=0;i<h2;i++) {
        for (int j=0;j<w2;j++) {
            x2 = ((j*x_ratio)>>16) ;
            y2 = ((i*y_ratio)>>16) ;
            temp[(i*w2)+j] = pixels[(y2*w1)+x2] ;
        }                
    }                
    return temp ;
}


What happen in this modification is we replace all floating point variables with integers and multiply the original size with 65536 before calculating ratios. The << operator is the bitwise shift left operator, and x<<16 is equivalent to x * 65536. The >>16 is equivalent to divide by 65536. It is also possible to replace most of the multiplication with just addition, can you see it? Once you get the above working, try yourself with addition only optimization. I'm sure it will be worth the effort.

edit note: the original has problems up-sizing to 300%, 500%, 700%, and so on if you look real closely into the resulting image (thanks to Madhu for the observation). Taking an example of 300% sizing factor, the problem lies in calculating something akin to (1/3)*3. With Microsoft's calculator it gives back the answer 1, but trying to code that with integer only operation, 0 is the result. We can get around this by cheating with the math a bit by adding a small error factor for the ratio.

This implementation is sufficient for simple up and down scaling, except for condition zero size, but that should be an easy fix for someone like you. I have prepared some images scaled by the algorithm describe above. Don't mind the black stripes, they are just to show where the empty spaces are located when enlarging the original image.

Original image:

grape.png

Scale 200%

grape-200.png

Scale 200% with empty spaces shown (black pixels)

grape-200-incomplete.png

Scale 130%

grape-130.png

Scale 130% with empty spaces shown (black pixels)

grape-130-incomplete.png

Scale 50%

grape-50.png
Last edited on 19 July 2009

Comments

~Jeremy McLeod, 26 July 2009, 07:13 PM
Does this algorithm take color depth into account? Is it designed for 32bpp only, or will it work independently of the bpp of the input/output surfaces?
~John, 26 July 2009, 08:42 PM
Hi Jeremy,

It will work independently of color depth. Nearest neighbor works by *copying* neighboring pixels not altering the color in any way so the bpp doesn't matter. If you think about it 32bit integer can also be used to represent grayscale information don't you think so?
~Mark, 29 October 2009, 07:54 PM
Thanks for your efforts! That is really helpful.
~karan, 12 February 2010, 09:59 PM
Thanks it really helps !!
~b359.com, 14 March 2010, 03:55 PM
You could achieve 30-40% performance gain by modifying your code in similar way:

for (int i=0;i<h2;i++)
{
int* t = temp + i*w2;
y2 = ((i*y_ratio)>>16);
int* p = pixels + y2*w1;
int rat = 0;
for (int j=0;j<w2;j++)
{
x2 = (rat>>16);
*t++ = p[x2];
rat += x_ratio;
}
}
~Alaa, 9 June 2010, 05:45 AM
Thanks alot
I have a general question:in choosing algorithms,
Should we try to decrease number of conditions or better to decrease number of operations?
~John, 12 June 2010, 10:29 PM
I guess choose algorithm that suits your needs best. However if you're designing an algorithm for a specific task, assuming it is done and working fine, profile and pinpoint the most expensive operation (usually inside a loop) and try changing it to a cheaper operation. For example some sorting method requires a lot of element swapping and each swap can be expensive when dealing with on disk/large individual element. To remedy this a clever method called 'array indices' is used so that only the index(or pointers) of elements are swapped - making it cheaper. As for the conditional checks, most of the time we can't remove it.
~MOHANAMUTHA, 1 July 2010, 08:23 AM
thank you
~Randall, 25 September 2010, 06:37 PM
I appreciate your code and your explanations. I had written my own but it was very slow. Yours did the trick a lot faster and with a lot fewer instructions. Thanks!
~Thomas Ingham, 8 November 2011, 01:31 AM
Thanks for the great example; ported to Javascript no problems.
~ketut, 10 November 2011, 02:20 AM
thank alot
I not familiar using java,
what will be this line becomes:
temp[(i*w2)+j] = pixels[(y2*w1)+x2] ;

into array temp(x,y)?
thank you
~mazei, 8 November 2012, 03:05 PM
Thanks!!!
~KP, 12 August 2013, 09:46 AM
i have tested resizePixels (second one)
i have used to upscale my QR-code, it working fine...but my QR codes are just 1 BPP Image (generally 25x25 to 40x40 pixel) and Storing 1 bit into 4 Byte is just waste of resource. So i have two Question.
1: if i convert it to Bit level will it cost a lot of CPU??
2:is there any way this algo can be optimize for 1BPP images ??
~Xiaoran Tong, 21 September 2013, 10:02 PM
Thanks, I use this algorithm to scale chromosome 2D maps.
~Baraka Maiseli, 2 November 2013, 05:41 AM
I am not familiar in Java, but I developed a MATLAB function for the nearest neighbor interpolation as follows:
function [ scaledImg ] = imgResize( inputImg, rows, cols, factor )
%UNTITLED2 Summary of this function goes here
% Detailed explanation goes here
scaledImg=zeros(rows*factor,cols*factor);
tic
for i=1:(rows*factor)
for j=1:(cols*factor)
x=floor(i/factor);
y=floor(j/factor);
if x==0
x=1;
end
if y==0
y=1;
end
scaledImg(i,j) = inputImg(x,y);
end
end
toc
figure(1);imshow(inputImg, []);
figure(2);imshow(scaledImg, []);
end

The function works fine. But I fail to test the performance of the function in comparison to other functions posted. Just by looking (analysis), may someone kindly analyze my code. In MATLAB, the function takes about 0.016001 seconds to interpolate an image of 240x240 size by a factor of 2, and also the function takes about 1.133815 seconds to interpolate the same input image by a factor of 13.
~Titon, 13 February 2014, 01:24 PM
For you C# users out there ,here is a version using Bitmap class

ublic static Bitmap NearestNeighborScale(Bitmap bmp, int newXSize, int newYSize)
{
if (newXSize == 0 || newYSize==0)
throw new ImageException(\"New dimensions cannot be zero for scaling!\");

Bitmap newBMP = new Bitmap(newXSize, newYSize);
int w1 = bmp.Width;
int h1 = bmp.Height;

// EDIT: added +1 to account for an early rounding problem
int x_ratio = (int)((w1 << 16) / newXSize) + 1;
int y_ratio = (int)((h1 << 16) / newYSize) + 1;

int x2, y2;
for (int i = 0; i < newYSize; i++)
{
for (int j = 0; j < newXSize; j++)
{
//Get the source position of the pixel
x2 = ((j * x_ratio) >> 16);
y2 = ((i * y_ratio) >> 16);
newBMP.SetPixel(j, i, bmp.GetPixel(x2, y2));
}
}
return newBMP;
}
Post a comment~
Name*
What is the first odd prime number?*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.