Landmark-based location of users

• US 6,766,245 B2
• Filed: 03/14/2002
• Issued: 07/20/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.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Gibson, Eric M.
• Application Number:
  US10/097,285
• Publication Number:
  US 20030176965A1
• Time in Patent Office: 859 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 method for determining a location of a user, the method comprising:

receiving a user input comprising a first landmark description of a first landmark visible to the user;

comparing the first landmark description to a database of known landmarks;

deriving, from the database of known landmarks, a first candidate landmark for the first landmark as a function of the first landmark description;

calculating a first visibility region for the first candidate landmark, wherein the calculating the first visibility region comprises determining whether the candidate landmark is visible from more than one location; and

determining the location of the user as a function of the first visibility region.

2. The method of claim 1, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the determining the location of the user is a function of an intersection of the first visibility region and a second visibility region if the first visibility region and the second visibility region intersect, and is a function of the first visibility region if the first visibility region and the second visibility region do not intersect, the method further comprising:

comparing the second landmark description to the database of known landmarks;

deriving, from the database of known landmarks, a second candidate landmark for the second landmark as a function of the second landmark description;

calculating the second visibility region for the second candidate landmark;

intersecting the first visibility region with the second visibility region; and

discarding the second candidate landmark if the first visibility region and the second visibility region have no intersection.

3. The method of claim 1, wherein the deriving the first candidate landmark comprises requesting additional information from the user.

4. The method of claim 1, wherein the calculating the first visibility region further comprises:

dividing an area covered by the database of known landmarks into subsections;

determining if the first candidate landmark is visible from the subsections, wherein the first candidate landmark is considered visible from a selected subsection if the first candidate landmark is visible from at least one point in the selected subsection.

5. The method of claim 4, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the determining the location of the user is a function of an intersection of the first visibility region and a second visibility region within a joint visibility subsection from which both the first candidate landmark and a second candidate landmark are visible, the method further comprising:

comparing the second landmark description to the database of known landmarks;

deriving, from the database of known landmarks, the second candidate landmark for the second landmark as a function of the second landmark description;

calculating a second visibility region for the second candidate landmark, wherein the calculating comprises;

determining if the second candidate landmark is visible from the subsections, wherein the second candidate landmark is considered visible from the selected subsection if the second candidate landmark is visible from at least one point in the selected subsection;

determining the joint visibility subsection from which both the first candidate landmark and the second candidate landmark are visible; and

intersecting the first visibility region with the second visibility region within the joint visibility subsection from which both the first candidate landmark and the second candidate landmark are visible.

6. The method of claim 1 further comprising:

comparing the determined location of the user to a threshold confidence area;

providing the determined location to the user if the determined location is less than the threshold confidence area; and

requesting additional information from the user if the determined location is greater than the threshold confidence area.

7. The method of claim 1, wherein the calculating the first visibility region further comprises applying a decreasing percentage of visibility to a visibility point within the first visibility region as a distance from the visibility point to the first candidate landmark increases.

8. The method of claim 1, wherein the database of known landmarks is a topographical database containing topographical information about known landmarks in the form of polygonal representations.

9. A method for determining a location of a user, the method comprising:

receiving a user input comprising a first landmark description of a first landmark, and a second landmark description of a second landmark;

deriving at least one first candidate landmark for the first landmark and at least one second candidate landmark for the second landmark by comparing the first landmark description and the second landmark description to a database of known landmarks;

calculating a visibility region for each of the at least one first candidate landmark and the at least one second candidate landmark; and

determining the location of the user as a function of an intersection of the calculated visibility regions.

10. The method of claim 9, wherein the calculating the visibility region comprises:

initially calculating the visibility region for each of the at least one first candidate landmark if there are fewer of the at least one first candidate landmark than there are of the at least one second candidate landmark; and

initially calculating the visibility region for each of the at least one second candidate landmark if there are fewer of the at least one second candidate landmark than there are of the at least one first candidate landmark.

11. A computer-readable medium having computer-executable instructions for determining a location of a user, the computer-executable instructions performing steps comprising:

receiving a user input comprising a first landmark description of a first landmark visible to the user;

comparing the first landmark description to a database of known landmarks;

deriving, from the database of known landmarks, a first candidate landmark for the first landmark as a function of the first landmark description;

calculating a first visibility region for the first candidate landmark, wherein the calculating the first visibility region comprises determining whether the candidate landmark is visible from more than one location; and

determining the location of the user as a function of the first visibility region.

12. The computer-readable medium of claim 11, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the determining the location of the user is a function of an intersection of the first visibility region and a second visibility region if the first visibility region and the second visibility region intersect, and is a function of the first visibility region if the first visibility region and the second visibility region do not intersect, the computer-readable medium having further computer-executable instructions for performing steps comprising:

comparing the second landmark description to the database of known landmarks;

deriving, from the database of known landmarks, a second candidate landmark for the second landmark as a function of the second landmark description;

calculating the second visibility region for the second candidate landmark;

intersecting the first visibility region with the second visibility region; and

discarding the second candidate landmark if the first visibility region and the second visibility region have no intersection.

13. The computer-readable medium of claim 11, wherein the computer-executable instructions for deriving the first candidate landmark comprise computer-executable instructions for requesting additional information from the user.

14. The computer-readable medium of claim 11, wherein the computer-executable instructions for calculating the first visibility region further comprise computer-executable instructions for:

dividing an area covered by the database of known landmarks into subsections;

determining if the first candidate landmark is visible from the subsections, wherein the first candidate landmark is considered visible from a selected subsection if the first candidate landmark is visible from at least one point in the selected subsection.

15. The computer-readable medium of claim 14, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the determining the location of the user is a function of an intersection of the first visibility region and a second visibility region within a joint visibility subsection from which both the first candidate landmark and a second candidate landmark are visible, the computer-readable medium having further computer-executable instructions for performing steps comprising:

comparing the second landmark description to the database of known landmarks;

deriving, from the database of known landmarks, the second candidate landmark for the second landmark as a function of the second landmark description;

calculating a second visibility region for the second candidate landmark, wherein the computer-executable instructions for calculating comprise computer-executable instructions for;

determining if the second candidate landmark is visible from the subsections, wherein the second candidate landmark is considered visible from the selected subsection if the second candidate landmark is visible from at least one point in the selected subsection;

determining the joint visibility subsection from which both the first candidate landmark and the second candidate landmark are visible; and

intersecting the first visibility region with the second visibility region within the joint visibility subsection from which both the first candidate landmark and the second candidate landmark are visible.

16. The computer-readable medium of claim 11 having further computer-executable instructions performing steps comprising:

comparing the determined location of the user to a threshold confidence area;

providing the determined location to the user if the determined location is less than the threshold confidence area; and

requesting additional information from the user if the determined location is greater than the threshold confidence area.

17. The computer-readable medium of claim 11, wherein the computer-executable instructions for calculating the first visibility region further comprise computer-executable instructions for applying a decreasing percentage of visibility to a visibility point within the first visibility region as a distance from the visibility point to the first candidate landmark increases.

18. The computer-readable medium of claim 11 having further computer-executable instructions for performing steps comprising:

determining a second location of the user with a user locating means;

using the determined location of the user and the determined second location of the user to determine a more accurate location of the user.

19. The computer-readable medium of claim 11, wherein the first landmark description comprises information regarding distance and direction between the user and the first landmark, and wherein the computer-executable instructions for determining the location of the user comprise computer-executable instructions for determining the location of the user as a function of the information regarding distance and direction.

20. The computer-readable medium of claim 11, wherein the database of known landmarks is a topographical database containing topographical information about known landmarks in the form of polygonal representations.

21. The computer-readable medium of claim 20 wherein the polygonal representations are smaller than the known landmarks.

22. The computer-readable medium of claim 11 having further computer-executable instructions performing steps comprising:

downloading a section of the database of known landmarks.

23. A computer-readable medium having computer-executable instructions for determining a location of a user, the computer-executable instructions performing steps comprising:

receiving a user input comprising a first landmark description of a first landmark, and a second landmark description of a second landmark;

deriving at least one first candidate landmark for the first landmark and at least one second candidate landmark for the second landmark by comparing the first landmark description and the second landmark description to a database of known landmarks;

calculating a visibility region for each of the at least one first candidate landmark and the at least one second candidate landmark; and

determining the location of the user as a function of an intersection of the calculated visibility regions.

24. The computer-readable medium of claim 23, wherein the computer-executable instructions for calculating the visibility region comprise computer-executable instructions for:

initially calculating the visibility region for each of the at least one first candidate landmark if there are fewer of the at least one first candidate landmark than there are of the at least one second candidate landmark; and

initially calculating the visibility region for each of the at least one second candidate landmark if there are fewer of the at least one second candidate landmark than there are of the at least one first candidate landmark.

25. The computer-readable medium of claim 23, wherein the intersection of the calculated visibility regions is calculated only for a subsection from which the at least one first candidate landmark and the at least one second candidate landmark are visible, and further wherein the computer-executable instructions for calculating the visibility region comprise computer-executable instructions for:

dividing an area covered by the database of known landmarks into subsections;

determining if the at least one first candidate landmark and the at least one second candidate landmark are visible from the subsections, wherein the least one first candidate landmark and the at least one second candidate landmark are considered visible from a selected subsection if the least one first candidate landmark is visible from at least one point in the selected subsection and the at least one second candidate landmark is visible from at least one point in the selected subsection.

26. A portable computing device for determining a location of a user, the portable computing device comprising:

a user input device for receiving a user input comprising a first landmark description of a first landmark visible to the user;

a memory storage device having stored thereon information comprising a database of known landmarks; and

a processing unit for performing steps comprising;

comparing the first landmark description to a database of known landmarks;

deriving, from the database of known landmarks, a first candidate landmark for the first landmark as a function of the first landmark description;

calculating a first visibility region for the first candidate landmark, wherein the calculating the first visibility region comprises determining whether the candidate landmark is visible from more than one location; and

determining the location of the user as a function of the first visibility region.

27. The portable computing device of claim 26, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the determining the location of the user is a function of an intersection of the first visibility region and a second visibility region if the first visibility region and the second visibility region intersect, and is a function of the first visibility region if the first visibility region and the second visibility region do not intersect, the processing unit further performing steps comprising:

comparing the second landmark description to the database of known landmarks;

deriving, from the database of known landmarks, a second candidate landmark for the second landmark as a function of the second landmark description;

calculating the second visibility region for the second candidate landmark;

intersecting the first visibility region with the second visibility region; and

discarding the second candidate landmark if the first visibility region and the second visibility region have no intersection.

28. The portable computing device of claim 26, wherein the deriving the first candidate landmark comprises requesting additional information from the user.

29. The portable computing device of claim 26, wherein the calculating the first visibility region further comprises:

dividing an area covered by the database of known landmarks into subsections;

determining if the first candidate landmark is visible from the subsections, wherein the first candidate landmark is considered visible from a selected subsection if the first candidate landmark is visible from at least one point in the selected subsection.

30. The portable computing device of claim 29, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the determining the location of the user is a function of an intersection of the first visibility region and a second visibility region within a joint visibility subsection from which both the first candidate landmark and a second candidate landmark are visible, the processing unit further performing steps comprising:

comparing the second landmark description to the database of known landmarks;

deriving, from the database of known landmarks, the second candidate landmark for the second landmark as a function of the second landmark description;

calculating a second visibility region for the second candidate landmark, wherein the calculating comprises;

determining if the second candidate landmark is visible from the subsections, wherein the second candidate landmark is considered visible from the selected subsection if the second candidate landmark is visible from at least one point in the selected subsection;

determining the joint visibility subsection from which both the first candidate landmark and the second candidate landmark are visible; and

intersecting the first visibility region with the second visibility region within the joint visibility subsection from which both the first candidate landmark and the second candidate landmark are visible.

31. The portable computing device of claim 26, wherein the processing unit further performs steps comprising:

comparing the determined location of the user to a threshold confidence area;

providing the determined location to the user if the determined location is less than the threshold confidence area; and

requesting additional information from the user if the determined location is greater than the threshold confidence area.

32. The portable computing device of claim 26, wherein the calculating the first visibility region comprises applying a decreasing percentage of visibility to a visibility point within the first visibility region as a distance from the visibility point to the first candidate landmark increases.

33. The portable computing device of claim 26, wherein the database of known landmarks is a topographical database containing topographical information about known landmarks in the form of polygonal representations.

34. A system for determining a location of a user, the system comprising:

a portable computing device comprising;

a user input device for receiving a user input comprising a first landmark description of a first landmark visible to the user; and

a processing unit for performing steps comprising;

determining the location of the user based at least in part, on a first visibility region for the first landmark, wherein the first visibility region was calculated by determining whether the candidate landmark is visible from more than one location; and

an infrastructure device comprising;

a memory storage device having stored thereon at least a part of the database of known landmarks; and

a communication device for performing steps comprising;

connecting to the portable computing device and transmitting a section of the database of known landmarks.

35. The system of claim 34, the communication device performing further steps comprising:

transmitting an infrastructure device location.

36. The system of claim 34 further comprising:

a second portable computing device comprising;

a processing unit for performing steps comprising;

determining a second location of a second user; and

a communication device for performing steps comprising;

connecting to the portable computing device and transmitting a most-recently determined location of the second user.

37. A portable computing device for determining a location of a user, the portable computing device comprising:

a user input device for receiving a user input comprising a first landmark description of a first landmark, and a second landmark description of a second landmark;

a memory storage device having stored thereon information comprising a database of known landmarks; and

a processing unit for performing steps comprising;

deriving at least one first candidate landmark for the first landmark and at least one second candidate landmark for the second landmark by comparing the first landmark description and the second landmark description to a database of known landmarks;

calculating a visibility region for each of the at least one first candidate landmark and the at least one second candidate landmark; and

determining the location of the user as a function of an intersection of the calculated visibility regions.

38. The portable computing device of claim 37, wherein the calculating the visibility region comprises:

initially calculating the visibility region for each of the at least one first candidate landmark if there are fewer of the at least one first candidate landmark than there are of the at least one second candidate landmark; and

initially calculating the visibility region for each of the at least one second candidate landmark if there are fewer of the at least one second candidate landmark than there are of the at least one first candidate landmark.

39. A system for determining a location of a user, the system comprising:

a portable computing device comprising;

a user input device for receiving a user input comprising a first landmark description of a first landmark visible to the user; and

a first communication device for communicating with a server computing device; and

the server computing device comprising;

a second communication device for communicating with the portable computing device;

a memory storage device having stored thereon at least a part of the database of known landmarks; and

a first processing unit for performing steps comprising;

calculating a first visibility region for a first candidate landmark, wherein the calculating the first visibility region comprises determining whether the candidate landmark is visible from more than one location.

40. The system of claim 39, wherein the second communication device transmits a section of the database of known landmarks to the portable computing device.

41. The system of claim 39, wherein:

the first communication device performs steps comprising;

transmitting a request to determine the location of the user to the server computing device,

transmitting the user input to the server computing device, and

receiving from the server computing device the determined location of the user;

the second communication device performs steps comprising;

receiving the request to determine the location of the user,

receiving the user input, and

transmitting to the portable computing device the determined location of the user; and

the first processing unit performs additional steps comprising;

comparing the first landmark description to the database of known landmarks;

deriving, from the database of known landmarks, the first candidate landmark for the first landmark as a function of the first landmark description; and

determining the location of the user as a function of the first visibility region.

42. The system of claim 39, wherein:

the portable computing device further comprises a second processing unit for performing steps comprising;

comparing the first landmark description to the database of known landmarks;

deriving, from the database of known landmarks, the first candidate landmark for the first landmark as a function of the first landmark description; and

determining the location of the user as a function of the first visibility region;

the first communication device performs steps comprising;

transmitting a request to calculate the first visibility region for the first candidate landmark to the server computing device, and

receiving from the server computing device the first visibility region for the first candidate landmark;

the second communication device performs steps comprising;

receiving the request to calculate the first visibility region for the first candidate landmark, and

transmitting to the portable computing device the first visibility region for the first candidate landmark.

43. A portable computing device for determining a location of a user, the portable computing device comprising:

means for receiving a user input comprising a first landmark description of a first landmark visible to the user;

means for storing information comprising a database of known landmarks;

means for comparing the first landmark description to a database of known landmarks;

means for deriving, from the database of known landmarks, a first candidate landmark for the first landmark as a function of the first landmark description;

means for calculating a first visibility region for the first candidate landmark, wherein the calculating the first visibility region comprises determining whether the candidate landmark is visible from more than one location; and

means for determining the location of the user as a function of the first visibility region.

44. The portable computing device of claim 43, wherein the user input further comprises a second landmark description of a second landmark visible to the user, and wherein the means for determining the location of the user include means for determining the location of the user as a function of an intersection of the first visibility region and a second visibility region if the first visibility region and the second visibility region intersect, and is a function of the first visibility region if the first visibility region and the second visibility region do not intersect, the portable computing device further comprising:

means for comparing the second landmark description to the database of known landmarks;

means for deriving, from the database of known landmarks, a second candidate landmark for the second landmark as a function of the second landmark description;

means for calculating the second visibility region for the second candidate landmark;

means for intersecting the first visibility region with the second visibility region; and

means for discarding the second candidate landmark if the first visibility region and the second visibility region have no intersection.

45. A method for determining a location of a user, the method comprising:

a step of receiving a user input comprising a first landmark description of a first landmark visible to the user;

a step of comparing the first landmark description to a database of known landmarks;

a step of deriving, from the database of known landmarks, a first candidate landmark for the first landmark as a function of the first landmark description;

a step of calculating a first visibility region for the first candidate landmark, wherein the calculating the first visibility region comprises determining whether the candidate landmark is visible from more than one location; and

a step of determining the location of the user as a function of the first visibility region.