OGM-Based Real-Time Obstacle Detection and Avoidance Using a Multi-beam Forward Looking Sonar

1.1 Image Preprocessing

Actual sonar images are easily influenced environmental noise, reverberation noise, and self-noise. Sound waves are affected by channel characteristics, such as scattering and reverberation, when propagated in water, resulting in sonar images with poor visibility and quality due to speckle noise (Yu et al., 2023). Therefore, denoising is an essential preprocessing technology in sonar image applications.

Existing image noise removal algorithms are generally categorized into spatial domain filtering (Petillot et al., 2001) and transform domain filtering (Paull et al., 2010). Spatial domain filtering methods include existing technologies such as median, Gaussian, and bilateral filtering. Lee (1981) used the adaptive median filtering algorithm designed based on secondary noise detection and adjacent pixel restoration to overcome the drawbacks of median filtering. Spatial domain filtering methods aim to remove specific types of noise, but the processed images often become blurry and lose detail. Notable transform domain-filtering methods include the discrete cosine transform (DCT) (Yuki et al., 2018), principal component analysis (PCA) (Zhang et al., 2018), and wavelet shrinkage denoising (Shen et al., 2017). Transform domain filtering methods can remove specific noise and cause a loss of detail by eliminating the high-frequency components of the signal. Similarly, the maximally stable extremal regions (MSER) method was introduced to detect stable regions for identifying potential object candidates (Hong, 2023).

Deep learning-based noise-removal algorithms have been researched to reduce noise in sonar images. For example, a neural network-based convolutional autoencoder can effectively remove noise in sonar images (Kim et al., 2017). On the other hand, deep learning technology demands high computational power and sonar datasets for training. Executing high-performance computing in AUVs and acquiring the necessary sonar data is challenging. Accordingly, pre-trained noise removal methods (Dong et al., 2018) have been a recent focus of research, but they are unsuitable for real-time image filtering because of their high computational requirements. This study applied a constant false alarm rate (CFAR) algorithm for noise filtering (Kim et al., 2017; Dong et al., 2018; Ritcey and Hines, 1991). The CFAR algorithm detects targets by accounting for the noise level of the surrounding environment and dynamically adjusting the threshold based on the changes in the environment. This particular algorithm is suitable for scenarios involving sonar images because the sonar intensity varies with distance and is affected by sidelobe effects.

1.2 Obstacle Detection

Underwater mapping technology involves producing a two-dimensional horizontal map or a three-dimensional spatial map by detecting obstacles. Detecting objects in sonar images is challenging because of significant noise and low resolution. In addition, 3D point clouds generated using the beam width of sonar include height information over a broad area but lack sufficient shape details. A stereo pair of orthogonally oriented sonars was proposed for 3D sonar mapping to complement each imperfection (McConnell and Englot, 2021), and Bayesian inference was used to reconfigure the regions without overlapped field of view. Additional methods have been suggested to reconfigure height information based on the mobility of AUVs and to partially address the ambiguity issues of angles related to the elevation angle of forward-looking sonar (FLS) (Kim et al., 2020). This study applied an occupancy grid map (OGM) to produce underwater maps, and obstacles were detected using Bayesian inference. The OGM reduces the uncertainty about the position of an object detected by sonar beams by estimating occupancy and non-occupancy of the grid. This algorithm enables robots to map the environment and quickly detect obstacles accurately. Bayesian inference updates the confidence level if the grid intensity surpasses a specific threshold. Regions with confidence above a certain probability are then considered obstacles.

1.3 Obstacle Avoidance

Obstacle avoidance aims to navigate robots from their current location to a target location without collisions. Widely used methods include the potential field algorithm (Weber, 2021; Sunny and Narayanan, 2022) and the A* algorithm (Thrun et al., 2005). The potential field algorithm is straightforward and computationally efficient, making it suitable for various platforms requiring low computational resources. This algorithm is used widely because it can calculate the paths in real-time, even in dynamic environments. The parameters of the potential field function can be adjusted to be applicable in various environments and scenarios. On the other hand, the potential field algorithm entails the issue of local minima. Several studies have examined the local minima issue using the revised potential field algorithm (Li et al., 2019; Rostami et al., 2019). The A* algorithm is a graph-search algorithm for finding the shortest path from a given starting vertex to a target vertex using a heuristic function (Hart et al., 1968). The limitation of the A* algorithm is its unsuitability for real-time path planning because it becomes computationally complex when dealing with dynamic obstacle maps. A genetic algorithm (GA) (Alhijawi and Awajan, 2024) involves significant computational costs and does not ensure an optimal solution. It excels in pre-trained paths but struggles to adapt flexibly to maps generated in real-time. When comparing the two most commonly used and straightforward algorithms―the potential field algorithm and the A* algorithm―the potential field algorithm is faster than the A* algorithm when applied to maps with the same resolution (Kot et al., 2024). The difference between the two algorithms becomes more pronounced as maps increase in size and contain more dynamic obstacles. Furthermore, the A* algorithm is restricted to specific angles (0°, 45°, 90°) for movement when setting the target direction in grid-format maps. In contrast, the potential field algorithm offers a range of target directions by calculating the attractive and repulsive forces between the AUV and obstacles. This allows for adaptable control of AUVs.

Recent research on obstacle detection and avoidance algorithms using sonar in underwater environments is leading to the development of various path-planning algorithms. Petillot et al. (2001) facilitated path planning in complex environments with fast-moving obstacles by acquiring the real-time dynamic characteristics of the obstacles. Another feature is that obstacles are represented as convex shapes, which reduces the likelihood of encountering local minima. On the other hand, in addition to distinct processing for static and dynamic characteristics, the computational load is high because dynamic obstacles are identified separately during image streaming. A hexagonal grid and a directed acyclic graph have been proposed for path planning. Nevertheless, avoiding dynamic obstacles is challenging because a directed acyclic graph requires computation for all cells (Paull et al., 2010). Another approach proposed involves combining a GA with a detection algorithm to compute the optimal search path. On the other hand, the GA was effective in finding the optimal path only when an intuitive solution was available (Cho et al., 2007). Recently, a method has been suggested for generating and simulating a path using flow-based stream functions of a fluid. Nevertheless, its application to real-time path planning is challenging because of its complex computation and difficult implementation (Kim et al., 2023). Therefore, this study proposes an OGM-based potential field algorithm that can generate an obstacle map and calculate the paths in real-time, even in dynamic environments, owing to its straightforward implementation and low computational requirements. This algorithm is effective for real-time obstacle avoidance because of its simple architecture and low computational demands. On the other hand, the parameters must be calibrated based on the control performance of AUVs, considering the noise and instability in sonar data. Therefore, the CFAR algorithm processes sonar images, producing a reliable OGM obstacle map through Bayesian inference. In the future, parameters will be calibrated to suitable values for the platform through a real sea test.

2.1 Multi-Beam Forward-Looking Sonar

This study uses the Gemini 1200ik from Tritech as an FLS. Table 1 lists the specifications of Gemini 1200ik.

A low-frequency mode, an operating distance of 50 m, and a horizontal beam width of 120° are used. A multi-beam FLS projects a 3D object onto a 2D image plane. Once a coordinate X (x_s, y_s, z_s) is given in a 3D Cartesian coordinate system, the relationship between this Cartesian coordinate system and a spherical coordinate system (r, θ, ϕ) can be described as Eq. (1)–(2).

where (r, θ, ϕ) represents the range, azimuth angles, and elevation angles, respectively. The Cartesian projection point P of point X is positioned at (x_s′, y_s′ ) on the image plane:

Fig. 1 shows that when a 3D point is projected onto a 2D image, there is a nonlinear component (cosϕ) between the two points. The vertical beam width of Gemini 1200ik is 20°. Thus, cos (20°) is 0.94 and cos(ϕ) ≈1, sin(ϕ) ≈0, suggesting that the effect of nonlinearity due to elevation can be disregarded. Accordingly, it can be expressed as a point, P̂=(x_s, y_s). In this model, the projection region rotates in the same manner as the sonar during yaw rotation, affecting the image. On the other hand, the pitch rotation of the sonar does not influence the projection of a point on the image plane, but roll motion can alter the projection position.

2.2 AUV Test Bed

An obstacle detection and avoidance algorithm is implemented to enhance the autonomy and success rate of AUV task completion. But AUVs cannot perform real-time communications, and there is a high risk of damage or loss because of collisions with obstacles. Therefore, the N-SURO ROV, currently owned by the Korea Institute of Robot and Convergence, is used as a test bed. Figs. 2 and 3 show the overall appearance of the AUV and system configuration, respectively.

N-SURO is a hovering type ROV equipped with six thrusters, providing it with five degrees of freedom, excluding pitch. A multi-beam FLS is mounted at the front for obstacle avoidance. All algorithm operations were executed on the Xavier AGX, with only the target heading value delivered as output to facilitate future conversion to an AUV.

2.3 Building the Experiment Site Environment

The experiment in this study is conducted at the coastal area near the Korea Institute of Ocean Science and Technology (KIOST) South Sea Research Institute, as shown in Fig. 4. The KIOST South Sea Research Institute was well-equipped with infrastructure for conducting marine experiments, owing to simple topological features from being a reclaimed land. The coastal area shows a 5 m depth difference (5 m at low tide and 9 m at high tide). The author conducted various experiments at this location and has experience obtaining nearby terrain data using the Gemini 1200ik FLS from Tritech. Typically, the front and seabed were detectable when the sonar range was set to 50 m in shallow coastal areas, where the seabed features a muddy geology and gentle topography. When conducting avoidance experiments using sonar with obstacles placed arbitrarily, external objects near the seabed are not always detected as obstacles. In addition, shallow depths reduce the operational range of the ultra-short baseline (USBL) system. Therefore, ROVs are operated at sea, and their positions are determined using a global positioning system (GPS).

This study set up two types of obstacles. The first obstacle aims to verify the effectiveness of the obstacle avoidance algorithm using an obstacle installed at the target point, while the second obstacle focuses on assessing the possibility of detecting small obstacles in the grid. The angular resolution of the sonar was configured to 0.25°, and its detection range was set to 50 m. The length covered by a single sonar beam at a distance of 50 m was approximately 0.218 m, calculated as the arc length. The obstacles were designed with a minimum diameter of 0.5 m to ensure detection using at least two beams. Plastic and steel were used for the obstacles, as the detection rate can vary according to the material. Fig. 5(a) shows the actual images of the obstacles. As shown in Fig. 5(b), the test obstacles were detectable up to 32 m, but due to the schedule, it could not be confirmed at 50 m.

The diameter of the test obstacles was 0.5 m. Hence, there must be only one pixel for an obstacle on the OGM. In reality, they are represented by more than one pixel because of reverberation noise, the rope used to catch the obstacles, and the yellow buoy being detected by the sonar. Fig. 5 shows the rope and the buoy.

3.1 CFAR Algorithm

Actual sonar data extensively contain speckle noise and impulsive noise because of reflections from the seabed, sea surface, or obstacle (Yu et al., 2023; Ritcey and Hines, 1991; McConnell and Englot, 2021). In this study, the CFAR algorithm is applied to mitigate impulsive noise. The CFAR algorithm is a signal processing technique commonly used in radar and sonar systems to enhance the reliability of signal detection and effectively manage noise. The CFAR algorithm adjusts the threshold dynamically based on the intensity around the reference cell to filter noise and reduce reflected impulsive noise. Among various CFAR algorithms, this study applies the greatest of the CFAR (GO-CFAR) algorithm. The GO-CFAR algorithm calculates the threshold using the maximum value instead of the mean or median value of the surrounding cells. This method responds effectively to strong signals, particularly when the noise intensity is weaker than the signal (Mbouombouo Mboungam et al., 2023). In this study, the threshold is set to 80% or higher of the largest value in the surrounding cells. Fig. 7 presents the algorithm.

3.2 OGM Composition

Generally, FLS captures a wide area at high resolutions using 512 or 1,024 beams, producing a large volume of data to process. In addition, AUVs are not constrained by the tether cable length as ROVs are, allowing them to explore a larger area and gather more data, which increases the computational load. Managing global map data and minimizing the computational load is essential to generating real-time obstacle maps for a large area. Given that the radius of rotation of an AUV typically exceeds 10 m, the resolution of the obstacle avoidance map must be adjusted accordingly.

This study uses the OGM to adjust resolutions and generate obstacle maps. The OGM estimates the occupancy state of each grid probabilistically, facilitating rapid exploration and decreasing the uncertainty of the position of an object detected by a sonar beam. Bayesian inference updates the confidence level if the grid intensity surpasses a specific threshold. Regions with confidence above a certain probability are then considered to contain obstacles. It provides data with 1,506 rows when the sonar range in this study is set to 50 meters. This indicates that the sonar resolution is approximately 0.03 m. This study focuses on avoiding obstacles based on the rotation radius of the AUV rather than on identifying the detailed shapes of the obstacles. Accordingly, the OGM is defined as one square meter in the Earth-centered, Earth-fixed coordinate system. Using area interpolation from the OpenCV (Open Source Computer Vision Library), the sonar image was adjusted from a range of 50 m, 512 columns, and 1,506 rows to a one-meter grid per pixel. This process is expressed as Eq. (4).

where D_p, N_r, and R are the pixel density, number of row pixels, and sonar range, respectively. D_p was calculated as 150650≈30 (pixel/meter). Thus, the rows of the original image were divided by 30 to ensure that one pixel corresponds to 1 m. The resolution was not reduced because the columns have a unit corresponding to each multi-beam number. The result was calculated using Eq. (5). where A_p is the adjusted pixel size, and O_p is the original pixel size.

The CFAR algorithm was applied to the adjusted image to remove noise. Most of the speckle noise was eliminated by adjusting the resolution, and impulsive noise generated in the vicinity during this process was also removed. The computational load of the CFAR algorithm increases based on the size of the comparison cells because the algorithm involves comparisons with nearby cells. On the other hand, the speed remains sufficiently fast if low-resolution images are used. A preprocessed image contains only pixels that are considered to include obstacles. These coordinates are then mapped in the global frame using this data along with the positional data of the AUV.

Here, (x_r, y_r, z_r ) is the pixel coordinate in the reference frame; (x_c, y_c, z_c) is the vehicle’s center position of the vehicle in the reference frame; r is the pixel distance in the multi-beam sonar head; θ_b is the respective beam angle. The coordinate transformation matrix Cbr from the vehicle frame to the reference frame is defined as follows:

(ϕ, θ, ψ) each represents the roll, pitch, and yaw of AUV, respectively.

Each cell of the OGM represents the probability of the presence of obstacles. The initial probability of the presence of an obstacle was set low because the long range of the sonar and the slow-moving speed of the AUV allowed for the collection of sufficient data. The reliability of the sonar image for obstacle identification was fine-tuned through multiple experiments. This adjustment reflects the sophisticated data processing method based on the Bayesian inference. Fig. 8 shows the Bayesian inference algorithm.

BM represents the probability of obstacles being present in each cell; pixelData is the actual sonar measurement of each cell; truePositiveRate is the probability of a sensor correctly detecting obstacles when they exist, and falsePositiveRate is the probability of a sensor falsely detecting obstacles when they are not present. B, D, and P() denotes the presence of obstacles, the detection of obstacles by a sensor, and the probability, respectively. Therefore, P(B) is the prior probability that obstacles are present at coordinates X, Y. P(D) is the probability that a sensor will detect obstacles; P(D | B) is the probability that a sensor will detect obstacles that are present; P(D | ￢ B) is the probability that a sensor will detect obstacles that are not present, and (1 – P(B)) is the prior probability that there are no obstacles present. P(D | B), indicating the sensor reliability, is pre-defined and calculated based on empirical data.

5.1 Image Preprocessing

The OGM technique and the GO-CFAR algorithm are used to eliminate speckle noise and impulsive noise from the sonar data. The original sonar image, with 1,506 rows, 512 columns, and a range of 50 m, is scaled to 1/30 of its size to produce a 1-m grid. The GO-CFAR algorithm is applied to identify the obstacles. Accordingly, both the computational load is reduced. The obstacle detection performance also decreases when noise is reduced by downsampling. In the actual sonar data, obstacles with high reflection intensity appear and disappear intermittently. This study addresses this issue by reducing the accuracy of the sensor model using Bayesian inference to ensure the stable recognition of obstacles. Fig. 10 shows the process of resizing an image and applying the GO-CFAR algorithm.

The image resized to 512 × 30 pixels is too small, so it is enlarged to 512 × 1,500 pixels to provide a more practical reference for visual inspection. The noise in image (b) is reduced through area interpolation, but azimuth streaking remains visible. In image (c), the CFAR algorithm is applied to remove azimuth streaking and noise. Certain strong noises remain, but they do not continue to appear at the same position, thus not being discerned as an obstacle in Bayesian inference.

5.2 Obstacle Map Production

The processed sonar data is converted from the reference frame to the global frame based on the attached position of the sonar. Based on this data, the obstacle map is updated through Bayesian inference, and positions with a probability 98% or higher are considered obstacles. The entire obstacle map is 200 × 2,000 pixels; Fig. 11 shows a part of the obstacle map generated in real-time by moving the test platform.

The obstacles are depicted as yellow dots, the movement path of the platform is shown as a red line, and the generated real-time path is indicated by a brown line. In addition to the installed obstacles, the surrounding walls, pontoon, rocks, and other platforms are recognized as obstacles.

5.3 Potential Field Algorithm Verification

This section introduces the performance experiment results of the potential field algorithm. The repulsion force radius of the obstacles is set to 7 m, considering the distance between the obstacles. Initially, the sonar does not detect the obstacles, but the obstacles gradually appear on the obstacle map as the platform moves forward. Fig. 12 shows the paths generated by the potential field algorithm. Successful paths often resemble each other, and notable examples of these paths are presented.

The experiments are repeated 10 times for each scenario. Table 2 lists the obstacle avoidance results, with an 80% success rate for scenario 1 and a 90% success rate for scenario 2.

The third trial of scenario 1 take place during high tide, leading to obstacle detection failure because of floating debris produced by the flood tide. The sonar intensity is then adjusted to enable detection. In the fourth trial of scenario 1, failure occurs because the AUV did not follow the planned path because of the increased distance between the obstacles. In the seventh trial of scenario 2, failure occurs because the platform fall into a local minimum when the nearby experimental platform is detected. Fig. 13 presents the failure paths.

Obstacle avoidance is mostly successful, but there are certain restrictions. First, floating debris is formed by the flood tide in the real sea. Floating debris disrupts sound wave transmission, leading to continuous fluctuations in the obstacle detection intensity. Consequently, adjusting the sonar intensity and the sensor reliability through Bayesian inference take considerable time. In this experiment, tether cables are used to monitor sensor data in real-time and promptly adjust the sonar intensity. On the other hand, adjusting AUVs is challenging and necessitates more robust algorithm modifications.

Another issue is that obstacles on the water surface are detected too easily. Buoys, thick ropes, and pontoons are also easily recognized as obstacles. In addition, the test platform in this study has a front-mounted thruster, and the bubbles produced by the thruster are also detected by sonar. As a result, additional chattering occurs because of the bubbles when the heading changes abruptly. Although most AUVs have rear-mounted thrusters, which minimizes the concern, it should still be considered. Similarly, obstacles that are not initially detected begin to be recognized suddenly when they are at closer distances. The potential field algorithm produces stronger repulsion as the distance to obstacles decreases. The platform often deviate by 180° because of the sudden strong repulsive forces, leading to obstacles appearing behind the platform because of abrupt heading changes. In such cases, the platform may become trapped in local minima, leaving obstacles on the map not present in the rear before proceeding.

The experiment reveals several issues that could occur in real-world situations, highlighting the need to develop a more robust algorithm that can effectively recognize and respond to environmental factors.