within 1 pixel (0.3 m), which is theoretically acceptable given
the 1-foot (~0.33 m) resolution of the aerial image used. In
particular and considering the horizontal accuracy of the
aerial image of 2.1
RMS
, the method’s accuracy results show
similar performance. It is noted that due to occlusion by un-
derbrush, some tree stems were not detected at several poses.
These poses were therefore discarded and shown as gaps in
the rover path as seen in Figure 9 and Figure 10.
Four factors play a major role in determining the positional
accuracy of the localization algorithm:
• Accuracy of the input datasets (aerial and lidar). Some
trees that are visible in the lidar dataset may not have
visible crowns in aerial imagery due to occlusions by
taller trees.
• Validity of tree stem centers estimated from aerial
imagery. Tree crowns tend to merge in dense forests
rendering the task of delineation somewhat tricky and
not without uncertainty.
• Validity of tree stem centers estimated from lidar. Some
trees that are visible in the aerial image may not be
visible in the lidar dataset due to occlusions by other
trees, underbrush or other obstructions.
• Orthorectified images of canopies are corrected based
on ground relief rather than the canopies themselves.
The error associated with the orthorectification process
presents a challenge when attempting to localize close
to tall trees that may not be necessarily vertical. A po-
tential solution could utilize the on-board lidar to scan
tall tree stems and use their extracted height informa-
tion to perform re-orthorectification of the overhead
imagery. Alternatively, aerial lidar maps of tree cano-
pies could be used.
The last three factors are important because they can easily
affect the positional accuracy reported by the algorithm. If
several tree centers were mislabeled, the matching algorithm
would have difficulties finding the true matches. In cases
where a moderate number of erroneous tree centers are pres-
ent in a dataset,
ICP
would certainly provide a biased result
regardless of how robust the algorithm is.
Figure 9 and Figure 10 show that there is a problematic
area lying between the 30 and 60 Easting lines towards the
top of the paths where estimates from the localization algo-
rithm do not agree well with the true positions (3 to 4 m mean
error). Manual inspection of the lidar data of the area revealed
that it contains moderate stands of tall (>2 m height) thick
underbrush that obscure tree stems and lead to false labeling
of tree stems. The moderate presence of “false positive” stems
limits the success of the
ICP
algorithm regardless of how ro-
bust it is. This is because it becomes challenging to aggregate
enough consensus for a robust position estimate if there are
many more false positives than true stems in the data.
However, Figure 11 shows that the algorithm produces
consistent performance using different configurations of lidar
data as input. The variations in the error reported from path
to path are attributed to the different densities of false posi-
tives observed in each pose.
Conclusions and Future Work
In conclusion, the localization algorithm presented in this
paper has the following properties that make it significant: (a)
It enables rover position estimation by matching vision data
from ground lidar and overhead visible imagery of the area of
interest, (b) Aside from an initial geoposition estimate from
GPS
and an overhead image of the area, the algorithm does not
require any additional georeferenced landmarks to tie data
together or perform corrections, and (c) The algorithm pro-
vides a positioning capability that is decoupled from
GPS
to
allow on demand localization in situations when
GPS
becomes
unreliable or inaccessible.
The algorithm presented in this paper is considered a
prototype that has constraints and limitations. In this phase
of the project, the utility of the algorithm has been verified to
provide reasonable horizontal position estimates using real-
world data. Future improvements to the positioning accuracy
and use of the algorithm are planned. These will involve uti-
lizing lidar based aerial data of tree canopies to provide higher
resolution orthorectified data independent of ground relief
underneath the canopy. Additional improvements will also
focus on extending the algorithm’s capabilities to accurately
utilize off-nadir overhead imagery, enabling wider localization
coverage of robots using a single orthorectified image.
References
Besl, P., and N. McKay, 1992. A method for registration of 3D shapes,
IEEE Transactions on Pattern Analysis and Machine Intelligence
,
Vol. 14, No. 2, pp. 239–256.
Bleau, A., and L.J. Leon, 2000. Watershed-based segmentation and
region merging,
Computer Vision and Image Understanding
,
77,
pp.317–370.
Chetverikov, D., D. Svirko, D.Stepanov, and P. Krsek, 2002. The
trimmed iterative closest point algorithm,
Proceedings of
the 16
th
International Conference on Pattern Recognition
,
Vol.3, No., pp.545–548. Fischler, M.A., and R.C. Bolles, 1981.
Random sample consensus: A paradigm for model fitting with
applications to image analysis and automated cartography,
Communications of the ACM
, Vol.24, No.6.
Granger, S., and X. Pennec, 2002. Multi-scale EM-ICP: A fast and
robust approach for surface registration,
Proceedings of the 7
th
European Conference on Computer Vision
, Part IV, pp. 418–432.
Guivant, J., F. Mason, and E. Nebot, 2002. Simultaneous localization
and map building using natural features and absolute
information,
Robotics and Automation Systems
,
40, pp. 79–90.
Jian, B., and B.C. Vemuri, 2011. Robust point set registration using
Gaussian mixture models,
IEEE Transactions on Pattern Analysis
and Machine Intelligence
, 33(8):1633–1645.
Kee, C., B.W. Parkinson, and P. Axelrad, 1991. Wide area differential
GPS,
Navigation
, Vol. 38, No. 2, pp. 123–146.
Larsen, M., 1997. Crown modeling to find tree top positions in aerial
photographs,
Proceedings of the Third International Airborne
Remote Sensing Conference and Exhibition
, Vol. 2.
Leonard, J.J., and H.F. Durrant-Whyte, 1991. Simultaneous map
building and localization for an autonomous mobile robot,
Proceedings of the IEEE/RSJ International Workshop on
Intelligent Robots and Systems - Intelligence for Mechanical
Systems
, Vol. 3, pp.1442–1447.
Liu, B., M. Adams, and J. Ibanez-Guzman, 2005. Multi-aided inertial
navigation for ground vehicles in outdoor uneven environments,
IEEE International Conference on Robotics and Automation
(ICRA),
pp.4703–4708.
McDaniel, M.W., 2010.
Classification and Modeling of Forested
Terrain Using LiDAR Sensing
, S.M. dissertation, Massachusetts
Institute of Technology (MIT).
McDaniel, M., T. Nishihata, C. Brooks, P. Salesses and K. Iagnemma, 2012.
terrain classification and identification of tree stems using ground-
based LIDAR,
Journal of Field Robotics
, Vol. 29, No. 6, pp. 891–910.
Parkinson, B.W., and J.J. Spilker, 1996. Global Positioning System:
Part 1: GPS fundamentals, Part 2: GPS performance and error
effects; Vol. 2, Part 3: differential GPS and integrity monitoring,
Part 4: integrated navigation systems, Part 5: GPS navigation
applications, Part 6: special applications (Vol. 2),
AIAA
.
Wang, L., P. Gong, and G.S. Biging, 2004. Individual tree-crown
delineation and treetop detection in-spatial resolution aerial
imagery,
Photogrammetric Engineering & Remote Sensing
, Vol.
70, No. 3, pp. 351–357.
(Received 07 July 2014, accepted 11 March 2015, final version
07 May 2015)
846
November 2015
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
