# US 10,482,761 B2 · Lane-level geometry and traffic information > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,482,761 B2 - Document ID: US10482761B2 - Status: Granted - Kind: B2 - Application number: 15/956,316 - Filed: 2018-04-18 - Published: 2019-10-24 - Granted: 2019-11-19 - Earliest claimed: 2018-04-18 - Assignees: HERE Global B.V. - Applicants: HERE Global B.V. - Inventors: Ole Henry Dorum - Web page: https://patentgrep.com/patent/US10482761B2 ## CPC - G08G 1/0112: {from the vehicle, e.g. floating car data [FCD]} - G08G 1/0116: {from roadside infrastructure, e.g. beacons} - G01C 21/3658: {Lane guidance} - G01S 19/51: Relative positioning - G05D 1/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)} - G06F 16/29: Geographical information databases - G06F 17/15: Correlation function computation {including computation of convolution operations (arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00)} - G08G 1/0129: {for creating historical data or processing based on historical data} - G08G 1/0141: {for traffic information dissemination} - 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 - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Provided herein is a method for establishing lane-level data from probe data. Methods may include receiving probe data points associated with a plurality of vehicles; determining, for each of the probe data points, a location and road segment corresponding to the location; generating, from the probe data points associated with a first road segment, a probe density histogram for the first road segment, where the probe density histogram represents a volume of probe data points at each of a plurality of positions across a width of the first road segment; applying a deconvolution method to the probe density histogram to obtain a multi-modal histogram; determining, from the multi-modal histogram, a number of statistically significant peaks, where each statistically significant peak represents a lane of the first road segment; and computing, from the multi-modal histogram, lane-level properties of the probe data of the first road segment. ## Claims ### Claim 1 A mapping system comprising: a memory comprising map data; and processing circuitry configured to: receive probe data points associated with a plurality of vehicles, each probe data point received from a probe apparatus of a plurality of probe apparatuses, each probe apparatus comprising one or more sensors and being onboard a respective vehicle, wherein each probe data point comprises location information associated with the respective probe apparatus; for each of the probe data points, determine a location and a road segment corresponding to the location; generate, from the probe data points associated with a first road segment, a probe density histogram for the first road segment, wherein the probe density histogram represents a volume of probe data points at each of a plurality of positions across a width of the first road segment; apply a deconvolution method to the probe density histogram to obtain a multi-modal histogram; determine, from the multi-modal histogram, a number of statistically significant peaks, wherein each statistically significant peak represents a lane of the first road segment; compute, from the multi-modal histogram, lane-level properties of the probe data of the first road segment; and provide data for at least one of navigational assistance or at least semi-autonomous vehicle control based on the computed lane-level properties of the probe data of the first road segment. ### Claim 2 (depends on 1) The mapping system of claim 1, wherein the processing circuitry configured to compute, from the multi-modal histogram, lane-level properties of the probe data of the first road segment comprises processing circuitry configured to: determine, from the multi-modal histogram, a distance of each statistically significant peak from the first road segment centerline. ### Claim 3 (depends on 2) The mapping system of claim 2, wherein the processing circuitry configured to compute, from the multi-modal histogram, lane-level properties of the probe data of the first road segment comprises processing circuitry further configured to: generate digital map data having a number of road segment lanes corresponding to the number of statistically significant peaks at positions corresponding to the distance of each statistically significant peak from the road segment centerline; and provide for at least semi-autonomous vehicle control or navigation assistance using the generated digital map data. ### Claim 4 (depends on 1) The mapping system of claim 1, wherein the processing circuitry configured to generate a probe density histogram for the first road segment representing a volume of probe data points at each of a plurality of positions across a width of the road segment comprises processing circuitry configured to: sub-divide a width of the first road segment into a plurality of bins according to a chosen bin size; bin each probe data point to a respective one of the plurality of bins corresponding to a distance of the respective probe data point from a centerline of the road segment; and generate the probe density histogram based on a volume of probe data points in each bin across a width of the road segment. ### Claim 5 (depends on 1) The mapping system of claim 1, wherein the deconvolution method comprises a Maximum Entropy Method. ### Claim 6 (depends on 1) The mapping system of claim 1, wherein the processing circuitry configured to apply a deconvolution method to the probe density histogram to obtain a multi-modal histogram comprises processing circuitry configured to: model location error of the probe data points associated with the first road segment using a point spread function; apply the deconvolution method to the probe density histogram using the point spread function; and generate the multi-modal histogram for the first road segment. ### Claim 7 (depends on 1) The mapping system of claim 1, wherein the processing circuitry configured to determine, from the multi-modal histogram, a number of statistically significant peaks, wherein each statistically significant peak represents a lane of the first road segment; comprises processing circuitry configured to: identify a lane of the first road segment in response to a corresponding statistically significant peak being within a range of 2.5 meters to 3.6 meters of another statistically significant peak. ### Claim 8 (depends on 1) The mapping system of claim 1, wherein the processing circuitry configured to, for each of the probe data points, determine a location and a road segment corresponding to the location comprises processing circuitry configured to: map-match the probe data points to the first road segment; sub-divide the road segment into a plurality of sub-segments; and associate each of the probe data points map-matched to the first road segment to one of the plurality of sub-segments, wherein the processing circuitry configured to generate, from the probe data points associated with a first road segment, a probe density histogram for the first road segment comprises processing circuitry configured to: generate, from the probe data points associated with a first road segment, a probe density histogram for each of the sub-segments of the first road segment. ### Claim 9 A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code instructions stored therein, the computer-executable program code instructions comprising program code instructions to: receive probe data points associated with a plurality of vehicles, each probe data point received from a probe apparatus of a plurality of probe apparatuses, each probe apparatus comprising one or more sensors and being onboard a respective vehicle, wherein each probe data point comprises location information associated with the respective probe apparatus; for each of the probe data points, determine a location and a road segment corresponding to the location; generate, from the probe data points associated with a first road segment, a probe density histogram for the first road segment, wherein the probe density histogram represents a volume of probe data points at each of a plurality of positions across a width of the first road segment; apply a deconvolution method to the probe density histogram to obtain a multi-modal histogram; determine, from the multi-modal histogram, a number of statistically significant peaks, wherein each statistically significant peak represents a lane of the first road segment; compute, from the multi-modal histogram, lane-level properties of the probe data of the first road segment; and store the computed lane-level properties of the probe data of the first road segment to augment a geographic database. ### Claim 10 (depends on 9) The computer program product of claim 9, wherein the program code instructions to compute, from the multi-modal histogram, lane-level properties of the probe data of the first road segment comprises program code instructions to: determine, from the multi-modal histogram, a distance of each statistically significant peak from the first road segment centerline. ### Claim 11 (depends on 10) The computer program product of claim 10, wherein the program code instructions to compute, from the multi-modal histogram, lane-level properties of the probe data of the first road segment comprises program code instructions to: generate digital map data having a number of road segment lanes corresponding to the number of statistically significant peaks at positions corresponding to the distance of each statistically significant peak from the road segment centerline; and provide for at least semi-autonomous vehicle control or navigation assistance using the generated digital map data. ### Claim 12 (depends on 9) The computer program product of claim 9, wherein the program code instructions to generate a probe density histogram for the first road segment representing a volume of probe data points at each of a plurality of positions across a width of the road segment comprises program code instructions to: sub-divide a width of the first road segment into a plurality of bins according to a chosen bin size; bin each probe data point to a respective one of the plurality of bins corresponding to a distance of the respective probe data point from a centerline of the road segment; and generate the probe density histogram based on a volume of probe data points in each bin across a width of the road segment. ### Claim 13 (depends on 9) The computer program product of claim 9, wherein the deconvolution method comprises a Maximum Entropy Method. ### Claim 14 (depends on 9) The computer program product of claim 9, wherein the program code instructions to apply a deconvolution method to the probe density histogram to obtain a multi-modal histogram comprises program code instructions to: model location error of the probe data points associated with the first road segment point spread function using a point spread function; apply the deconvolution method to the probe density histogram using the point spread function; and generate the multi-modal histogram for the first road segment. ### Claim 15 (depends on 9) The computer program product of claim 9, wherein the program code instructions to determine, from the multi-modal histogram, a number of statistically significant peaks, wherein each statistically significant peak represents a lane of the first road segment; comprises program code instructions to: identify a lane of the first road segment in response to a corresponding statistically significant peak being within a range of 2.5 meters to 3.6 meters of another statistically significant peak. ### Claim 16 (depends on 9) The computer program product of claim 9, wherein the program code instructions to, for each of the probe data points, determine a location and a road segment corresponding to the location comprises program code instructions to: map-match the probe data points to the first road segment; sub-divide the road segment into a plurality of sub-segments; and associate each of the probe data points map-matched to the first road segment to one of the plurality of sub-segments, wherein the program code instructions to generate, from the probe data points associated with a first road segment, a probe density histogram for the first road segment comprises causing the apparatus to: generate, from the probe data points associated with a first road segment, a probe density histogram for each of the sub-segments of the first road segment. ### Claim 17 A method for establishing lane-level data from probe data comprising: receiving probe data points associated with a plurality of vehicles, each probe data point received from a probe apparatus of a plurality of probe apparatuses, each probe apparatus comprising one or more sensors and being onboard a respective vehicle, wherein each probe data point comprises location information associated with the respective probe apparatus; for each of the probe data points, determining a location and a road segment corresponding to the location; generating, from the probe data points associated with a first road segment, a probe density histogram for the first road segment, wherein the probe density histogram represents a volume of probe data points at each of a plurality of positions across a width of the first road segment; applying a deconvolution method to the probe density histogram to obtain a multi-modal histogram; determining, from the multi-modal histogram, a number of statistically significant peaks, wherein each statistically significant peak represents a lane of the first road segment; computing, from the multi-modal histogram, lane-level properties of the probe data of the first road segment; and providing data for at least one of navigational assistance or at least semi-autonomous vehicle control based on the computed lane-level properties of the probe data of the first road segment. ### Claim 18 (depends on 17) The method of claim 17, wherein computing, from the multi-modal histogram, lane-level properties of the probe data of the first road segment comprises: determining, from the multi-modal histogram, a distance of each statistically significant peak from the first road segment centerline. ### Claim 19 (depends on 18) The method of claim 18, wherein computing, from the multi-modal histogram, lane-level properties of the probe data of the first road segment comprises: generating digital map data having a number of road segment lanes corresponding to the number of statistically significant peaks at positions corresponding to the distance of each statistically significant peak from the road segment centerline; and providing for at least semi-autonomous vehicle control or navigation assistance using the generated digital map data. ### Claim 20 (depends on 17) The method of claim 17, wherein generating a probe density histogram for the first road segment representing a volume of probe data points at each of a plurality of positions across a width of the road segment comprises: sub-dividing a width of the first road segment into a plurality of bins according to a chosen bin size; binning each probe data point to a respective one of the plurality of bins corresponding to a distance of the respective probe data point from a centerline of the road segment; and generating the probe density histogram based on a volume of probe data points in each bin across a width of the road segment.