Method of creating map data

• US 10,030,980 B2
• Filed: 02/15/2010
• Issued: 07/24/2018
• Est. Priority Date: 08/25/2009
• Status: Active Grant

• Current Assignee: Tomtom Belgium NV (TomTom NV)
• Original Assignee: Tomtom Global Content B.V (TomTom NV)
• Inventors: Nowak, Wojciech Tomasz, Coppens, Sven
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): King, Rodney P
• Application Number:
  US13/392,526
• Publication Number:
  US 20120158286A1
• Time in Patent Office: 3,081 Days
• Field of Search: 701400, 701409, 701410, 701532, 701533
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A computerized method of creating map data from a plurality of trips where each trip comprises position data derived from the positions of at least one navigation device over a period of time, the method comprising using a processing circuitry to perform the following steps: i. processing the position data; ii. calculating, from the processing of the position data, trip terminal positions at which the navigation device started to generate positions and/or stopped generating positions and which provide an end point of a trip; iii. performing statistical analysis on the terminal positions in order to determine origin locations at which trips commonly terminate and/or originate; iv. generating further map data, which comprises the origin locations.

Claims

1. A computerised method of creating map data from a plurality of trips where each trip comprises position data derived from the positions of at least one navigation device over a period of time, the method comprising using a processing circuitry to perform the following steps:

processing the position data;

calculating, from the processing of the position data, trip terminal positions at which the navigation device started to generate positions and/or stopped generating positions and which provide an end point of a trip;

performing statistical analysis on the terminal positions in order to determine origin locations at which trips commonly terminate and/or originate;

identifying, based on each of the origin locations, a location of an entrance and/or exit to a corresponding structure; and

incorporating the origin locations into map data, the incorporating comprising placing, in the map data, indications of the locations of entrances and/or exits of the corresponding structures for each of the origin locations.

2. A method according to claim 1 which generates a coordinate for each origin location.

3. A method according to claim 1 in which the statistical analysis comprises performing clustering on the terminal positions in order to generate one or more cluster to obtain the origin locations.

4. A method according to claim 3 which comprises determining a coordinate associated with each cluster, which may be a centre region of a cluster.

5. The method of claim 4, wherein the centre region is assigned to a building footprint.

6. The method of claim 3, wherein the performed clustering rejects clustering a group of coordinates below a predetermined number.

7. A method according to claim 1 in which, the method comprises marking within the map data the positions of structures that contain the origin locations and may further comprise marking the origin locations in association with the structures.

8. A method according to claim 1 which fuses position data from more than one data source to generate at least one of the terminal positions and the origin locations which may be from the group comprising:

GPS data;

INS (Inertial Navigation System) Data;

image processing.

9. A method according to claim 1 in which origin locations generated by the method are subsequently merged with data from other sources, which may include data from the group comprising:

GPS data;

INS (Inertial Navigation System) Data;

image processing data.

10. A method according to claim 1 which performs image processing on an image and determines potential positions for at least one of exits and entrances within that image and subsequently assigns an origin location to the location of the so determined exit and/or entrance.

11. The method of claim 10, wherein the image is a 3D Image.

12. The method of claim 11 fusing the entrance and exit information with the 3D image to provide candidate positions for doors and windows.

13. The method of claim 1, wherein the positional data is acquired from one or more pedestrians.

14. The method of claim 1, wherein the positional data is acquired when the navigation device acquires a signal from a GPS network and ends when the navigation device loses the signal from the GPS network.

15. The method of claim 1, wherein the structure is one of:

buildings, underpasses and bridges.

16. The method according to claim 1, further comprising:

determining whether each origin location is associated with an entrance and/or exit for the corresponding structure, the determination being based at least in part on a direction of travel.

17. A machine comprising a processor and memory and arranged to create map data, wherein the machine is arranged to receive and process position data from at least one source, the position data comprises the positions of at least one navigation device over a period of time, the machine being arranged to:

process the position data;

calculate trip terminal positions at which the navigation device generating that trip started to generate and/or stopped generating positions;

perform statistical processing on the terminal positions between the trips in order to determine origin locations at which a plurality of trips terminate and/or originate;

identify, based on each of the origin locations, a location of an entrance and/or exit to a corresponding structure; and

incorporate the origin locations into map data, the incorporating comprising placing, in the map data, indications of the locations of entrances and/or exits of the corresponding structures for each of the origin locations.

18. The machine according to claim 17, wherein the machine uses a signal acquisition and signal loss of the at least one navigation device to determine trip start and/or stop positions.

19. The machine according to claim 17, wherein the machine is further arranged to:

determine whether each origin location is associated with an entrance and/or exit for the corresponding structure, the determination being based at least in part on a direction of travel.

20. A non-transitory machine readable medium containing instructions which, when executed by a machine, cause the machine to perform a method for creating map data from a plurality of trips, each trip comprising position data derived from positions of at least one navigation device over a period of time, the method comprising:

processing the position data;

calculating, based on the processing of the position data, trip terminal positions at which the navigation device started to generate positions and/or stopped generating positions and which provide an end point of a trip;

performing a statistical analysis on the terminal positions to determine origin locations at which trips commonly terminate and/or originate;

identifying, based on each of the origin locations, a location of an entrance and/or exit to a corresponding structure; and

incorporating the origin locations into map data, the incorporating comprising placing, in the map data, indications of the locations of entrances and/or exits of the corresponding structures for each of the origin locations.