Convolution Pyramids Based Rapid Screened Poisson Equation Solver

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.