Determining localization from images of a vicinity

Patent metadata

Field	Value
Publication number	US-9704245-B2
Application number	US-201514828552-A
Country	US
Kind code	B2
Filing date	Aug 18, 2015
Priority date	Aug 18, 2015
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

A method and system for determining a user's location in a pre-mapped environment from one or more images of the user's vicinity is provided. The method includes providing a probabilistic data structure derived from a second data structure, querying the second data structure for corresponding feature characteristics stored in the second data structure that respectively correspond to each feature characteristic from a plurality of feature characteristics, which may be a subset of an initial plurality of feature characteristics extracted from the one or more images from the user's vicinity, and identifying the user's location from the corresponding feature characteristics. The plurality of feature characteristics is determined by querying the probabilistic data structure.

First claim

What is claimed is:

1. A method for determining a user's location in a pre-mapped environment from one or more images of the user's vicinity, the method comprising:
providing a first data structure, wherein the first data structure is a probabilistic data structure derived from a second data structure;
querying the second data structure for corresponding feature characteristics stored in the second data structure that respectively correspond to each feature characteristic from a plurality of feature characteristics,
wherein the plurality of feature characteristics is a subset of an initial plurality of feature characteristics extracted from the one or more images of the user's vicinity, and
wherein the plurality of feature characteristics is determined by queries to the first data structure; and

identifying the user's location in the pre-mapped environment from the corresponding feature characteristics.

2. The method according to claim 1 , wherein determining the plurality of feature characteristics by queries to the first data structure comprises:
querying the first data structure for a number of initial corresponding feature characteristics stored in the first data structure that respectively correspond to each feature characteristic from the initial plurality of feature characteristics;
generating a ranked list of each feature characteristic having a non-zero number of initial corresponding feature characteristics; and
selecting the plurality of feature characteristics from the ranked list,
wherein the plurality of feature characteristics contains feature characteristics from the initial plurality of feature characteristics having a least number of initial corresponding feature characteristics.

3. The method according to claim 1 , wherein the probabilistic data structure is a Bloom filter.

4. The method according to claim 1 , wherein identifying the user's location in the pre-mapped environment from the corresponding feature characteristics comprises:
applying a spatial clustering analysis to the corresponding feature characteristics.

5. The method according to claim 4 , wherein identifying the user's location in the pre-mapped environment from the corresponding feature characteristics further comprises:
determining an angle of observation with which the user observed each of the feature characteristics from the initial plurality of feature characteristics that corresponds to the corresponding feature characteristics.

6. The method according to claim 4 , wherein identifying the user's location in the pre-mapped environment from the corresponding feature characteristics further comprises:
applying a triangulation analysis to the corresponding feature characteristics.

7. The method according to claim 1 , further comprising:
providing a plurality of first data structures, wherein each of the first data structures from the plurality of first data structures is a probabilistic data structure derived from the second data structure.

8. The method according to claim 1 , wherein the initial plurality of feature characteristics extracted from the one or more images of the user's vicinity is extracted by an image feature detecting algorithm.

9. The method according to claim 8 , wherein the image feature detecting algorithm is selected from the group consisting of scale-invariant feature transform (SIFT), speeded up robust features (SURF), and features from accelerated segment test (FAST).

10. The method according to claim 1 , wherein the corresponding feature characteristics stored in the second data structure are three-dimensional (3D) keypoints extracted from a multiplicity of images of the pre-mapped environment.

11. The method according to claim 1 , wherein the second data structure contains three-dimensional (3D) keypoints extracted from a multiplicity of images of a plurality of pre-mapped environments.

12. The method according to claim 10 , wherein deriving the first data structure from the second data structure comprises:
querying the second data structure for a number of corresponding 3D keypoints that respectively correspond to each 3D keypoint stored in the second data structure;
analyzing a distribution of the number of corresponding 3D keypoints to determine threshold values for predetermined quantiles; and
generating the first data structure based on the threshold value for one of the predetermined quantiles.

13. The method according to claim 1 , wherein the second data structure is provided in a cloud computing environment.

14. The method according to claim 1 , wherein identifying the user's location in the pre-mapped environment from the corresponding feature characteristics comprises:
providing additional probabilistic data structures; and
receiving a number of matching feature characteristics stored in the additional probabilistic data structures that respectively correspond to each of at least two feature characteristics from the plurality of feature characteristics.

15. A computer program product for determining a user's location in a pre-mapped environment from one or more images of the user's vicinity, the computer program product comprising at least one computer readable non-transitory storage medium having computer readable program instructions thereon for execution by a processor, the computer readable program instructions comprising program instructions for:
providing a first data structure, wherein the first data structure is a probabilistic data structure derived from a second data structure;
querying the second data structure for corresponding feature characteristics stored in the second data structure that respectively correspond to each feature characteristic from a plurality of feature characteristics,
wherein the plurality of feature characteristics is a subset of an initial plurality of feature characteristics extracted from the one or more images of the user's vicinity, and
wherein the plurality of feature characteristics is determined by queries to the first data structure; and

identifying the user's location in the pre-mapped environment from the corresponding feature characteristics.

16. The computer program product according to claim 15 , wherein determining the plurality of feature characteristics by queries to the first data structure comprises:
querying the first data structure for a number of initial corresponding feature characteristics stored in the first data structure that respectively correspond to each feature characteristic from the initial plurality of feature characteristics;
generating a ranked list of each feature characteristic having a non-zero number of initial corresponding feature characteristics; and
selecting the plurality of feature characteristics from the ranked list,
wherein the plurality of feature characteristics contains feature characteristics from the initial plurality of feature characteristics having a least number of initial corresponding feature characteristics.

17. The computer program product according to claim 15 , wherein the probabilistic data structure is a Bloom filter.

18. A computer system for determining a user's location in a pre-mapped environment from one or more images of the user's vicinity the computer system comprising:
at least one processor;
at least one computer readable memory;
at least one computer readable tangible, non-transitory storage medium; and;
program instructions stored on the at least one computer readable tangible, non-transitory storage medium for execution by the at least one processor via the at least one computer

Assignees

• IBM

Inventors

• Manweiler Justin G

Classifications

• G06F17/30256

  Physics · mapped topic

• G06F17/30268

  Physics · mapped topic

• G06T2207/10012

  Stereo images · CPC title

• G06T2207/20076

  Probabilistic image processing · CPC title

• G06T2200/04

  involving 3D image data · CPC title