TION
/ is primarily
nitially been
ectangles. It
ılly designed
ed stochastic
| a simulated
tion without
r SAR wave-
context: the
cath, modifi-
'nce process.
aightforward
ization. The
AP) criterion
oupling of a
2) with a Re-
MC) sampler
les the stochas-
mplex search
ive function,
(Descombes,
‘lo
vides a series
ability distri-
C that allows
es of varying
295) consists
steps to build
rch space (2)
istribution 7.
running con-
tion Xo.
ary distribu-
ie purpose of
jlicative con-
en ratio. This
d as the nor-
x)
(a) = 45
Algorithm 1: RIMCMC sampler: Metropolis-Hastings-Green
© Initialize the configuration Xo such that T(Xo) # 0
repeat
e Sample i q(-|X«) ; // Select a reversible kernel Qj
e Sample X; e Q;(-|X:) : // Sample the kernei Q;
(Xi) Qi(X4X0 .
oR = XO. xD.
e x — min (1, R) ;
// Green ratio
// Acceptance rate
a3: A
e With probability l 2 E ; Ten e M
until convergence ;
Algorithm 1 requires a set of reversible kernels (Qi) associated
with normalized probabilities q(;|.X;). Each reversible kernel Q;
models a simple stochastic modification of the current configura-
tion, based only on the current configuration X;: ie. Q;(-| X«)
defines a probability distribution over €). For the correctness of
the algorithm 7Q; must have continuity properties and Q; must
be reversible: Q;(X|Y) » 0 = Q;(Y|X) » 0 (Descombes,
2011). We will consider reversible kernels defined using the fol-
lowing elements (Green, 1995):
A probability p;(n'|n) of applying the reversible kernel,
with n, n' such that X, € Q4, X; € Q,.
e A pair of forward and backward views 0 = 1;(X;) € BY,
0 = (Xi) € RM" that provide a probabilized set of con-
current extractions of a fixed length vector representation
0 of the configuration. For instance it may provide one of
many redundant parameterization of the configuration, or a
parameterization of a stochastically chosen element of the
configuration.
A pair of forward and backward distributions $i, à; defined
over respectively RY and RY’. That completes the vectors
0 and 0' to match the dimension of the bijective transform.
o A bijective transform 7; : RN RP where P= M+N =
M’ + N’, such that T7, the backward transform is qp
The kernel contribution to the Green ratio is then:
Qi(Xi|Xe) _ piln’In) di (uw) [ÖT:(0, u)
= (0, u)
QuXX]) pi(nln) 6i (u) (1)
22 Marked Point Process
A (possibly multi-) Marked Point Process (MPP) (van Lieshout,
2000) is a stochastic unordered set of geometric objects of one or
many types (e.g. points, segments, circles, ellipses or rectangles
in 2D, ellipsoids or spheres in 3D). The marked point denomi-
nation arises from the usual decomposition of the object parame-
terization into a point of its embedding space (usually its center)
and a vector of values (the marks) that completes the geometric
parameterization of the object (e.g. orientation, length or radius
parameters), hence the name Marked Point Process.
The l1ibrjmcmc currently focuses on (multi) MPP in both sam-
pling and optimization contexts. When direct sampling of the
MPP is not possible, as when its probability distribution function
(PDF) is not samplable and not normalized, the RIMCMC algo-
rithm 1 may be used to build a Markov Chain which distribution
converges to the desired target stationary distribution.
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
A MPP is defined by a probabilized space (€, 7). If K denotes
the set of possible values of a single object, elements of the con-
figuration space Q = | Joo, K" are unordered sets of a vary-
ing number n of elements in this set Æ. If the process is multi-
marked, ® is then a Cartesian product of such spaces. A sim-
ple probabilization of this configuration space may be given by
a probabilization of the set K of each object type and a discrete
probabilities defined over the natural numbers N for each object
type that samples the number of object n of each type. This prob-
abilization allows a direct sampling of the configuration space 2
by sampling both the object counts, and then each object inde-
pendently. In our context, we will consider more complex prob-
abilizations 7 of the configuration space €), which sampling will
require the more advanced RIMCMC framework.
2.3 Simulated Annealing
Simulated annealing is a physical process inspired by annealing
in metallurgy and is widely used in many communities where
global optimization is of importance (Salamon et al., 2002). At
each step of the algorithm, the stationary distribution is replaced
by a similar stationary distribution that is increasingly more selec-
tive around the maxima. Coupled with the RIMCMC framework,
it enables the global optimization of an extremely large class of
energy functions over complex search spaces of varying dimen-
sions. The goal of the simulated annealing process is to drive
the initial RIMCMC sampler from an initial probability distribu-
tion function given by an energy-agnostic probabilization of the
search space (denoted as the reference process) to a target prob-
ability distribution function which support is exactly the set of
global minima of the energy. To interpolate the PDF between the
initial reference PDF and the final PDF, a Boltzmann distribution
is usually used (see section 3.2.2), parameterized by a tempera-
ture T' which decreases from -4-oo to zero. The stationary RJM-
CMC PDF then converges in theory to a mixture of Dirac masses
at the global minima of the energy. More informally energy in-
creases are allowed which avoid being trapped in a local minima.
But as the temperature T' decreases, the maximum allowable en-
ergy increase decreases. Depending on the temperature decrease
rate and its schedule, and its adequacy to the energy landscape, a
solution close to optimal is found in practice.
3 GENERIC LIBRARY DESIGN
3.1 Generic Programming
Generic Programming is a paradigm that offers compile-time poly-
morphism through templates. It is not as flexible as object-oriented
programming but is much more compiler-friendly as it exposes
types at compile-time rather than at runtime. Therefore the com-
piler is given the opportunity to optimize and produce machine
code of similar performance than a special-purpose code, while
keeping the object-oriented advantage of segregating orthogonal
concepts to modularize the library. This even lets us provide var-
ious implementations of each orthogonal concept, which are de-
noted models of these concepts. A concept may be seen as the
documentation of the requirements and behavior of a particular
template parameter. Concepts have been proposed but not yet
accepted as a C++ extension, which would simplify both the doc-
umentation and the compiling error reporting of generic libraries.
3.2 RJMCMC Concepts
The RIMCMC sampler is implemented in the class sampler, which
can be customized using the template parameters: Density,
Acceptance and a list of Kernels. It offers access to statistics
