Road Maps from Clusters of Line Segments of Multiple Sources

• US 20140095062A1
• Filed: 09/28/2012
• Published: 04/03/2014
• Est. Priority Date: 09/28/2012
• Status: Abandoned Application

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: WANG, Yin, LIU, Xuemei, Zhu, Yanmin
• Application Number:
  US13/630,253
• Publication Number:
  US 20140095062A1
• Time in Patent Office: Days
• US Class Current: 701/409
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles

Abstract

A method of generating a road map from clusters of line segments of multiple datapoint sources. The method includes defining line segments for the datapoint sources between consecutive samples from the sources, grouping the line segments into clusters according to a position criterion, applying curve fitting to the clusters to obtain centerlines, and generating a road map from the center lines.

Claims

1. A method of generating a road map from clusters of line segments of multiple datapoint sources, the method comprising:

defining line segments for the datapoint sources between consecutive samples from the sources;

grouping the line segments into clusters according to a position criterion;

applying curve fitting to the clusters to obtain centerlines; and

generating a road map from the centerlines.

2. The method of claim 1 and further comprising removing any line segments that violate a directional constraint.

3. The method of claim 2 wherein the directional constraint comprises a maximum angle between a line segment and an orientation of a datapoint that defines that line segment.

4. The method of claim 1 wherein the position criterion comprises one or more of a maximum separation angle between line segments and a maximum distance between line segments.

5. The method of claim 1 wherein grouping the line segments comprises splitting a cluster that contains line segments indicative of divergent road centerlines by:

defining a backbone curve from a plurality of samples adjacent an edge of a cluster, the samples having similar orientations;

adding to the backbone curve any other samples that satisfy a divergence criterion with respect to the samples in the backbone curve;

moving all the samples in the backbone curve to a new cluster; and

repeating until all samples have been added to a backbone curve.

6. The method of claim 5 wherein the divergence criterion comprises a distance between samples and a difference of orientation between samples.

7. The method of claim 1 wherein curve fitting comprises shape-aware curve fitting according to how many direction changes are in a cluster.

8. The method of claim 1 wherein curve fitting comprises B-spline curve fitting.

9. The method of claim 8 wherein curve fitting comprises determining how many direction changes are in a cluster and identifying a quantity of control points for curve fitting that cluster according to the number of direction changes.

10. A road map generation system including clustering of segments from multiple datapoint sources, the system comprising:

a plurality of sensors to provide datapoints indicative of positions and orientations of the datapoint sources;

a receiver in communication with the sensors;

a map display device; and

a server in communication with the receiver and the map display device to define line segments between the datapoints, group any line segments that are close to each other into a cluster, and generate a road map on the map display device by curve fitting the clusters.

11. The system of claim 10 wherein the datapoint sources comprise motor vehicles.

12. The system of claim 10 wherein the sensors comprise GPS units and the receiver comprises a cell phone network.

13. The system of claim 10 wherein the map display device comprises a printer.

14. The system of claim 10 wherein grouping any line segments that are close to each other into a cluster comprises grouping into a cluster any line segments that are closer together than a predetermined distance and that have orientations that differ by less than a predetermined separation angle.

15. The system of claim 14 and further comprising splitting a cluster that contains line segments indicative of divergent road centerlines into two or more clusters each containing line segments indicative of only one road centerline.