International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia
LIBRJMCMC:
AN OPEN-SOURCE GENERIC C++ LIBRARY FOR STOCHASTIC OPTIMIZATION
Mathieu Brédif? and Olivier Tournaire??
!IGN, MATIS, 73 avenue de Paris, 94160 Saint-Mandé, France ; Université Paris-Est
?CSTB, 84 avenue Jean Jaurés, 77447 Marne la Vallée, France
?Imagine/LIGM, Université Paris-Est, 6 avenue Blaise Pascal, 77455 Marne la Vallée, France
Commission III/3
KEY WORDS: Stochastic Optimization, RJ-MCMC, Simulated Annealing, Generic C++ Library, Open-Source
ABSTRACT:
The libr jmomc is an open source C++ library that solves optimization problems using a stochastic framework. The library is primarily
intended for but not limited to research purposes in computer vision, photogrammetry and remote sensing, as it has initially been
developed in the context of extracting building footprints from digital elevation models using a marked point process of rectangles. It
has been designed to be both highly modular and extensible, and have computational times comparable to a code specifically designed
for a particular application, thanks to the powerful paradigms of metaprogramming and generic programming. The proposed stochastic
optimization is built on the coupling of a stochastic Reversible-Jump Markov Chain Monte Carlo (RIMCMC) sampler and a simulated
annealing relaxation. This framework allows, with theoretical guarantees, the optimization of an unrestricted objective function without
requiring any initial solution.
The modularity of our library allows the processing of any kind of input data, whether they are 1D signals (e.g. LiDAR or SAR wave-
forms), 2D images, 3D point clouds... The library user has just to define a few modules describing its domain specific context: the
encoding of a configuration (e.g. its object type in a marked point process context), reversible jump kernels (e.g. birth, death, modifi-
cations...) the optimized energies (e.g. data and regularization terms) and the probabilized search space given by the reference process.
Similar to this extensibility in the application domain, concepts are clearly and orthogonally separated such that it is straightforward
to customize the convergence test, the temperature schedule, or to add visitors enabling visual feedback during the optimization. The
library offers dedicated modules for marked point processes, allowing the user to optimize a Maximum A Posteriori (MAP) criterion
with an image data term energy on a marked point process of rectangles.
1 INTRODUCTION
Optimization of an objective function over a given search space
is a very important and wide research topic. Optimization prob-
lems come however in very different flavors: the objective func-
tion may or may not exhibit nice properties like convexity or the
search space may be a simple compact of IR", a (possibly infinite)
set of discrete values, or even a combination of both: a (possibly
infinite) union of spaces embeddable in IR". This article proposes
an implementation of a stochastic optimization framework for op-
timizing arbitrary objective functions over the latter and more
complex search spaces. Given the difficulty of these problems
that mix combinatorial and variational aspects and the generic-
ity of the proposed library, it does not provide a one-size-fits-all
solution. Instead, it implements a theoretically sound stochastic
framework that is easily and highly customizable for rapid proto-
typing and tuning of the optimization process. The 1ibr jmenc is
a generic C++ library (Abrahams and Gurtovoy, 2004) designed
to be both heavily optimized and highly modular.
In this paper, we first briefly remind the mathematical founda-
tions involved in the chosen stochastic framework (section 2). We
then present our implementation choices to build a computation-
ally efficient and generic library (section 3). Before concluding,
we demonstrate sample uses of the library, including the discus-
sion of the implementation of the building footprint extraction
from satellite imagery proposed in (Tournaire et al., 2010) (sec-
tion 4).
2 STOCHASTIC OPTIMIZATION
librjmcmc 's optimization is performed using a coupling of a
simulated annealing relaxation (Salamon et al., 2002) with a Re-
versible Jump Markov Chain Monte Carlo (RIMCMC) sampler
(Hastings, 1970; Green, 1995). This framework enables the stochas-
tic minimization of a large class of energies over complex search
spaces, only requiring the evaluation of the objective function,
rather than e.g. derivatives or convexity properties (Descombes,
2011).
2.1 Reversible-Jump Markov Chain Monte Carlo
A Markov Chain Monte Carlo (MCMC) sampler provides a series
of samples according to a given unnormalized probability distri-
bution function. RIMCMC is an extension of MCMC that allows
the configuration space €) to be the union of spaces of varying
dimensions () — LI, Q4. Algorithm 1 (Green, 1995) consists
in repeating stochastic proposition and acceptance steps to build
a series of configurations (i.e. elements of the search space €!)
which stationary distribution is the desired target distribution m.
Note that after a sufficient number of iterations, the running con-
figuration X, is independent of the initial configuration Xo.
A well-known property of interest is that the stationary distribu-
tion 7 is not only never sampled directly (as it is the purpose of
the algorithm) but also only evaluated up to a multiplicative con-
stant, as it only appear in the term sn of the Green ratio. This
thus enables the sampling of a probability 7 defined as the nor-
malization of a non-negative integrable function f: w(x) = fe).
"- @ |! "nl
s ak mt ^ uat cR
