Gauss fuzzy introduction
Gaussian blur is a common operation in image processing, which is used to reduce image details and smooth the image. In simple terms, the processing process of Gaussian blur is to make each pixel of the image take the average value of the surrounding pixels, which is the weighted average value with reference to the normal distribution.
For example, gaussian blur with kernel of 3*3 is to take 8 points around each pixel and add the weighted average value of the pixel. The weight of each point is shown in Figure 1.
Figure 1 gaussian blur with kernel 3, weight value of each point
The weight distribution of each point in gaussian blur is based on normal distribution. One-dimensional normal distribution function
The functional image is shown in Figure 2.
FIG. 2 One-dimensional standard normal distribution
different
FIG. 3 Different normal distributions
Two dimensional normal distribution function
FIG. 4 two-dimensional normal distribution image
You can see that the two-dimensional normal distribution function is the product of the two one-dimensional normal distribution functions in the x and y directions.
Generally, gaussian blur will not directly calculate the weighted average of points within the range of M *m. The time complexity of this method is O(N * N *m*m). Here, it is assumed that the size of the incoming image is N * N and the kernel is M. It is more common to do weighted averages in the x direction and in the y direction. The time complexity can be reduced to O(n*n*m).
Box Blur: Fast implementation on CPU
Gaussian blur requires that the closer the point is to the center, the higher the weight is, and the farther the point is, the lower the weight is. If all points have the same weight, a smooth blur effect cannot be achieved.
However, the same weight fuzzy operation, repeated several times, can also get the effect of gaussian blur. That’s box blur. The effect comparison between Box blur and Gaussian blur is shown in Figure 5.
FIG. 5 Comparison of box blur and Gaussian blur effect
From a one-dimensional perspective, the change of logarithms in box blur is shown in FIG. 6. After box blur once, after box blur twice, and after box blur three times.
FIG. 6 Comparison of multiple processing results of Box blur
Box blur was repeated three times, and the difference from Gaussian blur was within 3%. It’s very close in effect.
The biggest advantage of Box blur is that the sliding window method can be used to calculate the average of the same weight. The time complexity of Box blur is O(n*(n+m)). Since m<
If gaussian blur effect is implemented with CPU, Box blur is the most efficient algorithm, and the speed of Box blur can be further improved by multi-threading. However, for mobile GPU, using OpenGL interface, it is difficult to calculate the average by sliding window method, so the advantages of Box blur are difficult to be reflected on GPU.
Third, use GPU linear interpolation to reduce the sampling times
One of the commonly used optimization methods for Gaussian blur on GPU is to use linear interpolation of texture sampling to reduce sampling times and calculation times.
The linear interpolation operation for the Texture sample is shown in Figure 7.
Figure 7. Texture sampling linear interpolation
a.b.c.distextureThe four points next to each other, if you go fromtextureUpsampling, incomingeThe coordinates of the point are exactly ata.bBetween, then the value obtained isa,bThe weighted average of the two points
Linear interpolation can be used to get the values of two points at a time, which speeds up the calculation of Gaussian blur. For example, see Figure 8.
FIG. 8 Using linear interpolation to reduce the sampling times
Suppose that the horizontal weighted average is made, and the center point is C, and two points are taken at the left and right sides of point C. The weight of each point is shown in the figure.
C ‘= 0.625a + 0.25b + 0.375c + 0.25d + 0.625e
At point A and point B, samples should be taken at 0.625/(0.625+0.25) points to the left of point B by linear interpolation. The results obtained are (0.625 A + 0.25B)/(0.625+0.25). Similarly, the weighted sum of d and E can be obtained with a single sample. It used to take five samples, but now it only takes three.
By using the above method, the sampling times of Gaussian fuzzy can be reduced by half and the efficiency can be improved obviously. However, this method only uses a single sample to obtain the values of two points, whereas a single sample can obtain the values of up to four points. So in the use of GPU linear interpolation, is there a faster way to achieve Gaussian blur? The answer is yes, Kawase blur.
Kawase blur uses a single sampling to get the values of four points, four samples per processing, and multiple processing to get a result that is close to Gaussian blur. As shown in Figure 9, Kawase blur can achieve a similar effect of Gaussian blur with kernel size 35 through five times of processing.
Figure 9 Kawase blur with kernel 0,1,2,2,3
The gray square represents a pixel in the texture and the blue dot represents the sampling position. The red square represents the point at which the average sum is currently calculated. The Kawase blur kernel that defines these five processes is 0, 1, 2, 3. Such an array can be used to describe the Kawase blur of a specific number and kernel.
The following figure compares the difference in processing results between gaussian blur with kernel 35 and Kawase blur (0,1,2,2,3) from a one-dimensional perspective.
Figure 10 left: Gaussian blur with kernel 35. Right :(0,1,2, 3) Kawase blur
The following figure is a comparison of the results of the two fuzzy algorithms on actual images. The original image, gaussian blur, Kawase blur.
FIG. 11 Kawase blur versus Gaussian blur
In terms of efficiency, gaussian blur with a kernel of 35 is optimized by linear interpolation, and the sampling times of each point are 18*2=36 times, while the sampling times of Kawase blur with (0,1,2, 3) are only 4*5=20 times. Figure 12 shows the processing time ratio of Gaussian blur and Kawase blur with different hardware and kernel. Kawase blur is faster than Gaussian blur. The processing time of Gaussian blur increases linearly with the increase of kernel, while the processing time of Kawase blur increases less than linearly with the increase of kernel.
Figure 12 Kawase blur versus Gaussian blur running time
The main limitation of Kawase blur is that there is no way to directly obtain the kernel list of Kawase blur for any Gaussian blur kernel.
Four, shrink the picture
Another common optimization method for Gaussian blur is to reduce the image, blur it again, and finally enlarge the image to its original size.
Zooming out an image often loses the details of the image, while gaussian blur is used to smoothly reduce the details of the image. So you can use the method of shrinking the image to reduce the amount of calculation and almost not affect the final result.
The common approach is to reduce the image -> Gaussian blur -> enlarge the image, but this is prone to a problem, when the reduction scale is large, the image will be jagged after the gaussian blur.
The solution is to shrink N times, each time to 1/4 of the original size with a fuzzy (fixed kernel), and do the fuzzy with kernel as K again on the final small graph. N and K are related to the gaussian fuzzy kernel to be achieved.
This method can avoid sawtooth and is faster than standard Gaussian blur in time complexity. The amount of calculation at each point of standard Gaussian blur is proportional to kernel. In this method of reducing ambiguity, the calculation amount of each point is estimated to be proportional to the logarithm of kernel. When the kernel is large, the efficiency of this method is significantly improved.
reference
1) https://en.wikipedia.org/wiki/Gaussian_blur
2) https://en.wikipedia.org/wiki/Box_blur
3) https://prolost.com/blog/2006/3/2/a-tale-of-three-blurs.html
4) https://software.intel.com/en-us/blogs/2014/07/15/an-investigation-of-fast-real-time-gpu-based-image-blur-algorithms
5) http://www.daionet.gr.jp/~masa/archives/GDC2003_DSTEAL.ppt
6) https://www.google.com/patents/US7397964
About the author: Camusli (Li Xiaoqi), Tian Tiantu Android engineer