快速双边滤波器

空间领域通过二次采样的低存储、简单、快速双边滤波器摘要：文章提出一个算法，来加速基于二次采样的策略的彩色双边滤波器，工作在空间领域。基本思路是使用一个合适样本子集来获得一个准确滤波器的好的估计，方法的优点是在视觉质量和加速之间有一个很好的权衡，需要一个小的内存开销和非常简单的在GPU上实现实时滤波，论文展示了滤波器的不同应用，特别是高效的交叉滤波器，实时识别边的图像编辑和快速视频去噪，我们从时间性能，内存使用，图像质量和前沿方法比较。介绍：领域处理包括：1.定义中心点（x，y）2.仅对定义的以（x，y）为中心的领域进行运算，3.运算结果为该点处处理的响应，4.对图像上的每一点做相同的操作。移动中心会产生新的领域，每个领域对应与输入图像上的一个像素。线性滤波的概念源于频域中信号处理所使用的傅利叶变换。线性运算包括将领域中的每一个像素与相应的系数相乘，然后将结果进行累加，从而得到（x，y）处的响应，若领域的大小是m*n，则总共需要mn个系数。这些系数排列成矩阵，我们称为滤波器、掩模、滤波掩模、核、模板或者窗口。为简便起见，我们通常称为卷积滤波、掩模或核等术语。非线性空间滤波也是基于领域操作，和线性滤波不一样，它是基于非线性操作，令每一点处的响应等于其领域的最大像素值的操作就是非线性滤波。非线性滤波器广泛使用在计算机图论、图像和视觉，用作不同的应用，特别指出，双边滤波器是一个非常流行的非线性滤波器，由Tomansi和Manduchi两人提出的，因为过滤图像的区域同时保持完整的边。而且它简单的公式和灵活性使得它应用在不同的问题上，例如：消除图像噪音、图像视频格式化、高动态范围色调映射、频闪摄影术、边清晰的二次采样等等，根据Tomansi和Manduchi公式，双边滤波器定义如下：I表示一个k维图像，Ω表示像素xi的一个集合，fr和gs分别表示范围衰减函数和空间衰减函数，这些函数都是权值函数，典型的高斯函数，Adams提出了公式1的一个简洁形式：p是多维像素，例如pi={ri,gi,bi,xi,yi}T,(ri,gi,bi)T是RGB颜色，（xi，yi）是像素的空间坐标位置，pi乘以高斯函数的一个标准方差（σr,σg,σb,σx,σy)−T，方程2认为权值函数是高斯函数，在我们的方法中，我们没有作出太多的假设，保持了原有的公式，方程1的计算复杂度非常高，图像的每一个像素的时间复杂度是O(Nk），这些年，在算法的改进方面激发了大量的研究工作，来加快计算速度。一些改进的技术也可以用来加速高维的非线性的滤波器，例如non-localmeans，是目前比较流行的去噪算法，被广泛应用于高分辨率图像显示。图1：取左边图像中的一个子集样本samples，通过加权值weight累加得到最终的值reault。这篇论文的主要贡献就是实现双边滤波器的加速技术，很容易在一个计算性能高、内存小，不许要预处理的Gpu上执行。对于彩色双边滤波提供一个高质量结果，我们技术的主要思路是提供一个二次采样策略加速方程1的计算。换句话说，为了提供准确滤波器值的估计，滤波器核是通过空间域的一个子集来计算。每一个像素采取不同的采样模式，避免已经过滤过的图像产生结构噪音。这种方法不能加速高维的滤波，不管怎样，它能够在GPU和CPU上执行，能够提供高质量结果。尽管如上提到的局限性，但是这方法能够用在交叉双边滤波器，而且很容易推广在视频处理中，算法的时间复杂度是O(mNk），N是核的半径，k是图像维数，m是图像像素的总数，这改善了方程1的蛮力计算，其时间复杂度O(mNk），而且我们的方法不需要预处理特征，空间复杂度O（1）。2相关工作最近提研发了几种方法加速不同类型的双边滤波器，例如灰度级滤波器、彩色滤波器或者交叉双边滤波器。这些方法也能够有效计算高维非线性滤波器，例如non-localmeans。这儿讨论最先进的方法。一个最简单的加速计算双边滤波器的方法，如果是图像，则把滤波器分离成两个一维滤波器，如果是视频，则把滤波器分离成3个滤波器。这样就可以把每个像素的时间复杂度从O（NK）降到O（NK），这是一个粗略的双边滤波器的近视值，但是它在视频去噪方面能够得到好的结果，技术的主要有点如下：对于中大内核半径（over20pixes）方法产生错误的结果，而且空间复杂度从O（1）增加到O（m），因为图像必须存储第二次来估计滤波器Paris和Durand提出一个新颖的方法计算双边滤波器，通过把它作为一个高维的卷积，在一个spatio-tonal空间，方法的第一步是splating（抛雪球算法）把数据转换到高维空间(spatio-tonal)，这个时候数据通过标准卷积变得模糊，数据能够高效计算，最后，滤波过的值通过空间插值被转换到原来的域，算法的最后阶段叫做splicing，Chen提出了双边网格，一个GPU友好的数据结构，方法的实现充分利用现在图像硬件的并行性。这种方法能够处理高阶滤波器，但是需要消耗很大的内存，而且，双边网格不是转化不变的，例如，滤波的结果依赖网格的阶段，高斯KDTREE像双边网格一样，但是使用了不同的数据结构来实现splating、bluring和splicing。这种技术能够有效的加速高维滤波器，前提是低的内存消耗。最新的一个加速技术是Adams提出，方法的数据结构有双边网格和高斯KD树一样的性能，它比高斯KD树要稀疏，同时比双边网格消耗更低内存，所以这种技术能够有效计算高维滤波器。另一个不同的方法，加速双边滤波减少多余操作利用窗口的有序重叠，非常有名的例如中值滤波。BenWeiss从中值滤波器基于直方图的加速算法中获得灵感，开发了对于中值滤波器的快速算法（每个像素的时间复杂度是O（logN）），BenWeiss使用同样的方法加速双边滤波器，假设空加函数平均在一个正方形核中。Porikli使用直方图开发灰度级双边滤波器的快速算法（每一次图像的一个通道被处理），算法的时间复杂度O(1)，通过重新定义双边滤波器计算公式，fx（s）=c是线性滤波器的一个准确和，这个和可以通过积分直方图在常时间内计算不依赖核的大小，Porikli通过泰勒展开式把公式拓展到任意空间滤波器，这种情况，得到的结果非常接近真实的双边滤波器。Yang改进了这种方法（Porikli），量化放到一个范围函数而不是图像强度，获得一系列线性滤波器，滤波过的图像通过滤波器输出的线性空间插入获得，Yu优化了yang的方法，引入一种权衡优化标准。Gunturk改进了porikli的方法，采用盒子核，使用盒子核的加权和近似任意域核。而且Igarashi提出在一个算法中使用多层直方图来减少这种滤波器的内存需求，所有的这些基于直方图的方法都适用于8位图，而不适用于HDR图像。evaluateYoshizawa提出一个基于快速高斯转换（FGT）的加速算法。FGT是高斯加权和快速、错误控制计算的一种技术。主要想法是在一个高维域把双边滤波器作为一个高斯加权和处理。使用FGT计算结果的和。该算法有线性的时间复杂度。Fattal提出了一个加速策略，该方法重复使用j规模级来计算j+1级滤波器。我们的算法不同于以上提到的方法，因为它整个基于二次采样，直接执行在空间域。使用二次采样来加速处理的想法并不是最新的，从计算射线轨迹的呈现方程(使用不同采样策略)到一个基于霍尔顿采样的二次采样策略被用来加速计算两个图像的相似信息，而且双边网格在它的构造期间采用缩减采样，高斯KD树在节点构造期间采用梦特卡罗采样。此外，chen提出了一个应用在spatial-tonal域的对视频的泊松磁盘二次采样优化，不管咋样，我们的二次采样策略执行在空间域（图像在同样的域下定义），不许要把样本映射到其它域，这就容许在CPU和图形硬件上简单实现，尽管方法简单，但是能够提供图像视频的高质量结果，正如叙述的，它只适用于一定阶的滤波器，而不适用于高阶滤波器，例如：双边网格，高斯KD树，FGT。无论如何，对于图像的动态范围、空间和范围函数我们不做任何假设。3.算法我们算法的主要思路是计算方程1（k维图像NK核窗口的Ω的一个子集ᴧ），算法1展示完整双边滤波器的伪代码实现，算法2快速双边滤波器伪代码。Bruteforce算法要计算Ω集的所有像素，我们的方法很简单，只需要通过一个均匀分布的子集ᴧ来计算方程1。算法的主要部分是getsample()函数，它返回样本的坐标，为了取得双边滤波器确切值的一个近似值，getsample（）必须小心取样，对于getsample（），我们测试了不同的采样策略，例如：规则采样（RPS），梦特卡罗采样（MCS），分层的梦特卡罗采样（SMS），泊松磁盘采样（PDS），在我们测试中，我们使用Bridson算法产生泊松磁盘分布的样本。为了避免结构噪音和改善随机性，不同部分的子集提前计算，至于PDS，就随机性而言，64块足够获得好的结果，模式集的存储在内存需要小的开销，例如255*255的核需要64kb的内存，与图像原始大小无关，而且这些采样模式的计算非常快。Figure3展示不同采样策略的视觉对比，RPS产生结构噪音，所以需要随机性的删除这些artefacts，无论如何，MCS也导致噪音，SMS也产生噪音，基于这些问题，我们选择泊松磁盘分布来得到样本，虽然有噪音，但这些噪音在人类视觉系统面前被模糊了。从理论观点看，我们可以通过使用最大泊松磁盘采样程序使采样处理变得没有偏差。为了确保相符和的估计量保持无偏差，我们可以使用克兰利帕特森旋转(Cranley-Pattersonrotaion)随机移动集合，使用移动策略点集的存储就会降低，例如256*256核需要1kb内存，我们方法的错误约束与图像的变化有关，在平滑区域错误期待降到最低，错误增加依赖与区域的变化(中心、边)，因为对于整个区域(N2)只有一些样本(KN)被提取。提出的方法也可以处理视频，2维图像和视频仅有的不同是泊松磁盘采样分别在2维和3维中计算，它不能像其它方法一样扩展到K维，因为不能保证泊松磁盘采样很好的工作于任意维。由于方法的简单性，我们直接在OPENGL框架上使用GLSL着色器实现算法，即使在低档的图形硬件也能高效的实现。3.1需要的样本数的分析使用高斯函数作为衰减函数，gswithvarianceσs,frwithvarianceσr，我们通过不同的采样密度测试我们采样近视值的精确性，对于一个N*N像素的核，KN个样本被使用(K=1、2……7)，6个HDR图像随着σrorσs变化，从Figure4中可以看到，一个N*N大小的核使用N或2N的样本就质量而言是合理的，N=3N，需要增加计算时间，3N和4N样本之间的差异是1dB。在figure4中，对于固定的mPSNR值，需要的样本减少，这种减少遵循矩形双曲线的形状随着坐标轴平行于他们的渐进线，从这些图的滤波数据到双曲线，可以推出:smallkenerl（σs20pixes）需要2.5N样本，mediumkenerls（20σs40）需要0.75N到2.5样本，largekenerls（σs40）需要0.75N样本。4应用为了展示方法的有效性，我们现在可以把算法应用在计算机图像图像处理中，包括图像和视频滤波，迭代滤波，交叉或者节点双边滤波，色调映射。4.1视频去噪：双边滤波器的一个典型的应用是图像视频去噪，因为滤波器删除了高斯噪音同时保持了完整的边，figure5是视频去噪的一个应用。我们的方法非常应用于视频去噪，因为它需要的内存比较小，对于高清视频可以实现实时的帧速率。4.2抽象我们的双边滤波器适合迭代滤波，因为它收敛与非常相近的参考结果，由于一个事实，每一次迭代，每个像素在空间位置中改变，迭代双边滤波器非常适用于图像视频抽象。4.3闪光非闪光摄影iso高感光度和高速快门2使用闪光灯3通过标准交叉双边滤波器使用闪光非闪光摄影去噪4采用我们的算法4.4边识别图像编辑双边滤波器可以用作边识别图像编辑。在一个选中区域图像的参数被修改，通过画刷描边避免修改相领的区域，区域被边分割开来。滤波器的输出是边识别画刷，可以用来修改图像的