Better Image Scaling

Nearest Neighbor

We have previously learned that when scaling to a target size that is a multiple of the source size we need to simply skip pixels or reuse pixels when copying. However this limited technique will not work when the target and source sizes are not multiples. Consider as before the 4x4, 16 pixel image at the left below which would be represented in memory as the values in the given table to the right:

0 1 2 3 0 255,255,255 206,0,0 10,0,206 39,206,0 1 249,222,6 2,94,13 254,155,38 140,9,9 2 171,6,248 172,250,6 6,240,249 236,6,250 3 192,192,192 128,128,128 64,64,64 0,0,0

If we wished to scale it to a 10x10 image we would obviously need to reuse some of the pixels from the source more than once. The question is which ones since the target is not a multiple of the source. One answer to this question is the nearest neighbor algorithm.  

Linear Interpolation

The nearest neighbor algorithm is based upon linear interpolation. Consider the first row of the above image as a single line. Each point along the line can be treated as a percentage of distance of the line length, (divide each point by the length of the line, i.e. the width of the image, 4).

The first row of the 10x10 scaled image to be created can be considered in the same manner.

To determine which value from the first line to copy when forming the second line we use the nearest corresponding percentage value from the first line. In other words, if we are deciding upon the value for 1 from the 10x10 line, we first divide its value by the length (width) of the line to get 0.10, the percentage of its distance along the line. Next we multiply this percentage by the width of the first line: 0.10 * 4 = 0.4. If the lines were real numbers the value 0.4 would be the same interpolated distance along the first line as 1 is along the second line. If there was a pixel at this distance it would be the pixel color we would use for the coloring. Since pixel coordinates are integers we must instead use the nearest integer pixel coordinate to this interpolated real value pixel. We do this by simply rounding to the nearest integer. Thus 0.4 rounds to 0 and we reuse the 0 pixel from the first line for the second pixel color of the larger line.  We can accomplish this by using the Python built-in round() function. The result of this interpolation for the lines above follows.

Note that the last point (9) rounds to an interpolated value of 4 for which no pixel exists. The nearest pixel in this case is the previous pixel. Care must be taken to not access pixel values which do not exist. Similar interpolation is also used down the Y axis using the height as the divisor for the percentages.

 Thus to determine the nearest neighbor pixel coorddinates for the source for any x,y pixel of the target we use the following interpolation formulas:

sourceX = int( round ( targetX / targetWidth * sourceWidth ) )

sourceY =  int( round ( targetY / targetHeight * sourceHeight ) )

 The above operations must be real operations and the resulting source coordinates must be checked to be sure they do not exceed the width and height respectively.

 Go ahead and try to write a nearestNeighborScaling() function now. To view the completed function move your mouse over the following paragraph.

The image at the left below is the famous painting "Idylle Atomique" by Salvador Dali which is 720, 534. The image following it is the result of a scaling using the above code to 500x300.

Although nearest neighbor scaling does not achieve great results its advantage is speed due to the simplicity of the computations. It is used in some systems for producing thumbnails and icons from images where speed is of the essence.