Indoor structure inference using points of interest

• US 9,395,189 B2
• Filed: 06/21/2012
• Issued: 07/19/2016
• Est. Priority Date: 06/21/2012
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Sridhara, Vinay, Chao, Hui, Das, Saumitra Mohan, Gupta, Rajarshi
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): Chen, Yu
• Application Number:
  US13/530,051
• Publication Number:
  US 20130342565A1
• Time in Patent Office: 1,489 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/3811 Point data, e.g. Point of Interest [POI]
• CPC Class Codes: G01C 21/383 Indoor data
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map

Abstract

In one implementation, a method may comprise: obtaining a digital map of an indoor region that identifies boundaries between subsections within the indoor region; and approximating locations of walls separating rooms within at least one of the subsections based, at least in part, on locations of feature labels provided in the digital map.

Claims

1. A method comprising:

obtaining, from a memory, a digital map of an indoor region that identifies boundaries between subsections within the indoor region;

extracting feature labels from the digital map and establishing points based on locations of the extracted feature labels;

approximating locations of walls separating rooms within at least one of the subsections by superimposing polygons over the subsections within the indoor region based on the established points; and

generating heat map values at a plurality of points within at least one subsection based on an estimated number of walls crossed between the plurality of points and at least one transceiver.

2. The method of claim 1, wherein the feature labels identify one or more points of interest.

3. The method of claim 1, wherein the feature labels comprise names of one or more stores.

4. The method of claim 3, further comprising:

approximating the locations of the feature labels based on a quantity of the one or more stores.

5. The method of claim 3, further comprising:

modifying the locations of the feature labels based on the names of the one or more stores.

6. The method of claim 1, wherein the polygons comprise Voronoi cells.

7. The method of claim 1, further comprising:

determining routeability for at least a portion of the indoor region based on the approximated locations of walls.

8. The method of claim 1, further comprising:

computing values of a radio heatmap database based on locations of transceivers and the approximated locations of walls.

9. The method of claim 8, wherein the radio heatmap database comprises received signal strength indicator (RSSI) values.

10. The method of claim 1, wherein at least one of the subsections within the indoor region comprises an anchor store of a shopping mall, the method further comprising:

determining a size of the anchor store based on a lookup table; and

constraining the approximating locations of walls based on the determined size.

11. An apparatus comprising:

means for obtaining a digital map of an indoor region that identifies boundaries between subsections within the indoor region;

means for extracting feature labels from the digital map and establishing points based on locations of the extracted feature labels;

means for approximating locations of walls separating rooms within at least one of the subsections by superimposing polygons over the subsections within the indoor region based on the established points; and

means for generating heat map values at a plurality of points within the at least one polygon based on an estimated number of walls crossed between the plurality of points and at least one transceiver.

12. The apparatus of claim 11, wherein the feature labels identify one or more points of interest.

13. The apparatus of claim 11, wherein the feature labels comprise names of one or more stores.

14. The apparatus of claim 13, further comprising:

means for approximating the locations of the feature labels based-on a quantity of the one or more stores.

15. The apparatus of claim 13, further comprising:

means for modifying the locations of the feature labels based on the names of the one or more stores.

16. The apparatus of claim 11, wherein the polygons comprise Voronoi cells.

17. The apparatus of claim 11, further comprising:

means for determining routeability for at least a portion of the indoor region based on the approximated locations of walls.

18. The apparatus of claim 11, further comprising:

means for computing values of a radio heatmap database based on locations of transceivers and the approximated locations of walls.

19. The apparatus of claim 18, wherein the radio heatmap database comprises received signal strength indicator (RSSI) values.

20. The apparatus of claim 11, wherein at least one of the subsections within the indoor region comprises an anchor store of a shopping mall, the apparatus further comprising:

means for determining a size of the anchor store based on a lookup table; and

means for constraining the approximated locations of walls based on the determined size.

21. An apparatus comprising:

a receiver to receive wireless signals; and

one or more processing units configured to;

obtain, from a memory, a digital map of an indoor region that identifies boundaries between subsections within the indoor region;

extract feature labels from the digital map and establish points based on locations of the extracted feature labels;

approximate locations of walls separating rooms within at least one of multiple subsections by superimposing polygons over the subsections within the indoor region based on the established points; and

generate heat map values at a plurality of points within the at least one subsection based on the estimated number of walls crossed between the plurality of points and at least one transceiver.

22. The apparatus of claim 21, wherein the feature labels identify one or more points of interest.

23. The apparatus of claim 21, wherein the feature labels comprise names of one or more stores.

24. The apparatus of claim 23, wherein the one or more processing units are further configured to:

approximate said locations of the feature labels based on a quantity of the one or more stores.

25. The apparatus of claim 23, wherein the one or more processing units are further configured to:

modify said locations of the feature labels based on the names of the one or more stores.

26. The apparatus of claim 21, wherein the polygons comprise Voronoi cells.

27. The apparatus of claim 21, wherein the one or more processing units are further configured to:

determine routeability for at least a portion of the indoor region based on the approximated locations of walls.

28. The apparatus of claim 21, further comprising one or more processing units configured to:

compute values of a radio heatmap database based on locations of transceivers and the approximated locations of walls.

29. The apparatus of claim 28, wherein the radio heatmap database comprises received signal strength indicator (RSSI) values.

30. The apparatus of claim 21, wherein the at least one of the subsections within the indoor region comprises an anchor store of a shopping mall, and wherein the one or more processing units are further configured to:

determine a size of the anchor store based on a lookup table; and

constrain the approximated locations of walls based on the determined size.

31. An article comprising:

a non-transitory storage medium comprising machine-readable instructions stored thereon that are executable by a special purpose computing device to;

evaluate a digital map of an indoor region to identify boundaries between subsections within the indoor region;

extract feature labels from the digital map and establish points based on locations of the extracted feature labels;

approximate locations of walls separating rooms within at least one of the subsections by superimposing polygons over the subsections within the indoor region based on the established points; and

generate heat map values at a plurality of points within the at least one polygon based on an estimated number of walls crossed between the plurality of points and at least one transceiver.

32. The article of claim 31, wherein the feature labels identify one or more points of interest.

33. The article of claim 31, wherein the feature labels comprise names of one or more stores.

34. The article of claim 33, further comprising machine-readable instructions stored thereon that are executable by the special purpose computing device to:

approximate the locations of the feature labels based on a quantity of the one or more stores.

35. The article of claim 33, further comprising machine-readable instructions stored thereon that are executable by the special purpose computing device to:

modify the locations of the feature labels based on the names of the one or more stores.

36. The article of claim 31, wherein the polygons comprise Voronoi cells.

37. The article of claim 36, wherein the Voronoi cells are generated based on the locations of said feature labels.

38. The article of claim 31, further comprising machine-readable instructions stored thereon that are executable by the special purpose computing device to:

determine routeability for at least a portion of the indoor region based on the approximated locations of walls.

39. The article of claim 31, further comprising machine-readable instructions stored thereon that are executable by the special purpose computing device to:

compute values of a radio heatmap database based on locations of transceivers and the approximated locations of walls.

40. The article of claim 39, wherein the radio heatmap database comprises received signal strength indicator (RSSI) values.

41. The article of claim 31, wherein at least one of the subsections within the indoor region comprises an anchor store of a shopping mall, the article further comprising machine-readable instructions stored thereon that are executable by the special purpose computing device to:

determine a size of the anchor store based on a lookup table; and

constrain the approximated locations of walls based on the determined size.