7.2.1.1 Topology Estimation

Unfortunately, if positioning data coming from USBL, LBL, or DVL are not available, using time-consecutive image registration, assumed to have an overlapping area, becomes the only method to estimate the trajectory of the robot. This dead-reckoning estimate suffers from a rapid accumulation of registration errors, which translates into drifts from the real trajectory followed by the vehicle. However, it does provide valuable information for non-time-consecutive overlapping between the involved images. The matching between non-time-consecutive images is fundamental to accurately recover the path followed by the vehicle. This task is performed using global alignment methods (Capel 2004; Elibol et al. 2008 2011a; Ferrer et al. 2007; Gracias et al. 2004; Sawhney et al. 1998; Szeliski and Shum 1997). The refined trajectory can be used to predict additional overlapping between nonsequential images, which can be consequently attempted to match. The iterative process involving the registration of the new image pairs and the subsequent optimization is known as topology estimation (Elibol et al. 2010 2013). Even when navigation data are available, performing a topology estimation step is required to guarantee recovering accurate estimates of the vehicle path, and its value becomes even higher when dealing with large-scale surveys involving hundreds of thousands of images (Figure 7.2).

When dealing with data sets of thousands of images, all-to-all image pair matching strategies are unfeasible to carry out the topology estimation. Consequently, the use of more efficient techniques is required. Elibol et al. (2010) proposed an extended Kalman filter (EKF) framework, aimed at minimizing the total number of matching attempts while obtaining the most accurate trajectory. This approach predicts new possible image pairs considering the uncertainty of the recovered path. Another solution to the topology estimation problem based in a bundle adjustment (BA) framework was proposed by Elibol et al. (2011b). The approach combines a fast image similarity criterion with a minimum spanning tree (MST) solution to obtain an estimate of the trajectory topology. Then, image matching between pairs with high probable overlap is used to improve the accuracy of the estimate.

7.2.1.2 Image Registration

The image registration problem (Brown et al. 2007) consists of finding an appropriate planar transformation, which allows aligning in two or more 2D images taken from different viewpoints. The aim is to overlay all of them into a single and common reference frame (see Figure 7.3).

There are two main groups of image registration methods: direct methods and feature-based methods. The first group, also known as featureless methods, relies on the maximization of the photometric consistency over the overlapping image regions and is known to be appropriate to describe small translations and rotations (Horn and Schunck 1981; Shum and Szeliski 1998; Szeliski 1994). Nevertheless, in the context of underwater imaging using downward-looking cameras attached to an autonomous underwater vehicle (AUV) or remotely operated vehicle (ROV), it is common to acquire stills using stroboscopic lighting. This is due to power consumption restrictions affecting vehicle autonomy and leads to a low-frequency image acquisition. Consequently, the images do not have enough overlap to be registered using direct methods. For that reason, feature-based methods are most widely used to register not only underwater but also terrestrial and aerial imagery in the literature. Feature-based methods use a sparse set of salient points (Bay et al. 2006; Beaudet 1978; Harris and Stephens 1988; Lindeberg 1998; Lowe 1999) and correspondences between image pairs to estimate the transformation between them.

Image registration using feature-based methods involves two main stages. First, in the feature detection step, some interest or salient points should be located in one or both images of an image pair. Next, in the feature matching step, these salient points should be associated according to a given descriptor. This procedure is also known as the resolution of the correspondence problem. Depending on the strategy used to detect and match the features, two main strategies can be distinguished.

A first feature-based registration strategy relies on detecting salient points in one image using a feature detector algorithm, such as Harris (Harris and Stephens 1988), Laplacian (Beaudet 1978), or Hessian (Lindeberg 1998), and recognizing the same features in the other. In this case, the identification is performed using cross-correlation or a sum of squared differences (SSD) measure, involving the pixel values of a given area surrounding the interest point. A second method consists of detecting interest points on both images using some invariant image detectors/descriptors, such as SIFT (Lowe 1999), its faster variant SURF (Bay et al. 2006), or others, and solving the correspondence problem comparing their descriptor vectors. The descriptors have demonstrated to be invariant to a wide range of geometrical and photometric transformations between the image pairs (Schmid et al. 1998). This robustness becomes highly relevant in the context of underwater imaging, where viewpoint changes and significant alterations in the illumination conditions are frequent. Furthermore, the turbidity of the medium has been proven to have an impact in the performance of the feature detectors (Garcia and Gracias 2011) (Figure 7.4).

7.2.1.3 Motion Estimation

Once a set of correspondences has been found on an image pair, they can be used to compute a planar transformation describing the motion of the camera between both. This transformation is stored in a homography matrix (Hartley and Zisserman 2003; Ma et al. 2003), which can describe a motion with up to eight degrees of freedom (DOF).

The homography matrix encodes information about the camera motion and the scene structure, a fact that facilitates establishing correspondence between both images. can be computed, in general, from a small number of corresponding image pairs.

The homography accuracy (Negahdaripour et al. 2005) is strongly tied to the quality of the correspondences used for its calculation. The homography estimation algorithms assume that the only source of error is the measurement of the locations of the points, but this assumption is not always true inasmuch as mismatched points may also be present. There are several factors that can influence the goodness of the correspondences detected. Images can suffer from several artifacts, such as nonuniform illumination, sunflickering (in shallow waters), shadows (specially in the presence of artificial lighting), and digital noise, among others, which can produce a failure of the matching. Furthermore, moving objects (including shadows) may induce correspondences which, despite being correct, do not obey the dominant motion between the two images. These correspondences are known as outliers. Consequently, it is necessary to use an algorithm able to discern right and wrong correspondences. There are two main strategies to reject outliers widely used in the bibliography (Huang et al. 2007): RANSAC (Fischler and Bolles 1981) and LMedS (Rousseeuw 1984). LMedS efficiency is very low in the presence of Gaussian noise (Li and Hu 2010; Rousseeuw and Leroy 1987). For this reason, RANSAC is the most widely used method in the literature in the underwater imaging context.

7.2.1.4 Global Alignment

Pairwise registration of images acquired by an underwater vehicle equipped with a downward-looking camera cannot be used as an accurate trajectory estimation strategy. Image noise, illumination issues, and the violation of the planarity assumption may unavoidably lead to an accumulative drift. Therefore, detecting correspondences between nonconsecutive frames becomes an important step in order to close a loop and use this information to correct the estimated trajectory.

The homography matrix represents the transformation of the image withrespect to the global frame (assuming the first image frame as a global frame) and is known as absolute homography. This matrix is obtained as a result of the concatenation of the relative homographies between the and images of a given time-consecutive sequence. As mentioned earlier, relative homographies have limited accuracy and computing absolute homographies by cascading them results in cumulative error. This drift will cause, in the case of long sequences, the presence of misalignments between neighboring images belonging to different transects (see Figure 7.5).

The main benefit of global alignment techniques is the use of the closing-loop information to correct the pairwise trajectory estimation by reducing the accumulated drift.

There are several methods in the literature intended to solve the global alignment problem (Szeliski 2006). Global alignment methods usually require the minimization of an error term based on the location of the image correspondences. These methods can be classified according to the domain where this error is defined, leading to two main groups: image frame methods (Capel 2001; Ferrer et al. 2007; Marzotto et al. 2004; Szeliski and Shum 1997) and mosaic frame methods (Can et al. 2002; Davis 1998; Gracias et al. 2004; Kang et al. 2000; Pizarro and Singh, 2003; Sawhney et al. 1998).

7.2.1.5 Image Blending

Once the geometrical registration of all the mosaic images has been carried out, during the global alignment step, the photomosaic can be rendered. In order to produce an informative representation of the seafloor that can be used by the scientists to perform their benthic studies, the use of blending techniques to obtain a seamless and visually pleasant mosaic is required (see Figure 7.6).

On the one hand, the geometrical warping of the images forming the mosaic may lead to inconsistencies on their boundaries due to registration errors, moving objects, or the presence of 3D structures of the scene violating the planarity assumption in which the 2D registration relies. On the other hand, differences in the image appearance due to changes in the illumination conditions, oscillations in the distance to the seafloor, or the turbidity of the underwater medium cause the image boundaries to be easily noticeable (Capel 2004). Consequently, the consistency of the global appearance of the mosaic can be highly compromised. The main goal of image blending techniques is to obtain a homogeneous appearance of the generated mosaic, not only from the esthetic but also from the informative point of view, enhancing the visual data when needed, to obtain a continuous and consistent representation of the seafloor.

There are two main groups of blending algorithms depending on their main working principle (Levin et al. 2004): transition smoothing methods and optimal seam finding methods. The transition smoothing methods (also known as feathering (Uyttendaele et al. 2001) or alpha blending methods (Porter and Duff 1984)) are based on reducing the visibility of the joining areas between images combining the overlapping information. The optimal seam finding methods rely on searching the optimal path to cut the images along their common overlapping area in which the photometric differences between both are minimal (Davis 1998; Efros and Freeman 2001). The combination of the benefits of both groups of techniques lead to a third group (e.g., Agarwala et al. (2004) and Milgram (1975)), which can be called hybrid methods. These methods reduce the visibility of the seams, smoothing the common overlapping information around a photometrically optimal seam.

Image blending methods can be classified according to their capabilities and weaknesses, which may make them appropriate for certain applications but unfeasible for others. Considering the main principle of the techniques, the combination of a transition smoothing around an optimally found boundary (i.e., the use of hybrid methods) seems to be the most adopted approach in the recent bibliography. The tolerance of the techniques to moving objects is strongly tight to the principle, being all the optimal seam finding based methods able to deal with this issue up to a certain degree. This is due to the fact that optimal seam finding methods place the cut path on areas where photometric differences are small. As a consequence, overlapping areas with moving objects are cut. Concerning the domain in which the blending is performed, both luminance and gradient domains are widely used, the second having gained a special importance in recent years (Mills and Dudek 2009; Szeliski et al. 2008; Xiong and Pulli 2009). One of the benefits of the gradient domain is the easy reduction of exposure differences between neighboring images, which does not require additional pre-processing, due to the fact that image gradients are not sensitive to differences in exposure. Ghosting and double contouring effects arise when fusing information between images affected by registration errors or astrong violation of the planarity assumption. The ghosting effect occurs when wrong-registered low-frequency information is fused, while double contouring affects the high-frequency information. Given that all transition smoothing methods are affected by this artifact, the restriction of the fusion to a limited width area is required to reduce its visibility. Concerning the color treatment, it is similar in most of the techniques in the literature. Concretely, the blending is always performed in a channel-wise manner independent of the number of channels of the source images (i.e., color or gray-scale images). There are few methods in the literature conceived to work in real time (Zhao 2006), which therefore requires sequential processing to be performed. However, methods working in a global manner are better conditioned to deal with problems such as the exposure compensation so as to ensure global appearance consistency. The sequential processing tends to accumulate drift on the image corrections, which may strongly depend on the first processed and stitched image. Few blending methods are claimed to work with high dynamic range images. Nevertheless, gradient-based blending methods are able to intrinsically deal with them due to the nature of the domain. Methods able to process high dynamic range images require the application of tone mapping (Neumann et al. 1998) algorithms in order to appropriately display the results. The high dynamic range should be stretched in order to allow its visualization into low dynamic range devices, such as screen monitors or printers.

Large-scale underwater surveys often lead to extensive image data sets composed from thousands to hundreds of thousands of stills. Given the significant computational resources that the processing of this amount of data may require, the use of specific optimal techniques such as that proposed by Prados et al. (2014) is needed. The first stages of the pipeline involve the input sequence pre-processing, required to reduce artifacts such as the inhomogeneous lighting of the images, mainly due to the use of limited-power artificial light sources and the phenomenon of light attenuation and scattering. In this step, a depth-based non-uniform-illumination correction is applied, which dynamically computes an adequate illumination compensation function depending on the distance of the vehicle to the seafloor. Next, a context-dependent gradient-based image enhancement is used, allowing to equalize the appearance of neighboring images when those have been acquired at different depths or with different exposure times. The pipeline follows with the selection of each image contribution to the final mosaic based on several criteria, such as image quality (i.e., image sharpness and level of noise) and acquisition distance. This step allows getting rid of redundant and low quality image information, which may affect in a counterproductive way the surrounding contributing images. Next, the optimal seam placement between all the images is found, minimizing the photometric differences around the cut path and discarding moving objects. A gradient blending in a narrow region around the optimally computed seams is applied, in order to minimize the visibility of the joining regions as well as to refine the appearance equalization along all the involved images. The usage of a narrow region of fusion reduces the appearance of artifacts, such asghosting or double-contouring, due to registration inaccuracies. Finally, a strategy allowing to process gigamosaics composed of tens of thousands of images in conventional hardware is applied. The technique divides the whole mosaic in tiles, processing them individually, and seamlessly blending all of them again using another method that requires low computational resources.

7.2.3.1 Surface Reconstruction

Due to the above-mentioned common downward-looking configuration of the sensor, there are few approaches tackling the problem of 3D mapping in the underwater community. One of the few examples in this direction can be found in Johnson-Roberson et al. (2010), where they use the surface reconstruction method of Curless and Levoy (1996), originally devised to unrestricted 3Dreconstruction. Nevertheless, the added value of applying this method in front of a 2.5D approximation is not clear in this case, since the camera still observes the scene in a downward-looking configuration. Another proposal, this time using a forward-looking camera and working on a more complex structure, is that presented in Garcia et al. (2011), where an underwater hydrothermal vent is reconstructed using dense 3D point cloud retrieval techniques and the Poisson surface reconstruction method (Kazhdan et al. 2006).

For downward-looking configurations, the straightforwardness of changing from depth readings to 2.5D representations makes the reconstruction of the scene as a triangulated terrain model to be just a side result. However, we are now concerned with a more general scenario, where the sensor can be mounted in a less restrictive configuration, that is, located anywhere on the robot and with any orientation. With this new arrangement, objects can be observed from arbitrary viewpoints, so that the retrieved measures are no longer suitable for projection onto a plane (and hence, a 2.5D map cannot be built). Viewing the object from further positions allows a better understanding of the global shape of the object since its features can be observed from angles that are more suitable to their exploration. An example in this direction is depicted in Figure 7.8, where we can find a survey of an underwater hydrothermal vent. It is clear in Figure 7.8b that it is not possible to recover the many details and concavities of this chimney using just a 2.5D representation. The more general configuration of the camera, in this case mounted at the front of the robot oriented approximately at angle with respect to the gravity vector, allowed a more detailed observation of the area, attaining also higher resolution. Consequently, it is obvious that for these new exploration approaches, the problem of surface reconstruction is of utmost importance to complete the 3D mapping pipeline.

Another issue that burdens the development of surface reconstruction techniques is the defect-ridden nature of point sets retrieved on real-world operations. The large levels of noise and the huge number of outliers present in the data clearly complicate the processing. Thus, the surface reconstruction method to use mainly depends on the quality of the data we are dealing with and the ability of the method to recover faithful surfaces from corrupted input.

Given the ubiquity of point set representations and the generality of the problem itself, surface reconstruction has attracted the attention of many research communities, such as those of computer vision, computer graphics, or computational geometry. In all of them, the different approaches can be mainly classified into two types: those based on point set interpolation, and those approximating the surface with respect to the points. Usually, these methods are applied to range scan data sets because of the spread use of these sensors nowadays. Nevertheless, they tend to be generic enough to be applicable to any point-based data regardless of their origin, consequently including our present case of optical and acoustic point sets retrieved from an underwater scenario.

Another relevant issue is the requirement of some methods to have some additional information associated with the point set. Many methods in the state of the art require available per-point normals to help in disambiguating this ill-posed problem. Moreover, some methods assume even higher level information, such as the pose of the scanning device at the time of capturing the scene, to further restrict the search for a surface that corresponds to that of the real scanned object. The availability of these properties will also guide our selection of the proper algorithm.

In the following sections, we overview both interpolation and approximation-based approaches in the state of the art.

Approximation-Based Approaches

We can find a large variety of procedures based on approximation, which makes them more difficult to classify. Nevertheless, the common feature of most of the methods is to define the surface in implicit form and evaluate it using a discretization of the working volume containing the object. After approximating the surface in this embodiment, the surface triangle mesh can be extracted by means of a surface mesher step (Boissonnat and Oudot 2005; Lorensen and Cline 1987). Thus, we can mainly classify these methods depending on the implicit definition they provide.

One of the most popular approaches is to derive a signed distance function (SDF) from the input points. This SDF can be defined as the distance from a given point to a set of local primitives, such as tangent planes (derived from known normals at input points) (Hoppe et al. 1992; Paulsen et al. 2010), or moving least squares (MLS) approximations (Alexa et al. 2004; Guennebaud and Gross 2007; Kolluri 2008). Alternatively, some methods work with the radial basis function (RBF) interpolation of the SDF. The RBF method, usually used to extrapolate data from samples, is used to derive the SDF from point sets with the associated normals (Carr et al. 2001; Ohtake et al. 2003 2004).

On the other hand, there are some approximation approaches where the implicit function sought is not a distance function but an indicator function. This simpler definition denotes for a given point whether it is part of the interior of the object or the outside (i.e., it is a pure binary labeling) (Kazhdan et al. 2006; Kazhdan and Hoppe 2013; Manson et al. 2008). Usually, this inside/outside information is derived from the information provided by known per-point normals.

Note that, up to this point, all the reviewed methods require that the surface normal vector is known for each input point. It is clear that the requirement of per-point normals may be a burden in the cases where the scanning methodology does not provide this information. Moreover, estimating the normals at input points to reconstruct a surface is a chicken and egg problem: to compute the normals, we have to infer somehow the surface around each point. Nevertheless, even when working with raw point sets without normals, we can derive some distance function. The only drawback is that the resulting function is bound to be unsigned. When working with unsigned distance functions (UDFs), the main problem resides in the fact that we cannot extract the surface from the zero-level set as is done for SDF or indicator function-based approaches. Thus, methods try to recover the sign of the function using some heuristics (Giraudot et al. 2013; Hornung and Kobbelt 2006; Mullen et al. 2010; Zhao et al. 2001).

In all the above-mentioned cases, both noise attenuation and outlier rejection are problematic, and most of them require per-point normals. Still, there exist other methods proposing unconventional procedures but not requiring any additional information, such as in Campos et al. (2013a 2015), where they merge a set of local shapes derived from the points into a global surface without resorting to an intermediate implicit formulation. Instead, they modify the surface meshing method in Boissonnat and Oudot (2005) to be able to deal with these local surfaces directly. Thus, in these cases, meshing and surface reconstruction problems are intrinsically related, meaning that the quality of the resulting surface is also a user parameter. Moreover, both methods work with the idea of dealing with noise and outliers in the data, by means of using robust statistics techniques within the different steps of the method, and allow the reconstruction of bounded surfaces, usually appearing when surveying a delimited area of the seafloor. These last two methods are applied specifically to underwater optical mapping data sets, and a sample of the behavior of Campos et al. (2015) can be seen in Figure 7.8a.

7.2.3.2 Further Applications

The ability of modern graphics hardware (i.e., graphics processing units (GPUs)) to display in real-time triangle primitives eases the visualization of the reconstructed scenes. Moreover, the widespread use of triangle meshes has motivated the rapid development of various mesh processing techniques in recent years that may be helpful in further processing (see Botsch et al. (2010) for a broader overview of these methods). Some of these techniques include the following:

• (Re)Meshing: Changes the quality/shape of triangles (see Figure 7.9b). Some computations, such as the finite element method (FEM), require the shape of the triangles to be close to regular, or adaptive to the complexity or curvatureof the object. Meshing (or remeshing) methods allow tuning the quality of the triangulation according to some user-defined parametrization on the shape of the triangles.
• Simplification: Related to remeshing, we can change the complexity of the mesh (see Figure 7.9c) to attain real-time visualization, or to also simplify further calculus to compute the data.
• Smoothing: Smooths the appearance of the resulting surface. Note that this technique may be specially useful in the case of using an interpolation-based surface reconstruction technique, since in this case a noisy point cloud will result in a rough and spiky approximation of the surface. Smoothing methods try to attenuate small high-frequency components in the mesh, resulting in a more visually pleasant surface.

In contrast to the pure mesh-based approaches, when using optical-based reconstruction we can also benefit from texture mapping. Texture mapping is a post-processing step where the texture of the original images used to reconstruct the scene can also be used to colorize and basically give a texture to each of the triangles of the resulting mesh. Since we have reconstructed the surface from a set of views, both the cameras and the surface are in the same reference frame. Thus, as shown in Figure 7.10, the texture mapping is quite straightforward: we can back-project each triangle to one of its compatible views and use the enclosed texture. The problem then reduces to that of blending, discussed in Section 7.2.1, but in 3D. The different available variants of these methods are mainly concerned with the selection of the best view to extract the texture from a given triangle, and also with alleviating the differences in illumination that may appear when composing the textures obtained from different views. Two representative methods in the literature can be found in Lempitsky and Ivanov (2007) and Gal et al. (2010).