In the two-dimensional data resize / mapping / coordinate conversion and other operations, often the original integer coordinates will be transformed into decimal coordinates, for non-integer coordinate values an intuitive and effective way of interpolation for bilinear interpolation.
Introduction to Interpolation
Bilinear interpolation, also known as bilinear interpolation. Mathematically, bilinear interpolation is a linear interpolation extension of an interpolating function with two variables, where the central idea is to perform a single linear interpolation in each of the two directions.
Bilinear interpolation as an interpolation algorithm in numerical analysis is widely used in signal processing, digital image and video processing.
Suppose we have a situation where we need to choose a point (a,b) to take an approximation in the middle (within the square) of the coordinates of four neighboring square integer points (A,B,C,D).
At this point we know the value of the four points VA,VB,VC,VD, given the decimal coordinates E(a,b),0 ≤ a,b ≤ 1, how to interpolate to solve the value of the E point it is to solve similar problems collectively referred to as the interpolation of the above figure Show the formula for the calculation of bilinear interpolation.
Nearest Interpolation
One of the easiest methods is the nearest neighbor method, which directly takes the value of the point that is closest to the current point as the interpolation result:
where roundroundround for rounding operations, the method is simple and very fast, but often not fine enough
Bicubic interpolation
Bicubic interpolation is to use 16(4*4) points in the original image to calculate 1 point in the new image, which is better, but the computational cost is too large.
Bilinear Interpolation
Using one point for interpolation is too rough, 16 points is too cumbersome, then use the values of 4 points around the EEE point to approximate the solution, which is a compromise that balances the computational cost and interpolation effect, and is also the default interpolation operation of the major transformation libraries.
bilinear interpolation
By looking at the above moving picture (you can move your hand around a bit) you can clearly see that bilinear interpolation is essentially the result of linearly weighting the values in the four corners in proportion to the area of the square.
Okay, that's the core of the math in one sentence.
So now that you understand the essence, the math equations are good to write:
python implementation
In the implementation, of course, the for loop method solves everything, but it's not very elegant, so let's try to use numpy to do the bilinear interpolation.
Assuming the original imageimageThe transformed matrix of fractional coordinates Xx_gridY matrixy_gridThen you can use the followingbilinear_by_meshgrid function fast bilinear interpolation with boundaries already taken care of.
def bilinear_by_meshgrid(image, x_grid, y_grid):
# Ia, Wd Ic, Wb
# (floor_x, floor_y) (ceil_x, floor_y)
#
# (x, y)
#
# Ib , Wc Id, Wa
# (floor_x, ceil_y) (ceil_x, ceil_y)
#
assert == x_grid.shape == y_grid.shape
assert == 2
H, W = [:2]
floor_x_grid = (x_grid).astype('int32')
floor_y_grid = (y_grid).astype('int32')
ceil_x_grid = floor_x_grid + 1
ceil_y_grid = floor_y_grid + 1
if (ceil_x_grid) > W -1 or (ceil_y_grid) > H -1 or (floor_x_grid) < 0 or (floor_y_grid) < 0:
print("Warning: index value out of original matrix, a crop operation will be applied.")
floor_x_grid = (floor_x_grid, 0, W-1).astype('int32')
ceil_x_grid = (ceil_x_grid, 0, W-1).astype('int32')
floor_y_grid = (floor_y_grid, 0, H-1).astype('int32')
ceil_y_grid = (ceil_y_grid, 0, H-1).astype('int32')
Ia = image[ floor_y_grid, floor_x_grid ]
Ib = image[ ceil_y_grid, floor_x_grid ]
Ic = image[ floor_y_grid, ceil_x_grid ]
Id = image[ ceil_y_grid, ceil_x_grid ]
wa = (ceil_x_grid - x_grid) * (ceil_y_grid - y_grid)
wb = (ceil_x_grid - x_grid) * (y_grid - floor_y_grid)
wc = (x_grid - floor_x_grid) * (ceil_y_grid - y_grid)
wd = (x_grid - floor_x_grid) * (y_grid - floor_y_grid)
assert (wa) >=0 and (wb) >=0 and (wc) >=0 and (wd) >=0
W = wa + wb + wc + wd
assert (W[:, -1]) + (W[-1, :]) == 0
wa[:-1, -1] = ceil_y_grid[:-1, -1] - y_grid[:-1, -1]
wb[:-1, -1] = y_grid[:-1, -1] - floor_y_grid[:-1, -1]
wb[-1, :-1] = ceil_x_grid[-1, :-1] - x_grid[-1, :-1]
wd[-1, :-1] = x_grid[-1, :-1] - floor_x_grid[-1, :-1]
wd[-1, -1] = 1
W = wa + wb + wc + wd
assert (W) == (W) == 1
res_image = wa*Ia + wb*Ib + wc*Ic + wd*Id
return res_imageThis function is integrated in my own python librarymtutils in which it can be passed:
pip install mtutils
Install it directly and you can refer to it directly afterward:
from mtutils import bilinear_by_meshgrid
Above is based on Python to realize two-dimensional image bilinear interpolation details, more information about Python bilinear interpolation please pay attention to my other related articles!