Convolution Pyramids

晃晃

Convolution Pyramids

Zeev Farbman Raanan Fattal Dani Lischinski

The Hebrew University The Hebrew University The Hebrew University







Abstract

We present a novel approach for rapid numerical approximation of

convolutions with filters of large support. Our approach consists of

a multiscale 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 im-

age cloning, and scattered data interpolation, outperforming exist-

ing state-of-the-art methods.

Keywords: convolution, Green’s functions, Poisson equation,

seamless cloning, scattered data interpolation, Shepard’s method

1 Introduction

Many tasks in computer graphics and image processing involve

applying large linear translation-invariant (LTI) filters to images.

Common examples include low- and high-pass filtering of images,

and measuring the image response to various filter banks. Some less

obvious tasks that can also be accomplished using large LTI filters

are demonstrated in Figure 1: reconstructing images by integrating

their gradient field [Fattal et al. 2002], fitting a smooth membrane

to interpolate a set of boundary values [P´ erez et al. 2003; Agarwala

2007], and scattered data interpolation [Lewis et al. 2010].

While convolution is the most straightforward way of applying an

LTI filter to an image, it comes with a high computational cost:

O(n2) operations are required to convolve an n-pixel image with

a kernel of comparable size. The Fast Fourier Transform offers a

more efficient, O(nlogn) alternative for periodic domains [Brigham

1988]. Other fast approaches have been proposed for certain special

cases. For example, Burt [1981] describes a multiscale approach,

which can approximate a convolution with a large Gaussian kernel

in O(n) time at hierarchically subsampled locations. We review this

and several other related approaches in the next section.

In this work, we generalize these ideas, and describe a novel mul-

tiscale framework that is not limited to approximating a specific

kernel, but can be tuned to reproduce the effect of a number of

useful large LTI filters, while operating in O(n) time. Specifically,

we demonstrate the applicability of our framework to convolutions

with the Green’s functions that span the solutions of the Poisson

equation, inverse distance weighting kernels for membrane inter-

polation, and wide-support Gaussian kernels for scattered data in-

terpolation. These applications are demonstrated in Figure 1.

Our method consists of a multiscale scheme, resembling the Lapla-

cian Pyramid, as well as certain wavelet transforms. However,

unlike these more general purpose transforms, our approach is to

custom-tailor the transform to directly approximate the effect of a

given LTI operator. In other words, while previous multiscale con-

structions are typically used to transform the problem into a space

where it can be better solved, in our approach the transform itself

directly yields the desired solution.

Specifically, we repeatedly perform convolutions with three small,

fixed-width kernels, while downsampling and upsampling the im-

age, so as to operate on all of its scales. The weights of each of

these kernels are numerically optimized such that the overall action

of the transform best approximates a convolution operation with

some target filter. The optimization only needs to be done once for

each target filter, and then the resulting multiscale transform may

be applied to any input signal in O(n) time. The motivation behind

this design was to avoid dealing with the analytical challenges that

arise from the non-idealness of small finite filters, on the one hand,

while attempting to make the most out of the linear computational

budget, on the other.



全文请下载附件：

晃晃

凡系斑竹滴话要听；凡系朋友滴帖要顶!

奇

我也来支持下

晃晃

不错不错，收藏了

C.R.CAN

不错不错，收藏了

C.R.CAN

不错不错，收藏了

奇

不错不错，收藏了

C.R.CAN

已阵亡的 蝶 随 风 舞 说过  偶尔按一下 CTRL A 会发现 世界还有另一面