0

I've tried reading the bilinear interpolation on the Wikipedia page https://en.wikipedia.org/wiki/Bilinear_interpolation and I have implemented one of the algorithms and I wanted to know if I'm doing it right or not.

This is the algorithm I implemented from the page: Bilinear interpolation from unit squre

This what I tried to implement in code:

for(int i = 0; i < w; i++) {
    for( int j = 0; j < h; j++) {
        new_img(i,j,0) = old_img(i,j,0)*(1-i)(1-j) + old_img(i+1,j,0)*i*(1-j) + old_img(i,j+1)*(1-i)*j + old_img(i+1,j+1,0)*i*j;
    }
}

Is that how to implement it?

Josh
  • 63
  • 1
  • 10
  • Bilinear interpolation deals with putting values "between" known pixels. For example if you want to rescale or warp an image and put values in missing places. In the equation you put the indexes x, y are not integers but floats, and the goal is to find a value of a location between 0 and 1 in both axis x and y. Try to explain exactly what you want to do. – TzviLederer May 25 '21 at 05:09
  • I want to use bilinear interpolation to resize an image – Josh May 25 '21 at 10:27
  • It is implemented in opencv in the function resize (there are a flag INTER_LINEAR that implements it). Do you want to implement it yourself? – TzviLederer May 25 '21 at 10:36
  • Yes, I would like to implement it myself. I'm self teaching myself computer vision and I'm following a course from University of Washington and this is a problem on the homework to complete: https://github.com/holynski/cse576_sp20_hw2 – Josh May 25 '21 at 10:44
  • This answer helped me solve understand and solve the problem: https://stackoverflow.com/a/26143655/10613210 – Josh May 27 '21 at 16:19

1 Answers1

0

The bilinear interpolation deals with upsampling an imgae. It try to estimate the value of an array (e.g. an image) between the known values. For example, if i have an image and I want to estimate its value in the location (10.5, 24.5), the value will be a weighted average of the values in the four neighbors: (10,24), (10,25), (11,24), (11,25) which are known. The formula is the equation you posted in your question.

This is the python code:

    scale_factor = 0.7

    shape = np.array(image.shape[:2])
    new_shape = np.ceil(shape * scale_factor).astype(int)

    grid = np.meshgrid(np.linspace(0, 1, new_shape[1]), np.linspace(0, 1, new_shape[0]))
    grid_mapping = [i * s for i, s in zip(grid, shape[::-1])]

    resized_image = np.zeros(tuple(new_shape))
    for x_new_im in range(new_shape[1]):
        for y_new_im in range(new_shape[0]):
            mapping = [grid_mapping[i][y_new_im, x_new_im] for i in range(2)]
            x_1, y_1 = np.floor(mapping).astype(int)
            try:
                resized_image[y_new_im, x_new_im] = do_interpolation(f=image[y_1: y_1 + 2, x_1: x_1 + 2], x=mapping[0] - x_1, y=mapping[1] - y_1)
            except ValueError:
                pass


def do_interpolation(f, x, y):
    return np.array([1 - x, x]).dot(f).dot([[1 - y], [y]])

Explanation:
new_shape = np.ceil(shape * scale_factor).astype(int) - calculate the new image shape after rescale.
grid = np.meshgrid(np.linspace(0, 1, new_shape[1]), np.linspace(0, 1, new_shape[0]))
grid_mapping = [i * s for i, s in zip(grid, shape[::-1])] - generate a x,y grid, when x goes from 0 to the width of the resized image and y goes from 0 to the hight of the new image. Now, we have the inverse mapping from the new image to the original one.
In the for loop we look at every pixel in the resized image and where is its source in the original image. The source will not be an integer but float (a fraction).
Now we take the four pixels in the original image that are around the mapped x and y. For example, if the mapped x,y is in (17.3, 25.7) we will take the four values of the original image in the pixels: (17, 25), (17, 26), (18, 25), (18, 26). Then we will apply the equation you bring.

note:
I add a try-except because I did not want to deal with boundaries, but you can edit the code to do it.

TzviLederer
  • 117
  • 1
  • 8
  • Would you be able to explain what each line does as python syntax gets confusing for me sometimes. Also what does 'do_interpolation' do? How does it do the interpolation? – Josh May 25 '21 at 14:10
  • I add explanation. Sorry, I forgot the function do_interpolation, I add it. – TzviLederer May 25 '21 at 21:34
  • what formula do you use to turn the source to a float? – Josh May 25 '21 at 21:52
  • It is a mapping from the dest to the source. The mapping dont has to be to an integer because the scale factor can be any number. So in most of the cases the mapping will be to a non integer index and this is why you need the interpolation. – TzviLederer May 26 '21 at 07:17
  • Can you help me understand the math behind bilinear interpolation? So let's say I'm at pixel location (3,5) in my new img array and I need to determine the pixel at this location, how would I go about performing bilinear interpolation at pixel location (3,5)? – Josh May 26 '21 at 11:40
  • I edited my answer, tell me if its not clear – TzviLederer May 26 '21 at 13:08