Geometric fingerprinting for localization of a device

• US 10,145,956 B2
• Filed: 11/08/2016
• Issued: 12/04/2018
• Est. Priority Date: 12/26/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Modica, Leo, Stenneth, Leon, Lynch, James
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): Testardi, David A
• Application Number:
  US15/346,360
• Publication Number:
  US 20170055116A1
• Time in Patent Office: 756 Days
• 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, from an end user device equipped with a depth sensing device, a set of three-dimensional data from the depth sensing device, the end user device being attached to or carried by a pedestrian, or connected to a vehicle;

segmenting, using a processor, the set of three-dimensional data into planes defining elevations;

extracting, using the processor, a plurality of two-dimensional feature geometries from the segmented set of three-dimensional data;

ranking the extracted two-dimensional feature geometries to provide a ranking value for each of the plurality of extracted two-dimensional feature geometries;

selecting a fingerprint of a subset of the extracted two-dimensional feature geometries based at least in part on the ranking value of the extracted two-dimensional feature geometries;

providing for a comparison of the selected fingerprint of the subset of the extracted two-dimensional feature geometries to a fingerprint database of fingerprints corresponding to stored feature geometry data;

receiving data indicative of a location corresponding to the selected fingerprint of the subset of extracted two-dimensional feature geometries based on the comparison; and

determining a location of the end-user device based on the selected fingerprint of the subset of extracted two-dimensional feature geometries.

2. The method of claim 1, wherein the ranking is at least in part based on a shape of the plurality of feature geometries.

3. The method of claim 2, wherein the ranking ranks simplistic shapes higher than complex shapes.

4. The method of claim 3, wherein the simplistic shapes include a line, an arc, or a spline.

5. The method of claim 1, wherein the ranking is at least in part based on a size of the plurality of feature geometries, an elevation of the plurality of feature geometries, or a variance of the plurality of feature geometries.

6. The method of claim 1, wherein the ranking is at least in part based on a geometric dilution of precision of the plurality of feature geometries.

7. The method of claim 6, wherein the geometric dilution of precision is based on angular distance between the plurality of feature geometries in a plane.

8. The method of claim 7, wherein the angular distance between the plurality of feature geometries is defined based on a direction of travel of a vehicle including the depth sensing device.

9. The method of claim 1, wherein the depth sensing device includes a light detection and ranging device, a radio detection and ranging device, an ultrasound device, a structure light camera, or a moving mono-camera.

10. 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;

receiving, from an end user device equipped with a depth sensing device, a set of three-dimensional data from the depth sensing device, the end user device being attached to or carried by a pedestrian, or connected to a vehicle;

segmenting, using the processor, the set of three-dimensional data into planes defining elevations;

extracting a plurality of two-dimensional feature geometries from the segmented set of three-dimensional data;

ranking the extracted two-dimensional feature geometries to provide a ranking value for each of the plurality of extracted two-dimensional feature geometries;

selecting, using the processor, a fingerprint of a subset of the extracted two-dimensional feature geometries based at least in part on the ranking value of the extracted two-dimensional feature geometries;

providing for a comparison of the selected fingerprint of the subset of the extracted two-dimensional feature geometries to a fingerprint database of fingerprints corresponding to stored feature geometry data;

receiving data indicative of a location corresponding to the selected fingerprint of the subset of extracted two-dimensional feature geometries based on the comparison; and

determining a location of the end-user device based on the selected fingerprint of the subset of extracted two-dimensional feature geometries.

11. The apparatus of claim 10, wherein the selecting of the fingerprint selects simplistic shapes over complex shapes.

12. The apparatus of claim 11, wherein the simplistic shapes include a line, an arc, and a spline.

13. The apparatus of claim 10, wherein the selecting the fingerprint is at least in part based on a size of the plurality of feature geometries, an elevation of the plurality of feature geometries, or a variance of the plurality of feature geometries.

14. The apparatus of claim 10, wherein the selecting the fingerprint is at least in part based on a geometric dilution of precision of the plurality of feature geometries.

15. The apparatus of claim 14, wherein the geometric dilution of precision is based on distance between the plurality of feature geometries in a plane.

16. The apparatus of claim 15, wherein the distance between the plurality of feature geometries is defined based on a direction of travel of a vehicle including the depth sensing device.

17. One or more non-transitory computer-readable media including instructions that when executed are configured to cause a processor to perform:

receiving, from an end user device equipped with a depth sensing device, a set of three-dimensional data from the depth sensing device, the end user device being attached to or carried by a pedestrian, or connected to a vehicle;

segmenting, using the processor, the set of three-dimensional data into planes defining elevations;

extracting a plurality of two-dimensional feature geometries from the segmented set of three-dimensional data;

ranking the extracted two-dimensional feature geometries to provide a ranking value for each of the plurality of extracted two-dimensional feature geometries;

generating, using the processor, a fingerprint of a subset of the extracted two-dimensional feature geometries based at least in part on the ranking value of the extracted two-dimensional feature geometries;

providing a comparison of the selected fingerprint of the subset of the extracted two-dimensional feature geometries to a fingerprint database of fingerprints corresponding to stored feature geometry data;

receiving data indicative of a location corresponding to the selected fingerprint of the subset of extracted two-dimensional feature geometries based on the comparison; and

identifying a location of the end-user device based on the selected fingerprint of the subset of extracted two-dimensional feature geometries.