The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008
195
corresponding weights. The weights are optimized according to
their local geometric and topological similarity. After each
iteration, the global matching (i.e. global compatibility) is
measured. The process reaches an optimal matching when the
global compatibility measurement becomes unchanged or varies
to a limited threshold. We details the matching process in
following subsections.
4.1 Local Similarity
Once we have constructed the attributed graphs from two
networks we proceed with their optimal matching. Given V k m
from G m as the current label of V? in G d , the goodness of such
mapping (V d ->V k m ) can be measured through a modified
version of the exponential function (Li, 1992). Our aim is to
iteratively re-label the nodes of the data graph with the model
graph so as to optimize a global compatibility measured by the
structures and geometries of matched nodes. The goodness of
the local fit can be measured with H (V d , V k m ):
a) If not both Vf and V k m are associated with the basic loop
= (2)
Where s, a = road intersections in the dataset
to be registered, where s & a are connected with i
k,t, t= road intersections in model dataset, where
t & r are connected with k
a * = sum of relative distances of
intersections i, s and i, a
a » = sum of relative distances of
intersections k, t and k, r
b) If both V? and V k m are associated with the basic loop
tf(^.0 = exp(-lmin| b l{ J-b k ^ |) (3)
+ exp(-1 D (s a) j d - D U T) K m |)
Where i, s, a, j = road intersections in the dataset
To be registered and form the basic loop of i
k, t, x, k = road intersections in model dataset
and form the basic loop of k
a * = sum of relative distances of
U (s,a),j
intersections s,j and a,j
a - = sum of relative distances of
U U,t).k
intersections t, k and r, k
Use Figure 3 as an example. If we consider labelling V 2 m for V d ,
V d has two connected vertices V d and V d , which also both
connect with vertex V d . At the same time, V 2 m also has two
connected vertices V™ and V 5 m both connecting with vertex V 4 m .
In this case, H should be measured with the formula (3). If V k m
has more than two adjacent vertices as F / m , we choose the two
vertices that minimize the power value in function H.
Figure 3. Vertices with inexact degrees
The novel feature of this local consistency measure H is its
compound structure, which distinguishes it from many
alternatives in the literature. Specifically, the geometry and
topology for measuring local mapping goodness is formed by
nodes both directly connected (marked with yellow circles in
Figure 3) and indirectly connected (marked with blue circles in
Figure 3) with the mapping nodes. The underlying advantages
with these two measurements is that the constructed H function
will not be affected by the presence of noise (i.e. the additional
link V 3 m in Figure 3) and the ambiguity will be reduced as low
as possible. Similarly, the presence of noise (i.e. additional
links) in V y would not affect our matching.
4.2 Global Compatibility
With function H, the local difference between V k m and V? under
the minimal relative distance constraint is mapped into a
similarity measure for assigning V k m to Vf . As the continuous
relaxation labeling framework, weighted values other than
logical assertions (1 or 0) are attached to all possible
assignments for each vertex in G d . The weight (denoted by Pi(>»))
with which label V™ is assigned to vertex V? belongs to [0,1].
In addition, the sum of the weights for all possible assignments
to any vertex should be equal to 1. Let 0 be all available
assignments with V to V d . The global compatibility function
can be formed as:
A(01 d,m) = Z Y.H,{V k \V;)p i <y k m )p J <y;)
(4 )
Thus, the optimal labeling of with V™ will be the assignment
that maximizes the above function. We use the gradient ascent
algorithm, which iteratively computes the length and direction
of the update vector to update the weight p such that the global
compatibility function A will increase with each updating of p.
The iteration terminates when the algorithm converges,
generally producing an optimal labeling (or matching).
Interested readers are referred to (Hummel and Zucker, 1983)
for additional details.
5. EXPERIMENTS
We tested proposed approach in two experiments in order to
demonstrate its performance and robustness. All tests are
implemented in MATLAB environment.
5.1 Test 1
The two road networks used in this experiment are detected
respectively from a map, typically having larger coverage, and
from an image with smaller coverage. They are shown on the
left in Figure 4, with their corresponding graphs on the right.
The two networks reflect typical registration conditions,
whereby an image and a corresponding map may differ