187 
In: Paparoditis N., Pierrot-Deseilligny M.. Mallet C... Tournaire O. (Eds). IAPRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3. 2010 
Figure 1: An image with green dots drawn on it to show the sparse 
3D points found during calibration using SURF. 
Comelis et al. also detects the location of any cars in the scene 
to improve its visual reconstruction. Lhullier et al. (Lhuillier 
and Quan, 2005) proposed a quasi-dense approach to 3D surface 
model acquisition from uncalibrated images. Sparse matching is 
first applied, then in the neighborhood of the matched points, new 
matches are found based on a combination of local constraints 
such as correlation, gradient disparity, and confidence. 
The method proposed in (Louchet, 1999) searches for 3D points 
using the images from two calibrated cameras for the purpose 
of detecting obstacles in front of a moving robot. They use an 
evolutionary algorithm in which a set of 3D points is evolved to 
correspond to the surfaces of objects, and to not be too closely 
concentrated in one area of the scene. These goals are achieved 
by assigning a fitness value to each point that depends on (1) the 
image gradient of the point’s projection onto one of the images, 
(2) the similarity measure betw'een the point’s projections onto 
the two images, and (3) the proximity of this point to other points 
in 3D. A linear weighted average of a small subset of points from 
the current generation, along with random mutations, are used to 
evolve the next generation of points. 
3 A 2D IMAGE AND ID DEPTH HEURISTIC SEARCH 
This heuristic attempts to find points in the 3D world coordinate 
frame that correspond to the surfaces of stationary objects that are 
visible in the scene. The input to this algorithm is comprised of a 
set of calibrated images such that any point in the world reference 
frame can be projected onto each of these images with reasonable 
accuracy. Optionally, in addition to the calibrated images, a set of 
image points that are known to match in two or more of the input 
images can also be used to initialize the algorithm. 
The algorithm first detects a set of candidate pixels in a refer 
ence image T r . In this paper, a candidate pixel is any pixel that 
lies on an edge since edges are useful features for detecting ob 
jects in the scene, and edges occur more frequently than SURF 
and SIFT features. The location X of a candidate point in the 
three dimensional world coordinate frame is found by searching 
for the pixel in a neighboring image /„ that most closely matches 
the pixel in J r . This search is performed along the corresponding 
epipolar curve in /„. The coordinates of X are computed using 
the matching image pixels in I r and I n ■ To further test that X is 
indeed correct, X is projected onto each of the images, except I r 
and /„, to see if any of these projections match with the projec 
tion of X onto I r . 
To carry out the detection of edge pixels, a multi-start search 
method similar to the flies algorithm (Louchet, 1999) is used. 
The multi-start search methodology uses a set of agents that each 
behave according to a set of rules. In this algorithm each agent 
searches I r for an edge pixel using a combination of local and 
line searches, and random jumps. 
For each combination of pairs of images (7 r ,/„) in the set of 
input images, the algorithm proceeds as follows: 
1. Each agent randomly chooses a pixel in I r as its starting 
point. 
2. While the stopping condition (Section 3.3.1) is not satisfied, 
each agent does the following: 
(a) Search for an edge pixel using the line search (Section 
3.2.1) . If the line search finds an edge pixel that has 
already been found by any agent, then go to Step 2e. 
(b) Search along the epipolar curve in /„ for the pixel that 
best matches the corresponding pixel in I r (Section 
3.1) . 
(c) If the match search is successful then check the condi 
tions (Section 3.3) to determine if the 3D point corre 
sponding to this match will be added to the set of good 
points, and add or discard the match accordingly. If 
the match is discarded then go to Step 2e. 
(d) Perform a local search (Section 3.2.2) to find the next 
edge pixel. If the local search is successful then go to 
Step 2b. 
(e) Change this agent’s location in I r by adding a nor 
mally distributed random two dimensional vector to 
its current position. The normal distribution has a 
mean of 0 and a standard deviation that is set as a mul 
tiple of the desired density of good solution points in 
Ir. 
(f) Go to Step 2a. 
3.1 Match Search 
The search for a pixel in an image /„ that matches a given pixel p r 
in the reference image I r is performed by searching every pixel 
p n along the corresponding epipolar curve in This search is 
performed if and only if p r is an edge pixel. Let X r be the three 
dimensional point corresponding to p r in the coordinate frame of 
I r . Each pixel on the epipolar curve in I n is found by quantis 
ing the distance d r x between X r and the focal point f r of I r 
so that two or more values of X r do not project onto the same 
pixel in I n . This contrasts with the method proposed by Louchet 
(Louchet, 1999), which treats d r x as a continuous value. Since 
there are many values of d r x that correspond to the same pixel 
in I n , treating d r x as a continuous value may result in wasted 
computation time. 
The similarity measure M* n used in this paper is computed us 
ing Equation 1. It is the normalized sum of square differences 
between the intensities I r (p) of all pixels p within a square neigh 
borhood N r of p r , and the corresponding intensities / n (p-.n)), 
where is the projection of p onto 
m£ = {I) 
\J^2 P eN r ^ r ^P) 2 x ^2peN r Ir{P~n)) 2 
The sum of square differences is used assuming that the images 
were captured under similar lighting conditions. Projecting pixels 
in I n onto I r in this way reduces the effect of scale differences 
and image warping on the similarity measure. This assumes that 
every part of the surface in the scene that is projected onto N rn 
is the same distance from the focal point of I r ■ Although this 
assumption is not generally correct, neighborhood projection still 
works better than not using it. N rn is centered on p r and has a 
size of 21 x 21. 
All of the following conditions must be true for p n to be consid 
ered as a match for p r . Note that p r is an edge pixel.