{'fraction_non_alphanumeric': 0.029654985426692877, 'fraction_numerical': 0.0046431234325221985, 'mean_word_length': 4.851080705929011, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Underwater inspection using sonar-based volumetric submaps

We propose a submap-based technique for mapping of underwater structures with complex geometries. Our approach relies on the use of probabilistic volumetric techniques to create submaps from multibeam sonar scans, as these offer increased outlier robustness. Special attention is paid to the problem of denoising/enhancing sonar data. Pairwise submap alignment constraints are used in a factor graph framework to correct for navigation drift and improve map accuracy. We provide experimental results obtained from the inspection of the running gear and bulbous bow of a 600-foot, Wright-class supply ship.

visibility conditions: with increased turbidity (common in harbors and near-shore environments), the range of optical sensors decreases, negatively impacting their coverage rate, if not preventing their operation altogether. This limitation has been addressed successfully in the context of ship hull inspection by utilizing an imaging sonar-again in a feature-based smoothing approach [2]. A common aspect to these techniques is that both target the smooth sections of the hull-the underlying assumption being that these are sufficiently smooth so that local planar approximations can be made, onto which features can then be registered. This is not a limitation of either technique, but rather, of the sensor used (imaging sonars, for instance, have an inherent elevation ambiguity). Geometrically complex scenes, such as a propeller, break this assumption and require us to use other sensors. While optical sensors are available that let us circumvent this limitation, such as ranging lasers based on either time-of-flight or structured light, they're often very costly and still subject to visibility issues, precluding their use in many man-made environments. Instead, their functionally equivalent acoustic counterparts, single-or multibeam sonars, are often used for underwater mapping of more complex scenes.
Some of the earliest work on underwater mapping used both ship-and ROV-mounted multi-beam sonars to create bathymetric maps and inspect ship wrecks [3]. The sensor model utilized took into consideration not only the finite width of a sonar beam, but also the uncertainty associated with the vehicle pose, making evidence grids especially attractive. More recently, a vehicle equipped with singlebeam sonars was used to inspect and map flooded sinkholes [4]. The 2D SLAM technique used in that application relies on particle filters and a specialized occupancy grid implementation that is amenable to the high number of operations associated with particle filter techniques.
Due to the nature of the measurements taken by these single-and multi-beam sonars, the direct use of featurebased techniques (i.e. on individual measurements) is limited. Similar to side-scan sonars, multi-beam sonars return echo intensities along rays cast from the sensor, in a plane normal to the vehicle's trajectory (i.e. a grayscale image in polar coordinates), resulting in no overlap between subsequent measurements. This, together with the apparent lack of "featurerichness", severely limits the use of "dense" techniques such as the ones previously mentioned. Submap techniques address this limitation by accumulating measurements in a higher level map representation over some limited time interval.
Small ROVs equipped with mechanically swept sonars have also been used to map man-made structures. One approach has the ROV hover in place while the sonar assembles a full 360-degree, two-dimensional scan of its surroundings, from which line features are extracted and utilized as landmarks in a filtering (EKF) context [5]. Alternatively, scan-matching techniques can also be used to obtain relative pose measurements [6]. This is of particular interest for applications in less structured environments, such as the inspection of ancient water cisterns [7]. In this last example, a complete 2D map is built from pairwise registration of scans. To mitigate the motion-induced errors associated with hovering, the ROV lands at the bottom of the cistern before sweeping the sonar to assemble a scan. Submap-based methods have also been successfully applied to the problem of bathymetric mapping [8]. Registered multi-beam returns are assembled into submaps, which are checked for "richness" and consistency/drift. Like the previous examples, pairwise submap registrations-obtained through use of 2D correlation and Iterative Closest Point (ICP) algorithms-are incorporated in an EKF as relative pose measurements. A similar submap technique has also been proposed in the context of ship hull inspection, replacing filtering with smoothing by integrating pairwise registrations as loop-closure constraints in a factor graph [9]. Finally, note that other submap techniques that deal with "dense" approaches are also available in the literature-see, for instance, Tectonic SAM [10], where submaps are created by partitioning a pre-existing factor graph, and the Atlas framework [11], which aims at reducing computational effort by limiting the complexity of individual submaps.
The aim of this work is to develop a mapping technique able to produce a map of a complex underwater structure with centimeter-level resolution. This resolution requirement stems from the features of interest in the ship hull inspection scenario, which have characteristic dimensions on the order of a few centimeters to a few tens of centimeters. Additionally, it is desirable that such a framework can be run in real time, either due to the time-critical nature of some of ship hull inspection tasks, or so that the map can be used by an ROV operator for navigation. Finally, our focus lies on mapbuilding using only sonar data for sensing, for the reasons mentioned above.
Our proposed approach builds upon previous work on submap-based mapping by combining the submap partitioning techniques of [8] with a pose graph framework similar to that of [9]. Moreover, we replace the direct registration of sonar returns-common to both approaches-with the use of volumetric techniques, preceded by enhancement and classification of sonar data. This increases robustness to outliers and classification errors, reducing the need for smoothing or filtering of submaps and improving the overall map quality.

II. PROBLEM STATEMENT
The problem at hand, as previously mentioned, is that of inspecting underwater structures with complex geometries (e.g. curved surfaces, non-convexities, sharp edges, etc.). To accomplish this task, we assume that a hovering AUV/ROV is used. These vehicles are typically equipped with the "standard" navigation payload, comprising a Doppler Velocity Log (DVL), an Attitude and Heading Reference System (AHRS), and a depth sensor. By utilizing the attitude estimate from the AHRS, the DVL's measurement of bottom-relative velocity in body frame coordinates can be projected ontoand integrated in-the world frame. When combined with the AHRS output, this constitutes a full 6DoF pose estimate; nevertheless, actual implementations will often replace the z estimate obtained through integration with the direct measurements available from high accuracy depth sensors. Furthermore, the use of tactical grade inertial measurement units in the AHRS results in roll and pitch accuracies of better than 0.1 • , reducing the pose estimation problem from 6 to 3 degrees of freedom (x, y, and ψ). However, unlike the AHRS roll and pitch estimates, the yaw estimate is not driftfree. While this can be mitigated through the use of an aiding sensor such as a compass, this is not always desirable, particularly when working in the proximity of metal structures such as a ship hull. As a result, the horizontal pose estimates provided by these systems are bound to drift over time. As indicated in the previous section, inspection platforms often carry a multibeam sonar as part of its primary payload. These sonars comprise an array of transducers that produce one or more narrow beams that sweep within a plane to create a scan (figure 1). The number of beams and their horizontal (i.e. "in-plane") beam width determine the sonar's horizontal field of view 2 and angular resolution. Range resolution is determined by the timing characteristics of the receiving circuit (longer time bins will yield lower radial resolution and vice versa). Typical values of a few hundred of beams, beam widths of 1 • or less, centimeter-level range resolution, and typical ranges on the order of a few tens of meters make them excellent sensors for underwater mapping, capable of providing high-resolution scans at large stand-off distances. Multi-beam sonars often output their measurements as a 2D array, where each element corresponds to the return intensity for that particular range and angle bin-essentially an image in polar coordinates (see figure 3(a) for an example of a sonar image after conversion to Cartesian coordinates).
Since our objective is to produce a map with a resolution such that objects of a certain size can be identified, we must then ensure that the uncertainty associated with the mapped sonar returns or features remains bounded and below the required resolution. This requires (i) robust classification/detection of valid sonar returns, (ii) accurate (short-term) registration of those returns, and (iii) long-term position accuracy through drift correction.

III. SUBMAP CREATION
Our submap creation pipeline can be summarized as follows (figure 2): we begin by enhancing the incoming sonar data, with the aim of reducing some of the most significant systematic errors present in the data. This makes range extraction-the second step in our approach-much more reliable, seeing as there are less outliers in the data. Having extracted and registered the sonar ranges, they are inserted into an occupancy grid to build volumetric submaps, which are then converted into point clouds and filtered before being handed over to the SLAM module (section IV).

A. Data Enhancement
Like any sensor, multibeam sonars are not free from either random or systematic error. Random error is caused both by the acoustic noise in the environment and electronic noise in the transducer and signal processing circuitry. Systematic error manifests itself in several different ways, and can be traced to a combination of causes, including non-zero beamwidth, cross-talk, vehicle motion, and multi-path scattering [12]. Figure 3(a) shows a corner of a tank, as seen by the multibeam sonar used in our experiments (covered in greater detail in section V). There we observe both noise and the artifacts caused by the different error sources: angular and radial blur due to the non-zero beam-width; a mirror image of one of the walls caused by multi-path scattering, and crosstalk between transducer beams resulting in the curved ("arc"-like) feature. Considering that range extraction will rely on intensity values from the sonar scan, it is thus highly desirable to mitigate these effects as much as possible.
Our approach to this problem is to model the sonar as a linear, time-invariant (LTI) system, where the output image y is the result of a convolution between the ideal image x and the sonar impulse response h, under additive noise n(r, θ): If this model holds, we can then try to identify the sensor impulse response (also known as point spread function, or PSF, in the context of imaging systems), and deconvolve the image using a two-dimensional Wiener filter [13]. To model the PSF, however, we must first understand how the sonar forms an image.
To reduce cross-talk artifacts, the DIDSON fires its 96 transducers in a staggered fashion-it takes 8 cycles, each firing 12 transducers, to form a complete image. This strategy limits cross-talk to the beams firing in the same cycle, which, despite being separated by 7 inactive transducers, are still "sensitive" to each other, as can be seen from figure 4.
If we assume the other transducers in the array have the same beam pattern, then the PSF can be obtained by sampling the beam pattern at the angular positions of the other transducers firing in the same cycle. Note that this approach has some limitations in the sense that it (i) only captures the angular component of the PSF, and, (ii) assumes the PSF is isotropic. While addressing the former assumption would likely require some prior information about the scene being mapped, we can at least account for the angular dependence of the PSF by pre-multiplying the sonar image by an angle-dependent function to account for the fact that the beam pattern for a transducer, while keeping the same overall shape, decreases in amplitude as we move away from the center of the array. A similar approach is used to compensate for the radial decay in return intensity, by modeling both geometric and absorption losses. The results of this enhancement step are shown in figure 3.

B. Range extraction
Having enhanced the sonar image, the next step is to classify it, that is, to detect the presence (or absence) of objects in the current scene. We follow a standard technique [5], [9], [14], [15] for multibeam sonar data by selecting, for each beam, either the first or the strongest return that is above a certain threshold. For the i th detected return, at coordinates (r i , θ i ), the 3D position of the return in the sonar frame is obtained by conversion to Cartesian coordinates: x s = [r i cos (θ i ), r i sin (θ i ), 0] T . Using homogeneous coordinates, the location of that return in the global frame is where T v s is the (fixed) transform describing the sonar pose in the vehicle frame, and T g v is the vehicle pose estimate in the global frame, obtained from the navigation solution.

C. Volumetric mapping
Despite the improvements in return selection obtained through the enhancement of sonar data, the classifier still has non-zero probabilities for both false positives (false detections) and false negatives (missed detections). This can be further aggravated by the presence of bubbles, suspended sediments, and fish schools, which, due to the strong sonar returns they produce, will also be registered, effectively resulting in outliers. In order to mitigate the undesirable effects of such outliers, we use probabilistic volumetric techniques, where instead of registering returns, we update the occupancy probability for the region of space where that return lies. These techniques have the additional advantage that they let us use negative information-that is, we can use the knowledge that the space between the vehicle and the return is empty to update the occupancy probability for the regions traversed by the beam. To compensate for the nonzero beam width and height of the sonar beams, we have extended the OctoMap library [16] to support sonar beam insertion-this allows us to implicitly model some of the angle uncertainty associated with a sonar return and, since a larger number of voxels have their occupancy probabilities updated, obtain denser submaps.

D. Point clouds and filtering
Once a submap has been assembled, it is transformed to a point cloud by thresholding: for each voxel whose occupancy probability exceeds a user-defined level, a point is added to the corresponding point cloud, with its coordinates being equal to the center of the voxel. Since some outliers will still make their way through the volumetric submapping module, subsequent filtering is often necessary. For this purpose we employ a clustering-based filter: points are first grouped into clusters based on each point's distance to their nearest neighbours(s), and small clusters (below a given number of points) are then removed. The motivation for this filter stems from the observation that these "persistent" outliers are, in fact, the result of creatures and/or objects (e.g. fish, bubbles) that remain in the sonar's field of view over the course of a few frames, leaving a small, sparse cloud of points in their wake.

E. Submap span
On the one hand, submaps should be large enough so as to have enough geometric features that allow for a submap to be registered against another; on the other, a submap must be short enough that the accumulated odometry error is small. Under linear motion at constant depth, and given measurement covariances of (σ 2 x , σ 2 y ) for the horizontal velocity and σ 2 ψ for the yaw angle, the pose covariance after T i seconds is The two main assumptions in the equation above-linear motion and reduction to 3 dimensions-will be addressed in greater detail in the following sections.

IV. 3D SLAM
Using range measurements extracted from enhanced sonar scans, we have assembled a sequence of submaps connected by odometry-based relative pose estimates. Knowing that these estimates are not drift-free, if we want to improve navigation performance and map accuracy we must leverage the information contained in the submaps. As we have previously mentioned, one way to do this is through pairwise submap registration: for any submap pair for which there is scene overlap, we can obtain a new relative pose constraint by aligning the two so that these match in the overlapping area. While this can be a better estimate of relative pose, this is not always the case, especially for submaps with small overlap and/or simple geometries (e.g. mostly planar). As we obtain more of these estimates, we arrive at an optimization problem where we must try and find the pose estimates that best fit both odometry and pairwise registration constraintswe tackle this problem using a factor graph approach.

A. Factor graph
At every instant t i , a new pose estimate x i and sonar scan S i are available 3 . The relative pose between two subsequent scans can be written as: This can be represented as a factor graph, where each pose estimate x i is associated with a node, and odometry constraints u i,i+1 are represented as edges connecting the nodes for poses x i and x i+1 . The assoicated covariance, Σ i , can be determined using equation (3). At this point, the (acyclic) factor graph represents what is known as an "odometry chain" (figure 5), and the value of each pose can be obtained through composition of odometry constraints.

B. Submapping in a factor graph perspective
In this factor graph representation, each node is implicitly paired with the measurements taken at that instant-in our case, the sonar scans. For the reasons listed in section I, these are rarely informative enough that loop closure information can be extracted from a pair of scans; instead, subsequent scans are "accumulated" into a finite set (represented by the colors in figure 5(a)), so that constraints can then be obtained by pairwise analysis of these sets. This "accumulation" process-the assembly of volumetric submaps from individual sonar scans, introduced in section III-C-can be described as the registration of all sonar scans in one submap, in the frame of the first pose of that submap: the base pose ( figure 5(b)). The edges connecting the base poses of submaps j and j + 1 are obtained by composition of the odometry constraints of the poses associated with submap j.

C. Pairwise registration
At this point we have arrived at a higher-level odometry chain, where each base node is associated with a submap instead of a sonar scan (figure 5(c)); still, if navigation performance is to be improved, additional constraints need to be added to the factor graph. While detection and matching of 3D features (such as planes) from submap pairs may be a feasible technique, we intend to keep our technique capable of dealing with both structured and unstructured environments-thus, we use scan matching to derive these loop closure constraints.
Once a new submap is assembled, we begin by identifying potential matches by finding other submaps with which it overlaps. For each potentially matching submap a transformation estimate is computed through ICP [17], [18]. Since all points in each submap are referenced to its base pose, we compose the odometry constraints connecting the two nodes to arrive at the initial transformation estimate. Having obtained a transformation estimate o ij for the alignment between submaps S i and S j , we use the resulting score, as well as the time difference between submap acquisitions, to provide us with some guidance on its acceptance (e.g. the greater the time difference, the greater the threshold on the difference between odometry and ICP transformations, as more drift is likely to have been accumulated). Given a process model x i = f (x i−1 , u i−1 ) subject to additive white Gaussian noise (AWGN) w i with covariance, and a measurement model o jk = h(x j , x k ), also under AWGN v jk , we want to find the maximum a posteriori (MAP) estimate X = {x 1 , . . . , x N }: 5. An overview of our submapping technique from a factor graph perspective: the starting graph (a) for the robot trajectory has each pose x i connected to the next pose x i+1 by an edge u i,i+1 (odometry constraint) with associated covariance Σ i ; poses are grouped into submaps, with the corresponding base poses replacing the originating poses (b); finally, pairwise constraints are added between base poses whose corresponding submaps have been co-registered (c). Note that the covariance matrices associated with each edge are not represented. where Λ i is the covariance matrix for the process model noise, and O is the set of all tuples (j, k) for which a pairwise registration constraint o jk has been added between x j and x k , with associated covariance matrix Γ jk . We use iSAM [19] to solve this optimization problem and obtain updated base pose estimates x i . The final map is constructed by merging all submaps once their base poses have been replaced with the updated values.

V. EXPERIMENTAL RESULTS
In this section we begin by briefly describing the inspection vehicle and its navigation and sensor payloads before going over the results obtained for the two datasets.

A. Platform
In our experiments we use the Hovering Autonomous Underwater Vehicle (HAUV) [20] from MIT/Bluefin ( figure  6). It is equipped with five rim-driven thrusters that make it The HAUV's primary payload is a dual-frequency identification sonar (DIDSON) [21], which we use primarily in its high frequency (1.8MHz) mode, as it provides greater detail. It has a total of 96 beams, each with 0.3 • of horizontal beam width. Since we are interested in complex geometries, we make use of a concentrator lens, reducing its vertical field of view from the standard 14 • to 1 • (-3dB values). While its range resolution depends on the minimum and maximum range configuration, a typical window of 9.5 meters will yield a resolution of better than 2 centimeters.

B. SS Curtiss dataset
This dataset covers the inspection of the complex areas of the SS Curtiss: the running gear (rudder and propeller) and the bulbous bow (highlighted areas in figure 7). Both datasets were acquired while performing "coarse" surveysessentially a vertical lawn-mower pattern (i.e. constant depth transects) designed to rapidly create a map for the purposes of situational awareness. This is of particular use on unseen ships or structures, before any close-in inspection is performed. Since resolution is not as important as coverage and coverage rate, the vehicle is deployed with the sonar scan plane parallel to the hull's longitudinal cross-section plane. Submap duration was chosen to be equal to 30 seconds, which, for the performance specifications listed in table I, corresponds to a horizontal uncertainty of approximately 0.02m and 3 • (1σ values). Finally, the results shown were obtained in real time while performing inspection. Submap coverage for the running gear (a) and bulbous bow (b) datasets (each colored patch represents a submap). The maps span approximately 45 and 39 meters, respectively. Map height is roughly equal to the ship's draft: 9 meters. minutes) cover one side of the running gear. However, the relatively fast coverage rate is not without disadvantages: the complex geometry of the propeller is poorly represented as the propeller is not imaged from its front or back, resulting in sparse coverage of each blade. Unlike the hull and rudder, which are nearly normal to the incident sonar beams, propeller blades are ensonified at shallow angles, resulting in increased radial uncertainty in the sonar returns.
Despite the relatively short duration of this inspection run, there is still a significant amount of drift in the vehicle's horizontal position estimates. This is especially evident on the forward and aft edges of the map: the rudder appears as multiple parallel sections (instead of a single, continuous surface), with the distance between these sections reaching 2 meters. The proposed SLAM technique is able to reduce this worst-case distance to approximately 70cm while improving the overall shape of the map. This improvement is also noticeable towards the forward section of the map where this inter-submap distance is reduced from 1.2m to 40cm (approximate values).
2) Bulbous bow: A "coarse" survey of the bulbous bow of the ship, again from starboard side, was also performed and captured in this dataset. The coverage and results for this run are shown in figures 8(b) and 11, respectively.
Like the previous dataset, inspection of the bow was done by performing horizontal transects parallel to the ship's longitudinal axis. Due to the curvature of the hull, however, and in order to keep a consistent stand-off distance from the hull, a small yaw maneuver was performed about halfway through each transect. This resulted in a rather large amount of drift, as can be seen from the forward and aft regions of the map. On the top half of figure 11, it is possible to distinguish three "instances" of the bow tip-this has been successfully corrected by the proposed SLAM technique ( figure 11, bottom).
This inspection run also includes detailed inspection of a test object placed on the hull prior to the inspection run, and found in the course of the survey. This results obtained from a sample submap containing this object are shown in figure 9. From these we can see that while the shape has not been perfectly recovered (the object is a round metal cylinder 30cm in diameter), the submap is accurate enough to represent features on the scale of a few centimeters. Also of note is the vertical gap in figures 9(a) and 9(b)-this is the result of a missed sonar frame, possibly due to network congestion.

VI. CONCLUSION AND FUTURE WORK
We have proposed a technique for sonar-based SLAM that, while tailored to underwater scenes with complex geometries, can also be used in other applications such as bathymetric mapping. This technique extends previous work by focusing on improving submap accuracy through modeling of systematic errors and the use of probabilistic volumetric techniques for increased outlier robustness. Experimental validation on the problem of ship hull inspection indicates that it is both able to improve map accuracy by successfully correcting for navigation drift and represent features on the order of a few centimeters.
In our approach to sonar data enhancement (section III), we limited modeling to the angular component of the point spread function and made the assumption that it was angleinvariant. Relaxing these limitations should, in principle, yield better results: adding a radial dimension would improve range accuracy. Furthermore, the experimentally observed angular variation in beam pattern could be accounted for in an anisoplanatic PSF. Despite the relative success in eliminating outliers and improving overall submap quality, the use of volumetric techniques (as well as the subsequent filtering step) points to the challenge of sonar image classification. Our classifier is biased towards "empty space" (instead of occupied) to reduce the number of outliers at the cost of missing actual returns-because of its simple thresholdbased model, increasing its sensitivity would necessarily increase the number of outliers. Thus, improving classification performance is one of the main goals of ongoing work.
Still related to the classification problem, and motivated by the end-use of the sonar in a mapping framework, is the possibility of extracting additional information from sonar data, namely, surface orientation: given the narrow vertical field of view of an imaging sonar, it should be possible to at least restrict (if not completely determine) the orientation of surface elements to a finite set. This would be of particular use to the registration (ICP) step in our SLAM approach, and to the reconstruction of a 3D mesh from the resulting set of maps-the data product of an inspection system.
Additional improvements to the accuracy of both the SLAM solution and final map could be obtained by delaying the conversion from occupancy grids to point clouds to further along in the mapping pipeline. Replacing the use of ICP in the pairwise registration step with dense volumetric alignment techniques would improve pose estimate accuracy as both positive and negative information are used in the process. The final map could then be obtained by merging the different SLAM-corrected volumetric submaps onto a single occupancy grid and only then reconstructing a point cloud and/or 3D mesh. Finally, another relevant topic for future work would be the extension of these techniques to the inspection of dynamic scenes.