Robust lane marking detection remains a challenge, particularly in temperate climates where markings degrade rapidly due to winter conditions and snow removal efforts. In previous work, dynamic Bayesian networks with heuristic features were used with the feature distributions trained using semi-supervised expectation maximization, which greatly reduced sensitivity to initialization. This work has been extended in three important respects. First, the tracking formulation used in previous work has been corrected to prevent false positives in situations where only poor RANSAC hypotheses were generated. Second, the null hypothesis is reformulated to guarantee that detected hypotheses satisfy a minimum likelihood. Third, the computational requirements have been greatly reduced by computing an upper bound on the marginal likelihood of all part hypotheses upon generation and rejecting parts with an upper bound less likely than the null hypothesis. Therefore, parts that could never surpass the null hypotheses are excluded from contributing to the n2 complexity of the tracking and pairing processes. These improvements have led to real-time operation at the frame rate of the stereo camera and robust detection results on the evaluation dataset. The evaluation and training datasets were obtained from geographically distinct regions, both with significantly degraded lane markings.