INDOOR LIKELIHOOD HEATMAP

• US 20120044265A1
• Filed: 07/11/2011
• Published: 02/23/2012
• Est. Priority Date: 07/13/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Gupta, Rajarshi, Das, Saumitra Mohan, Aggarwal, Alok, Khorashadi, Behrooz
• Granted Patent: US 8,825,388 B2
• Time in Patent Office: Days
• US Class Current: 345/641
• 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, articles, or means 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 for a particular grid point of said multiple grid points a count of said feasible paths that 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 count.

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 wherein said determining for said particular grid point of said multiple grid points said count comprises;

determining said count of said feasible paths that traverse said particular grid point based, at least in part, on said number of absorbed grid points.

8. 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 counts of feasible paths between grid point pairs that 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.

9. The method of claim 8, further comprising:

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

10. The method of claim 8, 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.

11. The method of claim 10, 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.

12. The method of claim 8, 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.

13. 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 for a particular grid point of said multiple grid points a count of said feasible paths that 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 count.

14. The device of claim 13, 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.

15. The device of claim 14, 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.

16. The device of claim 15, 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.

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

18. The device of claim 17, 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.

19. The device of claim 18, 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 to determine for said particular grid point of said multiple grid points said count said one or more processors are further to execute said instructions to;

determine said count of said feasible paths that traverse said particular grid point based, at least in part, on said number of absorbed grid points.

20. 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 counts of feasible paths between grid point pairs that 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.

21. The mobile device of claim 20, 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.

22. The mobile device of claim 20, 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.

23. The mobile device of claim 22, 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.

24. The mobile device of claim 20, 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.

25. 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 for a particular grid point of said multiple grid points a count of said feasible paths that 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 count.

26. The device of claim 25, 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.

27. The device of claim 26, further comprising:

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

28. The device of claim 27, 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.

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

30. The device of claim 29, 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.

31. The device of claim 30, 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 means for determining for said particular grid point of said multiple grid points said count comprises;

means for determining said count of said feasible paths that traverse said particular grid point based, at least in part, on said number of absorbed grid points.

32. 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 counts of feasible paths between grid point pairs that 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.

33. The mobile device of claim 32, further comprising:

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

34. The mobile device of claim 32, 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.

35. The mobile device of claim 34, 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.

36. The mobile device of claim 32, 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.

37. An article comprising:

at least one 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 for a particular grid point of said multiple grid points a count of said feasible paths that 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 count.

38. The article of claim 37, 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.

39. The article of claim 38, 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.

40. The article of claim 39, 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.

41. The article 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.

42. The article of claim 41, 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.

43. The article of claim 42, 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 to determine for said particular grid point of said multiple grid points said count said instructions stored on said at least one storage medium are further executable by the one or more processors to;

determine said count of said feasible paths that traverse said particular grid point based, at least in part, on said number of absorbed grid points.

44. An article comprising:

at least one 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 counts of feasible paths between grid point pairs that 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.

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:

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

46. The article of claim 44, 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.

47. The article of claim 46, 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.

48. The article of claim 44, 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.