Method of operating a navigation system Number:7,149,626 from the United States Patent and Trademark Office (PTO) owispatent A method for operating a navigation system obtains an ordered plurality of interconnected segments providing a route from an origin to a destination. A guidance message for each of the segments is formed. The step of forming the guidance message comprises determining whether to reference a previous segment and adding a reference to a current segment.<H navigation, operating, Method, of, opera, 7149626.html, Patent, pto, 7149626

Title: Method of operating a navigation system

Abstract: A method for operating a navigation system obtains an ordered plurality of interconnected segments providing a route from an origin to a destination. A guidance message for each of the segments is formed. The step of forming the guidance message comprises determining whether to reference a previous segment and adding a reference to a current segment.

Patent Number: 7,149,626 Issued on 12/12/2006 to Devries, et al.

Inventors: Devries; Steven P. (Schererville, IN), Herbst; James M. (Chicago, IL), Hopkins; Karen A. (Chicago, IL), McGrath; Suzanne M. (Chicago, IL), Bauer; Ellen M. (Chicago, IL), Bennett; James R. (San Jose, CA), Borak; Jason M. (Algonquin, IL)
Assignee: Navteq North America, LLC (Chicago, IL)

Appl. No.: 10/881,310

Filed: June 30, 2004

Current U.S. Class: 701/211 ; 701/201; 701/208; 701/209; 701/25

Current International Class: G01C 21/30 (20060101)

Field of Search: 701/201,202,23,25,209,211,208,212 340/988 342/357.01,357.13

References Cited [Referenced By]

U.S. Patent Documents


6119065	September 2000	Shimada et al.
6321161	November 2001	Herbst et al.
6339746	January 2002	Sugiyama et al.
6374182	April 2002	Bechtolsheim et al.
6405128	June 2002	Bechtolsheim et al.
6442478	August 2002	Hamada et al.
6490522	December 2002	Suigiyama et al.
6510379	January 2003	Hasegawa et al.
6526350	February 2003	Sekiyama
6542811	April 2003	Doi
6577950	June 2003	Shimazu
6594581	July 2003	Matsuda et al.
6622089	September 2003	Hasegawa et al.
6728636	April 2004	Kokojima et al.
6735515	May 2004	Bechtolsheim et al.
6751549	June 2004	Kozak
6766245	July 2004	Padmanabhan
6922630	July 2005	Maruyama et al.
2002/0120397	August 2002	Kepler
2002/0120398	August 2002	Matsuda et al.
2003/0158650	August 2003	Abe et al.
2003/0176965	September 2003	Padmanabhan
2004/0122591	June 2004	MacPhail

Foreign Patent Documents


1030167	Aug., 2000	EP
1160694	May., 2001	EP
1305783	Nov., 2004	EP

Primary Examiner: Jeanglaude; Gertrude A.
Attorney, Agent or Firm: Shutter; Jon D. Kozak; Frank J. O'Brien; Grace L.

Claims

We claim:

1. A method of operating a navigation system comprising: providing a geographic database containing data that represent geographic features in a geographic region; obtaining an ordered plurality of interconnected segments providing a route from an origin to a destination, wherein said route includes at least a first segment followed by a second segment; and forming a guidance message for said second segment, said step of forming said guidance message comprising: obtaining data associated with said first segment from said geographic database that indicates whether a reference to the first segment provides orientation for an end user traveling from said first segment to said second segment; if said data indicates said reference provides orientation, providing a phrase of after or a synonym thereof and a name of said first segment; providing an indication of travel direction to said second segment; and providing a reference to said second segment.

2. The method of claim 1 wherein said name of said first segment is a name of at least one feature visible from a location proximate said first segment.

3. The method of claim 1 wherein said reference to said second segment includes one of a predetermined number of phrases and a name of said second segment.

4. The method of claim 3 wherein said name of said second segment is a name of at least one feature visible from a location proximate said second segment.

5. The method of claim 3 wherein said one of a predetermined number of phrases is selected from the group consisting of above, through, by, right, left, between, up, down, across, after, along, past and synonyms thereof.

6. The method of claim 1 wherein said step of forming said guidance message further comprising: determining whether to reference a current node, wherein said current node connects said first segment to said second.

7. The method of claim 6 wherein if said step of determining whether to reference said current node determines to reference said currents node, said guidance message includes a phrase of at or a synonym thereof and a name of said current node.

8. The method of claim 6 wherein said step of determining whether to reference a current node comprising: obtaining data associated with said current node from said geographic database that indicates whether a reference to the current node provides orientation for an end user traveling from said first segment to said second segment.

9. The method of claim 1 wherein said step of providing said direction of travel comprising: calculating an angle between said first segment and said second segment; and adding to said guidance message a turn direction corresponding to said angle.

10. The method of claim 1 wherein said step of forming said guidance message further comprising: determining whether to reference a next node, wherein said next node connects said second segment to a next segment.

11. The method of claim 10 wherein if said step of determining whether to reference said next node, said guidance message includes a phrase of toward or a synonym thereof and a name of said next node.

12. A navigation system comprising: a geographic database containing data that represent geographic features in a geographic region; a route calculation application that generates an ordered list of interconnected segments providing a route from an origin to a destination; and a route guidance application that generates a guidance message for each segment of said route, wherein said guidance message for a current segment is generated by: obtaining data associated with a previous segment from the geographic database that indicates whether a name of the previous segment provides orientation for an end user on said route traveling to said current segment; if said data indicates said name of the previous segment provides orientation, providing said name of said previous segment, wherein said name of said previous segment is a name of a geographic feature visible from said previous segment; providing an indication of travel direction to said current segment; and providing a name of said current segment, wherein said name of said current segment is a name of a geographic feature visible from said current segment.

13. The navigation system claim 12 wherein prior to said name of said previous segment said guidance message includes a phrase of after or a synonym thereof.

14. The navigation system of claim 12 wherein prior to or after said name of said current segment includes a phrase selected from a group consisting of above, through, by, right, left, between, up, down, across, after, along, past and synonyms thereof.

15. The navigation system of claim 12 wherein said guidance message further comprising: a reference to a current node, wherein said current node connects said previous segment to said current segment.

16. The navigation system of claim 15 wherein said reference to said current node includes a phrase of at or a synonym thereof and a name of said current node.

17. The navigation system of claim 12 wherein said generating said guidance message further comprising: calculating an angle between said previous segment and said current segment; and adding to said guidance message a turn direction corresponding to said angle for said a direction of travel.

18. The navigation system of claim 12 wherein said guidance message further comprising: a reference to a next node, wherein said next node connects said current segment to a next segment.

19. The navigation system of claim 18 wherein said reference to said next node includes a phrase of toward or a synonym thereof and a name of said next node.

20. A navigation system comprising: a route guidance application that provides a guidance message, wherein said guidance message comprising: a phrase of after or a synonym thereof; a name of a previous segment, wherein said name of said previous segment is a name of a geographic feature visible from a location proximate said previous segment; an indication of a travel direction to a current segment; and a name of said current segment, wherein said name of said current segment is a name of a geographic feature visible from a location proximate said current segment.

21. The navigation system of claim 20 wherein prior to or after said name of said current segment said guidance messages comprising a phrase selected from a group consisting of above, through, by, right, left between, up, down, across, after, along, past and synonyms thereof.

Description

REFERENCE TO RELATED APPLICATIONS

The present application is related to the co-pending application entitled "METHOD OF COLLECTING INFORMATION FOR A GEOGRAPHIC DATABASE FOR USE WITH A NAVIGATION SYSTEM" filed on the same date herewith, application Ser. No. 10/881,312, the entire disclosure of which is incorporated by reference herein. The present application is related to the co-pending application entitled "METHOD OF COLLECTING INFORMATION FOR A GEOGRAPHIC DATABASE FOR USE WITH A NAVIGATION SYSTEM" filed on the same date herewith, application Ser. No. 10/881,660, the entire disclosure of which is incorporated by reference herein. The present application is related to the co-pending application entitled "PERIOD OF COLLECTING INFORMATION FOR A GEOGRAPHIC DATABASE FOR USE WITH A NAVIGATION SYSTEM" filed on the same date herewith, application Ser. No. 10/880,660, the entire disclosure of which is incorporated by reference herein. The present application is related to the co-pending application entitled "METHOD OF OPERATING A NAVIGATION SYSTEM USING IMAGES" filed on the same date herewith, application Ser. No. 10/880,815, the entire disclosure of which is incorporated by reference herein. The present application is related to the co-pending application entitled "METHOD OF COLLECTING INFORMATION FOR A GEOGRAPHIC DATABASE FOR USE WITH A NAVIGATION SYSTEM" filed on the same date herewith, application Ser. No. 10/880,816, the entire disclosure of which is incorporated by reference herein.

BACKGROUND OF THE INVENTION

The present invention relates to a method and system for collecting information for a geographic database, and more particularly to a method and system for collecting pedestrian-related information for a geographic database.

Vehicle navigation systems are available that provide end users with various navigation-related functions and features. For example, some navigation systems are able to determine an optimum route to travel along a road network from an origin location to a destination location in a geographic region. Using input from the end user, and optionally from equipment that can determine the end user's location (such as a GPS system), the navigation system can examine various potential routes between the origin and destination locations to determine the optimum route. The navigation system may then provide the end user with information about the optimum route in the form of guidance that identifies the driving maneuvers required to be taken by the end user to travel from the origin to the destination location. The guidance may take the form of visual and/or audio instructions that are provided along the way as the end user is traveling the route. Some navigation systems are able to show detailed maps on displays outlining the route, the types of maneuvers to be taken at various locations along the route, locations of certain types of features, and so on.

In order to provide these and other navigation-related functions and features, navigation systems use geographic data. The geographic data may be in the form of one or more geographic databases that include data representing physical features in the geographic region. The geographic database includes information about the represented geographic features, such as the positions of the roads, speed limits along portions of roads, address ranges along the road portions, turn restrictions at intersections of roads, direction restrictions, such as one-way streets, and so on. Additionally, the geographic data may include points of interest, such as restaurants, hotels, airports, gas stations, stadiums, police stations, and so on.

Although navigation systems provide many important features, there continues to be room for new features and improvements. One area in which there is room for improvement relates to determining a route for a pedestrian and to providing guidance to the pedestrian following the route. Pedestrian routes and guidance provides challenges not associated with vehicle guidance. Pedestrians are not limited to travel only on the road network; rather, pedestrians may walk through public spaces, such as plazas and parks, having no associated road network. Additionally, pedestrians do not have direction restrictions as a vehicle; pedestrians can walk down a one-way street in both directions. Moreover, pedestrians have a greater degree of freedom of motion and may become more frequently confused as to their orientation to destination.

Accordingly, it would be beneficial to have an improved way to guide users of a navigation system.

SUMMARY OF THE INVENTION

To address these and other objectives, the present invention comprises a method for operating a navigation system. The method obtains an ordered plurality of interconnected segments providing a route from an origin to a destination. The method forms a guidance message for each of the segments. The step of forming the guidance message comprises determining whether to reference a previous segment and adding a reference to a current segment.

Another aspect of the present invention is a navigation system comprising a route guidance application that provides a guidance message for each segment of a route between an origin and a destination. The guidance message comprises a reference to a previous segment and a reference to a current segment.

BRIEF DESCRIPTION OF THE DRAWINGS

An exemplary embodiment of the present invention is described herein with reference to the following drawings.

FIG. 1 is a block diagram of a navigation system, according to an exemplary embodiment.

FIG. 2 illustrates a map of a geographic region.

FIG. 3 is a block diagram of a geographic database included in the navigation system depicted in FIG. 1, according to an exemplary embodiment.

FIG. 4 is a block diagram of components of data records contained in the geographic database depicted in FIG. 3, according to an exemplary embodiment.

FIG. 5 is a representation of a portion of the geographic region depicted in FIG. 2, according to an exemplary embodiment.

FIG. 6 is a flow chart for collecting pedestrian information for unorganized geographic areas, according to an exemplary embodiment.

FIG. 7A is a representation of a plaza.

FIG. 7B is a representation of the plaza of FIG. 7A containing virtual pedestrian segments, according to an exemplary embodiment.

FIG. 8 is a flow chart collecting pedestrian information for organized geographic areas, according to an exemplary embodiment.

FIG. 9A is a flow chart for collecting pedestrian text route guidance information, according to an exemplary embodiment.

FIG. 9B is a representation of a portion of a train station.

FIG. 10 is a block diagram of components of pedestrian segment and orientation node data records, according to an exemplary embodiment.

FIG. 11 is a table of pedestrian segment data records in the geographic database, according to an exemplary embodiment.

FIG. 12 is a table of orientation node data records in the geographic database, according to an exemplary embodiment.

FIG. 13 is a block diagram of components of a pedestrian text route guidance data record, according to an exemplary embodiment.

FIG. 14 is a block diagram illustrating components of the output of a route calculation function, according to an exemplary embodiment.

FIG. 15 is a flow chart for creating a pedestrian guidance message, according to an exemplary embodiment.

FIGS. 16A D is a flow chart that depicts a more detailed method of constructing the pedestrian guidance message as the depicted in FIG. 15, according to an exemplary embodiment.

FIGS. 17A and 17B provide examples of creating pedestrian guidance messages, according to an exemplary embodiment.

FIGS. 18A, 18B and 18C are screen shots of pedestrian guidance messages a pedestrian may receive using the navigation system of FIG. 1.

DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS

I. Navigation System

FIG. 1 is a block diagram of a navigation system 100 associated with a computing platform 102, such as a personal digital assistant (PDA), mobile telephone or any other computer, according to an exemplary embodiment. The navigation system 100 is a combination of hardware and software components. In one embodiment, the navigation system 100 includes a processor 104, a drive 106 connected to the processor 104, and a non-volatile memory storage device 108 for storing navigation application software programs 110 and possibly other information.

The navigation system 100 also includes a positioning system 112. The positioning system 112 may utilize GPS-type technology, a dead reckoning-type system, or combinations of these or other systems, all of which are known in the art. The positioning system 112 may include suitable sensing devices that measure the traveling distance speed, direction, orientation and so on. The positioning system 112 may also include a GPS system. The positioning system 112 outputs a signal to the processor 104. The navigation application software programs 110 that run on the processor 104 use the signal from the positioning system 112 to determine the location, direction, orientation, etc., of the computing platform 102.

The navigation system 100 also includes a user interface 114 that allows the end user to input information into the navigation system 100 and obtain information from the navigation system 100. The input information may include a request for navigation features and functions of the navigation system 100. To provide navigation features and functions, the navigation system 100 uses a geographic database 116 stored on a storage medium 118. In one embodiment, the storage medium 118 is installed in the drive 106 so that the geographic database 116 can be read and used by the navigation system 100. In one embodiment, the geographic database 116 may be a geographic database published by NAVTEQ North America, LLC of Chicago, Ill. The storage medium 118 and the geographic database 116 do not have to be physically provided at the location of the navigation system 100. In alternative embodiments, the storage medium 118, upon which some or the entire geographic database 116 is stored, may be located remotely from the rest of the navigation system 100 and portions of the geographic data provided via a communications system 120, as needed.

In one exemplary type of system, the navigation application software programs 110 load from the non-volatile memory storage device 108 into a random access memory (RAM) 122 associated with the processor 104. The processor 104 also receives input from the user interface 114. The navigation system 100 uses the geographic database 116 stored on the storage medium 118, possibly in conjunction with the outputs from the positioning system 112 and the communications system 120, to provide various navigation features and functions. The navigation application software programs 110 may include separate applications (or subprograms) that provide the various navigation-related features and functions. The navigation functions and features may include route calculation 124 (wherein a route from an origin to a destination is determined), route guidance 126 (wherein detailed directions are provided for reaching a desired destination), map display 128, and positioning 130 (e.g., map matching).

Other functions and programming 132 may be included in the navigation system 100. The navigation application software programs 110 may be written in a suitable computer programming language such as C, although other programming languages, such as C++ or Java, are also suitable. All of the components described above may be conventional (or other than conventional) and the manufacture and use of these components are known to those of skill in the art.

II. Geographic Database

In order to provide navigation-related features and functions to the end user, the navigation system 100 uses the geographic database 116. The geographic database 116 includes information about one or more geographic regions. FIG. 2 illustrates a map 200 of a geographic region 202. The geographic region 202 may correspond to a metropolitan or rural area, a state, a country, or combinations thereof, or any other area. Located in the geographic region 202 are physical geographic features, such as roads, points of interest (including businesses, municipal facilities, etc.), lakes, rivers, railroads, municipalities, etc.

FIG. 2 also includes an enlarged map 204 of a portion 206 of the geographic region 202. The enlarged map 204 illustrates part of a road network 208 in the geographic region 202. The road network 208 includes, among other things, roads and intersections located in the geographic region 202. As shown in the portion 206, each road in the geographic region 202 is composed of one or more road segments 210. A road segment 210 represents a portion of the road. Each road segment 210 is shown to have associated with it two nodes 212; one node represents the point at one end of the road segment and the other node represents the point at the other end of the road segment. The node 212 at either end of a road segment 210 may correspond to a location at which the road meets another road, i.e., an intersection, or where the road dead-ends.

Referring to FIG. 3, the geographic database 116 contains data 302 that represents some of the physical geographic features in the geographic region 202 depicted in FIG. 2. The data 302 contained in the geographic database 116 includes data that represent the road network 208. In the embodiment of FIG. 3, the geographic database 116 that represents the geographic region 202 contains at least one road segment database record 304 (also referred to as "entity" or "entry") for each road segment 210 in the geographic region 202. The geographic database 116 that represents the geographic region 202 also includes a node database record 306 (or "entity" or "entry") for each node 212 in the geographic region 202. The terms "nodes" and "segments" represent only one terminology for describing these physical geographic features, and other terminology for describing these features is intended to be encompassed within the scope of these concepts.

The geographic database 116 may also include other kinds of data 312. The other kinds of data 312 may represent other kinds of geographic features or anything else. The other kinds of data may include point of interest data. For example, the point of interest data may include point of interest records comprising a type (e.g., the type of point of interest, such as restaurant, hotel, city hall, police station, historical marker, ATM, golf course, etc.), location of the point of interest, a phone number, hours of operation, etc. The geographic database 116 also includes indexes 314. The indexes 314 may include various types of indexes that relate the different types of data to each other or that relate to other aspects of the data contained in the geographic database 116. For example, the indexes 314 may relate the nodes in the node data records 306 with the end points of a road segment in the road segment data records 304. As another example, the indexes 314 may relate point of interest data in the other data records 312 with a road segment in the segment data records 304.

FIG. 4 shows some of the components of a road segment data record 304 contained in the geographic database 116. The road segment data record 304 includes a segment ID 304(1) by which the data record can be identified in the geographic database 116. Each road segment data record 304 has associated with it information (such as "attributes", "fields", etc.) that describes features of the represented road segment. The road segment data record 304 may include data 304(2) that indicate the restrictions, if any, on the direction of vehicular travel permitted on the represented road segment. The road segment data record 304 includes data 304(3) that indicate a speed limit or speed category (i.e., the maximum permitted vehicular speed of travel) on the represented road segment. The road segment data record 304 may also include data 304(4) indicating whether the represented road segment is part of a controlled access road (such as an expressway), a ramp to a controlled access road, a bridge, a tunnel, a toll road, a ferry, and so on.

The road segment data record 304 also includes data 304(6) providing the geographic coordinates (e.g., the latitude and longitude) of the end points of the represented road segment. In one embodiment, the data 304(6) are references to the node data records 306 that represent the nodes corresponding to the end points of the represented road segment.

The road segment data record 304 may also include or be associated with other data 304(7) that refer to various other attributes of the represented road segment. The various attributes associated with a road segment may be included in a single road segment record, or may be included in more than one type of record which cross-references to each other. For example, the road segment data record 304 may include data identifying what turn restrictions exist at each of the nodes which correspond to intersections at the ends of the road portion represented by the road segment, the name or names by which the represented road segment is known, the street address ranges along the represented road segment, and so on.

FIG. 4 also shows some of the components of a node data record 306 contained in the geographic database 116. Each of the node data records 306 may have associated information (such as "attributes", "fields", etc.) that allows identification of the road segment(s) that connect to it and/or it's geographic position (e.g., its latitude and longitude coordinates). For the embodiment shown in FIG. 4, the node data records 306(1) and 306(2) include the latitude and longitude coordinates 306(1)(1) and 306(2)(1) for their node. The node data records 306(1) and 306(2) may also include other data 306(1)(3) and 306(2)(3) that refer to various other attributes of the nodes.

III. Collecting Pedestrian Data

Referring to FIG. 2, the enlarged portion 206 of the illustrated geographic region 202 includes a portion of the road network 208 and a portion of a park 214. In one embodiment, the navigation system 100 provides navigation-related features and functions to a user operating a motor vehicle, such as a truck, car or motorcycle. For this embodiment, the navigation system 100 utilizes data representing the road network 208 in the geographic database 116 to provide navigation-related features and functions, such as route calculation and route guidance. For example, the route calculation application provides a continuous navigable route from the origin to the destination as an order list identifying a plurality of road segment data entities. The route guidance application provides maneuvering instructions along the road network to follow the calculated route.

In another embodiment, the navigation system 100 provides navigation-related features and functions to a user that is not operating a motor vehicle, such as a pedestrian. For this example, the pedestrian is not limited to travel only on the road network 208. Rather, the pedestrian may walk through public plazas and parks having no associated road network. Additionally, the pedestrian does not have direction restrictions as a vehicle; the pedestrian can walk down a one-way street in both directions. Moreover, the pedestrian has a greater degree of freedom of motion and may become more frequently confused as to their orientation.

FIG. 5 illustrates a portion of a park 214 in the geographic region 202 of FIG. 2. Suppose the pedestrian requests a route from the navigation system 100 from his or her current position 502 to a cafe 504. If the navigation system 100 calculated the route using only the road network 208, the route to the cafe 504 would comprise consecutive road segments 506, 508, 510 and 512 with left turn maneuvers at nodes 514 and 516. However, since the pedestrian can walk through the park, a more direct and shorter route is possible. To allow the navigation system 100 to provide improved pedestrian routes, a geographic database developer collects information relating to the geographic features of the geographic region useful for providing pedestrians and other users with navigation-related features and functions. In one embodiment, a geographic researcher travels the geographic region to collect information relating to geographic features useful for providing pedestrians with navigation-related features and functions (hereinafter "pedestrian data"). In another embodiment, the geographic researcher uses aerial images to collect pedestrian data.

A. Collecting Pedestrian Data for Unorganized Geographic Areas

An unorganized geographic area is a geographic area that lacks underlying organization into paths or roads. That is, the unorganized geographic area does not contain path or road geometry marked by paving, contrasting ground cover, such as a dirt trail through a grassy meadow, or paint trails over concrete. For example, the park illustrated in FIG. 5, includes established paths 518 and 520, paved or unpaved; however, the park also includes an unorganized portion 522 over which the pedestrian may walk without any paths, such as over grassy areas.

FIG. 6 is a flow chart 600 for collecting pedestrian data for unorganized geographic areas, according to an exemplary embodiment. The steps of FIG. 6 will be illustrated using the unorganized geographic area 522 of the park 214 of FIG. 5. At step 600, the geographic researcher identifies a portion of the unorganized geographic area appropriate for a virtual pedestrian network. The virtual pedestrian network is similar to the road network 208. Whereas the road network 208 comprises of road segments and nodes, the virtual pedestrian network comprises virtual pedestrian segments and orientation nodes. Whereas a vehicle may be routed and guided from an origin to a destination over the road network 208, a pedestrian or other user may be routed and guided from an origin to a destination over, in part or entirely, the virtual pedestrian network which traverses unorganized geographic area lacking the road network or established paths. In one embodiment, the geographic researcher identifies a portion of the unorganized geographic area appropriate for a virtual pedestrian network by determining that pedestrians may readily traverse the unorganized geographic area, that pedestrians may reduce their travel distance and/or travel time by traversing the unorganized geographic area and/or that pedestrians may desire to be routed and guided to a feature or point of interest within the unorganized geographic area.

Once the geographic researcher has identified a portion of the unorganized geographic area appropriate for the virtual pedestrian network, the geographic researcher identifies a series of interconnected virtual pedestrian segments and associated orientation nodes. Each virtual pedestrian segment is associated with two orientation nodes; one orientation node represents one end of the virtual pedestrian segment and the other orientation node represents the other end of the virtual pedestrian segment. The orientation node at either end of the virtual pedestrian segment may correspond to a location at which the virtual pedestrian segment meets another virtual pedestrian segment, where the virtual pedestrian segment meets a road segment, where the virtual pedestrian segment meets a pedestrian segment associated with a path of an organized geographic area, at a point of interest or where the virtual pedestrian segment dead-ends.

Referring to FIG. 6, at step 602, the geographic researcher identifies an orientation node. The location of the orientation node is selected at a location that may be readily described to provide orientation to the pedestrian. In one embodiment, the orientation node is selected at a location that may be visually identified by the pedestrian. For the exemplary embodiment illustrated in FIG. 5, an orientation node 524 is located near a statue 526. The statue 526 is a prominent feature readily visually observed by the pedestrian. Additionally, a clear and concise description of the statue 526, such as statue of a man on a horse, provides orientation to the pedestrian.

At step 604, the researcher collects attribute information of the orientation node. Attribute information includes descriptive words characterizing the location of the orientation node and any surrounding features, such as statue of a man on a horse, for orientation node 524. The attribute information also may include a latitude and longitude position of the orientation node. A positioning system may be used to determine the latitude and longitude position of the orientation node. The position system may utilize GPS-type technology, a dead reckoning-type system, or combinations of these or other systems, all of which are known in the art. The positioning system may include suitable sensing devices to obtain a GPS signal and to measure the traveling distance speed, direction, and so on, of the system. Alternatively, aerial images of the area may be used to determine the position of the orientation node.

Other attribute information of the orientation node that may be collected include: wheel chair accessible, children friendly, pet friendly, well-lighted area, poorly lighted area, busy area, non-busy area, noisy/peaceful, smelly/polluted, sheltered from rain, not sheltered from rain, no bikes allowed, tree lined, paved area, unpaved area, grassy area, gravel area, dirt area, muddy when wet area, and any other attribute information. The geographic researcher may record the attribute information using any data collection method, such as handwriting, voice recording, and data entry into a user device. In one embodiment, the researcher may capture an image of the orientation node including the surrounding area with a digital camera. Furthermore, the researcher may collect guidance information as discussed below in conjunction with FIG. 8 for the orientation node.

In one embodiment, the researcher collects connection information indicating whether the orientation node is in close proximity to the road network 208. If the orientation node is close to the road network 208, the researcher identifies the road node close to the orientation node. In another embodiment, the researcher may identify a road segment for connection information. The researcher may record the connection information in the form of a street address, name or ID of a road segment or road node, a distance from a node along an identified road segment, intersection of two identified road segments, a point of interest or in any other appropriate form. For the example depicted in FIG. 5, the researcher records connection information identifying that orientation node 524 connects with road segment 506. If the orientation node is not close to the road network, the researcher records such an indication.

At step 606, the geographic researcher identifies another orientation node. The second orientation node 528 is selected at another location that may be readily described to provide orientation to the pedestrian. Additionally, the second orientation node is selected at a location in which the pedestrian may be directed from the first orientation node location to the second orientation node location. In one embodiment, the second orientation node is selected at a distance from the first orientation node such that the pedestrian may visually identify the location of the second orientation node from the location of the first orientation node. In another embodiment, the second orientation node location may be obscured from view or beyond visual identification from the first orientation node location. For example, the pedestrian may be directed to walk in a certain direction, such as toward a lake, and after walking some distance, the second orientation node comes into view.

For the exemplary embodiment illustrated in FIG. 5, a second orientation node 528 is located near a barbeque pit 530. The barbeque pit 530 is a prominent feature readily visually observed by the pedestrian. Additionally, a clear and concise description of the barbeque pit 530, such as a stone barbeque pit with pizza oven feature, provides orientation to the pedestrian. At step 608, the researcher collects attribute information of the orientation node in the similar manner as discussed above for the first orientation node 524.

At step 610, the researcher identifies a virtual pedestrian segment 532. The virtual pedestrian segment 532 is an artificially created segment over the unorganized portion 522 on which the pedestrian may walk from the first orientation node 524 to the second orientation node 528. When identifying the virtual pedestrian segments, the geographic researcher insures that the pedestrian may walk unobstructed from the first to the second orientation node. For example, the geographic researcher would not identify a virtual pedestrian segment that goes over a cliff.

At step 612, the researcher collects attribute information of the virtual pedestrian segment. Attribute information includes descriptive words characterizing the virtual pedestrian segment and any surrounding features. For example, virtual pedestrian segment 532 may be described as "keeping the pond on your right/left." The attribute information may also include a distance or length of the virtual pedestrian segment, such as 50 meters, or an estimated travel time to walk the virtual pedestrian segment. Other attribute information of the virtual pedestrian segment that may be collected include: wheel chair accessible, children friendly, pet friendly, well-lighted area, poorly lighted area, busy area, non-busy area, noisy, peaceful, smelly/polluted, sheltered from rain, not sheltered from rain, no bikes allowed, tree lined, paved area, unpaved area, grassy area, gravel area, dirt area, muddy when wet area, hilly, steps, rough terrain, grade, and any other attribute information. Additionally, the researcher may collect information relating to points of interest proximate the virtual pedestrian segment including location of bike racks, water fountains, toilets, historic sites, recreational facilities, entrances to points of interest or any other information. Additionally, the researcher may collect position data along the virtual pedestrian segment to be used as shape points for cartographically representing the virtual pedestrian segment. In one embodiment, the researcher may capture an image of the virtual pedestrian segment including the surrounding area with a digital camera. Furthermore, the researcher may collect guidance information as discussed below in conjunction with FIG. 8 for the virtual pedestrian segment.

Referring to FIG. 5, the researcher continues to identify orientation nodes and virtual pedestrian segments for the unorganized area 522. For example, another orientation node 534 is identified near tennis courts 536, and another virtual pedestrian segment 538 connects orientation node 528 with orientation node 534. Yet another orientation node 540 is identified near the cafe 504 and a parking lot 542, and another virtual pedestrian segment 544 connects orientation node 534 with orientation node 540.

In alternative embodiments, the steps for collecting pedestrian data for unorganized geographic areas are performed in a different order than presented in FIG. 6. In another embodiment, the researcher identifies a first orientation node, identifies a virtual pedestrian segment from the first orientation node and then identifies a second orientation node completing the virtual pedestrian segment. In yet another embodiment, the researcher identifies virtual pedestrian segments and then identifies orientation nodes along the virtual pedestrian segments. For example, the researcher collects pedestrian data for a scenic walk along a lakefront by first identifying virtual pedestrian segments along the lakefront and then identifying orientation nodes between the virtual pedestrian segments.

FIG. 7A illustrates another unorganized geographic area 700. The unorganized area 700 is a plaza in a city center. A portion of the road network 702 comprising several road segments 704 and nodes 706 surrounds the plaza 700. The plaza may be paved but lacks underlying organization into paths, such as paths provided by paint markings or paths marked by contrasting paving bricks. Despite the lack of organization into paths, the pedestrian is free to walk through the plaza. In one embodiment, the researcher collects pedestrian data for the plaza 700 in a similar manner as described above in conjunction with FIG. 6. For the exemplary embodiment of FIG. 7A, the researcher identifies the unorganized geographic area 700 of the plaza as appropriate for a virtual pedestrian network because pedestrians may readily traverse the plaza 700 and pedestrians may reduce their travel distance and/or travel time by traversing the plaza 700.

To collect the pedestrian data, the researcher identifies orientation nodes 708 in close proximity to the road network nodes 706 associated with intersecting road segments 702 that bound the plaza 700. FIG. 7B illustrates orientation nodes 708 in close proximity to the road nodes 706 of the intersections bounding the plaza 700. The researcher also collects attribute information for each of the orientation nodes 708. The attribute information includes words characterizing the location of the orientation node and any surrounding features, such as the street names of the corresponding intersection, a street address, description of prominent building, prominent signage or point of interest adjacent the orientation node. Additionally, the collected attribute information may include a latitude and longitude position. Other information of the orientation node may be collected including wheel chair accessible, children friendly, pet friendly, well-lighted area, poorly lighted area, busy area, non-busy area, noisy, peaceful, smelly/polluted, sheltered from rain, not sheltered from rain, no bikes allowed, tree lined, paved area, unpaved area, grassy area, gravel area, dirt area, muddy when wet area, shaded, shopping zone, curb cutouts, crosswalks and any other attribute information. In one embodiment, the researcher may capture an image of the orientation nodes including their respective surrounding areas with a digital camera.

For the exemplary embodiment of FIGS. 7A and 7B, the researcher also identifies orientation nodes within the center of plaza 700. The researcher identifies orientation nodes 710 at the center portions of the plaza 700. The researcher also collects attribute information for each of the orientation nodes 710. The attribute information includes words characterizing the location of the orientation node and any surrounding features, such as band pavilion, large fountain, statue of bald man, prominent buildings or any other feature. Additionally, the collected attribute information may include a latitude and longitude position and other information as discussed above for orientation nodes 708.

For the exemplary embodiment of FIGS. 7A and 7B, the researcher also identifies virtual pedestrian segments 712 between the identified orientation nodes 708 and 710 within the plaza 700. The researcher identifies the virtual pedestrian segments connecting two of the orientation nodes 708 and 710. A virtual pedestrian segment may be established between each of the orientation nodes; however, the researcher may decide to establish virtual pedestrian segments between only certain orientation nodes because the path between some of the orientation nodes may be blocked, such as by seasonal cafe seating. The researcher also collects attribute information for each of the virtual pedestrian segments 712. The attribute information includes descriptive words characterizing the virtual pedestrian segment and any surrounding features. Additionally, the collected attribute information may include an approximate length of the virtual pedestrian segment, or any other attribute information as discussed above. In one embodiment, the researcher may capture an image of the virtual pedestrian segments including their surrounding areas with a digital camera. Referring to FIG. 7B, after the researcher has identified orientation nodes 708 and 710 and the virtual pedestrian segments 712, the virtual pedestrian network provides navigatable geometry over which the pedestrian may be routed and guided.

B. Collecting Pedestrian Data for Organized Geographic Areas

An organized geographic area is a geographic area that has underlying organization into paths and roads. For example, the park illustrated in FIG. 5, includes established paths 518 and 520, paved or unpaved. The geographic researcher collects pedestrian data to provide a pedestrian network using the underlying organization. The pedestrian network is similar to the road network 208. Whereas the road network 208 comprises road segments and nodes, the pedestrian network comprises pedestrian segments following existing paths and orientation nodes on or near existing paths. Whereas a vehicle may be routed and guided from an origin to a destination over the road network 208, a pedestrian may be routed and guided from an origin to a destination over, in part or entirely, the pedestrian network which traverses the organized geographic area using existing or established paths. To develop the pedestrian network, the geographic researcher identifies a series of interconnected pedestrian segments and associated orientation nodes. Each pedestrian segment is associated with two orientation nodes; one orientation node represents one end of the pedestrian segment and the other orientation node represents the other end of the pedestrian segment. The orientation node at either end of the pedestrian segment may correspond to a location at which the pedestrian segment meets another pedestrian segment, where the pedestrian segment meets a road segment, where the pedestrian segment meets a virtual pedestrian segment, at a point of interest or where the pedestrian segment dead-ends.

FIG. 8 is a flow chart for collecting pedestrian data for organized geographic areas, according to an exemplary embodiment. The steps of FIG. 8 will be illustrated using the established paths 518 and 520 of the park 214 of FIG. 5. In one embodiment, the geographic researcher walks the paths 518 and 520 to collect the pedestrian data. At step 800, the geographic researcher identifies an orientation node for the existing path 518. The location of an orientation node is selected at a location that may be readily described to provide orientation to the pedestrian. In one embodiment, orientation nodes are provided at the intersection of two or more established paths. In one embodiment, the orientation node is selected at a location that may be visually identified by the pedestrian. For the exemplary embodiment illustrated in FIG. 5, an orientation node 548 is located near the entrance gate 550 of the park. The entrance gate 550 is a prominent feature readily visually observed by the pedestrian. Additionally, a clear and concise description of the entrance gate 550, such as entrance gate to park from X Street, provides orientation to the pedestrian.

At step 802, the researcher collects attribute information of the orientation node. The attribute information also may include a latitude and longitude position of the orientation node. A positioning system may be used to determine the latitude and longitude position of the orientation node. The position system may utilize GPS-type technology, a dead reckoning-type system, or combinations of these or other systems, all of which are known in the art. The positioning system may include suitable sensing devices to obtain a GPS signal and to measure the traveling distance speed, direction, and so on, of the system. Alternatively, aerial images of the area may be used to determine the position of the orientation node. Other attribute information of the orientation node that may be collected include: wheel chair accessible, children friendly, pet friendly, well-lighted area, poorly lighted area, busy area, non-busy area, noisy, peaceful, smelly/polluted, sheltered from rain, not sheltered from rain, no bikes allowed, tree lined, paved area, unpaved area, grassy area, gravel area, dirt area, muddy when wet area, and any other attribute information. The geographic researcher may record the attribute information using any data collection method, such as handwriting, voice recording, and data entry into a user device.

At step 804, the researcher collects guidance information for the orientation node. Guidance information includes descriptive words characterizing the location of the orientation node and any surrounding features, such as entrance gate to park from X Street for orientation node 548. These descriptive words will be used as the name for the orientation node. In one embodiment, the researcher collects the name of the orientation node as a name of a feature visible from the location of orientation node. For the example provided in FIG. 5, the name for the orientation node may be "entrance gate to park from X Street." In one embodiment, the researcher identifies the time of day or seasonal restrictions on the descriptive words or orientation node name. For example, during nighttime hours or during the frozen winter, the entrance gate may not be readily visible to the pedestrian. The geographic researcher may record time and season appropriate alternatives.

Additional guidance information collected by the researcher is a calculate angle data. That is, the researcher indicates whether maneuvers may be performed at the orientation node, such as at the intersection of two or more pedestrian segments. If maneuvers may be performed at the orientation node, the route guidance feature will have to calculate a maneuver angle. For orientation node 548 in FIG. 5, the researcher indicates a yes for the calculate angle data. Furthermore, the researcher collects at explication data. That is, an indication of whether the descriptive words characterizing the location of the orientation node and any surrounding features are helpful to indicate where a maneuver is to be performed or helpful to indicate where the pedestrian is located at when guiding the pedestrian on a route that passes through the orientation node. For the example in FIG. 5, the researcher records a yes indication for the at explication data indicating that "at the entrance gate" provides useful guidance for pedestrians at the orientation node 548. In one embodiment, the researcher may capture an image of the orientation node 548 and its surroundings with a digital camera.

In one embodiment, the researcher also collects connection information indicating whether the orientation node is in close proximity to the road network 208. If the orientation node is close to the road network 208, the researcher identifies the road node close to the orientation node. In another embodiment, the researcher may identify a road segment for connection information. The researcher may record the connection information in the form of a street address, name or ID of a road segment or road node, a distance from a node along an identified road segment, intersection of two identified road segments, a point of interest or in any other appropriate form. If the orientation node is not close to the road network, the researcher records such an indication.

At step 806, the researcher identifies a pedestrian segment. Referring to FIG. 5, the pedestrian segment 552 is a portion of the established path 518. At step 808, the researcher collects attribute information of the pedestrian segment 552. The attribute information also may include a latitude and longitude positions of shape points along the pedestrian segment 552. The attribute information may also include a distance or length of the pedestrian segment, such as 50 meters or an estimated travel time to walk the pedestrian segment. Other attribute information of the pedestrian segment that may be collected include: wheel chair accessible, children friendly, pet friendly, well-lighted area, poorly lighted area, busy area, non-busy area, noisy, peaceful, smelly/polluted, sheltered from rain, not sheltered from rain, no bikes allowed, tree lined, paved area, unpaved area, grassy area, gravel area, dirt area, muddy when wet area, hilly, steps, rough terrain, grade, and any other attribute information. Additionally, the researcher may collect information relating to points of interest proximate the pedestrian segment including location of bike racks, water fountains, toilets, historic sites, recreational facilities, entrances to points of interest or any other information. Additionally, the researcher may collect position data along the pedestrian segment to be used as shape points for cartographically representing the pedestrian segment. In one embodiment, the researcher may capture an image of the pedestrian segment 552 and its surroundings with a digital camera.

At step 810, the researcher collects guidance information for the pedestrian segment 552. The guidance information includes descriptive words characterizing the pedestrian segment and any surrounding features. These descriptive words will be used as the name of the pedestrian segment. In one embodiment, the researcher collects the name of the pedestrian segment as a name of a feature visible from the path. In one embodiment, the visible feature is a readily identifiable geographic feature other than the path itself. In one embodiment, the researcher uses a list of predetermined phrase words for the text description the pedestrian segment. Table I lists phrase words that the researcher may use to collect descriptive words characterizing the pedestrian segment according to an exemplary embodiment. Additional phrase words may be used than those listed in Table I.

TABLE-US-00001 TABLE I PHRASE ID PHRASE WORDS 1 ABOVE 2 THROUGH 3 BY 4 KEEPING <blank> ON YOUR RIGHT 5 BETWEEN 6 UP 7 DOWN 8 ACROSS 9 AFTER 10 ALONG 11 KEEPING <blank> ON YOUR LEFT 12 PAST

Referring to FIG. 5, the researcher collects descriptive words characterizing the pedestrian segment 552 and/or its surroundings as "keeping the <POND> on your left." That is, the name of a visible feature from the pedestrian segment 552 is the "POND," and the phrase words "keeping the <blank> on your left" in conjunction with the visible features provide a text description of the pedestrian segme