Remediating dissimilarities between digital maps and ground truth data via dissimilarity threshold tuning

• US 10,801,844 B2
• Filed: 08/06/2018
• Issued: 10/13/2020
• Est. Priority Date: 12/31/2017
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Viskic, Ines, Starhill, Philip, Dalapathi, Divya, Chen, Danny H.
• Primary Examiner(s): To, Tuan C
• Application Number:
  US16/056,109
• Publication Number:
  US 20190204090A1
• Time in Patent Office: 799 Days
• Field of Search: 701446
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3859 Differential updating map data
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/909 using geographical or spatial information, e.g. location spatiotemporally dependent retrieval from the web G06F16/9537
• CPC Class Codes: G06F 18/2163 Partitioning the feature space
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

A network system determines and remediates dissimilarities between a digital map and trace data of a road network in an area as service providers and service requesters coordinate service using the road network in the area. To determine dissimilarities the network system can select and convert a digital map, aggregate received trace data into trace data accurately representing the road network in the area, generate a visualization of the dissimilarities, and remediate the dissimilarities using a variety of methods. A first remediation method includes verifying the dissimilarity using a single service provider, a second method includes verifying the dissimilarity leveraging multiple service providers, and a third method modifies the methods used to determine dissimilarities. After remediation, the network system can generate a map of the area that accurately represents the road network in the area.

Claims

1. A computer-executed method for verifying a digital map data, the method comprising:

receiving, for each of a plurality of road segments, a set of trace data, each of the trace data in the set collected by a mobile computing device traversing a road segment of a plurality of road segments;

determining, for each of the plurality of road segments, a dissimilarity score based upon differences between the set of trace data for the road segment and stored map data for the road segment;

determining, for each of the plurality of road segments, whether the dissimilarity score exceeds a first threshold dissimilarity score;

responsive to the dissimilarity score exceeding the first threshold dissimilarity score for more than an expected number of the plurality of road segments;

increasing the first threshold dissimilarity score to form a second threshold dissimilarity score, such that the dissimilarity scores for the plurality of road segments do not exceed the second threshold dissimilarity score for more than the expected number of the plurality of road segments;

selecting for verification the road segments of the plurality of road segments having a dissimilarity score exceeding the second threshold dissimilarity score; and

requesting verification of the selected road segments.

2. The computer-executed method of claim 1, wherein the differences between the road segment and the stored map data for the road segment include a difference in position of the trace data of the road segment and the stored map data for the road segment.

3. The computer-executed method of claim 1, wherein the differences between the road segment and the stored map data for the road segment include a difference in direction of the trace data of the road segment and the stored map data for the road segment.

4. The computer-executed method of claim 1, wherein the differences between the road segment and the stored map data for the road segment include a difference in a geometric shape of the trace data of the road segment and the stored map data for the road segment.

5. The computer-executed method of claim 1, wherein the second threshold dissimilarity score is based on a second plurality of road segments similar to the plurality of road segments.

6. The computer executed of claim 1, wherein the second threshold dissimilarity score is based on the area containing the plurality of road segments.

7. The computer-executed method of claim 1, comprising:

determining a second threshold dissimilarity score for the plurality of road segments, based on a plurality of previously observed dissimilarity scores for similar plurality of read segments.

8. The computer-executed method of claim 1, comprising:

determining a first threshold dissimilarity score for the plurality of road segments, based on a plurality of previously observed dissimilarity scores for similar plurality of read segments.

9. The computer-executed method of claim 1, wherein the first threshold dissimilarity score is based on a second plurality of road segments similar to the plurality of road segments.

10. The computer executed method of claim 1, wherein the second threshold dissimilarity score is based on the area containing the plurality of road segments.

11. A non-transitory computer-readable storage medium storing instructions, the instructions that when executed by one or more processors cause the one or more processors to:

receive, for each of a plurality of road segments, a set of trace data, each of the trace data in the set collected by a mobile computing device traversing a road segment of a plurality of road segments;

determine, for each of the plurality of road segments, a dissimilarity score based upon differences between the set of trace data for the road segment and stored map data for the road segment;

determine, for each of the plurality of road segments, whether the dissimilarity score exceeds a first threshold dissimilarity score;

responsive to the dissimilarity score exceeding the first threshold dissimilarity score for more than an expected number of the plurality of road segments;

increase the first threshold dissimilarity score to form a second threshold dissimilarity score, such that the dissimilarity scores for the plurality of road segments do not exceed the second threshold dissimilarity score for more than the expected number of the plurality of road segments;

select for verification the road segments of the plurality of road segments having a dissimilarity score exceeding the second threshold dissimilarity score; and

request verification of the selected road segments.

12. The non-transitory computer-readable storage medium of claim 11, wherein the differences between the road segment and the stored map data for the road segment include a difference in position of the trace data of the road segment and the stored map data for the road segment.

13. The non-transitory computer-readable storage medium of claim 11, wherein the differences between the road segment and the stored map data for the road segment include a difference in direction of the trace data of the road segment and the stored map data for the road segment.

14. The non-transitory computer-readable storage medium of claim 11, wherein the differences between the road segment and the stored map data for the road segment include a difference in a geometric shape of the trace data of the road segment and the stored map data for the road segment.

15. The non-transitory computer-readable storage medium of claim 11, wherein the second threshold dissimilarity score is based on a second plurality of road segments similar to the plurality of road segments.

16. The non-transitory computer-readable storage medium of claim 11, wherein the second threshold dissimilarity score is based on the area containing the plurality of road segments.

17. The non-transitory computer-readable storage medium of claim 11, wherein the computer instructions further cause the processor to:

determine a second threshold dissimilarity score for the plurality of road segments, based on a plurality of previously observed dissimilarity scores for similar plurality of read segments.

18. The non-transitory computer-readable storage medium of claim 11, wherein the computer instructions further cause the processor to:

determine a first threshold dissimilarity score for the plurality of road segments, based on a plurality of previously observed dissimilarity scores for similar plurality of read segments.

19. The non-transitory computer-readable storage medium of claim 11, wherein the first threshold dissimilarity score is based on a second plurality of road segments similar to the plurality of road segments.

20. The non-transitory computer-readable storage medium of claim 11, wherein the second threshold dissimilarity score is based on the area containing the plurality of road segments.