Multigrid and Multilevel Preconditioners for Computational Photography

晃晃

Multigrid and Multilevel Preconditioners for Computational Photography

Dilip Krishnan  Richard Szeliski

Department of Computer Science Interactive Visual Media Group

New York University Microsoft Research







Abstract

This paper unifies multigrid and multilevel (hierarchical) precon-

ditioners, two widely-used approaches for solving computational

photography and other computer graphics simulation problems. It

provides detailed experimental comparisons of these techniques

and their variants, including an analysis of relative computational

costs and how these impact practical algorithm performance. We

derive both theoretical convergence rates based on the condition

numbers of the systems and their preconditioners, and empirical

convergence rates drawn from real-world problems. We also de-

velop new techniques for sparsifying higher connectivity problems,

and compare our techniques to existing and newly developed vari-

ants such as algebraic and combinatorial multigrid. Our experimen-

tal results demonstrate that, except for highly irregular problems,

adaptive hierarchical basis function preconditioners generally out-

perform alternative multigrid techniques, especially when compu-

tational complexity is taken into account.

Keywords: Computational photography, Poisson blending, col-

orization, multilevel techniques, fast PDE solution, parallel algo-

rithms

1 Introduction

Multigrid andmultilevel preconditioning techniques have long been

widely used in computer graphics and computational photography

as ameans of accelerating the solution of large gridded optimization

problems such as geometric modeling [Gortler and Cohen 1995],

high-dynamic range tone mapping [Fattal et al. 2002], Poisson and

gradient-domain blending [P´ erez et al. 2003; Levin et al. 2004b;

Agarwala et al. 2004], colorization [Levin et al. 2004a] (Fig. 1), and

natural image matting [Levin et al. 2008]. They have also found

widespread application in the solution of computer vision prob-

lems such as surface interpolation, stereo matching, optical flow,

and shape from shading [Terzopoulos 1986; Szeliski 1990; Pent-

land 1994], as well as large-scale finite element and finite difference

modeling [Briggs et al. 2000; Trottenberg et al. 2000].

While the locally adaptive hierarchical basis function technique de-

veloped by Szeliski [Szeliski 2006] showed impressive speedups

over earlier non-adaptive basis functions [Szeliski 1990], it was

never adequately compared to state-of-the art multigrid techniques

such as algebraic multigrid [Briggs et al. 2000; Trottenberg et al.

2000] or to newer techniques such as combinatorial multigrid

[Koutis et al. 2009]. Furthermore, the original technique was re-

stricted to problems defined on four neighbor (N4) grids.

In this paper, we generalize the sparsification method introduced in

[Szeliski 2006] to handle a larger class of grid topologies, and show

how multi-level preconditioners can be enhanced with smoothing to

create hybrid algorithms that accrue the advantages of both adap-

tive basis preconditioning and multigrid relaxation. We also pro-

vide a detailed study of the convergence properties of all of these

algorithms using both condition number analysis and empirical ob-

servations of convergence rates on real-world problems in computer

graphics and computational photography.



全文请下载附件：

菜刀吻电线

无聊时可以刷屏幕 灌水 也可以试试 帖子的标题究竟可以写多长

晃晃

不会吧，太恐怖了

晃晃

百度的叫度娘，网易的叫易娘，新浪内部还在为是叫新娘还是浪娘而争论不休！……不管你们是企鹅的额娘，豆瓣的伴娘，还是华为的伪娘，都要记得，淘宝才是你们的亲娘啊！亲！！

C.R.CAN

很经典，很实用，学习了!

晃晃

我就看看，我不说话

菜刀吻电线

不错哦,顶一下......

晃晃

很经典，很实用，学习了!

晃晃

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

菜刀吻电线

无聊时可以刷屏幕 灌水 也可以试试 帖子的标题究竟可以写多长