AUTOMATIC LINKING OF POINTS OF INTEREST FOR INDOOR LOCATION BASED SEARCHING

• US 20110179027A1
• Filed: 06/11/2010
• Published: 07/21/2011
• Est. Priority Date: 01/21/2010
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Gupta, Rajarshi, Das, Saumitra Mohan, Khorashadi, Behrooz
• Granted Patent: US 8,359,344 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

A database of the location based relationships of points of interest within an environment is automatically generated using a digital representation of the environment that includes the points of interest at different locations within the environment. The locations of the points of interest in the environment are identified and the location based relationships between the points of interest are determined. The points of interest are labeled with the determined relationships and the points of interest and labeled relationships are stored. For example, a graph structure may be produced where each node is a point of interest and the edges between nodes is labeled with the determined relationships.

Claims

1. A method comprising:

inputting a digital representation of an environment into a processor, the digital representation including points of interest at different locations within the environment;

identifying the locations of the points of interest in the environment;

determining location based relationships between the points of interest in the environment;

labeling the location based relationships of the points of interest in the environment to produce labeled location based relationships; and

storing the points of interest and the labeled location based relationships.

2. The method of claim 1, wherein inputting the digital representation of the environment comprises inputting into the processor the points of interest indexed with reference to the locations in the environment.

3. The method of claim 1, wherein the digital representation of the environment includes identification of rooms that are disconnected from each other by doors, wherein determining location based relationships between the points of interest in the environment comprises determining the points of interest having locations within a same room and determining the points of interest having locations that are not within a same room, and wherein labeling the location based relationships of the points of interest in the environment comprises labeling the relationships of the points of interest that have locations within the same room and that have locations that are not within the same room.

4. The method of claim 3, further comprising identifying doors to rooms in the digital representation of the environment and wherein determining the points of interest having locations within the same room comprises determining the points of interest that are not separated by a door.

5. The method of claim 1, wherein determining location based relationships between the points of interest in the environment comprises identifying the points of interest within a predetermined distance from one another and wherein labeling the location based relationships of the points of interest in the environment, labels the points of interest based on the predetermined distance.

6. The method of claim 5, wherein the predetermined distance is related to time to walk from one point of interest to another.

7. The method of claim 1, wherein determining location based relationships between the points of interest in the environment comprises identifying distances between a first point of interest and a plurality of points of interest of a same type and comparing the distances to identify a shortest distance between the first point of interest and a second point of interest out of the plurality of points of interest and wherein labeling the location based relationships of the points of interest in the environment, labels the relationship between the first point of interest and the second point of interest based on the shortest distance.

8. The method of claim 1, wherein storing the points of interest and the labeled location based relationships comprises outputting from the processor a graph structure with nodes representing the points of interest and edges between the nodes annotated with the labeled location based relationships between the points of interest.

9. The method of claim 1, wherein the points of interest include room numbers in the environment.

10. An apparatus comprising:

an external interface for receiving a digital representation of an environment, the digital representation including points of interest at different locations within the environment;

a processor connected to the external interface;

memory connected to the processor; and

software held in the memory and run in the processor to cause the processor to identify the locations of the points of interest in the environment from the digital representation of the environment;

determine location based relationships between the points of interest in the environment;

label the location based relationships of the points of interest in the environment to produce labeled location based relationships; and

store the points of interest and the labeled location based relationships.

11. The apparatus of claim 10, wherein the digital representation of the environment includes the points of interest indexed with reference to the locations in the environment.

12. The apparatus of claim 10, wherein the software run in the processor causes the processor to identify rooms in the environment from the digital representation of the environment, determine the points of interest having locations within a same room and the points of interest having locations that are not within a same room, and label the points of interest with locations within the same room and locations that are not within the same room.

13. The apparatus of claim 12, wherein the software run in the processor causes the processor to identify doors to rooms in the digital representation of the environment and determine the points of interest that are not separated by a door to determine the points of interest having locations within the same room.

14. The apparatus of claim 10, wherein the software run in the processor causes the processor to determine location based relationships between the points of interest in the environment by identifying the points of interest within a predetermined distance from one another and label the points of interest based on the predetermined distance.

15. The apparatus of claim 14, wherein the predetermined distance is related to time to walk from one point of interest to another.

16. The apparatus of claim 10, the software run in the processor causes the processor to determine location based relationships between the points of interest in the environment by identifying distances between a first point of interest and a plurality of points of interest of a type and comparing the distances to identify a shortest distance between the first point of interest and a second point of interest out of the plurality of points of interest and label the location based relationships for the first point of interest and the second point of interest based on the shortest distance.

17. The apparatus of claim 10, wherein the software run in the processor causes the processor to output a graph structure with nodes representing the points of interest and edges between the nodes annotated with the labeled location based relationships between the points of interest to be stored.

18. The apparatus of claim 10, wherein the points of interest include room numbers in the environment.

19. A system for generating a database of location based relationships of points of interest within an environment, the system comprising:

means for receiving a digital representation of the environment including points of interest at different locations within the environment;

means for identifying the locations of the points of interest in the environment;

means for determining location based relationships between the points of interest in the environment;

means for labeling the location based relationships of the points of interest in the environment to produce labeled location based relationships; and

means for storing the points of interest and the labeled location based relationships.

20. The system of claim 19, the digital representation of the environment includes identification of rooms that are disconnected from each other by doors, wherein the means for determining location based relationships between the points of interest in the environment determines the points of interest having locations within a same room and the points of interest having locations that are not within a same room, and the means for labeling the location based relationships of the points of interest in the environment, labels the relationships of the points of interest that have locations within the same room and that have locations that are not within the same room.

21. The system of claim 19, wherein the means for determining location based relationships between the points of interest in the environment identifies the points of interest within a predetermined distance from one another and the means for labeling the location based relationships of the points of interest in the environment, labels the points of interest based on the predetermined distance.

22. The system of claim 21, wherein the predetermined distance is related to time to walk from one point of interest to another.

23. The system of claim 19, wherein the means for determining location based relationships between the points of interest in the environment identifies distances between a first point of interest and a plurality of points of interest of a same type and compares the distances to identify a shortest distance between the first point of interest and a second point of interest out of the plurality of points of interest, and the means for labeling the location based relationships of the points of interest in the environment, labels the first point of interest and the second point of interest based on the shortest distance.

24. The system of claim 19, wherein the means for storing the points of interest and the labeled location based relationships outputs a graph structure with nodes representing the points of interest and edges between the nodes annotated with the labeled location based relationships between the points of interest.

25. The system of claim 19, wherein the points of interest include room numbers in the environment.

26. A computer-readable medium including program code stored thereon, comprising:

program code to identify locations of points of interest in an environment from a digital representation of the environment;

program code to determine location based relationships between the points of interest in the environment;

program code to label the location based relationships of the points of interest in the environment to produce labeled location based relationships; and

program code to store the points of interest and the labeled location based relationships.

27. The computer-readable medium of claim 26, further comprising program code to identify rooms in the environment from the digital representation of the environment, program code to determine the points of interest having locations within a same room and the points of interest having locations that are not within a same room.

28. The computer-readable medium of claim 26, wherein the program code to determine location based relationships between the points of interest in the environment identifies the points of interest within a predetermined distance from one another and the program code to label the location based relationships of the points of interest in the environment, labels the points of interest based on the predetermined distance.

29. The computer-readable medium of claim 28, wherein the predetermined distance is related to time to walk from one point of interest to another.

30. The computer-readable medium of claim 26, wherein the program code to determine location based relationships between the points of interest in the environment identifies distances between a first point of interest and a plurality of the points of interest of a same type and compares the distances to identify a shortest distance between the first point of interest and a second point of interest out of the plurality of points of interest and the program code to label the location based relationships of the points of interest in the environment, labels the first point of interest and the second point of interest based on the shortest distance.

31. The computer-readable medium of claim 26, further comprising program code to output a graph structure with nodes representing the points of interest and edges between the nodes annotated with the labeled location based relationships between the points of interest to be stored.

32. The computer-readable medium of claim 26, wherein the points of interest include room numbers in the environment.