Indoor likelihood heatmap

• US 8,825,388 B2
• Filed: 07/11/2011
• Issued: 09/02/2014
• Est. Priority Date: 07/13/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Khorashadi, Behrooz, Gupta, Rajarshi, Das, Saumitra Mohan, Aggarwal, Alok
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US13/180,464
• Publication Number:
  US 20120044265A1
• Time in Patent Office: 1,149 Days
• Field of Search: 701/23, 701/26, 701/408, 701/411, 701/416, 701/434, 701/467, 701/469, 701/409, 345/641, 455/456.1
• US Class Current: 701/434
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

The subject matter disclosed herein may relate to methods, apparatuses, systems, devices or articles for generating or using an indoor likelihood heatmap, etc. For certain example implementations, a method for a device may comprise projecting multiple grid points over a schematic map of an indoor area, with the schematic map indicating multiple obstructions of the indoor area. Feasible paths between grid point pairs of the multiple grid points may be determined. For a particular grid point of the multiple grid points, a count of the feasible paths that traverse the particular grid point may be determined. A likelihood heatmap for use in one or more navigational applications may be generated based, at least in part, on the count. Other example implementations are described herein.

Claims

1. A method for a device, the method comprising:

projecting multiple grid points over a schematic map of an indoor area, said schematic map indicating multiple obstructions of said indoor area;

determining feasible paths between grid point pairs of said multiple grid points;

determining an indication for a particular grid point of said multiple grid points, said indication being based, at least in part, on how many of said feasible paths traverse said particular grid point; and

generating a likelihood heatmap for use in one or more navigational applications based, at least in part, on said indication.

2. The method of claim 1, wherein said generating of said likelihood heatmap comprises:

traversing said feasible paths between starting grid points and ending grid points to establish traversed paths, said traversed paths including intermediate grid points subject to a smallest cost based, at least in part, on lengths of said traversed paths; and

attributing a likelihood value to said intermediate grid points of said traversed paths for said likelihood heatmap.

3. The method of claim 2, further comprising:

affecting said smallest cost based, at least in part, on a sparse connectivity graph for said indoor area.

4. The method of claim 3, wherein said affecting of said smallest cost comprises:

attributing a reduced cost to said intermediate grid points based, at least in part, on said sparse connectivity graph.

5. The method of claim 1, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area.

6. The method of claim 5, wherein said determining of said feasible paths between said grid point pairs comprises:

directing said feasible paths between said grid point pairs through at least one grid point of said sparse connectivity graph.

7. The method of claim 6, wherein said at least one grid point of said sparse connectivity graph is associated with a number of absorbed grid points from said multiple grid points;

and further comprises;

determining said indication further based, at least in part, on said number of absorbed grid points.

8. The method of claim 1, wherein said indication comprises a count of said feasible paths traverse said particular grid point.

9. A method comprising:

obtaining a likelihood heatmap for an indoor area that includes multiple obstructions, said likelihood heatmap corresponding to a schematic map of said indoor area and including multiple grid points, wherein likelihood values that are indicated for individual grid points of said multiple grid points are based at least partly on an indication of how many feasible paths between grid point pairs traverse said individual grid points; and

determining an estimated location of a mobile device within said indoor area based, at least in part, on said likelihood heatmap.

10. The method of claim 9, further comprising:

implementing at least one navigational application using said estimated location of said mobile device.

11. The method of claim 9, wherein said likelihood values are attributed to intermediate grid points of traversed paths;

and wherein said traversed paths are established with said feasible paths between starting grid points and ending grid points of said traversed paths, said intermediate grid points of said traversed paths subject to a smallest cost that is based, at least in part, on lengths of said traversed paths.

12. The method of claim 11, wherein said intermediate grid points of said traversed paths are further subject to a sparse connectivity graph that is overlaid on a connectivity graph that includes said multiple grid points.

13. The method of claim 9, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area and are constrained between said grid point pairs to pass through at least one grid point of said sparse connectivity graph.

14. The method of claim 9, wherein said indication comprises a count of said feasible paths between said grid point pairs traverse said individual grid points.

15. A device for generating a likelihood heatmap, the device comprising:

at least one memory to store instructions; and

one or more processors to execute said instructions to;

project multiple grid points over a schematic map of an indoor area, said schematic map indicating multiple obstructions of said indoor area;

determine feasible paths between grid point pairs of said multiple grid points;

determine an indication for a particular grid point of said multiple grid points, said indication being based, at least in part, on how many of said feasible paths traverse said particular grid point; and

generate said likelihood heatmap for use in one or more navigational applications based, at least in part, on said indication.

16. The device of claim 15, wherein to generate said likelihood heatmap said one or more processors are further to execute said instructions to:

traverse said feasible paths between starting grid points and ending grid points to establish traversed paths, said traversed paths including intermediate grid points subject to a smallest cost based, at least in part, on lengths of said traversed paths; and

attribute a likelihood value to said intermediate grid points of said traversed paths for said likelihood heatmap.

17. The device of claim 16, wherein said one or more processors are further to execute said instructions to:

affect said smallest cost based, at least in part, on a sparse connectivity graph for said indoor area.

18. The device of claim 17, wherein to affect said smallest cost said one or more processors are further to execute said instructions to:

attribute a reduced cost to said intermediate grid points based, at least in part, on said sparse connectivity graph.

19. The device of claim 15, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area.

20. The device of claim 19, wherein to determine said feasible paths between said grid point pairs said one or more processors are further to execute said instructions to:

direct said feasible paths between said grid point pairs through at least one grid point of said sparse connectivity graph.

21. The device of claim 20, wherein said at least one grid point of said sparse connectivity graph is associated with a number of absorbed grid points from said multiple grid points;

and wherein said one or more processors are further to execute said instructions to;

determine said indication based, at least in part, on said number of absorbed grid points.

22. The device of claim 15, wherein said indication comprises a count of said feasible paths traverse said particular grid point.

23. A mobile device for using a likelihood heatmap, the mobile device comprising:

at least one memory to store instructions; and

one or more processors to execute said instructions to;

obtain said likelihood heatmap for an indoor area that includes multiple obstructions, said likelihood heatmap corresponding to a schematic map of said indoor area and including multiple grid points, wherein likelihood values that are indicated for individual grid points of said multiple grid points are based at least partly on an indication of how many feasible paths between grid point pairs traverse said individual grid points; and

determine an estimated location of said mobile device within said indoor area based, at least in part, on said likelihood heatmap.

24. The mobile device of claim 23, wherein said one or more processors are further to execute said instructions to:

implement at least one navigational application using said estimated location of said mobile device.

25. The mobile device of claim 23, wherein said likelihood values are attributed to intermediate grid points of traversed paths;

and wherein said traversed paths are established with said feasible paths between starting grid points and ending grid points of said traversed paths, said intermediate grid points of said traversed paths subject to a smallest cost that is based, at least in part, on lengths of said traversed paths.

26. The mobile device of claim 25, wherein said intermediate grid points of said traversed paths are further subject to a sparse connectivity graph that is overlaid on a connectivity graph that includes said multiple grid points.

27. The mobile device of claim 23, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area and are constrained between said grid point pairs to pass through at least one grid point of said sparse connectivity graph.

28. The mobile device of claim 23, wherein said indication comprises a count of said feasible paths between said grid point pairs traverse said individual grid points.

29. A device for generating a likelihood heatmap, the device comprising:

means for projecting multiple grid points over a schematic map of an indoor area, said schematic map indicating multiple obstructions of said indoor area;

means for determining feasible paths between grid point pairs of said multiple grid points;

means for determining an indication for a particular grid point of said multiple grid points, said indication being based, at least in part, on how many of said feasible paths traverse said particular grid point; and

means for generating said likelihood heatmap for use in one or more navigational applications based, at least in part, on said indication.

30. The device of claim 29, wherein said means for generating said likelihood heatmap comprises:

means for traversing said feasible paths between starting grid points and ending grid points to establish traversed paths, said traversed paths including intermediate grid points subject to a smallest cost based, at least in part, on lengths of said traversed paths; and

means for attributing a likelihood value to said intermediate grid points of said traversed paths for said likelihood heatmap.

31. The device of claim 30, further comprising:

means for affecting said smallest cost based, at least in part, on a sparse connectivity graph for said indoor area.

32. The device of claim 31, wherein said means for affecting said smallest cost comprises:

means for attributing a reduced cost to said intermediate grid points based, at least in part, on said sparse connectivity graph.

33. The device of claim 29, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area.

34. The device of claim 33, wherein said means for determining said feasible paths between said grid point pairs comprises:

means for directing said feasible paths between said grid point pairs through at least one grid point of said sparse connectivity graph.

35. The device of claim 34, wherein said at least one grid point of said sparse connectivity graph is associated with a number of absorbed grid points from said multiple grid points;

and wherein said further comprises;

means for determining said indication further based, at least in part, on said number of absorbed grid points.

36. The device of claim 29, wherein said indication comprises a count of said feasible paths traverse said particular grid point.

37. A mobile device for using a likelihood heatmap, the mobile device comprising:

means for obtaining said likelihood heatmap for an indoor area that includes multiple obstructions, said likelihood heatmap corresponding to a schematic map of said indoor area and including multiple grid points, wherein likelihood values that are indicated for individual grid points of said multiple grid points are based at least partly on an indication of how many feasible paths between grid point pairs traverse said individual grid points; and

means for determining an estimated location of said mobile device within said indoor area based, at least in part, on said likelihood heatmap.

38. The mobile device of claim 37, further comprising:

means for implementing at least one navigational application using said estimated location of said mobile device.

39. The mobile device of claim 37, wherein said likelihood values are attributed to intermediate grid points of traversed paths;

and wherein said traversed paths are established with said feasible paths between starting grid points and ending grid points of said traversed paths, said intermediate grid points of said traversed paths subject to a smallest cost that is based, at least in part, on lengths of said traversed paths.

40. The mobile device of claim 39, wherein said intermediate grid points of said traversed paths are further subject to a sparse connectivity graph that is overlaid on a connectivity graph that includes said multiple grid points.

41. The mobile device of claim 37, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area and are constrained between said grid point pairs to pass through at least one grid point of said sparse connectivity graph.

42. The mobile device of claim 37, wherein said indication comprises a count of said feasible paths between said grid point pairs traverse said individual grid points.

43. An article comprising:

at least one non-transitory storage medium having stored thereon instructions executable by one or more processors to;

project multiple grid points over a schematic map of an indoor area, said schematic map indicating multiple obstructions of said indoor area;

determine feasible paths between grid point pairs of said multiple grid points;

determine an indication for a particular grid point of said multiple grid points, said indication being based, at least in part, on how many of said feasible paths traverse said particular grid point; and

generate a likelihood heatmap for use in one or more navigational applications based, at least in part, on said indication.

44. The article of claim 43, wherein to generate said likelihood heatmap said instructions stored on said at least one storage medium are further executable by the one or more processors to:

traverse said feasible paths between starting grid points and ending grid points to establish traversed paths, said traversed paths including intermediate grid points subject to a smallest cost based, at least in part, on lengths of said traversed paths; and

attribute a likelihood value to said intermediate grid points of said traversed paths for said likelihood heatmap.

45. The article of claim 44, wherein said instructions stored on said at least one storage medium are further executable by the one or more processors to:

affect said smallest cost based, at least in part, on a sparse connectivity graph for said indoor area.

46. The article of claim 45, wherein to affect said smallest cost said instructions stored on said at least one storage medium are further executable by the one or more processors to:

attribute a reduced cost to said intermediate grid points based, at least in part, on said sparse connectivity graph.

47. The article of claim 43, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area.

48. The article of claim 47, wherein to determine said feasible paths between said grid point pairs said instructions stored on said at least one storage medium are further executable by the one or more processors to:

direct said feasible paths between said grid point pairs through at least one grid point of said sparse connectivity graph.

49. The article of claim 48, wherein said at least one grid point of said sparse connectivity graph is associated with a number of absorbed grid points from said multiple grid points;

and wherein said instructions stored on said at least one storage medium are further executable by the one or more processors to;

determine said indication further based, at least in part, on said number of absorbed grid points.

50. The article of claim 43, wherein said indication comprises a count of said feasible paths traverse said particular grid point.

51. An article comprising:

at least one non-transitory storage medium having stored thereon instructions executable by one or more processors to;

obtain a likelihood heatmap for an indoor area that includes multiple obstructions, said likelihood heatmap corresponding to a schematic map of said indoor area and including multiple grid points, wherein likelihood values that are indicated for individual grid points of said multiple grid points are based at least partly on an indication of how many feasible paths between grid point pairs traverse said individual grid points; and

determine an estimated location of a mobile device within said indoor area based, at least in part, on said likelihood heatmap.

52. The article of claim 51, wherein said instructions stored on said at least one storage medium are further executable by the one or more processors to:

implement at least one navigational application using said estimated location of said mobile device.

53. The article of claim 51, wherein said likelihood values are attributed to intermediate grid points of traversed paths;

and wherein said traversed paths are established with said feasible paths between starting grid points and ending grid points of said traversed paths, said intermediate grid points of said traversed paths subject to a smallest cost that is based, at least in part, on lengths of said traversed paths.

54. The article of claim 53, wherein said intermediate grid points of said traversed paths are further subject to a sparse connectivity graph that is overlaid on a connectivity graph that includes said multiple grid points.

55. The article of claim 51, wherein said feasible paths between said grid point pairs are based, at least in part, on a sparse connectivity graph for said indoor area and are constrained between said grid point pairs to pass through at least one grid point of said sparse connectivity graph.

56. The article of claim 51, wherein said indication comprises a count of how many feasible paths between said grid point pairs traverse said individual grid points.