1 Introduction
The human vision and memory system can sense
and store a scene, and when observe the same scene
again, even with different illuminations and view
points, human can still recognize it [1]. In computer
vision this phenomena is called Image
Matching/Registration [5]. In vision navigation of
an aircraft or a satellite, it is named scene matching.
Scene matching is fundamental vision navigation
missions, but it has many problems such as how to
improve the correct rate, accuracy and efficiency of
matching in different viewpoints, illuminations, and
times. In addition, we can expand the adaptability of
the algorithm to match images from different
sensors, or to area with less salient objects.
The studies of scene matching algorithm consist of
the followings:
1- Selection of scene matching area;
2- Feature space;
3- Similarity metric;
4- Search Space and Strategy.
Many surveys [16-19] have discussed the state-of-
art of scene matching methods, but seldom
addressed the model and influencing factors. To
answer these questions, the scene matching problem
is modelled, and then, its influencing factors are
analyzed.
Scene Matching Techniques Using Satellite Imagery Data
A. A. SHAHIN
Professor in National Authority for Remote Sensing & Space Sciences, NARSS, Cairo, EGYPT
Abstract: - The problem of scene matching is a challenging problem in the field of image processing and pattern
recognition. Therefore, it is modeled and its influencing factors are analyzed. According to sources, influence
factors can be catalogued into three types: 1- changes of scenes 2- changes of image conditions 3- changes of
sensors. For each factor, its mechanism is discussed. Given a pictorial description of a region of a scene, it is
desired to determine which region in another scene is similar. The most efficient algorithms for scene matching
are discussed. Those are the sequential hierarchical scenes matching algorithms for grey-scale and binary
images and the two-stage template-matching algorithm. Experimental results are presented for matching
satellite images of AI-Minea (EGYPT) and Montana (USA) using those approaches. The results prove
efficiency and success in reaching the best match location with minimum required computations. A comment
on the results is presented as well as a comparison between the applied methods.
Keywords: scene matching, image registration, feature space, remote sensing
Received: October 11, 2022. Revised: September 9, 2023. Accepted: October 12, 2023. Published: November 2, 2023.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
194
Volume 5, 2023
The target of t his paper is to reach the best match
location with minimum computations required and
this leads us to deal with the most efficient scene
matching algorithms. Those are the basic sequential
hierarchical scene matching, the sequential
hierarchical scene matching rising edge features,
and the two-stage template matching for binary
images. An overview of the techniques is provided
as well as an analogy between the different
algorithms applied.
2 Definition and Modeling
Scene matching algorithm geometrically aligns the
sensed images and the reference images of the same
scene, which were taken at different time, from
different viewpoints and/or by different sensors,
according to similarity measurements [20-25]. Since
the reference images are calibrated, the coordinate
of targets in the sensed images could be known.
An image is a 2D function of greyscale on the
coordinates (x, y), the reference image could be
denoted as F reference.
IF real-time and F reference should be the same if no
influences in viewpoints, times, sensors and
illuminations. Therefore, the problem in scene
matching is created due to these influences. These
influences could be catalogued into: 1) changes of
scenes; 2) changes of image conditions; 3) changes
of sensors. These influences are functional since its
independent and dependent variables are 2D
functions.
F real-time = M (F reference
Figure: Influencing Factors of Scene Matching
2.1 Changes of Scenes
2.1.1 Greyscale Changing of Correspondence
Due to the different times at which the reference and
sensed images are acquired, the albedo and radiance
of the same point may change [26-30]. These kind
of changes stochastic, but are decided by hidden
mechanism. The green grassland in summer may
change into yellow in autumn. The influence of
greyscale changing can be modelled by:
F
) (1)
feature change = M feature change (F reference
2.1.2 Target Movement, Deformation and
Occlusion
, m).
(2)
m denote the generalized materials but not limited to
the materials of target points (x, y).
The target movement and deformation could also
cause differences between reference and sensed
image. The greyscale of the same point didn’t
change but its position changed. This can be
modelled by:
F feature movement = M feature movement (F reference )
= f reference{x (u, v), y (u, v)} (3)
Where x ( u, v), y (u, v) a re the movement
correspondence points. If it could be recognized, the
influences functional are modelled.
Occlusion is another influencing factor, which could
be considered as greyscale changing.
F mask =M mask (F reference
2.2 Changes of Imaging Conditions
, m) (4)
In scene matching, the major light source is the sun.
2.2.1. The illumination in a sunny day could be
modelled as parallel light (I x, I y , I z) whose
magnitude denotes the intensity and the direction
represents the direction of light. The scene could be
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
195
Volume 5, 2023
also modelled by a 3x1 vector S(Sx , Sy ,Sz ) whose
magnitude denotes the albedo and the direction
represents the surface normal [10].
F illumination = M illumination (F reference , L, S) (5)
2.2.2. Different Atmospheric Transmission
Atmosphere may dissipate and absorb the signal,
causing changes in brightness and contrast of
images.
F dissipation =M dissipation (F reference, d)
= d x F reference
2.3 Changes of Sensors
(6)
Where d € [0, 1] denotes the dissipation factor in
transmission.
2.3.1 Different Sensor Performances
Even in scene matching between the same modal of
images, the different sensor performances might
also influence the images.
Fsensor performance= Msensor performance (F reference
2.3.2 Multimodal Sensors
, para) (7)
The para describes the signal-to-noise ratio (SNR),
the sensitivity and resolution and so on.
For the same scene, the optical, infrared and
synthetic aperture radar (SAR) image sensed
different features and images.
F sensor difference = M sensor difference ( F reference
2.3.3 Different Position and Attitude of Cameras
, m) (8)
The mechanism of multimodal images is similar to
greyscale changing of correspondence, but the
differences are greater. It has a st rong connection
with the materials m.
The image difference caused by camera position and
attitude are modelled by
F position attitude = M position attitude (F reference, R, T) =
f reference
2.3.4 Different Internal Parameters of Cameras
{x (u, v), (y (u, v)} (9)
The position changes of correspondence
points x (u, v), y (u, v) follow the prospective
transformation which is the dependent variables of
the translation and rotation.
Focal length difference, lens distortion, angle
of view and other factors are the reason of
image distortion. x(u, v), y(u, v) can also model
the difference between.
F inter parameter = M inter parameter (F reference)
= f reference {x(u, v), y(u, v)}
To conclude Eq. (1~ 10), we get
F real time = (M inner parameter * M position attitude * M
sensor difference*M sensor performance*M dissipation* M
illumination *M mask*M feature deformation*M feature
movement*M feature change)* (F reference
2) Some factors share similar models and could
be merged. The greyscale changing of
correspondence is a slight version of
multimodal.
) (11)
Considering the following reasons, Eq. (11) could
be simplified.
1) The occurring probability of some influencing
factors is low or can be eliminated through the
calibration, say the target movement, deformation,
occlusion and the lens distortion.
3) Some problems have been solved by current
methods, such as the difference of brightness
and contrast.
F real time = (M sensor difference * M projection *M gray mapping
* M illumination) (F reference) (12)
Where M sensor difference is the functional of
multimodal; M illumination denotes the functional
illumination difference; M projection
(10)
describes the
functional of perspective projection;
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
196
Volume 5, 2023
3. The Sequential Hierarchical Scene
Matching Algorithms
These approaches incorporate a hierarchies search for a
possible match location starting at a low resolution level.
During the search at each resolution level, sequential and
detecting rules are applied to further minimize the
amount of computations.
A- The Basic Sequential Hierarchical Scene Matching
Algorithms:
The simple rule by which the level-K scene is reduced
level K-1 scene is simple four-point averaging [1], i.e.
BY this rule, it is possible to create a set of images which
are of lower resolution and smaller size. Hierarchical
search analysis is created in [12].
(13)
Two sets of these images are created, one for the window
and the other for the search region. For a search region of
size N x N and a window of size M x M in the highest
resolution level, the number of possible match locations
is (N-M+1). This number reduces to
[(N/2L)-(M/2L) +1]2
When dealing with lower resolution levels, L is the
search level.
Sequential Decision Rules:
Dealing with the lowest resolution level, each window
pair (the window W and the sub image of the search
region of the same size S) are compared and the error
measurement is calculated as:
E
n
K (u, v) = (14)
E K u, v (si, wi) = | si – wI
This is done for all possible test locations in the lowest
resolution level, and then this error measure is compared
against a threshold T.
| is the error measure of the
ith window pair of test location (u, v), n =M x M, and K
is the resolution level.
Threshold Sequence Categories:
The threshold Tn. is determined as the average of the
cumulative error, i. e.,
T n= E n. (15)
As the search resolution increases, the threshold sequence
Tnk= (√2) m-k rm (n +g
Where,
k√)
(16)
previously introduced must be modified. [ 3,4,5]
suggested a method of a determining the threshold for
every resolution level K :
rm
g
= the amplitude of the av erage er ror
measure at the matched location of the
lowest resolution level m.
k
As the value of g
= amount of deviation from the mean.
k increases, the threshold increases, and
so is the probability of match. However, the
computational efficiency decreases.
Let this method be denoted as method A1 for gk=0.
The most reasonable method of determining the threshold
is to consider the accumulated error measurement for the
number of successful test locations. Then the new
threshold will be the average error calculated. In general,
the threshold at any resolution level will be [6],
En
k= (1/n) ∑
1 (17)
Where,
Ej= the total error at each successful test
location
n = the number of successful test location which
is determined by the previous level.
Let this method be denoted as method A2.
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
197
Volume 5, 2023
Tnk
The sequential decision rules can be formulated as
follows,
= (1/ √2). ∑
=1
(18)
Also, one may think of these error measurements as
if they were the spectrum of computations. So, the
effective number of results may be considered as the
3dB bandwidth of the last measured one of equation
(5), so
Let this method be denoted as method A3.
Let Nk be a set of test locations (u, v) at search
level K such that:
(19)
Nk= {(u, v) | En
k (u, v) < Tn
k, 1≤ n ≤ M2
Where
< T
}
n
k
(20)
matrix G
is threshold computed at search level k. to
deal with the resolution level K-1 a location
k-1 is generated whose dimension depends
on the way the resolution decreases.
This location search continues until one of two cases is
encountered:
a) GK-1 (u, v) =1 for only one value of (U, V)
b) At K=0, there exist several locations (u, v) such that
G0
(b) Sequential Hierarchical Scene Matching Using
Edge Features:
,(u, v)=1. Select the location with the smallest
accumulated error as the most likely match location.
For this method, it is the similarity between the two that
is important, it is more appropriate to use edge and
introduce a measure of similarity.
(1) Edge Extractions:
Edge images created for scene matching
must be capable of meeting some basic
requirements [17]. Letting the grey-scale image to be S
(x, y), we can generate a binary
image S (x,y) such that:
(2) Pairing Functions:
In a m atching process two image arrays are produced.
Using the two quantization level (0 and 1), there will be
four types of pairs: 0-0, 0-1, 1-0, and 1-1. The pairing
functions matrix would be given by [8],
Where Nij= the number of I in W that pair with j in S.
A similarity correlation R (u, v) can be constructed as:
(23)
Where n= the number of quantization levels.
R (u, v) is the product of the rations of the number of
matched window pairs to the number of possible matches
of each type. For binary case
(22)
(21)
k
k
k
N
N
ji
ji
jiG ∉
∈
=−−
−
),(
),(
,0
,1
{)12,12(
1
}{
11
01
10
00
N
N
N
N
)],(
0
1
/),([
0
1
),( vuNij
j
n
vuNii
i
n
vuR
=
∑
−
=
∏
−
=
k
k
k
N
N
ji
ji
jiG ∉
∈
=−−
−
),(
),(
,0
,1
{)12,12(
1
(24)
T
T
yxfS
yxifS
in
ax
yxS <
≥
=),(
),(
Im
Im
{),(
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
198
Volume 5, 2023
For each resolution level, given a probability of match,
one can determine the threshold required as in [7]:
RTK= max [(,)]P-YRbk (25)
Where:
Rb
k= the background level at resolution level K.
Y= A parameter determines the probability of match.
The test location which has a similarity measure less than
this threshold is eliminated from discussion in higher
resolution levels.
III- The binary Two Stage Template Matching:
This approach towards increasing the efficiency of
template matching is to divide the matching process into
two stages. The first stage applies the optimum sub
template of the given template (window) at each location
of the picture (the search region). The second stage
applies the entire template, but only at locations where
there is a sufficient match between the sub template and
the picture. This match is determined for every test
location by applying a m ismatch measure which counts
the number of mismatch points for each kind (0 and 1)
normalized to the total number of points in the template,
[19], i.e.
(1/n) [NU (0) + NZ (1)] (26)
Where,
U ≡ the set of template points which are 1.
Z ≡ the set of template points which are 0.
NU (0) ≡ the number of picture points in U which are 0.
NZ (1) ≡ the number of picture points in U which are 1.
Each mismatch measure is examined against a threshold.
The successful match locations are those which have
mismatch measures less than this threshold which is
determined for each Optimum sub template size. This
optimum size is determined for minimum computational
cost which is determined as follows [19],
E (p, q, t, m, n) = m + ф (c m1/2) [n – m] (27)
Where,
m is a sub-template size.
n is a template size.
ф (c m1/2
Table II: Performance of the sequential hierarchical
scene matching using edge features
) is False alarm probability.
q is a fraction of template points which are 1.
P is Probability of occurrence of 1 in the background.
The Previous algorithms have been applied on satellite
imagery of parts of AI-Minea (Egypt) and Montana
(USA) of size 64x64 and different window sizes. The
window is selected from the search region to be at the top
left corner (position (1, 1).This work is done using the
Remote Image Processing System (RIPS). Figures 1, 2
and 3 show the search regions under test. Samples of the
results are listed in tables I, II, and Ill for a search region
of Al-Minea and a window size of 24x24 at the highest
resolution level.
Table I: Performance of the basic sequential
hierarchical technique
Table III: Performance of the binary two stage
template matching
Resol-
ution level, k
SR Size
Window Size
Threshold
No. of
successful test
locations
A1 A2 A3 A1 A2 A
3
2 16x16 6x6 1453 122
1 32x32 12x12 8219 3010 2129 60
1 64x64 24x24 60 39 15
Minimum error
at position (1, 1)
Resolution
level, k
RMax
[R]
b Y R P
T
No. of
successful
test
locations
K
2 0.241 1.0 3 0.276 0.998 121
1 49
0 0.240 1.0 2 0.519 0.977 31
1 0.760 0.841 8
0.5 0.860 0.691 1
At position
(1, 1)
))((),(
111
11
01
00
NN
N
NN
N
vuR ooo ++
=
4. Experimental Work:
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
199
Volume 5, 2023
It is seen that on the three matching methods, sequential
hierarchical scene matching with edge features appeared
to be the best candidate for scene matching. The second
candidate is the basic sequential scene matching
algorithm then finally the binary two-stage template
matching.
The first candidate has an advantage of having a high
probability of match. Excellent performance was
obtained in the matching of images of regions that have a
variety of contents to have a variability of gray values.
The results show that the final decision (the true match
location) is reached at greatly reduced computations than
the other two methods.
Scene matching with the basic sequential hierarchical
method provides good performance in matching of scenes
that contain relatively man-made objects of varying
background. A final direct decision of the true match is
rarely reached from the first step and this needs
investigations of the error measure of the previous
resolution level. It is noted that as the window size
decreases the number of successful test location
increases. As a m atter of fact, the efficiency of this
method will increase as the resolution levels increase.
The third candidate shows great efficiency in dealing
with the image of Montana as seen in table IV. On the
other hand, this method is not effective at all in dealing
with the image of AI-Minea may be because the nature of
this image is that the different details are rare besides that
the selected window has the same nature of the search
region as a whole.
Table IV: Performance of the binary two-stage
template matching for the Image of Montana with a
window size 32x32
Fig. 4 Binary images of AlMinea and Montana
The disadvantages of the methods dealing with edge
features, general, lie in the problem of edge extractions,
which may result in a loss of the desired object with
respect to background.
The problem of deciding which matching method is more
effective for a certain image than the others depends on
many factors such as: the kind of objects to be
investigated, the dynamic range of the scene and the
relation between the objects and the background. As a
matter of fact the choice is restricted to the sequential
hierarchical scene matching algorithms only for their
superior performance which could be guaranteed for
almost all images. Edge feature methods is the best for
scenes which have objects that have grey scale values
that vary considerably with respect to the background.
Threshold Stage Window
Size
No. of successful
test locations
0.3
1
3x3
809
0.3
2
24x24
569
Threshold
Stage
Window
Size
No. of successful test
locations
0.4
0.4
1
2
3x3
32x32
333
3
minimum mismatch
at (1, 1)
0.25
0.25
1
2
4x4
32x32
69
2
minimum mismatch
at (1, 1)
5. Conclusion
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
200
Volume 5, 2023
References:
[1] Li. Xiang, “Scene Matching Techniques”; Modeling
and Analysis. Y. Yang, M. Ma, and B. Liu (Eds.):
ICICA 2013, Part II , CCIS 392, pp. 184–193, 2013.
[2] Deshmukh, M., Bhosle, U., “A Survey of Image
Registration”; International Journal of Image
Processing 5(3), 245–269 (2011).
[3] Wyawahare, M.V., et al., “Image Registration
Techniques: An overview”; International Journal of
Signal Processing 2(3), 11–28 (2009).
[4] Dawn, S., Saxena, V., Sharma, B., “Remote Sensing
Image Registration Techniques: A Survey”; The
International Conference on Image and Signal
Processing”, pp. 103–112 (2010).
[5] Guo, Q., “Modeling and simulation of the scene
matching and orientation system”; Infrared and
Laser Engineering 35(z1), 295–300 (2006).
[6] Wang, H., Zhang, K., Li, Y., “Research Progress on
Image Matching”; Computer Engineering And
Applications 40(19), 42–44 (2004).
[7] Zitova, B., Flusser, J., “Image registration methods:
a survey”; Image and Vision Computing 21, 977–
1000 (2003).
[8] Brown Gottesfeld, L., “A survey of image
Registration Techniques”; ACM Computing Surveys
24, 325–376 (1992).
[9] E.M. Abdel-Raheem, “Microcomputer Applications
in Scene Matching, “M. Sc. Thesis, Faculty of Eng.,
Ain Shams Univ, Cairo, December (1988).
[10] A. A. Shahin et al., “Analogy of Different Matching
Methods using Satellite Imagery”, Aeronautical Science
& Aviation Technology ASAT; Cairo, 1985.
[11] Tanimoto, S. and P avlidis, T., “A Hierarchical Data
Structure for Picture Processing.” Comp. Graphics
Image Processing 4, 104-119, (1975).
[12] Hall E.L., "Computer Image Processing
Recognition," Academic Press, New York, (1979).
[13] R.Y. Wong and E.L. Hall, "Sequential Hierarchical
Matching," IEEE Trans. Comp. C-27, 359-366,
(1978).
[14] Hall E.L., Wong, R.Y., and Rouge, J., "Sequential
Scene Matching with Hierarchical Search," Proc.
IEEE Southeast Conf., Williamsburg, Va., April,
pp.402-405, (1977).
[15] Wong, R.Y., Hall, E.I. and Rouge, J., "Hierarchical
Search for Image Matching," Proc. IEEE Conf.
Decision and Control, Clearwater, Va., December
(1976).
[16] Wong, R.Y., "Sequential Scene Matching Using
Edge Features, “IEEE Aerosp. Electr. Syst., Vol.
Aes-14, Jan. (1978).
[17] Green, G.S., Reagh, F.L. and H ibbs, E.B.,
"Detection Threshold Estimation for Digital Area
Correlation, "Trans. Syst. Man Cybern. SMC-6,
No.1, 65-70, (1976).
[18] G.J. VanderBurg and A. Rosenfeld, “Two-Stage
Template Matching,” IEEE Trans. Comput., Vol. C-
26, No. 4, April (1977).
[19] R.Y. Wong and E.L. Hall, "Sequential Hierarchical
Matching," IEEE Trans. Comp. C-27, 359-366,
(1978).
[20] Hall E.L., Wong, R.Y., and Rouge, J., "Sequential
Scene Matching with Hierarchical Search," Proc.
IEEE Southeast Conf., Williamsburg, Va., April,
pp.402-405, (1977).
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS,
COMPUTATIONAL SCIENCE AND SYSTEMS ENGINEERING
DOI: 10.37394/232026.2023.5.18
A. A. Shahin
E-ISSN: 2766-9823
201
Volume 5, 2023
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
The author contributed in the present research, at all
stages from the formulation of the problem to the
final findings and solution.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
No funding was received for conducting this study.
Conflict of Interest
The author has no conflict of interest to declare that
is relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
