Android图像处理系列 - 高斯模糊的几种优化方法

一，高斯模糊简介

高斯模糊是图像处理中常用的一种操作，用于减少图像细节，平滑图像。简单来说，高斯模糊的处理过程，是让图像每个像素都取周边像素的平均值，是参照正态分布的加权平均值。

比如kernel为3*3的高斯模糊，就是取每个像素周围8个点再加上该像素的加权平均值，每个点的权重如图1。

图1 kernel为3的高斯模糊，每点权重值

高斯模糊每个点的权重分配以正态分布为依据。一维正态分布函数

函数图像如图2。

图2 一维标准正态分布

不同的

，对应不同的函数图像，如图3。另外正态分布函数中

。高斯模糊实现时，如何选择

，如何根据给定的模糊半径确定有限个采样点的权重，都是需要解决的问题，不过并不在本文讨论范围之内。

图3 不同的正态分布

二维正态分布函数

图4 二维正态分布图像

可以看出，二维正态分布函数，等于x方向和y方向的两个一维正态分布函数的乘积。

高斯模糊的实现，一般不会直接对m*m范围内的点计算加权平均，这种方式的时间复杂度为O(n*n*m*m)，这里假设传入图像大小为n*n，kernel为m。较常见的做法是，分别在x方向和y方向，各做一次加权平均。时间复杂度可以降低到O(n*n*m)。

二，box blur：cpu上的快速实现

高斯模糊要求距离中心点越近的点，权重越高，越远则权重越低。如果所有点权重一样，则无法得到平滑的模糊效果。

但是，权重相同的模糊操作，重复多次之后，也可以得到类似高斯模糊的效果。这就是box blur。Box blur与高斯模糊的效果比较如图5。

图5 box blur与高斯模糊效果比较

从一维角度观察，box blur对数值的改变情况如图6所示。依次是经过一次box blur，经过两次box blur和经过三次box blur的结果。

图6 box blur多次处理结果比较

Box blur重复三次，与高斯模糊的差异在3%以内。效果上非常接近。

Box blur的最大优势，在于计算相同权重平均数，可以使用滑动窗口方法。Box blur的时间复杂度为O(n*(n+m))，因为一般m<<n，所以增大模糊半径，对box blur的耗时影响很小。

如果用CPU实现高斯模糊效果，box blur应该是最高效的算法，还可以利用多线程进一步提高box blur的速度。不过对于移动端GPU，使用OpenGL接口，较难使用滑动窗口方法计算平均数，所以box blur的优势在GPU上较难体现出来。

三，利用GPU线性插值减少采样次数

GPU做高斯模糊，常用的优化方法之一，是利用texture采样时的线性插值，来减少采样次数和计算次数。

Texture采样的线性插值操作如图7所示。

图7 texture采样线性插值

a，b，c，d是texture上相邻的四个点，如果从texture上采样，传入的e点的坐标刚好在a，b之间，那么取得的值为a、b两点的加权平均值

，。如果e位于a、b、c、d之间，则e的值是a、b、c、d四点双线性插值的结果。Texture采样时的线性插值操作，由GPU硬件默认完成，效率较高。

利用线性插值可以做到一次采样得到两个点的值，加快高斯模糊的计算速度。例如图8。

图8 利用线性插值减少采样次数

假设做横向的加权平均，中心点为c，c点左右各取两个点，每个点的权重如图所示。

c’ = 0.625a + 0.25b + 0.375c + 0.25d + 0.625e。

a点和b点本来各需做一次采样，利用线性插值，在b点左侧0.625/(0.625+0.25)个点距的位置采样，得到的结果就是(0.625a + 0.25b)/(0.625+0.25)。同理d和e的加权和也可以用一次采样得到。原来共需要5次采样，现在只需要3次。

利用上述方法，大体上可以让高斯模糊采样次数减半，效率提升明显。不过，这种方法只是利用一次采样获取两个点的值，而一次采样最多可以得到四个点的值。所以在利用GPU线性插值这一点上，是否有更快的实现高斯模糊的方法？答案是肯定的，那就是Kawase blur。

Kawase blur利用一次采样获取四个点的值，每一次处理做4次采样，进行多次处理，最终得到近似于高斯模糊的结果。如图9，Kawase blur通过5次处理，可以得到类似kernel size为35的高斯模糊的效果。

图9 kernel依次为0，1，2，2，3的Kawase blur

图中的灰色方格表示texture中的一个像素，蓝色点表示采样位置。红色方格表示当前要计算平均和的点。规定这5次处理的Kawase blur kernel，依次是0，1，2，2，3。可以通过这样一个数组来描述特定次数和kernel的Kawase blur。

下图是从一维角度，比较kernel 为35的高斯模糊，和上述(0,1,2,2,3)的Kawase blur在处理结果上的差异。

图10 左：kernel为35的高斯模糊。右：(0,1,2,2,3)的Kawase blur

下图是两种模糊算法处理实际图片的结果比较。依次是原图，高斯模糊处理结果，Kawase blur处理结果。

图11 Kawase blur与高斯模糊效果对比

效率上面，kernel为35的高斯模糊，使用线性插值的优化方法，每个点的采样次数为18*2=36次，(0,1,2,2,3)的Kawase blur的采样次数仅为4*5=20次。图12是不同硬件，不同kernel的高斯模糊与Kawase blur处理时间比。可以看出Kawase blur比高斯模糊速度更快。高斯模糊的处理时间会随kernel增大而线性增加，Kawase blur的处理时间随着kernel增大，似乎会以低于线性的速度增加。

图12 Kawase blur与高斯模糊运行时间对比

Kawase blur的主要限制在于，对任意的高斯模糊kernel，没有方法可以直接得到对应的Kawase blur的kernel list。

四，缩小图片

高斯模糊另一个常见的优化方法，是对图片进行缩小，然后再做模糊，最后再把图片放大到原来尺寸。

缩小图片往往有丢失图像细节的问题，而高斯模糊的作用在于平滑地降低图像细节。所以可以利用缩小图片的方法，减少计算量同时几乎不影响最终效果。

常见做法是缩小图片-->高斯模糊-->放大图片，但这样容易出现一个问题，当缩小比例较大时，小图高斯模糊之后，图像会有锯齿。

解决方法，N次缩小，每次缩小到原来的1/4并伴随一次（固定kernel的）模糊，在最终的小图上再做一次kernel为K的模糊。N和K与要达到的高斯模糊kernel有关。

这种方法可以避免锯齿，时间复杂度上也比标准高斯模糊更快，标准高斯模糊每个点上的计算量与kernel成正比。这种缩小模糊的方法，每个点的计算量估计与kernel的对数成正比。在kernel比较大时，这种方法效率提升明显。

参考文献

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

作者简介：camusli(李小奇)，天天P图Android工程师