Tag Archives: nearest neighbor interpolation

Image Processing – Nearest Neighbour Interpolation

In the previous blog, we discussed image interpolation, its types and why we need interpolation. In this blog, we will discuss the Nearest Neighbour, a non-adaptive interpolation method in detail.

Algorithm: We assign the unknown pixel to the nearest known pixel.

Let’s see how this works. Suppose, we have a 2×2 image and let’s say we want to upscale this by a factor of 2 as shown below.

Let’s pick up the first pixel (denoted by ‘P1’) in the unknown image. To assign it a value, we must find its nearest pixel in the input 2×2 image. Let’s first see some facts and assumptions used in this.

Assumption: a pixel is always represented by its center value. Each pixel in our input 2×2 image is of unit length and width.

Indexing in OpenCV starts from 0 while in matlab it starts from 1. But for the sake of simplicity, we will start indexing from 0.5 which means that our first pixel is at 0.5 next at 1.5 and so on as shown below.

So for the above example, the location of each pixel in input image is {’10’:(0.5,0.5), ’20’:(1.5,0.5), ’30’:(0.5,1.5), ’40’:(1.5,1.5)}.

After finding the location of each pixel in the input image, follow these 2 steps

  1. First, find the position of each pixel (of the unknown image) in the input image. This is done by projecting the 4×4 image on the 2×2 image. So, we can easily find out the coordinates of each unknown pixel e.g location of ‘P1’ in the input image is (0.25,0.25), for ‘P2’ (0.75,0.25) and so on.
  2. Now, compare the above-calculated coordinates of each unknown pixel with the input image pixels to find out the nearest pixel e.g. ‘P1′(0.25,0.25) is nearest to 10 (0.5,0.5) so we assign ‘P1’ value of 10. Similarly, for other pixels, we can find their nearest pixel.

The final result we get is shown in figure below:

This is the fastest interpolation method as it involves little calculation. This results in a pixelated or blocky image. This has the effect of simply making each pixel bigger

Application: To resize bar-codes.

Shortcut: Simply duplicate the rows and columns to get the interpolated or zoomed image e.g. for 2x, we duplicate each row and column 2 times.

In the next blog, we will discuss Bi-linear interpolation method. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Image Interpolation using OpenCV-Python

In the previous blogs, we discussed the algorithm behind the

  1. nearest neighbor 
  2. bilinear and
  3. bicubic interpolation methods using a 2×2 image.

Now, let’s do the same using OpenCV on a real image. First, let’s take an image, either you can load one or can make own image. Loading an image from the device looks like this

This is a 20×22 apple image that looks like this.

Now, let’s zoom it 10 times using each interpolation method. The OpenCV command for doing this is

where fx and fy are scale factors along x and y, dsize refers to the output image size and the interpolation flag refers to which method we are going to use. Either you specify (fx, fy) or dsize, OpenCV calculates the other automatically. Let’s see how to use this function

Nearest Neighbor Interpolation

In this we use cv2.INTER_NEAREST as the interpolation flag in the cv2.resize() function as shown below

Output: 

Clearly, this produces a pixelated or blocky image. Also, it doesn’t introduce any new data.

Bilinear Interpolation

In this we use cv2.INTER_LINEAR flag as shown below

Output: 

This produces a smooth image than the nearest neighbor but the results for sharp transitions like edges are not ideal because the results are a weighted average of 2 surrounding pixels.

Bicubic Interpolation

In this we use cv2.INTER_CUBIC flag as shown below

Output: 

Clearly, this produces a sharper image than the above 2 methods. See the white patch on the left side of the apple. This method balances processing time and output quality fairly well.

Next time, when you are resizing an image using any software, wisely use the interpolation method as this can affect your result to a great extent. Hope you enjoy reading.

If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Image Demosaicing or Interpolation methods

In the previous blog, we discussed the Bayer filter and how we can form a color image from a Bayer image. But we didn’t discuss much about interpolation or demosaicing algorithms so in this blog let’s discuss these algorithms in detail.

According to Wikipedia, Interpolation is a method of constructing new data points within the range of a discrete set of known data points. Image interpolation refers to the “guess” of intensity values at missing locations.

The big question is why we need interpolation if we are able to capture intensity values at all the pixels using Image sensor?

  1.  Bayer filter, where we need to find missing color information at each pixel.
  2.  Projecting low-resolution image to a high-resolution screen or vice versa. For example, we prefer watching videos in the full-screen mode.
  3.  Image Inpainting, Image Warping etc.
  4.  Geometric Transformations.

There are plenty of Interpolation methods available but we will discuss only the frequently used. Interpolation algorithms can be classified as

Non-adaptive perform interpolation in a fixed pattern for every pixel, while adaptive algorithms detect local spatial features, like edges, of the pixel neighborhood and make effective choices depending on the algorithm.

Let’s discuss the maths behind each interpolation method in the subsequent blogs.

In the next blog, we will see how the nearest neighbor method works. Hope you enjoy reading.

If you have any doubt/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.