基于卷积金字塔的屏蔽泊松方程快速求解算法

Convolution Pyramids Based Rapid Screened Poisson Equation Solver

屏蔽泊松方程在图像视频处理和图形学领域有着广泛应用,传统上一般借助离散余弦变换或快速傅里叶变换求解,计算复杂度为O(nlogn).提出了一种基于卷积金字塔的快速近似求解算法,将屏蔽泊松方程求解视为一个“大核”卷积过程,利用卷积金字塔,将“大核”卷积分解为若干个“小核”卷积,从而将计算复杂度改善至线性.实验发现,在图像无缝拼合和梯度域绘制的应用中,对于千万像素级别图像,所提算法能获得5~6倍的性能提升.进一步,屏蔽泊松方程求解也是许多图像迭代算法的中间步骤,以加权最小二乘图像光滑和基于总变差正则化的图像重建算法为例,运用所提算法,在视觉效果和均方误差上都有着很好的近似,在速度上有显著的提升.

Screened Poisson equation has plenty of applications in image video processing and computer graphics.Generally,discrete cosine transform or fast Fourier transform with a computational complexity of O(n log n)is used to solve the equation.In this paper,a fast approximation algorithm is proposed in which solving the screened Poisson equation is regarded as a convolution with a large-sized kernel.Then,the convolution pyramid is used to decompose the convolution with a large-sized kernel into several convolutions with a small-sized kernel.The algorithm can reduce the computational complexity to linearity.Experiments showed that the method can achieve 5~6 times performance improvement for ten-megapixel level images in seamless image cloning and gradient domain rendering.Moreover,the screened Poisson equation solver can be used as an intermediate step in many image iterative algorithms.Applying the proposed method in these algorithms,we obtained a good approximation in visual effects and mean squared error,and a significant increase in speed.