A Storage-Saving Quadtree-Based Multibeam Bathymetry Map Representation Method

Abstract

With the rapid advancement of the simultaneous localization and mapping (SLAM) technology, the collaboration of several autonomous underwater vehicles (AUVs) in large-scale seafloor imaging has become a trending topic. Electromagnetic waves are difficult to transfer underwater, the only viable method of communication is acoustic transmission, but its bandwidth is limited. Therefore, how to compress and process multibeam bathymetry maps so that AUVs can acquire maps gathered by other AUVs has become an important topic of study. This study presents a representation approach for multibeam bathymetry maps based on a quadtree structure. In comparison to the girding approach, the sparse pseudo-input Gaussian processes (SPGPs) method, and the octree-based method, the quadtree-based method suggested in this study preserves precision while compressing storage space. Experiments utilizing field data validate the performance of the proposed technique, and the method’s ability to compress storage space towards an AUV cooperative SLAM’s scenario.

1. Introduction

Autonomous underwater vehicles (AUVs) have uses in a variety of industries, including the oil and gas industry, the detection of marine life, and environmental monitoring [1,2,3]. The increasing demand for AUVs is driven by technological advancements, such as downsizing, improved processing power, and upgraded sensors [4,5]. AUVs are becoming more cost-effective and their capabilities are improving, making them a viable option for a variety of applications.

Simultaneous localization and mapping (SLAM) is a difficult topic in underwater robotics since the aquatic environment is frequently crowded and dynamic, and reliable measurements are difficult to collect [6]. Complex procedures, such as surveying targets throughout a large territory, can be completed more quickly if more working vehicles are employed [7].

The field of cooperative SLAM has made significant strides in recent years [8,9]. In contrast, the majority of cooperative SLAM research was conducted with the aid of underwater cameras or side-scan sonar [10]. Underwater visual SLAM is only successful when the AUV is operating in very clear water near the ocean floors [11]. Furthermore, the precision of cooperative side-scan sonar SLAM relies heavily on the quantity of undersea features such as manganese nodules [12]. Cooperative bathymetric SLAM based on multibeam sonar is the strategy that lends itself best to mapping and navigating underwater environments when compared to the approaches outlined previously.

The effectiveness of a underwater cooperative SLAM system is based on the quality of the communications channel [13]. Due to the fact that communication via the acoustic channel has a low bandwidth (less than one kilobit per second), high latency (because signals travel at the speed of sound, which is approximately 1500 m per second), and is even unreliable (packet loss can occur), it is extremely difficult to send a substantial amount of bathymetric data via the acoustic channel [14]. However, unlike the visual and side-scan sonar SLAM approaches, the bathymetric SLAM method lacks identifying characteristics. Therefore, it is difficult to compress bathymetric data by deleting their landmarks. Typically, octree methods are used to compress bathymetric data [15], but the quantity of data is still too high for underwater acoustic transmission; sparse pseudo-input Gaussian processes (SPGPs) approach is also employed [16], but the quality of the reconstructed map cannot be guaranteed.

Figure 1 displays a typical situation in which Multiple Autonomous Underwater Vehicles (MAUVs) are used to discover underwater locations. Several AUVs equipped with underwater positioning equipment, including inertial navigation systems, multibeam sonars, and compass sensors, investigate the target region in this scenario. AUVs can only communicate with one another using underwater acoustic modems due to the lack of electromagnetic radiation in the underwater environment. This article examines ways to compress terrain data to a file size that can be sent through underwater acoustic modems.

The contribution of this paper has two main points:

1. This paper proposed a representation approach for multibeam bathymetry maps based on a quadtree structure. The quadtree structure storage depth map is able to better recover the 2.5-dimensional model, where the depth information is represented in two dimensions (x and y), while the third dimension (z) represents the depth, of seabed terrain detection, which, in turn, makes it possible for the map to take a lesser amount of storage space. Because the method described above for converting a gridded map to a quadtree map does not result in any loss of accuracy, the possibility that AUVs would use the map for collaborative SLAM is increased.

2. In order to compare and evaluate different compression algorithms (girding approach, SPGPs method, octree-based method, and the quadtree-based method presented here), as well as the compressed storage space and accuracy, several tests have been developed. These tests utilizes retrospective simulation to play back the dataset obtained by the authors during sea trials.

2. Related Wroks

2.1. Bathymetry Data Processing

Two 1300 km tracks of SEASAT altimeter data and related bathymetry are analyzed using the linear response function technique in the Musician Seamounts region north of Hawaii [17]. An empirical method for predicting seafloor facies from multibeam bathymetry and acoustic backscatter data obtained in central Santa Monica Bay, California, has been developed [18]. White [19] investigate the effectiveness of linear and non-linear filtering techniques for removing impulse spikes from a digital bathymetry signal. The primary focus of  [20] is the compilation and editing of NOAA, individual scientists, SIO, NGA, JAMSTEC, IFREMER, GEBCO, and NAVOCEANO raw soundings. Merwade [21] discusses the effect of spatial trend on isotropic interpolation algorithms. Uunk [22] provide a fully automated method for deriving the daily intertidal beach bathymetry from video images of low-sloping beaches with intermittent intertidal bar emergence. Hasan [23] predict the distribution of benthic biological habitats by integrating backscatter angular response with MBES bathymetry, backscatter mosaic, and their derivatives in a classification process using a random forests (RF) machine learning method. Using multi-temporal satellite pictures and random forest machine learning to generate a generic depth estimate model, a method for mapping shallow water bathymetry was devised [24]. Guo used an airborne laser bathymetry (ALB) technology with digital full waveform signal collection to generate a bathymetry map from a full waveform echo signal [25]. Wang described the quantitative approach of terrain suitability and the grid parameter solution method for optimal partition of suitable matching region [26,27], which increased the precision of terrain reference navigation navigation for AUVs.

2.2. Bathymetry Data Application

Bathymetry information has numerous applications. Lyons [28] offer a method for mapping bathymetry and seagrass in shallow coastal waters by merging field survey data and high spatial resolution, multi-spectral satellite image data. Sembiring [29] demonstrate the potential use of nearshore bathymetry calculated from video data in a coastal operational model for the Dutch Coast that forecasts daily waves, water levels, and rip currents. At Thorpeness, Suffolk, UK, Atkinson [30] investigated the use of radar to derive nearshore bathymetry at a difficult site. Another important use of bathymetry data is terrain-matching navigation and bathymetry-based SALM. Ma expanded on AUV terrain matching navigation [31], while Wang introduced estimate of confidence intervals to improve navigation precision [32]. Cong [33] and Ma [34] suggested a technique for AUV path planning in terrain-aided navigation. Ma investigated the fundamentals of AUV robust bathymetric SLAM [35] and presented a multi-window consistency method (MCM) to enhance the algorithm’s resilience [36]. Zhang suggested using a particle filter for AUV bathymetric SLAM [37,38]. Ling presented an AUV active bathymetric SLAM approach [39] that allows AUVs to choose their own routes for exhaustively exploring a region.

2.3. Multi-AUVs Detection

Due to the characteristics of the underwater environment, robot communication offers several challenges [40]. Girod [41] examine an acoustic ranging system that operates effectively in the face of several kinds of interference, but returns inaccurate results in non-line-of-sight settings. Adaptive Hybrid Automatic Repeat Request (HARQ) is used to provide reliable communications in the face of connection faults [42]. Arun Kumar [43,44] proposes a kind of fog computing to improve the cloud computing of the Internet of Things, and provides a way to reduce energy consumption for multi-robot cooperative networking. Tsiogkas [45] focused on the scientific field of underwater archaeology. Remmas [46] discusses the management of a highly-maneuverable autonomous underwater vehicle for diver-tracking based on the data fusion of visual and audio signals recorded by low-cost sensors. Robotic cooperation and autonomy across many domains, autonomous mission planning, and the fusion of multi-domain data are described by Ross [47]. Hilger examined the constraints of auditory communication in this respect in the realm of multi-AUV collaborative SLAM [48]. Paull extracted landscape characteristics with an AUV equipped with side-scan sonar (SSS) [13]. Ma employed multi-beam sonar terrain data to do this [16], however employing SPGP’s approach to compress the map results in unclear map restoration problems.

3. System Definition

Considering the circumstance shown in Figure 2, the AUV bathymetric detection system is specified. This system uses AUVs equipped with multibeam echo sonar (MBES) to measure the terrain of the bottom. AUVs navigate at the same depth to ensure optimal mapping precision and vehicle coverage. $X_i(i=1,2,\dots ,N_1)$ are the states of the vehicle at consecutive instants of time i where $N_1$ is the number of states of the vehicle throughout the course of a mission. Dead reckoning (DR) systems are used to provide navigation data, including the vehicle’s control vectors $u_i^1(i=1,2,\dots ,N_1-1)$.

Bathymetric data obtained by MBES contains distances ${\beta }_j$ and angles ${\alpha }_j$ ($j=1,2,\dots ,N_b$, where $N_b$ represents the number of beams broadcast by MBES) from the MBES head to the terrain, and the measured points are the sites where the beams hit the terrain. The horizontal locations $X_i^{MP}\left[j\right]$($j=1,2,\dots ,N_b$) and terrain depths $h_i^{MP}\left[j\right]$($j=1,2,\dots ,N_b$) of measured places at consecutive instants of time i may be calculated using bathymetric measurements collected with the MBES and related navigation data.

A 3D point cloud bathymetry map obtained by an AUV is seen in Figure 3. The Eastings and Northings labels on the x and y axes reflect the geodetic coordinates used to measure location in the easting and northing directions, respectively. This map will used as an example in subsequent portions of the study.

In this bathymetric SLAM system, similar to a real multi-AUV cooperative detection situation, the sub-map incorporates bathymetric data and vehicle statuses, which the AUVs utilize for SLAM to produce exact maps while self-locating. Specifically, a sub-map comprises of a vehicle’s local trajectory plus a collection of swaths, with each swath including a significant number of measured points. The kth sub-maps created by the AUV are designated as $m_k^1$ ($k=1,2,\dots ,M_1$), where $M_1$ is the total number of sub-maps created by the AUV. When a vehicle creates a new sub-map, it will broadcast this sub-map using acoustic packets, and another vehicle will identify loop closures between this sub-map and all past sub-maps by recording these packets. After acquiring these loop closures, AUVs will complete SLAM using graph optimization algorithms or filtering algorithms.

4. Bathymetry Map Representation Method

4.1. Girding Approach

The Girding methodology has been thoroughly developed, and there are already numerous effective solutions. In the process of translating a point cloud map into a girding map, interpolation methods, such as Inverse Distance Weighting (IDW) [49], Kriging [50], and Natural Neighbor Interpolation (NNI) [51] are often utilized. Using these techniques, the values of girding map cells are approximated based on the values of surrounding points within the point cloud data.

Figure 4a is a girding map converted from the test map (Figure 3) using the girding approach. Figure 4b is the contour map obtained from the girding map (Figure 4a).

The girding technique can describe terrain depth maps fast and precisely, and it plays a significant role in the area of map storage. However, for the scenario of multi-AUVs cooperative detection, there is a greater need for storing space owing to the constraint of bandwidth. The girding map must be further compressed before it can be used, since its storage space is quite vast.

4.2. Sparse Pseudo-Input Gaussian Processes (SPGPs) Method

The sparse pseudo-input Gaussian processes (SPGPs) registration approach is used for registration and prediction by building an SPGPs model using historical data. Set of input points used to approximate the function being modeled by the Gaussian process. Instead of utilizing all of the training dataset’s input points, a subset of pseudo-points is chosen to represent the whole dataset. These pseudopoints are selected to offer a decent approximation of the function being modeled while minimizing the model’s computing expense. In contrast to conventional Gaussian processes registration (GPR) approaches, the SPGPs model is trained using just a limited number of pseudo points that retain the majority of the sub-map’s information, as opposed to all previous bathymetric data. Sub-maps may be sent if an AUV compresses the sub-map into certain pseudo points and calculates the hyperparameters of the SPGPs model associated with the sub-map, then the compressed sub-map is rebuilt in other AUVs.

The pseudo-point selection of SPGPs and associated theoretical derivation are available in Ma’s article [16], thus they will not be duplicated here. Algorithm 1 is a proposed map compression algorithm utilizing SPGPs.

Algorithm 1 Compression of Seafloor Terrain Maps using SPGPs

Require: Seafloor terrain maps, Pseudopoints

Ensure: Compressed terrain maps

1: Train the SPGPs model using the pseudopoints

2: Compute the mean and covariance function for each terrain map

3: Predict the terrain maps based on the mean and covariance function

4: for each terrain map do

5:  Compute the difference between the predicted terrain map and the actual terrain map

6:  Store the difference in a separate variable

7: end for

8: Compress the difference variable

9: Store the compressed difference variable along with the mean and covariance function for each terrain map

10: return The compressed terrain maps

Figure 5a depicts the recovered map of the seafloor in the test map (Figure 3), which was compressed using the SPGPs approach. Figure 5b is the contour map obtained from the recovered map (Figure 5a). In this scenario, 150 pseudo-input points are chosen. It is evident that the original map’s elevation change has been maintained, and that employing 150 points and hyperparameters to express the map may significantly minimize the amount of storage space required. However, this approach has the drawback of being a lossy compression method. A approach that is not only capable of lossless compression but also requires a modest amount of storage space may improve SLAM across various AUVs.

4.3. Octree-Based Method

The octree space occupancy approach for describing seafloor terrain maps is based on the concept of hierarchical spatial division. The octree approach breaks 3D space into progressively smaller cubes or octants, until each octant is tiny enough to reflect the terrain map’s depth. The octree map depicts the depth of the seabed topography via the occupancy of the three-dimensional space of the seabed.

In this approach, spatial partitioning is accomplished recursively, beginning with a single big cube that completely encloses the terrain map. The cube is then subdivided into eight smaller octants, each of which may be further subdivided if necessary. The leaf nodes of the octree structure hold data about the space filled by the seafloor terrain, whereas the non-leaf nodes store data regarding the occupancy of their children. Algorithm 2 depicts the algorithm flow.

Depending on the required resolution for a given application, several stop criteria may be configured. The objective of this research was to accomplish lossless compression of the gridded map, hence the stop criterion for the octree approach was set equal to the grid map resolution.

The octree space occupancy map created by the test map is shown in Figure 6. When the voxel size of the octree map is sufficiently tiny (the same as the resolution of the girding map), it may be considered a lossless compression of the girding map. However, the map consumes a storage space of 10.8 kb, which surpasses the amount of data that AUVs can send in the time it takes to construct a submap (The bandwidth of high-performance underwater acoustic modems carried by the majority of AUVs is around 1000 bits per second. A data transfer of 10.8 kb per submap, which is equal to $10.8\ast 1024\ast 8=$ 88,473 bits and requires 88.47 s if sent by an AUV. Every 40 s, a new submap is formed, hence 10.8 kb is too huge to be sent by the existing AUVs). Therefore, this compression approach is not optimal for sharing maps between AUVs.

Algorithm 2 Octree spatial occupancy method for representing seafloor terrain girding maps

Require: Seafloor terrain girding maps, voxel size, maximum tree depth

Ensure: The compressed octree representation of the seafloor terrain

1: Convert each girding map into a voxel grid with the specified voxel size

2: Initialize an octree with the maximum tree depth

3: for each voxel in the voxel grid do

4:   if the voxel is occupied then

5:   CAdd the voxel into the octree

6:   end if

7: end for

8: Prune the octree by removing empty voxels and merging nearby occupied voxels

9: Compress the octree by encoding the information of each node into a compact representation

10: return The compressed octree representation of the seafloor terrain

4.4. Quadtree-Based Method

A two-dimensional area is subdivided into four subregions according to the notion of describing seafloor topography maps using a quadtree structure. A node represents each subregion in the quadtree structure. This hierarchical technique efficiently represents sparse data by saving just the nodes that contain relevant information.

For terrain data, as illustrated in Figure 7, the top-down building strategy is utilized. First, the whole landscape is treated as a node C0, which is at the minimum separation rate level. Divide into four child nodes C1, C2, C3, C4 of identical size; and the C1 node may be segmented into C5, C6, C7, C8.

The number of data blocks rises with two to the $2n$th power, where n is the number of levels, as seen in the block hierarchical organizing technique (Figure 8). If there is a data block $a\_b$ in the kth layer, then the following formula may be used to determine the number $Num{F}_k$ of all data blocks in the corresponding l ($l>k$) layer:

$$Num{F}_k=2^{2\times (l-k)}$$

(1)

Additionally, the names of the data blocks at the four corners of the l ($l>k$) layer corresponding to $a\_b$ are $A_1\_B_1$, $A_2\_B_2$, $A_3\_B_3$, and $A_4\_B_4$, determined using the following formulas:

$$A_1=a\times 2^{l-k}+2^{l-k}-1,B_1=b\times 2^{l-k}$$

(2)

$$A_2=a\times 2^{l-k}+2^{l-k}-1,B_2=b\times 2^{l-k}+2^{l-k}-1$$

(3)

$$A_3=a\times 2^{l-k},B_3=b\times 2^{l-k}$$

(4)

$$A_4=a\times 2^{l-k},B_4=b\times 2^{l-k}+2^{l-k}-1$$

(5)

As seen in Algorithm 3, the premise of employing a quadtree approach to record seabed terrain maps requires encoding the maps as a hierarchical data structure in which each node corresponds to a square region on the map. The tree is formed by splitting the map into four squares of equal size, which serve as the current node’s children. This procedure is repeated until each leaf node represents a single square with identical seafloor terrain depth. Since the quadtree structure is separated into two-dimensional planes to store data, it resembles the 2.5D structure of the seabed topographic map, making it a more suitable way for map expression. In essence, the quadtree approach used in this work offers an alternate representation of a 2.5D grid-based map. The compression resolution is identical to that of the original gridded map, and so is the depth of each point in the resultant map. Thus, it is a form of lossless compression.

Table 1. Comparison table of the four algorithm.

Algorithm	Advantages	Disadvantages	Computational Complexity	Data Storage Requirement
Girding approach	Easy to understand and implement.	Requires more storage space and may result in lower accuracy.	Low	High
SPGPs method	Able to significantly reduce storage requirements.	Computationally intensive and may require more training data.	Medium	Medium
Octree-based method	Allows for variable resolution, reducing storage requirements.	May result in higher computational requirements.	High	Medium
Quadtree-based method	Able to better recover the underwater terrain 2.5-dimensional model.	May result in higher computational requirements if girding maps are losslessly compressed.	Medium	Low

summarizes the four algorithms from the theoretical level, including advantages and disadvantages, computational complexity and data storage requirement.

The quadtree representation map created by the test map is shown in Figure 9. When the precision of the leaf node and the girding map are same, it may be considered a lossless compression of the girding map, similar to the octree map. In certain large regions with the same depth, the area is expressed by one or several large nodes, therefore conserving storage space. In certain huge regions with the same depth, the area is expressed by one or more large nodes, therefore conserving storage space. The map requires just 1936 bytes of storage space, allowing for its transmission.

Algorithm 3 Quadtree representation of seabed terrain grid maps

Require: Terrain grid maps

Ensure: Quadtree representation of seabed terrain grid maps

1: Initialize quadtree structure

2: for each cell in the grid map do

3:  Assign cell value to corresponding node in quadtree

4:  Check if cell value satisfies subdivision criteria

5:   if subdivision criteria is satisfied then

6:   Subdivide node into 4 child nodes

7:   end if

8: end for

9: return Quadtree representation of seabed terrain grid maps

5. Experiments and Settings

5.1. Datasets

This section utilizes information from an experiment performed at sea near Qingdao, China. As shown in Figure 10, a vessel equipped with multibeam sonar and INS devices was used to collect data from the East China Sea (Figure 11).

Using two GNNS receivers of the XW-GI5651 INS/GNSS integrated navigation system mounted in the longitudinal portion of a vessel, the GPS trajectories of the vehicle were acquired. Using the system, the heading, pitch, and roll angles were measured with angular accuracies of O($0.1deg$), O($0.01deg$), and O($0.01deg$), respectively, at a frequency of 4 Hz.

In order to acquire bathymetric data, a shipborne T-sea CMBS200 MBSE operating at a frequency of 4 Hz was used. This sonar has a working bandwidth of 40 kHz and a center frequency of 200 kHz. It has a horizontal beamwidth of more than 1 degree and a vertical beamwidth of more than 2 degrees, both of which are remarkable. Horizontal field of vision larger than or equal to 140 degrees; detection range greater than or equal to 300 m; and distance resolution greater than or equal to 2 cm. In the experiment, 101 submaps were employed, including the test map used before (Figure 3).

5.2. Map Compressing

In this work, we will assess the efficacy of four distinct compression techniques for displaying submaps of seabed landscape. In total, 101 maps have been chosen for compression testing. The objective is to evaluate and determine the most economical and effective compression technique for portraying complicated and high-resolution seabed landscape data. To guarantee a fair and thorough assessment, we will measure the performance of each technique using encoding time and storage utilization.

This research used a computer platform with the following specifications: an AMD Ryzen 3700X CPU, an NVIDIA GeForce RTX 2060 Super GPU, and 32 GB of DDR4 memory. This setup is adequate for the computing requirements of this study’s activities and is capable of giving dependable and efficient performance for the compression of seabed terrain maps. In addition, the machine is equipped with a 64-bit operating system and adequate storage space to support the datasets used in this research.

Under the multi-AUV cooperation situation, the robot will transmit the obtained submap. The acquisition time for each of the 101 submaps in the dataset is an average of 39.9 s, totaling 4030.5 s. Combining the performance of the already prevalent AUV underwater acoustic transmission modem (1000 bit/s), we determined the qualification line for the size of a single sub-map file after map compression to be 40,000 bit, or 5000 byte.

6. Results

In the experiment, 101 submaps were compressed using four different algorithms (Girding, SPGPs, Octree, Quadtree).

In addition to the previously used test map (Figure 3), the test results of three maps (No. #74, #80, and #98) are shown as examples in Figure 12, Figure 13 and Figure 14, respectively. It can be shown that, as predicted in the theoretical section, all four approaches can represent the seabed terrain depth map extremely effectively, among which SPGPs is a lossy compression, while the octree method and the quadtree method are lossless compression of the girding map.

In terms of disk space savings, the four methods vary significantly. According to Figure 15 and

Table 2. Statistical information on the volume of disk space occupied by four algorithms.

Algorithm	Average Value [byte]	Maximum Value [byte]	Minimum Value [byte]	Median Value [byte]
Girding approach	17,100	33,522	7113	15,882
SPGPs method	1850	1850	1850	1850
Octree-based method	9848	22,331	3834	8722
Quadtree-based method	2571	5293	1429	2595

, the average space consumed by the four methods is 1 kilobyte, 2 kilobytes, 1 kilobyte, and 1 kilobyte, respectively. In the preceding section, a qualifying line was given in each submap of 5000 bytes, or 5 kb; hence, in multi-robot cooperation situations, only maps generated using SPGPs and quadtree map representation techniques may be sent out.

7. Discussion

Using improved techniques for underwater mapping has been a major field of study in recent years. The fundamental reason for selecting this subject was to improve the effectiveness of multi-robot cooperation for underwater research. By deploying numerous robots to collaborate, a larger area may be mapped in less time, and the mapping process as a whole can be quickened.

The approach presented for underwater mapping employs the quadtree structure. This approach may be used to compress maps, making it perfect for settings with limited storage capacity. Unfortunately, the quadtree structure technique, like the SPGPs method, has a significant computational cost.

This approach achieves lossless compression on the girding map since the same resolution as the girding map is employed. In other words, map reconstruction errors stem from the rasterization process and not the compression strategy. Experiments indicate the efficiency of the compression.

Considering the viability of using both techniques for deep-sea exploration, both techniques may be used with certain considerations. For instance, underwater communication is possible using acoustic modems. Nevertheless, the performance of these modems must be considered to guarantee that the maps can be sent between AUVs effectively. In addition, the high computational cost of these approaches may not be a serious concern in deep water research since newer AUVs are equipped with strong processors capable of performing complicated computations.

8. Conclusions

In this study, a representation method for multibeam bathymetry maps based on a quadtree structure was developed. The following conclusions can be drawn:

1. The bathymetric map of the seafloor may be compressed and restored using the suggested quadtree structure-based method.

2. This approach requires less disk space than the existing method and can also assure map accuracy. The average size of the 101 sub-maps employed in the experiment is 2571 bytes, making it feasible to transfer maps across AUVs.

By using offered techniques for underwater mapping has the potential to considerably improve the effectiveness of underwater exploration. Although the suggested approaches provide a number of benefits, including a reduction in map storage needs, the high computational cost may be a disadvantage. Additionally though, with the developments of AUV technology and underwater communication, these techniques may be used to explore the deep oceans.

In future study, we will examine the performance of multi-AUV collaborative SLAM systems after transmitting compressed maps using this compression approach, as well as other relevant studies.