Discussion on high-speed secondary linear interpolation algorithm
principle
Linear interpolation is not difficult to understand. Taking the image processing field as an example, our ideal image is a uniform distribution in the two-dimensional plane right angle coordinate system, and give a pair of coordinates anywhere, it should be able to get a corresponding color value, but the reality is cruel, we only It is possible to approximate the image with discrete dot matrix information.
Now suppose gives a pair of coordinates (2.2, 4.0), you want to get the color corresponding to this coordinate, then a relatively simple method is to get the most recent pixels closest to this point, that is, the value of pixels (2, 4) with a four-way approach. Instead, this is obviously not very accurate. If the image is enlarged with this method, there will be a significant "mosaic" in the case of a large proportion.
For the above example, a better way is to mix the values of pixels (2, 4) and pixels (3, 4) in a certain proportion. How to choose a proportion? Very simple, which pixel is close, which pixel is mostly. So (simply, it is assumed to be a grayscale figure). If the value of the pixels (2, 4) is V_24, the value of the pixels (3, 4) is V_34, it can be obtained:
Coordinate (2.2, 4.0) color value V (2.2, 4.0) = v_24 * (1-0.2) v_34 * 0.2
Ok, now you have already understood what is linear interpolation!
Secondary linear interpolation is not difficult to understand. The coordinates we give this time are no longer so considerately - the color value of the coordinate (2.2, 4.6). Then you can think that the color value of coordinates (2.2, 4.0) and coordinates (2.2, 4.0) and coordinates (2.2, 5.0) can be obtained, and then use a vertical line type to get:
Coordinate (2.2, 4.0) color value V (2.2, 4.0) = v_24 * (1-0.2) v_34 * 0.2
Coordinate (2.2, 5.0) color value V (2.2, 5.0) = v_25 * (1-0.2) v_35 * 0.2
Coordinate (2.2, 4.6) color value = V (2.2, 4.0) * (1-0.2) V (2.2, 5.0) * 0.6
Here, in fact, we have obtained the calculation formula of secondary linear interpolation, and the expression is convenient to see the following symbols.
The adjacent four pixels values of the coordinates (X, Y) are P00, P01, P10, P11, the proportional coefficient of H0, H1, and the vertical direction, respectively, the ratio coefficient V1 (where H0 H1 = 1, " V0 V1 = 1), then get the Bilinear Interpolation:
v (x, y) = (p00 * h0 p01 * h1) * v0 (p10 * h0 p11 * h1) * v1 .............. (1.1)
With this formula, it is already possible to write an algorithm, but there are six floating point multiplication in this formula. If it is a true color map, there must be 18 floating point multiplication for each pixel! This is still not calculated that the time of generating floating point coordinate values (such as in the rotation algorithm, there are several floating point operations that have a pair of floating point coordinates).
optimization
Friends who have learned some linear algebraic knowledge may have noticed that formulas (1.1) can actually write a matrix multiplication form:
| p00 p01 | | H0 |
V (x, y) = | v0 v1 | * | | * | | ................................ 1.2)
| p10 p11 | | H1 |
Then we can optimize the algorithm by using the matrix multiplied algorithm. First, the arithmetic bottleneck here is from the four floating point values of V0, V1, H0, and H1, and do we need such a high precision? P00, P01, P10, P11 and our calculation results are integers (for our case, is an integer between 0-255). That is, when we finally assign our results to V (x, y), the fractional part has been cut off, we don't use so high precision at all! Then we can try to use an integer multiplication instead of floating point multiplication. For example, let V0 = (int) (V0 * 65536.0 0.5), V1 = 65536-V0, H0 = (int) (h0 * 65536.0 0.5), H1 = 65536-H0, then:
| p00 p01 | | H0 |
v (x, y) * 65536 * 65536 = | v0 v1 | * | | * | | ...................... (1.3)
| p10 p11 | | H1 |
Calculate (1.3) the value on the right side, the left can be used to replace the value of the V (x, y) in place of the division. Of course, when the algorithm is actually implemented, this formula will be overflow because the maximum value of the symbol integer is not (32768 * 65536-1), so the shift operation can be performed during the intermediate process.
Of course, optimization cannot be limited to this function, otherwise it is meaningless. When designing the entire algorithm (ie, an image processing algorithm that needs to use Bilinear InterPloation), it should avoid using floating point, guarantee V0, V1, H0 H1 is an inteleted value. In the WannaplayDib library, DIB_ROTATEFAST is a good example. In the central OX, OY can be obtained by intercepting the low 16-bit value, and H0 = 65536- H1, V0 = 65536-V1. Therefore, it is easy to write the second interpolation version of DIB_ROTATEFAST.
