# Utilization of Merge-Sorting Method to Improve Stitching Efficiency in Multi-Scene Image Stitching
## 4 Multi-Scene Image Stitching Based on Merge-Sorting Method
\(e_{c}\) is the grayscale difference map for the image and \(e_{g}\) is the texture structure difference map for the image, and their formulas are:  
\[e_{c}=\left|\left|\frac{1}{5\times 5}\sum\limits_{m=-2}^{2}\sum\limits_{n=-2}^{2} img\_sub(i+m,j+n)-img\_sub(i,j)\right|\right| \tag{8}\]  
\[e_{g}=\left|(\frac{1}{5\times 5}\sum\limits_{m=-2}^{2}\sum\limits_{n=-2}^{2} Grad\_x(i+m,j+n))^{2}\right. \tag{9}\]  
\[\left.+(\frac{1}{5\times 5}\sum\limits_{m=-2}^{2}\sum\limits_{n=-2}^{2} Grad\_y(i+m,j+n))^{2}\right|\]  
where \(img\_sub(i+m,j+n)\) and \(img\_sub(i,j)\) represent the value of a pixel in a \(5\times 5\) rectangle with the coordinate \((i,j)\) as the center and the pixel value at the coordinate \((i,j)\), respectively. \(Grad\_x(i+m,j+n)\) and \(Grad\_y(i+m,j+n)\) are the gradients in the x and y directions, respectively. We used the Scharr operator to calculate the gradient value. Using dynamic programming to calculate the energy value of each matching point in the overlapping area of the image according to the energy formula (Equation (7)), we were able to find the lowest energy seam from the top to the bottom of the image. We set the pixel with the lowest energy value among the matching points of the first row of the overlapping area of the image as the vertex of the image stitching line, denoting it as \(p(i,j)\)), and then denoted the three matching points of the next row as \(p(i-1,\)\(j+1)\), \(p(i,j+1)\), and \(p(i+1,j+1)\) and calculated their energy values. The \(j\) direction of the point with the minimum energy value was the expansion direction of the next row. The matching points were selected in turn downward. When the matching points of the last row were obtained, all the matching points were connected together, forming the optimal splicing line. The N images were set as N nodes in the merge-sorting model, and then  
Figure 2: Image mosaic structure diagram of merge sorting. The \(m\)-th layer represents the input unordered images, and the first layer represents the final stitched image. The parts with the same colors represent the overlapping areas of the images. each adjacent pair of images were merged together for feature point matching. When the images met the condition of having the minimum number of matching points, we used dynamic programming to determine the seam line with the lowest energy in the images for fusion and then used them as the upper-layer-node images, while those that did not meet the condition were directly used as the upper-layer-node images. The images in the upper-layer node were stitched according to the steps of Algorithm 1 and, finally, the images of the same scene were stitched into a complete image. The flowchart for the MSIS method is shown in Figure 3. We used unordered images of two scenes, scene 1 and scene 2. The four images of scene 1 were obtained from [28], and the five images of scene 2 were taken with Samsung mobile phones. Using the stitching model based on the merge-sorting algorithm proposed in this paper, the images were first divided into five groups and the feature points of the images were matched when each pair of images was grouped and the stitching conditions were met directly. Then, stitching was performed sequentially. It can be seen that the stitching results for scene 1 and scene 2 differed. The stitching result for scene 1 was a wide-angle image, while the stitching result for scene 2 was a 180\({}^{\circ}\) semi-panoramic image. The stitching results are shown in Figure 4.  
Figure 3: The flowchart of the MSIS method.