# US 2024/0200973 A1 · Method, data processing apparatus and computer program product for generating map data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2024/0200973 A1 - Document ID: US20240200973A1 - Status: Published application - Kind: A1 - Application number: 18/588,652 - Filed: 2024-02-27 - Published: 2024-06-20 - Earliest claimed: 2021-01-06 - Assignees: Grabtaxi Holdings Pte. Ltd. - Applicants: Grabtaxi Holdings Pte. Ltd. - Inventors: Adrian-Ioan MARGIN; Bogdan-Andrei GLIGA-HAMBET; Xiaocheng HUANG - Web page: https://patentgrep.com/patent/US20240200973A1 ## CPC - G01C 21/3815: {Road data} - G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles} - G01S 19/39: the satellite radio beacon positioning system transmitting time-stamped messages, e.g. GPS [Global Positioning System], GLONASS [Global Orbiting Navigation Satellite System] or GALILEO - G06N 3/0464: Convolutional networks [CNN, ConvNet] - G06N 3/09: Supervised learning - G06V 10/26: Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion - G06V 10/82: using neural networks - G06N 3/045: Combinations of networks - 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 - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Aspects concern a method for generating map data, the method including: generating of a plurality of cells of a real space area, each cell representing a two-dimensional sub-space of the real space area, wherein each of the cells comprise at least one global positioning system (GPS) point, and wherein the real space area comprises a road network; determining a number of GPS points for each cell of the plurality of cells; determining a road network based on the numbers of GPS points using a Smoothed Particle Hydrodynamics (SPH) analysis, wherein the cells of the plurality of cells are particles of the SPH analysis and the number of GPS points per cell of the plurality of cells are a scalar of each cell of the plurality of cells in the SPH analysis; and comparing the road network determined using the SPH analysis with the road network of the real space area. ## Claims ### Claim 1 A method for generating map data, the method comprising: receiving a request to generate an updated map associated with a road network; generating of a plurality of cells of a real space area, each cell representing a two-dimensional sub-space of the real space area the at least one GPS point received from at least one of a plurality of GPS devices, wherein each of the cells comprise at least one global positioning system (GPS) point, and wherein the real space area comprises the road network; determining a number of GPS points for each cell of the plurality of cells; determining a simulated road network based on the numbers of GPS points by analyzing the GPS points using a Smoothed Particle Hydrodynamics (SPH) analysis, wherein the cells of the plurality of cells are particles of the SPH analysis and the number of GPS points per cell of the plurality of cells are a scalar of each cell of the plurality of cells in the SPH analysis; comparing the simulated road network with the road network of the real space area to identify a first set of road segments that exist in the simulated road network that do not exist in the road network of the real space area; and generating an updated map including the first set of road segments and the road network of the real space area. ### Claim 2 (depends on 1) The method of claim 1, further comprising: determining a first plurality of cells, wherein the first plurality of cells includes the plurality of cells and at least one further cell, wherein the at least one further cell comprises no GPS point. ### Claim 3 (depends on 1) The method of claim 1, further comprising: providing GPS points from a plurality of mobile phone users in the real space area. ### Claim 4 (depends on 1) The method of claim 1, wherein the cells of the plurality of cells are spaces of a grid, wherein each cell comprises the same size. ### Claim 5 (depends on 4) The method of claim 4, wherein each cell is a Geohash. ### Claim 6 (depends on 1) The method of claim 1, wherein each GPS point of a cell has the same weight as other GPS points of the same cell. ### Claim 7 (depends on 1) The method of claim 1, wherein determining the road network comprises a reconstructing of a continuous field from the plurality of cells, wherein the continuous field is interpreted as a drivable area field. ### Claim 8 (depends on 7) The method of claim 7, wherein a high value of the continuous field in a certain point of the real space area is interpreted as a high probability of having a road in the point. ### Claim 9 (depends on 1) The method of claim 1, wherein determining the road network comprises a number of GPS points per cell interpreted as a road existence probability density function. ### Claim 10 (depends on 1) The method of claim 1, wherein the input to the SPH analysis represents an unprocessed heatmap built from the GPS points of each cell and the output is a normalized heatmap. ### Claim 11 (depends on 1) The method of claim 1, further comprising: providing at least one visualization image for the distribution of a number of GPS points per cell obtained after simulation. ### Claim 12 (depends on 11) The method of claim 11, further comprising: classifying each pixel from the resulting visualization image to determine whether the pixel is a part of a road or not. ### Claim 13 (depends on 12) The method of claim 12, wherein the classifying is performed using a deep neural network model with the visualization image as an input into a semantic segmentation. ### Claim 14 (depends on 12) The method of claim 12, wherein the classifying is performed using a deep neural network model with the visualization image as an input into a semantic segmentation. ### Claim 15 (depends on 14) The method of claim 14, wherein one or more labels are obtained by querying an open street map (OSM) and retrieving all existing geometries, and generating a binary image in which every pixel has a first label associated to a road or a second label associated to a non-road area by converting the geometries in the image by drawing a plurality of lines on an empty canvas. ### Claim 16 (depends on 1) The method of claim 1, wherein the road segments presented in the road network determined by the SPH analysis are considered as roads missing in the map of the real space area. ### Claim 17 (depends on 1) The method of claim 1, further comprising: determining whether there are existing roads in a proximity of new road segments determined by the SPH analysis. ### Claim 18 A data processing apparatus configured to carry out a method for generating map data, the method comprising: receiving a request to generate an updated map associated with a road network; generating of a plurality of cells of a real space area, each cell representing a two-dimensional sub-space of the real space area, wherein each of the cells comprise at least one global positioning system (GPS) point the at least one GPS point received from at least one of a plurality of GPS devices, and wherein the real space area comprises the road network; determining a number of GPS points for each cell of the plurality of cells; determining a simulated road network based on the numbers of GPS points by analyzing the GPS points using a Smoothed Particle Hydrodynamics (SPH) analysis, wherein the cells of the plurality of cells are particles of the SPH analysis and the number of GPS points per cell of the plurality of cells are a scalar of each cell of the plurality of cells in the SPH analysis; comparing the simulated road network with the road network of the real space area to identify a first set of road segments that exist in the simulated road network that do not exist in the road network of the real space area; and generating an updated map including the first set of road segments and the road network of the real space area. ### Claim 19 A non-transitory computer-readable medium storing computer executable code comprising instructions for generating map data according to a method for generating the map data, the method comprising: receiving a request to generate an updated map associated with a road network; generating of a plurality of cells of a real space area, each cell representing a two-dimensional sub-space of the real space area, wherein each of the cells comprise at least one global positioning system (GPS) point the at least one GPS point received from at least one of a plurality of GPS devices, and wherein the real space area comprises the road network; determining a number of GPS points for each cell of the plurality of cells; determining a simulated road network based on the numbers of GPS points by analyzing the GPS points using a Smoothed Particle Hydrodynamics (SPH) analysis, wherein the cells of the plurality of cells are particles of the SPH analysis and the number of GPS points per cell of the plurality of cells are a scalar of each cell of the plurality of cells in the SPH analysis; comparing the simulated road network with the road network of the real space area to identify a first set of road segments that exist in the simulated road network that do not exist in the road network of the real space area; and generating an updated map including the first set of road segments and the road network of the real space area.