# An Improved SIFT Underwater Image Stitching Method
## 3 Materials and Methods
### Underwater Image Stitching
#### 3.2.2 The Proposed Improved SIFT Method  
An improved SIFT method is proposed to address the drawback of only performing feature extraction once in the traditional SIFT algorithm. The reference image (image A) is denoted by \(I\) and the target image (image C) is denoted by \(I^{\prime}\). The expression is as follows:  
\[\mathbf{x}^{\prime\prime}=\mathbf{H}^{\prime}\mathbf{H}\mathbf{x} \tag{6}\]  
\[ \begin{bmatrix}x^{\prime\prime}\\ y^{\prime\prime}\\ 1\end{bmatrix} = \begin{bmatrix}h_{1}^{\prime}&h_{2}^{\prime}&h_{3}^{\prime}\\ h_{4}^{\prime}&h_{5}^{\prime}&h_{6}^{\prime}\\ h_{7}^{\prime}&h_{8}^{\prime}&h_{9}^{\prime}\end{bmatrix}\begin{bmatrix}h_{ 1}&h_{2}&h_{3}\\ h_{4}&h_{5}&h_{6}\\ h_{7}&h_{8}&h_{9}\end{bmatrix}\begin{bmatrix}x\\ y\\ 1\end{bmatrix} . \tag{7}\]  
where \(\mathbf{x}= \begin{bmatrix}x&y\end{bmatrix} ^{T}\) and \(\mathbf{x}^{\prime\prime}= \begin{bmatrix}x^{\prime\prime}&y^{\prime\prime} \end{bmatrix} ^{T}\) denote the pixel coordinates in the reference image and the pixel coordinates in the target image, respectively, \(\mathbf{H}\in\mathbb{R}^{3\times 3}\) represents the homography matrix from the training image (image B) to the reference image (image A), and \(\mathbf{H}^{\prime}\in\mathbb{R}^{3\times 3}\) represents the homography matrix from the target image (image C) to the training image (image B). Equation (7) shows the projection transformation of the target image (image C) to the reference image (image A). Again, the above equation can be organized as follows:\[x^{\prime\prime} = \frac{(h_{1}^{\prime}h_{1}+h_{2}^{\prime}h_{4}+h_{3}^{\prime}h_{7})x+ (h_{1}^{\prime}h_{2}+h_{2}^{\prime}h_{5}+h_{3}^{\prime}h_{8})y+(h_{1}^{\prime}h_ {3}+h_{2}^{\prime}h_{6}+h_{3}^{\prime})}{(h_{7}^{\prime}h_{1}+h_{8}^{\prime}h_{ 4}+h_{7})x+(h_{7}^{\prime}h_{2}+h_{8}^{\prime}h_{5}+h_{8})y+(h_{7}^{\prime}h_ {3}+h_{8}^{\prime}h_{6}+1)} \tag{8}\] \[y^{\prime\prime} = \frac{(h_{4}^{\prime}h_{1}+h_{5}^{\prime}h_{4}+h_{6}^{\prime}h_{ 7})x+(h_{4}^{\prime}h_{2}+h_{5}^{\prime}h_{5}+h_{8}^{\prime}h_{8})y+(h_{4}^{ \prime}h_{3}+h_{5}^{\prime}h_{6}+h_{6}^{\prime})}{(h_{7}^{\prime}h_{1}+h_{8} ^{\prime}h_{4}+h_{7})x+(h_{7}^{\prime}h_{2}+h_{8}^{\prime}h_{5}+h_{8})y+(h_{ 7}^{\prime}h_{3}+h_{8}^{\prime}h_{6}+1)}. \tag{9}\]  
During the stitching phase, we undertake a two-step approach involving coarse feature extraction and precise feature extraction, both based on the SIFT algorithm. Initially, coarse feature extraction is conducted on the reference image (image A) and the training image (image B). Subsequently, we employ the k-nearest neighbor algorithm (KNN) to gauge the similarity of key points between these two images. The KNN method utilizes the Euclidean distance as the measure for assessing feature point similarity. It performs feature point matching by systematically traversing all key points in the two images slated for concatenation. The Euclidean distance between any two corresponding feature points within these two images to be joined (\(D\)) can be defined as follows:  
\[D(F_{Q}^{i},F_{T}^{j})=\sqrt{\sum_{k=1}^{K}{(q_{k}^{i}-t_{k}^{j})}^{2}}, \tag{10}\]  
where \(F_{Q}^{i}\) and \(F_{T}^{j}\) represent feature points in the reference and training images, respectively, \(K\) represents the dimensions of the feature points, \(F_{Q}^{i}=(q_{1}^{i},q_{2}^{i},\ldots,q_{k}^{i})\), \(i\in[1,2,\ldots,M]\), \(M\) is the number of feature points in the reference image, \(F_{T}^{j}=(t_{1}^{j},t_{2}^{j},\ldots,t_{k}^{j})\), \(j\in[1,2,\ldots,N]\), and \(N\) is the number of feature points in the training image. Next, we iterate through all of the feature points in the reference image, identifying those within the training image that possess the closest Euclidean distances \(t_{1}\) and the second- closest Euclidean distances \(t_{2}\). After applying this selection process to the feature points, we can establish potential matching pairs.