Using DP Towards A Shortest Path Problem-Related Application

Jianhao Jiao, Rui Fan, Han Ma, Ming Liu

Abstract

The detection of curved lanes is still challenging for autonomous driving systems. Although current cutting-edge approaches have performed well in real applications, most of them are based on strict model assumptions. Similar to other visual recognition tasks, lane detection can be formulated as a two-dimensional graph searching problem, which can be solved by finding several optimal paths along with line segments and boundaries. In this paper, we present a directed graph model, in which dynamic programming is used to deal with a specific shortest path problem. This model is particularly suitable to represent objects with long continuous shape structure, e.g., lanes and roads. We apply the designed model and proposed an algorithm for detecting lanes by formulating it as the shortest path problem. To evaluate the performance of our proposed algorithm, we tested five sequences (including 1573 frames) from the KITTI database. The results showed that our method achieves an average successful detection precision of 97.5%.

1. Introduction

Lane detection is a cornerstone of autonomous vehicle perception, providing the "traversable area" necessary for safe navigation. However, detecting curved lanes remains a significant challenge. Most existing methods rely on strict geometric assumptions or precise Vanishing Point (VP) estimation. These "rigid" models often fail in complex environments like sharp turns, intersections, or under adverse conditions like heavy shadows and occlusions. This research seeks a more flexible approach that doesn't rely on a single global model but can still maintain the structural continuity of a lane. The core idea is to treat the image as a graph where the "shortest path" corresponds to the most likely lane boundary.

2. Methodology

The proposed system follows a multi-stage pipeline to transform raw sensor data into structured lane representations.

The proposed lane detection pipeline, including pre-processing, path searching via dynamic programming, and model fitting.

2.1 Pre-processing and Graph Construction

The process begins with Inverse Perspective Mapping (IPM) to convert the front-facing camera view into a "bird's-eye view," which linearizes lanes. Canny edge detection and grayscale normalization are then applied to create a feature map. A Directed Acyclic Graph (DAG) is constructed where nodes are pixels in the IPM image. The graph utilizes a "bottom-up" structure: each node connects only to a small neighborhood ($2k+1$ pixels) in the row immediately above it. This constrained search space transforms a complex global search into a highly efficient local one, resulting in $O(|P|)$ time complexity.

2.2 Shortest Path via Dynamic Programming

To identify the lane, the system solves a Shortest Path Problem (SPP) using Dynamic Programming (DP). The cost function $F$ is a weighted sum of edge and intensity data. A key innovation is the introduction of a regularization term, $\lambda j^2$ (where $j$ is horizontal movement), into the DP recurrence. This term penalizes sharp horizontal jumps, forcing the algorithm to find smooth, continuous paths even in noisy data. By adjusting $\lambda$, the system's "stiffness" can be tuned to ignore random noise like asphalt cracks.

2.3 Model Fitting

Once the DP identifies a path, RANSAC and a parabolic model ($f(v) = \beta_2v^2 + \beta_1v + \beta_0$) are used to fit the final lane line, effectively filtering out remaining outliers. To detect multiple lanes, the algorithm iteratively finds the shortest path, records it, "zeros out" the costs in that area, and repeats the process.

3. Results and Evaluation

The algorithm was evaluated using the KITTI dataset, specifically five sequences from the "Road Category" encompassing 1,573 frames and 3,146 individual lane markings.

Qualitative results of the lane detection algorithm on various road sequences from the KITTI dataset.

The method achieved an average successful detection precision of 97.5%, outperforming a baseline vanishing-point-based method (94.5%). The system showed high reliability (99%+) in standard road geometries, demonstrating the effectiveness of the DP approach for maintaining structural continuity.

4. Conclusion

While the system achieves high precision, it remains sensitive to environmental factors. Extreme over-exposure, heavy occlusion (e.g., grass), or strong shadows can create false edges that mislead the DP algorithm. Future work will focus on improving start/destination node detection, fusing stereo IPM images for a wider field of view, and addressing complex "multi-VP" scenarios such as multi-way crossings.

Summary updated

Abstract

The detection of curved lanes is still challenging for autonomous driving systems. Although current cutting-edge approaches have performed well in real applications, most of them are based on strict model assumptions. Similar to other visual recognition tasks, lane detection can be formulated as a two-dimensional graph searching problem, which can be solved by finding several optimal paths along with line segments and boundaries. In this paper, we present a directed graph model, in which dynamic programming is used to deal with a specific shortest path problem. This model is particularly suitable to represent objects with long continuous shape structure, e.g., lanes and roads. We apply the designed model and proposed an algorithm for detecting lanes by formulating it as the shortest path problem. To evaluate the performance of our proposed algorithm, we tested five sequences (including 1573 frames) from the KITTI database. The results showed that our method achieves an average successful detection precision of 97.5%.
BibTeX
@inproceedings{jiao2019using,
  author = {Jianhao Jiao and Rui Fan and Han Ma and Ming Liu},
  title = {{Using DP Towards A Shortest Path Problem-Related Application}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2019},
  url = {https://openreview.net/forum?id=-kzYgDvew1YO},
}
Figure