# US 2018/0023959 A1 · Matching observational points to road segments represented as edges in graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0023959 A1 - Document ID: US20180023959A1 - Status: Published application - Kind: A1 - Application number: 15/653,308 - Filed: 2017-07-18 - Published: 2018-01-25 - Earliest claimed: 2016-07-20 - Assignees: Harman Becker Automotive Systems GmbH - Applicants: Harman Becker Automotive Systems GmbH - Inventors: Volodymyr Ivanov; Alexey Pryakhin; Ievgenii Borshch - Web page: https://patentgrep.com/patent/US20180023959A1 ## 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 match application identifies an edge corresponding to a road segment based on an observational point specifying an estimated position and an estimated heading. The match application performs search operations on a road network graph based on the estimated position to identify multiple candidate edges. For a first candidate edge, the match application computes a first quality level based on at least a distance between the estimated position and the first candidate edge and an angle between the estimated heading and a direction associated with the first candidate edge. Subsequently, the match application determines that the first quality level indicates that the first candidate edge has a higher quality than any other candidate edge. Finally, the match application transmits the first candidate edge to an application that associates content specified in relation to the estimated position with the first candidate edge. ## Claims ### Claim 1 A method for associating an observational point with a road segment, the method comprising: performing one or more search operations on a road network graph based on an estimated position associated with the observational point to identify a plurality of candidate edges, wherein each candidate edge included in the plurality of candidate edges corresponds to a different road segment; computing a first quality level associated with a first candidate edge included in the plurality of candidate edges based on at least a first distance and a first angle, wherein the first distance comprises a distance between the estimated position and the first candidate edge, and the first angle comprises an angle between an estimated heading associated with the observational point and a direction associated with the first candidate edge; determining that the first quality level is greater than a quality level associated with any other candidate edge included in the plurality of candidate edges; and in response to the determining, transmitting at least one of information associated with the first candidate edge or a request for information associated with the first candidate edge to an application. ### Claim 2 (depends on 1) The method of claim 1, wherein transmitting information associated with the first candidate edge comprises transmitting an identification of the first candidate edge. ### Claim 3 (depends on 1) The method of claim 1, wherein performing the one or more search operations comprises: computing a position range based on the estimated position and a maximum distance; computing an angle range based on the estimated heading and a maximum angle difference; determining that at least a portion of the first candidate edge lies within the position range and a first direction associated with the at least the portion of the first candidate edge lies within the angle range; and in response, including the first candidate edge in the plurality of candidate edges. ### Claim 4 (depends on 1) The method of claim 1, wherein computing the first quality level comprises: projecting the estimated position onto the first candidate edge to determine a first projection factor; and generating a physical factor based on the first distance, the first angle, the first projection factor, and a width associated with the first candidate edge; and setting the first quality level based on the physical factor. ### Claim 5 (depends on 1) The method of claim 1, wherein computing the first quality level comprises computing a physical factor based on at least the first distance and the first angle, and adjusting the physical factor based on one or more attributes associated with the first candidate edge. ### Claim 6 (depends on 5) The method of claim 5, wherein a first attribute included in the one or more attributes specifies that the first candidate edge corresponds to a road segment included in a roundabout, a road segment included in a square, or a road segment that lies within a parking lot. ### Claim 7 (depends on 1) The method of claim 1, further comprising transmitting a confidence level to the application, wherein the confidence level indicates a confidence that the observational point is associated with a road segment corresponding to the first candidate edge. ### Claim 8 (depends on 7) The method of claim 7, further comprising computing the confidence level based on at least one of the first quality level, a second quality level that is associated with a second candidate edge included in the plurality of candidate edges, a number of candidate edges included in the plurality of candidate edges, and one or more distances associated with the first candidate edge. ### Claim 9 (depends on 8) The method of claim 8, wherein a first distance included in the one or more distances comprises a distance from a start of the first candidate edge or an end of the first candidate edge to a position associated with an exit lane attribute. ### Claim 10 A non-transitory computer-readable storage medium including instructions that, when executed by a processor, cause the processor to associate an observational point with a road segment by performing the steps of: performing one or more search operations on a road network graph based on an estimated position associated with the observational point and a maximum distance to identify a plurality of candidate edges, wherein each candidate edge included in the plurality of candidate edges corresponds to a different road segment; determining a traveling direction associated with the first candidate edge; computing a first quality level associated with a first candidate edge included in the plurality of candidate edges based on at least a first distance and a first angle, wherein the first distance comprises a distance between the estimated position and the first candidate edge, and the first angle comprises an angle between an estimated heading associated with the observational point and the traveling direction; determining that the first quality level is greater than a quality level associated with any other candidate edge included in the plurality of candidate edges; and in response to the determining, transmitting at least one of information associated with the first candidate edge or a request for information associated with the first candidate edge to an application. ### Claim 11 (depends on 10) The computer-readable storage medium of claim 10, wherein the observational point is associated with a plurality of observations. ### Claim 12 (depends on 10) The computer-readable storage medium of claim 10, wherein performing the one or more search operations comprises: computing a position range based on the estimated position and the maximum distance; computing an angle range based on the estimated heading and a maximum angle difference; determining that at least a portion of the first candidate edge lies within the position range and a direction associated with the at least the portion of the first candidate edge lies within the angle range; and in response, including the first candidate edge in the plurality of candidate edges. ### Claim 13 (depends on 10) The computer-readable storage medium of claim 10, wherein computing the first quality level comprises: projecting the estimated position onto the first candidate edge to determine a first projection factor; and generating a physical factor based on the first distance, the first angle, the first projection factor, and a width associated with the first candidate edge; and setting the first quality level based on the physical factor. ### Claim 14 (depends on 10) The computer-readable storage medium of claim 10, wherein computing the first quality level comprises computing a physical factor based on at least the first distance and the first angle, and adjusting the physical factor based on one or more attributes associated with the first candidate edge. ### Claim 15 (depends on 14) The computer-readable storage medium of claim 14, wherein a first attribute included in the one or more attributes indicates that the first candidate edge is associated with a first speed category, content associated with the observational point describes a road sign specifying a first speed limit, and adjusting the physical factor comprises decreasing the physical factor based on comparing the first speed category to the first speed limit. ### Claim 16 (depends on 10) The computer-readable storage medium of claim 10, further comprising transmitting a confidence level to the application, wherein the confidence level indicates a confidence that the observational point is associated with a road segment corresponding to the first candidate edge. ### Claim 17 (depends on 16) The computer-readable storage medium of claim 16, further comprising computing the confidence level based on at least one of the first quality level, a second quality level that is associated with a second candidate edge included in the plurality of candidate edges, a number of candidate edges included in the plurality of candidate edges, and one or more distances associated with the first candidate edge. ### Claim 18 (depends on 17) The computer-readable storage medium of claim 17, wherein a first distance included in the one or more distances comprises a distance from a start of the first candidate edge or an end of the first candidate edge to a first node that corresponds to an intersection between roads. ### Claim 19 A system for associating an observational point with a road segment, the system comprising: a memory storing a match application; and a processor coupled to the memory, wherein when executed by the processor, the match application causes the processor to: identify a plurality of candidate edges included in a road network graph based on an estimated position associated with the observational point, wherein each candidate edge included in the plurality of candidate edges corresponds to a different road segment; compute a first quality level associated with a first candidate edge included in the plurality of candidate edges based on at least a first distance and a first angle, wherein the first distance comprises a distance between the estimated position and the first candidate edge, and the first angle comprises an angle between an estimated heading associated with the observational point and a direction associated with the first candidate edge; determine that the first quality level is greater than a quality level associated with any other candidate edge included in the plurality of candidate edges; and in response to the determining, transmit at least one of information associated with the first candidate edge or a request for information associated with the first candidate edge to an application. ### Claim 20 (depends on 19) The system of claim 19, wherein the observational point is associated with a plurality of observations.