Bilinear interpolation algorithm for Python OpenCV image, the most detailed algorithm description in the whole network

2022-01-30 05:10:15

This article has participated in  「 Digging force Star Program 」 , Win a creative gift bag , Challenge creation incentive fund .

Python OpenCV 365 Day study plan , Go into the field of image with the eraser . This blog is the third in this series 42 piece .

Basic knowledge

This blog realizes the compilation of bilinear interpolation algorithm , By the way, revise The last blog nearest neighbor interpolation algorithm is finally implemented and OpenCV The built-in parameters provided are inconsistent . There's another problem , It's the speed of execution , This problem is solved after learning bilinear interpolation algorithm .

Bilinear interpolation algorithm of image

Bilinear interpolation algorithm is a better image scaling algorithm , It makes use of the four real pixel values around the virtual point in the source image , Determine a pixel value in the target image according to the weight .

First extract some principled descriptions ： For a target pixel , The virtual coordinates of the source image can be obtained by reverse transformation , The probability is the floating-point coordinates , The format is (i+u,j+v), among ij Is the integer part ,uv It's a fraction , Value [0,1), At this time, in the source image (i+u,j+v) It can be determined by the coordinates of the four surrounding pixels (i,j)(i+1,j)(i,j+1)(i+1,j+1) Obtained by calculation , That is, there is a formula ：

f(i+u,j+v) = (1-u)(1-v)f(i,j) + (1-u)vf(i,j+1) + u(1-v)f(i+1,j) + uvf(i+1,j+1)

The transformation of this step has been omitted a lot , The eraser also consulted a lot of information , Next, I'll add . First draw a picture to help understand ~

First, in the X Two linear interpolation in the direction , And then in Y In the direction of the interpolation calculation .

Before calculating , It's time to add knowledge , It's called linear interpolation , Known data $(x_0,y_0)$ and $(x_1,y_1)$, To calculate $[x_0,x_1]$ Somewhere in the interval x On a straight line y value , The formula is as follows ：

$\cfrac{y-y_0}{x-x_0}=\cfrac{y_1-y_0}{x_1-x_0}$

The formula is deformed to obtain ：

$y=\cfrac{x_1-x}{x_1-x_0}y_0+\cfrac{x-x_0}{x_1-x_0}y_1$

After the transformation, it will probably wait for $x_0$ and $x_1$ Distance as a weight , be used for $y_0$ and $y_1$ A weighted , Bilinear interpolation is linear interpolation in two directions .

Continue to look at the picture above , At point 1 With the point 2 Look for a point in the interval , According to the formula ：

$f( Interpolation point 1)\approx\cfrac{x_2-x}{x_2-x_1}f( spot 1)+\cfrac{x-x_1}{x_2-x_1}f( spot 2)$ The interpolation point 1 = $(x,y_1)$

The same algorithm obtains interpolation points 2：

$f( Interpolation point 2)\approx\cfrac{x_2-x}{x_2-x_1}f( spot 3)+\cfrac{x-x_1}{x_2-x_1}f( spot 4)$ The interpolation point 2 = $(x,y_2)$

The next in Y Linear interpolation calculation of direction ：

$f(P)\approx\cfrac{y_2-y}{y_2-y_1}f( Interpolation point 1)+\cfrac{y-y_1}{y_2-y_1}f( Interpolation point 2)$

Expand the above formula , You can get the final result , This is not very difficult , Just be careful when writing and reading ： $f(x,y)\approx\cfrac{f( spot 1)(x_2-x)(y_2-y)}{(x_2-x_1)(y_2-y_1)}+\cfrac{f( spot 2)(x-x_1)(y_2-y)}{(x_2-x_1)(y_2-y_1)}+\cfrac{f( spot 3)(x_2-x)(y-y_1)}{(x_2-x_1)(y_2-y_1)}+\cfrac{f( spot 4)(x-x_1)(y-y_1)}{(x_2-x_1)(y_2-y_1)}$

This formula can be further simplified , Because the interpolation between two adjacent points is 1, So simplify it as follows ： $f(x,y)\approx f( spot 1)(x_2-x)(y_2-y)+f( spot 2)(x-x_1)(y_2-y)+f( spot 3)(x_2-x)(y-y_1)+f( spot 4)(x-x_1)(y-y_1)$ Bring the coordinates of all points into $f(x,y)\approx f(x_1,y_1)(x_2-x)(y_2-y)+f(x_2,y_1)(x-x_1)(y_2-y)+f(x_1,y_2)(x_2-x)(y-y_1)+f(x_2,y_2)(x-x_1)(y-y_1)$ take (x,y) Replace with the initial wording (i+u,j+v) , The other coordinates are spot 1~ spot 4 Respectively ：(i,j)(i+1,j)(i,j+1)(i+1,j+1) , Bring in the above formula , The change results are shown in ： $f(i+u,j+v)\approx f(i,j)(i+1-(i+u))(j+1-(j+v))+f(i+1,j)(i+u-i)(j+1-(j+v))+f(i,j+1)(i+1-(i+u))(j+v-j)+f(i+1,j+1)(i+u-i)(j+v-j)$

Don't faint , It is estimated that this is the clearest conversion mode in the whole network ： $f(i+u,j+v)\approx f(i,j)(1-u)(1-v)+f(i+1,j)u(1-v)+f(i,j+1)(1-u)v+f(i+1,j+1)uv$ So far, it echoes the formula at the beginning of this blog .

So the point deduced from the target image , It can be calculated by the coordinates of four points , The in front of each coordinate is called weight , Suppose there is such a pixel whose coordinates are (1,1), The coordinates obtained in the source diagram are (0.75,0.75), Because floating point coordinates cannot exist in the image , So get the four surrounding coordinates, which are （0,0）（0,1）（1,0）（1,1）, because (0.75,0.75) distance (1,1) lately , therefore (1,1) The point has the greatest effect on the color of the pixel , Corresponding (1,1) The point corresponding to the point is f(i+1,i+1) , The coefficient weight in front of this variable is 0.75*0.75 , The result is the biggest , This explanation is explained by real data .

After getting the calculation method , Bilinear interpolation algorithm can be realized through code .

First through the built-in scaling function , Test the run time ：

if __name__ == '__main__':
start = time.time()
dst = cv2.resize(src, (600, 600))
print(' Built in function run time ：%f' % (time.time() - start))

cv2.imshow('src', src)
cv2.imshow('dst', dst)
cv2.waitKey()
Copy code 

The time obtained is  Built in function run time ：0.002000 , Very fast .

The next step is to verify the self writing function , I wrote the description of the code in the comments , You can study , Pay attention to the application of the formula

import cv2
import numpy as np
import time

def resize_demo(src, new_size):
#  The width and height of the target image
dst_h, dst_w = new_size
#  The width and height of the source image
src_h, src_w = src.shape[:2]

#  If the image size is consistent , Just copy and return directly
if src_h == dst_h and src_w == dst_w:
return src.copy()

#  Calculate scale
scale_x = float(src_w) / dst_w
scale_y = float(src_h) / dst_h

#  Traverse the target image
dst = np.zeros((dst_h, dst_w, 3), dtype=np.uint8)
# return dst
#  Cycle the channel
# for n in range(3):
#  Yes  height  loop
for dst_y in range(dst_h):
#  Yes  width  loop
for dst_x in range(dst_w):
#  The coordinates of the target on the source
src_x = dst_x * scale_x
src_y = dst_y * scale_y
#  Calculate on the source diagram  4  The location of two nearest neighbors
# i,j
i = int(np.floor(src_x))
j = int(np.floor(src_y))

u = src_x-i
v = src_y-j
if j == src_h-1:
j = src_h-2
if i == src_w-1:
i = src_h-2
# f(i+u,j+v) = (1-u)(1-v)f(i,j) + (1-u)vf(i,j+1) + u(1-v)f(i+1,j) + uvf(i+1,j+1)
dst[dst_y, dst_x] = (1-u)*(1-v)*src[j, i]+u*(1-v) * \
src[j+1, i] + (1-u)*v*src[j, i+1]+u*v*src[j+1, i+1]
# dst[dst_y, dst_x] = 0.25*src[j, i]+0.25 * \
# src[j+1, i] + 0.25*src[j, i+1]+0.25*src[j+1, i+1]
# dst[dst_y,dst_x,n] = 255

return dst

if __name__ == '__main__':
start = time.time()
dst = resize_demo(src, (500, 600))
print(' Self writing function running time ：%f' % (time.time() - start))

cv2.imshow('src', src)
cv2.imshow('dst', dst)
cv2.waitKey()
Copy code 

Code running consumes 2s many , It really takes time .

Eraser bars

I hope today's 1 You get something in an hour , I'll see you on our next blog ~

https://en.pythonmana.com/2022/01/202201300510129146.html