Abstract:

We present a novel approach for rapid numerical approximation of convolutions with filters of large support. Our approach consists of a multi-scale scheme, fashioned after the wavelet transform, which computes the approximation in linear time. Given a specific large target filter to approximate, we first use numerical optimization to design a set of small kernels, which are then used to perform the analysis and synthesis steps of our multiscale transform. Once the optimization has been done, the resulting transform can be applied to any signal in linear time. We demonstrate that our method is well suited for tasks such as gradient field integration, seamless image cloning, and scattered data interpolation, outperforming existing state-of-the-art methods.

Supplementary Materials:

It can be difficult to fully appreciate the differences between the small side-by-side images in the paper. Therefore, in these supplementary materials we include larger format versions of the images in the paper, with the ability to easily flip between them. We also include additional comparisons, examples, and visualizations. The material is organized in several pages, roughly corresponding to the figures in the paper.

Note: In order to view these pages properly, JavaScript must be enabled in your browser. In Internet Explorer, you may also need to allow blocked active content to run.

Sections:

1. Green's function - Reconstruction from gradients: chart, children, horses, beach
2. Green's function - Gradient domain HDR compression (Fattal et al 2002): kitchen, bottle, doll, lamp, synagogue, tree, lamp2
3. Membrane Construction: seamless cloning, object removal

Matlab Demo Code:

We provide several matlab scripts that implement our transform and make it possible to reproduce the various results shown in the paper. Please note that the running times quoted in the paper were measured using a different (optimized C++) implementation of the transform.

convpyr-code.zip

Kernels:

The optimized kernels used to produce the results in Sections 4--6 are available here: filters.txt