Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31103
A Valley Detection for Path Planning

Authors: In-Geun Lim, Jin-Soo Kim, Chirl-Hwa Lee


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.

Keywords: Path Planning, width, depth, valley

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1181


[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.