The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
194 
relaxation matching are described in Section 3. In Section 4, our 
revised relaxation labelling algorithm for matching is described 
in detail. Experimental results are presented in Section 5. 
Finally, Section 6 presents conclusion and outlines our future 
work. 
2. NETWORK PREPARATION 
Geographic features (road networks) extracted from both data 
sets are first transformed into graph structure as input to our 
approach: extracted intersections are modelled as vertices in the 
graph, while road segments between intersections are modelled 
as straight edges in the graph. The detection of intersections is 
not a topic addressed by this paper, as this is a well-researched 
topic in photogrammetry and computer vision. We assume that 
road intersections have been detected in both datasets being 
registered. Figure 1 exemplifies the transformation of the road 
networks in an image. 
one edge, while value 0 represents no edge. By definition 
adjacency matrix is invariant with respect to translation, 
rotation, and even scale variations between the image and the 
corresponding geospatial dataset. 
Typically Euclidean distance is an important measurement of 
the geometry. It is invariant to translations and rotations, but not 
to scale changes. In order to overcome this problem we use the 
relative distance between road intersections as a node-linking 
attribute (instead of Euclidean distance). Relative distance is 
defined as: 
(Z> +£>.,) *0.5 
where i,j, t = three road intersections 
n = relative distance between i and / 
ij 
Dy = euclidean distance between i and j 
Dj, = euclidean distance between i and t 
A third attribute (basic loop attribute) can be derived from 
adjacency matrix. It is used to model higher network 
topological structures, specifically the formation of closed loops 
in it. In the case of networks the closed loops are of triangle, 
quadrangular or higher forms, and accordingly the basic loop is 
defined as: 
Figure 1. Graph representation of road networks on imagery 
For the sake of clarity, we name the graph from image space as 
G d and the one from corresponding object space as G m . 
d dm 
Correspondingly, V\ is a vertex of G d , E\ an edge of G d , V\ 
m 
a vertex of G m , E\ an edge of G m ... 
3. FORMALIZATION OF INVARIANT ATTRIBUTES 
Invariant attributes are essential for matching as they can 
reduce ambiguities in local similarity and the corresponding 
search space. Developing invariant attributes, however, is a 
non-trivial issue. In one hand, as the involved imagery and GIS 
datasets may differ in terms of resolution, scale, coverage, and 
orientation in general, the conjugate features may also differ to 
a certain extent. On the other hand, as road networks usually 
involve high volume of data, it is important to develop 
attributes that require less computational efforts. In this section, 
we introduce attributes derived from the geometry and topology 
of road networks, which are invariant to translations, rotations 
and scale changes. 
We start with connectivity attribute represented by the formal 
adjacency matrix (noted as A), which can be used to model the 
topological structure of road networks. 
Definition 1. If there is at least one single road segment 
connecting road intersections i and j, i is said being connected 
to j (or vice versa). The entry for ij in the adjacency matrix A is 
of value 1. Otherwise, it is 0. 
Definition 2. If vertex V t has two adjacent (connected) vertices, 
each of which also has one common adjacent vertex other than 
Vi, Vj has one quadrangle associated to it. 
Figure 2. The quadrangle in networks 
This is exemplified in Figure 2. V, has two adjacent vertices V 2 
and V 4 . Both V 2 and V 4 are adjacent to V 3 . Thus, Vj is associated 
to one quadrangle formed by V,, V 2 , V 3 , V 4 . Same as V 4 , V 3 and 
V 2 . As mentioned above, the property can easily be extended to 
more complex, polygonal loops, if so desired. 
4. MATCHING TWO ROAD NETWORKS 
Accordingly, the road network is defined through the graph 
embedded two topological (connectivity and basic loop) and 
one geometric attribute (relative distance). The reader can 
easily understand that additional attributes may also be used as 
needed. This type of graph is termed attributed graph here (and, 
similarly, attributed network). Using the above notations for 
these two networks, our aim in matching is to optimally 
correspond (label) nodes V? in graph G d to those in graph G m 
satisfying certain matching criteria. The road network matching 
is formulated as a graph-labeling problem. 
The adjacency matrix can be derived from the graph. The entry 
values of the matrix correspond to the existence of edges 
between corresponding vertices, i.e. value 1 describes at least 
Based on relaxation labelling, the matching process iteratively 
re-labels the data nodes with model nodes by changing their