纳金网

标题: Convolution Pyramids [打印本页]

作者: 晃晃 时间: 2011-12-29 09:26
标题: 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 ﬁlters of large support. Our approach consists of

a multiscale scheme, fashioned after the wavelet transform, which

computes the approximation in linear time. Given a speciﬁc large

target ﬁlter to approximate, we ﬁrst 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 ﬁeld 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) ﬁlters to images.

Common examples include low- and high-pass ﬁltering of images,

and measuring the image response to various ﬁlter banks. Some less

obvious tasks that can also be accomplished using large LTI ﬁlters

are demonstrated in Figure 1: reconstructing images by integrating

their gradient ﬁeld [Fattal et al. 2002], ﬁtting 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 ﬁlter 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 efﬁcient, 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 speciﬁc

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

useful large LTI ﬁlters, while operating in O(n) time. Speciﬁcally,

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.

Speciﬁcally, we repeatedly perform convolutions with three small,

ﬁxed-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 ﬁlter. The optimization only needs to be done once for

each target ﬁlter, 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 ﬁnite ﬁlters, on the one hand,

while attempting to make the most out of the linear computational

budget, on the other.

全文请下载附件：

作者: 晃晃 时间: 2012-2-1 23:26
凡系斑竹滴话要听；凡系朋友滴帖要顶!

作者: 奇 时间: 2012-3-4 23:20
我也来支持下

作者: 晃晃 时间: 2012-5-5 23:22
不错不错，收藏了

作者: C.R.CAN 时间: 2012-6-26 23:19
不错不错，收藏了

作者: C.R.CAN 时间: 2012-6-28 23:24
不错不错，收藏了

作者: 奇 时间: 2012-12-3 23:25
不错不错，收藏了

作者: C.R.CAN 时间: 2013-2-10 23:22
已阵亡的蝶随风舞说过偶尔按一下 CTRL A 会发现世界还有另一面

欢迎光临纳金网 (http://go.narkii.com/club/)