bijective dif- 
nsions. They 
a kernel pro- 
ind abs -jacobian 
rd kernel, the 
. 
X EB 
only used to 
ext where the 
composed as 
bjects binary 
e thus tightly 
uration is a 
ffers vector_- 
ion models. 
he latter em- 
and non-zero 
s. 
ble to provide 
Marked Point 
pes) are sup- 
of objects as 
1 this context, 
ts have them 
ig function so 
stic. 
'orts energies 
Ja) energies: 
y) Q) 
2010) 
inary) 
»ctor flow 
section 
ergy models 
rea(xNy) by 
inary_energy(), 
lary energy 
ibution is de- 
ampler, which 
r each object 
niform object 
les. 
3.34 Accelerator Concept When queried with a configu- 
ration c and an object x, an accelerator provides a subset of the 
set of objects in c that interact with x (i.e. that have a non-zero 
binary energy with it). If the binary energy becomes null or neg- 
ligible when objects are further apart than a given threshold, an 
accelerator may only report objects that intersect a suitable ball 
centered on the query object x. Further releases of the library 
may include accelerators based for instance on quad-trees, uni- 
form grids or Kd-trees. However, the only model of this concept 
is currently the trivial_accelerator that returns the whole range 
of objects of the query configuration. 
335 MPP Kernels For efficiency, the energy evolution AU 
of the modifications proposed by the kernels must be easy to com- 
pute. Thus MPP Kernels usually only delete and/or insert a small 
number of objects. A Modification class thus keeps a vector 
of iterators to the death-proposed objects and a vector of birth- 
proposed new objects. The simplest MPP kernels that are suffi- 
cient for convergence are provided: RIMCMC:uniform birth kernel 
and its reverse kernel RJMCMC::uniform death kernel. 
3.4 Simulated Annealing Concepts 
The main simulated annealing function is the following free func- 
tion that performs the optimization loop until the convergence 
EndTest succeeds, advancing the temperature Schedule and calling 
the visitor functor at each iteration: 
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 
3.4.2 EndTest concept Models of the EndTest concept pro- 
vide a simple predicate that informs the simulated annealing frame- 
work that the process has converged or whatever reason requiring 
to stop the simulated annealing iterations, such as a user-issued 
cancellation. The only requirements of this concept is to provide 
the following member function: 
  
  
template«tvpename Configuration, typename Sampler 
bool operator()(const Configuration& configuration, 
const Sampler& sampler, double temperature); 
  
  
  
template< class Configuration, class Sampler, 
class Schedule, class EndTest, ciass Visitor > 
void simulated annealing::optimize( 
Configuration& config, Sampler& sampler, 
Schedule& schedule, EndTest& end test, Visitor& vis) 
double t = «schedule; 
visitor.begin(config,sampler,t); 
for(; lend test(config,sampler,t); t - x(++schedule )) 
sampler(config,t y 
visitor.visit(config,sampler,t); 
} 
visitor.end(config,sampler,t); 
Provided models are max_iteration_end_test that fails after a given 
number of iterations and delta_energy_end_test that fails after a 
given number of iterations without energy change. They may be 
combined using the composite end test model. 
Available EndTest Models 
max iteration end test i 2 na 
delta_energy_end_test Vi >t—-7, AU; =0 
composite_end_test< Lo, EA, pom or( Eo(), Ei () en) 
  
  
3.4.8 Visitorconcept Visitorsarehighly customizable ob- 
jects passed to the simulated annealing process. They may be 
used to visualize or to gather statistics on the current state of 
the optimization. Available models offer console (figure 1) or 
GUI (based on Gilviewer and WxWidgets, figure 2) feedback, or 
shapefile saving of the current configuration. They may be com- 
bined using a composite_visitor. This extensibility mechanism 
offer the possibility to compile the same RIMCMC code with 
a GUI to build intuition and monitor the running algorithm and 
without for batch timing purposes. 
  
  
  
34.1 Schedule concept Models of the Schedule concept 
are responsible for providing the evolution of the temperature 
throughout the simulated annealing process. The Schedule con- 
cept is a refinement of the Inputlicrator concept of the C++ Stan- 
dard Template Library. 
Available Schedule Models 
geometric_schedule Tr = at To 
  
  
; 3 em To 
logarithmic schedule n = logo (20 
inverse linear schedule + = #— +tAT 
step schedule« T" d Ti; 
Whereas the 1ogarithmic schedule is the one that ensures conver- 
gence (Descombes, 2011), the geonetric schedule is usually used 
instead in practice for computational efficiency. The step_schedule 
wraps another schedule to offer constant temperature periods of 
T iterations, enabling statistics computation through a visitor. 
  
The evaluation of a suitable initial temperature is not trivial. On 
the one hand, too high a temperature will unnecessarily prolong 
the initial phase of the simulated annealing where the sampling is 
unbiased by the target distribution. On the other hand, too low a 
temperature prevents the exploration of the whole configuration 
space and results in the convergence to a local minimum only. 
(Salamon et al., 2002) suggests considering an estimation of the 
variance of the energy of configurations sampled according to the 
reference process to estimate the initial temperature. The corre- 
sponding saiamon initial schedule Tp estimation function is pro- 
vided, which performs well in the absence of hardcore energy 
terms. 
  
template«typename Configuration, typename Sampler 
void begin(const Configuration& configuration, 
const Sampler& sampler, double temperature); 
   
template«typename Configuration, typéname Sampler 
void visit(const Configuration& configuration, 
const Sampler& sampler, double temperature); 
template«typename Configuration, iypename Sampler> 
  
  
255 
void end(const Configuration& configuration, 
const Sampler& sampler, double temperature); 
4 SAMPLES 
4.1 Circle packing 
This section details a simple example use of the 1ibrjmcmc li- 
brary. The goal is to find a set of circles that minimizes a simple 
objective function. Each circle center lie in the unit square and 
its radius is constrained in an interval [rmin; Tmaz]. Notice that 
the cardinality of set itself is unknown. The minimized function 
awards a negative constant value for each circle and penalizes ev- 
ery pair of overlapping circles by its intersection area. Basically, 
it tries to pack as many circles as possible into the unit square 
while minimizing their overlap. First, one needs to define the ob- 
ject type of the MPP, with all its geometric methods. Then, the 
object container is defined as well as an objective function as the 
sum of a unary term for each object and a binary term for each 
pair of objects. The set of objects is then probabilized using a 
Poisson reference process and uniform birth. A basic birth and 
death RIMCMC sampler is then defined to enable the sampling 
of the MPP relative to the Poisson reference process, modulated 
by the score of the objective function and a temperature parame- 
ter. Then header files relative to the optimization of the objective 
function are included. A sufficiently slow temperature decrease 
morphs the probability distribution function from the one of the 
reference process to a combination of Dirac masses at the global 
mimima of the objective function, thus achieving its minimiza- 
tion. A geometric scheduling of the temperature decrease is sub- 
optimal but is more practical and thus more commonly used.