A Valley Detection for Path Planning

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

Abstract:

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: valley, width, depth, path planning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331723

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.