Landmark-based location of users

• US 6,898,518 B2
• Filed: 07/12/2004
• Issued: 05/24/2005
• Est. Priority Date: 03/14/2002
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Padmanabhan, Venkata N.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Gibson, Eric M.
• Application Number:
  US10/889,397
• Publication Number:
  US 20040243303A1
• Time in Patent Office: 316 Days
• Field of Search: 701/200, 701/207, 701/208, 340/988, 340/995.24, 348/113, 348/116
• US Class Current: 701/207
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence

Abstract

Humans identify location and directions based on visual cues, such as landmarks, rather than a precise coordinate grid. A database of landmarks can be used to determine the location of a user who can merely describe their location in the same manner they would to any human contact. The location of the user can be determined based on the landmarks described in the input, and the areas from which all of those landmarks are visible. Various databases can be used, including text-based and three-dimensional. Similarly, various mechanisms can be used to determine the user'"'"'s location, including hierarchical approaches, query optimization approaches, and visibility percentage approaches. Ultimately, the user'"'"'s location can be determined without the need for expensive, dedicated infrastructure, without compromising the user'"'"'s security, and without subjecting the user to system outages.

Claims

1. A database of landmarks comprising, for each landmark in the database:

topological information related to the landmark, wherein the topological information describes a larger and more geometrically simple structure than the landmark; and

user-noticeable features related to the landmark, wherein the user-noticeable features are prominent features or features that distinguish the landmark from similar landmarks in the database, and wherein further the user noticeable features are added to the database via manual annotation.

2. The database of claim 1, wherein the topological information is automatically derived from a series of overlapping images.

3. The database of claim 2, wherein the topological information is automatically derived from the series of overlapping images using edge histogramming.

4. A method for generating a database of landmarks comprising:

deriving topological information from a series of overlapping images;

quantizing the topological information to represent a simple geometric structure;

increasing the size of the simple geometric structure to account for quantizing errors;

generating descriptions of user-noticeable features of the landmarks; and

linking the descriptions of the user-noticeable features to a corresponding quantized topological information.

5. The method of claim 4, wherein the simple geometric structure is only four polygons.

6. The method of claim 5, wherein the deriving the topological information from the series of overlapping images uses edge historgramming.

7. The method of claim 5, wherein the user-noticeable features are prominent features or features that distinguish a landmark from similar landmarks in the database.

8. The method of claim 5, wherein the user-noticeable features are manually selected.

9. The method of claim 5, wherein the generating descriptions of the user-noticeable features of the landmarks uses common linguistic terms used to describe the user-noticeable features.

10. The method of claim 5 further comprising removing each landmark from the database that is not either:

(1) likely to be identified by a user, or (2) is large enough to cause occlusion of at least one other landmark in the database.

11. A computer-readable medium having computer-executable instructions for generating a database of landmarks, the computer-executable instructions performing steps comprising:

deriving topological information from a series of overlapping images;

quantizing the topological information to represent a simple geometric structure;

increasing the size of the simple geometric structure to account for quantizing errors;

generating descriptions of user-noticeable features of the landmarks; and

linking the descriptions of the user-noticeable features to a corresponding quantized topological information.

12. The computer-readable medium of claim 11, wherein the simple geometric structure is only four polygons.

13. The computer-readable medium of claim 11, wherein the computer-executable instructions for deriving the topological information from the series of overlapping images implement edge historgramming.

14. The computer-readable medium of claim 11, wherein the user-noticeable features are prominent features or features that distinguish a landmark from similar landmarks in the database.

15. The computer-readable medium of claim 11, wherein the user-noticeable features are manually selected.

16. The computer-readable medium of claim 11, wherein the computer-executable instructions for generating descriptions of the user-noticeable features of the landmarks utlize common linguistic terms used to describe the user-noticeable features.

17. The computer-readable medium of claim 11, further comprising removing each landmark from the database that is not either:

(1) likely to be identified by a user, or (2) is large enough to cause occlusion of at least one other landmark in the database.