A method of generating improved map data for use in navigation devices

0001This invention relates to a method of generating improved map data for use in navigation devices. Navigation devices include Global Positioning System GPS based electronic personal navigation devices.

0002Map data for electronic navigation devices, such as GPS based personal navigation devices like the GO™ from TomTom International BV, comes from specialist map vendors such as Tele Atlas NV. 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 described as lines - i.e. vectors (e.g. start point, end point, direction for a road, with an entire road being made up of many hundreds of such sections, each uniquely defined by start point/end point direction parameters). A map is then a set of such road vectors, data associated with each vector (speed limit; travel direction etc.) plus points of interest (POIs), plus road names, plus other geographic features like park boundaries, river boundaries etc, all of which are defined in terms of vectors. All map features (e.g. road vectors, POIs etc.) are typically defined in a co-ordinate system that corresponds with or relates to the GPS co-ordinate system, enabling a device's position as determined through a GPS system to be located onto the relevant road shown in a map and for an optimal route to be planned to a destination.

0003To construct this map database, Tele Atlas starts with basic road information from various sources, such as the Ordnance Survey for roads in England. It also has a large, dedicated team of vehicles driving on roads, plus personnel checking other maps and aerial photographs, to update and check its data. This data constitutes the core of the Tele Atlas map database. This map database is being continuously enhanced with geo-referenced data. It is then checked and published four times a year to device manufacturers like TomTom.

0004Despite the huge resources that go into updating and verifying these maps, the data for some geographic areas may be a year or more out of date.

0005In addition to the ongoing improvements described above, end-users can directly report map errors to Tele Atlas using Tele Atlas' web site. Device manufacturers like TomTom also capture and forward map error reports from their users in this way. These error reports are generally just in a free text format, so that considerable effort has to be expended in working out what the error really means and what exact location they relate to. Once verified as a real error, the appropriate correction is validated and then included in a future map release. The correction may eventually find itself in an end-user device a year or more after first being notified or, in some cases, not at all.

0006It is also known to store a 'trace' of a journey planned and completed using a GPS satellite navigation device (see for example the 'GPS track submission' functionality offered by ALK Technologies of Princeton, USA). This trace is a record of the complete route taken by a vehicle, using geo-coded data. The user can then send this trace data back to the device vendor; it is then used to improve the accuracy and completeness of the map database. For example, the precise position of a road or a turning may not be accurately captured on a map used by a device; the aggregated tracks for people taking that road or turning will enable a more accurate position to be determined; future map releases by the device vendor can incorporate the correction.

0007Reference may also be made to collaborative mapping projects, frequently called 'wikimaps'. Wikimaps do not however generate 'map data' as we define that term -i.e. map data that is suitable for route guidance algorithms to plot a route on a road system to a destination.

0008<patcit id="pcit0001" dnum="EP1530025A"><text>EP1530025</text></patcit> describes a vehicle navigation system that is capable of learning user habits/preferences, mistakes in a digital map database, and new roads that may have been added or constructed after release of the digital map database is disclosed. The vehicle navigation system monitors a driver's habits and updates a database to thereby cause the vehicle navigation system to have a preference for the driver's habits. The vehicle navigation system may also monitor the geographic position of the vehicle and allow the driver to update or change data contained in the digital map database if an error exists. The vehicle navigation system is also capable of learning new roads that exist that are not included in the road network map of the digital map database and is also capable of adding these new roads to the digital map database.

0009<patcit id="pcit0002" dnum="EP1087359A"><text>EP1087359</text></patcit> describes a method for arranging route information or road data in a road map. Road data comprises a digitally coded geographical reference place within a road map presented on a display device. A road data symbol is assigned to a position on the map corresponding to the reference geographical location. The content of the road data is virtually assigned to the symbol using words. Upon the activation of input keys this data content is outputted in form of words. Each symbol is selected automatically when a vehicle approaches a given spot. <patcit id="pcit0003" dnum="US2004204833A"><text>US 2004204833</text></patcit> describes a display method and apparatus for navigation system for specifying the destination easily and quickly. The navigation system is designed to enable a user to quickly select a street name and easily specify the address number of the destination through a map image of the selected street. The navigation system includes a menu for changing a keyboard screen or other input screen to a map screen showing the image of the selected street. A user can find a location of the destination on the image of the selected street. Various display methods are provided to promote quick and easy operations for finding the location on the selected street. When there are two or more streets having same street name with different street types or street prefixes, the navigation system displays selection means for a user to select one of the streets.

0010<patcit id="pcit0004" dnum="WO9915857A"><text>WO 9915857</text></patcit> describes a method for updating and/or complementing a digital road map in a traffic network, especially a digital road map for detecting and/or predicting traffic and/or for navigation of motor vehicles using a traffic control center and enabling simple, economical and efficient updating of said digital road map. A terminal placed inside at least one vehicle repeatedly detects at least one position of the vehicle and the position is inputted in a digital road map in the terminal. At least one check is made to determine whether a road or the like is available on the digital road map on the basis of the inputted position indicating the detected position of the vehicle. When no road or the like is available on the digital map, the terminal informs the traffic control center. The invention further relates to a terminal and to a traffic control center.

0011According to a first aspect of the present invention, there is provided a method of creating and storing map alterations on a navigation device as set out in claim 1.

0012According to a second aspect of the present invention, there is provided a navigation device according to claim 23.

0013Hence, it is no longer necessary for an end-user to be restricted to reporting errors to the map vendor over a web link, then waiting for that map vendor to verify the error, update its maps and supply the update - a cycle that can take months and sometimes years to complete. Instead, the navigation device can use the correction without external processing - e.g. verification by the map vendor. Use of the correction by the device can, in relative terms, be 'immediate'. The term 'immediate' should not be construed as instantaneously, but as simply meaning soon after the correction has been input. There can be intervening steps, such as the user verifying that the correction should be used, turning the device on and then off etc.

0014In an implementation, there is a navigation device that allows users to make modifications to the map data stored on their device. The navigation device can be a portable stand-alone GPS navigation device with route guidance capability, such as the GO series device from TomTom International BV, or any other kind of portable information device, such as a mobile telephone or PDA. But equally, it could be a device integrated into a vehicle, or a computing device such as a static desktop PC (including a laptop) running navigation software (which term includes mapping software which does not actually deliver dynamic route guidance but instead simply mapping - where the user is. Also, the navigation software could run locally on the client device or run on a server remote from the client device). The PC can then dock with a portable navigation device with a route guidance capability and transfer the corrections to the portable navigation device.

0015Typical features of such a navigation device are: <ul id="ul0001" list-style="bullet" compact="compact"><li>A user interface allowing users to create corrections to a digitally stored map;</li><li>A user interface that allows users to include or exclude map corrections from route calculations;</li><li>A user interface that allows user to view their corrected map data on the digital map</li><li>A set of correction categories that allow users to associate map corrections with one or more transportation types;</li><li>The ability to share map corrections with other users, for example via a content aggregation service. Shared maps are available for use (e.g. by a route planning algorithm or map display engine) as soon as they are downloaded.</li></ul>

0016The present invention will be described with reference to the accompanying drawings, in which: <ul id="ul0002" list-style="none" compact="compact"><li><figref idref="f0001"><b>Figure 1A</b></figref> is the main error reporting screen displayed by a navigation device;</li><li><figref idref="f0001"><b>Figure 1B</b></figref> is the screen shown that allows users to define the type of error they wish to capture and report;</li><li><figref idref="f0002"><b>Figure 1C</b></figref> is an illustration of a set of symbols that can be used in one implementation of the invention;</li><li><figref idref="f0003"><b>Figure 1D</b></figref> is a screenshot of an international traffic sign placed on the map display of the navigation device;</li><li><figref idref="f0003"><b>Figure 1E</b></figref> is a screenshot showing further international traffic signs placed on the map display of the navigation device;</li><li><figref idref="f0003"><b>Figure 1F</b></figref> is a screenshot showing another embodiment using international traffic signs on map display of the navigation device;</li><li><figref idref="f0004"><b>Figure 2</b></figref> is a diagram of the core software modules deployed in a navigation device implementing the invention;</li><li><figref idref="f0005"><b>Figure 3</b></figref> is a screen shot from a navigation device implementing the present invention; the screen shot shows a plan map view and a status bar running along the bottom of the display;</li><li><figref idref="f0006"><b>Figure 4</b></figref> is a screen shot from a navigation device implementing a 3-D view;</li><li><figref idref="f0007"><b>Figure 5</b></figref> is a screen shot from a navigation device showing a navigation menu;</li><li><figref idref="f0008"><b>Figure 6</b></figref> is a perspective view of a navigation device; and</li><li><figref idref="f0009"><b>Figure 7</b></figref> is a schematic view of the system architecture for a navigation device;</li><li><figref idref="f0010"><b>Figure 8</b></figref> is a block diagram of components in a navigation device; and</li><li><figref idref="f0011"><b>Figure 9</b></figref> is a diagram of the electrical subassemblies in the <figref idref="f0010"><b>Figure 8</b></figref> navigation device.</li></ul>

0017The present invention will be described with reference to an implementation of a map data correction tool that allows users to fix and also to share and report map errors using personal navigation devices. The user enters the correction (or map fix) into the navigation device. The map fix is then applied locally in the device to supplement the map data used by the device in routing and displaying roads, POIs etc. The map fix is immediately available. The map fix can be reported to a remote server by the device in a number of ways: the device may have an integral communications capability (e.g. wireless cellular system that can send data to the server), may be able to send data over a short range wireless link to a mobile telephone which in turn sends the data to the server, may be able to dock with an internet connected PC that can communicate with the server, or may itself be that internet connected PC. The server might aggregate all corrections from all users, validate corrections, and distribute the corrections to other users, and share the corrections with one or more map vendors.

0018When fully implemented, this feedback could replace map vendor updates as the primary mechanism for updating map data in navigation products.

0019The scope of one implementation of the map data correction tool is to provide user friendly, on-device tools allowing the user to: <ul id="ul0003" list-style="bullet" compact="compact"><li>Block and un-block streets on their map;</li><li>Modify the traffic direction of streets on their map;</li><li>Add and modify street names on their map;</li><li>Modify speed limits of roads on their map.</li></ul>

0020Hence, the corrections directly affect how the routing calculation algorithms operate - i.e. they are used when calculating a route to a destination. The map data correction tool also allows the user to: <ul id="ul0004" list-style="bullet" compact="compact"><li>Add safety camera locations to the map;</li><li>Share map corrections with other users;</li><li>Download map corrections from other users;</li><li>Create map error reports for large errors.</li></ul>

0021In addition to on-device corrections, the same correction features for all the above correction types can be made available using a desktop computer application that is capable of connecting to the device, e.g. in order to store corrections.

0022In addition to on-device features, improvements are possible to existing web based map error reporting tools: <ul id="ul0005" list-style="bullet" compact="compact"><li>Map error reporting can be made easier on the support website of the manufacturer of the navigation device;</li><li>Map error reporting tools might be added to an application running on the users PC;</li><li>Users might receive feedback on the map errors that they have reported;</li><li>Errors may be prioritised before sending them to the map supplier, e.g. TeleAtlas.</li><li>As explained earlier, important features of the map data correction tool are:</li><li>Map corrections and error reporting is possible on the navigation device or an application running on the user's PC;</li><li>Corrections take immediate effect (e.g. those meeting user-defined criteria);</li><li>Users may exchange corrections with other users.</li></ul>

0023On a navigation device, this can be implemented by the device displaying a menu item 'Make changes to the map' <b>101,</b> as shown in <figref idref="f0001"><b>Figure 1A</b></figref><b>.</b> The consequences of selecting this item are discussed below. There are 2 further menu items that will be described first.

0024First, the menu item 'Exchange Changes' <b>103</b> allows the user to initiate an upload of the user's own changes, and download other people's changes to the device. Upload can be via a mobile telephone with a GPRS wireless link that links to the navigation device over a Bluetooth network or via an Internet connected PC that the device is docked with.

0025Secondly, the menu item 'Preferences About changes' <b>102</b> determines which changes to enable. Selecting this item can cause the device to display a menu screen or similar, e.g. with check boxes to indicate applicable types of changes to enable and disable. For example, the user may select to enable/disable any of the following: <ul id="ul0006" list-style="bullet" compact="compact"><li>own changes;</li><li>recent changes;</li><li>last year's changes;</li><li>changes made on other maps;</li><li>only if reported more than once;</li><li>only from trusted sources.</li></ul>

0026The navigation device might display the total number of available changes and also the number of changes enabled (selected for download) by the user based on the current preferences.

0027The 'Make changes to map' <b>101</b> icon might take the user to a submenu which offers options to change the map instantly - plus the option to report an error (if it is not covered by self-action). These include, as shown in <figref idref="f0001"><b>Figure 1B</b></figref><b>:</b><ul id="ul0007" list-style="bullet" compact="compact"><li>Add/change street name <b>111:</b> if a user selects this, then the device may, for example, display a list of names of streets currently being displayed by the map (or that would be displayed if the device were in the normal navigation mode); the user might select the street to be re-named and then enter the new name via an on-screen keyboard.</li><li>Block Street <b>112:</b> if a user selects this, then the device may, for example, display a list of names of streets currently being displayed by the map (or that would be displayed if the device were in the normal navigation mode); the user might select the street to be blocked.</li><li>Change traffic direction (not shown): if a user selects this, then the device may, for example, display a list of names of streets currently being displayed by the map (or that would be displayed if the device were in the normal navigation mode) together with the traffic direction; the user might select the street whose traffic direction is to be altered.</li><li>Change speed limit <b>114:</b> if a user selects this, then the device may, for example, display a list of names of streets currently being displayed by the map (or that would be displayed if the device were in the normal navigation mode) together with applicable speed limits; the user might select the street whose speed limit is to be altered and then select the appropriate new speed limit from a menu.</li><li>Un-block street <b>115:</b> if a user selects this, then the device may, for example, display a list of names of blocked streets currently being displayed by the map (or that would be displayed if the device were in the normal navigation mode); the user might select the street to be unblocked.</li></ul>

0028In addition, it is possible, selecting the 'Edit/delete POI' <b>113</b> icon to open a sub-menu with graphical options for the following corrections: <ul id="ul0008" list-style="bullet"><li>Rename a POI;</li><li>Move a POI;</li><li>Add a POI to a category;</li><li>Delete a POI;</li><li>Re-categorize a POI.</li></ul>

0029In each case, the device may, for example, display a list of names of POIs currently being displayed by the map (or that would be displayed if the device were in the normal navigation mode); the user might select the relevant POI and then edit or delete that POI. These POIs are typically those supplied by the map vendor but can include POIs downloaded by the user (e.g. speed cameras).

0030A further menu item is to 'Report other error' <b>116,</b> which enables complaints, missing roads etc. to be reported. It allows the user to pick a location, select from a list of typical issues, allow user to add free text commentary etc.

0031<figref idref="f0002"><b>Figure 1C</b></figref> illustrates some examples of international traffic signs <b>121</b> that might be used in one embodiment of the invention. Traffic signs or road signs are signage posted at the side of the roads to impart information to road users. International signs using symbols instead of words have been developed and adopted in most countries to facilitate international road traffic and to increase road safety. Traffic signs might be danger warnings, priority signs, prohibitory or restrictive signs, mandatory signs, special regulation signs, information, facilities, service, direction, position, indication signs, or additional panels such as those defined in the Vienna Convention on Road Signs and Signals. In some countries, they are referred to as signpost information. The terms traffic signs, road signs or signpost information as used here are meant to include any graphical symbols relating to road traffic, rules, identification of road objects or their location, such as road markings, lane information, zebra stripes for pedestrian crossing, street names, house numbers, brand names, logos and the like.

0032As shown in <figref idref="f0003"><b>Figure 1D</b></figref><b>,</b> the user might provide information about locations, traffic rules, traffic directions and other map related data by placing international traffic signs <b>121</b> on the map on the navigation device. In this example, the user might place the "no entry" traffic sign <b>121</b> on the entrance (i.e. near one corner) of a street or road <b>123</b> to indicate the road can not be entered by cars from that end.

0033<figref idref="f0003"><b>Figure 1E</b></figref> is another example of the invention, according to which, the user might place other prohibitory signs <b>121</b> such as a "no right turn" or "no left turn" signs on a street near the corner, indicating turn restrictions.

0034The user might place a "max tonnage" traffic sign <b>121</b> on a road or bridge to indicate cars or trucks above that weight can not travel across it. Height or width restrictions might be indicated in a similar fashion.

0035The user might place a "max 60 kph" or "minimum 80 kph" traffic sign on a road to indicate a speed limit for that road or for a portion of a road.

0036The user might also provide parking information. The signs might not match real-world signs. Signs might indicate that parking is not possible in a street, because it is either forbidden or simply there are no parking spots. The sign might simply indicate that drivers can not park there, rather than that it is not allowed to park there.

0037Correction of map related data is also possible on a PC, e.g. using a web browser or a mapping application. The user may place international traffic signs <b>121</b> on the map in a similar manner as on a navigation device regardless whether the navigation device is connected to the pc or not.

0038The user might place a traffic sign <b>121</b> on the map on the place where that same sign is posted in the real world. Regardless whether these signs are there in the real world or not, or where are they located exactly, the navigation device may display information about streets or traffic restrictions using these international traffic signs <b>121</b> to explain the situation graphically.

0039Traffic signs <b>121</b> are particularly appropriate for this purpose because <ul id="ul0009" list-style="dash" compact="compact"><li>they are international;</li><li>they are well-known;</li><li>they are suited to specify information about roads;</li><li>placing a particular sign on a map in the same location the sign exists in the real world will have exactly the desired effect.</li></ul>

0040The signs placed on the map might be used for various modes of transport, including cars, bicycles, motorists, trucks, taxis. The user might specify a transport mode, for which the entered map correction is valid, e.g. every sign entered is related to bicycles only as illustrated using item <b>122</b> on <figref idref="f0002"><b>Figure 1C</b></figref><b>.</b> Alternatively, map corrections might be valid for all modes of transport, and restrictions (or exemptions) for a certain mode of transport might be indicated separately.

0041The user selects the 'Make changes to map' menu <b>101</b> as described above, then selects what kind of correction to make and using which traffic sign. Either at this phase or earlier, the user selects the location where the change should take effect. The traffic sign <b>121,</b> i.e. the "do not enter" sign <b>121</b> in this example, is placed on the map by clicking at the appropriate area, for example at the entrance of a road or street <b>123.</b> The user might also drag the traffic sign icon to the appropriate location or might correct the location by clicking and dragging the traffic sign icon <b>121</b> on the map. The user might change the direction of a one-way street by moving the "no entry" sign <b>121</b> from one end of the street to the other one. The moving of the traffic sign <b>121</b> might be performed by clicking and dragging the icon or a similar action, e.g. by re-centering the screen. To place and to drag traffic sign icons <b>121</b> on the map, the touchscreen of the navigation device might be used. In other implementations, appropriate hard or soft-buttons might be used as well, such as arrow buttons (up, down, left, right) on the navigation device or a numerical input for entering the co-ordinates. Various other input peripherals might be used, such as a mouse and a keyboard of a personal computer.

0042In another embodiment, traffic signs <b>121</b> might be used in general to display information about roads and streets. Traffic signs <b>121</b> on their own, or in combination with appropriate text labels, might be used to give visual feedback about traffic rules and restrictions as shown in <figref idref="f0003"><b>Figure 1F</b></figref><b>.</b> Similarly, other types of graphical objects (not shown) might be placed on the map by the user in order to convey information about map items and locations. The user of the navigation device might place icons representing traffic lights or pedestrian crossings on the map to show or update real-life location of these objects.

0043It is possible that users place identification of businesses such as logos, brand names on the map to identify those businesses on the map as opposed to indicating traffic rules.

Other features

0044<ul id="ul0010" list-style="bullet" compact="compact"><li>Users might create "private" fixes for their map and "shared" fixes that are also sent to a remote server for aggregation;</li><li>Each map fix is stored independently;</li><li>Map fixes are highly compressible for OTA distribution;</li><li>Map fixes are secure (such that it is not possible to manually reverse engineer the format) to ensure that unauthorized users and devices cannot use map data corrections;</li><li>Map fixes are stored in a map-independent form so that they can be preserved during map upgrades and they can be applied to maps from different vendors;</li><li>Map fixes are automatically removed if the area related to the fix has changed in a new release of the map data (if the map error has been fixed by the map supplier); <ul id="ul0011" list-style="bullet" compact="compact"><li>Map fixes do not permanently modify the user's map data;</li><li>Users might choose which kinds of changes they use (e.g. use only own changes or use own changes and those from other sources);</li><li>User might choose from which other sources they accept map changes;</li><li>Map fixes might be associated with a map version and map supplier;</li><li>It is possible to maintain map fix databases for each released map version;</li><li>Users with new maps might receive fixes reported on older and current map versions</li><li>Users of old maps might not be able to receive fixes reported on newer maps;</li><li>An aggregation system might be used to collect and share map corrections and reports with other users;</li><li>The aggregation system might serve as a tool to add reliability so that the validity or credibility of map fixes and reports can be assessed;</li><li>Users who report good errors on a regular basis may become "trusted", and their fixes might be offered to all users without validation;</li><li>These "trusted" users may also validate fixes submitted by other users;</li><li>The manufacturer of a navigation device might endorse validated fixes sent by users.</li></ul></li></ul>

0045<figref idref="f0004"><b>Figure</b> 2</figref> shows schematically the core software modules deployed in a navigation device implementing the invention. The display <b>201</b> is a touch screen display that the user enters a destination address into in the conventional manner. That address data input is handled by the UI module <b>202</b> and sent to the navigation/ route planning module <b>203.</b> Route planning module <b>203,</b> taking a GPS feed from GPS module <b>204,</b> plans a route using map data from the encrypted, compressed map data that the device was shipped with (or was otherwise supplied from the map vendor, such as Tele Atlas). The present invention is then implemented as follows: the user enters a map correction as and when needed, using a touch screen interaction, touching large graphical icons, as exemplified by <figref idref="f0001"><b>Figures 1A</b></figref> and IB, into display 201. The UI module 202 captures the map fix and sends it to a map fix store 206. As soon as the map fix is in the map fix 206 store, it is made available to the route planning module 202 and the UI module 202. If the map fix requires re-planning of even the current route being driven, then that will happen automatically (if the user configures that option). For example, the device might plan a route that requires the user to turn into a street: when the turning is approached, the user finds that it has recently been made a 'no entry' street. The user can enter an appropriate map correction: a new route, taking into account the no entry street, is then immediately planned and appropriate route guidance given. Likewise, if the user plans a completely new route to another destination, the new route will also take the map fix into account. If the map fix should affect how the map should appear (for example, re-naming a road, showing a new POI, such as a speed camera), then that new appearance will be immediately present. Automatic use of the correction is not mandatory though; some users may prefer for route calculation etc. to exclude map corrections.

0046The following is a description of a typical device that can implement the present invention.

0047The present invention can be implemented in an integrated navigation device from TomTom International B.V. called GO. GO deploys navigation software called Navigator (or Navcore) and has an internal GPS receiver; Navigator software can also run on a touch screen (i.e. stylus controlled) Pocket PC powered PDA device, such as the Compaq iPaq. It then provides a GPS based navigation system when the PDA is coupled with a GPS receiver. The combined PDA and GPS receiver system is designed to be used as an in-vehicle navigation system.

0048The invention may also be implemented in any other arrangement of navigation device, such as one with an integral GPS receiver/computer/display, or a device designed for non-vehicle use (e.g. for walkers) or vehicles other than cars (e.g. aircraft). The navigation device may implement any kind of position sensing technology and is not limited to GPS; it can hence be implemented using other kinds of GNSS (global navigation satellite system) such as the European Galileo system. Equally, it is not limited to satellite based location/velocity systems but can be deployed using ground-based beacons or any other kind of system that enables the device to determine its geographic location.

0049When in use, a navigation device (or a navigation software running on a PDA) displays the normal navigation mode screen shown in <figref idref="f0005"><b>Figure 3</b></figref><b>.</b> This view provides driving instructions using a combination of text, symbols, voice guidance and a moving map. Key user interface elements are the following: a two dimensional map <b>301</b> occupies most of the screen. The map shows the user's car and its immediate surroundings, rotated in such a way that the direction in which the car is moving is always "up". Running across the bottom quarter of the screen is the status bar <b>302.</b> The current location of the device, as the device itself determines using conventional GPS location finding and its orientation (as inferred from its direction of travel) is depicted by an arrow <b>303.</b> The route calculated by the device (using route calculation algorithms stored in device memory as applied to map data stored in a map database in device memory) is shown as darkened path <b>304</b> superimposed with arrows giving the travel direction. On the darkened path <b>304,</b> all major actions (e.g. turning corners, crossroads, roundabouts etc.) are schematically depicted by arrows <b>305</b> overlaying the path <b>304.</b> The status bar <b>302</b> also includes at its left hand side a schematic <b>306</b> depicting the next action (here, a right turn). The status bar <b>302</b> also shows the distance to the next action (i.e. the right turn - here the distance is 220 meters) as extracted from a database of the entire route calculated by the device (i.e. a list of all roads and related actions defining the route to be taken). Status bar <b>302</b> also shows the name of the current road <b>308,</b> the estimated time before arrival <b>309</b> (here 2 minutes and 40 seconds), the actual estimated arrival time <b>310</b> (11.36am) and the distance to the destination <b>311</b> (1.4Km). The GPS signal strength is shown in a mobile-phone style signal strength indicator <b>312.</b>

0050<figref idref="f0006"><b>Figure 4</b></figref> is a three dimensional view of the navigation mode screen illustrating the same objects as discussed above with regards to <figref idref="f0005"><b>Figure 3</b></figref> using the same reference numbers..

0051If the user touches the screen <b>313,</b> then a navigation screen main menu (not shown) is displayed; from this menu, other core navigation functions within the Navigator application can be initiated or controlled. Allowing core navigation functions to be selected from a menu screen that is itself very readily called up (e.g. one step away from the map display to the menu screen) greatly simplifies the user interaction and makes it faster and easier.

0052The area of the touch zone which needs to be touched by a user is far larger than in most stylus based touch screen systems. It is designed to be large enough to be reliably selected by a single finger without special accuracy; i.e. to mimic the real-life conditions for a driver when controlling a vehicle; he or she will have little time to look at a highly detailed screen with small control icons, and still less time to accurately press one of those small control icons. Hence, using a very large touch screen area associated with a given soft key (or hidden soft key, as in the centre of the screen <b>313</b>) is a deliberate design feature of this implementation. Unlike other stylus based applications, this design feature is consistently deployed throughout Navigator to select core functions that are likely to be needed by a driver whilst actually driving. Hence, whenever the user is given the choice of selecting on-screen icons (e.g. control icons, or keys of a virtual keyboard to enter a destination address, for example), then the design of those icons/keys is kept simple and the associated touch screen zones is expanded to such a size that each icon/key can unambiguously be finger selected. In practice, the associated touch screen zone will be of the order of at least 0.7 cm² and will typically be a square zone. In normal navigation mode, the device displays a map. Touching the map (i.e. the touch sensitive display) once (or twice in a different implementation) near to the screen centre (or any part of the screen in another implementation) will then call up either directly (i.e. the next level down) or indirectly (i.e. two or more levels down) a navigation menu (see <figref idref="f0007"><b>Figure 5</b></figref>) with large icons corresponding to various navigation functions <b>501-506,</b> such as the option to calculate an alternative route <b>502,</b> and re-calculate the route so as to avoid the next section of road <b>503</b> (useful when faced with an obstruction or heavy congestion); or recalculate the route so as to avoid specific, listed roads <b>504-506.</b>

0053The actual physical structure of the device is fundamentally different from a conventional embedded device in terms of the memory architecture (see system Architecture section below). At a high level it is similar though: memory stores the route calculation algorithms, map database and user interface software; a microprocessor interprets and processes user input (e.g. using a device touch screen to input the start and destination addresses and all other control inputs) and deploys the route calculation algorithms to calculate the optimal route. 'Optimal' may refer to criteria such as shortest time or shortest distance, or some other user-related factors.

0054More specifically, the user inputs his start position and required destination in the normal manner into the Navigator software running on the PDA using a virtual keyboard. The user then selects the manner in which a travel route is calculated: various modes are offered, such as a 'fast' mode that calculates the route very rapidly, but the route might not be the shortest; a 'full' mode that looks at all possible routes and locates the shortest, but takes longer to calculate etc. Other options are possible, with a user defining a route that is scenic - e.g. passes the most POI (points of interest) marked as views of outstanding beauty, or passes the most POIs of possible interest to children or uses the fewest junctions etc.

0055Roads themselves are described in the map database that is part of Navigator (or is otherwise accessed by it) running on the PDA as lines - i.e. vectors (e.g. start point, end point, direction for a road, with an entire road being made up of many hundreds of such sections, each uniquely defined by start point/end point direction parameters). A map is then a set of such road vectors, plus points of interest (POIs), plus road names, plus other geographic features like park boundaries, river boundaries etc, all of which are defined in terms of vectors. All map features (e.g. road vectors, POIs etc.) are defined in a co-ordinate system that corresponds or relates to the GPS co-ordinate system, enabling a device's position as determined through a GPS system to be located onto the relevant road shown in a map.

0056Route calculation uses complex algorithms that are part of the Navigator software. The algorithms are applied to score large numbers of potential different routes. The Navigator software then evaluates them against the user defined criteria (or device defaults), such as a full mode scan, with scenic route, past museums, and no speed camera. The route which best meets the defined criteria is then calculated by a processor in the PDA and then stored in a database in RAM as a sequence of vectors, road names and actions to be done at vector endpoints (e.g. corresponding to pre-determined distances along each road of the route, such as after 100 meters, turn left into street x).

0057<figref idref="f0008"><b>Figure 6</b></figref> is a perspective view of an example of a navigation device <b>601.</b> The navigation device <b>601</b> is a unit that includes display, internal GPS receiver, microprocessor, power supply and memory systems (not shown). The device may sit on an arm <b>602,</b> which itself is secured to the car dashboard using a suction cup <b>603.</b> The navigation device <b>601</b> may also be docked onto the dashboard of the vehicle.

0058In contrast to conventional embedded devices which execute all the operating system and application code in place from a large mask read only memory ROM or Flash memory device, an implementation of the present invention might use a memory architecture as illustrated in <figref idref="f0009"><b>Figure 7</b></figref><b>.</b> The device, indicated generally at <b>701,</b> includes conventional items such as a microprocessor <b>706,</b> power source <b>707,</b> display and related rivers <b>708.</b> In addition, it includes a secure digital SD card reader <b>703;</b> a SD card <b>702</b> is shown slotted into position. The device <b>701</b> might have internal dynamic random access memory DRAM <b>704</b> and XIP (eXecute In Place) Flash <b>705</b> as well.

0059The device hence may use three different forms of memory: <ol id="ol0001" compact="compact"><li>1. A small amount of internal XIP Flash ROM <b>705.</b> This is analogous to the PC's BIOS ROM and will only contain a proprietary boot loader, E² emulation (for UID and manufacturing data) and splash screen bit maps. This is estimated to be 256 KB in size and would be on a slow 8 bit wide SRAM interface.</li><li>2. The main system RAM (or DRAM) memory <b>704,</b> this is analogous to the PC's main memory (RAM). This will be where all the main code executes from as well as providing the video RAM and workspace for the OS and applications. <b>Note:</b> No persistent user data will be stored in the main system RAM (like a PC) i.e. there will be no "Ram drive". This RAM will be exclusively connected to a 32bit 100MHz synchronous high-speed bus.</li><li>3. Non-volatile storage, analogous to the PC's hard disk might be implemented as removable flash based SD cards <b>702.</b> All the operating system, applications, settings files and map data might be permanently stored on SD cards.</li></ol>

0060<figref idref="f0010"><b>Figure 8</b></figref> is a block diagram illustrating some typical components of a navigation device implementing the invention.

0061A navigation device may be built on standard commodity components.

0062The navigation device might use a transflective 3.5" thin film transistor TFT backlit display <b>803</b> that might be a 'standard' ¼ video graphics array VGA display. It might also contain an integrated touch panel and backlight. The display <b>803</b> mounted in landscape, or in some cases, in portrait orientation.

0063The navigation device might comprise a highly integrated processor CPU <b>815,</b> an SD card memory slot <b>827</b> for application and map data storage, integrated GPS receiver <b>817</b> and antenna <b>805,</b> integrated two axis accelerometer <b>821</b> for simple dead reckoning, power supply (not shown), and external GPS antenna connection <b>806.</b> The navigation device may use a customized version of an embedded Linux OS without GUI layer as the navigation application provides its own UI. The navigation device may comprise a very simple touch screen UI optimised for finger use and a high quality integrated speaker <b>801</b> for voice instructions.

0064The navigation device may have an internal rechargeable battery (not shown) and it may operate independently from any connection to a vehicle. The battery might be charged, and the device powered (even if the battery contains no charge) from an external power source (not shown). This external power source might be supplied via the docking connector 825 or a DC jack socket (not shown). The device might be turned on and off using a single button or when the vehicle ignition is switched on and off.

0065The navigation device may have one or more hard buttons, at least a power button (not shown). It is pressed once to turn the device on or off. The UI might be designed so that all other operations are easily accessible through the touch screen.

0066The navigation device may comprise an universal serial bus USB connector <b>823</b> and a Bluetooth transceiver <b>829</b> for connecting with a PC or other devices such as a mobile phone.

0067The navigation device might have an internal speaker <b>801</b> to give spoken instructions. The speaker might be driven by an internal amplifier (not shown) and an audio codec <b>807.</b> Audio line out might also be present on the device or the docking connector <b>825.</b>

0068The docking connector <b>825</b> provides an interface to external docking stations.

0069Using the map data correction tool, map errors might be reported or be corrected immediately on the navigation device. Furthermore, the user might make map corrections on a PC connected to the navigation device using a web browser or an application such as the TomTom Home application.

0070The following is a description of some examples of map corrections that can be made using a navigation device or a suitable PC application. <ul id="ul0012" list-style="bullet" compact="compact"><li>The user may add the locations of safety cameras on the map;</li><li>The user may block roads on the map;</li><li>The user may un-block roads on the map;</li><li>The user may modify the traffic direction properties of roads on the map;</li><li>The user may change a two-way road into a one-way road (in either direction);</li><li>The user may change a one-way road to a two-way road;</li><li>The user may change the direction of a one-way road to the other direction.</li><li>The user may add a road (consisting of one or more nodes) on the map.</li><li>The user may connect 2 points on the map and define this new link as a new road.</li><li>The user may add street names to un-named roads on the map.</li><li>The user may modify the names of roads on the map.</li><li>The user may modify the maximum speed of roads on the map.</li></ul>

0071Once map corrections are present on the navigation device, they might be made available to the user by default or based on various criteria. For example, the user may use private corrections as soon as the corrections are recorded or the user may use public corrections as soon as the corrections have been downloaded to the device.

0072As some map corrections may have been made by other navigation device owners, the user is able to select which corrections to use when calculating routes.

0073The user might be able to choose whether to receive warnings for private and/or public reported safety cameras and the user might be able to use or ignore private map corrections whenever they plan a route that includes a correction.

0074The user might be able to use or ignore public map corrections whenever they plan a route that includes a correction.

0075The user might be able to configure the device such that private and/or public corrections from one or more categories are automatically included within route calculations. The user might be informed that map corrections are being used.

0076The user might be able to recalculate routes to include or exclude map corrections.

0077The user might be able to remove a map correction from the device.

0078Some map errors are too complicated or large in scale to make corrections on the device itself. These errors need to be reported to the manufacturer of the navigation device, so that the manufacturer (or our map suppliers) can take corrective action. Alternatively, error reports might be sent directly to the map supplier.

0079The user of the navigation device might have several options when making and using map data corrections and reports.

0080The user might be able to create map error reports and corrections on the device and upload these to a remote server.

0081For safety reasons, the user might not be able to create map error reports and corrections while driving.

0082It is possible to offer users a list of pre-defined error types when creating error reports on the device.

0083The user might be able to create map error reports and corrections within a PC application such as the TomTom Home and upload these to a remote server.

0084The user might not have to register or to be a customer in order to create map error reports and corrections.

0085The user might be able to import map error reports and corrections captured on the device to the PC application such as the TomTom Home application. The user might be able to edit these reports and then upload them to a remote server. The user might receive a feedback regarding reported map errors.

0086In some circumstances it is possible for the navigation device to suggest corrections to the user, based on use of the navigation device.

0087For example, the users might be prompted to block roads that they chose to avoid within route plans on multiple occasions.

0088The user might be prompted to add a road on the map if driving through a map area that is not marked as a road on multiple occasions.

0089The user might be prompted to add a name to unnamed roads on the map if planning routes to such a road on multiple occasions.

0090The user might be prompted to modify the speed limit of a road if driving along it at a significantly different speed from that stated in the map data on multiple occasions.

0091Users of the map data correction tool may wish to share their corrections with other navigation device users. For example, users might be able to create corrections for their personal use only. These corrections will not be sent to the remote server but might be transferred to a PC application such as the TomTom Home application.

0092The users might be able to create corrections that are shared with other navigation devices. These corrections might be uploaded to the remote server and made available to other navigation devices. The map data corrections might be shared directly between navigation devices, i.e. without using a remote server or a PC.

0093Users might be able to categorise their public map corrections according to the user community for which it is applicable. The following community categories are possible examples: <ul id="ul0013" list-style="bullet" compact="compact"><li>All users;</li><li>All motorists;</li><li>Heavy goods vehicle drivers;</li><li>Motorcyclists;</li><li>Limited speed vehicle drivers;</li><li>Pedestrians;</li><li>Bicycles.</li></ul>

0094Users may acquire "trusted user" status, based upon the number and quality of map corrections that they upload.

0095Users might be informed if they attempt to report a map correction that has been corrected in a newer version of the map data that they are using. Users might also be informed how they can purchase the updated map.

0096In order to use public map corrections the user might retrieve them e.g. from a remote server. The user might download public map corrections to the navigation device and/or to a PC application, such as the TomTom Home application. Public map corrections might be available for one or more community categories.

0097The user might be able to download public map corrections from one or more community source categories.

0098The user might be able to download public map corrections from one or more map supplier source categories. A supplier category might be provided for each map supplier.

0099The user might be able to download public map corrections from one or more location categories, which might comprise the following: <ul id="ul0014" list-style="bullet" compact="compact"><li>All maps;</li><li>All maps on device;</li><li>Currently loaded map on device.</li></ul>

0100In order to allow users to make informed decisions relating to public map corrections, the map data correction tool manages the corrections and provides a categorisation.

0101Public map corrections might be aggregated by the party hosting the server, i.e. the manufacturer of the navigation device or the map supplier. It is also feasible that map data corrections are collected, stored and aggregated by third parties.

0102Public map corrections might be analysed in order to assess their source, applicability and trustworthiness. Public map corrections might be distributed to users upon request. Public map corrections might be distributed automatically as well.

0103The applicability of each map correction might be assessed with respect to each map supplied to users. If a map correction is found not to be applicable for a given map then it is removed from the aggregated map corrections and not distributed to users of this map. Alternatively, if a map correction is found not applicable, it might be marked and/ or sent to further verification.

0104Map corrections held on the remote server might be categorised by source so that the user can be informed of the relative trustworthiness of the correction's source.

0105Specific map corrections might be endorsed and represented to the user in a specific category.

0106Map corrections that have been reported by a single user might be represented to other users in a specific category.

0107Map corrections that have been reported by more than one user might be represented to other users in specific categories. Specifically, the following categories might be represented: <ul id="ul0015" list-style="bullet" compact="compact"><li>Reported by 2 - 5 users;</li><li>Reported by more than 5 users.</li></ul>

0108Map corrections that have been reported by trusted users shall be represented to other users in a specific category.

0109Users of the map data correction tool might be able to endorse map corrections made by other users and evidence of these endorsements might be represented to the user.

0110In order to gain (and maintain) a competitive advantage from New York, it is imperative that map correction data is held in a structured, re-usable and secure way. This section describes the constraints relating to security.

0111Each map correction might be uniquely identified.

0112Map corrections might be time stamped with the time at which they were input and/ or reported.

0113Each map correction might be stored in a form that allows it to be applied to the map independently of all other map corrections (i.e. the navigation device or navigation software on a PDA shall be able to decide on a per-correction basis whether the correction should be applied to the map and represented to the user).

0114Map corrections do not make a permanent modification to the user's map data.

0115Map corrections might be compressed to allow fast and cheap distribution over wireless networks.

0116Map corrections might be highly encrypted such that it is not possible for the data format to be reverse engineered.

0117Map corrections might be stored in such a way that they are retained through a map upgrade process.

0118Map corrections might be compatible with future map versions, such that corrections made on older versions of a map can be applied to the latest version.

0119Map corrections might not be compatible with previous map versions. It might not be possible to apply a map correction made on the current map version with a previous map version.

0120Map corrections might be independent of map supplier, such that map corrections can be applied to maps from different suppliers.

0121Map corrections might be compatible with the map supplier's, e.g. Tele Atlas, map reporting API such that it is possible to send correctly formatted reports to the map supplier.

0122In order to ensure that map corrections are correctly handled on the user's device, certain rules might be applied. This section describes some examples of the constraints relating to on-device map correction handling.

0123Map corrections created on previous map versions might be checked to see if they are applicable to the currently loaded map on the user's device. Map corrections that are not applicable might not be used within route calculations.

0124In order to manage map error reports in a more effective manner, the recipient of the error reports, e.g. the manufacturer of the navigation device or the map supplier, might implement a method for aggregating and prioritising error reports.

0125Map error reports might be aggregated from various sources, including user devices, pc applications, and websites.

0126Map error reports might be assessed and assigned to priorities, such that the most serious errors might be highlighted. These priorities might be communicated to map suppliers when submitting error reports to them.

0127The user shall be able to modify the names of cities (and other places) on the map.

0128The user might block access to a road for one or more transportation types. Specifically the user might block access for the following transportation types: <ul id="ul0016" list-style="bullet"><li>All motor vehicles;</li><li>Pedestrians;</li><li>Heavy Goods Vehicles;</li><li>Bicycles.</li></ul>

0129The user might un-block access to a road for one or more transportation types. Specifically the user might un-block access for the following transportation types: <ul id="ul0017" list-style="bullet"><li>All motor vehicles;</li><li>Pedestrians;</li><li>Heavy Goods Vehicles;</li><li>Bicycles.</li></ul>

0130Besides the above described examples, the user of the navigation device (or a suitable computer application) might take various corrective actions, which might include, but are not limited to, any of the following: <ul id="ul0018" list-style="bullet" compact="compact"><li>The user might modify the "class" of roads on the map;</li><li>The user might add turn restrictions to roads on the map;</li><li>The user might remove turn restrictions applied to roads on the map;</li><li>The user might add house numbers (either a single number or a range) to roads on the map;</li><li>The user might modify the location of house numbers (either a single number or a range) applied to roads on the map;</li><li>The user might modify the average speed of roads on the map;</li><li>The user might mark a road on the map as a toll road;</li><li>The user might remove the presence of a toll from roads on the map;</li><li>The user might add signpost information to roads on the map;</li><li>The user might modify the properties of signpost information associated with roads on the map;</li><li>The user might remove signpost information associated with roads on the map;</li><li>The user might modify the location of POI on the map;</li><li>The user might modify the names of POI on the map;</li><li>The user might modify the category of POI on the map;</li><li>The user might remove POI from the map;</li><li>The user might modify the exit numbers of motorways on the map;</li><li>The user might modify the post code associated with a road on the map;</li><li>The user might add road height restrictions to roads on the map;</li><li>The user might add road width restrictions to roads on the map;</li><li>The user might add road weight restrictions to roads on the map;</li></ul>

0131Some map errors might be too complicated or large in scale to make corrections on the device itself. These errors might be reported to map suppliers to take corrective action.

0132The invention has been described with reference to certain preferred embodiments. It will be understood, however, that modifications and variations are possible within the scope of the appended claims.