AN ATTRIBUTE-DRIVEN APPROACH FOR IMAGE REGISTRATION 
USING ROAD NETWORKS 
Caixia Wang, Peggy Agouris, Anthony Stefanidis 
Center for Earth Observing and Space Research 
Department of Earth Systems and Geoinformation Sciences - (cwangg; pagouris; astefani)@ gmu.edu 
George Mason University, Fairfax, VA 22030, USA 
Commission IV, WG IV/2 
KEY WORDS: Georeferencing, Matching, Imagery, GIS, Feature, Transformation 
ABSTRACT: 
Geospatial analysis is becoming increasingly dependent on the integration of data from heterogeneous sources. In this paper, we 
present an automated, feature-based approach for geometric co-registration using networks of roads (or other similar features). This 
approach is based on a graph matching scheme that models networks as graphs with embedded invariant attributes. The main 
advantages of our approach reside in its ability of using both geometric and topological attributes to reduce the ambiguity in search 
space for inexact matching as well as its invariance to translation, rotation and scale differences (through the use of appropriate 
attributes). Furthermore, our approach requires no user-defined threshold to justify local matches. Using the information derived 
from this matching process, the registration of two datasets can be accomplished. 
1. INTRODUCTION 
Geospatial analysis is becoming increasingly dependent on the 
integration of data from heterogeneous sources. The geometric 
co-registration of these datasets still remains a challenging and 
crucial task, especially given the emergence of novel data 
capturing approaches, like the use of unmanned aerial vehicles 
(UAVs) to capture long image sequences. In this context, 
registration may refer either to the registration of images to 
images, to generate for example long mosaics, or to the 
registration of images to maps, to identify their orientation 
parameters. This registration problem becomes increasingly 
complex when we consider differences in coverage, scale, and 
resolution as corresponding objects in two datasets may also 
differ to a certain extent. 
Road networks usually are common features in areas of interest. 
Unlike points or point-like features e.g. manhole covers 
(Drewniok and Rohr, 1996) or building comers (Rohr, 2001), 
road networks contain inherently substantial semantic 
information in their structure (e.g. topology and geometry), and 
thus are considered robust entities for matching in our approach 
based on graph matching. A great deal of effort has been 
devoted to graph matching by the computer vision community. 
In the work of Barrow and Popplestone (1971), relational graph 
matching was first studied where a relational graph is designed 
to represent scene structure for matching. After that, it has been 
widely adopted and developed for matching problems. Two 
major approaches can be identified. One involves the 
construction of structural graph model where geometric 
attributes of components are not taken into consider. Matching 
techniques are developed solely based on structure pattern, like 
the graph and sub-graph isomorphism approaches (Shapiro and 
Haralick, 1985; Pellilo, 1999; Bunke, 1999; Jain et. al., 2002). 
The major drawbacks in these graph-theoretical methods are 
their computational complexity and inability to handle inexact 
matching due to noise or corruptions in the graph. Later works 
in Wilson and Hancock (1997) and Luo & Hancock (2001) 
exemplify some enhancements based on pure structural graph 
model. The second approach to the problem appreciates the 
measurements of network components and represents networks 
as attributed relational graphs. Matching techniques are 
developed to compute graph similarity based on these 
measurements and network relational structure, such as 
relaxation labelling algorithm (Rosenfeld et. al., 1976; Li, 1992; 
Gautama & Borgharaef, 2005), information theory principles 
(Shi and Malik, 1998), Markov Random Field method (Li, 
1994). In these approaches, invariant measurements of network 
components are essential for the matching as they can reduce 
ambiguities in local similarity and the corresponding searching 
space. But due to different scope of computer vision 
applications (e.g. face recognition, content-based image 
retrieval) research has addressed geometric and topological 
attributes of the network in a rather limited manner, focusing 
instead more on performance metrics (e.g. faster convergence). 
In this work, we develop an efficient algorithm of inexact graph 
matching using invariant attributes (geometry and topology) 
included in geographic networks and is based on the relaxation 
labelling introduced by Hummel and Zucker (1983). The 
challenges we are facing include the computational complexity 
of matching network components (i.e. junctions and polygons), 
as well as errors in feature extraction due to the presence of 
noise in scenes, like building-induced shadows and occlusions. 
In this paper, the utilization of point networks and revised 
relaxation labelling provides the ability to utilize structures and 
geometric attributes derived from the network to improve the 
matching algorithm and thus achieve relatively efficient 
computation. The process is fully automatic in terms of no input 
needed from users. These unique advantages serve both as the 
motivation for our work and constitute the main contributions 
of this paper. 
The remainder of the paper is organized as follows: Section 2 
describes the formal representation of road networks in terms of 
attributed relational graph. The attributes developed for 
193