. Istanbul 2004
rulings of the
1d by the angle
normal and the
olute residual.
he unavoidable
'andidates from
e generation of
ire is located at
1 information is
ilatching can be
METHOD
it view points,
yrrespondences.
n developed for
hotogrammetric
between the
he patches have
orientation in
nsider what is
ting coefficient
(1
or observed 3D
yn the surface of
2)
ssible in a final
nensional object
o the rectified z-
axis (perpendicularity) during the whole data acquisition from
the different view points of the scene, the ascending order of the
corresponding candidates in the different evaluated feature lists
is identical, which will be described more detailed in section 4.
Erop = j (Preighbor ? C jeighbor ) (3)
3.2 The matching strategy
Due to the fact that the amount of accepted features can be
controlled by the rigidity of particular thresholds, a simple
strategy for the matching is to assess all possibilities of
combinations. This is only possible if criteria can be used
whose influence is restricted to the individual point.
For combinatorial criteria optimization methods, e.g. graph cuts
(Huber et al. 2001) or Simulated Annealing (Weisensee and
Wendt, 2003, Luck et al., 2000) have to be used. To avoid
optimization methods Chen et al. (1999) used a modified
RANSAC (Random sample consensus) method. They randomly
select the minimum size of sets to estimate the transformation
parameters and assess the solution. They stop their algorithm,
when the consensus is found.
In the following the metropolis algorithm is briefly introduced,
to give an idea about the principle (cf. Press et al. 1992).
3.2.1 Simulated Annealing — the Metropolis Algorithm
The term annealing originates from the controlled heating and
cooling of material, e.g. metal. In case of liquefied metal a slow
cooling leads to a regular structure having a low energy level
while a fast cooling leads to irregular structure at a high energy
level. In a controlled operation of heating and cooling the
energy of the material rises temporarily but in total it can be
reduced to a global minimum. Thus, the metal is tempered. The
transfer of this principle to a procedure for the allocation of
corresponding candidates leads to an algorithm as shown in fig.
6.
The solution for the unknown corresponding candidates is
initialized by random numbers. Depending on the energy of the
initial solution a starting value for the equivalent of the
temperature 7, is determined. The relation given in equation (4)
has been derived in (Weisensee, 1992) to assure that a new
correspondence will be accepted by the algorithm at
. temperature 7, according to equation (5) with a probability of
approximately 0.5 even if the energy of the system increases.
L>AL%1 4 (4)
Starting from this temperature the system is cooled down after it
has reached the equilibrium, i.e. when the energy of the system
does not decrease any more or if a specified number of
iterations have been processed. Until equilibrium is achieved,
new corresponding candidates are randomly allocated. They
give rise to a change of energy AÆ compared with the previous
solution. A new solution is accepted always if the energy
decreases. Otherwise, it is accepted with a probability
AE.) = Iz |
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
with T, » 0. k- Boltzmann constant (5)
Initialyze,
Warming up
Ÿ
New Solution {|<
Ÿ
Calculate Energy
+ Y
Accept Accept f(AE, T)
*
Y
Decrement T
*
X.
Evaluate
Corresponding
Candidates
Figure 6: Principle of the metropolis algorithm
depending on the change in energy AE and the current
temperature 7; of the system. The temperature is reduced by a
constant factor qc which leads to a geometric series of numbers
T.. Ti ge with
1
gc 0. (6)
This scheme is repeated until the system is frozen.
4. VALIDATION OF THE MATCHING METHOD
Here, the processing of the data set is described. First the
features will be extracted with the IBPC operator. For the
corner extraction with SUSAN a radiometric threshold of t=20
grey values and g = 50% of the area of the circular mask is
used. For the geometric acceptance a viewing angle of max. 60°
is allowed and a max. point residual of 300 mm to the adjusted
plane. The discrete 31 x 31 pixels orthoimage is calculated with
a resolution of 30 mm per pixel in object space. The amount of
SUSAN features per photogrammetric image is reduced from
approximately 10 000 to approximately 500 features.
For the validation all possible combinations of candidates are
calculated. Only the combinations with a non-ambiguous
correlation coefficient in relation to the other solutions are
accepted. Here, the threshold is set that the largest correlation
coefficient is 10% larger than the second largest. This gives