s and 
nities: 
rrela- 
1 this 
"mity 
(3) 
(4) 
g the 
gure 
hed. 
oved 
very 
ities 
r re- 
odel 
erial 
1age 
that 
S) 
rtial 
(or 
Auclair Fortier, Marie-Flavie 
  
The external energy represents the image force (f (z, y)) attracting the snake. In our case, this force is the bright-line 
plausibility (f(2,y) = —Amaa (2,9). 
Equation 5 is an evolution problem (snake position evolves over time). The solution to this minimization problem is the 
simplified Euler evolution equation: 
Ov(s,t) 
au 
ot 
C OE. (v(s,t)) 
Ov ? 
where v" is the fourth derivative in s. The parameter ^y represents the viscosity of the curve. The higher the viscosity, 
the greater the inertia and the slower the evolution of the curve. 
— av" (s, t) -- Bv" (s, t) (6) 
Hn 
The discrete version of Equation 6 is obtained by setting a discrete version of the parametric curve at moment t: V, — 
{vit = (24i Vit), $ = 1..n}, where n is the number of points in the curve. The solution can be written in the following 
vectorial form: 
OV OE. V, 
Var Vet = SEO = (D) 
which can be rewriten in matrix form: 
OE. (V, 
(K - 41)V; 2 yV4, — OBezt(V1—1) (8) 
ov ; 
where / is the n x n identity matrix and K is a n x n matrix. The elements of K are determined by Equation 7 and the 
initial conditions; the snake has free extremities (Berger, 1991), i. e. v"(0,t) = v""(0,t) — v"(1,t) 2 v" (1,t) = 0. y is 
given by (Berger, 1991): 
| OEtot | 
Ou 
= ; 9 
y 5A (9) 
where A is the mean progression of the curve. The initial A must be determined by the user. We keep the same A until 
the total energy of the curve increases and then we decrease A by a factor of 0.75. We can approximate the total energy 
of the curve at time ? by: 
  
n 
Eia = X (Bezt(vi,t) + alvt | + Blot?) (10) 
i=1 
To summarize the correction step, for each road segment: 
1. Initialize a snake curve (Vo) with the re-localized road segment found in the matching step. Each pixel belonging to 
the curve is a v; o. Set t to 1. 
2. Compute V, from Equation 8. 
3. If the total energy of the curve decreases then increment ¢ and go to step 2. 
4. If A is not too low, decrease A, increment ¢ and go to step 2. 
5 GENERATION OF HYPOTHESIS FOR NEW ROADS 
As mentioned earlier, the second problem in updating road database is the detection of new roads. These new roads are 
also bright lines on a dark background, so the result of the line detector can be used. 
Our work is based on the supposition that new roads are connected with the existing road network. This hypothesis is 
realistic because roads are built to allow people to travel from one place to another. For this reason, we consider only lines 
connected to the road network as given in the existing database. The line-following algorithm starts from junctions in a 
N x N neighborhood of the roads, corrected using the snake approach (Figure 4a). We follow all lines originating from 
these junctions. We consider each line pixel in a 5 x 5 window around a junction as a starting pixel for the line-following 
process. 
For each line, we proceed as follows: Initially, we take one of the starting pixel (anyone). Let p be the last chosen pixel 
(we call it the parent). First, we consider three neighbors of this pixel in the line direction. For example, if the line 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B7. Amsterdam 2000. 93