Clustering offsets into lanes

To induce a lane model of a particular segment, we assume the system has an accurate geometrical representation of the centerline of the road, and that all lane centerlines are parallel to the centerline.² Since the lanes are parallel, the only parameter for each lane is the perpendicular distance to the centerline, which we call the offset.

We assume drivers generally are in a lane, so the perpendicular distance from most positions to the road centerline is an estimate of the offset for the lane. Since GPS is noisy and drivers are not always in the center of the lane, the mean of many samples should give a more accurate estimate of the true offset. Once the system has calculated an offset for each position in the position trace, the problem is to group these offsets into lanes and average them to find the lane centerline. Since the centerline is now accurate, we expect the hierarchical agglomerative clustering on offsets described in Section 4.2 to behave correctly.

Although our agglomerative clustering method is slow (O(n³) in the number of offsets), it has two important properties:

1.

It will never merge two lanes into one, because the procedure will terminate if the closest clusters are farther apart than the minimum lane width.

2.

It makes no prior assumptions on the number of lanes.

If the system incrementally builds the lane models from the same centerline, we can dramatically improve the speed of the algorithm for each iteration with the results of the previous traces. If the previous iteration processed m offsets and found N lanes, with $N \ll m$, and the current iteration is processing n offsets, the original algorithm creates one lane for all m+n offsets. Instead, the incremental algorithm creates one lane for the N known lanes and the n new points. This version essentially integrates new offsets into the lane structure, instead of recomputing the lane structure from scratch. To avoid spurious lanes (e.g., from very noisy position data), we require that each cluster represent a certain percentage of the data. For our experiments, the threshold was one percent.