A detailed evaluation of the lane models is also problematic, since it is difficult to measure a vehicle's true position within a lane, but a rough evaluation of the lane models is possible. Although regular training data from the field will be unlabelled, we labelled our data for testing purposes only. The label indicates the lane that the vehicle occupied for the given position. The system can find which cluster is closest to the position, and test if the cluster matches the label. For example, if a position's perpendicular distance to the centerline is 2.1 meters, and the closest cluster is centered at 2.0 meters, the system predicts that the vehicle is in the lane corresponding to that cluster. Although overall accuracy is important, the learning curve is also important here, because we want to know the minimum number of passes over a segment that yields acceptable results. For this experiment, instead of a fixed testing set evaluated against increasing amounts of training data, we incrementally treat each position trace first as testing data against the current lane models, then as training data to refine the lane models.
The remaining issue is matching clusters with labels. In our tests, we used integer labels starting at one for the rightmost lane. In our coordinate system, offsets increase as they move left, so smaller offsets correspond to lower lane numbers. Therefore, the evaluation matches the cluster with the smallest offset to the smallest lane label seen so far in training. It matches the cluster with the second-smallest offset to the second-smallest lane label seen so far, and so on. For example, if all the training data have come from lanes two and four, the system maps the smallest cluster to lane two and the second-smallest to lane four. If an offset is closest to any other cluster, it is automatically wrong. This means that if there is a spurious cluster with a very small offset, all other clusters will be ``bumped'' to the next lane label, probably making them all incorrect. Fortunately, this is not likely to happen, because the clustering algorithm deletes all clusters representing less than one percent of the data.
We evaluated the lane clustering process by assuming the best centerline model we have-- the result of centerline refinement on all 44 traces. With this centerline for all highway segments, we tested the cumulative lane prediction accuracy. For each trace, the system calculated the offsets from the centerline, then integrated the offsets into the current lane clusters using the incremental clustering algorithm presented in Section 5.2. For example, if all the offsets in the current trace were between 5.0 meters and 5.5 meters, and clustering previous traces had produced a lane at 5.1 meters, the system would predict that the vehicle was in this lane for all positions in the trace. The system would then update the lane by agglomerating the offsets into the lane cluster.
The accuracy of the trace is the percentage of positions in the trace whose nearest cluster matches its lane label. As the lanes get more data, the lane centers become more accurate and lane prediction accuracy improves. Figure 5 plots the average accuracy of the clustering algorithm over 50 random orderings of the traces. Surprisingly, the results are initially quite good, then drop slightly for a few traces. By the 44th trace, the performance is at or slightly higher than the initial level. We believe the initial good performance is due to our procedure for matching clusters to lanes. Since there are often samples of only one lane early in the experiment, the clustering algorithm will probably create only one cluster, and the mapping guarantees that the only cluster maps to the only tag, giving 100% accuracy. As more data become available, there are more clusters and more possibility of error. Overall accuracy probably never reaches 100% because of noisy GPS data and mislabelled points. These results encourage us to believe that, given an accurate centerline for a segment traversed by several traces, our system can confidently predict a vehicle's lane.
 |