Finding an accurate road centerline

Existing digital maps represent the centerline geometry of a road segment as a widely spaced sequence of latitude and longitude points, with an advertised accuracy of 15 meters, connected by line segments. We also represent geometry as a sequence of points, but at a much higher density of 10 meters to allow finer control. We also add estimated standard deviations for longitude and latitude to represent confidence in the point. We connected the points by linear interpolation. This is sufficient for low-curvature highways, but for roads with higher curvature, for better accuracy, or to reduce storage requirements, higher-order interpolation is possible. We have not addressed the issue of space efficiency of map representation.

The geometry refinement procedure iteratively improves the road geometry of a segment by performing a weighted average on the digital map with each trace. The map improvement process takes the current description of a map segment and a position trace corresponding to that segment, and produces a new and improved segment. Figure 3 illustrates the map improvement process for a short segment of map points. For each map point m with standard deviation $m_\sigma$, the procedure first finds the nearest point non the trace by linearly interpolating between the GPS trace points. The standard deviation $n_\sigma$ is the weighted average of the standard deviations of the surrounding GPS points. The new map point p is the average of m and n weighted by $m_\sigma$ and $n_\sigma$, and the new standard deviation is

$$p_\sigma = \sqrt{\frac{m_\sigma^2 \cdot n_\sigma^2}{m_\sigma^2 + n_\sigma^2}}.$$

  

Figure 3: ``Averaging'' a map and a position trace. In this case, the map is the baseline digital map with points interpolated every 10 meters. In general, the map line segments may not be collinear. The new map point is the average of the current map point and the closest trace point, weighted by the confidence in the map and the trace.

The net effect of these calculations for each point in the digital map is a weighted ``averaging'' of the map with a position trace. If the mean of the error distribution for the probe vehicle positions is zero, as assumed, then the weighted average will become more accurate as the number of traces increases. An interesting property of this procedure is that it does not compute the centerline of the road pavement, but instead weights the centerline toward the most-traveled lane. For example, if most vehicles travel along a segment in lane two and some in lane one, the centerline will be closer to lane two. Since the centerline is still parallel to the lanes, this property is not a serious issue.