# A Collaborative Human-Robot Framework for Visual Topological Mapping of Coral Reefs
## 2 Method
### Keyframe Selection for Adding Nodes to the Map  
Although it is possible to add every image of the sequence to the map, it will increase the processing time as more information has to be processed. Additionally, considering the typical frame rate of the cameras (30 or 60 frames per second), it is very likely that consecutive images contains repeated visual information. Therefore, only certain images (keyframes) are added to the graph and used in the rest of the processing pipeline. In this work, the keyframe selection criteria is based on keeping the overlapping area between them less than a maximum value \(ol_{max}\). Let \(I_{L}\) be the image added as the last node in the graph and \(I_{t}\) the current image, then \(I_{t}\) is added to the graph if the overlapping area between both images is less than a threshold \(ol_{max}\). To calculate  
Figure 1: General overview of the proposed approach. the overlap, the relative position of \(I_{t}\) with respect to \(I_{L}\) is required. This relation is encoded as a rigid transformation \(A_{ab}\) defined as:  
\[A_{ab}= \begin{bmatrix}\alpha_{11}&\alpha_{12}&\alpha_{13}\\ -\alpha_{12}&\alpha_{11}&\alpha_{23}\\ 0&0&1\end{bmatrix} = \begin{bmatrix}\cos\theta_{ab}&\sin\theta_{ab}&x_{ab}\\ -\sin\theta_{ab}&\cos\theta_{ab}&y_{ab}\\ 0&0&1\end{bmatrix} , \tag{1}\]  
where \(a=L\) and \(b=t\). Then, this transformation is applied to the four corners of \(I_{L}\) to obtain the corners' position of \(I_{t}\) with respect to \(I_{L}\), as shown in Figure 2. The overlap is calculated as the intersecting area of the rectangles defined by the two sets of corners divided by the area of \(I_{L}\). In the case of raster images (e.g., those obtained from digital cameras), the overlapping area can be calculated by simply counting the pixels in the intersecting area. To find a rigid transformation between two images \(I_{a}\) and \(I_{b}\), we need to find the common visual features in both of them by following the next procedure:  
1. For each visual feature descriptor \(z_{a,r}\) in \(Z_{a}\), its two most similar descriptors \(z_{b,q_{1}}\) and \(z_{b,q_{2}}\) in \(Z_{b}\) are found. If the ratio between \(\frac{\|z_{a,r}-z_{b,q_{1}}\|}{\|z_{a,r}-z_{b,q_{2}}\|}\) is less than a threshold \(\rho\), then the pair of indexes \((r,q_{1})\) is stored in a set \(m_{ab}\). The matching of descriptors is efficiently performed using the Fast Library for Nearest Neighbors search (FLANN) [35]. This is specialized to work on high-dimensional spaces, which is the case for the 64-dimensional descriptors obtained with SURF. 2. Step 1 is applied to obtain the pairs of corresponding features from image \(I_{b}\) to \(I_{a}\) and stored in \(m_{ba}\). 3. Only the pairs of indexes \((r,q)\) that appear in both \(m_{ab}\) and \(m_{ba}\) are kept and stored in a set \(m\). Given the set of matching features \(m\), the rigid transformation in (1) can be estimated by finding the matrix \(A^{*}\) that minimizes the following expression:  
\[A^{*}=\arg\min_{A_{ab}}\sum_{(r,q)\in m}\|f_{a,r}-A_{ab}f_{b,q}\|, \tag{2}\]  
where \(\|\cdot\|\) is the Euclidean norm. It is important to mention that the features' positions \(f\) are extended to be of the form \((x,y,1)\) so they can be multiplied by the rigid transformation as defined in (1). Figure 2: Example of the overlap calculation. Given two images \(I_{a}\) and \(I_{b}\), the visual features between both images are matched. From those matches, a rigid transformation \(A_{ab}\) is obtained. After that, we can calculate the intersection between both frames and its area. Although \(A_{Lt}\) can be estimated directly from \(I_{L}\) and \(I_{t}\) there can be some cases where not enough corresponding features are found, causing a bad estimation of the rigid transformation. That is why \(A_{Lt}\) is calculated by concatenating all the rigid transformations between consecutive frames from \(I_{L}\) to \(I_{t}\):  
\[A_{Lt}=A_{L,k}A_{k,k+1}...A_{t-1,t}, \tag{3}\]  
where \(k\) is the index of the next image in the sequence after image \(I_{L}\) was added to the graph.