Graphics Reference
In-Depth Information
To limit the edge complexity of the graph, edges need to be heuristically pruned
during operation. Removing an edge from the graph is equivalent to discarding the
information represented by the edge, as though the observation or measurement had
never been made.
One simple approach to limiting the number of edges is to maintain a priority
queue of nodes with degrees exceeding a fixed, predetermined bound. This queue
needs to be updated only when edges are added to the graph (measurements or node
removals). Edges are removed from each node in the queue until no node degrees
exceed the bound.
The heuristic operates as follows: the edges of a high-degree node
n
are examined
one at a time. If the opposite endpoint through edge
e
is not connected to
n
through a
path that excludes
e
, with length under a predetermined bound, then
e
is not eligible
for removal, as the graph would be potentially disconnected. The eligible edge with
the least residual is deleted. Of the edges incident to
n
, such an edge is in least
disagreement with the current state of the graph, and thus its removal should least
affect the graph optimum.
This simple, greedy heuristic does not consider the collective effect of removing
multiple edges in series. Nonetheless, our evaluation shows that it performs ade-
quately.
2.9 Evaluation
We use three indoor sequences (
) to evaluate the performance
of the system and the effects of graph complexity reduction.
Seq1
,
Seq2
,
Seq3
Seq1
and
Seq2
were
collected using an Evolution Robotics Scorpion, and
with an iRobot Roomba.
In each instance, the robot was equipped with a web camera and wheel odometry.
Fiducials placed in the environment were observed by a SICK NAV200 laser range
finder mounted on the robot to provide ground truth.
The sequence parameters are described in Table
2.2
, and example images are
shown in Fig.
2.5
. The ground truth trajectories are shown in Fig.
2.6
.
Seq3
Table 2.2
Test sequences
Seq1
Seq2
Seq3
Environment
Warehouse
Home
Office
Frame rate (Hz)
1.5
1.5
3.0
Timesteps
1,035
1,822
3,896
Extent (m)
24
×
12
20
×
9
19
×
10
Views created
41
103
140
