A Valley Detection for Path Planning

This paper presents a constrained valley detection algorithm. The intent is to find valleys in the map for the path planning that enables a robot or a vehicle to move safely. The constraint to the valley is a desired width and a desired depth to ensure the space for movement when a vehicle passes through the valley. We propose an algorithm to find valleys satisfying these 2 dimensional constraints. The merit of our algorithm is that the pre-processing and the post-processing are not necessary to eliminate undesired small valleys. The algorithm is validated through simulation using digitized elevation data.

Authors:

• In-Geun Lim
• Jin-Soo Kim
• Chirl-Hwa Lee

Keywords:

• valley
• width
• depth
• path planning.

References:

[1] E. W. Dijkstra. "A Note on Two Problems in Connection with Graphs",
Numerische Mathematic, 1959.
[2] Antonio M. Loİpez, Felipe Lumbreras, Joan Serrat, and Juan J. Villanueva,
"Evaluation of Methods for Ridges and Valley Detection", IEEE Trans.
Pattern Analysis and Machine Intelligence, vol. 21, no. 4, pp. 327-335,
April 1993.
[3] D. Page, A. Koschan, M. Abidi, and J. Overholt, "Ridge-Valley Path
Planning for 3D Terrains," in Proc. IEEE Int. Conf. Robotics and
Automation ICRA06, Orlando, FL, pp. 119-124, May 2006.
[4] R. Haralick, "Ridges and Valleys on Digital Images," Computer Vision,
Graphics, and Image Processing, vol. 22, no. 10, pp. 28-38, Apr. 1983.
[5] D. Eberly, R. Gardner, B. Morse, S. Pizer, and C. Scharlach, "Ridges for
Image Analysis," J. Math. Imaging and Vision, vol. 4, no. 4, pp. 353-373,
Dec. 1994.
[6] J. Gauch and S. Pizer, "Multiresolution Analysis of Ridges and Valleys
in Grey-Scale Images," IEEE Trans. Pattern Analysis and Machine
Intelligence, vol. 15, no. 6, pp. 635-646, June 1993.