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