Clustering observations of objects along roads for navigation-related operations

• US 10,074,270 B2
• Filed: 07/18/2017
• Issued: 09/11/2018
• Est. Priority Date: 07/20/2016
• Status: Active Grant

• Current Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Original Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Inventors: Ivanov, Volodymyr, Pryakhin, Alexey, Borshch, Ievgenii
• Primary Examiner(s): Nguyen, Tan Quang
• Application Number:
  US15/653,321
• Publication Number:
  US 20180025628A1
• Time in Patent Office: 420 Days
• Field of Search: 701117
• CPC Class Codes: G01C 15/002 Active optical surveying means optical plumbing G01C15/105
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/28 with correlation of data from several navigational instruments
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01S 19/51 Relative positioning
• CPC Class Codes: G01S 19/53 Determining attitude
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 9/44526 Plug-ins; Add-ons
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/052 with provision for determining speed or overspeed speed measuring in general G01P
• CPC Class Codes: G08G 1/093 : Data selection, e.g. prioritizing information, managing message queues, selecting the information to be output
• CPC Class Codes: G08G 1/09623 : Systems involving the acquisition of information from passive traffic signs by means mounted on the vehicle G08G1/0967 takes precedence
• CPC Class Codes: G08G 1/0967 : Systems involving transmission of highway information, e.g. weather, speed limits transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/096716 : where the received information does not generate an automatic action on the vehicle control
• CPC Class Codes: G08G 1/20 : Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Abstract

In one embodiment, a cluster application generates navigation-related data based on observations received from vehicles. In operation, the cluster application computes an oriented distance between two observed object positions based on a heading, where each observed object position is associated with a different one of two observations. The cluster application then generates a cluster that includes the two observations based on the oriented distance. Subsequently, the cluster application computes an object position that is associated with the cluster based on the two observations. The cluster application transmits the object position and at least one characteristic associated with the observations to a update application that generates an update to a road database. Because the cluster application computes the object position based on multiple observations that are likely of a single object, the object position associated with the cluster may be more reliable than the observed object positions.

Claims

1. A method for generating navigation-related data, the method comprising:

computing a first oriented distance between a first observed object position and a second observed object position based on a first heading, wherein the first observed object position and the first heading are associated with a first observation received from a first vehicle, and the second observed object position is associated with a second observation received from a second vehicle;

generating, based on the first oriented distance, a first cluster that includes the first observation and the second observation;

computing an object position associated with the first cluster based on at least the first observation and the second observation; and

transmitting the object position and at least one characteristic associated with the first observation to an update application, wherein the update application generates an update to a road database.

2. The method of claim 1, wherein generating the first cluster comprises performing one or more density-based clustering operations on a plurality of observations based on the first oriented distance, wherein the plurality of observations include at least the first observation and the second observation.

3. The method of claim 1, wherein the at least one characteristic comprises a speed limit.

4. The method of claim 1, further comprising transmitting a confidence level to the update application, wherein the confidence level indicates a reliability of the object position.

5. The method of claim 4, further comprising computing the confidence level based on at least one of a number of observations included in the first cluster, a number of observations included in a plurality of clusters that includes the first cluster, and a last observation time associated with the first cluster.

6. The method of claim 1, further comprising, prior to computing the first oriented distance:

computing a first sector based on the first heading, a first speed, and a first vehicle position, wherein the first speed and the first vehicle position are included in the first observation, and

determining the first observed object position based on the first sector.

7. The method of claim 1, wherein computing the object position comprises fitting at least the first observed object position and the second observed object position to a Gaussian distribution and setting the object position to a median of the Gaussian distribution.

8. The method of claim 1, further comprising, prior to generating the first cluster:

determining that a third observation is inconsistent with a plurality of observations that includes the first observation and the second observation, and

in response, discarding the third observation.

9. A non-transitory computer-readable storage medium including instructions that, when executed by a processor, configure the processor to generate navigation-related data by performing the steps of:

computing a first observed object position based on a first heading, a first speed, and a first vehicle position, wherein the first heading, the first speed and the first vehicle position are associated with a first observation;

computing a first oriented distance between the first observed object position and a second observed object position based on the first heading, wherein the second observed object position is associated with a second observation;

generating, based on the first oriented distance, a first cluster that includes the first observation and the second observation;

computing an object position associated with the first cluster based on at least the first observed object position and the second observed object position; and

transmitting the object position and at least one characteristic associated with the first observation to an update application, wherein the update application performs one or more update operations associated with a road database.

10. The computer readable medium of claim 9, wherein generating the first cluster comprises performing one or more density-based clustering operations on a plurality of observations based on the first oriented distance, wherein the plurality of observations include at least the first observation and the second observation.

11. The computer readable medium of claim 9, further comprising transmitting a confidence level to the update application, wherein the confidence level indicates a reliability of the object position.

12. The computer readable medium of claim 9, wherein computing the object position comprises fitting at least the first observed object position and the second observed object position to a Gaussian distribution and setting the object position to a median of the Gaussian distribution.

13. The computer readable medium of claim 9, further comprising, prior to generating the first cluster, determining that a third observation is inconsistent with a physical characteristics associated with vehicles, and, in response, discarding the third observation.

14. The computer readable medium of claim 9, further comprising:

determining that a second cluster and a third cluster are associated with a single logical object;

merging the second cluster and the third cluster to generate a fourth cluster; and

transmitting at least one characteristic associated with the fourth cluster to the update application.

15. The computer readable medium of claim 14, further comprising:

computing a first confidence level based on a number of observations included in the second cluster;

determining that the second cluster is associated with a left side and the third cluster is associated with a right side;

reducing the first confidence level to generate a second confidence level that indicates a reliability of the at least one characteristic; and

transmitting the second confidence level to the update application.

16. The computer readable medium of claim 15, further comprising:

computing a first confidence level based on a number of observations included in the second cluster;

determining that the second cluster is associated with both a left side and a right side; and

transmitting the first confidence level to the update application to indicate a reliability of the at least one characteristic.

17. A system for generating navigation-related data, the system comprising:

a memory storing a cluster application; and

a processor coupled to the memory, wherein when executed by the processor, the cluster application configures the processor to;

compute a first oriented distance between a first observed object position associated with a first observation and a second observed object position associated with a second observation based on a first heading;

perform one or more density-based clustering operations on a plurality of observations based on a plurality of oriented distances to generate a first cluster that includes the first observation and the second observation, wherein the plurality of oriented distances includes the first oriented distance;

compute an object position associated with the first cluster based on at least the first observation and the second observation; and

transmit the object position and at least one characteristic associated with the first observation to at least one of a navigation application and an update application, wherein the update application generates an update to a road database.

18. The system of claim 17, wherein, when executed by the processor, the cluster application further configures the processor to transmit a confidence level to the at least one of the navigation application and the update application, wherein the confidence level indicates a reliability of the object position.

19. The system of claim 17, wherein the cluster application configures the processor to compute the object position by fitting at least the first observed object position and the second observed object position to a Gaussian distribution and setting the object position to a median of the Gaussian distribution.

20. The system of claim 17, wherein the at least one characteristic comprises a speed limit.