International Archives of the Photogrammetry, R 
detection of error match and elimination function is developed. 
Figure 1 shows the workflow of matching approach. 
3.1 Feature points extraction 
In DEM generation, either predefined points (e.g. distinct 
points) or freely defined points must be measured. A 
requirement for optimality is the selection of points, which 
represent well the surface to be measured. The best case is to 
measure just these points that are sufficient to describe the 
surface. Therefore, feature points are extracted with location 
operator (Figure. 2). To ensure the well contribution of feature 
points, before feature point extraction, the image is divided into 
regular grid. Within each grid window only the feature with the 
best interest values is kept. The computed attributes of each 
feature depend on the dimensionality and on the desired 
computational complexity. The selected grid size depends on 
the image type and desired dense of match result. 
3.2 Approximate value estimation 
In matching, good approximations are necessary to reduce the 
search scale, thus reduce the number of false matches and 
multiple solutions. To get good approximations, two strategies 
have been used, image pyramid and seed point. 
3.2.1 Image pyramid: Before matching, images of different 
levels of resolution (named image pyramid) are constructed by 
reducing the resolution. Instead of using a pre-defined value, 
the number of pyramid levels is adaptively determined 
according to the type of images and relative registration results. 
The match is firstly applied in the highest level of the pyramid. 
In the following pyramid level, the initial approximation is 
derived using match results of previous level. 
3.2.2 Neighbouring and seed points: Besides image pyramid, 
derivation of approximate values can be achieved by using 
neighbouring points. The known points are relative registration 
results Then points close to the known ones can get 
approximations from their known neighbours and matching 
results of these points can be used to approximate other points. 
3.3 Matching with 2-D relaxation 
The important aspect of the relaxation match algorithm, which 
distinguishes it from the single point matching, is its compatible 
coefficient function and its smoothness constraint satisfaction 
scheme!*!*!, For each feature point in the left epipolar image, a 
search window, which centre line is alone the corresponding 
approximate epipolar line and its height is larger than one of the 
template centring in the given point, can be determined using 
the approximate value estimation method described above. 
There could be several candidate matches appearing in the 
search window. They can be searched by traditional cross- 
correlation technique in two directions (horizontal and vertical) 
instead of only in horizontal direction of 1-D relaxation. The 
candidate matches are selected if their correlation coefficient 
lies above a certain user-defined threshold. Let I; be one of the 
feature points on the template image and 7; (j71..... m) its 
candidate matches on the search image. P(i,j) is the probability 
of match /<>/;,. Moreover, let I, be one of the points located in 
the neighbourhood of point /; and I, (I=1....m) are 
corresponding candidate matches of /,. In order to link the 
matching results of the neighbouring feature points to each 
other, the following compatible coefficient function C(i,j; kJ), 
emote Sensing and Spatial Information Scienc 
es, Vol XXXV, Part B7. Istanbul 2004 
which quantifies the compatibility between the match /; €» /; 
and a neighbouring matc/ 7, €» I „is defined as 
CG, Fk. D) = (10) 
pu ha 
exp[(Ap,' + Np)! P) 
Apo m(x,—x)-(G,- X.) 
Ap, = (y; ey ) T (Yi cM: ) 
In equation (10), Ap, expresses the difference of the x- 
parallaxes in point /; and its neighbouring point /,, while Ap, the 
difference of the y-parallaxes. The bigger the 4p is, the smaller 
the compatibility. This corresponds to a smoothness constraint 
on the image matching results, and it provides an ability to 
bridge over the poor texture areas by assuming the parallax 
surface varies smoothly. 7 and fi are constant values. In the 
relaxation scheme, the global consistency of matching can be 
achieved by an iterative scheme where the probabilities P(i, J) 
are updated by the following rule: 
p^ j) = pu. ne" u. 
> p"(i,s)0 (s) 
s=l 
Qu, N= Il Y p" «nca, fk. 
I, eQ(I,) I=) 
O(1;) is the neighbourhood of point /i (can be determined by 
TIN construction or neighbourhood relation), and n is the 
iteration number. The quantity Q '" (i, j) expresses the support 
of the match [=>]; received at the nth iteration from the 
matches /,<>/; in its neighbourhood Q(T). The iteration scheme 
can be initialised by assigning the normalized correlation 
coefficient to P’(i, j) and, ideally the process will terminate 
when an unambiguous match result is reached, that is when 
each point /; is matched with one candidate with probability 1, 
the probabilities for all other candidate matches for this point 
being zero. In practice the process is terminated if any one of 
the following 2 conditions holds: a. For each feature point /;, 
one of the match probabilities raj (j71,...,m) exceeds 1-g, 
where e««l. b. Pre-defined number of iterations has been 
reached. The match, which gains the highest probability P(i. j) 
(j71...m) is selected as the actual conjugate. By the 
refinement of relaxation technique, the feature point based 
matching method becomes more reliable and robust. 
3.4 Check and filter 
Even though the matching approach made full use of the 
advantages feature point sampling and useful refinement based 
on probability relaxation, we can't guarantee that the all match 
results are completely correct. In addition, the errors produced 
at the lower pyramid level often greatly influence the result at 
subsequent level. So a system of checking and eliminating 
blunders and false matches appears very important. 
So an error detection function has been developed, witch 
considers the smoothness constraint satisfaction scheme. For 
each match, a weighted mean approximation can be calculated 
with neighbouring points. If the difference between the match 
and the approximation exceeds a predefined threshold, we deem 
it is a false match and delete it The weight is distance 
dependent. The more distant is, the less the weight. The results 
1098 
b: 
b: 
m 
If 
pl 
eC 
or 
Th 
Th 
the 
Be 
the 
pol 
Fin 
the 
In « 
face 
coo 
eacl 
groi 
of 
poly 
Whe 
Corr 
and 
Tabl. 
cases 
in the 
to 1. 
paran 
contr 
strict 
18, 1 
RMS 
points 
Table 
block