Geometric fingerprinting for localization of a device

• US 9,519,061 B2
• Filed: 12/26/2014
• Issued: 12/13/2016
• Est. Priority Date: 12/26/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Modica, Leo, Stenneth, Leon, Lynch, James
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): TESTARDI, DAVID A
• Application Number:
  US14/583,375
• Publication Number:
  US 20160189385A1
• Time in Patent Office: 718 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01S 13/08 Systems for measuring distance only indirect measurement G01S13/46
• CPC Class Codes: G01S 15/08 Systems for measuring distance only indirect measurement G01S15/46
• CPC Class Codes: G01S 17/06 Systems determining position data of a target
• CPC Class Codes: G01S 17/08 for measuring distance only indirect measurement G01S17/46; active triangulation systems G01S17/48
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 7/4808 Evaluating distance, position or velocity data
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30248 Vehicle exterior or interior
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/62 of area, perimeter, diameter or volume
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

Systems, apparatuses, and methods are provided for developing a fingerprint database for and determining the geographic location of an end-user device (e.g., vehicle, mobile phone, smart watch, etc.) with the database. A fingerprint database may be developed by receiving a depth map for a location in a path network, and then identifying physical structures within the depth map. The depth map may be divided, at each physical structure, into one or more horizontal planes at one or more elevations from a road level. Two-dimensional feature geometries may be extracted from the horizontal planes. At least a portion of the extracted feature geometries may be encoded into the fingerprint database.

Claims

1. A method comprising:

receiving a three-dimensional depth map for a location in a path network using a depth sensing device;

identifying, using a processor, data indicative of physical structures within the depth map;

dividing the depth map, at each physical structure, into one or more horizontal slices corresponding to one or more elevations from a road level, each horizontal slice having a thickness range associated with the respective elevation and including data from the depth map in the thickness range above and below the respective elevation;

identifying data points of the one or more horizontal slices representing feature geometries of the physical structures;

extracting two-dimensional feature geometries from the identified data points;

encoding portions of the extracted feature geometries into a database; and

providing the encoded portions of the extracted feature geometries for determination of a current geographic location of a vehicle.

2. The method of claim 1, wherein the depth sensing device is selected from the group consisting of:

a LIDAR camera, a RADAR device, an ultrasound device, a structure light camera, and a moving mono-camera.

3. The method of claim 1, wherein the one or more horizontal slices have a thickness of 0.1-2 meters.

4. The method of claim 1, wherein the two-dimensional feature geometries comprise lines, arcs, or splines.

5. The method of claim 1, further comprising:

ranking the extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors;

(1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and

sorting the ranked feature geometries from highest to lowest ranked feature geometries,

wherein the portion of extracted feature geometries encoded in the database correlate with the highest ranked feature geometries.

6. The method of claim 1,

wherein the encoding of the portion of the feature geometries comprises storing geographic attributes of selected control points of the feature geometries,

wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level.

7. A method comprising:

collecting a three-dimensional depth map at a location in a path network using a depth sensing camera attached to an end-user device;

dividing, using a processor, the depth map into one or more horizontal slices, each horizontal slice at a defined elevation from a road level and having a thickness in a range above and below the defined elevation, wherein each horizontal slice includes data from the depth map within a range above and below each respective elevation;

extracting two-dimensional feature geometries comprising one or more sets of connected lines from the one or more horizontal slices;

determining a geographic location of the end-user device through a comparison of at least a portion of the extracted feature geometries and a database of feature geometries for the path network; and

providing the geographic location to the end-user device.

8. The method in claim 7, further comprising:

ascertaining a geographic orientation of the end-user device through a comparison of the extracted feature geometries and the database of feature geometries.

9. The method of claim 7, wherein the end-user device is a vehicle, and wherein the depth sensing camera is selected from the group consisting of:

a LIDAR camera, a RADAR device, an ultrasound device, a structure light camera, and a moving mono-camera.

10. The method of claim 7, further comprising:

ranking the extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors;

(1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and

sorting the ranked feature geometries from highest to lowest ranked feature geometries,

wherein the portion of extracted feature geometries used in the comparison with the database comprise the highest ranked feature geometries.

11. The method of claim 7, wherein the two-dimensional feature geometries comprise lines, arcs, or splines.

12. The method of claim 7, wherein the geographic location of the device is determined using (1) geographic attributes of selected control points of the feature geometries in the database and (2) a determined distance of the device from each selected control point of the feature geometries,

wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level.

13. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

receive a three-dimensional depth map for a location in a path network from a depth sensing device;

identify physical structures within the depth map at the location;

divide the depth map into one or more horizontal slices, each of the one or more horizontal slices at a defined elevation from a road level and having a thickness in a range above and below the defined elevation, wherein each horizontal slice includes data from the depth map at the defined elevation and includes data from the depth map in the range above and below the defined elevation, until at least one feature geometry of a physical structure is identified;

extract at least one two-dimensional feature geometry from the one or more horizontal slices; and

encode at least a portion of the extracted at least one feature geometry into a database.

14. The apparatus of claim 13, wherein the depth sensing device is selected from the group consisting of:

a LIDAR camera, a RADAR device, an ultrasound device, a structure light camera, and a moving mono-camera.

15. The apparatus of claim 13, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform:

rank extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors;

(1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and

sort the ranked feature geometries from highest to lowest ranked feature geometries,

wherein the portion of extracted feature geometries encoded in the database correlate with the highest ranked feature geometries.

16. The apparatus of claim 13, wherein the encoding of the portion of the at least one feature geometry comprises storing geographic attributes of selected control points of the at least one feature geometry, wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level.

17. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

collect a three-dimensional depth map at a location in a path network using a depth sensing camera attached to an end-user device;

identify physical structures within the depth map at the location;

divide the depth map, at each physical structure, into one or more horizontal slices, each of the one or more horizontal slices at a defined elevation from a road level and having a thickness in a range above and below the defined elevation, wherein the one or more horizontal slices include data from the depth map at the defined elevation and include data from the depth map in the range above and below the defined elevation;

extract two-dimensional feature geometries comprising one or more sets of connected lines from the ones or more horizontal slices;

determine a geographic location of the end-user device through a comparison of at least a portion of the extracted feature geometries and a database of feature geometries for the path network; and

provide the geographic location of the end-user device to the end-user device.

18. The apparatus of claim 17, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform:

ascertain a geographic orientation of the end-user device through a comparison of the extracted feature geometries and the database of feature geometries.

19. The apparatus of claim 17, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform:

rank the extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors;

(1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and

sort the ranked feature geometries from highest to lowest ranked feature geometries,

wherein the portion of extracted feature geometries used in the comparison with the database comprise the highest ranked feature geometries.

20. The apparatus of claim 17, wherein the geographic location of the end-user device is determined using (1) geographic attributes of selected control points of the feature geometries in the database and (2) a determined distance of the end-user device from each selected control point of the feature geometries,

wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level.