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