System for providing driving directions with visual cues

[0002] This invention relates to the field of computerized navigation systems, and in particular, to such systems equipped with a database of image data in addition to the standard routing and directional data.

[0003] Computerized navigation systems are now available which enable a traveler to follow a customized route to his destination, without the use of conventional directions or printed maps. As these systems become more widely available, there will be an increasing need to make them easier to understand and to operate.

[0004] In this regard, it may be easier for some people to remember landmarks than the details of a printed map. People can become lost despite being given both a reasonable map and written directions on how to follow it. In comparison, directions that use objects in the environment that we are likely to notice are more easily followed; for example, “You'll drive for a couple of miles and then pass a bright red farmhouse all by itself; take the first left after that.” Such instructions may be much easier to remember.

[0005] Accordingly, the ease of use of computerized navigation systems would be greatly enhanced if pictorial cues to the geographic data could be provided along with the navigation directions. Specifically, the directions provided by such systems would be easier to follow if the user could see a display of photographs of the actual locations along the route, in addition to the route being displayed in a text or map format.

[0006] In general, presently available enhancements to computerized navigation systems aim to convey additional information which a driver may use to streamline the navigation process. For example, some Japanese systems transmit data about accidents, traffic congestion, availability of parking, road construction, and other specialized data to in-vehicle navigation devices. Such a navigation system may take these data into account when planning routes. In addition, earlier work on synthesized speech and voice-control systems is being incorporated into in-vehicle navigation systems so that drivers need not take their eyes off the road to interact with the system, as reported in Global Positioning& Navigation News.

[0007] In one particular application of computerized navigation, systems incorporating Global Positioning System (GPS) receivers are installed in motor vehicles. Some GPS units, such as the GPS 4000, allow the user to define custom landmarks (“the old oak tree,” “my favorite fishing hole”). These landmarks are shown on the unit's readout whenever the user approaches them.

[0008] Amtrak offers an on-line national map that describes every Amtrak route, scenery along the way, amenities, and seating and sleeping car accommodations. This is not useful to automotive and other travelers not using common carriers who need directions.

[0009] There are a number of maps, both print and computerized, that incorporate business logos. Various cities around the world have tourist-oriented maps that incorporate subject headings (restaurants, hotels, attractions) with logos of relevant businesses into a single interactive web-based map. Various web sites offer point-to-point driving directions between street addresses and/or cities in the United States, Canada, and occasionally, certain cities on other continents. In some instances, corporate logos are superimposed on maps as a way to identify features of interest to the traveler.

[0010] There are various single-user CD-ROM-based navigational products which may optionally be interfaced with portable GPS receivers to provide a real-time superimposition of the GPS location on the digital map. These products may include a variety of multimedia data, e.g. for users who specify San Francisco as their destination, the product might show a photograph of the Golden Gate Bridge. The location in the photograph may or may not be a useful landmark for a traveler following a customized route.

[0011] Several websites provide customized maps and driving directions. Several CD-ROMS, such as Travroute Software's Door-to-Door, also provide this service. MapQuest's maps have a feature called “points of interest” that lets the user choose a set of landmarks to be added to a custom map. For example, one could choose to display all the restaurants near one's destination; these would show up on the map as generic icons (such as a crossed knife and fork) and names. MapQuest also allows companies to pay to have their corporate logo displayed on the map, instead of a generic icon. However, these logos only appear on MapQuest's maps, and do not accompany driving directions. Travroute's Door-to-Door CD-ROM and the Freetrip website have similar features.

[0012] Northern Illinois University provides a campus tour planner on its website, including a clickable campus map with numbers indicating landmarks. Clicking on one of the numbers results in a display of a picture and description of the landmark. This may be viewed as a very small database of photographs for use in navigation. However, this system does not assemble the photographs into a set of customized directions for getting from one point to another.

[0013] Databases of photographs have been used in navigation for robots. One solution to the problem of getting a robot from one point to another is to have it store images of various points along its route, then retrace the route by matching what it sees with images in its database. This system does not, of course, create directions or maps that would be useful to a human.

[0014] “Database Requirements for Vehicle Navigation Systems,” published by the National Center for Geographic Information and Analysis (NCGIA) at the University of Maine, describes different data types and properties necessary for the system to associate adjacent spaces together in an effort to plan a multi-step route. This paper also notes that the U.S. Census Bureau's TIGER (Topologically Integrated Geographic Encoding and Referencing) files, which provide sufficient detail for accurate vehicle navigation, occupy approximately 3,600 megabytes of storage. These files specify the geometry of roads, geographic attribute data, and additional features such as county boundaries.

[0015] U.S. Pat. No. 5,329,108, entitled “Map with indexes for a geographical information system and system for applying same,” describes a method of applying index data to the printed surface of a geographical map; the index data represents information necessary to reproduce the contents of a region of an analog printed map with which the index data is associated.

[0016] U.S. Pat. No. 5,528,518, entitled “System and method for collecting data used to form a geographic information system database,” describes a portable data-acquisition device which combines a GPS receiver and a means of collecting information about objects viewable from the reference location established by the device's absolute geographical location. The device may thus collect location information that describes geography both in terms of its absolute coordinates as determined by the GPS, and with reference to notable objects near each GPS reference point.

[0017] U.S. Pat. No. 5,648,768, entitled “System and method for identifying, tabulating and presenting information of interest along a travel route,” describes a database system for entering starting and destination points, retrieving route information, and presenting the route information alongside other data relevant to the route.

[0018] U.S. Pat. No. 5,614,898, entitled “Guide system,” describes a system for providing supplemental information to users present in a tour bus or similar large-capacity passenger vehicle. If, for example, the bus drives near a famous building, the guide might provide basic information about the landmark, and the system might retrieve extensive historical data and present it in the form of a multimedia show.

[0019] U.S. Pat. No. 5,596,494, entitled “Method and apparatus for acquiring digital maps,” describes a method for acquiring airborne stereoscopic images from satellites and correlating them with GPS coordinates in a three-dimensional space. It is subsequently possible to provide a display of actual location on real photographic maps, rather than approximated digital representations thereof. A plurality of possible GPS coordinates are thus associated with a single visual image. The satellite photographs used in this system are very large-scale and do not offer visual representations of landmarks along an individual traveler's route.

[0020] U.S. Pat. No. 5,587,911, entitled “Navigation system with selective intersection display,” describes a new database format to be used for storing the data traditionally used by navigation systems. In its detailed specification, it describes an external memory “in which is stored all the data necessary for the route guidance including data for maps . . . branching points, photographs, destinations . . . and speech guidance.”

[0021] U.S. Pat. No. 5,537,323, entitled “Navigation device vehicle comprising the device,” describes a navigation system having a map display unit updated in accordance with changes in the user's position.

[0022] U.S. Pat. No. 5,442,557, entitled “Navigation device,” describes an in-car navigation system, featuring a database of “conspicuous objects” to be consulted when assembling routing information for a given origin/destination pair. However, this patent does not mention a database including photographs of all incidental intersections or general-purpose buildings that a user might witness during the navigation process.

[0023] The present invention is an enhancement to existing computerized navigation systems, whereby standard navigational data—maps, distance measurements, and instructions to turn at specific points—are matched with a database of illustrative photographs that will show the user exactly what to look for when following a route to a destination.

[0024] According to one aspect of the invention, a system for providing navigational instructions includes a communication port, a data storage device and a processor. The communication port receives signals representing location information including a starting point and a destination point, and for transmitting the navigational instructions. The data storage device has stored therein geographical information, photographic information, route processing instructions and photograph matching instructions. The photographic information includes digital representations of photographs of actual geographic locations, and the photograph matching instructions are instructions for matching a particular photograph with a corresponding geographic location. The processor processes the location information and the geographical information in accordance with the route processing instructions to obtain a route for travel to the destination point, and matches geographic locations along the route with representations of photographs thereof in accordance with the photograph matching instructions. The processor thereby determines the navigational instructions for traveling the route including representations of photographs. The processor outputs the navigational instructions using the communication port, thereby providing an operator with navigational instructions for traveling the route and a sequence of photographic representations of the geographic locations along the route.

[0025] According to another aspect of the invention, a method of providing navigational instructions has the following steps. A first database is provided which has geographical information. A second database is provided which has photographic information; the photographic information includes representations of photographs of actual geographic locations. Each of the representations of photographs in the second database is matched with the geographical information in the first database, so that a particular photograph has associated therewith the geographical information regarding the location depicted in the photograph. The method also includes a step of receiving location information including a starting point and a destination point. The location information, the geographic information from the first database, and the photographic information from the second database are processed to determine a route for travel to the destination point. Navigational instructions for traveling the route are generated, including representations of photographs. The navigational instructions and the photographic representations of geographic locations are outputted in a sequence, thereby providing an operator with a sequence of navigational instructions and photographic representations of geographic locations along the route.

[0026] FIG. 1 is a block diagram showing an overview of the system of the present invention, including a central controller and interface unit.

[0027] FIG. 2 is a block diagram of the central controller.

[0028] FIG. 3 is a block diagram of the interface unit.

[0029] FIG. 4 is an example of possible output from the system, including representations of photographs.

[0030] FIG. 5 shows in tabular form the fields in the photography database.

[0031] FIG. 6 shows in tabular form the fields in the optional matching results database.

[0032] FIG. 7 is a flowchart describing the photograph acquisition, categorization, and storage process, from the data-gatherer's point of view.

[0033] FIG. 8 is a flowchart describing the routing process executed by the navigational system.

[0034] FIG. 9 is a flowchart describing the process of matching the appropriate photographs to the results of the routing process for concurrent transmission and display.

[0035] FIG. 10 is a flowchart describing the process of checking the matching results database for overlap between an active query and all previously-stored queries, and retrieving any relevant data for further processing as described in FIG. 8.

[0036] This invention allows computer-generated driving directions to include photographs of important intersections and landmarks along the way. The system includes a database of photographs taken from several angles: for example, a four-way intersection would require a photograph for each of the four directions from which it can be approached. The system sequences these photographs and combines them with a set of driving directions (for example, “drive three miles to this intersection, and turn left on Peachtree Street”) that, taken together, guide the user to his or her destination. The photographs help the user recognize when he or she is on the correct route, and also help eliminate ambiguities that might be present in the written directions. (For example, there are dozens of streets called Peachtree in Atlanta, but thanks to the photographs, the user knows he or she needs to turn on the Peachtree Street that has a particular business on the corner).

[0037] An overview of a system embodying the invention is shown in FIG. 1. The system includes a central controller 101 and an interface unit 102, communicating by a communication link 105. If the interface unit 102 is remote from the central controller 101 (for example, if the interface unit 102 is installed in a motor vehicle while the central controller 101 is at a fixed location), the communication link 105 is preferably a high-speed digital communication link. In particular, the communication link 105 may be an on-line or web connection.

[0038] The central controller 101 includes a database (described in more detail below) with photographic information on various geographic locations. This information is obtained from a photography source 103, which may include for example a scanning/digitizing device for converting photographs to binary data. The photographs, of course, may be obtained by conventional methods. However, each photograph should be documented with the coordinates of the location shown and the direction of view of the photograph, in order for the photograph to be useful in presenting navigational instructions.

[0039] The central controller 101 transmits the navigational instructions to the interface unit 102 using the communication link 105. These instructions include not only directions in text form, but also photographic representations of the locations along the route to be followed.

[0040] The interface unit 102 conveys the navigational instructions to the system user (for example, the operator of a vehicle). This is done using an output device such as a display screen.

[0041] Details of the interface device are shown in FIGS. 3 and 4 and discussed below.

[0042] The system user transmits the starting point of his trip and desired destination to the central controller 101 using an input device, such as a keyboard or a microphone. Alternatively, a GPS receiver 104 may be connected to the interface unit; the GPS receiver provides the current location of the user, which the central controller uses as the starting point.

[0043] A more detailed structure of the central controller 101 is shown in FIG. 2. The central controller includes a central processing unit (CPU) 201, which is connected to a clock 202, memory units (RAM 203 and ROM 204) and a communication port 205. In addition, the CPU 201 is connected to a storage device 210, which includes a number of databases.

[0044] The communication port 205 transmits information between the interface unit 102 and the CPU 201. Specifically, the communication port receives signals from the interface unit representing the starting point and destination point of the trip for which the navigational instructions are desired. The communication port transmits those instructions to the interface unit. Software for execution by the CPU is stored in the RAM 203 and/or the ROM 204.

[0045] The databases in the storage device 210 include a geography database 211, a photography database 212, and optionally a matching results database 213 (which relates records in the geography and photography databases to each other). The storage device also includes route process software 214 for generating the navigational instructions, and photo matching process software 215 for matching geographic locations along the route with representations of photographs thereof.

[0046] FIG. 3 shows schematically the structure of the interface unit 102 according to this embodiment. The interface unit 102 includes a CPU 301, which is connected to a clock 302, RAM 303, ROM 304 and a communication port 305. The CPU 301 is connected to an input device 310 and an output device 320. Location information, such as the starting point and destination point, is input using the input device 310. The navigational instructions are output using the output device 320. The communication port 305 transmits information between the central controller 101 and the CPU 301. The optional GPS receiver 104 may be connected to the communication port 305; in the absence of a starting point input to the input device 310, the current location provided by the GPS receiver serves as the starting point. Possible examples of the input device 310 include a keyboard, microphone, touch screen, or a mouse. Possible examples of the output device 320 include a display, a speaker, or a printer.

[0047] FIG. 4 shows a possible format of the navigational instructions output by the system of the present invention, where the output device 320 is a display. The display 401 gives the starting point 411 (as input using the input device 310 or provided by the GPS receiver 104) and the destination point 412, and the navigational instructions on a screen 420. The instructions are given in a sequence of steps 421-1, 421-2, 421-3, etc. It should be noted that the instructions in each step may include either text only (as in 421-3) or a combination of text and a picture (as in 421-1 and 421-2). In the latter case, the picture displayed on the screen is a recreation of a photograph taken of the actual location mentioned in the instructions for that step. A highlight or arrow 425 may be overlaid on the picture display, pointing out the correct direction for the particular route being followed.

[0048] The structure of the photography database 212 is shown schematically in FIG. 5. Each record in this database corresponds to one photograph. A record includes an identification number 501 for the record and a representation 502 of the photograph in the form of binary data. The geographic location shown in the photograph is identified by coordinates 503 (for example, latitude and longitude) and the street address 505. In addition, the record includes the orientation 504 of the photograph; that is, the direction of view of the location shown in the photograph. Preferably the database 212 is accessible via public networks, using common protocols such as HTTP.

[0049] The geography database 211 may conveniently have a structure as is known in the art, such as the TIGER/Line database used by the U.S. Bureau of the Census. The TIGER/Line files contain point and area labels that describe landmarks' features and provide locational reference. Details regarding the format of the TIGER/Line files are available at http://www.census.gov/ftp/pub/geo/www/tiger/tigermetadata.html.

[0050] The structure of the matching results database 213 is shown schematically in FIG. 6. Each record of this database corresponds to a sequence of vectors for traveling a route from a particular starting point to a particular destination point. A record includes the starting address 601, the destination address 602, and a field 603 having identification numbers of the vectors comprising the route to be followed from the starting point to the destination point. The record also includes a field 604 having photography database record identifiers, indicating photographs that match the vectors in field 603.

[0051] FIG. 7 is a flowchart showing the process of building the photography database 211. First, a photograph of a geographic feature (such as an intersection or a landmark building) is taken (step 701). The photographer records the absolute coordinates of the location being photographed (step 702). This may conveniently be done using a mobile GPS unit. The orientation of the photograph is also recorded (step 703), as well as any distinguishing features of the geographic location being photographed (step 704). In addition, the street address of the feature is recorded (step 705). Finally, all of the recorded data is stored in the photography database (step 706).

[0052] FIG. 8 is a flowchart describing the process executed by the central controller to determine the navigational instructions. In step 801, the location information (the present position or starting point and the destination) are received from the interface unit 102 through the communication port 205; this location information is stored in RAM 203. To determine a route between the starting and destination points, the location information is first retrieved along with the route process software 214 (step 802). The CPU 201 computes the route between the starting point and destination point, using the route process software (step 803). The CPU builds a sequential list of geographic vectors to be used in following the route, and stores this list in RAM 203 (step 804). Instructions in natural language, corresponding to the sequence of vectors, are assembled and stored in RAM 203 (step 805). At this point the RAM 203 contains the results of the routing process.

[0053] FIG. 9 shows the process of matching the appropriate photographs to the results of the routing process. This process is performed in accordance with the photo matching process software 215. In step 901, the CPU 201 retrieves the sequential list of geographic vectors and natural language instructions from the RAM 203. The CPU 201 then consults the photography database 212 for photographs corresponding to locations along the route (step 902). Specifically, for each geographic vector in the list, the database 212 is searched for source coordinates 503 and orientations 504 which match the geographic vector. If a match is found, the record identifier 501 for the photograph is stored in the RAM 203 with the geographic vectors for the route (step 903).

[0054] Optionally (step 904), if the navigational instructions are provided as the route is actually traveled, the CPU 201 may receive updates of the location information from the interface unit 102 (which may be automatically provided by GPS receiver 104). The CPU 201 retrieves instructions from RAM 203 relevant to the current location, including any matching photographs, and transmits those instructions to the interface unit 102 for sequential output, for example in display 401.

[0055] The results of the photograph matching process may advantageously be stored in the matching results database 213. Using this database, a set of vectors 603 and matching photographs 604 may be associated with a particular starting address 601 and destination address 602, thereby avoiding the need to repeatedly compute the route between addresses 601 and 602 and search the photography database 212 for appropriate photographs.

[0056] The matching results database 213 may also be used in generating instructions for traveling between addresses not yet in the database. This process is shown schematically in FIG. 10. In step 1001, the starting and destination points are received and stored in RAM 203 (as in step 801). The geographic vectors for a route between the starting and destination points are calculated, using the route process software 214 (step 1002). The CPU 201 then consults the matching results database 213 (step 1003), searching for an overlap between the vectors just calculated and the geographic vectors 603 in the database.

[0057] If an overlap is found (step 1004), the CPU 201 then retrieves the common photographic record identifiers 604 for the photographs associated with those vectors and stores those identifiers in the RAM 203. The full photographic matching process is then performed for those vectors not found in the matching results database 213 (step 1005). This procedure thus minimizes the need to perform new photograph matching when a new route is calculated.

[0058] The operation of the system of this embodiment may be illustrated by the following example. A family moves to a new city, and needs to find the way from their house to the new school their children will attend. The route consists primarily of smaller roads, so there will not be significant signage of the same kind that might be found when traveling on an expressway.

[0059] According to this embodiment of the invention, a sequence of directions might be displayed in display 401 as follows:

[0060] Starting address 411: 123 Anyroad St.

[0061] Destination address 412: Placetown High School.

[0062] The steps to be followed (421-1, 421-2, etc. in FIG. 4) are displayed, with the display 401 updating as the vehicle approaches the locations described:

[0063] 1. Begin by following direction indicated by arrow on system display.

[0064] 2. At corner of Anyroad and 49th, turn right. (Accompanying this instruction is a display of a photograph of the intersection of Anyroad and 49th, as viewed from the direction currently followed by the vehicle.)

[0065] 3. Follow 49th to East Boulevard before train tracks, turn right. (Accompanying this instruction is a display of a photograph of the intersection of 49th and East Boulevard, showing the train tracks and highlighting the area towards which the vehicle should turn.)

[0066] 4. Follow East Boulevard across 41st. (Accompanying this instruction is a display of a photograph of a landmark building such as a fast-food restaurant.)

[0067] 5. Continue to corner of East Boulevard and 37th, school is on right-hand-side. (Accompanying this instruction is a display of a photograph of Placetown High School as viewed from East Boulevard.)

[0068] It should be noted that the actual street address of the high school need not be known. Furthermore, if the family's vehicle has a GPS receiver 104, the system can automatically determine the vehicle's position. In that case the user does not need to input the starting address.

[0069] The present invention has been described in the context of an interface unit 102 which is remote from a central controller 101. However, the invention is not limited to this embodiment. A large number of photographs is required for the system to be useful throughout the United States or internationally. The database 212 of photography information is likely to be correspondingly large. It therefore may be preferable to have the storage device 210 located remotely from the interface unit 102, whether or not the interface unit 102 is remote from the central controller 101.

[0070] In general, the interface unit 102 may comprise any system whereby the user may specify a destination and receive guidance from the central controller 101. If each photograph is stored with a textual description (for example, “a restaurant with red brick walls” or “an intersection with banks on three of the four corners”) then a visual display unit may not even be required.

[0071] The communication link 105 may be any suitable communication path. In a local application, the communication link 105 may be a direct connection. Preferably, the communication link 105 is a remote, network-based connection (for a web site application).

[0072] In an alternative embodiment, the interface unit 102 is installed in a motor vehicle, so that the system of the present invention is a mobile navigational system with the interface unit 102 communicating with a fixed central controller 101. In a further alternative embodiment, the vehicle has a GPS receiver 104 installed therein, so that the central controller 101 is automatically provided with the current location of the vehicle.

[0073] The complete sequence of navigational instructions (including the representations of photographs) may be transmitted to the interface unit 102 at the beginning of the trip and stored in the RAM 303. Alternatively, the instructions may be transmitted in stages as the trip progresses. As digital bandwidth available to mobile sites increases, it will become easier to transmit photographic data to vehicles in transit, thereby reducing the storage requirements of the RAM 303 of the interface unit 102.

[0074] The central controller 101 may alternatively generate the navigational instructions and retrieve the appropriate photographs on an as-needed basis while the route is being followed with no perceptible delay to the user. The effectiveness of this approach depends on the speed of the CPU 201 and the data handling capability of the communication link 105.

[0075] In another alternative embodiment, business logos could be used as a substitute for, or a supplement to, photography. By accessing a system such as the Yellow Pages® the central controller 101 could identify businesses along the user's route and use their logos to illustrate the directions it generates. This would substantially reduce the size of the photography database 212 and avoid the considerable effort involved of gathering photographs of large numbers of landmarks and intersections.

[0076] While the present invention has been described above in terms of specific embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. On the contrary, the present invention is intended to cover various modifications and equivalent structures included within the spirit and scope of the appended claims.