TECHNICAL FIELD

The present disclosure relates to an apparatus, a system and a method in the fields of navigation technology and computer vision technology. For example, the disclosure relates to an apparatus, a system and a method for supporting navigation in an area.

BACKGROUND

Precise and accurate map information is often essential for navigation, in particular, for computer vision-based autonomous navigation. To provide an accurate localization during navigation, the map information of a navigation system usually includes mapping data such as environment models, geometry data, and location information in a large scale. In some conventional solutions, a large scale map may be split into multiple sub-maps.

SUMMARY

A large scale map may scale less well to a real environment. For instance, small errors may be accumulated during the making of the map based on iterative algorithms such as a structure from motion (SfM or SFM) algorithm or simultaneous localization and mapping (SLaM or SLAM) algorithm. As a result, drifting may occur during navigation. Furthermore, a navigation apparatus may need more time for pose computation. Moreover, the large scale map may be complicated and time-consuming to maintain and update.

When a large scale map or an area of interest corresponding to the large scale map is split into multiple sub-maps of reduced size, the multiple sub-maps may be simply stored and aligned when needed. One problem of using the conventional split sub-maps is that any misalignment between adjacent sub-maps may cause localization jumps during navigation. Moreover, small errors accumulated during the making of the large-scale map might still exist in the multiple sub-maps.

In view of the above, there is a need to address the aforementioned technical drawbacks in existing devices to improve navigation in an area. Apparatuses, systems and methods according to this disclosure facilitate navigation in an area in a robust and efficient manner.

These and other objectives are achieved by the subject matter of the independent claims. Further implementations forms are apparent from the dependent claims, the description and the figures.

According to the present disclosure, a local and dynamic sub-map stitching method is used to align adjacent sub-maps based on one or more precomputed and loaded transformations during navigation provided by a navigation apparatus. During navigation, a current position of a navigation apparatus may be used to query one or more pre-computed transformations of surrounding sub-maps. Further, adjacent maps may be stitched together based on the pre computed transformation(s), in order to ensure continuous and smooth navigation.

A first aspect of the present disclosure provides an apparatus for supporting navigation in an area. The apparatus is configured to generate one or more reference positions in the area. Further, the apparatus is configured to split the area into multiple sub-areas. As a result, there is at least one sub-area comprising at least one reference position.

The navigation may be specifically a vision-based navigation, optionally in combination with global navigation satellite system (GNSS) localization.

Optionally, the apparatus may be configured to determine the density of the reference positions based on one or more navigation requirements. The density of the reference positions may be increased with a higher demand for smooth navigation.

Optionally, each reference position may be a two-dimensional (2D) position or a three- dimensional (3D) position, which may be dependent on the map type of each sub-area.

For each reference position, the apparatus is configured to obtain a map of a sub-area where the reference position is located and at least one neighbouring map of at least one neighbouring sub-area. The map of the sub-area where the reference position is located may also be referred to as a current map of a current sub-area. A neighbouring sub-area may be a sub-area adjacent to the current sub-area. In the present disclosure, a map of a sub-area may be referred to as a sub-map. That is, the current map of the current sub-area may be referred to as a current sub-map, and the neighbouring map of the neighbouring sub-area may be referred to as a neighbouring sub-map. Furthermore, the current sub-area and one of the at least one neighbouring sub-area in the present disclosure may be collectively referred to as “a set of neighbouring sub-areas”. Correspondingly, the map of the (current) sub-area and the at least one neighbouring map of the at least one neighbouring sub-area may be collectively referred to as “a set of neighbouring maps” or “a set of neighbouring sub-maps”.

Further, the apparatus is configured to determine one or more transformations and to transform one or more of the current sub-map and the at least one neighbouring sub-map based on the one or more transformations such that the set of neighbouring sub-maps are aligned. Optionally, each transformation may be in a form of a vector or matrix, or may comprise key parameters related to each transformation. Each transformation may comprise at least one of the following: translation transformation, rotation transformation, and scaling.

Then, the apparatus is configured to associate the one or more transformations with the reference position. The apparatus may associate the one or more transformations collectively with the reference position.

Then, the apparatus is configured to provide the associated one or more transformations to a navigation apparatus. In this way, based on the one or more transformations, the navigation service provided by the navigation apparatus may be facilitated and map transformation performed by the navigation apparatus may be simplified.

Optionally, the apparatus may be configured to determine the sub-map, the at least one neighbouring sub-map, and the associated one or more transformations based on pose information provided by the navigation apparatus. Further, the apparatus may determine a nearest reference position with respect to the pose information and retrieve the one or more associated transformations. The pose information, or simply referred to as pose, may comprise position information and/or orientation information. Further, the position information may comprise 2D or 3D coordinates. The 2D or 3D coordinates may be global coordinates, e.g., GNSS coordinates. Alternatively, the 2D or 3D coordinates may be local coordinates, e.g., relative coordinates with respect to a reference position of the area of interest. The orientation information may comprise roll, pitch, and yaw information in a 3D space, or may comprise an angle in a 2D space.

In this way, each reference position may be used as an index during navigation to determine associated one or more transformations. Then, the navigation apparatus may be configured to obtain a locally aligned map by combining the set of neighbouring sub-maps based on the one or more transformations, correspondingly. The locally aligned map may ensure continuous and smooth navigation. Bounces and drifts may be avoided during the navigation based on the locally aligned map. Furthermore, the accuracy of navigation may be improved.

Optionally, a map of a particular sub-area may be reusable for different stitching scenarios based on different reference positions. The maintenance and update of maps of the multiple sub-areas may be simplified.

Optionally, alignment between different sets of neighbouring maps may be achieved and dynamically updated during navigation. Therefore, there is no need to compute a global alignment of all the maps of the multiple sub-areas.

The apparatus for supporting navigation is also referred to as “supporting apparatus” in this disclosure.

In an implementation form of the first aspect, the sub-area and the at least one neighbouring sub-area may share an overlapping section. In this case, for transforming one or more of the map and the at least one neighbouring map based on the one or more transformations, the apparatus may be specifically configured to transform one or more maps of the sub-area and the at least one neighbouring sub-area such that the maps are aligned at least in the overlapping section.

Alternatively, when the sub-area and the at least one neighbouring sub-area do not share an overlapping section but share at least one common edge, the apparatus may align the maps of the sub-area and the at least one neighbouring sub-area by matching edge features of the maps. In an implementation form of the first aspect, the apparatus may be configured to determine a shape and/or a size of each sub-area of the multiple sub-areas based on one or more of the following criteria: topography of the area; geographical density of the environmental data of the area; available computational resources of the apparatus for handling environmental data associated with each sub-area.

Split sub-areas can have different shapes and sizes. That is, each sub-area may have an individual shape and size.

Further, the topography of the area may comprise one or more of the following: terrain information, road topology, road names, borders of a point of interest (POI).

In this way, each split sub-area may be determined according to an actual application scenario of the navigation and apparatus capabilities. Therefore, the flexibility of the navigation may be increased.

In an implementation form of the first aspect, for obtaining the map for each sub-area, the apparatus may be configured to: obtain raw data, and generate a representation of each sub-area as the map based on the obtained raw data. The raw data may comprise one or more of the following information: one or more images, light detection and ranging (LiDAR) data, coordinates information of one or more GNSSs, geometric data, and road data; and

Optionally, the one or more images may comprise one or more of the following: a color image, a monochrome image, and a depth image.

Further, the map of each sub-area may be an overlay of the raw data. In an implementation form of the first aspect, the map of each sub-area may further comprise at least one or more representations of the following: a 2D model of the sub-area; and a 3D model of the sub-area.

The 2D model may be a 2D point cloud representing the sub-area or a 2D mesh representing the sub-area, and the 3D model may be a 3D point cloud representing the sub-area or a 3D mesh representing the sub-area.

Optionally, the 2D model or the 3D model may represent environmental data of each respective sub-area, such as but not limited to roads, buildings, POIs, terrains like rivers, lakes, mountains, etc.

In an implementation form of the first aspect, the map of each sub-area may further comprise pose information associated with the one or more representations.

Optionally, the pose information may indicate a position and an orientation associated with each representation. The pose information may comprise poses of sensors that are used to collect the raw data. Alternatively or additionally, the pose information may comprise poses that are used to build maps by a mapping platform.

In an implementation form of the first aspect, when the map and the at least one neighbouring map share the overlapping section, the apparatus may be specifically configured to determine a relative pose between maps of the sub-area and the at least one neighbouring sub-area based on the overlapping section. Then, the apparatus may transform the map of the sub-area or of the at least one sub-area based on the relative pose.

The relative pose may be further determined by using an iterative closest points (ICP) algorithm based on representations of the set of neighbouring sub-areas. The representations may be 2D/3D models or maps.

Optionally, the relative pose may be included in the one or more transformations. The relative pose may be relative to the pose information included in the current sub-map. In an implementation form of the first aspect, for generating the one or more reference positions, the apparatus may generate the one or more reference positions at one or more landmarks in the area.

The one or more landmarks may comprise one or more of a road and a POI.

In an implementation form of the first aspect, for generating the one or more reference positions, the apparatus may be configured to generate the one or more reference positions in one or more accessible regions of the area.

In this way, the one or more reference positions may be efficiently allocated and computational resources can be saved.

In an implementation form of the first aspect, for generating the one or more reference positions, the apparatus may be configured to generate the one or more reference positions evenly in the area. Alternatively, the apparatus may generate the one or more reference positions randomly in the area. In either way, reference position generation may be simplified and time consumption for preparing the reference positions may be reduced.

In an implementation form of the first aspect, the apparatus may be configured to determine a quantity and/or a distribution of the one or more reference positions based on the complexity of the map of each sub-area.

The density of the reference positions may be higher for a more densely populated sub-area.

In an implementation form of the first aspect, for determining the one or more transformations, the apparatus may be specifically configured to: employ a stitching algorithm to compute a local alignment transformation centered on the reference position between maps of the sub-area and the at least one neighbouring sub-area; and obtain an output of the stitching algorithm as one of the one or more transformations. Optionally, the stitching algorithm may be used to match edge features between the set of neighbouring sub-areas or match overlapping sections between the set of neighbouring sub- areas.

In an implementation form of the first aspect, each transformation may be a two degrees of freedom, DoF, or a 3 DoF, or a 6 DoF, or a 7 DoF transformation, wherein the 2 DoF transformation may relate to a translational transformation on two axes, the 3 DoF transformation may relate to a translational transformation on three axes or to the 2 DoF transformation and orientation, the 6 DoF transformation may relate to rotational and translational transformations on three axes, and the 7 DoF transformation may relate to rotational and translational transformations on three axes and scaling.

In an implementation form of the first aspect, for associating the one or more transformations with the at least one reference position comprised in each sub-area, the apparatus may be configured to store the one or more transformations of the sub-area in a database indexed by each of the at least one reference position.

Optionally, for providing the associated one or more transformations to the navigation apparatus, the supporting apparatus may provide the database directly to the navigation apparatus before navigation starts. In this case, the navigation apparatus may retrieve the one or more transformations by querying the database based on current pose information during navigation.

In an implementation form of the first aspect, for providing the one or more transformations, to the navigation apparatus, the apparatus may be configured to: receive pose information from the navigation apparatus; determine a reference position based on the pose information; and determine the one or more transformations based on the determined reference position.

For determining the reference position based on the pose information, the apparatus may choose the closest reference position with respect to the position comprised in the received pose information as the determined reference position. A second aspect of the present disclosure provides a navigation apparatus for providing a navigation service to a device in an area. The navigation apparatus is configured to: obtain a current pose of the device; obtain maps of a current sub-area and at least one neighbouring sub-area based on the current pose; obtain, from a supporting apparatus for supporting the navigation service, one or more current transformations based on the current pose;

- transform the maps based on the one or more current transformations; and provide the navigation service based on the transformed maps.

The supporting apparatus for supporting the navigation service is an apparatus for supporting navigation, for instance, according to the first aspect. Support in a navigation service is the same as supporting navigation in this disclosure.

Optionally, the current pose may comprise position information and/or orientation information. The position information may comprise 2D or 3D coordinates. The orientation information may comprise roll, pitch, and yaw information in a 3D space, or may comprise an angle in a 2D space.

Optionally, the navigation apparatus may obtain maps of all the sub-areas within the area including the current sub-area and the at least one neighbouring sub-area from a mapping platform before navigation and may store the obtained sub-maps locally.

Alternatively, the navigation apparatus may obtain all the sub-maps from the supporting apparatus, especially when all the sub-maps are generated by the supporting apparatus. In this case, the navigation apparatus may receive all the sub-maps from the supporting apparatus before navigation and may store the received sub-maps locally.

Alternatively, the navigation apparatus may obtain maps of the current sub-area and the neighbouring sub-area during the navigation from the mapping platform or the supporting apparatus. In this case, the navigation may send the current pose to the mapping platform or to the supporting apparatus. In this way, the storage requirement of the navigation apparatus may be reduced. Optionally, the navigation apparatus may obtain a database comprising the one or more current transformations from the supporting apparatus before starting the navigation service. In this way, the navigation apparatus may be operated in an offline mode in which communication between the supporting apparatus and the navigation apparatus during navigation may not be needed. Communication delay may be circumvented. In the offline mode, for obtaining the one or more current transformations, the navigation apparatus may be configured to: choose, from the database, the closest reference position with respect to the current position comprised in the current pose; and retrieve, from the database, the one or more current transformations associated with the closest reference position.

Alternatively, the navigation apparatus may obtain the one or more current transformations during navigation. In this case, the navigation apparatus may provide the current pose to the supporting apparatus during navigation. In this way, the navigation apparatus may be operated in an online mode, and the storage requirement for the navigation apparatus may be reduced. In the online mode, for obtaining the one or more current transformations, the navigation apparatus may be configured to: send the current pose to the supporting apparatus; and receive the one or more current transformations from the supporting apparatus.

It is noted that, in both the offline mode and the online mode, the one or more current transformations may be regarded as obtained from the supporting apparatus.

For transforming the maps based on the one or more current transformations, if there is no transformation corresponding to a particular map of the maps, the navigation apparatus may be configured not to transform this particular map. Optionally, the navigation apparatus may be configured to combine this particular map with a transformed neighbouring map and provide the navigation service based on the combined map.

Optionally, the device provided with the navigation service may be a handheld device (e.g., terminal, mobile phone, tablet, GNSS station, etc.), augmented reality (AR) or virtual reality (VR) device, robot, land vehicle (e.g., car, bus, truck, tram, subway, train), watercraft, aircraft (e.g., drone), or the like. In an implementation form of the second aspect, the navigation apparatus may be further configured to:

- update the current pose;

- update the maps and the one or more transformations based on the updated pose;

- transform the updated maps based on the one or more updated transformations; and continue providing the navigation service based on the updated and transformed maps

Optionally, the navigation apparatus may be configured to keep updating the current pose of the device during the navigation service.

A third aspect of the present disclosure provides a system for navigation in an area. The system comprises a supporting apparatus according to the first aspect or any implementation form thereof, and a navigation apparatus according to the second aspect or any implementation form thereof.

Optionally, the supporting apparatus may be a device physically separated from the navigation apparatus. Alternatively, the supporting apparatus may be a device attachable to the navigation apparatus. Alternatively, the supporting apparatus may be a model inside the navigation apparatus.

A fourth aspect of the present disclosure provides a method for supporting navigation in an area. The method is executed by a supporting apparatus and comprises the following steps: generating one or more reference positions in the area; splitting the area into multiple sub-areas.

For each reference position, the method further comprises: obtaining a map of a sub-area where the reference position is located, and a neighbouring map of at least one neighbouring sub-area; determining one or more transformations;

- transforming one or more of the map and the at least one neighbouring map based on the one or more transformations such that the map and the at least one neighbouring map are aligned; and associating the one or more transformations with the reference position; providing the one or more transformations, to a navigation apparatus. In an implementation form of the fourth aspect, the sub-area and the at least one neighbouring sub-area may share an overlapping section.

In an implementation form of the fourth aspect, the method may further comprise determining a shape and/or a size of each sub-area based on one or more of the following criteria: topography of the area; geographical density of the environmental data of the area; and available computational resources of the apparatus for handling environmental data associated with each sub-area.

In an implementation form of the fourth aspect, the obtaining of the map for each sub-area may comprise: obtaining raw data comprising at least one of the following: one or more images,

LiDAR data, coordinates information of one or more global navigation satellite systems, geometric data, and road data; and generating a representation of each sub-area as the map based on the obtained raw data.

In an implementation form of the fourth aspect, the map of each sub-area may comprise at least one or more representations of the following: a two-dimensional, 2D, model of the sub-area; and a three-dimensional, 3D, model of the sub-area.

The 2D model may be a 2D point cloud representing the sub-area or a 2D mesh representing the sub-area, and the 3D model may be a 3D point cloud representing the sub-area or a 3D mesh representing the sub-area.

In an implementation form of the fourth aspect, the map of each sub-area further comprises pose information associated with the one or more representations. In an implementation form of the fourth aspect, the determining of the one or more transformations may comprise: determining a relative pose between the map and the at least one neighbouring map based on the overlapping section, wherein the determined relative pose is one of the one or more transformations.

In an implementation form of the fourth aspect, the generation of the one or more reference positions may comprise generating the one or more reference positions at one or more landmarks in the area.

In an implementation form of the fourth aspect, the generation of the one or more reference positions may comprise generating the one or more reference positions in one or more accessible regions of the area.

In an implementation form of the fourth aspect, the generation of the one or more reference positions may comprise: generating the one or more reference positions evenly in the area; or generating the one or more reference positions randomly in the area.

In an implementation form of the fourth aspect, the method may further comprise determining a quantity and/or a distribution of the one or more reference positions based on the complexity of the map of each sub-area.

In an implementation form of the fourth aspect, the determining of the one or more transformations may comprise: employing a stitching algorithm to compute a local alignment transformation centered on the reference position between the map and the at least one neighbouring map; and obtaining an output of the stitching algorithm as one of the one or more transformations.

In an implementation form of the fourth aspect, each transformation may be a 2 DoF, or a 3 DoF, or a 6 DoF, or a 7 DoF transformation, wherein the 2 DoF transformation may relate to a translational transformation on two axes, the 3 DoF transformation may relate to a translational transformation on three axes or to the 2 DoF transformation and orientation, the 6 DoF transformation may relate to rotational and translational transformations on three axes, and the 7 DoF transformation may relate to rotational and translational transformations on three axes and scaling.

In an implementation form of the fourth aspect, the associating of the one or more transformations with the reference position may comprise storing the one or more transformations in a database indexed by the reference position.

In an implementation form of the fourth aspect, the providing of the one or more transformations to the navigation apparatus may comprise: receiving pose information from the navigation apparatus; determining a reference position based on the pose information; and determining the one or more transformations based on the determined reference position.

A fifth aspect of the present disclosure provides a method for providing a navigation service to a device in an area. The method is performed by a navigation apparatus and comprises the following steps: obtaining a current pose of the device; obtaining maps of a current sub-area and at least one neighbouring sub-area based on the current pose; obtaining, from a supporting apparatus for supporting the navigation service, one or more current transformations based on the current pose;

- transforming the maps based on the one or more current transformations; and providing the navigation service based on the transformed maps.

In an implementation form of the fifth aspect, the method may further comprise:

- updating the current pose;

- updating the maps and the one or more transformations based on the updated pose;

- transforming the updated maps based on the one or more updated transformations; and providing the navigation service based on the updated and transformed maps. A sixth aspect of the present disclosure provides a computer program product comprising a program code for performing the method according to the fourth aspect or any implementation form thereof, when executed on a computer.

A seventh aspect of the present disclosure provides a computer program product comprising a program code for performing the method according to the fifth aspect or any implementation form thereof, when executed on a computer.

An eighth aspect of the present disclosure provides a computer-readable medium comprising instructions which, when executed by a computer, cause the computer to carry out the method according to any one of the fourth aspect or any implementation form thereof.

A ninth aspect of the present disclosure provides a computer-readable medium comprising instructions which, when executed by a computer, cause the computer to carry out the method according to any one of the fifth aspect or any implementation form thereof.

A tenth aspect of the present disclosure provides a chipset comprising instructions which, when executed by the chipset, cause the chipset to carry out the method according to any one of the fourth aspect or any implementation form thereof.

An eleventh aspect of the present disclosure provides a chipset comprising instructions which, when executed by the chipset, cause the chipset to carry out the method according to any one of the fifth aspect or any implementation form thereof.

It has to be noted that all apparatus, devices, elements, units, and means described in the present application could be implemented in software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity, which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

BRIEF DESCRIPTION OF DRAWINGS

The above-described aspects and implementation forms will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which

FIG. 1A shows an example of two sub-maps; FIG. IB shows another example of two sub-maps; FIG. 2 shows a diagram of a method; FIG. 3 shows a navigation system; FIG. 4 shows an illustrative example of area splitting; FIG. 5 shows an illustrative example of sub-areas; FIG. 6 shows an illustrative example of area splitting and reference position generation; FIG. 7 shows an illustrative example of map stitching and transformation computation for a reference position;

FIG. 8 shows an illustrative example of area splitting; FIG. 9 shows a diagram of a method; and FIG. 10 shows a diagram of another method.

DETAILED DESCRIPTION OF THE EMBODIMENTS

In FIGs. 1-10, corresponding elements may share the same features and may function likewise.

FIG. 1 A and FIG. IB show examples of two sub-maps. An apparatus for supporting navigation (also referred to in short as “supporting apparatus” in this disclosure) in an area is configured to split the area into multiple sub-areas and generate one or more reference positions in the area. It is noted that in the present disclosure, the area may be referred to as an area of interest, where navigation is provided or supported. The apparatus for supporting navigation may be referred to as a supporting apparatus.

As shown exemplarily in FIG. 1A and FIG. IB, two sub-maps 101 and 103 correspond to two split sub-areas. Each sub-area may represent a part of the area. In the present disclosure, each sub-map and each sub-area may be in a one-to-one correspondence. That is, a sub-area may be represented by a corresponding sub-map. Therefore, a sub-area and a corresponding sub-map may share a same reference sign for convenience. For example, in the present disclosure, sub- area 103 and sub-map 103 may be both used. Furthermore, terms of “sub-map” may be used to refer to a corresponding “sub-area”, and a sub-map may also be referred to as a map.

Optionally, the area may be an outdoor area, such as but not limited to a park, district, and city. Alternatively, the area may be an indoor area, such as but not limited to a shopping center, warehouse, and office building. Alternatively, the area may a combination of the outdoor area and the indoor area, such as but not limited to an industrial park comprising roads, office buildings, factories, and warehouses.

Although the sub-maps 101 and 103 are depicted as 2D maps in FIG. 1A and IB, it is noted that the sub-maps may comprise 2D and/or 3D maps. Optionally, the sub-maps may further comprise mapping data that may be overlaid onto the 2D/3D maps. The mapping data may comprise images, LiDAR scans, POIs, or GNSS coordinates, or any combination thereof.

The two sub-areas 101 and 103 may share a common border and may not share an overlapping section, as shown exemplarily in FIG. 1A. In another case, as shown exemplarily in FIG. IB, the two sub-areas 101 and 103 may share an overlapping section 102. That is, in this case, the overlapping section 102 is part of the sub-area 101 and part of the sub-area 103. In both cases, the sub-area 103 may be referred to as a neighbouring sub-area of the sub-area 101, while the sub-area 101 may also be referred to as a neighbouring sub-area of the sub-area 103. The two sub-areas 101 and 103 may be referred to as a pair of neighbouring sub-areas. When there are more than two neighbouring areas, a set of neighbouring sub-areas may be used. Optionally, a neighbouring sub-area of a particular sub-area may be referred to as a sub-area next adjacent to the particular sub-area that shares a common border or an overlapping section with the particular sub-area. When there are three or more sub-areas, any two sub-areas that share a common border or an overlapping section also be referred to as a pair of neighbouring sub- areas. That is, a set of neighbouring sub-areas may comprise one or more pairs of neighbouring sub-areas. Optionally, a pair of neighbouring sub-areas may be the smallest unit for transformation computation.

Further, a reference position is depicted exemplarily in FIG. 1A and FIG. IB. The supporting apparatus is configured to determine one or more transformations and transform the set of neighbouring maps such that the neighbouring maps are aligned. Optionally, the alignment may be directed to each pair of neighbouring sub-areas comprised in the set of neighbouring sub- areas. Optionally, each transformation may comprise at least one of a translation transformation (or simply translation), a rotation transformation (or simply rotation), and a scaling transformation (or simply scaling). The translation may be referred to as a geometric transformation that moves every point of a figure or space by the same distance in a given direction. The rotation may be referred to as a geometric transformation that moves every point of a figure or space by the same angle. The scaling may be a linear transformation that enlarges (increases) or shrinks (diminishes) coordinates by scale factors. The scaling may be isotropic scaling, of which the scaling factors of all the coordinates share the same value.

For example, a transformation of 2D mapping data may be applied by using a matrix operation as follows: in which (x,y) denotes 2D coordinates before transformation, (x y ’) denotes 2D coordinates after transformation, (h,k) denotes translation, a denotes rotation, and m denotes scaling. In this example, each reference position may be associated with an individual combination of (h, k ), a, and m.

It is noted that the matrix given above is a mere example for illustrating the transformation. There are other matrices in the field available representing the translation, rotation, and scaling. Optionally, it is sufficient that the transformation may comprise information indicating at least one of the translation, rotation, and scaling.

In FIG. 1A and FIG. IB, the supporting apparatus may determine that the sub-map 103 can move upwards with a specific distance D for this reference position such that the two sub-maps 101 and 103 can be aligned along the common border or in the overlapping section. Therefore, a transformation for the sub-map 103 may be performed by applying a matrix as follows: In this example, rotation and scaling are not required. Therefore, a = 0 and m = 1. Then, this transformation, e.g., information representing (h,k) = (0, D), a = 0, and m = 1, may be associated with this reference position. Furthermore, since no transformation is required for sub-map 101, transformation regarding sub-map 101 may be empty or may be void. It is noted that a void value for a scaling factor shall be understood as 1. That is, scaling is not performed if the scaling factor is 1 or is not defined in the transformation.

The determining of the transformation and transforming the set of neighbouring maps may be collectively referred to as map stitching and transformation computation. Algorithms for aligning and stitching 2D/3D/depth images corresponding to neighbouring maps are commonly known in the field. For example, a factor graph model may be used and non-linear optimization may be involved. Optionally, Levenberg-Marquardt algorithm and Gauss-Newton iteration may be used by the supporting apparatus during the map stitching and transformation computation. Details regarding the algorithms shall be commonly known to the skilled person and are not discussed in detail herein.

Optionally, the supporting apparatus may be configured to store the one or more transformations indexed by the reference position in a database. The database may be stored in a storage medium of the supporting apparatus. Optionally, the supporting apparatus may determine a unique identity (ID) for each reference position. The unique ID may be a sequence number, or GNSS coordinates of each reference position, or a hash value of the GNSS coordinates, or the like.

FIG. 2 shows a diagram of a method performed by a supporting apparatus. The supporting apparatus is configured to perform area splitting and reference position generation 201. It is noted that there is no specific execution order between area splitting and reference position generation.

In area splitting and reference position generation 201, the supporting apparatus may be configured to divide the area into the multiple sub-areas. Coverage of all the sub-areas together may be the same as the coverage of the area of interest. Some of the sub-areas may share an overlapping section. Optionally, the supporting apparatus may be configured to generate mapping data based on raw data of the area. The raw data may be collected from different sensors and may comprise one or more of the following: image(s) of the area, LiDAR data, GNSS coordinates, geometric data, POIs, and road information. Some SLAM algorithms commonly known in the field may be used to generate the mapping data. Mapping data of a sub-area may be simply referred to as a map in the present disclosure.

Optionally, the area of interest may already comprise the mapping data provided either by a mapping platform or via crowdsourcing means. Further, the mapping data may be built by the mapping platform based on mapping algorithms commonly known in the field, such as but not limited to SLAM and SFM algorithms. The mapping data may comprise a 2D model or 3D model of the area of interest or of each sub-area, which may be referred to as a 2D map or 3D map. Optionally, the mapping data may further comprise one or more of the following information of the area or of the sub-area: images of the environment, LiDAR scans, POI information, topography of the area, road information, and GNSS coordinates. When the area is split into multiple sub-areas, each sub-area may comprise corresponding mapping data inherited from the mapping data of the area. The supporting apparatus may be configured to store the mapping data of each sub-area and provide the mapping data to a navigation apparatus during navigation. Alternatively, mapping data of sub-areas may also be provided by the mapping platform to the navigation apparatus.

Optionally, the supporting apparatus may employ a splitting algorithm to split the area of interest. For example, the supporting apparatus may adapt the size and the shape of each individual sub-area based on one or more of road topology, road semantic, and geographical density of the mapping data. Alternatively, the supporting apparatus may also split the area such that the computation time for map stitching is comparable for each split sub-area.

Further, the supporting apparatus generates one or more reference positions in the area of interest. Optionally, two or more reference positions may be generated based on a regular sampling over the area of interest, where the reference positions may be located evenly over the area of interest. Alternatively, the two or more reference positions may be generated based on an irregular sampling. Optionally, the one or more reference positions may be located only in accessible regions in the area of interest. Optionally, the supporting apparatus may determine the density and the number of the one or more reference positions according to navigation requirements. A denser reference position may lead to smoother navigation, but also may lead to a larger database for storing transformations.

Once the area of interest is split, the one or more reference positions are also split into sub- areas, respectively.

Then, the supporting apparatus is configured to perform map stitching and computation 202 for each reference position. For convenience, a sub-area where the reference position is located shall be referred to as a current sub-area. Optionally, for each reference position, one or more neighbouring sub-areas with respect to the current sub-area may be determined by the supporting apparatus. Alternatively, the supporting apparatus may determine a distance and may exclude one or more neighbouring sub-areas that are not in the range of the distance from the current reference position. In this way, distant neighbouring sub-area(s) may be excluded for this reference position, and computational resources may be reduced.

Optionally, the supporting apparatus may be configured to employ conventional image alignment and stitching algorithms for performing the map stitching and transformation computation 202. Optionally, the stitching algorithm may be based on a factor graph model. Further, non-linear optimization may be used.

In some embodiments of the invention, one or more of global constraints and relative constraints may be applied to the conventional image alignment and stitching algorithms. The global constraints may also be referred to as absolute constraints, which may be used to ensure that certain mapping data in the transformed sub-map correspond to static values, such as GNSS coordinates, hand-picked pivot points, semantic features with known GNSS coordinates, and the like. The relative constraints may be used to ensure that mapping data of neighbouring sub maps are aligned between common edges or in the overlapping section if available. Furthermore, when mapping data of a pair of neighbouring sub-maps comprises 2D or 3D point clouds and associated pose information, an ICP algorithm may be used by the supporting apparatus for computing a relative pose between the pair of neighbouring sub-maps. The relative pose may comprise relative translation and rotation transformation that may be used to achieve an optimal alignment between the two neighbouring sub-maps. The relative pose may further comprise a scaling factor. By applying the global and relative constraints, the stitched sub-maps may be globally accurate because of the global constraints and continuous across sub-maps because of the relative constraints. Small errors introduced during mapping data collection and making process may be mitigated for neighbouring sub-maps during the local map stitching process.

For each reference position, there may be one transformation for each sub-map. If one sub-map does not need a transformation, no transformation may be comprised for this sub-map. When the relative transformation is used, there may be one relative transformation for each pair of neighbouring sub-maps.

Each transformation may be based on a 3 DoF or 6 DoF transformation. Optionally, each transformation may additionally comprise a scaling factor as an extra DoF. Optionally, the 3 DoF transformation may correspond to 2D maps and may comprise 2 DoF translation transformation and 1 DoF rotation transformation in a 2D space. When there is no rotation transformation, the 3 DoF transformation may also be in a form of 2 DoF, which may comprise 2 DoF translation transformation in the 2D space. 6 DoF transformation may correspond to 3D maps and may comprise 3 DoF translation transformation and 3 DoF rotation transformation in a 3D space. When there is no rotation transformation, the 6 DoF transformation may also be in a form of 3 DoF, which may only comprise 3 DoF translation transformation in the 3D space.

The supporting apparatus is further configured to associate the one or more transformations with the reference position. Optionally, the supporting apparatus may store the one or more transformations into a transformation database indexed by the corresponding reference position. Optionally, each reference position may be transformed into a unique value or ID such that the associated one or more transformations may be easily indexed through the unique value or ID. For example, the supporting apparatus may compute a hash value of GNSS coordinates of each reference position. Optionally, the transformation database may be in a structure of a look-up table, which has 0(1) access complexity and a high memory footprint. Alternatively, the transformation database may be in a structure of a KD-tree, which has O (n log(//)) access complexity and moderate memory footprint. Alternatively, any other suitable database in the field may be used by the supporting apparatus.

The supporting apparatus may be configured to perform steps 201 and 202 only once as preparation for navigation. Optionally, when mapping data needs to be updated, the supporting apparatus may be configured to update mapping data of affected sub-area(s) and re-calculate corresponding one or more transformations for any reference position comprised in the affected sub-area(s) and in neighbouring sub-area(s) of the affected sub-area(s). In this way, maintenance and update of maps of the area of interest may be simplified.

Then, the supporting apparatus may be configured to provide the stored mapping data of sub- areas and the transformation database to the navigation apparatus for providing a navigation service to a device in the area of interest. Alternatively, the mapping data of sub-areas may be provided by the mapping platform. This is not limited in embodiments of the invention. It is noted that the navigation apparatus may be an internal unit comprised in the device, or an external unit attachable to the device. This is not limited in embodiments of the invention. Optionally, the navigation apparatus may be configured to provide map-based localization to the device. Additionally, the navigation apparatus may be assisted by a GNSS positioning module.

During navigation, the navigation apparatus may perform dynamic map alignment 203 and localization 204. A current pose is obtained. A pose may comprise position information and optional orientation information of the device. The position information can be either 2 DoF or 3 DoF, e.g., 2D coordinates or 3D coordinates. The position information comprised in the current pose may be used to determine the nearest reference position so that one or more associated transformations may be retrieved from the transformation database based on the determined reference position. Optionally, the current pose may be a localization result obtained from a most recent localization 204. Alternatively, for example, if there is no previous localization result available, the current pose may be obtained by one or more sensors of the device, such as a GNSS module, camera, radar, LiDAR sensor, inertial measurement unit, and the like.

In some embodiments of the invention, the supporting apparatus may provide sub-maps of all the sub-areas in the area of interest and the transformation database to the navigation apparatus before navigation. That is, the navigation apparatus may be pre-loaded with all the sub-maps and the transformation database. In this case, a communication link between the navigation apparatus and the supporting apparatus is not required during navigation and the navigation apparatus may provide navigation service in an offline mode. In this case, the navigation apparatus may be configured not to provide the current pose to the supporting apparatus. The determination of the reference position may be performed locally on the navigation apparatus.

In some other embodiments of the invention, the navigation apparatus may be configured to provide the current pose to the supporting apparatus, so that a reference position may be determined by the supporting apparatus. In this case, a communication link between the navigation apparatus and the supporting apparatus is required during navigation and the navigation apparatus may provide navigation service in an online mode. Then, the navigation apparatus may obtain maps around the reference position and associated one or more transformations from the supporting apparatus. Alternatively, the navigation apparatus may obtain the maps from a mapping platform.

Nevertheless, in all the embodiments of the invention, the navigation apparatus at least obtains the one or more transformations from the supporting apparatus. It is noted that it also covers the situation when the navigation apparatus is configured to obtain the transformation database from the supporting apparatus. Because the one or more transformations is originally provided by the supporting apparatus in both the online mode and the offline mode.

Then, the navigation apparatus is configured to perform dynamic maps alignment 203. For performing the dynamic maps alignment 203, the navigation apparatus is configured to transform one or more sub-maps of corresponding sub-areas based on the one or more transformations indexed by the nearest reference position in the transformation database. Thereby, neighbouring sub-maps may be aligned along common borders or in the overlapping sections. Then, the navigation apparatus may be configured to perform the localization 204 based on the aligned neighbouring sub-maps in order to obtain an accurate and up-to-date pose of the device. The localization may also be referred to as pose estimation. The localization may be, for example, a map-based localization. Thus, the navigation apparatus can provide a continuous and smooth navigation service based on the transformed sub-maps, which are globally accurate and locally coherent. Details regarding the localization 204 shall be commonly known to the skilled person and are not discussed in detail herein.

During navigation, the navigation apparatus may be configured to obtain an updated pose with the movement of the device. This updated pose may cause a change of reference position. Therefore, the updated pose may be used to obtain one or more updated sub-maps and one or more updated transformations. Then, the navigation apparatus may transform the one or more updated sub-maps based on the one or more updated transformations and continue providing the navigation service. It is noted that the one or more updated transformations may indicate a transformation between a previously obtained sub-map (e.g., a sub-map obtained before the update) and at least one updated neighbouring sub-map. For example, previously, the navigation apparatus may provide navigation in sub-area 1 and 2. After pose update, the navigation apparatus may provide navigation in sub-area 2 and 3. In this case, only the map of sub-area 3 needs to be obtained. Therefore, it is possible that the navigation apparatus may obtain only one updated sub-map.

It is noted that for performing localization 204, a localization algorithm commonly known in the field may be used by the navigation apparatus to compute the pose of the device. The localization algorithm can be, for example, but not limited to:

SLaM algorithm in a localization mode, learned pose regressor,

ICP-like alignment algorithm, and

- Perspective-n-Point (PnP)-like feature to point alignment algorithm.

FIG. 3 shows a navigation system. The navigation system comprises a supporting apparatus 310 described according to FIGs. 1 and 2, and a navigation apparatus 320 described according to FIG. 2. FIG. 3 also depicts an optional mapping unit or platform 330 that may be configured to provide mapping data 311 to the supporting apparatus 310 and/or to the navigation apparatus 320. When the supporting apparatus 310 can generate the mapping data 311 on its own, the mapping unit 330 may not be needed. Optionally, the mapping platform 330 may be integrated into the supporting apparatus 310. Further, the mapping unit 330 may be configured to command a single mapping device sweeping the area of interest in order to collect the mapping data 311. Alternatively, the mapping unit 330 may be configured to lead a fleet of distributed collecting devices, which may be configured to collect the mapping data 311of the area of interest in a crowd-sourced manner.

The supporting apparatus 310 is configured to perform area splitting and reference position generation 201 in order to obtain multiple sub-areas and one or more reference positions 312. Optionally, the supporting apparatus 310 may notify the split multiple sub-areas to the mapping platform 330, so that the mapping platform may collect mapping data 311 of the sub-areas and provide it to the supporting apparatus 310 and/or the navigation apparatus 320.

Then, the supporting apparatus 310 performs map stitching and transformation computation 202 in order to obtain one or more transformations 313 for each reference position. Then, the obtained one or more transformations 313 are associated with each reference position and may be stored into a transformation database 314.

During navigation, the navigation apparatus 320 may obtain a current sub-map of a current sub- area, one or more neighbouring sub-map of one or more neighbouring sub-area and corresponding one or more transformations based on a current pose.

Alternatively, before navigation, the navigation apparatus 320 may obtain all the sub-maps 321 from the mapping unit 330 or the supporting apparatus 310. Further, the navigation apparatus 320 may obtain the transformation database 313 from the supporting apparatus 310.

Alternatively, the navigation apparatus 320 may also obtain maps of the current sub-area and the at least one neighbouring sub-area from the mapping platform 330 or the supporting apparatus 310 during navigation. In this case, the navigation apparatus 320 may provide the current pose to the mapping platform 330 or to the supporting apparatus 310, which is not shown in FIG. 3.

The navigation apparatus performs localization 204 and outputs a current pose 322 of the device. The current pose 322 may be used to determine the nearest reference position for a next round of localization 204. Based on the determined reference position, the navigation apparatus 320 obtains one or more associated transformations. Then, the navigation apparatus 320 performs map alignment 203 to obtain locally aligned neighbouring sub-maps 323. Then, the navigation apparatus 320 provides navigation service based on the locally aligned neighbouring sub-maps 323. During navigation, the current pose 322 may be updated with the movement of the device. Then, the navigation apparatus 320 may keep updating sub-map(s) and transformation(s) based on the up-to-date pose 322 and performing map alignment 203. Therefore, map alignment 203 may also be referred to as dynamic map alignment 203.

FIGs. 4-8 show illustrative examples based on a common area 400. FIG. 4 shows an illustrative example of area splitting. The area of interest 400 is split into four sub-areas 401-404, which are also marked as sub-area I-IV in FIG. 4.

FIG. 5 shows an illustrative example of sub-areas 401-404. In this example, every two sub- areas in FIG. 5 can be referred to as a pair of neighbouring sub-areas. That is, for sub-area 401, each of sub-area 402, sub-area 403, sub-area 404 is a neighbouring sub-area. Alternatively, there are a set of three neighbouring sub-areas 402, 403, 404 for sub-area 401. Alternatively, sub-areas 401, 302, 403, and 404 may be collectively referred to as a set of neighbouring sub- areas. Furthermore, in this example, every two sub-areas share an overlapping section marked in FIG. 5.

FIG. 6 shows an illustrative example of area splitting and reference position generation 201. In this example, multiple reference positions are generated along roads in the area of interest 400. Further, the multiple reference positions may be “inherited” in sub-maps 401-404, respectively.

FIG. 7 shows an illustrative example of map stitching and transformation computation 202 for a reference position. In particular, FIG. 7 shows map stitching and transformation computation 202 for a specific reference position marked in area 701. The area 701 corresponds to the area of interest 400 and is transformed based on the four transformations associated with this specific reference position. It is noted that for this specific reference position, transformations of sub- area I and sub-area II may be bound to global constraints, while transformations of sub-area III and sub-area IV may be bound to relative constraints. Because the specific reference position is closer to sub-area III and sub-area IV than to sub-area I and sub-area II. More specifically, the specific reference position is even in the overlapping section of sub-area III and sub-area IV in this illustrative example.

In some embodiments of the invention, a predetermined distance may be defined by the supporting apparatus. Sub-maps not in the range of the distance with respect to the reference position may be transformed bound to global constraints, while sub-maps within the range of the distance may be transformed bound to relative constraints.

It is noted that similar steps described with respect to FIG. 7 may be repeated for other reference positions. Some examples of the one or more transformations and associated reference positions for the area of interest 400 are illustrated in Table 1. In particular, Table 1 shows that for reference position 1, only the map of sub-area I needs to apply transformation 1. Therefore, transformation fields of other sub-areas may be void. For reference position 2, three transformations 2-4 are applied to sub-areas I to III, respectively. For reference position 3, three transformations 5-7 are applied to sub-areas I, II, and IV, respectively.

Some examples of constraints applied to determining the transformations are illustrated in Table 2. For instance, as shown in Table 2, transformations 2 to 4 applied to sub-areas I to III have been obtained by applying global constraints 1 to 3 to sub-areas I to III and relative constraints 1-2 for pairs of sub-areas I-II and II-III. An objective function according to the global constraints and the relative constraints may be as follows: minll

T _{l t} T ₂ where T is the optimized transformation for sub-area i, T“ is the transformation obtain by global constraint from sub-area i and T[ _j is the relative transformation obtained by relative constraint between sub-areas i and j. Table 1 - Transformation(s) associated with each reference position

Table 2 - Constraint(s) on determining transformation(s)

FIG. 8 shows an illustrative example of localization 204 and dynamic maps alignment 203.

Optionally, after obtaining the current pose, the navigation apparatus may determine a reference position that has a shortest distance to the current pose, and may retrieve the one or more current transformations based on the determined reference position. In this case, the transformation database may be pre-loaded onto the navigation apparatus before navigation.

Alternatively, the navigation apparatus may also provide the current pose to the supporting apparatus. Then, the supporting apparatus may determine the one or more current transformations based on the current pose. In this case, the transformation database may not be pre-loaded.

It can be seen from FIG. 8 that localization 204 and dynamic maps alignment 203 may be continuously executed when the pose of the device is continuously changing during navigation.

FIG. 9 shows a diagram of a method 900.

The method 900 is performed by a supporting apparatus for supporting navigation in an area and comprises the following steps: step 901 : generating one or more reference positions in the area; step 902: splitting the area into multiple sub-areas.

For each reference position, the method further comprises the following steps: step 903 : obtaining a map of a sub-area where the reference position is located and at least one neighbouring map of at least one neighbouring sub-area; step 904: determining one or more transformations; step 905: transforming one or more of the map and the at least one neighbouring map based on the one or more transformations such that the map and the at least one neighbouring map are aligned; step 906: associating the one or more transformations with the reference position; and step 907: providing the one or more transformations to a navigation apparatus.

It is noted that there is no strict execution order between step 901 and step 902. That is, step 902 may also be performed before step 901.

FIG. 10 shows a diagram of another method 1000.

The method 1000 is performed by a navigation apparatus for providing a navigation service to a device in an area. The method 1000 comprises the following steps: step 1001 : obtaining a current pose of the device; step 1002: obtaining maps of a current sub-area and at least one neighbouring sub-area based on the current pose; step 1003: obtaining, from a supporting apparatus for supporting the navigation service, one or more current transformations based on the current pose; step 1004: transforming the maps based on the one or more current transformations; and step 1005: providing the navigation service based on the transformed maps.

It is noted that the steps of methods 900 and 1000 may share the same functions and details from the perspective of FIGs. 1-8 described above. Therefore, the corresponding method implementations are not described in detail again at this point.

An application scenario of the invention may be to provide a localization service to a fleet of autonomous vehicles within a region. Each vehicle is equipped with one or more sensors such as cameras, radars, and a GNSS module. The mapping data, images and rough GNSS coordinates are collected in a crowd-sourced manner and sent to a remote server, which may be the supporting apparatus. Several computing units (or workers) have access to this server in order to retrieve and process the mapping data.

The remote server splits the region into multiple sub-areas of reasonable size, optionally according to available computing resources or complexity of sub-areas. A mapping manager dispatches several workers with mapping instructions. Each worker retrieves the mapping data from the remote server that lies within the sub-area and runs an instance of mapping algorithm to create a 2D/3D map of its own sub-area. The mapping manager and the workers may be integrated into the remote server or may be separate units from the remote server. For embodiments of the invention, it may be sufficient that the remote server obtains 2D/3D maps of split sub-areas.

Then, the remote server collects generated sub-maps from the workers and launches map stitching and transformation computation. The global constraints applied to each sub-map are the GNSS coordinates and camera poses registered in the reconstructed 2D/3D model. GNSS coordinates attached to the corresponding camera poses lead to a rigid transformation that aligns and scales the reconstructed 2D/3D model to a global frame of a corresponding GNSS position. Relative constraints between neighbouring sub-maps are obtained by registering multiple 2D/3D images present in one of the sub-map to another neighbouring sub-map. Once the same image or the same feature of two images is registered for two neighbouring sub-maps, camera poses associated with the images may be transformed to be the same, resulting in a strong relative constraint. Geo-fenced transformations are computed by taking account of global and/or relative constraints and are stored in a transformation database in the remote server.

To provide the localization service to the fleet of autonomous vehicles, sub-maps and the transformation database stored on the remote server may be uploaded to a navigation unit of each vehicle. The car pose is estimated using an Extended Kalman Filter (EKF) that fuse GNSS position and a pose obtained by a PnP algorithm. The PnP algorithm uses matches between features extracted from an image coming from one of the embedded cameras and the locally stitched sub-maps. The filtered pose predicted by the EKF is used to update the map stitching by determining the nearest reference position, retrieving associated transformation(s) from the transformation database. Optionally, the sub-maps may be updated thanks to a continuous flow of crowd-sourced data provided by the fleet of vehicles. If the geometry of a sub-map is modified after an update, the geo-fenced transformations around the sub-map are re-computed and the updated sub-map and transformation database is uploaded to the fleet of vehicles.

One benefit of embodiments of the invention is that the localization may be data-agnostic. That is, the localization based on stitched neighbouring maps may be applied to LiDAR-based localization or pure-camera based localization, which may be categorized as map-based localization.

Further, embodiments of the invention are “method-agnostic”. That is, different mapping algorithms may be used to construct the sub-maps, and different localization algorithms can be used at navigation time depending on the sub-maps nature and available sensors.

Further, embodiments of the invention do not rely on costly global alignment methods that generally do not converge to an optimal solution in case of small errors or drifts in individual sub-maps.

Further, the local map stitching and transformation computation in embodiments of the invention are robust to local map error and mapping drift. Because sub-maps alignment is computed for numerous locations on the area of interest, drift that could have been accumulated during the mapping process may be compensated when the navigation apparatus is moving.

Further, embodiments of the invention enable a faster and efficient distributed map creation. For instance, SFM algorithms commonly used in the field for creating maps do not scale well for a large number of images or points in the map. This is because bundle adjustment (BA) step needs to be performed. The BA is an operation with 0((n _c + n _p f) complexity, in which n _c is the number of cameras in the model, and n _p is the number of points in the model. Since the complexity increases cubically, a reduced size of the model because of the area splitting may have a positive impact.

Further, another benefit of embodiments of the invention is that updating and maintaining reduced-size maps of sub-areas is much easier than managing a single large-scale map of a whole area of interest. Local changes can be applied only on relevant sub-maps without impacting the whole localization system.

Further, flexibility may be introduced because different mapping data sources may be used to create maps of sub-areas.

Further, the computational resource may be saved by reusing sub-maps. For instance, if two different areas of interest share a common region, common sub-maps among the areas of interest can be shared for respective stitching procedures.

It is noted that the apparatus, including the supporting apparatus and the navigation apparatus, in the present disclosure may comprise processing circuitry configured to perform, conduct or initiate the various operations of the device described herein, respectively. The processing circuitry may comprise hardware and software. The hardware may comprise analog circuitry or digital circuitry, or both analog and digital circuitry. The digital circuitry may comprise components such as application-specific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or multi-purpose processors. In one embodiment, the processing circuitry comprises one or more processors and a non-transitory memory connected to the one or more processors. The non-transitory memory may carry executable program code which, when executed by the one or more processors, causes the device to perform, conduct or initiate the operations or methods described herein, respectively.

It is further noted that the apparatus in the present disclosure may be a single electronic device capable of computing, or may comprise a set of connected electronic devices or modules capable of computing with shared system memory. It is well-known in the art that such computing capabilities may be incorporated into many different devices, and therefore the term “device” may comprise a chip, chipset, computer (including in-vehicle computer), server, navigation equipment, radar microcontroller (MCU), advanced driver assistance system (ADAS), autonomous vehicle, drone, mobile terminal, tablet, wearable device, game console, graphic processing unit, graphic card, and the like.

The present disclosure has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed subject matter, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word “comprising” does not exclude other elements or steps and the indefinite article “a” or “an” does not exclude a plurality. A single element or another unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.