KR102847100B1 - Efficient 3D map generation method based on multi robots - Google Patents

Abstract

The efficient 3D map generation method based on a multi-robot system of the present invention comprises a step in which at least one robot independently performs 3D-SLAM to estimate its own position and simultaneously generates a 3D point cloud map, and transmits its own local position and local point cloud information to a server in real time, and a step in which the server sequentially repeats a map projection step, a feature extraction and matching step, an outlier filtering step, and a map-merge decision module execution step when converting the received 3D point cloud map into a 2D occupancy grid map each time data is received from each robot to perform map merging.

Description

Efficient 3D map generation method based on multi-robots

The present invention relates to a method for generating a map of a robot, and more particularly, to an efficient 3D map generation method based on a multi-robot system.

As the pursuit of automation and efficiency increases in modern society, interest in robotics technology is also growing. In particular, multi-robot systems are gaining recognition across various industries, as they can share tasks previously performed by a single robot.

For a multi-robot system to autonomously perform assigned tasks, Simultaneous Localization and Mapping (SLAM) technology is necessary unless prior information about the environment is available. SLAM is a key technology that enables robots to autonomously explore unknown environments and interact with various objects. It allows a robot to estimate its own position and simultaneously create a map of its surroundings. However, approaches that use a single robot to create a map of a large environment are inefficient due to factors such as sensor measurement range, battery efficiency, and time constraints.

To overcome these limitations, multi-robot SLAM is required, and in the process, a map-merging process must be performed to determine the exact position and orientation relationship between the maps of each robot and align the maps based on this to create a single map representing the overall environment.

The generated global map allows all robots to perform tasks using an environment composed of a global coordinate system, and also has the advantage of being able to establish efficient path planning for task performance by including information collected by other robots.

Major categories Subcategories explanation Direct
Map merge Robot observation information-based map merging When multiple robots meet at a designated location or by chance, map merging is performed using the relative distance and direction between the robots. Common Object-Based Map Merging When multiple robots detect the same object, map merging is performed using the information of the detected object. Indirect
Map merge Feature-based map merging Perform map merging by matching feature points of point clouds or images. Scan-matching-based map merging Perform map merging using scan matching algorithms such as ICP, NDT, etc. Spectrum-based map merging Perform map merging by extracting and matching spectral information from the map.

Table 1 shows the classification of map merging techniques.

Previous research proposed to solve 2D or 3D map merging problems is summarized in Table 1. Map merging techniques can be broadly categorized into two methods. The first is direct map merging using a multi-robot system, which includes map merging based on robot observation information and map merging based on common objects. Map merging based on robot observation information requires that each robot has a point of contact with each other, while map merging based on common objects requires that each robot detect the same object. Therefore, both methods are sensitive to the accuracy of the sensors used and are dependent on the environment.

Second, indirect map merging methods are implemented through map matching without using a multi-robot system. These methods include feature-based map merging, scan-matching-based map merging, and spectrum-based map merging. These methods commonly suffer from the drawback of being time-consuming. In particular, the scan-matching-based method, which is primarily used for 3D map merging, can converge to a local minimum during the map merging process. This necessitates the use of feature-based methods together with the scan-matching method, or the pre-implementation of a global matching technique to calculate an initial guess. This process incurs additional time consumption, making it unsuitable for real-time map merging systems.

That is, the problems can be summarized as follows.

- Defining the map merging problem

One of the key steps in multi-robot SLAM is the map merging process, which merges the map data collected by each robot into a single, unified map. This process is accomplished by calculating a transformation matrix between the maps generated by each robot. Therefore, the 3D point cloud map merging problem can be defined using a 3D transformation matrix, as shown in the equation below.

Here, t is the translation vector [△ _x ,△ _y ,△ _θ ] ^T , and R _x (α), R _y (β), and R _z (γ) represent matrices that rotate by αβγ around the x and yz axes, respectively.

- Problems with merging 3D maps

Computing a 3D map transformation matrix is significantly more computationally expensive than calculating a 2D map transformation matrix due to the number of variables to be calculated and the number of point clouds that comprise the 3D map. Because 3D point cloud maps contain hundreds of thousands to tens of millions of 3D points, using scan-matching-based methods like ICP alone incurs enormous computational costs and can lead to unreliable map merges due to convergence to local minima.

To solve this problem, a method can be used to extract feature points by calculating the relationship between points in advance, such as SHOT (Signature of Histograms of Orientations) or FPFH (Fast PointFeature Histogram), to clarify the correspondence between point clouds, or a method can be used to use an initial estimate calculated through a global matching technique, such as Quatro++ or Teaser. However, this takes additional time, making real-time calculation difficult.

KR 10-2096398 B

The present invention has been proposed to solve the above technical problems, and proposes a method for reducing computational costs and presenting reliable map merging results by converting a 3D point cloud map into a 2D occupancy grid map and performing map merging.

That is, the present invention proposes a method for projecting a 3D point cloud onto a 2D occupancy grid map and a map inspection module to solve the temporal problem of feature point-based map merging and the problem of map merging failure when performing real-time 3D point cloud map merging in an indoor environment.

The proposed method reduces the number of map merging failures, yields reliable results, and, when tested using data acquired in a real environment, takes less time than existing methods, demonstrating its suitability as a real-time map merging system.

According to one embodiment of the present invention for solving the above problem, a method for efficiently generating a 3D map based on multiple robots is provided, the method comprising: a step in which at least one robot independently performs 3D-SLAM to estimate its own position and simultaneously generates a 3D point cloud map, and transmits its own local position and local point cloud information to a server in real time; and a step in which the server sequentially repeats a map projection step, a feature extraction and matching step, an outlier filtering step, and a map-merge decision module execution step when converting the received 3D point cloud map into a 2D occupancy grid map each time data is received from each robot to perform map merging.

In addition, in the present invention, the map projection step is provided as an efficient 3D map generation method based on a multi-robot system, which includes a step of removing ceiling and floor areas based on height information defined in advance from point cloud information when generating a 2D occupancy grid map by receiving the local pose and local point cloud of the robot, and a step of projecting the point cloud from which the ceiling and floor areas have been removed into an image coordinate system through a predetermined transformation function and generating a 2D occupancy grid map.

In addition, in the present invention, the conversion function is

, x ₀ , y ₀ are the origin of the map, i and j represent the indices corresponding to the columns and rows of the occupancy map, and height, width, and resolution are the height, width, and resolution of the map, respectively. Floor function It is characterized by representing a type conversion to an integer by rounding down a real number to the nearest smaller integer.

In addition, the feature extraction and matching step in the present invention is characterized by extracting AKAZE feature points from the occupied grid map of each robot, and then matching the feature point with the smallest L2-Norm using a brute force algorithm.

In addition, the outlier filtering step in the present invention is characterized in that it calculates a transformation matrix based on pairs of feature points randomly selected within a set number of repetitions, and removes outliers by selecting a transformation that has the largest number of matching pairs within a set error when the transformation matrix is applied.

In addition, in the present invention, the Map-Merge decision module execution step is characterized in that it determines whether to merge maps by using a predefined overlap ratio threshold and overlap frame threshold.

In addition, in the present invention, the Map-Merge decision module execution step is characterized by including the steps of: calculating the smallest rectangle B _prev , B _curr among the rectangles having the respective normal values in the previous frame and the current frame as vertices, and calculating the internal area A _prev , A _curr of the corresponding rectangular shape; calculating the rectangle B _combined in the same manner from the union of the normal values of the previous frame and the current frame, and calculating the internal area A _combined of the corresponding rectangle; calculating an overlap area ratio R _overlap indicating how much the normal value of the current frame has changed from the normal value of the previous frame by utilizing the two calculated areas; and performing map-merging by considering a reliable normal value as a frame that satisfies a predetermined overlap area ratio threshold value and a continuous frame threshold value in a row.

The present invention addresses the problem of 3D map merging for multi-robot systems in indoor environments.

Because the individual maps acquired by each robot are large, 3D map merging requires significant computational time, which can degrade real-time performance. Furthermore, even within the same environment, robots' movements can vary significantly, resulting in significant differences in their individual maps, which can reduce the accuracy of map merging.

When performing map merging in an indoor environment, calculating all variables can be inefficient. Therefore, the present invention efficiently calculates the transformation matrix by converting a 3D point cloud map into a 2D occupancy grid map. Therefore, the map merging problem can be defined by reducing it to the following equation and a 2D transformation matrix.

In other words, the present invention proposes an efficient 3D map merging method that includes a feature point matching module utilizing a projected map and a map merging decision module. Experiments conducted in a real-world environment demonstrate that the proposed method reduces the time required by at least 58.68% compared to existing methods and successfully performs map merging even without initial estimates.

Figure 1 is a diagram showing the structure of a system that processes the map generation (merging) method of the present invention.
Figure 2 is an example of an occupancy grid map for each robot.
Figure 3 is a diagram showing the AKAZE feature point matching results.
Figure 4 is a diagram showing the results of outlier removal using RANSAC.
Figure 5 is a robot configuration diagram according to an embodiment.
Figure 6 is an example of the experimental environment and the movement path of each robot.
Figure 7 is a diagram showing an inlier for the map merge inspection module.
Figure 8 is a drawing showing an overlapping area.
Figure 9 is a diagram showing the results of the frame-by-frame map merge inspection module.
Figure 10 is a diagram showing the results of map creation (merging) according to the algorithm in each experimental environment.

Hereinafter, in order to explain in detail to a degree that a person having ordinary skill in the art to which the present invention pertains can easily practice the technical idea of the present invention, an embodiment of the present invention will be described with reference to the attached drawings.

Figure 1 is a diagram showing the structure of a system that processes the map generation (merging) method of the present invention.

The map generation system (1) according to this embodiment includes only a brief configuration to clearly explain the technical idea to be proposed.

Referring to Fig. 1, in a system (1) for processing an efficient 3D map generation method based on a multi-object robot,

Each robot (100) independently performs 3D-SLAM to estimate its own location and simultaneously generate a 3D point cloud map, and transmits its local location and local point cloud information to the server in real time.

Each time the server (200) receives data from each robot (!00), it sequentially repeats map projection, feature extraction and matching, outlier filtering, and map merge decision module.

The main operations of the efficient 3D map generation method based on a multi-object robot processed in a system configured as described above are as follows.

- Overall structure

The overall structure of the method proposed in the present invention is as shown in Fig. 1. The server processes data collected by each robot and can be configured as an independent system or as a leader robot within a multi-robot system.

First, each robot independently performs 3D SLAM to estimate its own position and simultaneously generate a 3D point cloud map. During this process, the robots transmit their local locations and local point cloud information to the server in real time.

Whenever data is received, the server sequentially repeats map projection, feature extraction and matching, outlier filtering, and map-merge decision module.

In the map projection process, 3D point cloud data is converted into a 2D occupancy grid map, thereby reducing the number of variables that must be processed in the map merging step.

In the feature point extraction and matching process, Accelerated-KAZE (AKAZE) feature points are extracted to calculate a transformation matrix between occupancy grid maps, and corresponding feature points between each occupancy grid map are matched.

In the outlier removal process, outlier filtering is performed using RANSAC (Random Sample Consensus) to prevent map merging performance from deteriorating due to incorrect matching that occurs during the feature point matching process.

Finally, the remaining normal values are used in the map merge decision module to determine whether to perform map merge, and map merge (generation) is performed depending on whether map merge is performed.

Below, we will examine in more detail the processes of map projection, feature extraction and matching, outlier filtering, and map-merge decision module described above.

(1) Map projection

Map projection is the process of generating a two-dimensional occupancy grid map by receiving the robot's local pose and local point cloud.

First, point cloud information removes ceiling and floor areas based on predefined height information. If ceilings and floors are included, free space and occupied space cannot be distinguished when generating an occupancy grid map, which negatively impacts feature point matching.

After that, the point cloud with the ceiling and floor areas removed is projected into the image coordinate system using the following transformation function.

That is, the point cloud and the robot's position from which the ceiling and floor areas have been removed are converted to two dimensions by removing the value corresponding to the z-axis, and are converted from the x-y coordinate system to the image coordinate system using a transformation function. The formulas below represent the transformation from the x-y coordinate system to the image coordinate system and the inverse transformation.

Here, x ₀ , y ₀ are the origin of the map, i and j represent the indices corresponding to the columns and rows of the occupancy map, and height, width, and resolution are the height, area, and resolution of the map, respectively. Floor function Indicates a conversion to integer type by rounding down a real number to the nearest smaller integer.

Figure 2 is an example of an occupancy grid map for each robot.

The positions of the robot and the point cloud after transformation are identified using the Bresenham line algorithm to identify occupied and free spaces, and based on this, a 2D occupied grid map is created, as shown in Figure 2. This process is continuously repeated while 3D-SLAM is being performed, updating each map.

(2) Feature point extraction and matching

To calculate the transformation matrix between maps, a feature point extraction and matching process of the generated occupancy grid map is performed. In the present invention, AKAZE feature points are used for feature point extraction. AKAZE feature points are faster and more noise-resistant than the existing KAZE feature points by using a nonlinear scale space, making them suitable for real-time operation. After extracting AKAZE feature points from the occupancy grid map of each robot, a brute force algorithm is used to match the feature point with the smallest L2-Norm. Figure 3 is a diagram showing the AKAZE feature point matching result. That is, Figure 3 is the occupancy grid map AKAZE feature point matching result.

(3) Outlier removal

Feature point pairs obtained through the feature point extraction and matching process may contain outliers due to the influence of dynamic objects or other factors during the map projection process. These outliers can cause errors in calculating the transformation relationship between maps and must therefore be removed.

The present invention uses the Random Sample Consensus (RANSAC) technique to remove outliers. The RANSAC process calculates a transformation matrix based on randomly selected feature point pairs within a set number of iterations. When the transformation matrix is applied, the transformation with the largest number of matching pairs within a set error range is selected to remove outliers. Figure 4 shows the results of outlier removal using RANSAC.

Looking back at the feature extraction, matching, and outlier removal described above,

The occupancy grid map generated through the map projection process is used to obtain a transformation matrix by performing feature point matching between maps. Figure 2 shows the occupancy grid map generated by each robot for feature point matching.

This system uses AKAZE feature points for feature extraction. AKAZE feature points are an improved algorithm based on KAZE feature points. AKAZE feature points utilize a nonlinear scale space, enabling faster feature extraction and greater noise robustness than the conventional KAZE feature point.

After feature points are extracted, a brute force algorithm is used to match the closest feature points based on the L2 norm. However, matching pairs may contain outliers caused by dynamic objects during the map projection process and other factors, making them unsuitable for direct map merging. Therefore, Random Sample Consensus (RANSAC) is applied to remove these outliers.

The RANSAC process calculates a transformation matrix based on randomly selected feature point pairs and then calculates the number of matching pairs that fall within a given error range when the transformation matrix is applied. This process is repeated to find the transformation matrix that provides the largest number of matching pairs and to remove outliers. Finally, the extracted normal values are used for map merging. Figures 3 and 4 show the results of feature point matching including outliers and the results after outlier removal via RANSAC.

(4) Map merge decision module

The map merge decision module uses a predefined overlap ratio threshold and overlap frame threshold to determine whether to merge maps.

Even if the normal values have been removed from outliers through RANSAC in the previous step, if the normal values from a single frame are used for map merging, inaccurate map merging results may occur due to misidentified normal values in environments with similar structures such as corridors.

To prevent this, the map merge decision module is designed to utilize consecutive frames to determine whether these normals are suitable for map merging.

First, the smallest rectangle B _prev , B _curr among the rectangles whose vertices are the normal values in the previous frame and the current frame, are calculated, and the interior areas A _prev , A _curr of the corresponding rectangles are calculated. After that, the rectangle B _combined is calculated in the same way from the union of the normal values in the previous frame and the current frame, and the interior area A _combined of the rectangles is calculated. Using the two calculated areas, the overlap ratio R _overlap , which indicates how much the normal value of the current frame has changed from the normal value of the previous frame, is calculated. An overlap ratio close to 1 indicates that the normal value of the current frame is similar to the previous frame, and a value close to 0 indicates a large difference. Therefore, if frames that satisfy the set overlap ratio threshold and the consecutive frame threshold are consecutive, they are considered reliable normal values and map merging is performed.

Table 2

Table 2 is the pseudo code of the map merge inspection module. Here, Th _ratio and Th _frame represent the overlapping area ratio threshold and the continuous frame threshold, B represents a rectangle, A represents the internal area, and R represents the overlapping area ratio. - B, A, and R represent the coordinates of the minimum rectangle that can be created including the input feature point normal value I, the area of the internal area, and the ratio of the overlapping area. - C represents the number of consecutive frames that satisfy the overlapping area ratio threshold condition, and S indicates whether the map is merged.

As described above, to perform cooperative tasks using a multi-robot system, a common map must be created. From this perspective, the advantages of the present invention are as follows.

First, a common 3D map required for a multi-robot system can be obtained in real time.

Additionally, efficient 3D map merging can be performed by converting a 3D point cloud map into a 2D occupancy grid map.

Additionally, 3D map merging can be performed without initial estimates.

Additionally, reliable 3D map merging can be performed through the map merging inspection module.

That is, the efficient 3D map generation method based on a multi-object robot of the present invention described above is,

It is processed through the map projection stage (step 1), feature extraction and matching stage (step 2), outlier removal stage (step 3), and map merge decision module stage (step 4).

The experimental results for an efficient 3D map generation method based on a multi-object robot processed in the system of the present invention are as follows.

- Experimental environment and multi-robot system configuration

This experiment was conducted in two experimental environments of different sizes, forming an intersection area to enable map merging. Figure 5 illustrates the multi-robot system used, and Figure 6 illustrates the experimental environment used and the movement paths of each robot.

The robot used is the R1 model from OMOROBOT, and the 3D LiDAR and IMU used are the VLP-16 model from Velodyne and the 3DM-GX5-AHRS model from Microstrain, respectively. For inter-robot communication, the A9004M from Iptime was used as a mesh network.

- Map merge inspection module results

Fig. 7 is a diagram showing an inlier for a map merge inspection module, Fig. 8 is a diagram showing an overlapping area, and Fig. 9 is a diagram showing the results of the map merge inspection module for each frame.

Each drawing represents the results obtained when the inter-experimental map merging inspection module was performed. Specifically, Figure 7 shows the normal feature points input to the map merging inspection module, and based on these, the overlapping area is calculated, as shown in Figure 8. Finally, as shown in Figure 9, if the ratio of overlapping areas during consecutive frames exceeds a predefined consecutive frame threshold, map merging is performed.

- Map merging results and analysis

The following describes the 3D map merging results and analysis. Measuring the accuracy of map merging is difficult due to the lack of publicly available data for map merging of multi-robot systems in indoor environments and the difficulty in deriving accurate evaluation metrics.

In the present invention, when the occurrence of a loop is determined in Loop Closure Detection, a method such as ICP is additionally used to find out the transformation relationship between nodes, and the proposed method was compared with ICP and Voxelized-ICP by referring to the fact that the transformation relationship between maps was calculated using the existing ICP.

Figure 10 is a diagram showing the results of map generation (merging) according to the algorithm in each experimental environment. In other words, Figure 10 shows the results of map merging of the comparative algorithm and the algorithm proposed in the present invention in each experimental environment.

In each figure, the blue point cloud map is the map generated by Robot 1, and the green point cloud map is the map generated by Robot 2. The ICP algorithm used is a function built into the Open3D package, and Voxelized-ICP was used by adding a voxelization process to achieve the same resolution as the proposed method during the ICP process. Furthermore, to use the same number of point clouds, all methods used the point clouds projected onto the two-dimensional plane described above.

Table 3

Table 3 shows a comparison with ICP and Voxelized-ICP.

The time required for the map merging process (Time) and the success/failure of the map merging were measured as comparative metrics, and are summarized in Table 3. The success/failure of the map merging indicates whether the method used has converged. As shown in Table 3, the proposed method reduces the time required by at least 58.68% compared to existing methods, demonstrating its suitability for real-time map merging.

In addition, as shown in Fig. 10, ICP and Voxelized-ICP failed to merge maps due to sensitivity to initial estimates, but the proposed method succeeds in merging maps even without initial estimates, thereby providing reliable map merging results.

That is, to summarize the experimental results again, referring to Figure 6, which is an example diagram of the experimental environment and the movement path of each robot, and Figure 10, which is a diagram showing the results of map creation (merging) according to the algorithm in each experimental environment,

The blue point cloud map is the point cloud map generated by Robot 1, and the green point cloud map is the point cloud map generated by Robot 2.

To compare map merging results, the present invention was compared with existing techniques, ICP and Voxelized-ICP. Comparison metrics were used to measure execution time and map merging success for each environment (Env1, Env2), which are summarized in Table 3.

The success of map merging indicates the convergence of the method used. Quantitative comparison results show that the present invention significantly reduces the time required compared to existing techniques, indicating that the present invention is more suitable for real-time map merging. Conversely, ICP and Voxelized-ICP failed to merge maps due to their sensitivity to initial estimates, whereas the present invention successfully merges maps without initial estimates, thereby providing reliable map merging results.

- conclusion

The present invention proposes a real-time map merging technique for a multi-robot system operating in an indoor environment.

The proposed technique includes map projection, feature extraction, matching and outlier removal, and map merge inspection modules, which alleviate the time problems that occur when merging 3D point cloud maps and provide reliable map merge results.

This is proven by showing that the proposed technique not only reduces the time by at least 58.68% when compared to existing methods using data acquired in a real environment, but also successfully merges maps even without initial estimates.

For reference, by taking into account the error in the quantization process that occurs during the map projection process, the proposed method can minimize the error in map merging while maintaining the temporal advantage by utilizing the structural information of the 3D plane within the overlapping area to improve the map merging performance.

As such, those skilled in the art will appreciate that the present invention can be implemented in other specific forms without altering its technical spirit or essential characteristics. Therefore, the embodiments described above should be understood as illustrative in all respects and not restrictive. The scope of the present invention is defined by the claims below rather than the detailed description above, and all changes or modifications derived from the meaning and scope of the claims and their equivalents should be construed as being included within the scope of the present invention.

100: Robot
200: Server

Claims (7)

A step in which at least one robot independently performs 3D-SLAM to estimate its own position and simultaneously generate a 3D point cloud map, and transmits its own local position and local point cloud information to a server in real time; and
The above server includes a step of sequentially repeating a map projection step, a feature extraction and matching step, an outlier filtering step, and a map-merge decision module execution step to perform map merging by converting the received 3D point cloud map into a 2D occupancy grid map whenever data is received from each robot;
The above map projection step is,
In generating a two-dimensional occupancy grid map by receiving the robot's local pose and local point cloud,
A step of removing ceiling and floor areas based on predefined height information from point cloud information;
A step of projecting a point cloud from which the ceiling and floor areas have been removed into an image coordinate system through a predetermined transformation function and generating a two-dimensional occupancy grid map;
An efficient 3D map generation method based on multi-robots.
delete In the first paragraph,
The above conversion function is,

, x ₀ , y ₀ are the origin of the map, i and j represent the indices corresponding to the columns and rows of the occupancy map, and height, width, and resolution are the height, width, and resolution of the map, respectively. Floor function An efficient 3D map generation method based on a multi-object robot, characterized in that it converts a real number to an integer by rounding it down to the nearest smaller integer.
In the first paragraph,
The above feature extraction and matching step is:
An efficient 3D map generation method based on multiple robots, characterized in that AKAZE feature points are extracted from the occupancy grid map of each robot, and then an exhaustive search (Brute Force Algorithm) is utilized to match the feature points with the smallest L2-Norm.
In the first paragraph,
The above outlier filtering step is:
An efficient 3D map generation method based on a multi-object robot, characterized in that a transformation matrix is calculated based on pairs of feature points randomly selected within a set number of iterations, and when the transformation matrix is applied, the transformation that produces the largest number of matching pairs within a set error is selected to remove outliers.
In the first paragraph,
The above Map-Merge decision module execution step is:
An efficient 3D map generation method based on a multi-object robot, characterized in that it determines whether to merge maps by using a predefined overlap ratio threshold and overlap frame threshold.
In paragraph 6,
The above Map-Merge decision module execution step is:
A step of calculating the smallest rectangle B _prev , B _curr among the rectangles having the respective normal values in the previous frame and the current frame as vertices, and calculating the internal area A _prev , A _curr of the corresponding rectangle;
A step of calculating a rectangle B _combined in the same manner from the union of the normal values of the previous frame and the current frame and calculating the internal area A _combined of the rectangle;
A step of calculating an _overlap ratio R, which indicates how much the normal value of the current frame has changed from the normal value of the previous frame, by utilizing the two calculated regions; and
An efficient 3D map generation method based on a multi-object robot, characterized in that it includes a step of proceeding with map merging by considering a reliable normal value when frames that satisfy a predetermined overlapping area ratio threshold value and a continuous frame threshold value are consecutive.