A MULTIRESOLUTION FEATURE BASED METHOD FOR
AUTOMATIC REGISTRATION OF SATELLITE IMAGERY
BASED ON DIGITAL MAPS
Farhad Samadzadegan, Sara Saeedi, Mohammad Hosseini
Dept. of Geomatics, Faculty of Engineering, University of Tehran, Tehran, Iran
Keywords: Registration, Feature Extraction, Matching, Satellite Images, Digital Maps, Genetic Algorithms.
Abstract: The registration of satellite imagery based on object information such as digital vector maps is one of the
main key tasks in most of remote sensing applications. Due to the tremendous complications and
complexities associated with the natural scenes appearing in satellite imageries and vector maps, fully
automatic registration process have faced serious obstacles and thus, only in a relatively simple imaging
environment a reliable result is normally expected. In the proposed procedure of this paper, Genetic
algorithms (GAs) are used to detect and match the corresponding key features in the satellite image and
object data based on a multi-resolution representation of information and math models. The present
approach is designed to be completely independent from the sensor type and any a prior information on the
exterior orientation. A first successful application of proposed approach is demonstrated for automatic
registration of IKONOS imagery and GIS map.
1 INTRODUCTION
With the ever increasing number of remote sensing
satellites, advances in data fusion and the
functionality of modern geographic information
systems, the use of multi-image spatial information
products is swiftly becoming commonplace.
However, in order to meet the requirements of the
user, each individual image making up the multi-
image product needs to be expressed in the same
geometric reference frame. This means the images
have to be accurately registered to geodetic co-
ordinate system (e.g. maps) (Dowman and Dolloff,
2000; Heipke, 1997; Smith and Park, 1999).
This paper, introduces a novel multiresolution
method for automatic image to map registration
based on key point features consideration. The
overall strategy for our proposed registration method
may be expressed by the following interrelated three
phases: 1-Multi-resolution Representation, 2-
Feature Extraction, and 3-Feature Based
Registration (Figure 1). In the following, the main
components of the each phase will be described with
more detail.
Image
Image
Object
Object
Geospatial
Data
Math
Model
Optimum Math Model
Optimum Math Model
∑
=
∑
=
∑
=
∑
=
∑
=
∑
=
=
n
i
n
j
n
k
k
Z
j
Y
i
X
ijk
b
m
i
m
j
m
k
k
Z
j
Y
i
X
ijk
a
x
000
000
∑
=
∑
=
∑
=
∑
=
∑
=
∑
=
=
n
i
n
j
n
k
k
Z
j
Y
i
X
ijk
b
m
i
m
j
m
k
k
Z
j
Y
i
X
ijk
a
y
000
000
Multiresolution
Representation
Multiresolution
Feature Extraction
Registeration
Multiresolution Registration and Math
Modeling
Affine
Reference
Feature
Pyramid
Input
Feature
Pyramid
Projective
Rational
Figure 1: proposed automatic registration method.
2 MULTIRESOLUTION
REPRESENTATION
One of the m+ain requirements needed for most of
registration algorithms is approximate values of two
corresponding points which is related to the
interrelation mathematical model of images and
object (i.e. digital vector map). The best known
solution to derive these approximations is to
construct multi-resolution representation of
523
Samadzadegan F., Saeedi S. and Hosseini M. (2006).
A MULTIRESOLUTION FEATURE BASED METHOD FOR AUTOMATIC REGISTRATION OF SATELLITE IMAGERY BASED ON DIGITAL MAPS.
In Proceedings of the First International Conference on Computer Vision Theory and Applications, pages 523-526
DOI: 10.5220/0001378505230526
Copyright
c
SciTePress
information and start the matching process at a low
resolution level (i.e. from the top of the image and
object pyramids). This can provide rough
approximate values for the successive levels of
image pyramids.
2.1 Multiresolution Representation
of Image Space
Construction of image pyramids in this project is
carried out according to wavelet transform. The
wavelet transform features are used because wavelet
transforms convey spatial and spectral
characteristics and their multi-resolution
representations enable efficient hierarchical
searching.
2.2 Multiresolution Representation
of Object Space
In proposed method, construction of object
pyramids, involves three stages of Partition of map
objects, Mesh simplification and Polygon merging.
In the first step, the vector map is separated to the
polygon classes by the major and minor roads
network. Mesh simplification principles are used to
construct vector pyramid levels for reasons of
combination and simplification of polygons. In order
to merge polygons (third step), neighbouring
polygons can be found in the data set by Delaunay
algorithm. In this step, by checking the bounding of
the polygons, neighbouring objects with or with out
common edges are detected and merged (Cecconi et
al., 2000).
2.3 Multiresolution Representation
of Mathematical Models
Most of high resolution satellite vendors (e.g. Space
Imaging) do not intend to present their sensor
models and precise ephemeris data. This means that
a large number of parameters are unknown, and will
not be able to be determined from the imagery alone.
So, in this study the tests are conducted based on a
multi-resolution representation of Generic Sensor
Models, i.e. Rational functions in the form of:
Direct Linear Transformation (DLT), 2D Projective,
and 3D affine models (Madani, 1999; Dowman,
2000; Tao and Hu, 2001; Grodecki, 2001).
3 FEATURE EXTRACTION
By construction the multi-resolution representation
of image and object, key points are extracted from
both of image and objects in all of pyramid levels.
3.1 Feature Extraction in Image
Space
Based on the generated image pyramids, the
implemented system extracts and constructs feature
pyramids by applying a modified Moravec operator
to each layer of the image pyramids. In addition to
point features the Moravec operator is also modified
to detect corners, intersections and centres of
gravity. The constructed feature pyramids therefore
include the feature attributes. These attributes will
greatly contribute to the Genetic algorithm as
described in section 2.3.1.
3.2 Feature Extraction in Object
Space
Referring to the vector structure of digital maps,
basically it is just need to identify the proper key
nods of line intersections or polygons vertexes with
a threshold for extraction of key nods.
4 FEATURE BASED
REGISTRATION
By construction of image and feature pyramids, in
this stage, for each feature in the feature pyramid of
image, based on corresponding mathematical model,
a search area is constructed on the corresponding
feature pyramid of object. Now to identify the
conjugate features the Genetic algorithm is
employed. The main advantage of Genetic algorithm
is its fast rate of convergency compared to the other
searching methods.
The Genetic algorithm starts with the selection of
population of features which followed by the
determination of a so called criterion function which
can comprise different similarity measures (e.g.
feature attributes) and geometric constraints (e.g.
affine transformation parameters). Using this
criterion function a new population is constructed by
decomposition of the old population using a so
called Cross-Over operator. The procedures are
repeated until a small subset of the population with a
specific pattern best satisfies the criterion function.
VISAPP 2006 - IMAGE ANALYSIS
524
4.1 Image Matching with Genetic
Algorithms
John Holland and his colleagues formally introduced
genetic algorithms (GAs) in (Holland, 1975). GAs
are based on the natural concept of evolution,
suggesting that diversity helps to ensure a population
survival under changing environmental conditions.
Chromosome Encoding: Using a bit string
encoding scheme for chromosome string, the
validity of conjugate pointes is encoded (Figure 2).
A 1-bit field is used to represent the possible
situation of individual conjugate point validity in
data set. The aim of coding is to create a
representation of conjugation (value 1) or non-
conjugation (value 0) of each pairs of points. This
allows any combination of points to be modified.
Figure 2: Encoding of n conjugate candidate into n bit
chromosome string.
Objective Function and Selection: The objective
function in image registration is to minimize the
RMSE of modelling residuals and maximize the
correlation between the image space and object
space. The correlation function between two images
A and B is given as
2
2
)()(
))((
),(
∑∑
∑
−−
−−
=
i
i
i
i
i
ii
BBAA
BBAA
BAC
For individual selection, we select highly fit
individuals with higher correlation (fitness) values
based on deterministic sampling. The mating is then
performed randomly using the crossover operation.
Finally, using the mutation rate of 0.05, each
selected individual is mutated by randomly altering
one bit in the chromosome string. The crossover
used in this research is the single-point uniform
crossover. The termination condition is to stop the
GA search after the solution converges or a pre-
specified number of generations are reached
(Chipperfield 1996; Husband 1990; Goldberg 1989).
5 EXPERIMENTS AND RESULTS
The potential of the proposed method is evaluated
using IKONOS imagery was acquired on 2004 and
corresponding digital map of the city of Tehran, Iran
(Figure 3). The maps have been produced in 2002
from 1:4000 aerial photographs. During these two
years time lapse between the generated map and the
IKONOS image acquisition, considerable changes
have also occurred in the city.
Registration process is performed hierarchically
using five–layer image pyramids. Each pyramid
layer has four times reduced resolution in relation to
its previous layer (Figure 4).
Table 1 shows the independent results for each
pyramid layer obtained by the Genetic algorithm
process. A comparison between the number of the
detected features in each layer and the number of
matched points clearly indicates how the Genetic
algorithm process has eliminated some of the points
in each layer (see Table 1). These are the points for
which, the geometric and the radiometric conditions
have not been satisfied according to the Genetic
algorithm parameters setting (Figure 4). The RMSE
values obtained by the GA based method are given
in Table 2. As this Table shows the RMSE values
for the first layer are 0.76, 1.09 and 0.94, 1.23 pixels
in the x and y image coordinate of the check and
control points respectively.
Figure 3: IKONOS image of TEHRAN (left) and
corresponding map (right).
(1)
Table 1: The number of matched points and the
corresponding residual errors on different layers.
Layer
Image
Points
Object
Points
Match
Points
Genera
tion
Math
Model
Order
5 12 115 7 100 P2=P4=1 2D-1
4 18 237 11 200 P2=P4 3D-1
3 31 496 20 300 P2=P4 3D-2
2 54 973 32 400 P2=P4 3D-3
1 85 1834 41 500 P2
=
P4 3D-3
Table 2: The number of matched points and the
corresponding residual errors in first layer.
Layer
Match
Points
Control
Points
Check
Points
RMSE
on
Control
RMSE
on
Check
1 41 30 11 0.76 1.09 0.94 1.23
1
Co
2
Co
n
Co
CandidatesofnumberN
bits
=
A MULTIRESOLUTION FEATURE BASED METHOD FOR AUTOMATIC REGISTRATION OF SATELLITE
IMAGERY BASED ON DIGITAL MAPS
525
6 CONCLUSION
The proposed automatic registration method
discussed in this paper, has proved to be very
efficient and reliable for automatic registration of
satellite imageries based on digital vector maps. The
implemented methodology has the following
characteristics:
• Utilization of a multi-resolution representation of
information and mathematical models.
• Employing a Genetic algorithm for conjugate
feature identification and modelling.
In spite of the success which is gained in the
implementation of the presented method, the topic
by no means is exhausted and still a great deal of
research works are needed. These research works
should be focused mainly on the development of a
more sophisticated Genetic algorithm, interest
operator and matching strategy. All of these are
currently under investigation in our institute.
REFERENCES
Chipperfield, A., Fleming, P., 1996. Parallel Genetic
Algorithms. In Parallel & Distributed Computing
Handbook by A. Y. H. Zomaya, McGraw-Hill, pp.
1118-1143.
Cecconi A., R. Weibel and M. Barrault 2000. Improving
automated generalization for on demand web mapping
by multi-scale databases. Proceedings of joint
international symposium on geospatial theory,
processing and application, ISPRS, Ottawa, Canada,
2002, pp. 1-9.
Dowman, I., and J.T. Dolloff, 2000. An evaluation of
rational functions for photogrammetric restitution.
Int’l Archive of photogrammetry and Remote Sensing,
33(Part B3): 254-266.
Greve, C.W., C.W. Molander, and D.K. Gordon, 1992.
Image processing on open systems, PE&RS, 58(1):
85-89.
Goldberg, D.E., 1989. Genetic Algorithms in Search,
Optimization & Machine Learning. Addison-Wesley
Longman.
Grodecki, J., 2001. IKONOS stereo feature extraction-
RPC approach. Proceedings of 2001 ASPRS Annual
Convention, 23-27 April 2001, St. Louis, Missouri,
unpaginated (CD ROM).
Heipke, C., 1997. Automation of interior, relative and
absolute orientation. ISPRS Journal of
Photogrammetry and Remote Sensing, 52: 57-73.
Holland, J., 1975. Adaptation of Natural and Artificial
Systems, The University of Michigan Press, Ann
Arbor.
Husband, P., 1990. Genetic Algorithms in Optimisation
and Adaptation. Advances in Parallel Algorithms
Kronsjo and Shumsheruddin ed., pp. 227-276, 1990.
Madani, M., 1999. Real-time sensor-independent
positioning by rational functions. Proceeding of ISPRS
Workshop on Direct versus Indirect Methods of
Sensor Orientation, 25-26 November 1999, Barcelons,
Spain, pp. 64-75.
Paderes, Jr, F.C., E.M. Mikhail, and J.A. Fagerman, 1989.
Batch and on-line evaluation of stereo SPOT imagery.
Proceeding of the ASPRS-ACSM Convention, 02-07
April, Baltimore, Maryland, pp. 31-40.
Smith, M. J. and Park, D. W. G., 1999. Towards a new
approach for absolute and exterior orientation.
Photogrammetric Record, 16(94): 617-623.
Tao, C.V., and Y. Hu, 2001. A comprehensive study of the
rational function model for photogrammetric
processing. Photogrammetric Engineering & Remote
Sensing, 67(12): 1347-1357.
Figure 4: Matched points in each layer of image pyramid (up), Matched points in each layer of vector map pyramid (down).
VISAPP 2006 - IMAGE ANALYSIS
526
