BACKGROUND OF THE INVENTION Navigational aids which assist users in identifying a route from a start position to a destination are well known and have particularly been used in vehicles who determine their location using the GPS (global positioning satellite) system in conjunction with electronic road maps.

In normal use, the system knows its current location and provides an optimal route to the user when the user selects a destination. The information provided by the user may be a display of a map and at times may include audio information that may point out certain landmarks to assist the driver in finding and following a route.

The problem with these types of navigational systems is that the user has to cognitively translate the information that is generally shown on a map into visual information that they can then use. The user has to thus be aware of the route, road signs and other visual locaters which assist in ensuring that they are on the correct route.

It is thought that users generally navigate by either one or a combination of two methods. Some users, generally men, navigate by maintaining an abstract, spatial representation of their environment and their position in it.

Others, in general women, represent routes in terms of landmarks and visual cues as to distance and orientation. In most cases, users may use both of these methods to varying extents.

In general, if a user wants to be assiste in finding a route to a particular destination, such as that in large shopping centres, airports and the like, there

are help or information desks that can provide a map or verbal directions respectively. However, both of these are not equal to the human navigational process and can lead to confusion and a person not finding their destination.

It is an object of the present invention to overcome at least some of the abovementioned problems or to at least provide the public with a useful alternative.

SUMMARY OF THE INVENTION Therefore in one form of the invention though this need not be the only or indeed the broadest form there is propose a navigation system providing a visual image of a route between a first position and a second position by calculating an optimise route through a plurality of points between said first and second positions said system including: a plurality of video clips, each video clip representative of a route between two points; a display means to display said video clips; an input means adapted to receive information as to the first position and the second position; and a processor means adapted to calculate an optimise route between the first position and the second position by calculating an optimise route through a number of sequential points located between the first and second positions said processor further adapted to display on said display means sequential video clips corresponding to the routes between said sequential points.

Generally the system would include video images between each adjacent point. However, it may not always be necessary to provide a video image of every points adjacent every other, since two points may very well be close to each other.

In preference said video clips are stored in a memory, or on storage devices such as a CD-ROM. However, they may also preferably be available from on- line optical devices such as cameras located at desirable locations.

Preferable the system inclues a location means adapted to provide the first position. For example when a user interacts with a display device, the system

will know the location of the display device. Of course the user may very well select a first position located away from the first location.

Preferably the video clips are sequentially spliced to provide a substantially uninterrupted video clip of a route between the first and second positions passing through a number of said points.

Preferably the display means is a television screen with the input means being a keyboard. One could equally well have the input means being an interactive TVscreen.

In preference said system inclues a number of display means. Thus it is envisage that a shopping centre may have a large number of these terminals to assist users.

Preferably the display devices are hand-held display devices allowing a user to e continuously provided with an image as they move around an area. To assist in this, the speed of the video clips may be appropriately varied to keep pace with the user as they are actually moving around.

In preference the system is further provided with an output means to provide an output of the optimise route, such as a printout of a map.

Preferably the system may simultaneously provide not only a video clip of the route but also a map which provide information in time with the video clip.

In a further form of the invention there is propose a method of providing a visual image of a route between a first position and a second position including the steps of; dividing an area into a number of discret points and creating a plurality of continuos video images of a route between adjacent points; choosing a first location and a second location and calculating an optimise route between said locations passing through a plurality of said adjacent discret points; sequentially displaying said video images corresponding to the optimise route passing through adjacent said points between the first and second location to thereby provide a user with a visual route between said first and second position.

BRIEF DESCRIPTION OF THE DRAWINGS FIG 1 is a plan view of a shopping centre layout superimposed on which are discrete points; FIG 2 is a typical example of a display means used to provide information to the user; FIG 3 is an example of a hand-held display means used to provide information to an user; and FIG 4 shows 6 frames from a typical video that the, user may see guiding them from a first to a second location.

DESCRIPTION OF THE PREFERRED EMBODIMENT To further assist in understanding the invention, reference is made by way of example only to the following embodiment.

It is envisage that the invention can be used in a number of applications, such as large shopping centres, airports and buildings, but may equally well be used in vehicles or as a personal display means carried by a user.

As shown in Figure 1 a layout of a shopping centre 10, for example, inclues a number of retail outlets 12 (shaded for easier visualisation) in between which there are walkways 14. The map inclues a grid of points 16, the locations of which are stored in a computer.

To use the system, a user 15 operates a display 16, a typical example of which is seen in Figure 2 and inclues a video screen 30 and controls 32. The display 16 may show a map of the shopping centre, such as that seen in Figure 1, or may allow the user to choose a location to which the user wants to go to, the latter simply accomplished by the user choosing a name of an outlet. Since the navigation system has been pre-programmed with information as to individual grid points within the shopping centre, using known optimisational routing algorithms, the navigation system calculates

what the optimal route between the users location and that which they want to go to, such as a retail shop, may be by. As shown in Figure 1 if a user wants to go from location 18 to location 20, the system calculates route 22. If the user wants to go from location 18 to location 24, the system calculates route 24.

The navigational system inclues a number of video clips, each video clip representative of a route between two individual points. When the system calculates what the optimal route may be, it extracts from memory each video clip representative of a route between two points and sequentially displays them on the display screen for the benefit of the user. Thus what the user in fact sees is an image of a route that a pedestrian may, for example, take from the location of the display means to that retail outlet. Since it is accepte that users will remember visual images much easier than traditional maps, the user can easily find their way to that retail outlet and therefore does not become stresse or lost.

The video clip itself may be played at a speed faster than a person normally would walk that route and thus what may usually take half a minute to a minute to walk may in fact only take 20-30 seconds to display on the display means.

What the user sees is in fact a first person perspective video, representing the view point of someone traversin the route. In addition, there may be displayed alongside the video a map concurrently showing progress along the route.

Thus the navigational system consists of a route finding element and a display element. The route finding element calculates a route as a series of segments with each segment having a corresponding visual video clip whose start and end positions are carefully aligned with those of any other joining segments.

When two adjoining segments are placed sequentially they appear contiguous. The navigation system can therefore display an arbitrary route between any two points as a video clip constructed from a limited number of short clips.

In operation, the system represents the area to be navigated as a graph.

Those points in the graph represent arbitrary locations in an area and contain information on their position in three dimension. Edges in the graph, link those that are conceptually adjacent to each other. That is, if one can walk directly from point or node A to node B without passing any other nodes, then

one can preferably see node B from node A and there is an edge AB between A and B and generally another edge BA from B to A. Edges contain information about the length and direction, that is they are vectors, and can identify an associated video segment showing someone's viewpoint as they walk or travel from A to B. There may also be a short animation segment representing the same process on an overhead map. Routes are represented as ordered lists of edges.

The locations are available as destinations for perusal are nodes in the graph, although there are other intermediate nodes. Having identifie a start node and an end node the navigation system calculates an efficient route by well known artificial intelligent techniques. Briefly these work by having multiple routes being calculated and at each node edges at angles of less than 90° to the direction of the travel are followed. Each one of these is then responsible for the creation of a new potential route which continues to be processed.

When routes reintersect the longer one is culled. A route terminates when it reaches the goal or has no edges in the direction of travel. When all routes have terminated, the shortest route that reaches the goal is selected and others are culled.

The route from start to end is now a list of edges. Each edge is listed and examine for its relevant video segment and animation which are played. As soon as this is finished, the next edge in the list is processed until there are no more edges. The destination is displayed as the final frame of the last video. A typical example of segments of the final visual video as seen by the user can be seen in Figure 4 consisting of 6 frames (a)- (.

It is therefore to be seen that the present system provides for a video clip of a route that a person wishes to traverse. The route may be that located in a shopping centre, airport or other building. It may however also equally be used in a vehicle or any other transportation means where a user may select a final destination that wish to go to.

It is also envisage that a portable display device 34, shown in Figure 3, can be carried by a user and connecte to a central processing unit by electronic communication means, such as mobile phone networks. A user possessing such a display means may choose a location they wish to go to. The display means in itself may contain a location device and thus will transmit this

location to the central system. The central system will then calculate an optimal route between the location of the display means and that which the user wishes to go to and may remotely transmit images to the display means to show the user which route they may have to go to. The resolution and quality of the image would depend upon the speed of the communication and also the necessity of the user.

In applications such as shopping centres and airports, it is envisage that a system would be provided with actual real video clips which may be produced by known filming. As an alternate possibility, a particular area may be drawn up 3-dimensionally using virtual reality methods and not require actual filming to have taken place. This artificial environment creation may assist when one is providing routing on a road, where it is not fundamentally important that particular visual images be represented and one only needs a coarse resolution of the route.

It has been found that providing a visual route to users is much easier to remember and assists the users greatly.

It may also be envisage that these navigational systems may be located in vehicles and may automatically provide route information to drivers by calculating the vehicles position using GPS systems and calculating an optimal route to the drivers destination.

Of course, the display means may not only provide a visual image of the optimise route, it may also display simultaneously a map showing the route to be taken. The map may further be interactive, that is as the video is playing a route marker may be showing the user on the map where the location of that image in fact is.

It is also to be understood that a user may select several locations that they may wish to go to. For example, a user may wish to go to 4 different locations.

The system will then provide the user with a visual map as to what the most efficient way to go to all of the four locations may be. The user may also specify that they may wish to go to a particular outlet first, the system simply calculating the relevant optimal route.

As discussed above, the video clips may be either real-life images or may be

artificially generated. A further alternative may be that a shopping centre and the like may actually have numerus optical devices around an area that may provide current images, with the system using the current images to put together a video clip. This would of course require multiple camera and the image would not be continuous. One possible way to overcome this is to combine current images with stored images to ensure a continuity of data.

Throughout this specification, the intention has been to describe the invention and not to limit it thus and other embodiments may equally well be used without limiting the invention to the particular one represented herein.