# US 2018/0025628 A1 · Clustering observations of objects along roads for navigation-related operations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0025628 A1 - Document ID: US20180025628A1 - Status: Published application - Kind: A1 - Application number: 15/653,321 - Filed: 2017-07-18 - Published: 2018-01-25 - Earliest claimed: 2016-07-20 - Assignees: Harman International Industries, Incorporated - Applicants: Harman International Industries, Incorporated - Inventors: Volodymyr Ivanov; Alexey Pryakhin; Ievgenii Borshch - Web page: https://patentgrep.com/patent/US20180025628A1 ## CPC - G08G 1/0104: {Measuring and analyzing of parameters relative to traffic conditions} - G01C 15/002: {Active optical surveying means (optical plumbing G01C15/105)} - G01C 21/26: specially adapted for navigation in a road network - G01C 21/28: with correlation of data from several navigational instruments - G01C 21/30: Map- or contour-matching - 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} - G01C 21/36: Input/output arrangements for on-board computers - G01C 21/3697: {Output of additional, non-guidance related information, e.g. low fuel level (G01C21/3679 takes precedence)} - G01C 21/3815: {Road data} - G01S 19/51: Relative positioning - G01S 19/53: Determining attitude - G06F 8/65: Updates (security arrangements therefor G06F21/57) - G06F 9/44526: {Plug-ins; Add-ons} - G06F 16/284: {Relational databases} - G06F 16/29: Geographical information databases - G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} - G06T 7/12: Edge-based segmentation - G06T 17/05: Geographic models - G08G 1/0112: {from the vehicle, e.g. floating car data [FCD]} - G08G 1/052: with provision for determining speed or overspeed {(speed measuring in general G01P)} - G08G 1/093: {Data selection, e.g. prioritizing information, managing message queues, selecting the information to be output} - G08G 1/09623: {Systems involving the acquisition of information from passive traffic signs by means mounted on the vehicle (G08G1/0967 takes precedence)} - G08G 1/0967: Systems involving transmission of highway information, e.g. weather, speed limits (transmission of navigation instructions to the vehicle G08G1/0968) - G08G 1/096716: {where the received information does not generate an automatic action on the vehicle control} - G08G 1/20: {Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles} - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) The method of claim 1, wherein the at least one characteristic comprises a speed limit. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 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. ### Claim 10 (depends on 9) 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. ### Claim 11 (depends on 9) 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. ### Claim 12 (depends on 9) 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. ### Claim 13 (depends on 9) 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. ### Claim 14 (depends on 9) 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. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 15) 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. ### Claim 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. ### Claim 18 (depends on 17) 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. ### Claim 19 (depends on 17) 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. ### Claim 20 (depends on 17) The system of claim 17, wherein the at least one characteristic comprises a speed limit.