Landmark-based location of users

• US 20040243303A1
• Filed: 07/12/2004
• Published: 12/02/2004
• Est. Priority Date: 03/14/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Padmanabhan, Venkata N.
• Granted Patent: US 6,898,518 B2
• Time in Patent Office: Days
• 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-45. -45. (Cancelled).

46. 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.

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

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

49. The database of claim 46, wherein the user-noticeable features are added to the database via manual annotation.

50. The database of claim 46, wherein the user-noticeable features are described in the database with common linguistic terms used to describe the user-noticeable features.

51. The database of claim 46, wherein each landmark in the database is either likely to be identified by a user or is large enough to cause occlusion of at least one other landmark in the database.

52. 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.

53. The method of claim 52, wherein the simple geometric structure is only four polygons.

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

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

56. The method of claim 53, wherein the user-noticeable features are manually selected.

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

58. The method of claim 53 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.

59. 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.

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

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

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

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

64. The computer-readable medium of claim 59, 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.

65. The computer-readable medium of claim 59 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.