In: Paparoditis N., Pierrot-Deseilligny M.. Mallet C.. Tournaire O. (Eds). 1APRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3. 2010 
knowledge of network region geometry. We will further factor 
ize the likelihood term into P(/r|/?, K) and P(In\R, K), that is 
into separate models for the image In in the network region R 
and the image In in the background R. The phase field HOAC 
model of directed networks then corresponds to P(R\K), while 
our image models correspond to P(Ir\R,K) and P(//j|J?, K). 
In practice, we will deal with negative log probabilities, i.e. a 
total energy E(R.I) = -\nP(R\I, K) that is the sum of a 
likelihood term E\(I,R) = — In P(I\R, K) and a prior term 
Ep(R) = — In P(/?|A").) We will then extract a maximum a 
posteriori (MAP) estimate for R by minimizing E(R, I) over R. 
This will be done using gradient descent. 
In section 1.1, we justify our choice of shape modelling frame 
work by surveying the alternatives. In section 2, we recall briefly 
the theoretical background of the models used: sections 2.1 and 2.2 
recall the undirected and directed phase field HOAC models re 
spectively. In section 3, we describe the test results obtained in 
applying the algorithm to VHR images: we compare ML seg 
mentations using different image models, and then test our new 
algorithm including the full model. We conclude in section 4. 
1.1 Previous work 
The models used in most previous work on region segmentation 
do not incorporate any nontrivial knowledge about region geom 
etry. For example, standard active contours, introduced by (Kass 
et al., 1988), further refined by many authors, and applied in a 
huge number of other papers, contain only the prior knowledge 
that the region boundary should be smooth. As we have empha 
sized, this degree of prior knowledge is almost never enough for 
the automatic solution of segmentation problems on real images, 
whatever the domain. As a result, recent work has developed 
models incorporating more sophisticated knowledge of region ge 
ometry. Most of this work models an ensemble of regions as per 
turbations of one or more reference regions, for example (Cre- 
mers et al., 2003. Rousson and Paragios, 2002, Srivastava et al., 
2003, Foulonneau et al., 2003). This is an intuitive and useful 
approach, but it is inappropriate when the region sought can have 
arbitrary topology, since such an ensemble of regions cannot be 
described as perturbations around a finite number of reference re 
gions. Since networks can have arbitrary topology (i.e. several 
connected components, each of which can have loops), the above 
work is not applicable to the network segmentation problem. 
To model regions with potentially arbitrary topology, higher-order 
active contours (HOACs) were introduced by (Rochery et al., 
2006). The HOAC prior energy defined by (Rochery et al., 2006) 
was used to model undirected network regions and to extract road 
networks from medium resolution optical images. The contour 
representation used by (Rochery et al., 2(X)6) suffers from many 
drawbacks, however. To overcome these drawbacks, (Rochery et 
al., 2005) reformulated HOACs as nonlocal ‘phase field’ mod 
els. This formulation facilitates model analysis and implemen 
tation, allows a ‘neutral’ initialization and complete topological 
freedom, and results in reduced execution times, sometimes by 
an order of magnitude. Phase field HOAC models of undirected 
networks have proved their efficiency for road network segmen 
tation from medium resolution images of rural or semi-rural ar 
eas (Rochery et al., 2005), and high resolution images of urban 
areas (Peng et al., 2010), but the models are not well adapted to 
non-urban road network segmentation from high resolution im 
ages, nor to hydrographic network segmentation. The main prob 
lem is that the branch width in these models is very tightly con 
strained. This works well for medium resolution where the range 
of visible widths is not large, but at high resolution and in hy 
drographic networks, the range of widths is much greater. Naive 
attempts to allow a greater range of widths have the unfortunate 
side effect of allowing width to vary rapidly along one branch: 
the branch sides lose their ‘rigidity’. The second difficulty is that 
the early model in (El Ghoul et al., 2009a) had problems closing 
large gaps in the network. The work of (Peng et al., 2010) solves 
these problems for urban road networks, but the solution involves 
favouring long straight branches, which is again not well adapted 
to non-urban road and hydrographic networks. 
To overcome these difficulties, (El Ghoul et al., 2009b) intro 
duced a phase field HOAC model for directed networks, in order 
to capture some of their distinctive geometric properties. Because 
these geometric properties are linked to the fact that directed net 
works carry a conserved flow, the model contains, in addition to 
the phase field specifying the network region, a vector field rep 
resenting a ‘flow’ in the network. The magnitude of the field 
is approximately constant, and the flow is approximately con 
served. As a result, branch width tends to change slowly and 
branches tend not to end, as both these would change the flow. 
At junctions, there is approximate ‘conservation of width’ so that 
incoming flow be approximately equal to outgoing flow. How 
ever, the model was only tested on a synthetic image showing the 
shape of a river, albeit with success. 
Other attempts to solve the hydrographic network segmentation 
problem include the work of (Dillabaugh et al., 2002). This work 
uses an interesting multiscale approach, but relies on user input to 
specify network endpoints, and is limited in the network topolo 
gies that it can find. The work of (Lacoste et al., 2004) models the 
network region using a marked point process of polylines. This 
model works well when the network has constant width over sig 
nificant distances, since each polyline has a fixed width. (Lacoste 
et al., 2005) uses an initial segmentation by Markov random field 
as a seed from which to build a hierarchical model of the network 
using a marked point process. This works well when the image 
is sufficiently clean for the MRF segmentation to capture most 
of the network, and when the network has a tree structure. For 
a review of the large number of techniques that have been devel 
oped for road network segmentation, see (Mena, 2003). How 
ever, none of these solve the problem of network segmentation 
from high resolution images in a quasi-automatic way. 
2 PRIOR MODEL E P 
In this section, we present the prior model Ep. We begin by re 
calling the simplest phase field HOAC model of an undirected 
network (Rochery et al., 2005), since this is the base on which 
the model of directed networks is built. 
2.1 Undirected network model 
A phase field 0 is a real-valued function on the image domain 
Q. A phase field determines a region by the thresholding map 
C= {x € O : (f>(x) > z} where z is a given threshold. The 
basic phase field energy is 
£o(0) = f d 2 x^d^-dcp 
“ +>(*-£)♦■(*-£)}• <■> 
If (1) is minimized subject to £*(</>) = t.e. for a fixed re 
gion, then away from the boundary, the minimizing function (pn 
assumes the value 1 inside, and —1 outside R thanks to the ul 
tralocal terms. To guarantee two energy minima (at —1 and 1),