SYSTEM AND METHOD FOR DETERMINING LOCATIONS WITHIN POINTS OF
INTEREST
BACKGROUND OF THE INVENTION
Field of the Invention
[0001] The present invention relates to a system and method for determining one or more locations within a point of interest for use in a navigation or mapping device.
Description of Related Art
[0002] GPS-based navigation devices are widely employed as in-car navigation systems. These devices have software that enables a user to input a start and destination address, then calculates the best route between the two points and displays instructions on how to navigate that route. By using the positional information derived from the GPS receiver, the software can determine at regular intervals the position of a pedestrian, vehicle, or other object, can display its current position on a map, and can display and/or vocalize appropriate navigation instructions. Graphics depicting the actions to be accomplished (i.e. a left arrow indicating a left turn ahead) can be displayed in a status bar, and also be superimposed over the applicable turns in the roads shown in the map itself.
[0003] Map data for these devices comes from specialized map vendors. This map data is specially designed to be used by route guidance algorithms, typically using location data from the GPS system. For example, roads can be defined as lines or vectors, with a starting point, an ending point, and a direction. An entire road may be made up of hundreds of vectors, each uniquely defined by its own starting point, ending point, and direction parameters. A map integrates a set of such road vectors, as well as data associated with each vector (such as speed limit, travel direction, etc.), points of interest (such as shopping malls, airports, hospitals, etc.), road names, and geographic features (such as parks, mountains, rivers, etc.). Each of these map features is typically defined in a coordinate system that corresponds with or relates to the GPS coordinate system, enabling a device's position as determined through a GPS system to be located within a road shown in a map, and for an optimal route to be planned to a destination. [0004] A probe trace of a journey may be planned and completed using a GPS satellite navigation device. This trace is a record of the route taken by a vehicle, during a trip or a part of a trip, using geocoded data. The user can then send this trace data back to the device vendor or a third party, which is conventionally used to improve the accuracy and completeness of the map database. For example, the precise position of a road or a turn may not be accurately captured on a map used by a device; the aggregated traces for people taking that road or turn will enable a more accurate position to be determined. Future map releases by the device vendor can then incorporate the updates.
SUMMARY OF THE INVENTION
[0005] There is a need in the art for systems and methods for determining one or more locations within a point of interest to further improve the accuracy and completeness of the map database. The present invention meets those needs and other needs by receiving geographic coordinates associated with points of interest from probe traces and associating them with one or more locations within the point of interest. The particular locations can be stored in a database as a subset of the point of interest.
[0006] One embodiment of the invention provides a method and system for determining multiple locations within a point of interest. The method preferably comprises deriving a plurality of geographic coordinates associated with the point of interest from a probe trace, associating the plurality of geographic coordinates with particular locations within the point of interest based on one or more inferences, and storing the particular locations in a database as a subset of the point of interest. The system preferably comprises modules configured to carry out the steps of the method.
[0007] The method may further comprise displaying the particular locations. The particular locations may be displayed as a map and/or as a routing option. The point of interest may be selected from the group consisting of an airport, a hospital, a shopping mall, an arena, an office, and a train station. The particular locations may include one or more of an entry point, a parking lot, a parking garage, a terminal, an eatery, a restroom, a shop, and a department. The probe trace may be received from a personal navigation device. [0008] Still other aspects, features and advantages of the present invention are readily apparent from the following detailed description, simply by illustrating a number of exemplary embodiments and implementations, including the best mode contemplated for carrying out the present invention. The present invention also is capable of other and different embodiments, and its several details can be modified in various respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and descriptions are to be regarded as illustrative in nature, and not as restrictive.
BRIEF DESCRIPTION OF THE DRAWINGS
[0009] The present invention will be understood more fully from the detailed description given below and from the accompanying drawings of various embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments, but are for explanation and understanding only.
[0010] FIG. 1 is a flowchart illustrating a method according to one embodiment.
[0011] FIG. 2 is a schematic diagram illustrating a method for determining a location within a point of interest according to one embodiment.
[0012] FIG. 3 is another schematic diagram illustrating a method for determining a location within a point of interest according to one embodiment.
[0013] FIG. 4 is another schematic diagram illustrating a method for determining a location within a point of interest according to one embodiment.
[0014] FIG. 5 is another schematic diagram illustrating a method for determining a location within a point of interest according to one embodiment.
[0015] FIG. 6 is an exemplary system for implementing the method according to one embodiment.
DETAILED DESCRIPTION
[0016] A system and method for determining multiple locations within a point of interest is described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the exemplary embodiments. It is apparent to one skilled in the art, however, that the present invention can be practiced without these specific details or with an equivalent arrangement. In some instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the preferred embodiment.
[0017] Referring now to the drawings, wherein like reference numerals designate identical or corresponding parts throughout the several views, FIG. 1 is a flowchart 100 illustrating a method for determining multiple locations within a point of interest. At processing block 110, a plurality of geographic coordinates associated with the point of interest are received from a probe trace. As discussed above, a probe trace is a record of a complete route collected from a navigation device indicating the position of the route over a period of time. A point of interest may be, for example, a shopping mall, airport, hospital, restaurant, landmark, arena, office, train station, or any other natural or manmade structure or group of structures. The geographic coordinates received from the probe trace are associated with the point of interest because, for example, they are within a specified distance of the point of interest.
[0018] At processing block 120, the plurality of geographic coordinates are associated with particular locations within the point of interest based on one or more inferences. The particular locations within the point of interest may be, for example, an entry point, a parking lot, a parking garage, a terminal, an eatery, a restroom, a shop, a department, and the like, or a combination thereof. Inferences may be made through a variety of methods in order to associate the plurality of geographic coordinates with particular locations. For example, if multiple geographic coordinates are received in close proximity to one another and at similar positions near a grocery store, it can be inferred that the entry and/or exit points of the grocery store are located near those geographic coordinates. Thus, the geographic coordinates in that example would be associated with an entry point.
[0019] At processing block 130, the particular locations are stored in a database as a subset of the point of interest. Each point of interest may have multiple locations stored as a subset. For example, a shopping mall may have multiple shops, restaurants, restrooms, parking lots, parking garages, entry points, and their associated geographic coordinates, stored as a subset of the shopping mall data. Once the information is stored and reviewed for accuracy, future map releases may include the multiple locations as subsets of the points of interest, and allow direct routing to those locations.
[0020] FIG. 2 is a schematic diagram illustrating a method for determining a location within a point of interest according to one embodiment. In FIG. 2, vehicle 210 having a navigation device requests a route from an origin associated with house 220 to a destination associated with airport 230. Vehicle 210 travels from house 220 to airport 230, stopping briefly at point 240 within a relatively close specified distance of terminal 230A, as evidenced by a plurality of probe traces. Vehicle 210 then returns to house 220, bypassing terminals 230B and 230C.
[0021] Based on this information, the system can infer that vehicle 210 stopped at terminal 230A to either drop someone off or pick someone up from the airport, due to the close distance by which vehicle 210 approached airport 230 and the only brief stop made at terminal 230A before returning to house 220. Thus, the system can identify terminal 230A as a location within airport 230, and store the geographic coordinates of terminal 230A in a database as a subset of airport 230. Further, the system can prompt the user of vehicle 210 to enter more detailed information about terminal 230A, such as which airlines serve that terminal and save that information along with the geographic coordinates for terminal 230A.
[0022] In FIG. 3, vehicle 310 having a navigation device requests a route from an origin associated with house 320 to a destination associated with airport 230. Vehicle 310 travels from house 320 to airport 230, stopping for some period of time at point 340 within a specified distance x of airport 230, as evidenced by a plurality of probe traces. Vehicle 310 then returns to house 320.
[0023] A variety of inferences can be made depending on how long vehicle 310 stays at point 340, and how far the specified distance x is from airport 230. For example, if vehicle 310 is at point 340 for 2 hours, and point 340 is within a quarter mile of airport 230, the system can infer that an hourly parking garage and/or cell phone waiting area is located at point 340, and save information about the location to a database as a subset of airport 230. If vehicle 310 is at point 340 for 2 days, and point 340 is within a mile of airport 230, the system can infer that a daily parking garage is located at point 340, and save information about the daily parking garage to a database as a subset of airport 230. In another example, if vehicle 310 is at point 340 for 2 weeks, and point 340 is within 5 miles of airport 230, the system can infer that a long-term and/or off-site parking garage is located at point 340, and save information about the location as a subset of airport 230. Various rules and algorithms can be used to derive significant points of the traces.
[0024] In FIG. 4, vehicle 410 having a navigation device requests a route from an origin associated with house 420 to a destination within shopping mall 400, such as a department store. Vehicle 410 travels from house 420 to shopping mall 400, stopping for some period of time at point 440 within a specified distance of entrance 400B, as evidenced by a plurality of probe traces. Vehicle 410 then returns to house 420, bypassing entrances 400A and 400C.
[0025] Based on this information, the system can infer that the department store is located within shopping mall 400 near point 440. Further, the system can infer that the entrance closest to the department store, or the entrance to shopping mall 440 nearest the department store, is entrance 400B, and associate entrance 400B with the department store within shopping mall 400.
[0026] In FIG. 5, vehicle 510 having a navigation device requests a route from an origin associated with house 520 to a destination associated with office building 500. Vehicle 510 travels from house 520 to office building 500, stopping for some period of time at point 540 apparently within office building 500, as evidenced by a plurality of probe traces. Vehicle 410 then returns to house 520. Based on the receipt of probe traces seemingly within office building 500 and the stop of vehicle 510 at point 540, the system can infer that a parking garage is located within office building 500, and store the parking garage as subset of office building 500.
[0027] Although described and illustrated with respect to a single route taken by a single personal navigation device to a single destination in the above examples, locations within a points of interest can be identified based on a plurality of routes taken by a plurality of navigation devices to a same location by aggregating the data and making inferences on the entire available information. Furthermore, although described above with respect to round trips, one-way, single destination or multiple destination trips may also be made with similar inferences.
[0028] FIG. 6 illustrates system of an embodiment for effecting the functions described above. Server 710 is connected over network 740 to a plurality of navigation devices 750. Server 710 includes memory 720 and processor 730, which are in communication with one another. Server 710 is configured to receive and deliver content to users at the plurality of navigation devices 750. Server 710 is typically a computer system, and may be an HTTP (Hypertext Transfer Protocol) server, such as an Apache server. Memory 720 may be any type of storage media that may be volatile or non-volatile memory that includes, for example, readonly memory (ROM), random access memory (RAM), magnetic disk storage media, optical storage media, flash memory devices, and zip drives. Network 740 may be a local area network (LAN), wide area network (WAN), a telephone network, such as the Public Switched Telephone Network (PSTN), an intranet, the Internet, or combinations thereof. The plurality of navigation devices 750 may be personal navigation devices, satellite devices, or computer-readable mediums on other computing devices, such as personal computers, laptops, personal digital assistants (PDAs), cell phones, netbooks, thin clients, and the like. The plurality of navigation systems 750 are characterized in that they are capable of being connected to network 740.
[0029] In use, when a user of one of the plurality of navigation devices 750 routes to a point of interest, a plurality of probe traces indicating the location of navigation device 750 are communicated to server 710 over network 740. For example, a signal is transmitted from one of the navigation devices 750, the signal having a destination address (e.g., address representing the server), content (e.g., a probe trace), and a return address (e.g., address representing the navigation device that sent the content). Processor 730 associates geographic coordinates of the probe traces with particular locations within the point of interest based on one or more inferences, and stores the particular locations in memory 720 as a subset of the point of interest.
[0030] It should be noted that the server as illustrated and discussed herein has various modules which perform particular functions and interact with one another. It should be understood that these modules are merely segregated based on their function for the sake of description and represent computer hardware and/or executable software code which is stored on a computer-readable medium for execution on appropriate computing hardware. The various functions of the different modules and units can be combined or segregated as hardware and/or software stored on a computer-readable medium as above as modules in any manner, and can be used separately or in combination. [0031] Further, it should be understood that processes and techniques described herein are not inherently related to any particular apparatus and may be implemented by any suitable combination of components. Further, various types of general purpose devices may be used in accordance with the teachings described herein. It may also prove advantageous to construct specialized apparatus to perform the method steps described herein. The present invention has been described in relation to particular examples, which are intended in all respects to be illustrative rather than restrictive. Those skilled in the art will appreciate that many different combinations of hardware, software, and firmware will be suitable for practicing the present invention.
[0032] Other implementations of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. Various aspects and/or components of the described embodiments may be used singly or in any combination. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.