Distributed device mapping

CROSS-REFERENCE TO RELATED APPLICATIONS

0001The present application is a continuation of U.S. application Ser. No. 16/653,708 filed on Oct. 15, 2019 which is a continuation of International Application No. PCT/GB2018/051023 filed Apr. 18, 2018 which claims benefit of U.S. Provisional Application No. 62/486,761 filed Apr. 18, 2017 and Great Britain Application No. 1706129.2 filed Apr. 18, 2017 and Great Britain Application No. 1804193.9 filed Mar. 15, 2019 which are hereby incorporated by reference herein.

FIELD

0002The present invention relates to a hardware and software method for environment mapping. More particularly, the present invention relates to the efficient use of both local and remote computational resources and communication bandwidth to provide distributed environment mapping using a plurality of mobile sensor-equipped devices to build a globally consistent and accurate map of large-scale environments and to determine accurate positions of localisation landmarks and enable the recovery of the trajectory of poses (three dimensions of position and three-dimensions of rotation) of individual sensors.

BACKGROUND

0003The capability to construct, with a high degree of precision, a globally-consistent and accurate map of a large-scale environment such as a city, for example having precision to within a centimetre, is likely to be pivotal for many robotics, augmented- and virtual-reality applications.

0004An example of a particularly useful form of map is map data relating to three-dimensional positions for localisation landmarks or points-of-interest. This localisation landmark data allows for localisation functionality, based on this localisation landmark data within a map of a large-scale environment, as each of the landmarks in the localisation landmark data can be observed and detected by sensors on devices operating using the map of the large-scale environment and the localisation landmark data (where the map and data may optionally be combined), and the device can then associate the observed landmarks and their positions in the map with the device position as the landmark(s) is/are observed by the device sensor(s). This, in turn, allows computation of an accurate estimate of sensor position and rotation with respect to the mapped environment.

0005For example, the aforementioned centimetre-level precision is likely to be critical to aforementioned example applications. This level of accuracy is typically not achievable in urban environments using the global navigation satellite system (GNSS) owing to various atmospheric effects, strong reflection, or limited satellite visibility due to occlusion of the sky by tall buildings.

0006The exact form of the individual localisation landmarks, their detection and association depends on the employed sensor and localisation technology.

0007As an example, for camera-based sensors, a known method that can be used is to detect image features (for example by using approaches such as detecting image corners, Scale-invariant Feature Transform (SIFT), or Speeded Up Robust Features (SURF)). Detected image features can then be associated with localisation landmarks in a map, thereby allowing the triangulation of the position of the camera on each device.

0008As an alternative example, a similar functionality can be achieved by using so called direct methods of optimising the image reprojection error of the localisation landmarks. In this case localisation landmarks take the form of a three-dimensional point cloud or surface structure of the environment. For laser, Light Detection and Ranging (LIDAR), or depth-camera sensors a similar method of determining the iterative closest point can be used to align sensor measurements against the three-dimensional model of the environment to achieve similar effect.

0009Different methods can be used interchangeably or in conjunction for existing or future sensors.

0010Methods for constructing such localisation landmark data have been studied in various disciplines and known methods exist for their construction at a small scale. For example, considering camera sensor data, such a map can be constructed from a collection of two-dimensional images of the environment using so called structure from motion methods. An example of such a method is a computation known as a “Bundle Adjustment”. These methods involve jointly solving the problem of estimating all image poses in the three-dimensional space and the corresponding locations of observed landmarks. The disadvantage of this solution is that it is very computationally and memory intensive. Existing available state-of-the-art methods and packages, such as OpenMVG or OpenSfM, scale poorly with the amount of data being processed thus limiting their applicability to only few thousands of pictures at once. This is not sufficient for mapping a large-scale environment, using the millions or billions of pictures that are likely to be necessary for the aforementioned applications. Using distributed computation to implement these methods is difficult due to the large number of potential data constraints necessary to ensure global consistency.

0011A separate problem involves the difficulties involved with obtaining sensor data. Given the size of the mapped environment the effort of obtaining sensor data can be distributed, but distributing the data collection across multiple devices can result in multiple sensors mapping the environment simultaneously and the resultant data typically being transferred to a single localised storage for computation. It is also likely that data transfer is required to occur as the data is being collected, for example through a cellular network or other bandwidth-restricted channel, to minimise any or all of downtime, requirements for local storage and/or to avoid additional complexity associated with docking the device to the storage. Substantially simultaneous data transfer is likely to be needed for a lifelong continuous mapping system of the environment. Restricted bandwidth situations combined with a requirement for near simultaneous data transfer over a bandwidth-limited channel puts additional restrictions on the structure of the data collected.

0012Real-time simultaneous localisation and mapping (SLAM) systems such as ORB SLAM or LSD SLAM are used as alternates to state-of-the-art methods by producing faster results at the expense of solution quality. These systems avoid a full-map bundle adjustment to achieve a real-time map building performance. However, although such systems perform relatively well with single-device settings, they are not designed for multi-device mapping which is necessary to construct maps of large environments.

0013It is therefore desired that utilisation of sensors, available bandwidth, local and remote storage and computational resources is as efficient as possible.

SUMMARY OF INVENTION

0014Aspects and/or embodiments seek to provide a distributed localisation and/or mapping system capable of delivering substantially high-accuracy real-time localisation at a device. Aspects and/or embodiments also seek to address the problem relating to structure from motion methods where a three-dimensional reconstruction of an environment is difficult to obtain in dependence upon two-dimensional sensor images.

0015According to a first aspect, there is provided a method of determining a global position of one or more landmarks on a global map, the method comprising the steps of determining one or more differences between sequential sensor data poses captured by one or more moving devices; estimating one or more relative localisation landmark positions with respect to the one or more moving devices; estimating relative device poses for the one or more moving devices in dependence upon the one or more relative localisation landmark positions; determining absolute device positions by optimising the estimated relative device poses; and determining an absolute global position for the one or more localisation landmarks based on a correlation between each absolute device pose or position and the one or more relative localisation landmark positions.

0016The locations of any number of objects or features of an environment that is easily recognisable at a distance can be identified and located by a plurality of mobile devices equipped with sensors for capturing data at regular intervals along a movement path.

0017The term global map throughout the specification can respectively be replaced with base map, map or a map stored at a sever. A portion of a map stored at a server can also be used in some aspects and/or embodiments. In some instances, the term pose graph can be used to describe an environment without landmarks being located.

0018Having located the positions of a landmark, the location and/or pose of a plurality of mobile devices can be identified with respect to the landmark. More than one landmark can be used to identify where a mobile device is, and even in which direction a mobile device is facing. The estimated landmark positions are therefore used to generate constraint values to further optimise the relative poses and/or positions.

0019Optionally, optimising the device poses comprises satisfying or minimising a constraint based on the estimated relative poses between sensor data. The sensor can be sequential data for the same device or data from other devices.

0020Optionally the step of determining one or more differences comprises a time stamp for each sequential sensor data.

0021The sensor of the device can capture consecutive measurements which advantageously requires less computational power and memory intensive systems.

0022Optionally, the one or more devices comprise as a sensor any or a combination of: an image camera; a video camera; a laser based sensor; a depth camera; a stereo camera; a high dynamic range camera; a light detection and ranging sensor; a radio detection and ranging sensor.

0023Optionally, the step of determining one or more differences is performed in real-time on each of the one or more devices.

0024Since the method does not require a large amount of computational power or memory, the calculations of differences between the consecutive data measurements captured by the sensors can be performed on each device to lessen the bandwidth requirements of the overall system.

0025Optionally, the sensor data comprises pose data.

0026Pose data can relate to position and orientation of the device. More particularly, pose data of a sensor can relate to the pose of a sensor at the time the sensor data is captured.

0027Optionally, the step of determining one or more differences comprises relative pose between sequential sensor data.

0028The differences between poses, or sensor data, can relate to the amount a device has rotated and/or traversed.

0029Optionally, the step of estimating one or more relative localisation landmark positions comprises obtaining landmark data substantially directly from the one or more device sensors.

0030Optionally, the step of estimating one or more relative localisation landmark positions is based upon triangulation of the sequential sensor data.

0031As sequential data can enable easier computation, a localisation landmark can be captured by a sensor several times as the device traverses an environment. Simple triangulation techniques can be implemented to locate the landmark on a base map using a sequence of sensor data alone.

0032Optionally, the step of estimating one or more relative localisation landmark positions is performed in substantially real-time on each of the one or more devices.

0033The relative positions of the localisation landmarks can be determined almost instantaneously by the device or within the system.

0034Optionally, the step of determining one or more differences and the step of estimating one or more relative localisation landmark positions is performed independently.

0035These steps can also be performed at the same time to determine the relative movement of the sensor(s) and the relative position of the landmarks.

0036Optionally, determining relative device poses based on one or more differences between sequential sensor data comprises determining a relative pose between one or more sensors.

0037The position of the one or more device can be more accurately identified based on the orientation or movement difference between the same device in the same area as it was previously, or by another device in the same area.

0038Optionally, the step of estimating relative device poses is performed on a centralised server or distributed across a cluster of computers within the network.

0039Optionally, the step of determining correlation, in the method of the first aspect, each landmark position is computed independently.

0040The efficient distribution of the computational power can enable the position of each localisation landmark to be determined independently from all others.

0041Optionally, the step of determining correlation, in the method of the second aspect further comprises any combination of Global Navigation Satellite System, GNSS, and Inertial Measurement Unit, IMU, data.

0042Optionally, the data captured by the sensors is distributed across a plurality of devices.

0043The efficiency of the data collected by the devices can be significantly improved by splitting the data among multiple devices.

0044Optionally, the data captured by the sensors is transmitted through a wireless network.

0045The efficiency of the data collected by the devices can be improved by communicating the data using a wireless network.

0046Optionally, the determinations and/or computations are performed on a combination of devices and a centralised server.

0047Optionally, the step of determining absolute device positions comprises minimising the difference between the estimated relative device poses and their determined pose after optimisation.

0048Efficiency of computation can be achieved by splitting the computation between the cloud and sensors/devices.

0049Optionally, the determinations and/or computations are performed on a device within a geographical area.

0050Efficiency of computation can be achieved through computing loop closures, is performed only in geographically close sensor locations.

0051Optionally, the method of re-computing poses of devices from known landmarks and re-computing positions of localisation landmarks. Re-computation can further enhance the accuracy of location and/or pose information for the devices and the localisation landmarks. Optionally, this can have a form of simultaneous optimisation of landmark positions and sensor poses known as “bundle adjustments”.

0052The re-computing step can be performed a number of times.

0053Optionally, sensor data is used to create or update the global map. Optionally, creating or updating the global map comprises any of: creating a new constraint or variable, such as pose data, in the global map; updating or amending an existing node in the global map; deleting a node in the global map; optimising the global map; or performing global loop-closures to link positions of different localisation nodes.

0054Updating the global map or global master map using sensor data allows the global map to adapt over time and continuously improve through AR uses. This includes the global map growing larger in size and richer in data for, for example, different environmental conditions.

0055Optionally, the global map comprises digital content associated with the one or more landmarks. Optionally, the digital content comprises any of: a picture, textual description or a video. In this way, landmarks can be annotated to enable a more personalised or descriptive tag of the landmark.

0056According to another aspect, there is provided an apparatus comprising a plurality of sensors operable to traverse an environment and collate pose data in sequence and communication means operable to send the pose data to a server system, wherein the server system is operable to perform the method of any preceding claim.

0057The server system can be a centralised sever or a collation of cloud and mobile devices.

0058According to another aspect, there is provided a computer program product for providing the method or system of any preceding claim.

0059According to another aspect, there is provided a method of determining a pose of one or more devices on a global map, the method comprising the steps of determining one or more differences between sequential sensor data captured by one or more moving devices; determining one or more relative localisation landmark positions with respect to the one or more moving devices; determining relative device poses based one or more differences between sequential sensor data relative to the one or more relative localisation landmark positions; and determining a correlation between: the relative device poses and differences between sequential sensor data and the one or more relative localisation landmark positions.

BRIEF DESCRIPTION OF DRAWINGS

0060Embodiments will now be described, by way of example only and with reference to the accompanying drawings having like-reference numerals, in which:

0061<figref idref="DRAWINGS">FIG. <b>1</b></figref> illustrates an overview of the cloud server system in communication with a plurality of mobile platforms in transit on an example road layout according to an embodiment;

0062<figref idref="DRAWINGS">FIG. <b>2</b></figref> illustrates a flowchart showing the system operation between platforms and server system according to an embodiment;

0063<figref idref="DRAWINGS">FIG. <b>3</b></figref> illustrates trajectories for a plurality of platforms according to the embodiment of <figref idref="DRAWINGS">FIG. <b>1</b></figref>;

0064<figref idref="DRAWINGS">FIG. <b>4</b></figref> illustrates sensor measurements for each platform in transit along the transit routes of <figref idref="DRAWINGS">FIG. <b>3</b></figref>;

0065<figref idref="DRAWINGS">FIG. <b>5</b></figref> illustrates the sequence of the sensor measurements of <figref idref="DRAWINGS">FIG. <b>4</b></figref>;

0066<figref idref="DRAWINGS">FIG. <b>6</b></figref> illustrates the post constrains of the sequence of sensor measurements of <figref idref="DRAWINGS">FIG. <b>5</b></figref> with additional links between related sensor measurements between platforms; and

0067<figref idref="DRAWINGS">FIG. <b>7</b></figref> illustrates optimised poses of the sequences of the sensor measurements of <figref idref="DRAWINGS">FIG. <b>6</b></figref>.

SPECIFIC DESCRIPTION

0068An example embodiment will now be described with reference to <figref idref="DRAWINGS">FIGS. <b>1</b> to <b>7</b></figref>.

0069Referring now to <figref idref="DRAWINGS">FIG. <b>1</b></figref>, a typical implementation of the system according to at least one embodiment is shown. In the implementation shown in this diagram, there is provided a centralised server system or cloud-based server <b>10</b> communicating with a plurality of platforms <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>where the platforms in this example are automobiles. Each of the platforms <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>are equipped with one or more sensors, which in this example are image or video cameras.

0070The server system <b>10</b> of this embodiment will now be described in more detail below.

0071In this embodiment, the server system <b>10</b> is running on and implemented using cloud infrastructure, but in other embodiments the server system <b>10</b> may have a variety of physical and/or virtual configurations. In other embodiments, for example, there may be one or more servers and/or server systems and, where there are more than one servers and/or server systems, these may be configured to act as a single server or server system or as multiple independent servers or server systems and may or may not be in direct communication with each other.

0072Such a system is able to construct large maps of the environment by using a fleet of mobile sensors (on-board platforms <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d</i>) to develop a special problem structure which can then be solved by distributed computation, effectively exploiting the computational power of both the platform (i.e. mobile) and cloud (i.e. cloud-based server) resources.

0073In use, the platforms <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>traverse the environment <b>30</b> (which in the example of <figref idref="DRAWINGS">FIG. <b>1</b></figref> is a road system) and at the same time record sensor data. Depending on the embodiment, this sensor data can include any of camera data, laser data, GNSS or other satellite positioning data, and/or IMU data. This sensor data is in its raw form (that is to say ‘unprocessed’) and is then communicated to the server system <b>10</b> or to centralised data storage, such as a cloud storage implementation. The data communication, or transfer, can occur through, for example, a wireless data network such as a ‘phone data network or Wireless LAN, or logs can be stored locally on each platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>and transferred later in order to reduce bandwidth requirements.

0074The platforms <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>in other embodiments can be a variety of other vehicles (manned or unmanned) or alternatively devices such as mobile phones or AR/VR headsets or similar devices having sensors and the ability to communicate data with the cloud-based server <b>10</b>.

0075Referring now to <figref idref="DRAWINGS">FIG. <b>4</b></figref>, the process outlined above in relation to <figref idref="DRAWINGS">FIG. <b>1</b></figref> results in the creation of a dataset including a set of independent logs or datasets each containing a sequence of captured data <b>410</b><i>a</i>, <b>410</b><i>b</i>, <b>410</b><i>c</i>, <b>410</b><i>d</i>, <b>410</b><i>e </i>from a single device or platform as it progresses/progressed along a trajectory <b>400</b>. Each entry in the log or dataset <b>410</b><i>a</i>, <b>410</b><i>b</i>, <b>410</b><i>c</i>, <b>410</b><i>d</i>, <b>410</b><i>e </i>captures sensor data, for example an image frame or laser scan, that was captured by the respective device or platform at a particular moment in time when the device or platform was at a particular pose in three-dimensional space.

0076For most entries, i.e. points for which sensor data has been captured for each platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d</i>, the exact pose (i.e. position and orientation) of the sensor on each platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>is not usually known and it is also possible that only an approximate position for the platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d</i>, for example available through GNSS, is directly known.

0077In some embodiments, for efficiency purposes and to reduce the amount of data that needs to be processed/handled/transmitted, sensor data can be sub-sampled at a selected frequency in time (for example, three frames per second) or space (for example, a new sensor reading every x metres) or, in other embodiments, using another method or a hybrid method with the aim that good coverage of the environment is substantially achieved (for example, through use of an uncertainty function based on the speed of movement through the environment and the constraint to keep the function below a certain threshold of uncertainty value).

0078The sensor data, or sub-sampled sensor data, is then sent to be processed on a centralised server system <b>10</b> where all data is stored and computation of the map is executed.

0079In some embodiments, if the platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>or sensor thereupon is equipped with a processor of sufficient computational power then it can perform locally at least a part of the computation on data captured (as described later) and uploads the computation result to the centralised server <b>10</b> together with or instead of the sensor data or sub-sampled sensor data. This can result in a solution having higher scalability, as a major portion of the computation can be offloaded from the centralised server <b>10</b> to a sufficiently computationally powerful local resource located on the platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>(for example the sensor device on the platform <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d</i>). Additionally, it may also reduce the bandwidth required for uploading the data to the centralised server <b>10</b>.

0080Referring now to <figref idref="DRAWINGS">FIG. <b>2</b></figref>, an illustration of the sensors used, data collected and processed and communications in an embodiment are shown. The computation performed in at least one embodiment will now be described in detail.

0081The function of the computation in the embodiments is to substantially accurately determine the global position of both individual sensor device/platform poses and any observed localisation landmarks, both of which comprise the base map. When the system is initialised, for example when it is first started or when a new platform is added or new location is being mapped, neither the global position of the individual sensor device/platform pose nor any observable localisation landmarks are known and so must be computed.

0082As shown in <figref idref="DRAWINGS">FIG. <b>2</b></figref>, a method according to an embodiment for computing the base map is illustrated. This method comprises several steps:

0083(1) The relative transform between successive sensor poses is computed;

0084The first step involves independently estimating the relative motion of the individual sensors as they are traversing the mapped environment based on the captured data.

0085In this embodiment, a specific structure is adopted for the data such that it is stored sequentially in the order in which sensor data is collected. The sensor data can be the pose of a camera when it captured image data. As consecutive sensor measurements can be assumed to differ only slightly in capture position, a time stamp for each sensor measurement allows the use of computationally-lightweight odometry methods (instead of more computationally and memory intensive full-SLAM implementations). For example, such a computationally-lightweight odometry method is the use of an effective visual odometry method used in conjunction with a camera sensor to estimate the relative motion between camera frames. Further, this process can be carried out in real-time on the sensor device (or platform) itself as the data is captured, rather than at a remote server or cloud, provided there is a dedicated chip or sufficient computational power available locally in the sensor device (or platform).

0086The output from the odometry applied to the sequential data are motion estimates that can be locally-smooth and locally-accurate between successive frames but which can, however, “drift” over time—i.e. become increasingly inaccurate when compared to the true motion or actual/global position—thus lack globally accurate position or scale in the three-dimensional space. Thus, these motion estimates might not accurately represent the true trajectory that the sensor device (or platform) has travelled in the three-dimensional space (for example as illustrated in <figref idref="DRAWINGS">FIG. <b>3</b></figref>) and thus cannot be relied upon.

0087The result of the computation performed in this step is the output of a relative pose (i.e. rotation and translation) between successive camera positions in individual logs, as shown in <figref idref="DRAWINGS">FIG. <b>5</b></figref>.

0088(2) The relative positions of localisation landmarks are computed;

0089The second step is to perform the computation of the relative position of observable localisation landmarks along each of the trajectories of each platform. The landmark data can be obtained directly from a sensor (for example as a local point-cloud if the sensor is laser-based or a stereo- or depth-camera system) or the positions of the landmarks can be triangulated from successive sensor movements as the device moves (for example where the device or system is estimating image features with a camera).

0090As only the relative pose of the sensor positions is known at this stage from the first step, the absolute positions of the landmarks cannot be determined accurately. Only the relative positions of landmarks with respect to the sensor device or platform, based on captured sensor poses, can be computed and stored. This computation is carried independently for each log in this embodiment. Again, the sequential structure of the data makes this computation easier, as a single landmark is likely to be observed in a sequence of consecutive frames that are necessary for its triangulation relative to the estimated motion of the sensor device or platform, and thus data for each observed and triangulated landmark can also be stored on the captured device itself.

0091Optionally, in some embodiments the first step of computing visual odometry can be combined with the second step of estimating positions of landmarks to jointly produce relative motion estimates of the sensor and relative position data for landmarks.

0092(3) The relative pose between nearby sensor poses is computed;

0093The third step is to detect and estimate relative poses between different sensors or the same sensor when these visit the same place again (i.e. the same location in the master or base map) in the mapped environment, in order to perform a process called loop closing.

0094The process of loop closing can be achieved by means of a two-stage process:

0095First, it is determined whether or when a sensor visits somewhere in the mapped environment that has already been visited by another sensor or the same sensor—this process is termed “loop detection”. This step can be achieved via a search of nearby sensor data having a similar or the same location based on satellite-determined positioning data, or by determining statistical similarity in a bag-of-word representation of multiple sensor poses, or by determining similarity in the structure of localisation landmarks as computed in the second step, or through use of another form of semantic or appearance hashing where locations are mapped to memory addresses in such a way that similar locations are located in “nearby” memory addresses. Of course, a combination of such techniques may be used to carry out the loop detection process.

0096Second, a process termed “re-localisation” is performed where the relative pose is determined between corresponding pairs of poses (identifying any or each of rotation, translation or scale difference) determined in the loop detection step. As the relative pose of localisation landmarks is already known for individual logs from the second step, this can be achieved by cross-localisation of individual pieces of sensor data.

0097The computation required for this third step needs access to the logs (consecutive sensor measurements) from a portion of the map data (i.e. a zone surrounding one or more locations within the map data), and therefore the computation occurs in the centralised server after the data and the results of any local computation are transferred to the server. The computation can, however, be easily distributed across a cluster of computers based on for example geographical location. The output of this third step is a list of correctly detected loop closures between individual camera poses as illustrated in <figref idref="DRAWINGS">FIG. <b>6</b></figref>.

0098(4) Pose constraints <b>240</b> are generated;

0099The output of the first and second step results in a plurality of estimated relative pose transforms between various pieces of sensor data.

0100Due to the noise in the sensor data and imperfections in the sensors, the estimated pose transforms are likely to be noisy. The result of this is that in most cases no valid absolute (global) positions for the sensors which match the computed estimated pose transforms perfectly.

0101To allocate absolute (global) positions for each sensor over time to substantially match the pose transforms, a process termed “sensor pose optimisation” is performed. Sensor pose optimisation involves searching for a single assignment of variables that minimise the error between the absolute global positions and the estimated position derived from each sensor pose, where a collection of constraints are applied to the searching. In the embodiment, the variables correspond to relative sensor positions and the constraints are implied by the estimated relative transforms from the computations of the relative transformations between successive sensor poses and landmarks. Optionally, other constraints can be applied such as taking into account other data from sensors such as Global Navigational Satellite System (‘GNSS’) positioning data or IMU data. In an example, data from a GNSS sensor may be used to determine the absolute scale of the map, reduce the effect of drift, and improve the overall consistency of the absolute global positions.

0102This step does not involve optimising the relative position of landmarks, which significantly reduces the complexity of the problem and thus the problem can be solved very efficiently for millions of poses using off-the-shelf optimisation packages such as Ceres (RTM) or g2o. For extremely large instances, such as the ones corresponding to months of data collection at a global scale, a more tailored hierarchical approach might be needed.

0103The output of this step is a globally and locally consistent six degrees-of-freedom pose for each sensor through time as illustrated in <figref idref="DRAWINGS">FIG. <b>7</b></figref>. Moreover, as the amount of data and number of constraints grows, the accuracy of the solution increases.

0104(5) The absolute global positions of localisation landmarks are determined;

0105With the absolute poses of individual sensor positions known, the global position of localisation landmarks can be computed directly by multiplying its relative pose (landmark-to-sensor), as computed in the second step, by the computed absolute global pose of its corresponding sensor pose. The multiplication operation may include translating and rotating the or each pose information.

0106Alternatively, the absolute position of individual localisation landmarks can be re-computed from known poses (a problem of “structure from known poses” or “structure-only bundle adjustment”), similar to the approach used in the second step, but instead using the optimised (global) poses. This computation can be carried very effectively in a distributed way as each landmark can be re-computed independently from all others.

0107The result of the previous computations is a globally consistent map of both sensor poses and localisation landmarks.

0108(6) Optionally, iterative refinement of the solution is performed.

0109This solution can be further enhanced in accuracy by various methods. For example, employing an iterative refinement scheme involving (a) re-computing poses from known landmarks (for example by using a motion only bundle-adjustment method); (b) re-computing landmarks (for example by using a structure only bundle-adjustment); and repeating these two steps until convergence is achieved, or by using a bundle adjustment method.

0110The system of some, or all, of these embodiments can be used in distributed large-scale scenarios with low-cost client hardware, for example mobile ‘phones, and/or with any, or all, of: augmented reality headsets, self-driving cars, drones, and other robots.

0111The server system <b>10</b> and platforms <b>20</b><i>a</i>, <b>20</b><i>b</i>, <b>20</b><i>c</i>, <b>20</b><i>d </i>are in communication with each other, typically through a bandwidth-restricted communication channel, and in this embodiment for example the communications channel is a mobile ‘phone cellular data network. In other embodiments, other wireless data networks may be used instead or in addition to a mobile ‘phone cellular data network.

0112Any system feature as described herein may also be provided as a method feature, and vice versa. As used herein, means plus function features may be expressed alternatively in terms of their corresponding structure.

0113Any feature in one aspect of the invention may be applied to other aspects of the invention, in any appropriate combination. In particular, method aspects may be applied to system aspects, and vice versa. Furthermore, any, some and/or all features in one aspect can be applied to any, some and/or all features in any other aspect, in any appropriate combination.

0114It should also be appreciated that particular combinations of the various features described and defined in any aspects of the invention can be implemented and/or supplied and/or used independently.