Proximal:EfficientImageOptimationUsingProximalAlgorithms资源-CSDN文库

需积分: 9 89 浏览量 2018-01-15 16:18:11 上传评论收藏 25.19MB PDF 举报

标题《Proximal: Efficient Image Optimization Using Proximal Algorithms》表明这篇文章主要讨论了使用邻近算子（proximal algorithms）来实现高效图像优化的技术。文章发表在ACM Transactions on Graphics (TOG)杂志上，这是计算机图形学领域的重要期刊，2016年出版。文章的标题中的“Proximal”一词指的是邻近算子，这是一种数学概念，用于解决凸优化问题。描述中提到，“ProxImaL: Efficient Image Optimization using Proximal Algorithms”是由Felix Heide等人撰写的研究工作，他们来自斯坦福大学、不列颠哥伦比亚大学以及KAUST（沙特阿拉伯国王大学）等机构。这部分内容暗示这项工作是由多机构合作完成的研究成果，具有较强的研究背景和实践价值。此外，描述强调ProxImaL是一种域特定语言，用以方便快速地原型设计各种逆问题（inverse problems）的高效优化程序。逆问题在图像处理领域中指的是从观察到的数据中推断出造成这些数据的成因的过程。比如，从模糊图像推断出清晰图像的过程就属于逆问题的范畴。描述中还特别提到了Poisson分布的散粒噪声（shot noise），这是一种常见的噪声模型，适用于描述光子计数等事件中的随机性。标签为“Image Optimization”，即图像优化，是指利用计算机算法对图像进行调整以改善其视觉效果或满足特定的应用需求。图像优化技术广泛应用于图像处理、计算机视觉、计算摄影学等领域，目的是提高图像的品质或实现特定的图像处理效果。文章的部分内容展示了ProxImaL语言在图像处理中的应用实例，例如退化（deconvolution）处理。退化是图像处理中的一种技术，通常用于从模糊或失真的图像中恢复出高质量的图像。Poisson分布的散粒噪声在这里作为一个典型的噪声模型被考虑在内。另外，内容中还提到了有向无环图（DAG），这是图论中的一个概念，用以表示变量之间的依赖关系。在这里它被用来描述图像处理流程中的步骤和计算依赖。 ProxImaL语言的使用使得实验不同问题形式和算法选择变得更加容易。它使用了邻近算子作为线性和非线性图像形成模型、成本函数、高级图像先验和噪声模型的基础构建块。编译器智能化地选择了最好的方式来翻译问题的特定领域，允许用户轻松原型化不同惩罚函数、高级图像先验以及不同的优化算法。文章中提到的逆问题示例还涉及了图像去噪（denoising）、相位恢复（phase retrieval）等应用。图像去噪是去除图像中噪声的过程，以提高图像质量。相位恢复则是用于恢复波前相位信息的算法，它在光学成像和计算成像中有重要应用。ProxImaL语言支持快速评估不同的图像优化程序，因此在这些以及其他成像应用中都能得到前沿的实验结果。文章指出，随着计算摄影学系统变得越来越多样，不同系统之间共享着基本的图像处理任务，如马赛克处理、退化、去噪、修复、图像融合和对齐等。形式化优化方法最近被证明在许多这类应用中可以达到最先进的质量。遗憾的是，对于不同的问题，可能需要不同的自然图像先验和优化算法的组合，而实现和测试每一种组合目前是一个耗时且容易出错的过程。ProxImaL语言和编译器通过提供一个针对图像优化问题的特定领域语言和编译器，简化了这些问题和算法组合的实验过程。语言的基础是邻近算子，它为各种线性和非线性图像形成模型和成本函数、高级图像先验和噪声模型提供了构建块。文章介绍了一个先进的图像处理框架，即ProxImaL语言和编译器，它们利用邻近算子理论来简化图像优化问题的定义和求解。这种方法在图像处理、计算摄影学以及相关领域具有广泛的应用前景，能够帮助研究者和工程师更高效地实验和实现高效率和高质量的图像处理算法。

资源推荐

资源详情

资源评论

ProxImaL: Efﬁcient Image Optimization using Proximal Algorithms

Felix Heide

1,2

Steven Diamond

Matthias Nießner

Jonathan Ragan-Kelley

Wolfgang Heidrich

3,2

Gordon Wetzstein

Stanford University

University of British Columbia

KAUST

Burst Denoising

Poisson Deconvolution

Phase Retrieval

ProxImaL Code and DAG

data_term

grad_sparsity

objective

Variable

(300, 300, 3)

poisson_norm

(

conv

(x, psf) - input )

norm1

(

grad

(x) )

= data_term + grad_sparsity +

nonneg

(x)

Problem

( objective )

p.solve()

Figure 1:

As a domain-speciﬁc language, ProxImaL makes it easy to prototype a range of inverse problems in imaging. For example, we show

ProxImaL code for deconvolution in the presence of Poisson-distributed shot noise and the corresponding directed acyclic graph (DAG, left)

as well as the results generated by the compiled optimization algorithm (center left). The ProxImaL language makes it easy to prototype

highly-efﬁcient optimization routines for problems as diverse as denoising a stack of images (center right), or even nonlinear problems such

as phase retrieval (right). For any of these applications, ProxImaL allows for different penalty functions, advanced image priors, and also

different optimization algorithms to be rapidly evaluated. We demonstrate state-of-the-art results for these and other imaging applications.

Abstract

Computational photography systems are becoming increasingly

diverse, while computational resources—for example on mobile

platforms—are rapidly increasing. As diverse as these camera sys-

tems may be, slightly different variants of the underlying image

processing tasks, such as demosaicking, deconvolution, denoising,

inpainting, image fusion, and alignment, are shared between all of

these systems. Formal optimization methods have recently been

demonstrated to achieve state-of-the-art quality for many of these

applications. Unfortunately, different combinations of natural image

priors and optimization algorithms may be optimal for different prob-

lems, and implementing and testing each combination is currently

a time-consuming and error-prone process. ProxImaL is a domain-

speciﬁc language and compiler for image optimization problems

that makes it easy to experiment with different problem formulations

and algorithm choices. The language uses proximal operators as

the fundamental building blocks of a variety of linear and nonlinear

image formation models and cost functions, advanced image pri-

ors, and noise models. The compiler intelligently chooses the best

way to translate a problem formulation and choice of optimization

algorithm into an efﬁcient solver implementation. In applications

to the image processing pipeline, deconvolution in the presence of

Poisson-distributed shot noise, and burst denoising, we show that

a few lines of ProxImaL code can generate highly efﬁcient solvers

that achieve state-of-the-art results. We also show applications to

the nonlinear and nonconvex problem of phase retrieval.

Keywords:

computational photography, digital image processing,

optimization

Concepts: •Computing methodologies →

Computational photo-

graphy; Regularization;

•Mathematics of computing →

Continu-

ous optimization; Solvers;

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are not

made or distributed for proﬁt or commercial advantage and that copies bear

this notice and the full citation on the ﬁrst page. Copyrights for components

of this work owned by others than the author(s) must be honored. Abstracting

1 Introduction

Digital image processing is a research area with a wide variety of ap-

plications in computational photography, computer vision, robotics,

scientiﬁc imaging, remote sensing, microscopy, and computer graph-

ics. Traditionally, image processing algorithms have been tailored

independently to each of these applications, with few techniques

that generalize across ﬁelds. Researchers have recognized that all

these applications share the fundamental task of recovering informa-

tion from blurry, noisy, saturated, sparsely or indirectly sampled, or

otherwise corrupted measurements. In particular, the information re-

covery task can be formulated as an optimization problem. Methods

that approach image processing as solving an optimization problem

have achieved state-of-the-art results in many classical applications,

for example the demosaicking, deconvolution, and inpainting tasks

of the image processing pipeline [Heide et al. 2014].

Optimization-based image processing generalizes across application

areas, and thus, in theory, makes it easy to develop image processing

techniques for new domains. In practice, however, developing image

optimization methods can be difﬁcult, because there are many ways

to frame an image processing task as an optimization problem, and

it is virtually impossible to predict which framing will yield the best

results. This requires researchers to experiment with a wide variety

of optimization approaches to see which works best for a given task.

For instance, consider the classic problem of deconvolution: we are

given measurements

that approximately satisfy

b = Dx

, where

is a linear operator representing convolution with a known kernel

and

is an unknown image. Our goal is to recover

given

. The

optimization-based approach to deconvolution is to say that

is the

with credit is permitted. To copy otherwise, or republish, to post on servers

or to redistribute to lists, requires prior speciﬁc permission and/or a fee.

Request permissions from permissions@acm.org.

2016 Copyright held by

the owner/author(s). Publication rights licensed to ACM.

SIGGRAPH ’16 Technical Paper,, July 24 - 28, 2016, Anaheim, CA,

ISBN: 978-1-4503-4279-7/16/07

DOI: http://dx.doi.org/10.1145/2897824.2925875

solution to the optimization problem:

minimize f(Dx − b) + r(x),

(1)

where

is an error metric, and

is a penalty function that expresses

prior knowledge about the image x.

There are many reasonable choices for

and

. For instance, we

might deﬁne

as a sum-of-squares error, a Huber loss, or a Poisson

penalty. The penalty function

could be a constraint on the range of

the values of

, a sparsity-inducing penalty such as total-variation, a

non-local patch prior as in the BM3D-based reconstruction shown

in [Danielyan et al. 2012], or a combination of all these penalties.

Once we have chosen f and r, we must choose an algorithm to use

for solving the optimization problem. Dozens of different optimiza-

tion algorithms have been applied to image optimization problems,

such as the alternating direction method of multipliers (ADMM)

[Boyd et al

2011], the primal-dual algorithm by Chambolle and

Pock [2011], and half-quadratic splitting [Geman and Yang 1995].

Moreover, for each algorithm there may be many ways to translate

Problem

(1)

into that algorithm’s standard form. The only way to

know which algorithm and translation into standard form works best

for a problem is to try all of them.

Finding an effective image optimization method thus requires ex-

ploring a large space of problem formulations, algorithms, and trans-

lations between standard forms. Currently, researchers must develop

a new solver implementation for each point they explore in the space,

which is a time-consuming and error-prone process. Developing

implementations is particularly challenging for image optimization

problems since these problems typically involve millions of variables

and can only be solved efﬁciently by exploiting problem structure.

In this paper, we address these challenges by introducing ProxImaL,

a domain-speciﬁc language (DSL) for image optimization. The

ProxImaL language allows users to describe image optimization

problems in a few lines of code using an intuitive syntax that follows

the math. Users write their problem using a ﬁxed set of mathematical

functions, whose structure can be exploited to generate an efﬁcient

solver. Most functions that occur in image optimization problems

are included in the language, and it is easy to add support for more.

Compositions of functions are limited by a set of simple rules that

ensure the problems constructed by the user match our standard

mathematical representation.

The ProxImaL compiler takes the user’s problem description and

choice of algorithm and automatically generates a solver imple-

mentation. The compiler considers a wide range of possible solver

implementations and selects one based on expert knowledge about

how to best formulate problems for the chosen solver algorithm. The

user can also easily override the compiler’s default choice to try out

more implementations. The solver implementations generated by

the compiler are highly efﬁcient because we created optimized code

for the core mathematical operations using Halide [Ragan-Kelley

et al. 2013].

We demonstrate the utility of ProxImaL through applications to

the image processing pipeline, burst photography and denoising,

deconvolution, and phase retrieval. In many cases a few lines of

ProxImaL code and the default solver implementation generated by

the ProxImaL compiler achieves state-of-the-art results, often with a

runtime under ten seconds.

We make the following contributions in this paper:

•

We developed a simple language and mathematical representa-

tion for image optimization problems that captures the problem

structure needed to generate an efﬁcient solver.

•

We built a compiler that takes the user’s problem description

and choice of solver algorithm and automatically generates an

efﬁcient solver, intelligently choosing from the many transla-

tions possible.

•

We show that our framework can achieve state-of-the-art res-

ults on a variety of image optimization problems while also

producing highly efﬁcient solver implementations.

2 Related Work

Languages for Graphics and Image Processing

Domain-

speciﬁc languages for graphics and rendering have successfully

made the transition from research to industry standard [Foley and

Hanrahan 2011]. Today, general-purpose languages for GPU pro-

gramming, such as CUDA, are popular for many applications beyond

graphics. OpenCL extended this concept to heterogeneous comput-

ing platforms. Domain-speciﬁcity can be exploited to accelerate

the execution of common tasks in a particular domain, for example

in image processing [Ragan-Kelley et al

2013], physical simula-

tion [Bernstein et al

2015], or multi-material 3D printing [Vidimice

et al

2013]. Most of these languages and systems focus on ﬁnding a

domain-speciﬁc tradeoff between intuitive use and high-performance

execution. ProxImaL follows this strategy but we build on formal

optimization methods to develop a language and compiler for image

optimization.

Optimization for Image Processing

Over the past years, numer-

ical optimization has become a standard tool for solving a number

of classical restoration and reconstruction problems in computa-

tional photography. Examples include blind [Fergus et al

2006]

and non-blind [Krishnan and Fergus 2009; Joshi et al

2009] de-

convolution, image denoising [Zoran and Weiss 2011], and inpaint-

ing [Bertalmio et al

2000]. Optimization has been successfully

applied to image editing problems such as tonemapping [Fattal et al

2002], Poisson-blending [Levin et al

2004b] and colorization [Levin

et al

2004a]. Very efﬁcient solvers have been developed for most

of these problems [Krishnan and Szeliski 2011; Schmidt and Roth

2014]. Optimization techniques are also becoming increasingly

popular solutions for scientiﬁc imaging problems such as x-ray

tomography [Sidky and Pan 2008] and phase retrieval [Tian and

Waller 2015]. Recently, it was shown that a large subset of low-level

image processing problems can be solved through a single proximal

algorithm framework [Heide et al. 2014].

Optimization and Optimization Languages

The literature on

algorithms for solving image optimization problems is extensive.

A particularly fruitful line of research has focused on solving con-

vex optimization problems using operator splitting methods and

proximal algorithms [Parikh and Boyd 2013]. Prominent examples

of such methods include the proximal point algorithm [Rockafel-

lar 1976], forward-backward splitting [Bruck 1975], the Pock-

Chambolle algorithm [Chambolle and Pock 2011; Pock et al

2009],

the split Bregman method [Goldstein and Osher 2009], ISTA and

FISTA [Beck and Teboulle 2009], the alternating direction method

of multipliers [Boyd et al

2011], PDHG [Esser et al

2010], and

half-quadratic splitting [Geman and Yang 1995]. Recent work has

applied these methods to nonconvex optimization problems and

found conditions that guarantee convergence (though not necessarily

to the global optimum); see, e.g., [Attouch et al

2011; M

ollenhoff

et al. 2015; Li and Pong 2015].

DSLs for optimization have a long history, going back to GAMS

[Brooke et al

1988] in the 1970s, and including DSLs specialized for

convex optimization, such as CVX [Grant and Boyd 2014], YALMIP

[Lofberg 2004], CVXPY [Diamond and Boyd 2016b], and Convex.jl

[Udell et al

2014]. These approaches reliably solve modest size

problems, with on the order of

10, 000

s of variables, but for image

optimization problems with millions of variables these solvers be-

come infeasible due to their memory and computational cost. There

have been several different approaches towards making an optim-

ization DSL or framework that can handle large problems such as

occur in image optimization. The approach in [Diamond and Boyd

2015] extends CVXPY to recognize and exploit fast linear transforms,

such as convolution and the discrete Fourier transform. The Epsilon

framework takes advantage of fast proximal operators for individual

functions, transforming problems so they can be efficiently solved by

a variant of ADMM [Wytock et al

2015]. The TFOCS framework

makes it easy to apply a variety of proximal and first order algorithms

to optimization problems, and accommodates fast linear transforms

[Becker et al

2011]. None of these systems can compete with ex-

isting specialized solvers for individual image processing problems,

however, and they are also limited to convex problems.

3 Representing Image Optimization Problems

We model an image optimization problem as a sum of penalties

on linear transforms K

x with x ∈ R

being the unknown:

argmin

i=1

x) with K =













, (2)

where here

K ∈ R

m×n

is one large matrix that is composed of

stacked linear operators

, . . . , K

. The linear operator

∈

×n

selects a subset of

rows of

. This subset of rows is

then the input for the penalty functions f

: R

→ R.

Image optimization problems generally contain

• variables representing the image(s) to be reconstructed,

•

a forward model of image formation in terms of linear operators,

•

a penalty based on the difference of the results of this forward

model from measured data,

• and priors and constraints on the the variables.

For example, consider a slightly more complex version of the decon-

volution problem

(1)

where the convolved image

is subsampled

by a known demosaicking pattern, which we represent with the lin-

ear operator

. We formulate our problem using a sum-of-squares

error metric, f(x) = kMDx − bk

, and the penalty function:

r(x) = µk∇xk

+ (1 − µ)k∇xk

+ I

[0,∞)

(x),

where µ ∈ [0, 1], ∇ is the gradient operator, and:

[0,∞)

(x) =

(

0, if x ≥ 0

∞, otherwise.

The penalty function encodes the priors that many gradients are

zero and the pixel values are nonnegative. Problem

(3)

shows the

full optimization problem and how we represent it in the form of

Problem (2).

opt

= argmin

kMDx − bk

+ r(x) (3)

r(x) = µk∇xk

+ (1 − µ)k∇xk

+ I

[0,∞)

(x) (4)

model:

(v) = kv − bk

, K

= MD

(v) = µkvk

, K

= ∇

(v) = (1 − µ)kvk

, K

= ∇

(v) = I

[0,∞)

(v), K

= I

(5)

Note that there are other ways to represent the problem in our stand-

ard form. For example, we could use:

(v) = kMv −bk

, K

= D.

A key insight is that the choice of representation can drastically

affect the performance of the solver algorithms. We take advantage

of this fact and provide strategies to ﬁnd an optimal reformulation.

The only assumption we make about the penalty functions

, . . . , f

is that they provide a black box for evaluating the function’s proximal

operator. The proximal operator of a function f is deﬁned as:

prox

τf

(v) = argmin



f(x) +

2τ

kx − v k



where

τ > 0

and

v ∈ R

[Parikh and Boyd 2013]. The proximal

operator optimizes over the function in isolation, but incorporates

a quadratic term that can be used to link the optimization with

a broader algorithm. Many algorithms can be carried out using

proximal operators that cannot be carried out using the traditional

approach of interacting with functions by computing their gradients

and Hessians [Parikh and Boyd 2013].

Similarly, the only assumption we make about each linear operator

is that it provides a black box for evaluating the forward operator

x → K

and the adjoint operator

z → K

. This is a useful

abstraction because many linear operators that arise in optimization

problems from image processing are fast transforms, i.e., they have

methods for evaluating the forward and adjoint operator that are

more efﬁcient than standard multiplication by the operator represen-

ted as a dense or sparse matrix. Common fast transforms in image

processing include the discrete Fourier transform (DFT), convolu-

tion, and wavelet transforms; see [Diamond and Boyd 2016a] for

many more examples.

For simplicity, we assume that all linear operators are maps from

a multidimensional real space

×···×n

to another multidimen-

sional real space

×···×m

. Complex-valued linear operators

such as the DFT are represented as real valued operators using the

standard embedding of a complex vector in

×···×n

as a real

vector in R

×···×n

We call algorithms that solve Problem

(2)

using only these black

boxes proximal, matrix-free solvers. All solver algorithms in Prox-

ImaL are proximal, matrix-free solvers. ProxImaL currently sup-

ports the Pock-Chambolle algorithm, ADMM, linearized ADMM,

and half-quadratic splitting. See the supplement for detailed deriva-

tions showing that all of these methods ﬁt into our framework from

(2)

. These algorithms can solve Problem

(2)

when the functions

, . . . , f

are convex.

Much state-of-the-art image optimization makes use of nonconvex

penalty functions; however, in applications ranging from denoising

and deconvolution to burst reconstruction and registration. Patch-

based approaches and hard thresholding in particular have been very

successful for image reconstruction problems [Krishnan and Fergus

2009; Danielyan et al. 2012; Heide et al. 2014].

Surprisingly, the same proximal, matrix-free solvers that work for

convex problems yield good results for certain problems that in-

clude nonconvex penalty functions [Danielyan et al

2012; Heide

et al

2014; Hallac et al

2015]. There is often no guarantee that

the algorithms will converge (see conditions in [Ochs et al

2014]

for exceptions). Furthermore, there is no guarantee that they ﬁnd

the optimal

, but empirically for many problems with nonconvex

penalties the algorithms do produce good results in a reasonable

number of iterations.

剩余14页未读，继续阅读

评论收藏

内容反馈

起不了一点

粉丝: 0
资源: 2

Proximal: Efficient Image Optimation Using Proximal Algorithms

最新资源

Proximal: Efficient Image Optimation Using Proximal Algorithms

Proximal Algorithms

Proximal Algorithm

proximal:近端幼儿学习管理系统

二阶响应matlab代码-sparse-ReIR-proximal:该存储库提供与在WASPAA2017研讨会上发表的论文“通过二阶锥规划快速

Proximal-gradient-total-least-squares-master_重构算法_最小二乘_proximal_

压缩感知proximal Gradient算法实现

A recursive predictive risk estimate for proximal algorithms

基于python的强化学习算法Proximal_Policy_Optimization设计与实现

MATLAB代码：n阶机械臂单、多智能体控制 关键词：n阶机械臂单 多智能体 单智能体 参考文档： 1.Proximal P

proximal, 邻近运算符的样例实现.zip

apg.rar_ Nuclear Norm_APG_APG算法_nuclear norm_proximal

Proximal gradient method

ProximalAlgorithms_StephenBoyd(20181116125346)

A Proximal Method for Solving Vector Variational Inequalities

ProximalOperators.jl：Julia中用于非平滑优化的近似运算符

好用的去噪代码matlab-Cauchy-Proximal-Splitting-CPS-Algorithm:基于非凸柯西罚分的收敛保证近端分裂

论文研究-Proximal SVM在脑功能分类中的应用研究.pdf

Proximal Policy Optimization的实现细节的源代码

PPO算法，即Proximal Policy Optimization（近端策略优化）.pdf

Proximal and syndetical properties in nonautonomous discrete systems

A Predual Proximal Point Algorithm Solving a NonNegative Basis

PPO（Proximal Policy Optimization，近端策略优化）算法

深度强化学习 - Proximal Policy Optimization (PPO)

正交采样Matlab代码-Proximal.jl:近端算法的Parikh和Boyd代码的翻译

SVM.rar_Proximal SVM_SVM_svm.dat_svm算法实现

文有为_A Fast Proximal Gradient Algorithm For Single Particle Recon

最新资源

MATLAB代码：n阶机械臂单、多智能体控制关键词：n阶机械臂单多智能体单智能体参考文档： 1.Proximal P