# UV3D: Underwater Video Stream 3D Reconstruction Based on Efficient Global SFM
## 4 Lts-Lira
### Lts-L1 ra Algorithm  
In this paper, we come up with a more efficient method based on the L1 RA (\(l1-norm\) rotation averaging) and c-step methods. In 2013 [35], Govindo firstly minimized and estimated the global rotations robustly. In the L1 RA algorithm, the initial guesses for global rotations \(R_{global}=\{R_{1},R_{2},\ldots,R_{n}\}\) are firstly calculated according to Equation (4) and then the sparse matrix \(A\) is constructed. After this comes the iterative optimization process, whereby each iteration recalculates the error of the relative rotation vector \(\varpi_{rel}\) (step 1: calculate \(\Delta R_{ij}\), the discrepancy between the observations \(R_{ij}\), and the current global estimate; step 2: convert \(\Delta R_{ij}\) to \(\Delta\varpi_{ij}\) due to Equation (7)) and then minimizes \(\left\|A\Delta\varpi_{global}-\Delta\varpi_{rel}\right\|_{l1}\) with \(l1\) minimization to obtain \(\Delta\varpi_{global}\) (step 3) and update the global rotations (step 4). The iteration stops once the error meets the requirement. A review of the L1 RA method is shownas Algorithm 2. ```
Input:\(R_{ij}=\left\{R_{ij1},R_{ij2},\ldots,R_{ijk}\right\}\) Relative Rotations Output:\(R_{global}=\{R_{1},R_{2},\ldots,R_{n}\}\) Global Rotations Initialization: Initial guess Function name and argument:\(L1(R_{relative},R_{guess})\) \(A\leftarrow\) compute sparse matric from relative rotations while \(\left\|\varpi_{rel}\right\|<\varepsilon\) do: 1:\(\Delta R_{ij}={R_{j}}^{-1}R_{i}R_{ij}\) 2:\(\Delta\varpi_{ij}=\log(\Delta R_{ij})\) 3: solve \(A\Delta\varpi_{global}=\Delta\varpi_{ij}\) (minimize \(\left\|A\Delta\varpi_{global}-\Delta\varpi_{rel}\right\|_{l1}\)) 4:\(R_{new}=R_{old}\exp(\Delta\varpi_{global})\) end while
```  
**Algorithm 2**\(l1-norm\) Rotation Averaging  
The LTS (least trimmed squares) method is a robust regression method that was proposed by [PERSON] in 2006 [38]. They raised a new basic idea that makes it possible to compute a more approximate solution starting from any approximation to the LTS regression coefficients, and this process is called the c-step, where c stands for the 'concentration'. The c-step is an iterative process, which iteratively fits the h-subset (a subset of h cases out of \(n\) samples) with the smallest error until reaching convergence, while the pseudocode of each iteration in the c-step is shownas Algorithm 3. ```
1:estimate the regression coefficient \(\varpi_{old}\) based on the complete sample set \(H\)
2:compute the residuals based on \(H\) and sort according to ascending order: \(e_{old(i)},i=1,2,\ldots,n\)
3:put \(H_{new}\) as h samples with the smallest error
4:estimate the regression coefficient \(\varpi_{new}\) based on \(H_{new}\)
```  
**Algorithm 3** Pseudocode of C-step  
In the c-step, the regression coefficient \(\varpi_{old}\) is firstly estimated based on set \(H\), then we compute the residuals \(e_{old(i)},i=1,2,\ldots,n\) based on \(H\) and sort them according to ascending order: \(e_{old(i)},i=1,2,\ldots,n\)  
**Algorithm 4** Pseudocode of C-step  
In the c-step, the regression coefficient \(\varpi_{old}\) is firstly estimated based on set \(H\), then we compute the residuals \(e_ing order. Then, we extract h samples \(H_{new}\) with the smallest error, and the breakdown value h is always set as \(n/2\) to \(n\), which is the ratio of dirty data that can exist before making an incorrect estimate. In step 4, the new regression coefficient \(\omega_{new}\) is estimated based on \(H_{new}\). Additionally, it was demonstrated in [39] that often the robust solution is obtained after two or three c-steps; that is, step 2 and step 3 are repeated in the pseudocode above, which makes the convergence faster. The details of the LTS-1 IRA method are shown in Algorithm 4.