Map rendering for navigation systems

<u>Field of the Invention</u>

0001This invention relates to navigation devices and to methods and apparatus for rendering map information, such as navigation maps, for display. Illustrative embodiments of the invention relate to portable navigation devices (so-called PNDs), in particular PNDs that include Global Positioning System (GPS) signal reception and processing functionality. Other embodiments relate, more generally, to any type of processing device that is configured to display map information and/or to execute navigation software so as to provide route planning, and preferably also navigation, functionality.

<u>Background to the Invention</u>

0002Portable navigation devices (PNDs) that include GPS (Global Positioning System) signal reception and processing functionality are well known and are widely employed as in-car or other vehicle navigation systems.

0003In general terms, a modern PNDs comprises a processor, memory (at least one of volatile and non-volatile, and commonly both), and map data stored within said memory. The processor and memory cooperate to provide an execution environment in which a software operating system may be established, and additionally it is commonplace for one or more additional software programs to be provided to enable the functionality of the PND to be controlled, and to provide various other functions.

0004Typically these devices further comprise one or more input interfaces that allow a user to interact with and control the device, and one or more output interfaces by means of which information may be relayed to the user. Illustrative examples of output interfaces include a visual display and a speaker for audible output. Illustrative examples of input interfaces include one or more physical buttons to control on/off operation or other features of the device (which buttons need not necessarily be on the device itself but could be on a steering wheel if the device is built into a vehicle), and a microphone for detecting user speech. In a particularly preferred arrangement the output interface display may be configured as a touch sensitive display (by means of a touch sensitive overlay or otherwise) to additionally provide an input interface by means of which a user can operate the device by touch.

0005Devices of this type will also often include one or more physical connector interfaces by means of which power and optionally data signals can be transmitted to and received from the device, and optionally one or more wireless transmitters/receivers to allow communication over cellular telecommunications and other signal and data networks, for example Wi-Fi, Wi-Max GSM and the like.

0006PND devices of this type also include a GPS antenna by means of which satellite-broadcast signals, including location data, can be received and subsequently processed to determine a current location of the device.

0007The PND device may also include electronic gyroscopes and accelerometers which produce signals that can be processed to determine the current angular and linear acceleration, and in turn, and in conjunction with location information derived from the GPS signal, velocity and relative displacement of the device and thus the vehicle in which it is mounted. Typically such features are most commonly provided in in-vehicle navigation systems, but may also be provided in PND devices if it is expedient to do so.

0008The utility of such PNDs is manifested primarily in their ability to determine a route between a first location (typically a start or current location) and a second location (typically a destination). These locations can be input by a user of the device, by any of a wide variety of different methods, for example by postcode, street name and house number, previously stored "well known" destinations (such as famous locations, municipal locations (such as sports grounds or swimming baths) or other points of interest), and favourite or recently visited destinations.

0009Typically, the PND is enabled by software for computing a "best" or "optimum" route between the start and destination address locations from the map data. A "best" or "optimum" route is determined on the basis of predetermined criteria and need not necessarily be the fastest or shortest route. The selection of the route along which to guide the driver can be very sophisticated, and the selected route may take into account existing, predicted and dynamically and/or wirelessly received traffic and road information, historical information about road speeds, and the driver's own preferences for the factors determining road choice (for example the driver may specify that the route should not include motorways or toll roads).

0010In addition, the device may continually monitor road and traffic conditions, and offer to or choose to change the route over which the remainder of the journey is to be made due to changed conditions. Real time traffic monitoring systems, based on various technologies (e.g. mobile phone data exchanges, fixed cameras, GPS fleet tracking) are being used to identify traffic delays and to feed the information into notification systems.

0011PNDs of this type may typically be mounted on the dashboard or windscreen of a vehicle, but may also be formed as part of an on-board computer of the vehicle radio or indeed as part of the control system of the vehicle itself. The navigation device may also be part of a hand-held system, such as a PDA (Portable Digital Assistant) a media player, a mobile phone or the like, and in these cases, the normal functionality of the hand-held system is extended by means of the installation of software on the device to perform both route calculation and navigation along a calculated route.

0012Route planning and navigation functionality may also be provided by a desktop or mobile computing resource running appropriate software. For example, the Royal Automobile Club (RAC) provides an on-line route planning and navigation facility at http://www.rac.co.uk, which facility allows a user to enter a start point and a destination whereupon the server to which the user's PC is connected calculates a route (aspects of which may be user specified), generates a map, and generates a set of exhaustive navigation instructions for guiding the user from the selected start point to the selected destination. The facility also provides for pseudo three-dimensional rendering of a calculated route, and route preview functionality which simulates a user travelling along the route and thereby provides the user with a preview of the calculated route.

0013In the context of a PND, once a route has been calculated, the user interacts with the navigation device to select the desired calculated route, optionally from a list of proposed routes. Optionally, the user may intervene in, or guide the route selection process, for example by specifying that certain routes, roads, locations or criteria are to be avoided or are mandatory for a particular journey. The route calculation aspect of the PND forms one primary function, and navigation along such a route is another primary function.

0014During navigation along a calculated route, it is usual for such PNDs to provide visual and/or audible instructions to guide the user along a chosen route to the end of that route, i.e. the desired destination. It is also usual for PNDs to display map information on-screen during the navigation, such information regularly being updated on-screen so that the map information displayed is representative of the current location of the device, and thus of the user or user's vehicle if the device is being used for in-vehicle navigation.

0015An icon displayed on-screen typically denotes the current device location, and is centred with the map information of current and surrounding roads in the vicinity of the current device location and other map features also being displayed. Additionally, navigation information may be displayed, optionally in a status bar above, below or to one side of the displayed map information, examples of navigation information include a distance to the next deviation from the current road required to be taken by the user, the nature of that deviation possibly being represented by a further icon suggestive of the particular type of deviation, for example a left or right turn. The navigation function also determines the content, duration and timing of audible instructions by means of which the user can be guided along the route. As can be appreciated a simple instruction such as "turn left in 100 m" requires significant processing and analysis. As previously mentioned, user interaction with the device may be by a touch screen, or additionally or alternately by steering column mounted remote control, by voice activation or by any other suitable method.

0016A further important function provided by the device is automatic route recalculation in the event that: a user deviates from the previously calculated route during navigation (either by accident or intentionally); real-time traffic conditions dictate that an alternative route would be more expedient and the device is suitably enabled to recognize such conditions automatically, or if a user actively causes the device to perform route re-calculation for any reason.

0017It is also known to allow a route to be calculated with user defined criteria; for example, the user may prefer a scenic route to be calculated by the device, or may wish to avoid any roads on which traffic congestion is likely, expected or currently prevailing. The device software would then calculate various routes and weigh more favourably those that include along their route the highest number of points of interest (known as POIs) tagged as being for example of scenic beauty, or, using stored information indicative of prevailing traffic conditions on particular roads, order the calculated routes in terms of a level of likely congestion or delay on account thereof. Other POI-based and traffic information-based route calculation and navigation criteria are also possible.

0018Although the route calculation and navigation functions are fundamental to the overall utility of PNDs, it is possible to use the device purely for information display, or "free-driving", in which only map information relevant to the current device location is displayed, and in which no route has been calculated and no navigation is currently being performed by the device. Such a mode of operation is often applicable when the user already knows the route along which it is desired to travel and does not require navigation assistance.

0019Devices of the type described above, for example the GO 950 LIVE model manufactured and supplied by TomTom International B.V., provide a reliable means for enabling users to navigate from one position to another.

0020As will be appreciated from the above, an important aspect of the operation of such navigation devices is the display of map information to the user by the device. This may be done, for example, by rendering the whole scene based on the vector data for each frame.

0021Another known technique is to represent the map information (in the 3D world) on a tile-by-tile basis, i.e. to represent the 3D "world" view of the map (which will then be transformed to 2D screen space for display, as is known in the art) as one or more tiles, each representing some or all of the map in the 3D world view of the map to be displayed.

0022In such arrangements, the tiles may, as is known in the art, be stored and displayed at varying levels of detail, to provide further visual improvement. The different level of detail tiles may also be overlaid and filtered to provide a more seamless transition between levels of detail.

0023Such tile-based map and road network rendering is an efficient and powerful way for displaying road network and geographic data in both two and three dimensions. Tile-based rendering is especially efficient given that most mobile graphics rendering subsystems (which is typically what will be used in a PND (and may be implemented in hardware or software or both, as is known in the art)) are limited in the amount of geometry they can process in order to get an acceptable frame rate and that a lot of the more powerful features found in desktop graphics accelerators have not made it to the mobile space yet.

0024When a stored map is rendered for display on a PND, for example, it will typically be processed in discrete parts, with data representing given parts of the whole map to be displayed typically being loaded into a local (e.g. cache) memory of the graphics processor for processing in succession. The different discrete parts of the map data may, e.g., comprise bitmaps representing tiles that will be used to form the map, and/or a 2D/3D vector representation of the relevant part of the map to be displayed. The need to load and process such map information for rendering is a significant requirement of PND operation.

0025<patcit id="pcit0001" dnum="US6092076A"><text>US 6092076 A</text></patcit> discloses a map display tool for use with a navigation system and used with a map database, wherein the map display tool is adapted to render a map on a display or in a graphics buffer for a predetermined geographic region.

0026<patcit id="pcit0002" dnum="WO2008089231A1"><text>WO 2008/089231 A1</text></patcit> discloses a system of processing map images that includes a web mapping service (WMS) for storing map images.

0027<patcit id="pcit0003" dnum="EP1526359A1"><text>EP 1526359 A1</text></patcit> discloses a method for managing map data for a vehicle using a navigation system, wherein upon display of the map data, memory loading for the display of the map data can be quickly performed by reducing the number of access to a physical storage medium with an entire map stored therein.

<u>Summary of the Invention</u>

0028According to a first aspect of the present invention, there is provided a method of rendering a map for display on a mapping or navigation apparatus as claimed in claim 1.

0029According to a second aspect of the present invention, there is provided a mapping or navigation apparatus as claimed in claim 7.

0030In the present invention, when the map rendering processor (which may be, and preferably is, a graphics processor) is due to process a new part of a map for display, it is first checked to see whether any existing data in the local memory (e.g. cache) available to the rendering processor is similar to the new map part to be processed. If the data that is already in the local memory is determined to be sufficiently similar to the new data to be loaded, the rendering processor processes the existing data in its local memory to display the map part in question.

0031This operation has the advantage of, e.g., being able to avoiding loading and processing new map data from the main map information store, where it is determined, by means of the similarity test, that existing map data in the rendering processor's local memory can be used instead. This can thereby save, e.g., on the amount of data loading and processing that needs to be done for rendering a given map for display. Thus, in a particularly preferred embodiment, if it is determined that a part of the map whose data is already stored in the local memory for the rendering processor is sufficiently similar to the new part of the map to be processed, as well re-using data for the existing part of the map stored in the local memory of the rendering processor for displaying the new part of the map, the data representing the new part of the map is not loaded (and processed) from the main map data store.

0032The Applicants have recognised that many maps to be displayed on PNDs can contain a large degree of self-similarity, for example due to re-occurring patterns (repetition) within and between the maps being displayed. For example, in more modern, urban environments, roads and buildings may typically be set out in rectangular grids, in which repeating patterns are often present. Even in mountainous or mediaeval cities, there may be repetition and similarities across the road network, albeit potentially at a lower scale. Individual road features, such as roundabouts, may also share common features, wherever they appear.

0033The present invention exploits this recognition, by exploiting similarity between successive map parts, e.g., tiles, to be prepared to render a map for display, to reuse already loaded (e.g. cached) map data, e.g., tiles, when displaying the map, thereby reducing computational load on the processor as well as reducing the amount of memory access by reducing the need to retrieve data and transfer data from the main map storage.

0034The map to be rendered may represent any desired map that is to be displayed and the data representing it can take any suitable and desired form. In one preferred embodiment, the map data comprises a vector representation of the map or maps in question. In another preferred embodiment it comprises a bitmap, e.g., tile-based, representation of the map. (In both these cases it will be possible to identify appropriate similarities and repetition within the map information that can then be exploited when rendering the map for display.) In a particularly preferred embodiment, the stored map data is such as to allow the map information to be displayed using varying levels of detail.

0035(As will be appreciated, references herein to the map information being a tile-based representation of a map to be displayed refers to the use of tiles (bitmaps) for representing the map information in the 3D "world" space, which tiles in the 3D world which will then be projected to the 2D screen space when they are actually displayed.)

0036In a preferred embodiment, the map data is stored in a compressed form. The compression process is preferably based on an analysis of the repetition and similarity present within the initial, base map information. This then has the advantage of being able to store the map data in a more compressed form as compared to its original, "raw" state, thereby, e.g., saving on the amount of storage resource that needs to be used for the map data (and thus provided in a given PND, for example).

0037The respective parts of the map to be processed may represent any desired and appropriate parts of the map to be processed. In a bitmap, e.g., tile-based map representation, they could, e.g., and preferably do, comprise bitmaps, e.g., tiles (3D world tiles) of the map. In a vector representation, they could, e.g., and preferably do, comprise appropriate vector representations of given parts or elements of the map to be displayed. The map parts that are to be displayed and whose similarity is assessed are preferably clearly identifiable parts of the map, such as respective defined bitmaps, such as 3D world tiles, of the map to be displayed.

0038The map parts are preferably parts of the map that will or can be treated and processed separately when the map is displayed. Thus the map parts are preferably geometrical elements (features) in the map that the map data represents, such as, and preferably two-dimensional and/or three-dimensional elements of the map that will be displayed. The map parts accordingly preferably represent appropriate map features, such as road sections, road junctions, roundabouts, buildings, blocks of buildings, bridges, etc..

0039In a particularly preferred embodiment, the map parts are elements of the map that could have similar shapes. An example of this would be that all roundabouts will generally be round, and so can be considered to be similar in shape.

0040The map parts are preferably elements of the map that could be similar when presented on a display to a user. Examples of this would be that all roundabouts will appear oval in a 3D-representation on a display, roads will normally have the same appearance of being gray, with white markings, when displayed, etc.. Thus, the map parts are preferably map elements that the map data represents that could be similar in the visual domain (when displayed to a user).

0041In a particularly preferred embodiment, the stored map data is in the form of a set or library of base map display elements, which elements can then be used to reproduce a desired map or maps. These map display elements are preferably then the map "parts" whose similarity is assessed (and that are then reused or not, accordingly): (Most preferably, the stored map information also includes a set of "map construction" data, indicating how to reproduce the map (or maps) using the predefined map display elements (using the predefined map display element "library").)

0042The predefined map display elements preferably represent appropriate map features, such as road sections, road junctions, roundabouts, buildings, blocks of buildings, bridges, etc..

0043The base, predefined map display elements preferably comprise one or more, and preferably plural, (predefined) shape templates, which can then be used to reconstruct a map itself. The shape templates may, e.g., represent larger features, such as roundabouts, and/or smaller features such as entrances or exits to roundabouts, etc.. Storing display elements (e.g. shape templates) representing smaller scale features may facilitate greater reuse of the stored display elements, and vice-versa.

0044In a particularly preferred embodiment, display elements (e.g. shape templates) for different scale features are included in the stored map data.

0045In a particularly preferred embodiment, the stored map data uses a hierarchically arranged set of predefined map display elements (e.g. shape templates), i.e. such that a given display element (shape template) is represented at plural different levels of detail. This then allows an element having the required level of detail for the map view being displayed to be used, rather than, e.g. always having to load and store a high resolution image even when that may not be perceptible to a user. The map display elements could also or instead be deconstructed into multiple sub-elements.

0046In these arrangements, the similarity between already stored map display elements and a new map display element or elements to be processed is accordingly preferably assessed, and then either a new map display element(s) loaded or an already stored map display element(s) reused, accordingly.

0047The main store for the map data to be displayed can take any suitable and desired form, and the map data can be stored in any desired and suitable fashion. The main map data store may, e.g., be a main memory of the displaying device (e.g. PND) itself. Alternatively or additionally, the main map information store could be a remote memory, coupled to a server, for example, with the map data then being transferred to the displaying device (e.g. PND) in use, e.g., via an, e.g. wireless, network connection.

0048The local memory of the rendering processor may similarly take any suitable and desired form. It is preferably a cache memory of or available to the rendering processor.

0049As discussed above, in the present invention if it is determined that a new part of the map to be processed for display is sufficiently similar to map data that is already stored in the local memory of the rendering device, data for the new part of the map is preferably not read from the main map data store and processed by the rendering device, but instead the existing map data in the local memory of the rendering device is re-used.

0050Conversely, if it is determined that the existing map data stored in the local memory of the rendering device is not sufficiently similar to the new map data so as to be able to be re-used, then the data representing the new part of the map should be, and preferably is, loaded and processed by the rendering device so as to display the relevant part of the map.

0051The similarity assessment may be performed by any suitable and desired element or processor, etc., e.g., of the navigation apparatus. Thus it may, e.g., be performed on the "host" (i.e. main application) processor of the navigation apparatus, by means of a separate processor (e.g. a DSP), or by the rendering processor (e.g. GPU), itself, as desired.

0052The similarity (or otherwise) between the respective parts of the map can be assessed and determined in any desired and suitable manner. The aim of this process is preferably to identify whether the map parts will be similar when displayed. Thus, the similarity assessment preferably attempts to identify whether the respective map parts (e.g. map display elements) will be (sufficiently) similar when displayed (as opposed, e.g., to looking for similarity at the bit level in the map information (in the bitwise representation of the map information)).

0053In a particularly preferred embodiment, the similarity assessment considers whether geometrical elements (features) in the map parts that are being considered are similar (i.e. looks for similarity at the geometry level in the map), e.g. and preferably, so as to identify similarity between geometrical features in the map (represented in the map information). Most preferably the similarity assessment considers whether two-dimensional and/or three-dimensional elements of the map will be similar when displayed.

0054In a particularly preferred embodiment, the similarity assessment considers shape similarity in the initial map information, i.e. whether the map parts (e.g. map display elements in or of the map parts) have similar shapes. An example of this would be that all roundabouts will generally be round, and so can be considered to be similar in shape. Thus, in a particularly preferred embodiment, the similarity assessment considers whether the respective map parts can be considered to have similar shapes (based, e.g., and preferably, on a suitable image or component analysis of the map parts in question).

0055The similarity assessment preferably also or instead, and preferably also, considers similarity of representation of the map information, i.e. considers whether the parts of the map will be (sufficiently) similar when presented on a display to a user. Examples of this would be that all roundabouts will appear oval in a 3D-representation on a display, roads will normally have the same appearance of being gray, with white markings, when displayed, etc.. Thus, the similarity assessment preferably considers whether the map parts will be similar in the visual domain (when displayed to a user).

0056The similarity assessment considers whether the map parts can be considered to be sufficiently similar or not by comparison to some form of predefined similarity threshold. Specifically, the similarity assessment uses a function that calculates a relative error between the already stored map part and the new map part and then determines whether the relative error is below a selected threshold value or not. If the relative error is above the threshold value, the data for the new map part will be loaded and processed. The relative error calculation function preferably use image analysis and/or component analysis techniques, and/or stores this data in some form when the image (map) data is generated.

0057In a preferred embodiment, the similarity assessment uses one or more component analysis techniques such as Fourier analysis, Principal Component Analysis, Discrete Cosine Transformation, and/or Hough Transform, etc., to assess the similarity between the map parts.

0058In a particularly preferred embodiment, the similarity assessment uses Primary Component Analysis (PCA) techniques (or similar) to determine the major components (of contribution) of the map part to be loaded and of the map part that is already loaded, and then compares these components, preferably by determining the root mean squared error (RMSE) between the contributing components of the already locally stored map part, and the contributing components of the desired (to be loaded) map part, to determine the relative "error" measurement.

0059In a particularly preferred embodiment, the stored map data includes meta-information to allow the device displaying the map to test and determine how similar respective parts of the map are. This similarity test meta-information preferably comprises, e.g., data representing the contributing component(s) of the map part, e.g., as determined by primary component analysis (as discussed above).

0060The similarity, e.g. 'contributing component', data may, e.g., be determined in advance or in use and stored with the map part data in the main map store and the local memory (as required), and then used when carrying out the similarity determination.

0061Other similarity assessment arrangements and processes would, of course, be possible. For example, image analysis techniques such as the Hough transform to detect lines/circles or skeletization techniques may be used to derive the necessary error comparison information, if desired.

0062The similarity assessment is preferably configured to take account of run-time parameters, such as the position of the map part in the 3D world, the camera angle, projection settings, whether fogging is used, display resolution, colour depth, etc.. One or more of these run-time parameters is preferably used to tune the similarity assessment and, e.g., and preferably, the error margin allowed for the similarity assessment. The Applicants have recognised that an assessment of whether given map parts for display can be considered to be sufficiently similar or not can depend on such run-time parameters, and therefore the present invention preferably takes them into account in the similarity assessment.

0063In a particularly preferred embodiment, the similarity test for deciding whether new data needs to be processed for display is modified depending upon the distance from the viewer of the map part that is being displayed. Thus, e.g., where a threshold is used to determine whether the map parts are similar or not, the threshold value is preferably varied and selected in accordance with the distance from the viewer of the map part that is to be displayed.

0064The Applicants have recognised that as the amount of visible detail decreases with distance from the viewer, the similarity analysis can employ a larger error margin, the greater the distance from the viewer of the map part in question. Employing a larger error margin for the similarity analysis increases the chance of a match from the local memory and thus the efficiency of the process.

0065Thus, the similarity analysis preferably takes account of the level of detail required. To facilitate this, multiple levels of detail (e.g. accompanied by similarity data as described above) may be stored simultaneously (like for mip-mapping techniques), if desired.

0066Once the similarity assessment (determination) has been completed, the appropriate map part is selected for display based on the similarity analysis. As discussed above, the chosen map part candidate may be a processed map part that is already in the local memory for the rendering device, or it may be a new map part to be processed from the main map storage.

0067The map part selected for display is preferably subjected to appropriate parameterisation for display, so as to, e.g., and preferably, modify and/or control the way the map part is displayed in view of the current (run-time) display conditions for the map part. Such parameterisation is preferably based on run-time parameters, such as rotation, skew, scaling factors, transparency, color re-mapping parameters, etc..

0068In a particularly preferred embodiment, the map rendering can apply a transformation to an already stored map part when it is displayed. Such transformation could, e.g., and preferably does, comprise one or more of rotating, scaling and/or translating the map part element relative to its stored state or configuration.

0069This facilitates using already locally stored (cached) map parts for (new) map parts that they may not match exactly, as it may be used to compensate for slight variations, e.g., in the road network, such as map parts not being perfectly aligned (but otherwise being very similar). This may in particular be used for map parts that are further from the viewer (nearer map display parts may need to be loaded and processed in full, as simply applying a transformation may lead to unacceptable visual quality).

0070Thus, in a particularly preferred embodiment the similarity determination can and preferably does include determining whether there is any misalignment between the map parts, and preferably, also determining, if necessary and possible, a transformation to apply to compensate for the determined misalignment. The misalignment, if any, and the form of translation to apply to compensate for it, is preferably determined by comparing the contributing components of a map part in the local memory to the corresponding components of the new map part to be displayed. Simple affine rotations are preferably employed. For scaling, a comparison of desired and available scale is preferably done.

0071In a preferred embodiment, a larger map part can be split into smaller parts that can then be processed and displayed individually. This may reduce the effects of any non-alignment, and help to prevent too much distortion of bitmaps under scaling, for example. Also, since the individual, smaller parts may be expected to occur more frequently, they may be reused more frequently as well.

0072The map data can be rendered to display the map part in question in any suitable and desired manner. Exactly how this is done will depend upon the form of the map data, but essentially the map data should be read and processed appropriately by the rendering device to allow the map part to be displayed. The rendering may be carried out either in software or using a graphics processor, for example.

0073In a preferred embodiment, the rendering processor can selectively store a map part that it has processed for display in the local memory for future use. The rendering processor may generate a particular or selected version of the rendered map part for storage in the local memory for future use, if desired.

0074The present invention may be used for any form or representation of the map display information. For example, the self-similarity holds both for bitmap data (e.g. when rendering tiles) and for vector (2D/3D) data.

0075Furthermore, the present invention is applicable for digital terrain models as well. For example, self-similarity is to be expected in mountains as well, and a level-of-detail refinement as described above would suit terrain models (the acceptable error margin for terrain models may be higher).

0076In a preferred embodiment, the local storing (caching) process is scaleable, depending upon the memory available to the rendering processor. For example, if less memory is available, cached data can be evicted and regenerated more often. Normal cache eviction mechanisms can also be used (LRU, FIFO etc.), if desired.

0077The principles of the present invention in any of its aspects and embodiments are applicable to any form of mapping or navigation apparatus and to the display of any desired and suitable form of map information. In preferred embodiments the apparatus is a navigation apparatus. One particular area of utility is in relation to portable navigation devices (PND). In embodiments, therefore, the mapping or navigation apparatus is a portable navigation device (PND). In accordance with a further aspect, the present invention provides a portable navigation device (PND) comprising the apparatus in accordance with any of the aspects or embodiments of the invention described. Accordingly, in embodiments of the invention, the method is a method of operating a mapping or navigation system of a portable navigation device. The PND may, and preferably does, include one or more other features typical of PNDs, such as, and preferably, an input interface configured to enable a user to interact with and/or control the apparatus and/or device.

0078The invention is also applicable to navigation apparatus which is provided as part of an integrated navigation system. For example the apparatus may form part of an in-vehicle integrated navigation system. In accordance with another aspect of the invention, the present invention provides a navigation system comprising a navigation apparatus in accordance with any of the aspects or embodiments of the invention described. Accordingly, in embodiments of the invention, the method is a method of operating a navigation apparatus of a navigation system. The navigation system may be an integrated in-vehicle navigation system.

0079Regardless of its implementation, a navigation apparatus used with the present invention may comprise a processor, memory, and digital map data stored within said memory. The processor and memory cooperate to provide an execution environment in which a software operating system may be established. One or more additional software programs may be provided to enable the functionality of the apparatus to be controlled, and to provide various other functions. A navigation apparatus of the invention may preferably include GPS (Global Positioning System) signal reception and processing functionality. The apparatus may comprise one or more output interfaces by means of which information may be relayed to the user. The output interface(s) may include a speaker for audible output in addition to the visual display. The apparatus may comprise input interfaces including one or more physical buttons to control on/off operation or other features of the apparatus.

0080In other embodiments, the mapping or navigation apparatus may be implemented by means of an application of a processing device which does not form part of a specific mapping or navigation device. For example the invention may be implemented using a suitable computer system arranged to execute mapping or navigation software. The system may be a mobile or portable computer system e.g. a mobile telephone or laptop, or may be a desktop system.

0081Although the present invention has been described above with particular reference to tile-based map information rendering, the techniques of the present invention may be applied to other techniques for rendering map information. For example, the techniques of the present invention could equally be used when rendering maps for display using vector graphics or triangle meshes, etc..

0082As will be appreciated by those skilled in the art, all of the aspects and embodiments of the invention described herein can and preferably do include any one or more of the preferred and optional features of the invention described herein, as appropriate.

0083The methods in accordance with the present invention may be implemented at least partially using software e.g. computer programs. The present invention thus also extends to a computer program comprising computer readable instructions executable to perform a method according to any of the aspects or embodiments of the invention.

0084The invention correspondingly extends to a computer software carrier comprising such software which when used to operate a system or apparatus comprising data processing means causes in conjunction with said data processing means said apparatus or system to carry out the steps of the methods of the present invention. Such a computer software carrier could be a non-transistory physical storage medium such as a ROM chip, CD ROM or disk, or could be a signal such as an electronic signal over wires, an optical signal or a radio signal such as to a satellite or the like.

0085Where not explicitly stated, it will be appreciated that the invention in any of its aspects may include any or all of the features described in respect of other aspects or embodiments of the invention to the extent they are not mutually exclusive. In particular, while various embodiments of operations have been described which may be performed in the method and by the system or apparatus, it will be appreciated that any one or more or all of these operations may be performed in the method and by the system or apparatus, in any combination, as desired, and as appropriate.

0086Advantages of these embodiments are set out hereafter, and further details and features of each of these embodiments are defined in the accompanying dependent claims and elsewhere in the following detailed description.

<u>Brief Description of the Drawings</u>

0087Various aspects of the teachings of the present invention, and arrangements embodying those teachings, will hereafter be described by way of illustrative example with reference to the accompanying drawings, in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Fig. 1</figref> is a schematic illustration of a Global Positioning System (GPS);</li><li><figref idref="f0001">Fig. 2</figref> is a schematic illustration of electronic components arranged to provide a navigation device;</li><li><figref idref="f0002">Fig. 3</figref> is a schematic illustration of the manner in which a navigation device may receive information over a wireless communication channel;</li><li><figref idref="f0003">Figs. 4A and 4B</figref> are illustrative perspective views of a navigation device;</li><li><figref idref="f0004">Figure 5</figref> shows an exemplary map to be displayed that the technique of the present invention can be applied to;</li><li><figref idref="f0005">Figure 6</figref> shows schematically the preparation of a map representation for use in a preferred embodiment of the present invention;</li><li><figref idref="f0006">Figure 7</figref> shows schematically a preferred embodiment for rendering a map for display in accordance with the present invention; and</li><li><figref idref="f0004">Figures 8 and 9</figref> illustrate further preferred techniques for use in preferred embodiments of the present invention.</li></ul>

0088Like reference numerals are used for like features throughout the drawings.

<u>Detailed Description of Preferred Embodiments</u>

0089Preferred embodiments of the present invention will now be described with particular reference to a PND. It should be remembered, however, that the teachings of the present invention are not limited to PNDs but are instead universally applicable to any type of processing device that is configured to display map information (and preferably to execute navigation software so as to provide route planning and navigation functionality). It follows therefore that in the context of the present application, a navigation device is intended to include (without limitation) any type of route planning and navigation device, irrespective of whether that device is embodied as a PND, a navigation device built into a vehicle, or indeed a computing resource (such as a desktop or portable personal computer (PC), mobile telephone or portable digital assistant (PDA)) executing route planning and navigation software.

0090It will also be apparent from the following that the teachings of the present invention even have utility in circumstances where a user is not seeking instructions on how to navigate from one point to another, but merely wishes to be provided with a view of a given location. In such circumstances the "destination" location selected by the user need not have a corresponding start location from which the user wishes to start navigating, and as a consequence references herein to the "destination" location or indeed to a "destination" view should not be interpreted to mean that the generation of a route is essential, that travelling to the "destination" must occur, or indeed that the presence of a destination requires the designation of a corresponding start location.

0091With the above provisos in mind, <figref idref="f0001">Fig. 1</figref> illustrates an example view of Global Positioning System (GPS), usable by navigation devices. Such systems are known and are used for a variety of purposes. In general, GPS is a satellite-radio based navigation system capable of determining continuous position, velocity, time, and in some instances direction information for an unlimited number of users. Formerly known as NAVSTAR, the GPS incorporates a plurality of satellites which orbit the earth in extremely precise orbits. Based on these precise orbits, GPS satellites can relay their location to any number of receiving units.

0092The GPS system is implemented when a device, specially equipped to receive GPS data, begins scanning radio frequencies for GPS satellite signals. Upon receiving a radio signal from a GPS satellite, the device determines the precise location of that satellite via one of a plurality of different conventional methods. The device will continue scanning, in most instances, for signals until it has acquired at least three different satellite signals (noting that position is not normally, but can be determined, with only two signals using other triangulation techniques). Implementing geometric triangulation, the receiver utilizes the three known positions to determine its own two-dimensional position relative to the satellites. This can be done in a known manner. Additionally, acquiring a fourth satellite signal will allow the receiving device to calculate its three dimensional position by the same geometrical calculation in a known manner. The position and velocity data can be updated in real time on a continuous basis by an unlimited number of users.

0093As shown in <figref idref="f0001">Figure 1</figref>, the GPS system is denoted generally by reference numeral 100. A plurality of satellites 120 are in orbit about the earth 124. The orbit of each satellite 120 is not necessarily synchronous with the orbits of other satellites 120 and, in fact, is likely asynchronous. A GPS receiver 140 is shown receiving spread spectrum GPS satellite signals 160 from the various satellites 120.

0094The spread spectrum signals 160, continuously transmitted from each satellite 120, utilize a highly accurate frequency standard accomplished with an extremely accurate atomic clock. Each satellite 120, as part of its data signal transmission 160, transmits a data stream indicative of that particular satellite 120. It is appreciated by those skilled in the relevant art that the GPS receiver device 140 generally acquires spread spectrum GPS satellite signals 160 from at least three satellites 120 for the GPS receiver device 140 to calculate its two-dimensional position by triangulation. Acquisition of an additional signal, resulting in signals 160 from a total of four satellites 120, permits the GPS receiver device 140 to calculate its three-dimensional position in a known manner.

0095<figref idref="f0001">Figure 2</figref> is an illustrative representation of electronic components of a navigation device 200 according to a preferred embodiment of the present invention, in block component format. It should be noted that the block diagram of the navigation device 200 is not inclusive of all components of the navigation device, but is only representative of many example components.

0096The navigation device 200 is located within a housing (not shown). The housing includes a processor 210 connected to an input device 220 and a display screen 240. The input device 220 can include a keyboard device, voice input device, touch panel and/or any other known input device utilised to input information; and the display screen 240 can include any type of display screen such as an LCD display, for example. In a particularly preferred arrangement the input device 220 and display screen 240 are integrated into an integrated input and display device, including a touchpad or touchscreen input so that a user need only touch a portion of the display screen 240 to select one of a plurality of display choices or to activate one of a plurality of virtual buttons.

0097The navigation device may include an output device 260, for example an audible output device (e.g. a loudspeaker). As output device 260 can produce audible information for a user of the navigation device 200, it is should equally be understood that input device 240 can include a microphone and software for receiving input voice commands as well.

0098In the navigation device 200, processor 210 is operatively connected to and set to receive input information from input device 220 via a connection 225, and operatively connected to at least one of display screen 240 and output device 260, via output connections 245, to output information thereto. Further, the processor 210 is operably coupled to a memory resource 230 via connection 235 and is further adapted to receive/send information from/to input/output (I/O) ports 270 via connection 275, wherein the I/O port 270 is connectible to an I/O device 280 external to the navigation device 200. The memory resource 230 comprises, for example, a volatile memory, such as a Random Access Memory (RAM) and a non-volatile memory, for example a digital memory, such as a flash memory. The external I/O device 280 may include, but is not limited to an external listening device such as an earpiece for example. The connection to I/O device 280 can further be a wired or wireless connection to any other external device such as a car stereo unit for hands-free operation and/or for voice activated operation for example, for connection to an ear piece or head phones, and/or for connection to a mobile phone for example, wherein the mobile phone connection may be used to establish a data connection between the navigation device 200 and the internet or any other network for example, and/or to establish a connection to a server via the internet or some other network for example.

0099<figref idref="f0001">Fig. 2</figref> further illustrates an operative connection between the processor 210 and an antenna/receiver 250 via connection 255, wherein the antenna/receiver 250 can be a GPS antenna/receiver for example. It will be understood that the antenna and receiver designated by reference numeral 250 are combined schematically for illustration, but that the antenna and receiver may be separately located components, and that the antenna may be a GPS patch antenna or helical antenna for example.

0100Further, it will be understood by one of ordinary skill in the art that the electronic components shown in <figref idref="f0001">Fig. 2</figref> are powered by power sources (not shown) in a conventional manner. As will be understood by one of ordinary skill in the art, different configurations of the components shown in <figref idref="f0001">Fig. 2</figref> are considered to be within the scope of the present application. For example, the components shown in <figref idref="f0001">Fig. 2</figref> may be in communication with one another via wired and/or wireless connections and the like. Thus, the scope of the navigation device 200 of the present application includes a portable or handheld navigation device 200.

0101In addition, the portable or handheld navigation device 200 of <figref idref="f0001">Fig. 2</figref> can be connected or "docked" in a known manner to a vehicle such as a bicycle, a motorbike, a car or a boat for example. Such a navigation device 200 is then removable from the docked location for portable or handheld navigation use.

0102Referring now to <figref idref="f0002">Fig. 3</figref>, the navigation device 200 may establish a "mobile" or telecommunications network connection with a server 302 via a mobile device (not shown) (such as a mobile phone, PDA, and/or any device with mobile phone technology) establishing a digital connection (such as a digital connection via known Bluetooth technology for example). Thereafter, through its network service provider, the mobile device can establish a network connection (through the internet for example) with a server 302. As such, a "mobile" network connection is established between the navigation device 200 (which can be, and often times is mobile as it travels alone and/or in a vehicle) and the server 302 to provide a "real-time" or at least very "up to date" gateway for information.

0103The establishing of the network connection between the mobile device (via a service provider) and another device such as the server 302, using an internet (such as the World Wide Web) for example, can be done in a known manner. This can include use of TCP/IP layered protocol for example. The mobile device can utilize any number of communication standards such as CDMA, GSM, WAN, etc.

0104As such, an internet connection may be utilised which is achieved via data connection, via a mobile phone or mobile phone technology within the navigation device 200 for example. For this connection, an internet connection between the server 302 and the navigation device 200 is established. This can be done, for example, through a mobile phone or other mobile device and a GPRS (General Packet Radio Service)-connection (GPRS connection is a high-speed data connection for mobile devices provided by telecom operators; GPRS is a method to connect to the internet).

0105The navigation device 200 can further complete a data connection with the mobile device, and eventually with the internet and server 302, via existing Bluetooth technology for example, in a known manner, wherein the data protocol can utilize any number of standards, such as GPRS, the data protocol standard for the GSM standard, for example.

0106The navigation device 200 may include its own mobile phone technology within the navigation device 200 itself (including an antenna for example, or optionally using the internal antenna of the navigation device 200). The mobile phone technology within the navigation device 200 can include internal components as specified above, and/or can include an insertable card (e.g. Subscriber Identity Module or SIM card), complete with necessary mobile phone technology and/or an antenna for example. As such, mobile phone technology within the navigation device 200 can similarly establish a network connection between the navigation device 200 and the server 302, via the internet for example, in a manner similar to that of any mobile device.

0107For GPRS phone settings, a Bluetooth enabled navigation device may be used to correctly work with the ever changing spectrum of mobile phone models, manufacturers, etc., model/manufacturer specific settings may be stored on the navigation device 200 for example. The data stored for this information can be updated.

0108In <figref idref="f0002">Fig. 3</figref> the navigation device 200 is depicted as being in communication with the server 302 via a generic communications channel 318 that can be implemented by any of a number of different arrangements. The server 302 and a navigation device 200 can communicate when a connection via communications channel 318 is established between the server 302 and the navigation device 200 (noting that such a connection can be a data connection via mobile device, a direct connection via personal computer via the internet, etc.).

0109The server 302 includes, in addition to other components which may not be illustrated, a processor 304 operatively connected to a memory 306 and further operatively connected, via a wired or wireless connection 314, to a mass data storage device 312. The processor 304 is further operatively connected to transmitter 308 and receiver 310, to transmit and send information to and from navigation device 200 via communications channel 318. The signals sent and received may include data, communication, and/or other propagated signals. The transmitter 308 and receiver 310 may be selected or designed according to the communications requirement and communication technology used in the communication design for the navigation system 200. Further, it should be noted that the functions of transmitter 308 and receiver 310 may be combined into a signal transceiver.

0110Server 302 is further connected to (or includes) a mass storage device 312, noting that the mass storage device 312 may be coupled to the server 302 via communication link 314. The mass storage device 312 contains a store of navigation data and map information, and can again be a separate device from the server 302 or can be incorporated into the server 302.

0111The navigation device 200 is adapted to communicate with the server 302 through communications channel 318, and includes processor, memory, etc. as previously described with regard to <figref idref="f0001">Fig. 2</figref>, as well as transmitter 320 and receiver 322 to send and receive signals and/or data through the communications channel 318, noting that these devices can further be used to communicate with devices other than server 302. Further, the transmitter 320 and receiver 322 are selected or designed according to communication requirements and communication technology used in the communication design for the navigation device 200 and the functions of the transmitter 320 and receiver 322 may be combined into a single transceiver.

0112Software stored in server memory 306 provides instructions for the processor 304 and allows the server 302 to provide services to the navigation device 200. One service provided by the server 302 involves processing requests from the navigation device 200 and transmitting navigation data from the mass data storage 312 to the navigation device 200. Another service provided by the server 302 includes processing the navigation data using various algorithms for a desired application and sending the results of these calculations to the navigation device 200.

0113The communication channel 318 generically represents the propagating medium or path that connects the navigation device 200 and the server 302. Both the server 302 and navigation device 200 include a transmitter for transmitting data through the communication channel and a receiver for receiving data that has been transmitted through the communication channel.

0114The communication channel 318 is not limited to a particular communication technology. Additionally, the communication channel 318 is not limited to a single communication technology; that is, the channel 318 may include several communication links that use a variety of technology. For example, the communication channel 318 can be adapted to provide a path for electrical, optical, and/or electromagnetic communications, etc. As such, the communication channel 318 includes, but is not limited to, one or a combination of the following: electric circuits, electrical conductors such as wires and coaxial cables, fibre optic cables, converters, radio-frequency (RF) waves, the atmosphere, empty space, etc. Furthermore, the communication channel 318 can include intermediate devices such as routers, repeaters, buffers, transmitters, and receivers, for example.

0115In one illustrative arrangement, the communication channel 318 includes telephone and computer networks. Furthermore, the communication channel 318 may be capable of accommodating wireless communication such as radio frequency, microwave frequency, infrared communication, etc. Additionally, the communication channel 318 can accommodate satellite communication.

0116The communication signals transmitted through the communication channel 318 include, but are not limited to, signals as may be required or desired for given communication technology. For example, the signals may be adapted to be used in cellular communication technology such as Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), Code Division Multiple Access (CDMA), Global System for Mobile Communications (GSM), etc. Both digital and analogue signals can be transmitted through the communication channel 318. These signals may be modulated, encrypted and/or compressed signals as may be desirable for the communication technology.

0117The server 302 includes a remote server accessible by the navigation device 200 via a wireless channel. The server 302 may include a network server located on a local area network (LAN), wide area network (WAN), virtual private network (VPN), etc.

0118The server 302 may include a personal computer such as a desktop or laptop computer, and the communication channel 318 may be a cable connected between the personal computer and the navigation device 200. Alternatively, a personal computer may be connected between the navigation device 200 and the server 302 to establish an internet connection between the server 302 and the navigation device 200. Alternatively, a mobile telephone or other handheld device may establish a wireless connection to the internet, for connecting the navigation device 200 to the server 302 via the internet.

0119The navigation device 200 may be provided with information from the server 302 via information downloads which may be periodically updated automatically or upon a user connecting navigation device 200 to the server 302 and/or may be more dynamic upon a more constant or frequent connection being made between the server 302 and navigation device 200 via a wireless mobile connection device and TCP/IP connection for example. For many dynamic calculations, the processor 304 in the server 302 may be used to handle the bulk of the processing needs, however, processor 210 of navigation device 200 can also handle much processing and calculation, oftentimes independent of a connection to a server 302.

0120As indicated above in <figref idref="f0001">Fig. 2</figref>, a navigation device 200 includes a processor 210, an input device 220, and a display screen 240. The input device 220 and display screen 240 are integrated into an integrated input and display device to enable both input of information (via direct input, menu selection, etc.) and display of information through a touch panel screen, for example. Such a screen may be a touch input LCD screen, for example, as is well known to those of ordinary skill in the art. Further, the navigation device 200 can also include any additional input device 220 and/or any additional output device 241, such as audio input/output devices for example.

0121<figref idref="f0003">Figs 4A and 4B</figref> are perspective views of a navigation device 200. As shown in <figref idref="f0003">Fig. 4A</figref>, the navigation device 200 may be a unit that includes an integrated input and display device 290 (a touch panel screen for example) and the other components of <figref idref="f0001">fig. 2</figref> (including but not limited to internal GPS receiver 250, microprocessor 210, a power supply, memory systems 230, etc.).

0122The navigation device 200 may sit on an arm 292, which itself may be secured to a vehicle dashboard/window/etc. using a suction cup 294. This arm 292 is one example of a docking station to which the navigation device 200 can be docked.

0123As shown in <figref idref="f0003">Fig. 4B</figref>, the navigation device 200 can be docked or otherwise connected to an arm 292 of the docking station by snap connecting the navigation device 292 to the arm 292 for example. The navigation device 200 may then be rotatable on the arm 292, as shown by the arrow of <figref idref="f0003">Fig. 4B</figref>. To release the connection between the navigation device 200 and the docking station, a button on the navigation device 200 may be pressed, for example. Other equally suitable arrangements for coupling and decoupling the navigation device to a docking station are well known to persons of ordinary skill in the art.

0124As discussed above, an important aspect of the operation of the navigation device 200 of the present embodiment is to display map information to a user on its display screen 240. The map information will be displayed, e.g., in response to a user's inputs, under the control of the processor 210. To facilitate this, the processor 210 includes a graphics processor that renders the desired images for display in response to appropriate graphics commands and data generated by the processor 210.

0125The map information that is displayed is stored in the memory 230 of the navigation device 200 and then read therefrom and processed appropriately by the processor 210 for display on the display screen 240.

0126Map information for display may also be stored in the mass data storage 312 of the server 302 and transferred to the memory in the navigation device 200 via the communications channel 318 in use, as required. This will then allow, e.g., the map information stored by the navigation device 200 to be updated in use, and allow the navigation device to have access to and to display more maps than, e.g., could be stored in the memory 230 of the navigation device 200 at any one time.

0127As discussed above, the present invention relates to methods for rendering the map information to be displayed in a more efficient manner. A number of preferred embodiments for achieving this will be described.

0128The Applicants have recognised that maps of road networks which are typically to be displayed on a navigation device can have a large degree of self-similarity, for example due to re-occurring patterns in, e.g., urban construction and layout. For example, to maximise space and reduce cost, buildings are often arranged in rectangular blocks. The road network surrounding these built-up areas is typically rectangular as well. Even in mountainous or medieval cities, there will often be self-similarity within the road network, although potentially at a lower scale.

0129<figref idref="f0004">Figure 5</figref>, which shows a map from a suburb of Detroit, MI, USA, illustrates this. As can be seen in <figref idref="f0004">Figure 5</figref>, the map contains a number of similar, horizontally and vertically oriented roads 1, a number of roughly 90° intersections (both 4-way and T-crossings) 2, and combinations 3 of these elements (which may, e.g., be similar under stretching and scaling transformations). A component analysis of this image would show mainly "horizontal" and "vertical" components.

0130The present embodiments exploit this property of self-repetition within maps to be displayed, to make the map rendering process more efficient.

0131In the first place, algorithms are applied to reduce the redundancy in the map data, thereby allowing the map display data to be stored in a smaller amount of storage space. This can include exploiting multi-scale self-similarity, and equality under scaling, rotation and translation transformations, or even non-linear transformations. (Such processing of the map display data is not essential, but it is preferred.)

0132<figref idref="f0005">Figure 6</figref> shows schematically an arrangement for preparing a representation of map display information for use by a navigation device.

0133As shown in <figref idref="f0005">Figure 6</figref>, a set of source map data 600 is subject to a similarity analysis (step 601) and a classification and transformation parameter generation (step 602), and then a compressed representation of the map data is generated (step 603) and stored in memory (step 604) for use by or provision to the navigation device 200.

0134The similarity analysis 601 is configured to try to identify shape and/or representation similarity in the source map data. The shape similarity relates to the shape of elements to be displayed in the source map data (e.g. a roundabout is always round-ish) and can be considered to be a property of the source map data. Representation similarity assesses the similarity of elements in the source map that will be similar in the visual domain, i.e. when displayed to a user. For example, roundabouts will tend always to be oval under 3D projection and roads typically will be gray with white lines when displayed (in the visual domain), irrespective of their shape.

0135The similarity analysis 601 accordingly identifies elements in (represented by) the source map data 600 that are similar in terms of their shape and/or their appearance in the visual domain (when displayed).

0136The classification and transformation parameter generation process 602 operates to classify elements in the map into "buckets" (i.e. groups) of similar elements (in terms of their shape and/or representation in the visual domain, as determined by the similarity analysis 601). Thus, it, in effect, classifies elements in the map into sets of similar elements which elements can then be used as "reference" elements for the map. Preferably the arrangement is so as to store a full set of data for only a single reference copy of map elements determined to be similar, with the map data then referencing that copy when required and including, e.g., data indicating the place of the element in the map data. The reference map display elements may be stored as bitmaps, or as vector representations, etc..

0137The classification and transformation parameter generation process 602 also determines the parameters and conditions under which the identified map elements can be considered to be similar. This can include, for example, identifying any necessary rotation, such as scaling or transformation, that is needed to make a given map element similar to another (to the reference element), as determined by the similarity analysis. This process also establishes and stores references between the classified reference map display elements and the original place of the map element in question in the source data. (Alternatively, this could be carried out as a separate step.)

0138The compressed map generation process 603 operates to apply further compression to the map data. This may use, for example, conventional bitwise compression algorithms. This step is not essential, but applying conventional data compression techniques to the map data further reduces the storage required for the map data.

0139In this arrangement, the similarity analysis 601 and classification and transformation parameter generation 602 may comprise, e.g., using component analysis techniques such as Fourier analysis or Principal Component Analysis, pattern matching techniques, local search methods, such as simulated annealing, geometric algorithms, etc., to detect the level of self-similarity within the source map information 600 and to extract the basic features of the source map information, which features can then be used to reconstruct the original map information data set. The basic features are then stored in the memory 604 together with any further instructions or information (such as transformation parameters) needed to be able to use them to reconstruct the original map for display.

0140In this arrangement, the similarity analysis 601 and classification and transformation parameter generation 602 operate to derive and generate a map "database" that includes a "library" of predefined (predetermined) map display elements in the form of shape templates having aspects for which desired parameters can be specified, which "base" shape templates can then be used to construct (generate) a desired map for display. The shape templates may be, e.g., in the form of bitmaps, and/or vector representations, etc..

0141The map database also includes map "construction" information that references into the shape template library and includes parameter information to define how the shape templates should be used and displayed to display the map in question.

0142The shape templates and map construction information are encoded with less bits than the original map information, so the result is a compressed representation of the original, source map.

0143For example, a roundabout may, e.g., be stored in the source map information as a set of lines and nodes, often with additional intermediate points to improve the shape. However, the Applicants have recognised that roundabouts in a map database may often be categorized into a limited set of 'similar' roundabouts. A unique roundabout in the source map database can then be described by a reference to a predefined roundabout in a shape library and particular values for additional parameters indicating how the roundabout should be displayed.

0144The shape template parameters that are set in this regard can be of various types, such as location (longitude, latitude), rotation, etc.. Additional lines to describe an entry or exit road could also or instead be a parameter. The parameters could also or instead relate to road-attributes. For instance, turn restrictions of roads that connect to a roundabout will be present in other roundabouts, too.

0145The parametrization could be done in such a way that a pure lossless compression is achieved. However, in some cases it may be acceptable to have a small error (e.g. a slightly different shape), which is still within an acceptable margin. This can increase the efficiency of the map data compression.

0146The same principle can be applied to arbitrary other sub-shapes in the map database. For example, a similar thing holds for buildings, and blocks of buildings. Buildings can be categorized into a library of predefined buildings too, and by adding parameters this can be exploited for size. For example, location, scale, rotation, and texture, or even sub-shape, can be parameters of the predefined shape templates.

0147The set of shape-templates to be used for the map database and how to parametrise them is determined by applying an appropriate algorithm to the initial, source map information. Suitable algorithms for this could use, e.g., simple heuristics, genetic algorithms, simulated annealing, etc.

0148In the present embodiment, the shape-templates (for roads, buildings and terrain) are constructed hierarchically, so as to be able to apply them appropriately for different levels of detail. For example, a residential block may be a single cube in the database, with additional refinements. The single cube with coarse texture is shown on high zoom levels. Additional shapes (e.g. higher boxes on top of the coarse block) are then used for finer zoom levels, accompanied by a refinement of the texture.

0149The shape templates also have associated with them a number of attributes, e.g., indicating an appropriate texture or textures to be applied or that could be applied to the template to provide details such as road markings, one-way markers, etc.. This then allows the same base shape template to be used, even though different parts of the road network can differ by details such as road markings, one-way markers, etc.. Such attributes can also be employed to augment the displayed road network with, e.g., "face" data showing land use in a geographical area. Multiple textures may be used on a given display element (shape template) if desired.

0150It would also be possible to use different template sets for certain areas, e.g. for left- and right-driving countries, or countries with special traffic rules.

0151The shape-definition of an entry in the shape-template library could refer to other entries in the library as well. This can in some be cases be useful to decrease the size of the shape-definitions in the library.

0152Arrangements where base map display elements are stored and then referenced when the map is to be displayed can advantageously be used for remote applications such as, e.g., a web-based map or over-the-air updates of base map data or map patch distribution. For example, a map patch showing a roundabout would only need to transfer the reference to the already stored shaped template or map display element representing a roundabout in the library of map display elements that is already stored by the navigation device. A whole, new map could be distributed by sending new map construction information referencing the predefined map display elements (shape templates) in the library of map display elements.

0153<figref idref="f0006">Figure 7</figref> shows a preferred embodiment of the rendering of the map information that has been prepared in accordance with the above techniques to display a map on the display device 200. This rendering is done in accordance with the present invention.

0154As discussed above, when a stored map is rendered for display, it will typically be processed in discrete parts, e.g., as pre-defined map elements, such as 3D world tiles. To facilitate this, data representing parts, such as elements (e.g. tiles), of the whole map to be displayed will typically be processed successively by the rendering processor for display.

0155The Applicants have recognised that similarity between map parts to be displayed can be exploited to reuse already locally stored (e.g. cached) map parts when displaying a map, thereby reducing computational load on the rendering processor as well as reducing the amount of memory access by reducing the need to retrieve data and transfer information to the rendering processor.

0156<figref idref="f0006">Figure 7</figref> shows a preferred embodiment of this process.

0157As shown in <figref idref="f0006">Figure 7</figref>, when the application processor 705 is due to process a new part of a map to be displayed (such as a new map element or elements) from the main map storage 230 for display, it checks to see whether any existing data in its local cache memory 706 represents a similar part (e.g. element) to the new data that should be processed. This is done by performing a shape and/or representation similarity analysis 601 between the new map parts (elements) to be processed and any already processed map part (elements) that are stored in the cache 706.

0158The similarity analysis 601 is configured and operates in the same manner as the similarity analysis 601 shown in <figref idref="f0005">Figure 6</figref>. Thus the similarity analysis 601 in <figref idref="f0006">Figure 7</figref> operates to consider and identify map elements that can be considered to be similar in shape and/or representation in the visual domain (i.e. when displayed). The similarity analysis 601 is also configured to take account of run-time parameters 700, such as the position of the map element (e.g. geometry) in the world, the camera angle, projection settings, whether fogging is used, display resolution, colour depth, etc.. These run-time parameters are used to tune the similarity analysis and error margin allowed for the similarity analysis. The Applicants have recognised that an assessment of whether given map elements for display can be considered to be sufficiently similar or not can depend on such run-time parameters, and therefore the present embodiment takes them into account in the similarity analysis.

0159The similarity analysis 601 considers, in the light of the run-time parameters 700, whether a map element already stored in the cache 706 can be considered to be sufficiently similar to a new map element to be processed and loaded from the main map storage 230. The map element to use for display is then selected in a candidate selection stage 701 based on the similarity analysis. The chosen candidate may be a processed map element that is already in the cache 706, or it may be new map data to be processed from the main map storage 230, based on the results of the similarity analysis.

0160The similarity analysis 601 uses a function that calculates the relative error between the candidate map elements being compared (i.e. in the cache and in the main map store) and determines whether the error is below a selected threshold value or not. If the error is above the threshold value, new data will be generated. The relative error calculation function could use image analysis techniques, for example, and/or store this data in some form when the map elements (data) are generated.

0161In a preferred embodiment, the similarity assessment 601 uses Primary Component Analysis (PCA) techniques (or similar) to determine the major axes of contribution of a given display element, etc. to be loaded or that is already loaded. (For the road junction display element shown in <figref idref="f0004">Fig. 9</figref>, this would be a mainly vertical component (the road with the dashes) as most contributing component, directly followed by a mainly horizontal component (the road to the right) as well as probably some minor components.)

0162This 'contributing component' data is then stored alongside the display element, e.g. bitmap (or other representation), in the cache 706. The root mean squared error (RMSE) between the contributing components of the already stored display element, and the contributing components of the desired (to be loaded) display element is then determined and used as the relative "error" measurement. The "desired components" (i.e. those that need to be rendered) can be stored alongside vector data in the map database (main map storage 230).

0163Depending on the type of rendering technique (tile/bitmap or vector), image analysis techniques such as the Hough transform to detect lines/circles or skeletization techniques may be used to derive the necessary error comparison information (e.g. if the bitmaps were not generated on the fly and thus this information is not available).

0164Other similarity assessment arrangements and processes would, of course, be possible. For example, in the present embodiment, it is the "host", application processor of the navigation apparatus that performs the similarity assessment, but other arrangements such as having a separate processor (e.g. a DSP) or the rendering processor (e.g. GPU) itself, doing this, would be possible if desired.

0165The selected map element candidate for display is then subject to appropriate parameterisation for display in a parameterisation step 702. Such parameterisation is based on the run-time parameters (e.g. rotation, skew, scaling factors, transparency, color re-mapping parameters, etc.), and may be used to modify and control the way the element is displayed in view of the current (run-time) display conditions for the element.

0166The selected candidate map display element is then rendered appropriately in a rendering step 703 for display on the display 240. The rendering step may be carried out, as is known in the art, either in software or using a graphics processor, for example. The renderer 703 may also generate a version of the rendered map element for storage in the cache 706 for future use.

0167Thus, in this arrangement, when map data is to be processed for display, it is determined whether to use already cached map data to display the map data in question, or whether new map data needs to be loaded and processed from the main map storage 230. This is done by means of a similarity analysis 601. If the map data already in the cache 706 is determined to be sufficiently similar to the map data that is to be displayed, the new data from the memory 230 is not loaded, but instead the existing data in the cache is processed for display of the map element in question. This has the benefit of a reduced system load, since already processed data does not need to be reloaded and reprocessed.

0168In a preferred embodiment, the caching process is scaleable, depending upon the memory available to the rendering process. For example, if less memory is available, cached data can be evicted and regenerated more often. Normal cache eviction mechanisms can also be used (LRU, FIFO etc.), if desired.

0169In the present embodiment, the similarity analysis 601 for deciding whether new data needs to be processed for display is modified depending upon the distance from the viewer of the map element that is being displayed. The Applicants have recognised that as the amount of visible detail decreases with distance from the viewer, the similarity analysis can employ a larger error margin, the greater the distance from the viewer of the map element in question. Employing a larger error margin for the similarity analysis increases the chance of a match from the cache and thus the efficiency of the process.

0170<figref idref="f0004">Figure 8</figref> illustrates this. Map display elements, such as tiles and textures at level zero (nearest to the viewer) shown in <figref idref="f0004">Figure 8</figref> will have and require the highest accuracy, but the accuracy requirement decreases with distance from the viewer (indicated by a higher number in <figref idref="f0004">Figure 8</figref>). Thus the similarity analysis 601 takes account of the level of detail required. To do this, multiple levels of detail (accompanied by error figures as described above) are stored simultaneously in the cache (like for mip-mapping techniques).

0171The embodiment also applies transformations, such as scaling, rotation and/or translation, to map display elements that are to be displayed. This is to compensate for slight variations in the road network, such as map display elements not being perfectly aligned in their "base", defined form. This may in particular be used for map display elements that are further from the viewer (nearer map display elements may need to be loaded and processed in full, as simply applying a transformation may lead to unacceptable visual quality).

0172<figref idref="f0004">Figure 9</figref> illustrates this, and shows in the first two figures the need to apply a rotational transformation to a base map display element to improve the accuracy of the reused map display element. Any misalignment, and the form of translation to apply to compensate for it, is determined by comparing the contributing components of a map display element (e.g. shape template) in the cache to the corresponding components of the element actually to be displayed. Simple affine rotations are employed. For scaling, a comparison of desired and available scale is done.

0173<figref idref="f0004">Figure 9</figref> also illustrates in the right-hand image a further feature of this embodiment, namely splitting a larger map display element into smaller components and storing those components individually. This may reduce the effects of any non-alignment, and help to prevent too much distortion of bitmaps under scaling, for example. Also, since the individual, smaller features may be expected to occur more frequently, they may be reused more frequently as well.

0174The present invention may be used for any form or representation of the map display information. For example, the self-similarity holds both for bitmap data (e.g. when rendering tiles) and for vector (2D/3D) data.

0175Furthermore, the present invention is applicable for digital terrain models as well. For example, self-similarity is to be expected in mountains as well, and a level-of-detail refinement as described above would suit terrain models (the acceptable error margin for terrain models may be higher).

0176As will be appreciated from the above, the present invention facilitates the rendering of map information for display, e.g., on a PND, in a more efficient manner. This then leads to smaller loading and processing requirements for the map information, thereby facilitating, e.g., speed increases due to caching effects and a reduction in the load/read requirements on the storage medium.

0177This is achieved, in the preferred embodiments of the present invention at least, by identifying and exploiting similarities in the map information, so as to reduce the amount of map information that has to be loaded and processed to display the map.

0178It will also be appreciated that whilst various aspects and embodiments of the present invention have heretofore been described, the scope of the present invention is, not limited to the particular arrangements set out herein and instead extends to encompass all arrangements, and modifications and alterations thereto, which fall within the scope of the appended claims.

0179For example, whilst embodiments described in the foregoing detailed description refer to GPS, it should be noted that the navigation device may utilise any kind of position sensing technology as an alternative to (or indeed in addition to) GPS. For example the navigation device may utilise using other global navigation satellite systems such as the European Galileo system. Equally, it is not limited to satellite based but could readily function using ground based beacons or any other kind of system that enables the device to determine its geographic location.

0180It will also be well understood by persons of ordinary skill in the art that whilst the preferred embodiment may implement certain functionality by means of software, that functionality could equally be implemented solely in hardware (for example by means of one or more ASICs (application specific integrated circuit)) or indeed by a mix of hardware and software.

0181The scope of the invention is defined by the appended claims.