# UV3D: Underwater Video Stream 3D Reconstruction Based on Efficient Global SFM
## 3 SFM Preliminaries
### Extract Key Frames  
In this section, the key frame extraction algorithm based on clustering is elaborated. In machine learning, clustering is an unsupervised learning method used for data grouping. Clustering divides a data set into different classes or clusters according to a certain standard (such as a distance criterion). When it comes to key frame extraction, the crucial issue of the clustering process is the choice of clustering criteria [27; 28]. The key frame extraction method based on clustering can be divided into 2 steps, and the pseudocode of the key frame extraction algorithm is shown in Algorithm 1:  
```
Input:\(F_{initial}=\{F_{1},F_{2},\ldots,F_{n}\}\) Initial frames Output:\(F_{key}=\{F_{1},F_{2},\ldots,F_{k}\}\) Key frames
```  
**procedure:** Dendrogram Construction  
1: features of initial frames: \(f=\{f_{1},f_{2},\ldots,f_{n}\}\);  
2:\(\left\{D_{ij}\middle|i_{j}=1,2,\ldots,n\right\}\) Distances \(\leftarrow\) pdist (features);  
3: while (num of clusters > 1):  
merge the clusters with smallest distance;  
calculate distances between new cluster and old clusters;  
endprocedure  
**procedure:** Key frame extraction  
4: \(t\leftarrow\) OTSU (\(D_{ij}\))  
5: num of clusters \(k\leftarrow\) cluster (dendrogram, \(t\))  
6: \(F_{key}=\{F_{1},F_{2},\ldots,F_{k}\}\leftarrow\) extract clustering centers endprocedure  
**procedure:** Dendrogram Construction  
**Step 1:** Extract features of image sequence \(f=\{f_{1},f_{2},\ldots,f_{n}\}\) from initial frames \(F_{initial}=\{F_{1},F_{2},\ldots,F_{n}\}\). Differing from other kinds of data, the image data are all high-dimensional. If we directly use the Euclidean distance between the image data as the standard for clustering, the calculation is too large and may lead to memory overflow. In step 1, instead of calculating Euclidean distances among images, we use LBP and HSV fusion features. An LBP (local binary pattern) [29] is an operator used to describe the local texture features of an image. It has significant advantages, such as gray invariance and rotation invariance, and it is easy and efficient to calculate. Additionally, the LBP feature is robust to illumination changes, and uneven illumination may occur underwater, so it is suitable for underwater image description. HSV (hue, saturation, value) is a kind of color space created by [PERSON] in 1978 [30] according to the intuitive characteristics of color, and it is closer to people's experience and perception of color than RGB. In addition, HSV features describe the global features of the image, while LBP features describe the local texture information of the image, so their fusion can describe a frame more comprehensively. Due to the low saturation of underwater images, the saturation component in the HSV space is not convincing as an image feature. At the same time, due to the uneven illumination of the underwater environment, the V component in the HSV space can better represent the difference between frames. Therefore, we use the combination of H and V components in the HSV space with the image's LBP features to refine the local feature of the image. **Step 2:** Compute distances \(\left\{D_{ij}\middle|i,j=1,2,\ldots,n\right\}\) between frames with the pdist function in SciPy (an open-source Python algorithm library and math toolkit). **Step 3:** Generate a dendrogram through the while loop. Hierarchical clustering is an iterative process of continuously calculating the class spacing and merging the classes with the smallest distance until there is only one class left and results in a dendrogram. Which is shown in Figure 3, the abscissa of dendrogram represents the sample number, and the ordinate represents the distance between clusters. **procedure2: Key frame extraction Step 4:** Obtain the adaptive threshold \(t\) to split the dendrogram with the OTSU algorithm. Different clustering results can be obtained via segmentation at a specific level according to a threshold, so the determination of the segmentation threshold is very important.