Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Python OpenCV 365 day learning plan, enter the graphics realm with eraser. This blog is the 42nd in a series.
Foundation of basic knowledge
This blog to achieve bilinear interpolation algorithm writing, incidentally modify the last blog nearest neighbor interpolation algorithm and OpenCV to provide built-in parameters inconsistent problem. There is also a problem of execution speed, which is solved after learning the bilinear interpolation algorithm.
Image bilinear interpolation algorithm
Bilinear interpolation algorithm is a good image scaling algorithm, which uses four real pixel values around the virtual point in the source image to determine a pixel value in the target image according to the weight.
Here are some basic descriptions: For a target pixel, the virtual coordinate of the source image can be obtained by reverse transformation, which is mostly floating point coordinate in the format of (I +u,j+v), where I and j are integer parts, u and v are decimal parts, and the value is [0,1). At this time, (I +u,j+ V) in the source image can be calculated from the surrounding four pixel coordinates (I,j), (I +1,j), (I,j+1), (I +1,j+1), that is, the existence 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)
This step of the transformation is omitted a lot, eraser also looked up a lot of information, for you to add. Let me draw a picture to help you understand
Two linear interpolations are performed in the X direction, followed by one in the Y direction.
And before we do that, we have linear interpolation, we have (x0,y0)(x_0,y_0)(x0,y0) and (x1,y1)(x_1,y_1)(x1,y1), To calculate the y value of a position x on the line in the interval [x0,x1][x_0,x_1][x0,x1], the formula is as follows:
The formula is deformed to obtain:
After the transformation, the distance between x0x_0x0 and x1x_1x1 is used as a weight for the weighting of y0y_0y0 and y1y_1y1. Bilinear interpolation is linear interpolation in two directions.
Continue to look at the figure above, find a point in the interval between point 1 and point 2, and obtain according to the formula:
F (interpolation point 1) material x2 – xx2 – x1f (point 1) + x – x1x2 – x1f (point 2) f (interpolation point 1) \ approx \ cfrac {x_2 – x} {x_2 – x_1} (1) + f \ cfrac {x – x_1} {x_2 – x_1} f (point 2) f (interpolation point 1) material x2 – x1x 2 – xf (point 1) + x2 – x1x – x1f (point 2) in which the interpolation point 1 = (x, y1) (y_1, x) (x, y1)
The same algorithm obtains interpolation point 2:
F (interpolation point 2) material x2 – xx2 – x1f (point 3) + x – x1x2 – x1f (point 4) f (2) of interpolation points \ approx \ cfrac {x_2 – x} {x_2 – x_1} f (point 3) + \ cfrac {x – x_1} {x_2 – x_1} f (point 4) f (interpolation point 2) material x2 – x1x 2 – xf (point 3) + x2 – x1x – x1f (point 4) interpolation of point 2 = (x, y2) (x, y_2) (x, y2)
Next, linear interpolation is performed in the Y direction:
Expand the above formula to get the final result, which is not too difficult, just write and read carefully: F (x, y) material (point 1) f (x2 – x) (y2 – y) (x2 – x1) (y2 – y1) + f (point 2) (x – x1) (y2 – y) (x2 – x1) (y2 – y1) + f (point 3) (x2) – x (y – y1) (x2 – x1) (y2 – y1) + f (point 4) (x – x1) (y – y1 ) (x2 – x1) (y2 – y1) f (x, y) \ approx \ cfrac {f (1) (x_2 – x) (y_2 – y)} {(x_2 – x_1) (y_2 – y_1)} + \ cfrac {(point 2) f (x – x_1) (y_2 – y)} {(x_2 – x_1) (y_2 – y_ 1)} + \ cfrac {f (point 3) (x_2) x (y – y_1)} {(x_2 – x_1) (y_2 – y_1)} + \ cfrac {(point 4) f (x – x_1) (y – y_1)} {(x_2 – x_1) (y_2 – y_1)} f (x, y) material (x2 – x1) (y2 – y1) F (1) (x2 – x) (y2 – y) + (x2 – x1) (y2 – y1) (point 2) f (x – x1) (y2 – y) + (x2 – x1) (y2 – y1) f (point 3) (x2 – x) (y – y1) + (x2 – x1) (y2 – y1) f (point 4) (x – x1) (y – y1)
This formula can be further simplified because the interpolation of two adjacent points is 1, so it is simplified as follows: F (x, y) material (point 1) f (x2 – x) (y2 – y) + f (point 2) (x – x1) (y2 – y) + f (point 3) (x2) – x (y – y1) + f (point 4) (x – x1) (y – y1) f (x, y) \ approx F (1) (x_2 – x) (y_2 – y) + f (point 2) (x – x_1) (y_2 – y) + f (point 3) (x_2) x (y – y_1) + f (point 4) (x – x_1) (y – y_1) f (x, y) material (point 1) f (x2 – x) (y2 – y) + f (point 2) (x – x1) (y2 – y )+ F (point 3)(x2−x)(y−y1)+ F (point 4)(x−x1)(y−y1) is substituting the coordinates of all points F (x, y) material (x1, y1) f (x2 – x) (y2 – y) + f (x2, y1) (x – x1) (y2 – y) + f (x1, y2) (x2) – x (y – y1) + f (x2, y2) (x – x1) (y – y1) 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) f (x, y) material (x1, y1) f (x2 – x) (y2 – y) + f (x2, y1) (x – x1) (y2 – y) + f (x1, y2) (x2) – x (y – y1) + f (x2, y2) (x – x1) (y – y1) (x, y) will replace the first writing (I + u, j + v), respectively, the coordinates of other points 1 ~ 4 are: (I,j), (I +1,j), (I,j+1), (I,j+1,j+1), substitute into the above formula, and the change results are shown as follows: F (I + u, j + v) material f (I, j) (I + 1 – + u) (I) (j + 1 – (j) + v) + f (I + 1, j) (I + u – I) (j + 1 – (j) + v) + f (I, j + 1) (I + 1 – + u) (I) (j + v – j) + f (I + 1, j + 1) (I + u – I) (j + v – j) f (i+u,j+v)\approx F (I, j) (I + 1 to + u) (I) (j + 1 to + v) (j) + f (I + 1, j) (I + u – I) (j + 1 to + v) (j) + f (I, j + 1) (I + 1 to + u) (I) (j + v – j) + f (I + 1, j + 1) (I + u – I) (j + v – j) f (I + u, j + v) material f ( I, j) (I + 1 – + u) (I) (j + 1 – (j) + v) + f (I + 1, j) (I + u – I) (j + 1 – (j) + v) + f (I, j + 1) (I + 1 – + u) (I) (j + v – j) + f (I + 1, j + 1) (I + u – I) (j + v – j)
Don’t get dizzy, this is probably the clearest conversion of the entire network: F (I + u, j + v) material 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) the uvf (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) the uvf (I + u, j + v) material 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 now corresponds to the formula from the beginning of this blog.
So are deduced by target image to the point, can pass for the computation of the coordinates of four points in front of each coordinate is called weight, assuming that there is such a pixel coordinates (1, 1), the estimation in the source map coordinates (0.75, 0.75), because there can be no floating point coordinates in the image, so get around four coordinates are (0, 0) (0,1) (1, 0) (1,1) since (0.75,0.75) is the closest to (1,1), point (1,1) has the greatest effect on the pixel color. The corresponding point (1,1) is f(I +1, I +1). The coefficient weight in front of this variable is 0.75*0.75. The result is maximum, and this illustration is illustrated by real data.
After getting the calculation method, you can realize the bilinear interpolation algorithm through the code.
Test the running time with the built-in scaling function:
if __name__ == '__main__':
src = cv2.imread('./t.png')
start = time.time()
dst = cv2.resize(src, (600.600))
print('Built-in function runtime: %f' % (time.time() - start))
cv2.imshow('src', src)
cv2.imshow('dst', dst)
cv2.waitKey()
Copy the codeThe resulting time is the runtime of the built-in function: 0.002000, which is very fast.
The next step is to write your own function validation, the code description I wrote in the comments, you can study, pay attention to the use of the formula
import cv2
import numpy as np
import time
def resize_demo(src, new_size) :
# Target image width and height
dst_h, dst_w = new_size
Source image width and height
src_h, src_w = src.shape[:2]
If the image size is the same, just copy it and return it
if src_h == dst_h and src_w == dst_w:
return src.copy()
# Calculate the scale
scale_x = float(src_w) / dst_w
scale_y = float(src_h) / dst_h
# Walk through the target image
dst = np.zeros((dst_h, dst_w, 3), dtype=np.uint8)
# return dst
Loop through the channel
# for n in range(3):
# for height loop
for dst_y in range(dst_h):
# loop over width
for dst_x in range(dst_w):
Coordinates of the target on the source
src_x = dst_x * scale_x
src_y = dst_y * scale_y
# Compute the positions of the four nearest neighbor points on the source graph
# 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__':
src = cv2.imread('./t.png')
start = time.time()
dst = resize_demo(src, (500.600))
print('Write function runtime: %f' % (time.time() - start))
cv2.imshow('src', src)
cv2.imshow('dst', dst)
cv2.waitKey()
Copy the codeThe code takes more than 2s to run, which is really time consuming.
Eraser section
I hope you learned something from today’s hour, and I’ll see you in the next blog