Methods and apparatus for position estimation

• US 9,341,483 B2
• Filed: 03/11/2013
• Issued: 05/17/2016
• Est. Priority Date: 03/11/2013
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Chao, Hui, Das, Saumitra Mohan, Holm, Eric K.
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): McPherson, James M
• Application Number:
  US13/794,316
• Publication Number:
  US 20140257688A1
• Time in Patent Office: 1,163 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: G01C 21/206 specially adapted for indoor navigation

Abstract

Systems, apparatus and methods disclosed herein facilitate mobile station (MS) location determination using MS captured images of known points of interest (POIs). In some embodiments, each POI is associated with a corresponding visibility map comprising a set of grid points, and a subset of the POIs may be identified from the MS captured images by matching the MS captured images of each POI in the subset with corresponding stored images. A cumulative grid point weight for a plurality of grid points in the visibility maps associated with the POIs in the subset may be computed. The cumulative grid point weight for each grid point represents the probability that the MS is located at that grid point. The location of the MS may be estimated based on the cumulative grid point weights of the plurality of grid points.

Claims

1. A processor-implemented method for estimating a position of a mobile station (MS) the method comprising:

identifying a subset of points of interest in a plurality of points of interest by matching MS captured images of each point of interest in the subset of points of interest with at least one corresponding stored image of a point of interest selected from images of the plurality of points of interest, each point of interest in the subset of points of interest being associated with a corresponding visibility map comprising a set of grid points;

computing a corresponding cumulative grid point weight for each grid point based on corresponding individual grid point weights, each individual grid point weight associated with one of the points of interest in the subset of points of interest; and

computing an estimated location of the MS based on the corresponding cumulative grid point weight of each grid point.

2. The processor implemented method of claim 1, wherein the corresponding cumulative grid point weight for each grid point is computed as a function of the corresponding individual grid point weights, each corresponding individual grid point weight associated with a point of interest in the subset of points of interest.

3. The processor implemented method of claim 1, wherein computing the corresponding cumulative grid point weight for each grid point comprises:

determining an area of intersection of visibility maps associated with the subset of the points of interest; and

computing the cumulative grid point weight for each grid point lying within the area of intersection of the visibility maps.

4. The processor implemented method of claim 1, wherein the MS is in a line of sight of each point of interest in the subset of points of interest.

5. The processor implemented method of claim 1, wherein each individual grid point weight of the corresponding individual grid point weights for a grid point corresponds to a distinct point of interest in the subset of points of interest and represents a probability relative to the corresponding point of interest that the MS is located at that grid point.

6. The processor implemented method of claim 5, wherein each individual grid point weight is based, in part, on a distance of the grid point from the corresponding point of interest.

7. The processor implemented method of claim 5, wherein each individual grid point weight is based, in part, on a viewing angle of the grid point relative to the corresponding point of interest.

8. The processor implemented method of claim 5, wherein each individual grid point weight is based on at least one of:

a distance (dist(g(x, y), POI_j)) and a viewing angle (α

_j^{g(x, y)}) of the grid point (g(x,y)) from the corresponding point of interest (POI_j)relative to a first distance (d0_j) and a first view angle (α

0_j) for viewing the corresponding point of interest (POI _j), respectively;

or

an estimated pose of the MS relative to the corresponding point of interest (POI_j) and a confidence interval associated with the estimated pose of the MS;

or

a history based on compiled information, the compiled information based, in part, on the at least one corresponding stored image associated with the corresponding point of interest (POI_j).

9. The processor implemented method of claim 2, wherein the function to compute the corresponding cumulative grid point weight for each grid point obtains, for each grid point, the corresponding cumulative grid point weight as a product of the corresponding individual grid point weights.

10. The processor implemented method of claim 8, wherein each individual grid point weight is computed using the estimated pose of the MS relative to the corresponding point of interest, if the confidence interval associated with the estimated pose of the MS exceeds a confidence interval threshold.

11. The processor implemented method of claim 8, wherein the estimated pose of the MS relative to the corresponding point of interest and the confidence interval associated with the estimated pose of the MS are based on the MS captured images.

12. The processor implemented method of claim 8, wherein each corresponding individual grid point weight (w_j^g(x,y)) is computed as a product of a distance component (w_d_j^g(x,y)) and an angular component (w_α

_j^g(x,y))of the corresponding individual grid point weight (w_j^g(x,y)).

13. The processor implemented method of claim 1, wherein the cumulative grid point weight for each grid point represents a probability that the MS is located at that grid point.

14. The processor implemented method of claim 1, wherein the method is performed by the MS.

15. The processor implemented method of claim 1, wherein the method is performed by a server.

16. The processor implemented method of claim 1, wherein matching the MS captured images of each point of interest in the subset of points of interest with the at least one corresponding stored image of the point of interest comprises:

matching the MS captured images with the at least one corresponding stored image of the point of interest based, in part, on Scale Invariant Feature Transform (SIFT) techniques.

17. An apparatus comprising:

a memory configured to store images of a plurality of points of interest and visibility maps wherein each visibility map is associated with a point of interest in the subset and comprises a set of grid points; and

a processor coupled to the memory, the processor configured to;

identify a subset of points of interest in the plurality of points of interest by matching Mobile Station (MS) captured images of each point of interest in the subset of points of interest with at least one corresponding stored image of a point of interest selected from the images of the plurality of points of interest stored in the memory;

compute a corresponding cumulative grid point weight for each grid point based on corresponding individual grid point weights, each individual grid point weight associated with one of the points of interest in the subset of points of interest; and

compute an estimated location of the MS based on the corresponding cumulative grid point weight of each grid point.

18. The apparatus of claim 17, wherein to compute the cumulative grid point weight for each grid point, the processor is configured to:

compute the cumulative grid point weight for each grid point as a function of the corresponding individual grid point weights, each corresponding individual grid point weight associated with a point of interest in the subset of points of interest.

19. The apparatus of claim 17, wherein to compute the cumulative grid point weight for each grid point, the processor is configured to:

determine an area of intersection of visibility maps associated with the subset of points of interest; and

compute the cumulative grid point weight for each grid point lying within the area of intersection of the visibility maps.

20. The apparatus of claim 17, wherein each individual grid point weight of the corresponding individual grid point weights corresponds to a distinct point of interest in the subset of points of interest and represents a probability relative to the corresponding point of interest that the MS is located at that grid point.

21. The apparatus of claim 20, wherein the processor is configured to determine each individual grid point weight based, in part, on a distance of the grid point from the corresponding point of interest.

22. The apparatus of claim 20, wherein the processor is configured to determine each individual grid point weight based, in part, on a viewing angle of the grid point relative to the corresponding point of interest.

23. The apparatus of claim 20, wherein the processor is configured to determine each individual grid point weight based on at least one of:

a distance (dist(g(x,y), POI_j)) and a viewing angle (α

_j^g(x,y)) of the grid point (g(x,y)) from the corresponding point of interest (POI_j) relative to a first distance (d0_j) and a first view angle (α

0_j)for viewing the corresponding point of interest (POI_j), respectively;

or

an estimated pose of the MS relative to the corresponding point of interest (POI_j) and a confidence interval associated with the estimated pose of the MS;

or

a history based on compiled information, the compiled information based, in part, on the at least one corresponding stored image associated with the corresponding point of interest (POI_j).

24. The apparatus of claim 18, wherein the function to compute the corresponding cumulative grid point weight for each grid point obtains, for each grid point, the corresponding cumulative grid point weight as a product of the corresponding individual grid point weights.

25. The apparatus of claim 23, wherein the processor is configured to determine each individual grid point weight by using the estimated pose of the MS relative to the corresponding point of interest, if the confidence interval associated with the estimated pose of the MS exceeds a confidence interval threshold.

26. The apparatus of claim 24, wherein the processor is configured to determine the estimated pose of the MS relative to the corresponding point of interest and the confidence interval associated with the estimated pose of the MS based on the MS captured images.

27. The apparatus of claim 24, wherein the processor is configured to compute each corresponding individual grid point weight (w_j^g(x,y)) as a product of a distance component (w_d_j ^g(x,y)) and an angular component (w_α

_j ^g(x,y)) of the corresponding individual grid point weight (w_j^g(x,y)).

28. The apparatus of claim 17, wherein the cumulative grid point weight for each grid point represents a probability that the MS is located at that grid point.

29. The apparatus of claim 17, wherein the apparatus is a mobile station (MS) and further comprises a camera, the camera configured to capture the images of each point of interest in the subset.

30. The apparatus of claim 17, wherein the apparatus further comprises a communications interface configured to receive the captured images of each point of interest in the subset from the mobile station.

31. The apparatus of claim 17, wherein to match the MS captured images of each point of interest in the subset of points of interest with the at least one corresponding stored image of the point of interest, the processor is configured to:

match the MS captured images with the at least one corresponding stored image of the point of interest based, in part, on Scale Invariant Feature Transform (SIFT) techniques.

32. An apparatus comprising:

means for storing images of a plurality of points of interest and visibility maps, wherein each visibility map is associated with a point of interest in the subset, wherein each visibility map comprises a set of grid points;

means for identifying a subset of points of interest in the plurality of points of interest by matching Mobile Station (MS) captured images of each point of interest in the subset with at least one corresponding stored image of a point of interest selected from stored images of the plurality of points of interest;

means for computing a corresponding cumulative grid point weight for each grid point based on corresponding individual grid point weights, each individual grid point weight associated with one of the points of interest in the subset of points of interest; and

means for computing an estimated location of the MS based on the corresponding cumulative grid point weight of each grid point.

33. The apparatus of claim 32, wherein the means for computing the corresponding cumulative grid point weight for each grid point computes the corresponding cumulative grid point weight for each grid point as a function of the corresponding individual grid point weights, each corresponding individual grid point weight associated with a point of interest in the subset of points of interest.

34. The apparatus of claim 32, further comprising the means for computing the cumulative grid point weight for each grid point comprises:

means for determining an area of intersection of visibility maps associated with the subset of points of interest; and

means for computing the cumulative grid point weight for each grid point lying within the area of intersection of the visibility maps.

35. The apparatus of claim 32, wherein means for computing a corresponding cumulative grid point weight comprises:

means for determining each individual grid point weight of the corresponding individual grid point weights for a grid point corresponds to a distinct point of interest in the subset of points of interest and represents a probability relative to the corresponding point of interest that the MS is located at that grid point.

36. The apparatus of claim 35, wherein the means for determining each individual grid point weight of the corresponding individual grid point weights determines each individual grid point weight based, in part, on a distance of the grid point from the corresponding point of interest.

37. The apparatus of claim 35, wherein the means for determining each individual grid point weight of the corresponding individual grid point weights determines each individual grid point weight based, in part, on a viewing angle of the grid point relative to the corresponding point of interest.

38. The apparatus of claim 35, wherein the means for determining each individual grid point weight of the corresponding individual grid point weights determines each individual grid point weight based on at least one of:

a distance (dist(g(x, y), POI_j)) and a viewing angle (α

_j^g(x,y)) of the grid point (g(x,y)) from the corresponding point of interest (POI_j) relative to a first distance (d0_j) and a first view angle (α

0_j) for viewing the corresponding point of interest (POI_J), respectively;

or

an estimated pose of the MS relative to the corresponding point of interest (POI_j) and a confidence interval associated with the estimated pose of the MS;

or

a history based on compiled information the compiled information based, in part, on the at least one corresponding stored image associated with the corresponding point of interest (POI_j).

39. The apparatus of claim 33, wherein the function to compute the corresponding cumulative grid point weight for each grid point obtains, for each grid point, the corresponding cumulative grid point weight as a product of the corresponding individual grid point weights.

40. The apparatus of claim 38, wherein the means for determining each corresponding individual grid point weight of the corresponding individual grid point weights determines each individual grid point weight based on an estimated pose of the MS relative to the corresponding point of interest, if the confidence interval associated with the estimated pose of the MS exceeds a confidence interval threshold.

41. The apparatus of claim 38, the estimated pose of the MS relative to the corresponding point of interest and the confidence interval associated with the estimated pose of the MS are based on the MS captured images.

42. The apparatus of claim 38, wherein the means for determining each corresponding individual grid point weight (w_j^g(x,y)) for each point of interest in the subset comprises:

means for computing a product of a distance component (w_d_j^g(x,y)) and an angular component (w_α

_j^g(x,y)) of the corresponding individual grid point weight (w_j^g(x,y)) relative to the corresponding point of interest (POI_j).

43. The apparatus of claim 32, wherein the cumulative grid point weight for each grid point represents a probability that the MS is located at that grid point.

44. The apparatus of claim 32, further comprising image capturing means, the image capturing means to capture the MS captured images of each point of interest in the subset.

45. The apparatus of claim 32, further comprising means for communicating, the means for communicating to receive the captured images of each point of interest in the subset.

46. The apparatus of claim 32, wherein matching the MS captured images of each point of interest in the subset of points of interest with the at least one corresponding stored image of the point of interest comprises:

matching the MS captured images with the at least one corresponding stored image of the point of interest based, in part, on Scale Invariant Feature Transform (SIFT) techniques.

47. A non-transitory computer-readable medium comprising instructions, which when executed by a processor, cause the processor to:

identify a subset of points of interest in a plurality of points of interest by matching Mobile Station (MS) captured images of each point of interest in the subset of points of interest with at least one corresponding stored image of a point of interest selected from images of the plurality of points of interest, each point of interest being associated with a corresponding visibility map comprising a set of grid points;

compute a corresponding cumulative grid point weight for each grid point based on corresponding individual grid point weights, each individual grid point weight associated with one of the points of interest in the subset of points of interest; and

compute an estimated location of the MS based on the corresponding cumulative grid point weight of each grid point.

48. The computer-readable medium of claim 47, wherein the corresponding cumulative grid point weight for each grid point is computed as a function of the corresponding individual grid point weights, each corresponding individual grid point weight associated with a point of interest in the subset of points of interest.

49. The computer-readable medium of claim 47, wherein computing the corresponding cumulative grid point weight for each grid point comprises:

determining an area of intersection of visibility maps of the subset associated with the points of interest; and

computing the cumulative grid point weight for each grid point lying within the area of intersection of the visibility maps.

50. The computer-readable medium of claim 47, wherein the MS is in a line of sight of each point of interest in the subset of points of interest.

51. The computer-readable medium of claim 47, wherein each individual grid point weight of the corresponding individual grid point weights for a grid point corresponds to a distinct point of interest in the subset of points of interest and represents a probability relative to the corresponding point of interest that the MS is located at that grid point.

52. The computer-readable medium of claim 51, wherein each individual grid point weight is based, in part, on a distance of the grid point from the corresponding point of interest.

53. The computer-readable medium of claim 51, wherein each individual grid point weight is based, in part, on a viewing angle of the grid point relative to the corresponding point of interest.

54. The computer-readable medium of claim 51, wherein each individual grid point weight is based on at least one of:

a distance (dist(g(x, y), POI_j)) and a viewing angle (α

_j^g(x,y))of the grid point (g(x,y)) from the corresponding point of interest (POI_j) relative to a first distance (d0_j) and a first view angle (α

0_j) for viewing the corresponding point of interest (POI_j) respectively;

or

an estimated pose of the MS relative to the corresponding point of interest (POI_j) and a confidence interval associated with the estimated pose of the MS;

or

a history based on compiled information, the compiled information based, in part, on the at least one corresponding stored image associated with the corresponding point of interest (POI_j).

55. The computer-readable medium of claim 49, wherein the function to compute the corresponding cumulative grid point weight for each grid point obtains, for each grid point, the corresponding cumulative grid point weight as a product of the corresponding individual grid point weights.

56. The computer-readable medium of claim 54, wherein each individual grid point weight is computed using the estimated pose of the MS relative to the corresponding point of interest, if the confidence interval associated with the estimated pose of the MS exceeds a confidence interval threshold.

57. The computer-readable medium of claim 54, wherein the estimated pose of the MS relative to the corresponding point of interest and the confidence interval associated with the estimated pose of the MS are based on the MS captured images.

58. The computer-readable medium of claim 54, wherein each corresponding individual grid point weight (w_j^g(x,y)) is computed as a product of a distance component (w_d_j^g(x,y)) and an angular component (w_α

_j^g(x,y)) of the corresponding individual grid point weight (w_j^g(x,y)) relative to the corresponding point of interest (POI_j).

59. The computer-readable medium of claim 47, wherein the cumulative grid point weight for each grid point represents a probability that the MS is located at that grid point.

60. The computer-readable medium of claim 47, wherein the method is performed by the MS.

61. The computer-readable medium of claim 47, wherein the method is performed by a server.

62. The computer-readable medium of claim 47, wherein matching the MS captured images of each point of interest in the subset of points of interest with the at least one corresponding stored image of the point of interest comprises:

matching the MS captured images with the at least one corresponding stored image of the point of interest based, in part, on Scale Invariant Feature Transform (SIFT) techniques.