ISPRS Commission III, Vol.34, Part 3A .Photogrammetric Computer Vision*, Graz, 2002 
2. BACKGROUND 
2. The Hough Transform 
Hough (1962) introduced a method for parameters estimation 
by way of a voting scheme. The basic principle behind this 
approach was to switch the roles of parameters and spatial 
variables. Hough transform is usually implemented through an 
accumulator array, which is an n-dimensional, discrete space, 
where n is the number of parameters under consideration. In 
this array, the cell with the maximum number of hits yields the 
parameters we are looking for. The variables contributing to the 
peak in the accumulator array can be tracked and identified. For 
more details, the reader can refer to (Leavers, 1993). 
2.2 The Modified Iterated Hough Transform (MIHT) for 
Robust Parameter Estimation 
Hough transform can be modified and used to estimate the 
parameters of a mathematical model relating entities of two data 
sets. In this approach, we assume no knowledge of 
correspondence and do not require complete matching between 
entities. As a result of the parameter estimation, the 
correspondence is implicitly determined. The method is 
outlined as follows. 
First, a hypothesis is generated that an entity in the first data set 
corresponds to an entity in the second one. The correspondence 
between conjugate entities of the data sets is expressed by a 
mathematical function. Using the hypothesized match, this 
mathematical function yields an observation equation(s). The 
parameters of the mathematical relation can be estimated 
simultaneously or sequentially, depending on the number of 
hypothesized matches simultaneously considered. All possible 
entity matches are evaluated, and the results (parameter 
estimations) are represented in an accumulator array. The 
accumulator array will exhibit a peak at the location of the 
correct parameter solution. By tracking the matched entities that 
contributed to the peak, the correspondence is determined. 
The number of parameters being simultaneously solved for 
determines the dimension of the accumulator array. In order to 
solve n parameters simultaneously, one must utilize the number 
of hypothesized entity matches needed to generate the required 
n equations. However, this approach is not practical. 
Simultaneous evaluation of all permutations of entities leads to 
combinatorial explosion. For example, if there are x entities in 
data set one and y entities in data set two, solving n parameters 
xy! 
(xy-n) nm 
(assuming that each matching hypothesis yields one equation). 
In addition, the memory requirements of an n dimensional 
accumulator array create another problem. 
simultaneously would lead to combinations 
Random Sample Consensus (RANSAC) is another alternative 
for fitting a model to experimental data (Fischler and Bolles, 
1981). Rather than using large data set with high percentage of 
blunders and trying to eliminate invalid matched, RANSAC 
starts by a and consistent data set whenever possible. This 
method is quite similar to using the modified Hough transform 
discussed in the previous paragraph, to simultaneously solve for 
all the involved parameters. 
An alternative approach is to solve for the parameters 
sequentially in an iterative manner (starting from some 
initial/approximate values), updating the approximations at each 
step. Consequentially, the accumulator array becomes one- 
dimensional and the memory problem disappears. Also, if there 
are x elements in data set one and y elements in data set two, the 
total number of evaluated entity matches becomes xy, reducing 
the computational complexity of the problem. After each 
iteration, the approximations are updated and the cell size of the 
accumulator array can be reduced to reflect the improvement in 
the quality of the approximate values of the unknown 
parameters. In this manner, the parameters can be estimated 
with high accuracy. The convergence of this approach depends 
on the correlation among the parameters and the non-linearity 
of the transformation function. Highly non-linear 
transformations have a slower convergence rate and would 
require more iterations. 
The basic steps for implementing the MIHT for parameter 
estimation are as follows: 1) A mathematical model is 
established that relates corresponding entities of two data sets. 
The relation between the data sets can be described as a 
function of its parameters: f(p;, py,...p,). 2) An accumulator 
array is formed for the parameters. The accumulator array is a 
discrete tessellation of the range of expected parameter 
solutions. The dimension of the accumulator array depends on 
the number of parameters to be simultaneously solved, which is 
related to the number of entity pairings simultaneously 
considered as well as the number of equations provided by a 
single matching hypothesis. 3) Approximations are made for 
parameters which are not yet to be determined. The cell size of 
the accumulator array depends on the quality of the initial 
approximations; poor approximations will require larger cell 
sizes. 4) Every possible match between individual entities of the 
two data sets is evaluated, incrementing the accumulator array 
at the location of the resulting solution. 5) After all possible 
matches have been considered, the maximum peak in the 
accumulator array will indicate the correct solution of the 
parameter(s). Only one peak is expected for a given 
accumulator array. 6) After each parameter is determined 
(usually in a sequential manner), the approximations are 
updated. For the next iteration, the accumulator array cell size is 
decreased, and steps 2-6 are repeated. Detailed explanation 
about the MIHT can be found in (Habib et al, 2000a) and 
(Habib et al, 2001). 
2.3 Single Photo Resection (SPR) 
In SPR, the collinearity model (Equation 1) is used to relate 
points in the image with corresponding points in the object 
space, and this relation is expressed as a function of the EOP. 
Traditionally, the parameters are estimated by way of a least 
squares adjustment involving measured control points in the 
image. At least three control points are required to estimate the 
six EOP. The introduction of more than three points increases 
the redundancy and strengthens the solution of the parameters. 
Xx, X, =X, (1) 
MV — A R' (v, 0, Kk) Yale 
mé 2,742, 
where 
A: Scale 
Xj, Vr Image coordinates of i point 
X,Y. Z Object coordinates of i point 
Xp Yo. C The camera interior orientation parameters. 
X, Yo, Zo, €, 0, X: The EOP of the camera exposure station. 
A - 151