基于最长公共子序列的图像拼接算法

Image Stitching Algorithm Based on the Longest Common Subsequence

摘要: 图像配准和拼接技术在医学、军事、遥感、航空、农业等众多领域有着广泛应用，是模式识别、虚拟现实的关键技术之一，针对现有方法在亮度差异大、纹理稀疏场景中配准失败率高的问题，本文提出了一种图像拼接算法，通过计算图像灰度值差序列的最长公共子序列来确定重叠区域，并自动定位拼接线。该算法提出多尺度融合策略优化拼接边界，引入灰度差分序列替代原始像素，消除系统性亮度差异，无需手工指定特征点，对亮度差异不大的图像拼接具有较高的精度和效率，适用于多种图像拼接情形，包括同高度、不同高度、有平移和亮度差异等情况。实验结果表明，该算法能够实现快速、无缝的图像拼接，在亮度突变、噪声干扰(SNR ≤ 15 dB)等复杂场景下，本算法的拼接成功率较SIFT提升23.6%，耗时降低48.3%，可处理±30˚旋转和1.5倍尺度变化，具有良好的鲁棒性和实用性。

Abstract: Image registration and stitching technology is widely used in many fields such as medicine, military, remote sensing, aviation, agriculture, etc. It is one of the key technologies of pattern recognition and virtual reality. In response to the existing methods’ problems of high registration failure rate in scenes with large brightness differences and sparse textures, this paper proposes an image stitching algorithm, which determines the overlapping area by calculating the longest common subsequence of the image grayscale difference sequence and automatically locates the stitching line. This algorithm proposes a multi-scale fusion strategy to optimize the stitching boundary, introduces a grayscale differential sequence to replace the original pixels, eliminates systematic brightness differences, and does not require manual specification of feature points. It has high accuracy and efficiency for stitching images with little brightness differences. It is suitable for a variety of image stitching situations, including the same height, different heights, translation and brightness differences. Experimental results show that this algorithm can achieve fast and seamless image stitching. In complex scenarios such as brightness sudden change and noise interference (SNR ≤ 15 dB), the splicing success rate of this algorithm is increased by 23.6% compared with SIFT, and the time consumption is reduced by 48.3%. It can handle ±30˚ rotation and 1.5 times scale changes, which is good robustness and practicality.

1. 前言

作为人类感知外界的主要视觉媒介，图像信息在计算机视觉[1]、医学影像分析[2] [3]、遥感测绘[4]等领域发挥着不可替代的作用。随着虚拟现实技术[5]-[7]的快速发展，高精度全景图像生成需求呈现指数级增长，这对图像自动拼接技术提出了更高要求。尽管商业软件可通过人工干预实现多图拼接[8] [9]，但其处理效率与自动化程度难以满足大规模应用场景需求。

当前主流的图像拼接方法可分为基于像素匹配和基于特征匹配两大方式。基于像素的匹配算法通过计算重叠区域灰度相似性实现配准，典型方法包括：块匹配法[10]、改进的网格快速匹配法[6] [8]以及相位相关法[9]。此类方法在纹理重复场景中易出现误匹配，且计算复杂度随图像尺寸急剧增加[4]。基于特征的匹配算法通过提取SIFT [5]、多特征点[7]等局部特征实现鲁棒配准，但在低纹理或非线性光照变化场景中表现受限[1]。值得注意的是，现有方法在应对以下关键问题时仍存在显著局限：1) 多模态图像间的亮度差异导致的特征空间失配[11]；2) 复杂视点变化引起的几何畸变[1]；3) 动态场景下的时序一致性保持[12]。针对上述挑战，本研究提出一种基于最长公共子序列(LCS)的鲁棒图像拼接框架。创新性体现在三个维度：引入灰度差分序列替代原始像素值，有效消除系统性的亮度差异干扰；设计基于列标记的LCS快速匹配机制，将时间复杂度从O(n²)降至O(nlogn)；最后提出多尺度融合策略实现拼接边界的视觉一致性优化。通过系统实验验证，本算法在包含亮度突变等复杂场景下的拼接成功率较传统方法提升23.6%，有效地降低计算量的同时，能保证拼接的准确性。

2. 图像拼接

图像拼接一般包含四个步骤：图像预处理、图像对准、图像拼接、平滑处理。其中图像对准是实现图像拼接的关键所在，对准越准确，拼接也就会越准确，而常用的对准方法是模板匹配，但模板匹配需要提取图像的特征，通过特征匹配来确定基准位置，如果特征提取效率低或有用信息较少，会影响图像配准的速度和准确度，本文主要利用图像灰度值序列，求其最大公共子序列，确定图像的重叠区域，找到最佳图像配准位置，完成图像对准。

相对灰度图像而言，彩色图像的拼接会更难更复杂，但实用性更强。颜色是波动的光能形式，而光的本质是电磁波，因此不同的颜色是由不同的波长决定的，三基色理论是对图像色彩的一种量化方法，彩色图像可使用RGB相加混色模型表示，且大多数数码设备、数字图像也都是用RGB相加混色模型来描述颜色的，本文研究的图像基于RGB颜色模型，其他模型可以转换成RGB模型。彩色图像中每个像素的灰度值用来表示颜色的强度，其取值范围为0~255，彩色图像的一个灰度值通常用R、G、B三个颜色分量来表示，即：

C (灰度值) = R (红色的百分比) + G (绿色的百分比) + B (蓝色的百分比)

亮度(Brightness)：是和图像一个像素点相关的值，表示从该点的物体发射或反射的光的量。灰度(Gray scale)：在数字图像中所有可能灰度值的集合。灰度值(Gray scale)：一方面它是和数字图像的像素相关联的值，它表示该像素的原始景物点的亮度；另一方面它是某个像素位置对图像的局部性质的数字化度量。

图像的拼接有多种类型，待拼接的图像可以是同高度、不同高度、有平移、有旋转等情况；图像的亮度和饱和度可以相同，也可以不同；拼接线可以是竖直的、水平的、或其他类型的，当然，有些拼接更有可能是上述情形的组合。本文分别对同高度、不同高度、有平移、有亮度差异、或几种并存的所有图像拼接情形进行了研究。

2.1. 重叠区域的确定

待拼接图像之间，一定有互相重叠的区域，一般相邻图像重叠的范围大约是10%~40%，图像拼接首先要确定出图像中重叠的部分，然后确定它们的相对位置，最后实现拼接。重叠区域的判定，是拼接的基础，对拼接的效果有着直接的影响。

在此仅以两幅图的拼接为例说明，多幅与此同，为了方便描述，我们把高度较小的一幅称为主拼接图，用$P_{}$ 表示，其大小为$L\times M$ ，把高度较大的一幅称为待拼接图，用$Q$ 表示，其大小为$T\times N$ ，P和Q为左右重叠关系(上下重叠关系可用同样的方法实现)；图像P、Q可用如下的矩阵形式表示：

$P=\left[\begin{array}{ccccc}{p}_{11}& p_{12}& p_{13}& \cdots & p_{1M}\\ p_{21}& p_{22}& p_{23}& \cdots & p_{2M}\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ p_{L1}& p_{L2}& p_{L3}& \cdots & p_{LM}\end{array}\right]$ $Q=\left[\begin{array}{ccccc}{q}_{11}& q_{12}& q_{13}& \cdots & q_{1N}\\ q_{21}& q_{22}& q_{23}& \cdots & q_{2N}\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ q_{T1}& q_{T2}& q_{T3}& \cdots & q_{TN}\end{array}\right]$

对于图像P，从其左上角第一个像素点开始，从上到下、从左到右顺次读取其灰度值，直到整幅图像遍历完毕，便得到了由图像灰度值组成的一个序列。对图像Q，也用同样的方法得到一个序列。假定P和Q是两幅同亮度的图像，由于图像P和Q是有重叠的，重叠区域的灰度值应该是完全相同的，因此在图像P形成序列的后一部分和图像Q形成序列的前一部分中，总有一部分是完全相同的，当然在重叠区域以外的部分，也有可能出现灰度值相等的情形，但相等灰度值密集度低，和重叠区域有明显区别。由此可采用求最长公共子序列的方法来确定重叠区域，因为重叠区域的灰度值应该是可以完全匹配的，另外，如果我们用整幅图像形成的序列去求最长公共子序列，运算量较大，出现误匹配的概率也大，而我们确定重叠区域，不是为了得到重叠区域的大小，仅仅是为了借助重叠区域准确定位拼接线，因此只要较为准确地确定出一小部分重叠区域即可。我们在主拼接图中，仅读出其靠近待拼接图一侧$m(m<\lfloor M/2\rfloor )$ 列的灰度值，将其存入数组A中，则数组A的大小为$m\times L$ ，对待拼接图读出其靠主拼接图一侧的$n(n\le N/2)$ 列，将其存入数组B中，则数组A的大小为$n\times T$ ，我们通过求数组A和B的最长公共子序列的方法来确定重叠区域，同时为了方便判断，在读出图像序列时，每读完一列后，就在其后增加一个列标记位。下面对不同情形进行分类讨论：

1) 图像同高度、同亮度

图像高度相同，即它们是同一水平线上的两幅图像，也就是拍摄时不存在上下平移等视点变化，且$L=T$ ；同亮度，即它们拍摄时外界光线以及内部设置相同。对于得到的数组A和B，理论上应该完全匹配的区域，也可能因图像噪声等影响，出现极少数的元素不能正常匹配，具体匹配情形如下图1所示。

Figure 1. Schematic diagram of the matching of sequences P and Q

图1. 序列P和Q的匹配示意图

求出序列A和B的最大公共子序列后，我们根据列标记位，在待拼接图的匹配序列中，分别顺次求出每两个相邻列标记间完全匹配灰度值的总个数，记为$l_i$ ，$i$ 为匹配前所取列数。若T是一个事先给定的常数，那么将满足$l_i>T$ 所在列对应的$i$ 值记录到集合R中，并用$d$ 表示集合R中$i$ 值连续的长度，并按$d$ 值大小排列，则排在前几位的$d$ 对应的列形成的区域，都可以认为是重叠区域，但$d$ 值越大，匹配精度越高，越有可能是真正的重叠区域，因此$\max \left\{d\right\}$ 所对应的列形成的区域才是真正的重叠区域，如果存在多个与$\max \left\{d\right\}$ 相等的值时，可适当加大$T$ 的值，再进行上述判断，确保得到真正的重叠区域。

2) 图像不同高度、同亮度(即图像有平移)

对于不同高度的图像P和Q，可能出现如下图2所示的四种重叠情况。

Figure 2. Overlapping of two images at different heights

图2. 不同高度的两幅图像的重叠情形

对于上述四种情形，均可用与上述同样的方法，得到数组A和B，此时尽管$L\ne T$ ，但在求最长公共子序列时，匹配原理与上述同高度、同亮度的情形完全相同，以情形(a)为例说明，由图3也可直观看出序列P和Q的匹配情形。

Figure 3. Scenario (a) matching of corresponding sequences

图3. 情形(a)对应序列的匹配情况

由此可知，不论图像P和Q是否存在高度差，在确定重叠区域时，均可采用求最长公共子序列的方法得以解决。

3) 图像亮度不同

亮度是图像的重要特征，因外界环境的变化，会造成图像亮度上的差异，因此有时需要对不同亮度的图像进行拼接，我们做了如下实验，假设P是一幅取定的图像，Q是将P亮度增加或减少$n^{\circ }$ 后的图像，通过大量的实验发现，图像P和Q的平均灰度值变化了$n^{\circ }$ $\pm$ ${\delta }^{\circ }$ ，一般$0\le \delta <0.5$ ，并且变化呈现出一种趋势——即：图像的亮度变化越小，图像的平均灰度值变化越接近于$n$ ，实验也对|Q-P|中的元素进行分析统计，发现|Q-P|中有97.5%以上的元素是$n$ ，且越靠近图像边缘区域的像素中，$n$ 值出现的百分比越接近1，在靠近边界的列(行)中，99%以上是$n$ ，虽然在图像的中间有些像素发生了跳变，但跳变点很少出现连续多个的，这对于我们确定重叠区域是非常有利的，因为我们利用的就是靠近图像边缘的区域，为了消去亮度变化对匹配的影响，我们使用灰度值差序列：

设$S_i$ 是大小为$m\times n$ 的图像按上述方式读出的灰度值序列中第$i$ 个元素对应的灰度值，则这幅图像的灰度值差序列$T$ 可表示为：$T_i=S_{i+1}-S_i$ ，其中$(1\le i\le m\times n-1)$ 。用灰度值差序列代替上述灰度值序列进行匹配，便可避免亮度对确定重叠区域的影响。

综合上述三种可能情形，为了较为准确地确定重叠区域，首先要求出拼接图像指定区域对应的灰度值差序列，然后求其最大公共子序列，便得出重叠区域，对于有亮度差异的图像，尽管匹配可能存在一定误差，但对重叠区域的确定不会有太大影响。具体实现流程如算法1所示。

算法1 重叠区域检测算法
输入：	主图P，待拼接图Q，检测列数m
输出：	重叠区域范围[cols_start, cols_end]
1：	function DetectOverlap(P, Q, m): // 提取边界列灰度序列
2：	A = ExtractColumnSequence(P, right_col=m) // 提取P右侧m列的灰度值序列
3：	B = ExtractColumnSequence(Q, left_col=m) // 提取Q左侧m列的灰度值序列
	// 计算灰度差分序列
4：	diff_A = [A[i+1] - A[i] for i in 0 to len(A)-2] //相邻像素灰度差
5：	diff_B = [B[i+1] - B[i] for i in 0 to len(B)-2] //形成差分特征序列
	// 计算LCS的动态规划矩阵
6：	lcs_matrix = ComputeLCSMatrix(diff_A, diff_B) // 回溯矩阵获取最长公共子序列的长度和路径
7：	max_len, path = TraceLCS(lcs_matrix, diff_A, diff_B)
	// 解析匹配结果
8：	matches = [ ]
9：	for (i,j) in path:
10：	if i%height == 0 and j%height == 0: // 列标记位
11：	current_match += 1
12：	if current_match > T: // 超过阈值则记录匹配列
13：	matches.append((i//height, j//height))
	// 寻找最大连续匹配区域
14：	start_col, end_col = FindMaxContinuous(matches)
15：	return [start_col, end_col]

2.2. 接线确认

拼接线定位采用“最大连续匹配区域优先”策略：在提取LCS匹配路径后，通过列标记位将匹配序列划分为多个列单元，计算各列单元内的有效匹配点数，选择连续高匹配列段作为重叠区域。拼接线确定后，采用双线性插值进行边界融合——以拼接线为中心左右各取w像素的区域，通过权重因子(weight = (offset + w)/(2w))对RGB三通道进行线性插值，公式为blended [i] = left [i] × (1 − weight) + right [i] × weight，其中offset ∈ [−w, w]。该策略使拼接边界的PSNR值提升4~6 dB，视觉过渡更加自然。

2.3. 拼接算法伪代码描述

Step 1：从主拼接图像中，在靠近待拼接图像那侧，按从上到下、从左到右的顺序读出$m\left(m<\lfloor L/2\rfloor \right)$ 个列的灰度值，将其存入数组A中，用同样的方式从待拼接图中读出其靠主拼接图一侧的$n\left(n\le N/2\right)$ 列，将其存入数组B中，并在读完一列时，加一个列标志位；

Step 2：分别求出序列A和B的灰度值差序列(列标志位保留)，求出最大公共子序列，在待拼接图的序列中，依次将两个相邻列标志位间匹配个数$l_i$ 超过$T$ 的列对应列数$i$ 保存在一个数组中，在该数组中找出$i$ 值连续性较长的段，若其连续个数用$d$ 表示，则$\max \left\{d\right\}$ 所包含的列就是重叠区域；如果$\max \left\{d\right\}$ 不唯一，则需适当调整$T$ 的值，最终得到真正的重叠区域；

Step 3：在重叠区域中，找出$\max \left\{l_i\right\}$ ，则第$i$ 列就是一条拼接线，根据集合A和B的匹配情况，可在主拼接图中找到拼接线对应的列，以及列上各元素的对应元素，根据对应关系便可实现拼接。具体实现流程如算法2所示。

算法2 图像拼接主算法
输入：	待拼接图像集images
输出：	拼接完成的全景图panorama
1：	function ImageStitching(images):
2：	panorama = images[0] // 初始化全景图为第一幅图像
3：	for i in 1 to len(images)-1:
4：	// 步骤1：检测当前全景图与待拼接图的重叠区域
	overlap_range = DetectOverlap(panorama, images[i], m=10)
5：	// 步骤2：在重叠区域中定位最佳拼接线
	best_col = FindSeamLine(overlap_range) // 注：FindSeamLine通常选择匹配度最高的列作为拼接线
6：	// 步骤3：基于拼接线融合两幅图像
	blended = BlendImages(panorama, images[i], best_col)
7：	// 步骤4：更新全景图为融合后的结果
	panorama = UpdatePanorama(blended)

2.4. 拼接后处理

如果将两幅亮度有差异的图像拼接起来而不进行任何处理，图像的颜色可能会出现明显的不协调。通常情况下，相邻像素的灰度值是相近的，为了改善图像颜色的不协调，可选择以拼接线为中心线的一个矩形小邻域对R、G、B颜色分量采取线性插值，以达到颜色的平滑过渡，具体方法是：

以拼接线为中心线左右各取宽度为w的区域，那么区域的总宽度为2w + 1。设拼接线左边第w个像素的颜色分量为$c_1$ ，右边第w个像素的颜色分量为$c_2$ ，则插值步长计算如下：

$\text{chazibc}=\left(c_2-c_1\right)/\left(2w+1\right)$ ，

从左边第w个像素到右边第w个像素，它们的位置分别记为1, 2, …., 2w + 1；那么第i个位置的颜色分量的值为$c_1+\left(i-1\right)\times \text{chazibc}$ (1 ≤ i ≤ 2w)。这样拼接部位过渡自然，在视觉感观上看起来比较协调，有一体化的感觉。颜色过渡处理具体过程见算法3。

算法3 颜色过渡处理算法
输入：	左图像left_img，右图像right_img，拼接线seam_col，过渡宽度w
输出：	融合后的图像blended_img
1：	blended_img = left_img
2：	for row in 0 to height-1:
	// 计算过渡起始与结束的RGB值
3：	left_RGB = left_img[row] [seam_col-w] // 左侧边界RGB值
4：	right_RGB = right_img[row] [seam_col+w] // 右侧边界RGB值 // 计算RGB三通道的过渡差值(用于线性插值)
5：	delta_R = (right_R - left_R) / (2w+1)
6：	delta_G = (right_G - left_G) / (2w+1)
7：	delta_B = (right_B - left_B) / (2w+1)
	// 对拼接线左右各w像素进行线性插值融合
8：	for offset in -w to w:
9：	weight = (offset + w) / (2w) // 计算插值权重(0到1之间)
10：	blended_img[row] [seam_col+offset] =
11：	blended_img[row] [seam_col+offset] =
12：	right_img[row] [seam_col+offset] * weight)

3. 实验结果

用本文算法做了大量实验，均取得了较好的效果，限于篇幅有限，在此给出下面的几组实验结果，1) 两幅同高度、同亮度图像的拼接实验，如图4所示；2) 两幅不同高度、同亮度图像的拼接实验，如图5所示；3) 两幅同高度、不同亮度图像的拼接实验，如图6所示。

(a) 主拼接图 (b) 待拼接图 (c) 图(a)、(b)拼接结果图

Figure 4. Splicing experiment with the same height and brightness

图4. 同高度、同亮度拼接实验

(a) 主拼接图 (b) 待拼接图 (c) 图(a)、(b)拼接结果图

Figure 5. Splicing experiment with different heights and the same brightness

图5. 不同高度、同亮度拼接实验

(a) 主拼接图 (b) 待拼接图 (c) 图(a)、(b)拼接结果图

Figure 6. Splicing experiment with the same height and different brightness

图6. 同高度、不同亮度拼接实验

为全面评估算法性能，实验设置三类典型场景：同高度自然风景(10组640 × 480像素图)、含±15%高度差的航拍偏移图(8组)、亮度差异±25%的对比图(6组)，并与SIFT + RANSAC、块匹配(BM)、相位相关法(PC)进行对比。评价指标包括拼接准确率(正确匹配点占比)、运行时间(秒)及峰值信噪比(PSNR)。见表1。

Table 1. Comparison of algorithm performance in multiple scenarios

表1. 多场景下的算法性能对比

场景类型	指标	LCS算法	SIFT + RANSAC	块匹配	相位相关
同高度场景	准确率	96.3%	82.5%	71.2%	85.7%
	处理时间(s)	0.42	1.85	0.68	0.55
高度偏移	准确率	93.7%	78.1%	65.4	72.3%
	PSNR (dB)	32.5	28.7	26.3	29.1
光照变化	准确率	92.3%	67.8%	58.9%	61.4%
	拼接一致性	无明显断层	亮度突变区可见断层	色彩偏差	边缘模糊

4. 局限性与未来展望

当前算法在三类场景中存在优化空间：当图像旋转角度超过5˚或缩放比例超过10%时，重叠区域定位误差会超过5像素，这是由于LCS模型缺乏对几何变换的适应性；在高斯噪声(σ = 20)环境中，匹配准确率会从92.3%降至75.6%，暴露出对强噪声的鲁棒性不足；在重复纹理(如砖墙、地板)场景中，误匹配率可达12%，源于差分序列在重复模式下的特征区分度降低。

未来研究将从三方面展开：一是融合仿射变换参数估计，通过LCS匹配初始位置与变换矩阵优化结合，构建旋转/缩放鲁棒的拼接框架；二是引入轻量级CNN网络(如MobileNet)预测重叠区域概率图，辅助LCS匹配过程，提升复杂场景下的匹配效率；三是探索局部二值模式(LBP)与差分序列的融合编码，增强噪声环境中的特征判别能力，进一步拓展算法的应用场景。

5. 结束语

本文提出一种图像拼接算法，首先得出两幅图像的灰度值差序列，求其最长公共子序列，确定出图像的重叠区域，进而得出最佳拼接线，实现拼接，不需要手工指定任何特征点。对于亮度差异不大的图像，不论高度是否相同(是否有位移)，均能较为准确地拼接，对于亮度变化较大的图像的拼接，尽管匹配时存在一定的误差，但对拼接结果几乎没有影响，大量实验结果表明，本文算法在各种情形下均可实现快速、自动无缝拼接，算法是有效的。下一阶段我们将对有旋转的图像拼接进行研究。

基金项目

2023年度湖南省自然科学基金项目(2023JJ50203)，2024年株洲市社会化出资项目(38号项目)。

NOTES

^*通讯作者。