HK1209488B - Method of locating a sensor and related apparatus - Google Patents

Description

Method for positioning a sensor and related device

Technical Field

Embodiments of the present invention relate to a method of locating a vehicle or a sensor arranged for use on a vehicle and related apparatus.

Background

As positioning (i.e., determining position) and mapping algorithms mature, the problem of true long-term navigation becomes more and more acute. A common problem in changing environments that require robotic (which in some embodiments may be a vehicle) navigation, and this problem is a major obstacle to achieving lifelong autonomy. Once at the initial visit, it is desirable that this be close enough on the surface to be available for subsequent visits, conventional mapping methods typically produce an initial map, which is typically a monolithic method (as a result of a fusion or averaging, etc. process). In recent years, attempts have been made to solve these problems.

To achieve long-term autonomy, a robotic system should be able to operate in changing environments, which is considered a huge challenge in the art. Variations can come from many sources: sudden structural changes, lighting conditions, time of day, weather, seasonal changes, etc. To illustrate, a camera is mounted on a robot operating outdoors in consideration of the problem of self-motion estimation. This is a rich research mining area, and we have immediate access to a visual navigation (simultaneous localization and mapping-SLAM) system that can map and localize simultaneously. However, when the location is revisited, a large change may occur, and for example, snow may be dropped. As the season changes, from summer to autumn, the appearance of the scene may gradually change. The prior art shows that there is a need to generate a monolithic map containing information that allows localization within a changing environment.

Konolige and Bowman ([1] K.Konolige and J.Bowman, "to wards lighting visual subsystems," in IROS,2009, pp.1156-1163) developed its View-based map system ([2] K.Konolige, J.Bowman, J.D.Chen, P.Mihelich, M.Calonder, V.Lepetit, and P.Fua, "View-basedmaps," International Journal of Robotics Research (IJRR), vol.29, No.10,2010) to accommodate changes in indoor environment. The system generates a keyframe outline from a VO (visual odometry) system. The views stored on the nodes are then updated and deleted according to a scheme designed to preserve view diversity while limiting the maximum number of views. Their profiles are within a single reference frame and are optimized incrementally by Toro ([3] G.Grisetti, C.Stachniss, S.Grzonka, and W.Burgard, "A Tree Pa-normalization for efficient manufacturing Likeloid Maps using Gradient Description," Robotics sciences and Systems, 2007). This shows office results including moving people, furniture, and changing lighting conditions.

The Milford and Wyeth RatSLAM systems ([4] M.Milford and G.Wyeth, "perceptual and mapping using a biological embedded SLAM system," the International Journal of Robotics Research,2009) use the concept of empirical maps that store a large number of experiences. The experience is that in many parts of the world, transition information to other experiences is also stored to solve the ranging bias problem. Over time, the empirical map relaxes to minimize the difference between the absolute empirical position and its transition information to other positions. Experience was also removed to control the density to be lower.

Biber and Duckett ([5] P.Biber and T.Duckett, "Dynamic maps for Long-term-displacement of mobile service robots," in Proceedings of Robotics: Science and systems, Cambridge, USA, June 2005) sample the laser map through a series of time scales to produce a single map with long-term and short-term structure. This allows them to shape short-term dynamic objects as well as long-term structural changes. They show improved positioning accuracy over several weeks with busy laboratory environments.

Attention is also directed to the work of fusion and Barfoot ([6] p.fusion and t.d.barfoot, "visual and repeat for long-range rotation autonomy," Journal of Field Robotics, vol.27, No.5, pp.534-560,2010), which developed teaching and repeating systems for using vision in outdoor environments. In the teaching phase, the robot generates a series of sub-images using the VO. The positioning module is then used to retrace the original path. They showed results in excess of several kilometers.

However, none of the above techniques satisfactorily address the changing environment that may be experienced as the sensor (or vehicle carrying the sensor) moves through the environment.

Disclosure of Invention

According to a first aspect of the present invention there is provided a method of locating a vehicle carrying a sensor, comprising at least one of the following steps:

a) acquiring data from a sensor at a current time, the sensor providing a sensed scene around a vehicle;

b) processing the sensed scene, where the processing determines a location of the vehicle from the sensed scene in relation to a position of the sensor at an earlier time;

c) comparing the sensed scene with one or more stored experiences to determine whether the sensed scene is identifiable within any or each stored experience;

d) if the sensed scene is identified in the stored experience, using the stored experience to generate an estimate of the position of the vehicle at the current time relative to the stored experience;

e) repeating at least some of steps a through d.

Embodiments that provide such a method are believed advantageous because they can allow for easier positioning of the vehicle in changing environments than prior art systems. Moreover, such an implementation means that only data relating to the sensed scene needs to be stored if needed, and such a strategy helps to reduce the amount of storage required and the amount of processing that may be required to process the stored data. Also, embodiments of the present invention may be more accurate, require less memory than expected, and be faster than the prior art.

The term locating the vehicle is intended to mean determining the location of the vehicle from the data generated by the sensors relative to an earlier time. Localization is taking data from sensors, processing the data while having a prior representation of the scene (usually provided by a map or in some embodiments by stored experience), and proposing a parameterization of the vehicle pose (position) with respect to the prior representation. Generally, in embodiments of the present invention, the prior representation is provided by a plurality of stored experiences.

Conveniently, the method is arranged such that if the sensed scene is not identified within more than a predetermined number of stored experiences, the method stores the sensed scene so that the sensed scene becomes part of the newly stored experience for future comparison. This embodiment is considered advantageous by one's own experience. As the vehicle senses more scenes, the amount of stored experience the vehicle may use in the future may increase.

The method used by embodiments of the present invention notes that features on a given tree in winter are not simply features that were written down on the same tree in summer; the detail seen on wet road surfaces at midday is different from the detail seen at dawn when the road surfaces are dry. Embodiments of the present invention do not attempt to make things consistent. For example, if the environment on tuesday is completely different from the environment on wednesday, then embodiments may consider it to be two separate experiences that also capture the essence of the environment. The implementation only binds them together topologically. Some embodiments may then connect the stored experience through the locality concept discussed below.

Embodiments of the present invention may save a series of visual features (typically provided by data generated from sensors) as a new experience when a new area initially sees the vehicle.

However, as the sensor/vehicle moves, embodiments of the present invention are arranged to attempt to locate the sensed scene within any saved experience. Also, upon revisiting the area, the sensor/vehicle attempts to locate in any saved experience using a real-time data stream (which may be an image). In some embodiments, the method may be arranged such that the stored experiences are generated by the vehicle/sensor using those experiences.

However, in other embodiments, the stored experiences may be used by vehicles/sensors other than the vehicle/sensor that generated the experiences. This may be used by the vehicle and/or sensors in addition to the vehicle/sensors that generated the experiences. Such an implementation is considered a centralized experience, allowing multiple vehicles to utilize the stored experience. Such a method may be advantageous because it allows data to be established and/or shared by multiple vehicles.

It may also be arranged to attempt to relocate in its previously stored experience (i.e. identify the sensed scene within the stored experience) while the vehicle continues while still preserving this new experience. If the relocation succeeds at any point, the saving of the new experience may be stopped and the method returns to the location in its previous experience.

Such an approach typically causes embodiments to store more representations for frequently changing sensed scenes and less representations for more fixed sensed scenes.

Thus, embodiments may seamlessly process new routes and fully locate faults. In practice, it is often a fault that drives the localization of the saved new experience. Also, a localization failure may be considered to be caused by a poor or unresolved data association, a previously existing data association now not existing at all.

In contrast to prior methods of the prior art, some embodiments may simply store new experience when the current stored experience is insufficient. Therefore, this method should produce every stored experience that represents a different visual pattern, and therefore, deletion is not a problem. Embodiments may allow for every experience within their own frame of reference, as this approach may allow for positioning in parallel and allow for multiple experiences to be used at any time. This also allows different visual modes, which may be significantly different, to represent the same physical space.

In some embodiments, the data of the sensor may be part of a data stream.

In one embodiment, the sensor is a pair of stereo cameras. Thus, the output of the sensor of such an embodiment may be a series of images and may be a plurality of pairs of images.

The method may perform initial processing on the output of a sensor that may identify common features between pairs of images generated by a stereo camera. The initial process may generate a 3D model of the location of the vehicle. Thus, some embodiments may extract feature sets from the sensed scene and use those extracted features to determine the location of the sensor, or the vehicle, or robot, etc. on which the sensor is mounted.

The 3D model may provide experience that may be referenced later. In some implementations, experience can be provided by a plurality of feature sets, wherein each feature set is extracted from a defined sensed scene. In general, embodiments cause the sensors to generate continuous 3D features (i.e., points within the data) relative to the trajectory of the vehicle. Thus, a trajectory can be viewed as a series of points at various moments in time connected with a stereo pair, a relative pose (image pair) at a previous point in time, and a number of 3D features.

The method may be arranged to analyse the data of the sensor to determine 3D features (which may also be referred to as points or nodes) within the sensed scene and further to concatenate those 3D features within the image at a first time (or other representation of the sensed scene generated by the sensor) with subsequent images at a second later time using the conversion. The connection may provide a track for the sensor and/or the vehicle.

The method may be arranged to determine landmarks within the image. A landmark may be a structure identifiable within the data of a sensor and generally corresponds to a real-world object. For example, the landmark may correspond to a corner of a building, a tree, and so on.

In some embodiments of the invention, the method may be arranged to generate a position of a landmark relative to a sensor and/or a vehicle. In embodiments where the sensor is a stereo camera, the position of the landmark can be determined using the information of the two images.

In general, the method may locate multiple landmarks within any one sensed scene.

In other embodiments, the sensor may have a laser sensor, radar, lidar (light detection and ranging), 3D strobe, Microsoft^TMKinect^TMAnd the like.

The method may utilize the coarse location of the sensor (or the vehicle on which the sensor is mounted) to substantially determine the location of the sensor. In particular, embodiments of the present invention may use a Global Positioning System (GPS), one or more accelerometers or other such ranging systems, or the like, to identify the location of the vehicle.

Embodiments may use the location of the sensor (or the vehicle on which the sensor is mounted) to determine which stored experience should be considered to determine whether the sensed scene can be identified within. Likewise, the location of the sensor using the coarse position may be considered as using a circuit closer.

In addition to or instead of using coarse locations, other embodiments may use image matching techniques to determine stored experiences that are visually similar to the sensed scene. This embodiment is considered advantageous because visually similar stored experience may provide good candidates for providing a match for the sensed scene.

The method may be arranged to run in parallel so that the method attempts to identify the sensed scene within a plurality of stored experiences at any one time. This can be viewed as running multiple locators at any time. In addition to identifying the sensed scene within the stored experience, the method may also calculate transitions from nodes located within the sensed scene to those nodes within the stored experience.

The method requires that the sensed scene be identifiable within a predetermined plurality of stored experiences before it is determined that the vehicle has been located. It is believed that one embodiment of providing such a step provides a greater degree of certainty that the vehicle has actually been correctly positioned.

The method may be arranged to determine whether stored experiences are associated with each other with similar locations. If it is determined that the stored experience is a similar place, then the implementation may be linked to such stored experience. Embodiments that connect with stored experience to form such a place are considered advantageous because the place can be used to assist in identifying the sensed scene within the stored experience.

The stored experience may include any of the following: raw data output from the sensor; the approximate location of the vehicle, the time of day, the date, the weather conditions, the nodes determined within the output of the sensor, the generated 3D image of the location of the vehicle.

According to a second aspect of the present invention, there is provided a system arranged to locate a vehicle, the system comprising: a sensor configured to generate data representative of a sensed scene surrounding a vehicle at a current time; processing circuitry arranged to process data, wherein the processing may be arranged to perform at least one of:

determining a location of a vehicle from the data relative to a position of the sensor at an earlier time;

comparing the data to one or more stored experiences maintained within a storage device to ascertain whether the sensed scene is identifiable within any stored experiences; and

if the data allows the sensed scene to be identified in any stored experience, the location of the vehicle is estimated using the stored experience.

The storage device may be provided by any suitable form of device, such as a hard disk drive, a series of hard disk drives, etc. In practice, the storage means may be distributed.

In some embodiments, at least a portion of the storage device may be mounted on a vehicle. In other embodiments, at least a portion of the storage device may be mounted external to the vehicle and configured to be accessible from the vehicle.

The system may include a server configured to communicate with processing circuitry on the vehicle. The server may be arranged to communicate with the processing circuitry over any suitable network, which may include the internet and/or a wireless telecommunications network, e.g. 3G, 4G, WIFI, etc.

The processing circuitry may be arranged to compare said data with a subset of available stored experiences. In some embodiments, the processing circuitry may be arranged to obtain from the remote storage device a subset of the available stored experience that may be held locally on a storage device located on the vehicle.

According to a third aspect of the present invention, there is provided a vehicle having a sensor mounted thereon, wherein the sensor is arranged to generate data representative of a sensed scene surrounding the vehicle at a current time; and processing circuitry arranged to process data, wherein the processing circuitry is arranged to perform at least one of:

determining a location of a vehicle from the data relative to a position of the sensor at an earlier time;

comparing the data to one or more stored experiences to ascertain whether the sensed scene is identifiable within any stored experiences; and

if the data allows the sensed scene to be identified in any stored experience, the location of the vehicle is estimated using the stored experience.

According to a fourth aspect of the present invention there is provided a server arranged to receive a network request from a network for one or more stored experiences, the server being arranged to process the request to retrieve a requested stored experience from a storage device and to transmit the requested stored experience over the network.

According to a fifth aspect of the invention there is provided a machine-readable medium containing instructions which, when read by a machine, cause the machine to perform the method of the first aspect of the invention, at least part of the system of the second aspect of the invention or the processing circuitry of the vehicle of the third aspect of the system.

The machine readable medium referred to in any of the above aspects of the invention may be any of the following: CDROM, DVDROM/RAM (including-R/-RW or + R/+ RW), hard disk drive, memory (including USB drive, SD card, flash memory card, etc.), transmitted signals (including internet download, ftp file transfer, etc.), wiring, etc.

Features described with respect to any of the above aspects of the invention may be applicable to any other aspect of the invention.

Drawings

Embodiments of the invention will now be described in detail, by way of example only, in which:

FIG. 1 is a schematic view of a vehicle utilizing one embodiment of the vehicle to position the vehicle relative to the location of the vehicle;

FIG. 2 is a series of photographs showing how the location of a vehicle may change over time and/or the weather experienced by the location;

FIG. 3 schematically illustrates a method according to an embodiment of the invention;

FIG. 4 schematically shows the output of a visual ranging system, for example as used in the vehicle of FIG. 1;

FIG. 5 schematically shows the manner in which data relating to a venue may be updated;

FIG. 6 provides further illustration of a scenario in which the places change frequently (a and b) or are relatively constant (c and d);

FIG. 7 shows a plurality of experiences generated and stored from a plurality of trips around the trace shown in the figure;

FIG. 8 shows the manner how sensed scenarios may be added to stored experience for traversing a test line;

FIG. 9 shows weather statistics for a trip used to generate the results of FIGS. 7 and 8;

FIG. 10 shows the effect of rearranging data on the experience of how to store a currently sensed scene as stored;

FIG. 11 shows the effect of weather on how sensed scenes are stored as stored experience;

FIG. 12 shows an example of locating a fault during a first pass around the trace of FIG. 7;

FIG. 13 shows an example of locating a fault during a second pass around the trace of FIG. 7;

FIG. 14 shows the time performance of the processing circuit of the vehicle shown in FIG. 1 during a third pass around the tracking of FIG. 7;

FIG. 15 is a flowchart outlining one example embodiment; and

fig. 16 shows another distributed embodiment of the invention.

Detailed Description

Embodiments of the present invention are described with respect to sensor 100 mounted on vehicle 102 and with respect to the flowchart of fig. 15. The sensor 100 is arranged to monitor its location and to generate data from the monitoring, thereby providing data about a sensed scene located around the vehicle 1500. In the depicted embodiment, then, since the sensor is mounted on the vehicle 102, the sensor 100 is also arranged to monitor the location of the vehicle.

In the described embodiment, the sensor 100 is a passive sensor (i.e. does not generate radiation and only senses radiation), in particular a stereo camera; including two cameras 104, 106. The skilled person will appreciate that such a sensor may be provided by two separate cameras.

In other embodiments, the sensor 100 may comprise other forms of sensors, such as a laser scanner, or the like. Also, the sensor 100 may be an active sensor configured to emit radiation therefrom and to sense reflected radiation.

In the embodiment shown in fig. 1, vehicle 102 is traveling along road 108 and sensor 100 images the location (i.e., building 110, road 108, etc.) as vehicle 102 travels. In this embodiment, the vehicle 102 also includes a processing circuit 112 configured to obtain data from the sensors and then process the data (in this case, the images) generated by the sensors 100. Thus, the processing circuitry obtains data from the sensors 100 that provides a sensed scene from around the vehicle at the current time. In the depicted embodiment, the processing circuit 112 also includes or accesses a storage device 114 located on the vehicle.

The lower portion of the diagram shows components that may be found within a typical processing circuit 112. A processing unit 118, which may beX86 processors, e.g., 15, 17 processors, etc. Processing unit 118 is placed in communication with an I/O subsystem 122 (and thus an external network, display, etc.) and memory 124 via a system bus 120.

The skilled artisan will appreciate that the memory 124 may be provided by various elements, including volatile memory, hard drives, non-volatile memory, and the like. In practice, memory 124 comprises a plurality of elements under the control of processing unit 118.

In general, however, memory 124 provides: a program storage portion 126 configured to store program code that, when executed, performs an action; and a data storage portion 128 that may be used to store data temporarily and/or permanently.

In other embodiments, at least a portion of the processing circuitry 112 may be provided remotely from the vehicle. Likewise, it is envisioned that the processing of the data generated by the sensors 100 may be performed outside the vehicle 102 or partially on the vehicle 102 and partially outside the vehicle. In embodiments where the processing circuitry is provided on-board the vehicle as well as off-board the network connection (e.g. 3G UMTS (universal mobile telecommunications system) or WiFi (IEEE 802.11), etc.) is made.

Reference is conveniently made to vehicles travelling along a roadway, but the skilled person will appreciate that embodiments of the invention need not be limited to land vehicles, and may be water borne vessels (e.g. ships, boats, etc.) or indeed air borne aircraft (e.g. airplanes, etc.). Also, in the following description, reference is made to image data generated by the cameras 104, 106 as a matter of convenience, but other embodiments of the invention may generate other types of data.

The sensor 100, together with processing circuitry 112 connected to the sensor 100 and software running on the processing circuitry 112, form an object commonly referred to as a Visual Odometry (VO) system. In the described embodiment, a Visual Odometry (VO) system continuously produces a world of (possibly transient) 3D models using data generated from cameras (104, 106). Typically, the VO system locates a feature (which may be referred to as a node or point) within each image of a camera pair that may be located within both images. These features are then tracked between subsequent images (i.e., between the first or earlier time and the second (possibly current) time) to generate the trajectory of the vehicle 102.

This arrangement of cameras may be referred to as a stereo pair. In the described embodiment, while the vehicle 102 is running, the VO system is always on, always using the real-time data streams (i.e., images) of the cameras (104, 106) and estimating the relative transitions (i.e., camera poses) between the images generated from the two cameras 104, 106 to generate trajectories and produce the positions of features relative to those camera poses. The stereoscopic nature of the camera allows the 3D position of the feature to be calculated relative to the camera.

Generating a set of multiple feature locations as the sensor 100/vehicle 102 moves; that is, a feature set is generated from each scene. Multiple sets of positions may be referred to as an experience. The processing circuitry 112 may be arranged to store at least one of the following metadata of the experience: data generated from the sensor 100 (in this embodiment, images of two cameras); features (i.e., 3D feature locations); time and/or date; weather; location (via global positioning system GPS, etc.); a degree of brightness; traffic level, cloud cover, sensor type, etc.

Thus, as the vehicle 102 moves, the experience is stored as a set of relative poses and feature (i.e., node) positions. It should be noted that this is a stored set of relative gestures. Embodiments of the present invention generally operate without a single global frame. Embodiments of the present invention propose the concept of correct measurements of camera motion and 3D feature positions in the vicinity of the current pose of the sensor 100. Embodiments of the present invention do not require determining the location of an object that is remote from the sensor and cannot be sensed (i.e., in this case, cannot be seen) by the sensor 100. As described later herein, when the vehicle 102 revisits an area, an attempt is made to locate in a previous (stored) experience associated with the area; such positioning is considered to attempt to determine the position of the vehicle 102 from the sensed scene in relation to the position of the sensor at an earlier time, where the position of the sensor at the earlier time is provided by the or each stored experience. In this context, locating may be considered to identify the sensed scene provided by the sensor 100 at the current time within at least one stored experience of providing the location of the sensor at an earlier time.

Also, and over time, the vehicle 102 moves around a stored set of experiences, each experience being independent of the other. A locator may be associated with each stored experience and may be configured to try and identify the sensed scene within its stored experience. In other embodiments, the locator may be configured to handle multiple stored experiences.

Embodiments of the present invention are configured to process stored experiences to try and identify the current location of the vehicle 102/sensor 100 within those previously stored experiences; that is, the embodiment may compare the sensed scene to the stored scene when attempting to locate the vehicle 102 (step 1506). Likewise, embodiments may be considered to include the comparator 134 (i.e., the locator). By locating, this means that the processing circuitry 112 can determine whether the current real-time image can successfully match the previous (stored) experience. This positioning is performed by a positioner 130 running on the processing circuitry 112 and can be performed by keeping previously stored experiences separate.

Embodiments of the present invention may also be arranged to determine landmarks within the sensed scene, which landmarks typically correspond to real world objects, such as corners of buildings and the like. If a landmark is identified within the sensed scene, a location of the landmark relative to the vehicle is determined. In this embodiment, this is done by geometric calculations, since the stereo camera pair provides two images within which landmarks can be found, providing sufficient information to determine the location of the landmarks relative to the sensor. When a landmark is generated, a piece of data is stored. In the described embodiment, this is pixel data, and in one example, a 9x9 grid of pixels is stored. Some embodiments may store any identified landmarks and/or pieces of data as part of the stored experience.

To match the sensed scene with the stored experience, some embodiments attempt to locate landmarks located within the sensed scene that were found within the stored experience. This goal is attempted by locating pieces of data (in this case, pixels of a 9x9 grid) associated with landmarks in the stored scene by those landmarks found in the sensed scene. In the described embodiment, the locator is associated with stored experience and looks for pieces of data associated with landmarks within the stored experience (associated with that experience in the sensed scenario).

Some embodiments may perform advanced data slice matching so that suitable candidate data slices can be quickly located and then compared in more detail to identify whether a match is actually deemed to have occurred.

The positioning in the previous experience can be done in parallel and allow the system to take advantage of the relevant previous experience. In practice, at run-time, people often find the number of active and successful positioning experiences to be small. As described below, generally, each new experience is only generated (in the described embodiment, this means that the images generated by the cameras 104, 106 cannot be matched with 2 or more stored experiences and cannot be located) since the data can only be matched in less than a predetermined number (N) of stored experiences. Consequently, subsequent access to an area should be able to locate it only within a small amount of stored experience, since its structure is visually different. Thus, if the method determines that the sensed scenes do not match in sufficient experience (i.e., more than a predetermined number) and thus positioning cannot be performed, then the sensed scenes are typically stored as newly stored experience, which may be used for future comparisons, step 1508.

Thus, embodiments of the present invention provide a framework for long-term navigation in varying environments. As briefly described above, the vehicle 102 continuously generates a 3D model of the environment from a VO system that takes as its input a real-time image stream from the sensors 100. At the same time, the processing circuitry 112 of the vehicle 102 opportunistically attempts to locate the current position in the previously stored experience.

If the location is successful in previous experience, then the embodiment assumes that the current location is adequately represented and is then able to generate an estimate of the vehicle position at the current time relative to the stored scene. However, if no fix can be made in the previous experience, a new experience is generated by saving the output of the VO system.

Experience is represented by ε, and the jth experience is represented as^jEpsilon. Thus, this set of all experiences produces a map, conveniently referred to as a plastic map. The map is provided by equation (1).

In general, embodiments of the present invention rely on local navigation and the ability to "close the loop"; it will be appreciated when the vehicle 102/sensor 100 has returned to a previously visited location (previously stored experience).

Techniques for local navigation are shown in various papers that provide trajectory estimation systems. In particular, techniques using laser scanners are discussed below:

[7]M.Bosse and R.Zlot,"Map Matching and Data Association for Large-Scale Two-dimensional Laser Scan-based SLAM,"International Journal ofRobotics Research,vol.27,pp.667-691,2008

techniques for trajectory estimation using a vision system are shown in the paper:

[8]D.Nister,O.Naroditsky,and J.Bergen,"Visual Odometry for GroundVehicle Applications,"Journal of Field Robotics,vol.23,2006

[9]C.Mei,G.Sibley,M.Cummins,P.Newman,and I.Reid,"Real:A system forlarge-scale mapping in constant-time using stereo,"International Journal ofComputer Vision,pp.1-17,2010,special issue of BMVC

the contents of these papers are hereby incorporated by reference herein, and the skilled artisan will focus on reading and understanding these papers, particularly with reference to the manner in which the trajectory of a vehicle of a VO system can be determined.

In the following discussion, further loop closing techniques are taught that can be used to determine whether current sensor data has been experienced in a previous experience with respect to the vision system:

[10]M.Cummins and P.Newman,"Highly Scalable Appearance-Only SLAM FAB-MAP2.0,"in Robotics Science and Systems,2009

moreover, the contents of this paper are hereby incorporated by reference, and the skilled artisan focuses on reading and understanding these papers, particularly with reference to a loop closure system that implements a VO system. Such systems typically attempt to locate images within stored experience (i.e., provide image matching techniques) that is visually similar to the experience of the sensed scene. Likewise, the fabmac can be considered a loop closer that can be used to trigger a locator associated with stored experience in order to try and locate the stored experience with the sensed scenario.

The skilled person will also appreciate that a Global Positioning System (GPS) may be utilised, which is capable of providing a position with an accuracy of a few metres. Thus, embodiments of the present invention may use the output of the GPS system 116 or other similar system to provide a coarse or approximate location. The output of the GPS system 116 is typically connected to processing circuitry to allow the processing circuitry to identify the approximate location of the vehicle 102. The term approximate location is intended to convey a relatively imprecise meaning compared to the positioning available using processing of the data of the sensor 100.

However, embodiments of the present invention, using the output of sensor 100, are able to determine that vehicle 102 is moving about a few millimeters or at least a few centimeters relative to previously stored experience.

Thus, as broadly described above, the VO system is in a series of stereoscopic framesThe above operations are performed.

At time k, the stereo frame is processed, and camera node n_kAnd node n_k-1Transforming t by 6 degrees of freedom_k＝[x，y，z，θ_r，θ_p，θ_q]^TConnections where thetar, thetap, and thetaq are roll, pitch, and yaw, respectively. Thus, node n_k-1Can be considered to occur at a first time, and node n_kMay be considered to occur at a second, subsequent time. Likewise, processing circuit 112 identifies nodes within second scenario 1502. These nodes may be tracked over a series of frames, as described below, to generate the trajectory of vehicle 1504. Embodiments may be viewed as including a node locator to perform this function' 132.

If the new 3D landmark is initialized toThen these landmarks are also connected to camera node n_k. Will be connected to n_kIs represented as l, where i is a global index (so that each landmark has a unique ID))_i，k＝[x，y，z]^TThis is the vector within the camera frame at time k. Camera node n_kIs also arranged to be included inA series of all landmarks observed within, many landmarks connected to other nodes, i.e., the node that initialized the landmark.

Also, by passing through^p∏_qThe operation represented will be_*，pIs converted into_*，qA landmark depicted within frame p may be concatenated with a different frame q to:

l_*，q←^p∏_q(l_*，p) (2)

in the depicted embodiment, the VO system runs continuously on the real-time frame stream (i.e., data) generated by the cameras 104, 106. If a new experience is generated (see discussion below regarding the time at which this occurs), then a new experience is generated^jε, and the output of the VO system is stored in this new experience. Then, the user can use the device to perform the operation,^jε may thus be only the camera node n_kChains, inter-node transformations, and associated 3D features. Nodes in experience are called^jε_m.. Later, the manner in which these chains are related (topologically) is explained to consistently form the plastic map.

Thus, fig. 4 shows the way in which an experience is constructed from the series of frames represented by node n. Each frame of the output of the VO system (represented by a circle) is denoted from n_k-2From n to n_kTo n_k+1(ii) a Current frame n_kBy the number 40And 0 represents. Each node n is described inAndthe 6 degrees of freedom of camera motion between.

Also, a series of landmarks 402, 404, 406, 408 are represented by the location of the vehicle 102 within the current frame. Each of these landmarks 402 and 408 may be transformed such that these landmarks use equation 2 above with respect to k.

As broadly described above, the locator is used to try and locate the current position of the vehicle 102 within previous experience. In a broad sense, this may be considered as identifying the sensed scene within previous experience (which may be stored experience). More than one positioner may be provided and the or each positioner is run on top of previous experience (i.e. stored experience). Such as fruit time frames ofThe task of the or each locator is to compute the slave frameTo node n in previous experience.

The locator may operate in a similar manner as the real-time VO system, except that the set of proposed landmarks comes from a saved experience rather than a previous frameAnd (c) other than. Landmarks are extracted empirically from local regions surrounding previous locations. Furthermore, in the described embodiment, the locator does not attempt to add or update landmarks in the current VO output or previous experience. Fully passive in its impact on current VO output and previous experience; i.e., the current VO output or previously experienced data is not modified.

PositioningThe device is set to know if "lost"; i.e. locating the input frame no longer in previous experienceThere are a number of ways to perform the calculation. The likelihood includes the number of landmarks found and/or classified as inliers and a comparison to the current VO output. The output of each locator at each time step is a binary result indicating whether the location was still successful:

if successful, the locator can be queried for querying empiricallyThe closest node.

Once loss of the locator is declared, it stays in this state until external assistance is received, discussed below, and again closes the circuit through previous experience.

N is defined as the minimum acceptable number of successful locators at any time (i.e., successful attempts to determine the current position within previous experience or in other terms, N being a predetermined minimum number of stored experiences in which the sensed scene should be identified before a fix is deemed to have occurred). For each frameThe set of activity experiences a is calculated. For each experience in A, its associated locator runs, the result is a binary vector S that indicates the success or failure of each experience. If | S | is lower than N, then a new experience is generated^jEpsilon, and save VO inputAnd out until | S | returns greater than or equal to N. The procedure is described by algorithm 1.

Likewise, if the sensed scene can be located in more than N stored scenes, the position of the vehicle 102 can be determined relative to those stored experiences, step 1512.

Referring to fig. 3, the algorithm may be interpreted and in the top region of fig. 3, different 'time points' are displayed, wherein each time point represents a set of frames of the output of the VO system at three different timesIn this embodiment, the minimum number of successful locators (N) has been set to 2.

For each time point A, on the left side of the figure, each frame has been labeled F_k-2From F_kTo F_k+3. Each of the other time points (B and C) may be labeled the same, but have not been labeled for clarity.

Under each frame of time points a to C, there are three representations: the top row of circles represents the current output of the VO system; the circles in the middle second row represent data stored in experience 1; and the bottom third row of circles represents the data stored in experience 2.

In time point a, it can be seen that the image produced by the sensor is a combination of two different trends of data that can be seen as black/gray 300 and a solid horizontal line 302. Looking at experience 1, it can be seen that there is a 'horizontal' solid line trend in the data, and as such, the localizer is able to locate the current image through experience 1. Looking at experience 2, it can be seen that there is a 'black/gray' trend in the data, and as such, the localizer is able to locate the current image through experience 2. Note that N-2, no new experience needs to be generated now because the localization has been done in the minimum number and the VO output can only be forgotten.

Moving to time point B, it can be seen that the image produced by the sensor is a combination of two different trends that can be seen as data for black/gray 300 and the solid horizontal line 304. Looking at experience 1, the horizontal solid line 302 trend cannot be located in the current image. However, looking at experience 2, it can be seen that there is a black/gray trend as in the current data, and as such, the localizer is still able to locate the current data within experience 2. However, since N is set to 2 and only a single fix has occurred, the output of the VO system is now stored as a new experience 306.

Then, moving on to point in time C, the trend in the current image returns to black/gray and the solid horizontal line, which can be positioned in experience 1 and experience 2. Likewise, the output of the VO system may be forgotten again.

The skilled person will appreciate that even if greater than N is located, embodiments may store the VO output, but it may be advantageous not to do so. Storing data unnecessarily, results in greater data accumulation and may reduce the performance of the system.

Thus, in addition to obtaining different appearances of the same region, the plastic map (identified in equation (1)) also stores a lot of experience covering an infinite space region, and therefore, experience is not all time dependent; that is, the VO system may output information for different spatial regions and/or different visual appearances. All experience does not derive the spatial position of the vehicle in its environment. Therefore, it is best to calculate which experiences apply toExperience is not stored in a single reference frame and therefore, local transformations cannot be integrated to estimate different positions.

To overcome the inability to estimate the position in different frames, the concept of locations that produce topological connections between experiences is introduced. The location is denoted as P, anAnd the z-th site is denoted as P^z。

P^z＝{^jε_mIs the set of all nodes (obtained from different experience) known to be located at the same time. Thus, P^zIs a set of camera frames looking at the physical location.

Simultaneous localization in more than one experienceThen a place is created. By querying each successful locator for each of its nearest nodes, the leaf can be panned through a set^jε_m}_kA place is created. However, it is also possible to have a previously created place contain some of these nodes, in which case the slave is mergedThe created collection and the previous location.

Wherein, according toWhether the node generated in (1) is in the previous place, P on the right-hand side^zPossibly an empty set. A simple example of venue creation and merging is shown in fig. 5 and is also explained with reference to fig. 3.

Referring first to fig. 3, it can be seen that in effect 3, there is experience represented in the figure: experience represented by the horizontal solid line; experience represented by black/gray; and experience indicated by the horizontal dashed line. Fig. 5 also shows 3 experiences: experiences 1, 2 and 3, represented by black, gray and white, respectively.

Fig. 5 shows a previous frame F_previousThe frame can be located in experience 1 and experience 2 to generate the locationA. However, in the current frame FK, it can be located in the experiences 2 and 3, thereby generating the location B. Thus, it can be concluded that sites a and B actually represent the same site (since experience 2 is included in both sites), and that, as such, sites a and B can be merged to create site C.

Thus, referring again to FIG. 3, it can be concluded that since experience 2 is shared by all three time points A through C, all three experiences represented therein (experience 1; experience 2 and the experience stored from VO in time point B) all actually represent the same place.

Thus, and as discussed with reference to fig. 3, a site may be used for a connection experience. The following capabilities were used: all sites are queried by a set of empirical nodes and the set of sites containing the nodes is received. The query is defined by Ω.

1) Calculating related experience: as described above, since the stored experience does not necessarily cover the current position of the vehicle, it is possible to do so with a vehicle having a vehicle with a vehicle speed that is higher than the current speed of the vehicleNot all stored experiences are relevant. Thus, embodiments allow the positioner to assume two states, namely an active and an inactive state. In the process ofThe set of successful locator positions of the previous frame^jε_m}_k-1For generating the set of relevant places:

then, each inactive locator queryQueries for the presence of its own node and, if any, activates itself at the retrieved location. When the vehicle 102 moves beyond an empirical range (i.e., the locator is lost, as described in fig. 3), the associated locator sets itself inactive.

2) Reinitializing the missing locators: since the current frame is no longer trackedThe positioner is lost, however, this may only be a temporary state and the positioner is able to reposition itself within experience. Also, after the locator is initially lost, the locator/experience may be correlated for a moment again, and thus, embodiments attempt to reinitialize the lost locator. The failure to reinitialize the missing locators when possible may cause the system to save more experience than necessary, with the associated problems of increased storage requirements for data and reduced processing performance due to the additional data.

Likewise, embodiments of the present invention may evaluate whether a location is another experience of passing locations if it has a known location in one experience. Thus, some embodiments may be provided where missing locators are periodically queriedSee if reinitialization is possible.

Sometimes, all the positioning process is lost, at which point the system does not know where in the plastic map. This may be because the current location has changed substantially (e.g., snowing), or because the vehicle 102 is detecting a new route. For whatever reason, the VO system continues to process the real-time frame (data) stream and saves the output into a new experience, as described in fig. 2 with respect to time point B. However, the vehicle 102 may then return to a location where it can be successfully located and again obtain its position in the plastic map; that is, the vehicle 102 can again be located in a number of experiences greater than N. For a solution to this problem, which should become less and less by repeated crossings, an external loop closer is used which can reinitialize the missing locator.

In discussing vehicles rejoining a previously explored route from a new route, in fig. 7 discussed below, the external circuit is emphasized as closed.

However, in some embodiments, a system such as GPS may be used to provide the approximate location of the vehicle 102. In such embodiments, the processing circuitry may use the approximate location of the vehicle to emphasize which stored experiences are promising candidates to consider locating the vehicle therethrough. Likewise, the approximate location of the vehicle 102 may be used to help identify which stored experience may be used to locate the vehicle 102, i.e., step 1510. Embodiments may be considered to include a circuit closer 136.

In the embodiments of the present invention, the following is generally the case: once the set of correlated locators has been computed, each locator becomes independent and, therefore, can be run in parallel. If the data association (i.e., matching landmarks from stored experience to each stereo camera frame of the sensed scene) and the trajectory estimation step (i.e., determining the change in the pose of the vehicle between the current and previous frames) control the computation time, then by paralleling them, embodiments are currently able to process frames with 15 Hz. The skilled person will appreciate that if further processing power is added, the frequency at which data can be processed increases.

Although the skilled person will understand the way in which the system capable of processing and generating trajectories from a large amount of sensor data is implemented, the following paper is used as a reference. These papers are incorporated herein by reference, and the skilled artisan is focused on reading the relevant portions of these papers.

To achieve robust data association, embodiments of the present invention may use binary robust independent primitive feature (BRIEF) descriptors.

[11]M.Calonder,V.Lepetit,C.Strecha,and P.Fua,"BRIEF:Binary RobustIndependent Elementary Features,"in European Conference on Computer Vision,September 2010

The BRIEF descriptor feature is computed and matched quickly using only the CPU of the processing circuit 112, and is able to provide comparable performance to SURF [12].

[12]H.Bay,A.Ess,T.Tuytelaars,and L.V.Goo,"Surf:Speeded up robustfeatures,"Computer Vision and Image Understanding(CVIU),vol.110,pp.346-359,2008

Embodiments of the invention may use a GPU (graphics processing unit), may utilize SURF and like descriptor implementations and allow for frame rate capability:

[13]N.Cornells and L.V.Gool,"Fast Scale Invariant Feature Detectionand Matching on Programmable Graphics Hardware,"in Computer Vision andPattern Recognition,2008

however, the matching step in each locator and real-time VO system requires access to the GPU (feature extraction on input frames is independent and can be done once at the start). Since most systems have at most only one GPU, the usage requirements of the GPUs are difficult to parallelize compared to running CPU-only programs on multi-core or multi-process systems. Also, embodiments tend to use GPU-based approaches.

Embodiments may use a fast corner extractor to compute points of interest for BRIEF:

[14]E.Rosten,G.Reitmayr,and T.Drummond,"Real-time video annotationsfor augmented reality,"in Advances in Visual Computing.LNCS3840,December2005,pp.294-302

in some embodiments, the matched landmarks can be improved to sub-pixel accuracy using efficient second order matching, Mei describes:

[15]C.Mei,S.Benhimane,E.Malis,and P.Rives,"Efficient homography-basedtracking and 3-d reconstruction for single-viewpoint sensors,"IEEETransactions on Robotics,vol.24,no.6,pp.1352-1364,Dec.2008

data was collected from 53 crossings of two half-overlapping 0.7km routes around the begbrooke Science Park. Data over a period of three months were collected at different times of day and by different weather conditions using the team's survey vehicle, Wildcat.

Fig. 7 shows the overhead of the field and two routes of travel for the vehicle, e.g., vehicle 102. The outer loop 700, represented by the bold line, is driven on the first 47 crossings, while the last 6 crossings pass through the inner loop 702, represented by the thinner line. The intensity of the plot indicates how much experience is plotted at each point, and a scale is shown on the right side of the plot. To illustrate, the signal of the outer loop shutoff is controlled, thus targeting only 14 predefined points on each loop. The points are substantially evenly spaced along each loop. Also, if the locator is lost, it can be relocated at these 14 predefined points. The skilled person will appreciate that other embodiments may achieve this goal differently, possibly randomly, substantially continuously, at predetermined time intervals, etc.

Some areas of the route require more experience than others. In fig. 6, examples of locations showing high and low visual changes are shown. An example of an area with high visual variance is a parking lot, fig. 6 (a). The contents and configuration of the space change daily, and therefore, experience stored over the previous days cannot be used. Another example is a road section covered by overhanging trees, as shown in fig. 6 (b). Sunlight causes strong and complex shadowing effects. While these are advantageous for the real-time VO system to provide landmarks within, localized landmarks are not often encountered, again indicating that previous experience is not useful. Images with high visual variation encourage the use of real-time VO systems at all times.

In contrast, fig. 6c and 6d show the unfolded extensions of the road, which extensions have a rather stable appearance under similar weather conditions.

Figure 8 shows the amount of each traversal saved and the time taken. Here, the order of the number of accesses is the order in which data is collected. Also, on the left side of the graph, it can be seen that most of the VO output is stored when the plastic map is relatively not extensive and does not store much experience. As the number of passes increases, the amount of VO output stored decreases since the vehicle 102 is able to locate itself in more prior experience (according to the discussion of fig. 3, where new VO output is no longer stored when a location occurs in more than N experience).

Since data was collected the first time the night-time came down, a large jump occurred around the crossing 35-38. The road also has standing water and is raining, something that this system has not previously experienced. Fig. 13 provides images generated by the sensor on the traversal 38 and images b) and d) on the traversal 38, however, images a) and c) on earlier traversals are also relevant to the stored experience. Thus, it can be seen that the image generated on the traversal 38 is different from the earlier traversed image.

By first driving the inner loop 702, a second peak is caused at access 47. Suddenly, any positioning is unsuccessful and the entire section is saved until the circuit closer is aimed. At or shortly after the time that the inner loop 702 rejoins the outer loop 704, the loop closer should be able to reposition the vehicle 102, and the positioner again be able to locate within stored experience.

Describing FIG. 8 in slightly more detail, this view shows a portion of the VO output (see left axis), which is saved for future use. Also, the results emphasize the effect of varying N (the minimum number of fixes required to determine that the vehicle 102 is not lost), and by changing the symbol for each row of the diagram, the results show a minimum number of fixes N-1, N-2, and N-3.

For each pass, the portion of the VO output saved is also calculated, while every other access serves as a single available experience and the results are averaged. This is referred to as averaging by a single prior experience (AwSPE) and is indicated by the dashed line labeled triangle.

Fig. 12 shows an example of a localized fault on crossing 4, where the strong shadow effect is encountered for the first time: images a) and c) were generated from earlier passes and these images were stored as experience, however, images b) and d) were generated on pass 4.

Thus, as can be seen in fig. 12 and 13, where conditions occur that cause a large change in the environment (e.g., traveling at dusk or over a different route), it has been found that it is generally necessary to remember fewer and fewer VO outputs on each traverse as the vehicle 102 revisits the route.

To assess the advantages of saving multiple experiences to build a map of plastics (described in embodiments of the invention) as described above, experiments were conducted that attempted to locate current VO data in a single prior visit, i.e., without attempting to obtain a changing environment. For these experiments, only the stored experience was limited to the selected example visits, and in each traversal of the route, the amount of VO output that needs to be saved was determined in each case, indicating a positioning failure, and the results were averaged. Thus, first, the traversal number 1 is considered as the selected instance and used as the only stored experience for the traversal numbers 2 through 53. Second, the traversal number 2 is considered a selected example and serves as the only stored experience for traversal numbers 1 and 3 through 53. This pattern is repeated until each pass has been used as the selected instance.

This is shown in fig. 8, which is referred to as averaging over a single prior experience (AwSPE) with all accesses, the saved average VO output is 65.8%, and none of the accesses is particularly "good" as a priority for the other accesses. This motivates the use of multiple experiences to represent the environment. Over time, new routes are revealed, and the embodiment of generating a plastic map as described above produces a 1/(traversal number) decay as the system acquires typical changes in routes.

The order in which data is collected is a privileged sequence. However, can pass through 53! The modes are ordered to produce different performance graphs. To demonstrate this, it was eagerly reordered, with the 10 most surprising traversals of the outer route and the first 6 inner traversals running the system anew. The resulting performance map is shown in fig. 10. Likewise, the most "interesting" and "surprising" traversals have moved to the beginning of the creation of the plastic map, and it is noted that the experience accumulation remains high (while highly variable traversals occur) until the traversal 18 before the large drop.

Each traversal can also be classified as cloudy or sunny (weather per visit is shown in fig. 9). In another experiment, the data was reprocessed using only the experience on cloudy or sunny days, the results of which are shown in fig. 11. (4 dusk were removed and 6 inner loop crossings. Interestingly, the system quickly accumulated sufficient experience to manage cloudy weather conditions when only cloudy days were pervasive (top view of fig. 11), while sunny days had slightly offset deviations throughout (bottom view of fig. 11). It is believed that the slight offset bias is caused by shadowing effects, making it difficult to locate in previous experience; this shading can of course be seen in fig. 6 b.

Finally, the performance of the system operating on the test vehicle is shown in fig. 14. The number of successful locators per frame on the crossing 47, which is the first crossing of the inner loop, is shown, as well as the time performance. The location is successful until frame 1296, at which time the vehicle is turned onto the inside loop. At this point, a new experience is started and since no relevant experience is stored, there is no positioning. At frame 2239, the outer loop shutoff is aimed and results in a successful fix, and therefore, the new experience ceases to save. Even with a different number of active locators, the time per frame typically remains below 100ms, while the average value of successfully located portions of the sequence (i.e., excluding frame 1296- > 2239) is 53 ms.

FIG. 16 shows one embodiment of a modified system when compared to the system of FIG. 1. However, for convenience, like parts are given like reference numerals. In this embodiment, the processing circuit 112 has a wireless communication device 1600, such as a 3G modem or the like. The wireless communication device 1600 allows the processing circuit 112 to communicate with a remote server 1604 over the network 1602. The network may be any suitable network, but is typically the internet. The skilled artisan will appreciate that while the server 1604 is represented in the figure as a single device, it may in fact be a plurality of separate devices, which may differ from one another.

In one embodiment, such as the embodiment shown in fig. 16, it is envisioned that remote server 1604 may share some of the processing load of processing the data generated from sensors 100 (and/or the output of the VO system). However, the server may also store experience that may be used to locate the vehicle 102.

As described above, the data output from the sensor 100 may vary greatly according to the time of day, weather conditions, and the like. Also, it is envisioned that only a subset of the stored experience may be used to locate vehicle 120 in its current location.

Likewise, remote server 1604 may be configured to store a set of experiences on storage 1606, and vehicle 102 may be configured to download a subset of the stored experiences. Thus, it is understood that storage device 1606 provides a storage device that is mounted outside of vehicle 102. A subset of the experience may be downloaded into the vehicle 102 based on various parameters, including any one or more of the following: time of day, weather conditions, expected route, location, etc.

Indeed, if the vehicle 102 generates a new experience while traversing, the vehicle 102 may be configured to upload the new experience to the remote server 1604.

In practice, the set of experiences maintained on the server 1604 may be generated by a plurality of vehicles. Likewise, the server 1604 may provide a library of experiences that may be used by any number of vehicles that wish to use those experiences to locate themselves.

Likewise, embodiments of the present invention may display a continuous positioning of vehicle 120. The positioning may be under varying lighting and/or weather conditions over a period of time, which is 3 months in the test. Embodiments use so-called plastic patterns. Likewise, embodiments do not focus on building monolithic graphs or inferring the underlying states that explain all the observations of the workspace, but rather on creating a composite representation constructed from multiple overlapping experiences. The representation (i.e., the plastic map) may be only as complex and rich as desired. Embodiments generally deal with drastic changes and slow changes in the same manner, and as soon as prior experience is not adequately described, a new experience is saved for future reference. Experiments have shown the advantage of the plastic map in localization performance (robustness) and using the 3 months of data that has been obtained, the asymptotic nature of plastic map maintenance can be shown.

Those skilled in the art will appreciate that many of the above-described features can be implemented in software, firmware, or hardware, or indeed by a combination of such software, firmware, and hardware. It is also intended to include systems implemented by any combination of these techniques.

Claims (23)

1. A method of locating a vehicle carrying a sensor, comprising the steps of:

a) obtaining data from the sensors at a current time, the sensors providing a sensed scene around the vehicle;

b) processing the sensed scene to extract a set of features from the sensed scene and using the extracted features to determine the position of the vehicle from the sensed scene in relation to the position of the sensor at an earlier time, by comparing the set of features extracted from the sensed scene with a plurality of stored experiences, wherein each stored experience is independent of the other stored experiences and each stored experience comprises a plurality of sets of features, where each set of features is determined from a previously sensed scene to ascertain whether the sensed scene can be identified within any of the stored experiences;

c) if the extracted feature set of the sensed scene is identified in any of the stored experiences, using the stored experience to generate an estimate of the vehicle's position at the current time relative to the stored experience;

d) repeating at least some of steps a to c,

wherein at least some of the stored experiences are captured in a given spatial region at different times.

2. The method of claim 1, wherein each stored experience exists in its own frame of reference.

3. The method of claim 1 or 2, wherein each stored experience represents at least a portion of an environment through which the vehicle moves; and wherein each stored experience is associated with at least one of the following other stored experiences:

(i) different spatial regions within the environment; or

(ii) A different visual appearance of the environment.

4. A method according to claim 1 or 2, wherein the stored experience provides a composite representation of the environment through which the vehicle is moving constructed from a plurality of overlapping experiences.

5. The method of claim 1, wherein the stored experiences are arranged in subsets according to one or more of the following parameters, and wherein a subset of the stored experiences is selected for use in steps (c) and (d) of the method according to one or more of the parameters:

(i) the time of day;

(ii) the day of the week;

(iii) season;

(iv) weather conditions;

(v) an expected vehicle route; and

(vi) a geographic location.

6. The method of claim 1, wherein at least some of the stored experience is downloaded from a remote server.

7. The method of claim 1, wherein the method is arranged such that if the sensed scene is not identified within more than a predetermined number of the stored experiences, the method stores the sensed scene so that the sensed scene becomes part of a new stored experience for future comparison.

8. The method of claim 7, wherein the method continues to try and identify the sensed scene within the one or more stored experiences as the method stores the sensed scene as new experience.

9. The method of claim 1, wherein the stored experiences are used by the vehicle/sensors that generated those experiences.

10. The method of claim 1, wherein the stored experiences are also used by vehicles and/or sensors other than the vehicle/sensor that generated those experiences.

11. The method of claim 1, analyzing the extracted features and using a transformation to link features within the sensed scene at the current time with features in a subsequent sensed scene at a second later time.

12. A method according to claim 11, wherein the method is arranged to generate a trajectory of the vehicle using the transitions linking nodes within the sensed scene.

13. The method of claim 1, wherein at least some of the stored experiences are associated with a location, and wherein the method uses a rough location of the vehicle to approximately determine the location of the vehicle.

14. The method of claim 13, which uses the location of the vehicle to determine which stored experiences should be considered to determine whether a sensed scene can be identified within.

15. The method of claim 1, wherein the captured data and stored experience comprise images, and wherein the method uses image matching techniques to determine stored experience similar to the sensed scene, and then uses the similar stored experience to determine whether the sensed scene can be identified within.

16. The method of claim 1, which requires that sensed scenes be identified within a predetermined number of stored experiences before it is determined that the vehicle has been located.

17. The method of claim 1, the method determining whether stored experiences are related to each other with similar places, and linking the stored experiences if it is determined that the stored experiences are related to approximately the same places.

18. A system for locating a vehicle, the system comprising: a sensor configured to generate data representative of a sensed scene surrounding the vehicle at a current time; processing circuitry arranged to process the data, wherein the processing is arranged to:

extracting a set of features from the sensed scene to determine a location of the vehicle from the data relative to a location of the sensor at an earlier time;

determining by comparing said data with a plurality of stored experiences maintained in a storage device, where each stored experience is independent of other stored experiences and each stored experience comprises a set of a plurality of feature locations to ascertain whether a sensed scene can be identified within any of said stored experiences; and

if the data allows the sensed scene to be identified in any stored experience, then the location of the vehicle is estimated using the stored experience,

wherein at least some of the stored experiences are captured in a given spatial region at different times.

19. The system of claim 18, wherein at least one of the following applies:

(i) at least a portion of the storage device is mounted outside of the vehicle and is arranged to be accessible from the vehicle;

(ii) the system further includes a server configured to communicate with processing circuitry on the vehicle;

(iii) the processing circuitry is arranged to compare the data with a subset of available stored experiences.

20. The system of claim 19, wherein the processing circuit is configured to obtain the subset of available stored experiences from a remote storage device, the subset of available stored experiences being locally maintained on a storage device on the vehicle.

21. A vehicle having a sensor mounted thereon, wherein the sensor is arranged to generate data representative of a sensed scene surrounding the vehicle at a current time; and processing circuitry arranged to process the data, wherein the processing circuitry is arranged to:

extracting a set of features from the sensed scene to determine a location of the vehicle from the data relative to a location of the sensor at an earlier time;

determining by comparing the data to a plurality of stored experiences maintained in a storage device, where each stored experience is independent of other stored experiences and each stored experience comprises a set of a plurality of feature locations to ascertain whether the sensed scene can be identified within any stored experience; and

if the data allows the sensed scene to be identified in any stored experience, then the location of the vehicle is estimated using the stored experience,

wherein at least some of the stored experiences are captured in a given spatial region at different times.

22. A system for locating a vehicle comprising: a sensor and a processing circuit provided in a vehicle; and

a server that is remotely located from the server,

wherein the sensor is configured to generate data representative of a sensed scene surrounding the vehicle at a current time,

the processing circuitry is arranged to:

extracting a set of features from the sensed scene to determine a location of the vehicle from the data relative to a location of the sensor at an earlier time;

determining by comparing said data with a plurality of stored experiences maintained in a storage of said server, where each stored experience is independent of other stored experiences and each stored experience comprises a set of a plurality of feature locations to ascertain whether a sensed scene can be identified within any of said stored experiences; and

if the data allows the sensed scene to be identified in any stored experience, then the location of the vehicle is estimated using the stored experience,

wherein at least some of the stored experiences are captured in a given spatial region at different times, and

the server is arranged to receive a network request from the network for one or more stored experiences, the server being arranged to process the request to retrieve the requested stored experience from the storage device and to transmit the requested stored experience over the network.

23. A storage medium comprising a stored program that, when executed by one or more computing devices, causes the one or more computing devices to perform the method of any of claims 1-17.