IEEE Robotics & Automation Magazine - December 2013 - 25

other so as to potentially guarantee a good spatial triangulation. Then, the second elaboration step consists of a matching
process between the two sets of keypoints, performed using a
Pyramidal Lucas-Kanade algorithm [14]. As often happens
with image matching algorithms, some outlier might be present. To reduce this, a RANSAC-based outlier rejection algorithm on the epipolar constraint is performed [17]. Finally, the
normalized image coordinates, corresponding to the matched
keypoints, are computed. An example of this process on real
images is shown in Figure 3.
By using the extracted pairs of normalized image points
(the projections of the 3-D point p, expressed in the camera
frame, on the image planes of the cameras P1 = 6X 1 Y1@T
and P2 = 6X 2 Y2@T ), a spatial triangulation problem is
solved, thus estimating the position of the corresponding 3-D
points p (see Figure 4). A robust least-squares solution can be
found in [22], where the poses of the camera frames corresponding to the grabbed images are required.
The accuracy of the triangulation process increases if a large
baseline between the two camera frames is employed, i.e., the
normal distance between the two camera positions corresponds to the employed images. On the other hand, the accuracy of the vehicle odometry between camera poses degrades
with the distance traveled by the UAV. Moreover, to succeed in
the keypoints matching process, it is preferable to use images
that have been grabbed from the closest possible pose. These
demands are evidently in contrast and, therefore, a tradeoff
should be implemented. On the basis of the performed experimental tests, by selecting images grabbed at distances in a range
from 15-20 cm, a well-conditioned triangulation process can
be achieved with a good matching rate and with an odometry
drift that does not affect the accuracy of the overall process.
The criterion adopted for the image-pair selection from the
buffer is as follows: the last image stored in the buffer is considered as the first key-frame of the pair; the second one is chosen
in the key-frames buffer by considering the latest one grabbed
at a distance greater than a suitable threshold from the first one.
If no matches are found, a finite number of next images are
considered until a right pair is found. If this process fails, the
map is not updated during this step. Finally, the 3-D coordinates of points corresponding to the matched keypoints are
computed. These points are considered as obstacles candidates,
because they are not yet statistically robust. In the following

Figure 4. The triangulation process between keypoint optical rays
evaluated from images extracted in different positions and stored
into the buffer.

section, "3-D Occupancy Map," the use of these candidates for
the construction/update of the occupancy map is presented.
3-D Occupancy Map
A 3-D discrete occupancy map that is obtained by discretizing the vehicle's workspace with elementary cubes of equal
size is considered. From a general point of view, the size of the
cubes should be less than half the size of the vehicle along any
direction to ensure the safety of the system. Obviously,
smaller cubes increase the capability of the system to describe
the environment, but the required memory increases as well,
often without a real benefit for the navigation safety. Hence, a
suitable tradeoff must be considered. For example, with
respect to the environment of Figure 5 and a vehicle of
(50 # 50 # 20) cm size, cubes with 10-cm edge length have

Target

Object 1

Object 2

Figure 3. Examples of keypoints matching between images taken
from different positions and stored into the buffer.

Figure 5. The workspace of the experimental tests.

DECEMBER 2013

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2013