current position:Home>Bilinear interpolation algorithm for Python OpenCV image, the most detailed algorithm description in the whole network

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

2022-01-30 05:10:15 Dream eraser

Little knowledge , Great challenge ! This article is participating in 「 A programmer must have a little knowledge 」 Creative activities

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 ~

Python OpenCV  Bilinear interpolation algorithm of image , The most detailed algorithm description of the whole network

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 ) (x_0,y_0) and ( x 1 , y 1 ) (x_1,y_1) , To calculate [ x 0 , x 1 ] [x_0,x_1] Somewhere in the interval x On a straight line y value , The formula is as follows :

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

The formula is deformed to obtain :

y = x 1 x x 1 x 0 y 0 + x x 0 x 1 x 0 y 1 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 x_0 and x 1 x_1 Distance as a weight , be used for y 0 y_0 and y 1 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 ) x 2 x x 2 x 1 f ( spot 1 ) + x x 1 x 2 x 1 f ( spot 2 ) 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 ) (x,y_1)

The same algorithm obtains interpolation points 2:

f ( Interpolation point 2 ) x 2 x x 2 x 1 f ( spot 3 ) + x x 1 x 2 x 1 f ( spot 4 ) 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 ) (x,y_2)

The next in Y Linear interpolation calculation of direction :

f ( P ) y 2 y y 2 y 1 f ( Interpolation point 1 ) + y y 1 y 2 y 1 f ( Interpolation point 2 ) 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 ) f ( spot 1 ) ( x 2 x ) ( y 2 y ) ( x 2 x 1 ) ( y 2 y 1 ) + f ( spot 2 ) ( x x 1 ) ( y 2 y ) ( x 2 x 1 ) ( y 2 y 1 ) + f ( spot 3 ) ( x 2 x ) ( y y 1 ) ( x 2 x 1 ) ( y 2 y 1 ) + f ( spot 4 ) ( x x 1 ) ( y y 1 ) ( x 2 x 1 ) ( y 2 y 1 ) 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 ) 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 ) 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 ) 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)\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 ) 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 ) 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 ) 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 ) u v 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__':
    src = cv2.imread('./t.png')
    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__':
    src = cv2.imread('./t.png')
    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 ~

copyright notice
author[Dream eraser],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201300510129146.html

Random recommended