IP Library › Granted Patent US 12,281,916
Granted Patent B2
US 12,281,916 · App. 17/662,151 · Granted Apr 22, 2025

Method, apparatus, and computer program product for map geometry generation based on data aggregation and conflation with statistical analysis

Inventor: Fei Tang (Aarau, CH)
Assignee: HERE GLOBAL B.V.
G01C21/3867G01C21/3841G01C21/3859G06F16/29G06T7/143G06T7/60G06T7/90G06T2207/20044
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,281,916
App. No.
17/662,151
Filed
May 5, 2022
Granted
Apr 22, 2025
Kind
B2
Art Unit
2645
USPC
382/173
Abstract

A method is provided automatically creating map geometry from data from various sources gathered within a geographical area using data aggregation and conflation with statistical analysis. Methods may include: receiving observation data associated with a geographic area; rasterizing objects within the observation data onto corresponding channels in a raster image corresponding to the geographic area having a given resolution; determining a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data; extracting analytic geometries from the raster image; generating map geometry based on the extracted analytic geometries; and updating a map database with the generated map geometry.

Claims (41)

1. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processor, cause the apparatus to at least:

receive observation data associated with a geographic area;

rasterize objects within the observation data onto corresponding channels in a raster image corresponding to the geographic area having a given resolution;

determine a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data;

extract analytic geometries from the raster image;

generate map geometry based on the extracted analytic geometries; and

update a map database with the generated map geometry.

2. The apparatus of claim 1 , wherein causing the apparatus to determine a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data comprises causing the apparatus to:

calculate a log likelihood of the objects at the locations within the raster image given corresponding distributions as parameterized by values in different channels of the raster image.

3. The apparatus of claim 2 , wherein causing the apparatus to calculate a log likelihood of the objects at the locations within the raster image given corresponding distributions as parameterized by values in different channels of the raster image comprises causing the apparatus to update the values in the different channels of the raster image to increase the log likelihood.

4. The apparatus of claim 1 , wherein the apparatus is further caused to determine a probability of observing a respective object at pixels proximate a location of the respective object based on the distribution of the location for the respective object.

5. The apparatus of claim 1 , wherein the apparatus is further caused to render pixels of the rasterized image based on the distribution of locations of the objects parameterized by the values in different channels in the raster image from the observation data.

6. The apparatus of claim 5 , wherein channels in the raster image comprises at least one of pixel color or pixel intensity.

7. The apparatus of claim 1 , wherein causing the apparatus to extract analytic geometries from the raster image comprises causing the apparatus to apply a skeletonization algorithm to the raster image to extract the analytic geometries.

8. A method comprising:

receiving observation data associated with a geographic area;

rasterizing objects within the observation data onto corresponding channels in a raster image corresponding to the geographic area having a given resolution;

determining a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data;

extracting analytic geometries from the raster image;

generating map geometry based on the extracted analytic geometries; and

updating a map database with the generated map geometry.

9. The method of claim 8 , wherein determining a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data comprises:

calculating a log likelihood of the objects at the locations within the raster image given corresponding distributions as parameterized by values in different channels of the raster image.

10. The method of claim 9 , wherein calculating a log likelihood of the objects at the locations within the raster image given corresponding distributions as parameterized by values in different channels of the raster image comprises updating the values in the different channels of the raster image to increase the log likelihood.

11. The method of claim 8 , further comprising determining a probability of observing a respective object at pixels proximate a location of the respective object based on the distribution of the location for the respective object.

12. The method of claim 8 , further comprising rendering pixels of the rasterized image based on the distribution of locations of the objects parameterized by the values in different channels in the raster image from the observation data.

13. The method of claim 12 , wherein channels in the raster image comprises at least one of pixel color or pixel intensity.

14. The method of claim 8 , wherein extracting analytic geometries from the raster image comprises applying a skeletonization algorithm to the raster image to extract the analytic geometries.

15. 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 observation data associated with a geographic area;

rasterize objects within the observation data onto corresponding channels in a raster image corresponding to the geographic area having a given resolution;

determine a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data;

extract analytic geometries from the raster image;

generate map geometry based on the extracted analytic geometries; and

update a map database with the generated map geometry.

16. The computer program product of claim 15 , wherein the program code instructions to determine a distribution of locations of the objects parameterized by values in different channels in the raster image from the observation data comprise program code instructions to:

calculate a log likelihood of the objects at the locations within the raster image given corresponding distributions as parameterized by values in different channels of the raster image.

17. The computer program product of claim 16 , wherein the program code instructions to calculate a log likelihood of the objects at the locations within the raster image given corresponding distributions as parameterized by values in different channels of the raster image comprise program code instructions to update the values in the different channels of the raster image to increase the log likelihood.

18. The computer program product of claim 15 , further comprising program code instructions to determine a probability of observing a respective object at pixels proximate a location of the respective object based on the distribution of the location for the respective object.

19. The computer program product of claim 15 , further comprising program code instructions to render pixels of the rasterized image based on the distribution of locations of the objects parameterized by the values in different channels in the raster image from the observation data.

20. The computer program product of claim 15 , wherein the program code instructions to extract analytic geometries from the raster image comprise program code instructions to apply a skeletonization algorithm to the raster image to extract the analytic geometries.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 5, 2022
From: TANG, FEI
To: HERE GLOBAL B.V.
Reel/Frame 059857/0925 →
Continuity (1)
Related Publication 20230358567A1 · Nov 9, 2023
References Cited (98)
US 8949021B2 · Witmer · 2015 [cited by applicant]
US 9171485B2 · Gautama et al. · 2015 [cited by applicant]
US 9177404B2 · Ramachandran et al. · 2015 [cited by applicant]
US 9658074B2 · Dorum · 2017 [cited by applicant]
US 10266280B2 · Derenick et al. · 2019 [cited by applicant]
US 10444020B2 · Dorum · 2019 [cited by applicant]
US 10546400B2 · Dorum · 2020 [cited by applicant]
US 10580292B2 · Dorum · 2020 [cited by applicant]
US 10760920B2 · Sekiyama · 2020 [cited by applicant]
US 11030476B2 · Xu et al. · 2021 [cited by applicant]
US 11068515B2 · Bukowski · 2021 [cited by applicant]
US 11093760B2 · Savla et al. · 2021 [cited by applicant]
US 11192558B2 · Thompson · 2021 [cited by applicant]
US 11209548B2 · Yang et al. · 2021 [cited by applicant]
US 11210537B2 · Koivisto et al. · 2021 [cited by applicant]
US 11227500B2 · Wang · 2022 [cited by applicant]
US 11244500B2 · Marschner et al. · 2022 [cited by applicant]
US 20030009287A1 · Howard et al. · 2003 [cited by applicant]
US 20090210388A1 · Elson et al. · 2009 [cited by applicant]
US 20130033591A1 · Takahashi et al. · 2013 [cited by applicant]
US 20140219558A1 · Teng et al. · 2014 [cited by applicant]
US 20160358477A1 · Ansari · 2016 [cited by applicant]
US 20170169313A1 · Choi et al. · 2017 [cited by applicant]
US 20170177933A1 · Mittal et al. · 2017 [cited by applicant]
US 20180003512A1 · Lynch · 2018 [cited by applicant]
US 20180107190A1 · Marshall et al. · 2018 [cited by applicant]
US 20190147320A1 · Mattyus et al. · 2019 [cited by applicant]
US 20190147331A1 · Arditi · 2019 [cited by applicant]
US 20190170519A1 · Anwar et al. · 2019 [cited by applicant]
US 20190221033A1 · Messerlie et al. · 2019 [cited by applicant]
US 20190258878A1 · Koivisto et al. · 2019 [cited by applicant]
US 20190287393A1 · Fowe et al. · 2019 [cited by applicant]
US 20190325738A1 · Dorum · 2019 [cited by applicant]
US 20190355103A1 · Baek et al. · 2019 [cited by applicant]
US 20200302223A1 · Dutta et al. · 2020 [cited by applicant]
US 20200410274A1 · Satoh et al. · 2020 [cited by applicant]
US 20210012166A1 · Braley et al. · 2021 [cited by applicant]
US 20210019516A1 · Mittal et al. · 2021 [cited by applicant]
US 20210056847A1 · Saxena et al. · 2021 [cited by applicant]
US 20210113130A1 · Tran · 2021 [cited by applicant]
US 20210164787A1 · Soni et al. · 2021 [cited by applicant]
US 20210209368A1 · Hao et al. · 2021 [cited by applicant]
US 20210224466A1 · Nehrenberg et al. · 2021 [cited by applicant]
US 20210302170A1 · Xie et al. · 2021 [cited by applicant]
US 20210333124A1 · Heo et al. · 2021 [cited by applicant]
US 20210342585A1 · Fleisig et al. · 2021 [cited by applicant]
US 20220113162A1 · Nomura · 2022 [cited by applicant]
US 20220156612A1 · Ren et al. · 2022 [cited by applicant]
US 20220198339A1 · Zhao et al. · 2022 [cited by applicant]
US 20220366259A1 · Wang et al. · 2022 [cited by applicant]
US 20230213945A1 · Sajjan · 2023 [cited by examiner]
US 20230252795A1 · Tong et al. · 2023 [cited by applicant]
CN 101924647A · 2010 [cited by applicant]
CN 107743431A · 2018 [cited by applicant]
EP 3280974A1 · 2018 [cited by applicant]
WO WO2016162665A1 · 2016 [cited by applicant]
WO WO2021002190A1 · 2021 [cited by applicant]
Agmon et al, “An algorithm for finding the distribution of maximal entropy”, Journal of Computational Physics, vol. 30, No. 2 (Feb. 1979), 9 pages. [cited by applicant]
Alotaibi A., “Deep Generative Adversarial Networks for Image-to-Image Translation: A Review”, Symmetry, vol. 12, No. 10, (Oct. 16, 2020), 26 pages. [cited by applicant]
Arman et al., “Lane-level routable digital map reconstruction for motorway networks using low-precision GPS data”, Transportation Research Part C: Emerging Technologies, (Jun. 3, 2021), 21 pages. [cited by applicant]
Batra, A., “Road Topology Extraction from Satellite Images by Knowledge Sharing”, International Institute of Information Technology, Deemed University, (Jul. 2019), 75 pages. [cited by applicant]
Biagioni et al., “Inferring Road Maps from Global Positioning System Traces: Survey and Comparative Evaluation”, Department of Computer Science, University of Illinois at Chicago, (2012), 11 pages. [cited by applicant]
Chen et al., “Probabilistic Modeling of Traffic Lanes from GPS Traces”, 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2010, (Nov. 3-5, 2010), 8 pages. [cited by applicant]
Dorum, O., “Deriving Double-Digitized Road Network Geometry from Probe Data”, SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, (Nov. 2017), 1… [cited by applicant]
Hartmann et al., “Night time road curvature estimation based on convolutional neural networks”, 2013 IEEE Intelligent Vehicles Symposium (IV), (Jun. 23-26, 2013), 6 pages. [cited by applicant]
He et al., “Sat2Graph: Road Graph Extraction through Graph-Tensor Encoding”, arXiv:2007.09547v1, (Jul. 19, 2020), 17 pages. [cited by applicant]
Horritt et al., “Developing a Prototype Tool for Mapping Flooding From All Sources Phase 1: Scoping and Conceptual Method Development”, Department for Environment Food and Rural Affairs, Flood and Coastal Erosion Risk M… [cited by applicant]
Kaji et al., “Overview of Image-To-Image Translation by Use of Deep Neural Networks: Denoising, Super-Resolution, Modality Conversion, and Reconstruction in Medical Imaging”, Radiological Physics and Technology 12(4), (… [cited by applicant]
Kupyn et al., “DeblurGAN-v2: Deblurring (Orders-of-Magnitude) Faster and Better”, 2019 IEEE/CVF International Conference on Computer Vision (ICCV), (2019), 10 pages. [cited by applicant]
Kupyn et al., “DeblurGAN: Blind Motion Deblurring Using Conditional Adversarial Networks”, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, (Nov. 19, 2017), pp. 8183-8192. [cited by applicant]
Mi et al., “HDMapGen: A Hierarchical Graph Generative Model of High Definition Maps”, 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), (Jun. 1, 2021), 10 pages. [cited by applicant]
Narayan et al., “Maximum Entropy Image Restoration in Astronomy”, Annual Review of Astronomy and Astrophysics, vol. 24, No. 1, (Nov. 2003), 44 pages. [cited by applicant]
Redmon et al., “YOLO: Real-Time Object Detection”, Retrieved on Oct. 18, 2022, Retrieved from the Internet: URL<https://pjreddie.com/darknet/yolo>, (2018), 9 pages. [cited by applicant]
Spolti et al., “Application of U-Net and Auto-Encoder to the Road/Non-Road Classification of Aerial Imagery in Urban Environments”, 15th International Conference on Computer Vision Theory and Applications, (Jan. 2020), … [cited by applicant]
Vu, “Vehicle Perception: Localization, Mapping with Detection, Classification and Tracking of Moving Objects”, Computer Science, Institut National Polytechnique de Grenoble—INPG, (2009), 127 pages. [cited by applicant]
Xiao et al., “VAE-info-cGAN: generating synthetic images by combining pixel-level and feature-level geospatial conditional inputs”, arXiv:2012.04196v1, (Dec. 8, 2020), 10 pages. [cited by applicant]
Zhang et al., “A Fast Learning Method for Accurate and Robust Lane Detection Using Two-Stage Feature Extraction with YOLO v3”, Sensors 2018 (Dec. 6, 2018), 20 pages. [cited by applicant]
U.S. Appl. No. 17/662,165, filed May 5, 2022, entitled, “Method, Apparatus, And Computer Program Product For Map Data Generation From Probe Data Imagery”, 43 pages. [cited by applicant]
U.S. Appl. No. 17/662,129, filed May 5, 2022, entitled, “Method, Apparatus, And Computer Program Product For Map Geometry Generation Based On Object Detection”, 40 pages. [cited by applicant]
U.S. Appl. No. 17/662,158, filed May 5, 2022, entitled, “Method, Apparatus, And Computer Program Product For Probe Data- Based Geometry Generation”, 35 pages. [cited by applicant]
U.S. Appl. No. 17/662,136, filed May 5, 2022, entitled, “Method, Apparatus, And Computer Program Product For Lane Geometry Generation Based On Graph Estimation”, 40 pages. [cited by applicant]
U.S. Appl. No. 17/662,144, filed May 5, 2022, entitled, “Method, Apparatus, And Computer Program Product For Map Geometry Generation Based On Data Aggregation And Conflation”, 43 pages. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 17/662,129 dated Aug. 24, 2023. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 17/662,158 dated Sep. 13, 2023. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 17/662,136 dated Sep. 14, 2023. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 17/662,144 dated Jan. 5, 2024. [cited by applicant]
Extended European Search Report for European Application No. 23171578.0 dated Oct. 10, 2023, 8 pages. [cited by applicant]
Extended European Search Report for European Application No. 23171576.4 dated Oct. 6, 2023, 9 pages. [cited by applicant]
Extended European Search Report for European Application No. 23171637.4 dated Oct. 19, 2023, 7 pages. [cited by applicant]
Extended European Search Report for European Application No. 23171632.5 dated Oct. 10, 2023, 8 pages. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/662,129 dated Feb. 15, 2024. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/662,136 dated Mar. 27, 2024. [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 17/662,158 dated Mar. 27, 2024. [cited by applicant]
Advisory Action for U.S. Appl. No. 17/662,129 dated Apr. 25, 2024. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/662,165 dated Jan. 27, 2025. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/662,129 dated Dec. 9, 2024. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/662,136 dated Dec. 23, 2024. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/662,144 dated Mar. 11, 2025. [cited by applicant]