杨英杰 杨 帆 曾庆喜

改进同余变换不变特征的视频拼接算法

杨英杰1杨 帆1曾庆喜2

1(东北电力大学信息工程学院 吉林 吉林 132012)

2(南京航空航天大学车辆工程系 江苏 南京 210096)

视频拼接的平滑过渡问题，是图像处理的难点，为很好地解决这一问题，提出一种基于Sobel算子改进的同余变换不变特征CIF(Congruence transformation Invariant Feature)的视频拼接算法。在图像配准阶段，采集视频序列的关键帧，首先运用改进的CIF算法提取特征点并匹配，然后基于RANSAC算法，估算并优化空间变换矩阵。在图像融合阶段，采用动态连接缝调整算法与色调正常化算法协同工作，以消除图像重合区域的重影与色差。实验表明，该算法不仅能够实现视频的实时拼接，还能很好解决视频拼接的平滑过渡问题。

视频拼接 同余变换不变特征算法 Sobel算子 特征点对 动态连接缝调整算法 图像色调正常化算法

0 引 言

视频拼接是将具有重叠部分的图像拼接在一起，得到一幅完整的图像，以达到实现定点全方位浏览的目的，多应用于大视场监控、航空测绘、实景地图、物联网以及游戏画面虚拟情景模拟等大型运动场景的再现，因而成为近年来国内研究的热点。

视频拼接是以图像拼接为基础的。图像拼接主要包括两个流程：图像配准与图像融合[1]。其中图像配准主要涉及空间变换矩阵(也称单应矩阵)的求解。图像融合主要将图像拼接为一幅平滑无缝的全景图像。将不同的图像配准方法归类，主要可以分为三种：基于灰度信息的方法，基于变换域的方法，以及基于特征的方法[1,2]。其中，基于特征的图像配准方法因其较好的时效性，正确率以及鲁棒性最为常用。对此，国内外研究已有很多算法，如：由D G Lowe提出的SIFT算法[3]以及Herbert Bay等人提出的在SIFT算法基础上改进的SURF算法[4]是较为常见的算法。Dianyuan Han分别在PC上基于SIFT算法[5]以及在手持电脑上基于SURF算法[6]实现了高大树木全景图像的拼接。虽然SIFT与SURF算法的描述能力强，但由于计算复杂度较高，通常效率较低。再如，由Rosten E等人最早提出了一种加速分割检测特征FAST(Features from Accelerated Segment Test)算法[7,8]。此后，由Rublee E等人在FAST的基础上又进行了改进，结合方向性特征算子BRIEF[10]，提出了ORB算法[9]。最近，Tian Fang等运用ORB算法进行图像拼接，并结合改进的图像融合算法处理全景图像的边缘平滑过渡问题[11]。通常，ORB算法要快于SURF与FAST算法，但原理仍然较为复杂。而Takayuki Nakamura等提出的同余变换不变特征CIF算法[12]，其虽然简化了描述子(16维向量)，提高了计算速度，但缺点在于，CIF算法原本用于机器人自动寻址领域，而非图像处理领域，其描述子是通过某一特征点与其周围具有序列的点求得的，而图像中的像素点是没有特定序列的。因此，为了将其引入图像处理中，还需对其做进一步的改进。

针对上述问题，本文提出了一种基于Sobel算子改进的CIF算法，首先提取并匹配特征点，计算其空间变换矩阵(也称单应矩阵)，然后采用动态连接缝调整算法与色调正常化算法处理图像融合处的平滑过渡问题。

1 改进的CIF特征值提取与匹配

视频拼接如果对视频流的每帧计算单应矩阵，存在准确性下降和无法实时拼接的问题。大型场景中摄像头位置通常是相对固定的，实际上只需提取视频流中尚无运动物体的背景帧计算对应的单应矩阵即可[14]。这里将这些背景帧称为“关键帧”。结合前述图像拼接的一般步骤，视频拼接主要流程如图1所示。

图1 视频拼接主要流程

由图1可知，视频拼接求解单应矩阵的第一步便是特征点的提取。

1.1 CIF基本算法

CIF是全局扫描中特征点的描述子。它是由特征点及其周围的点集求得，其表示了某点附近的二维形状。通常，一个全局扫描的CIF特征向量的生成，可以分为以下四个步骤：

(1) 确定特征点。定义特征点为全局扫描中梯度变化较大的点。扫描点pi的梯度是以计算连接pi与pi+α两点之间的线段的梯度为基础的。在一个有限半径的邻域中，pi+α是pi的邻域中立pi最远的点。梯度ηi表示为：

(1)

线段梯度的变化率是在一个扫描点pi处基于梯度ηi与ηi+1计算得到的，如下式所示：

θi=ηi+1-ηi

(2)

如果线段梯度的变化率大于阈值thresh，就得到了特征点pi。

(2) 建立局部坐标系。定义一个局部坐标系Σpi，原点就是特征点pi，x轴方向是ηi-1与ηi的平均值。y轴是与x轴垂直的。特征点pi的CIF描述子是相对于局部坐标系Σpi来表示的。所以，在坐标系因方向变换而产生的同余变换的前提下，CIF描述子是不变的。

(3) 绘制有向线段。考虑到CIF描述子是由特征点pi周围的M个最邻近点计算得到的，具体说是由连接特征点pi与邻域扫描点的线段的梯度直方图统计得到的。为此，定义了两种相对于局部坐标系Σpi的线段。第一种是有向线段SP，它以特征点为起点，以周围M个邻近点为终点；第二种是有向线段SD，它是以一个扫描点pi为起点，以扫描点pi+n为终点，n为不小于1的整数。

(4) 建立直方图。直方图由有向线段SP与有向线段SD构成，分别用来统计分布在八个统计区间内的有限线段条数，每个统计区间的大小为π/4。将统计直方图合并组成16维向量，前8维代表SP线段的分布情况，后8维代表SD线段的分布情况。这16维向量就是特征点pi的CIF描述子。

1.2 基于Sobel算子改进的CIF算法

CIF基本算法在提取特征点时涉及到某一点邻域中最远点以及邻域中的最近M个点，而在图像中，某一点邻域最远点以及最近M个点都不是唯一的。这里引入Sobel算子对其进行改进。Sobel算子同样涉及梯度计算，它与CIF基本算法提取特征点核心思想兼容。

在数字图像梯度的基础上，由Sobel提出一种将方向差分运算与局部平均相结合的方法，Sobel算子通过2个3×3的模板，对图2所示的图像中同样大小窗口进行卷积，分别求得x方向与y方向的偏导数，从而得到图像的梯度。

图2 像素点a4及其上下左右八邻域

Sobel算子是一种梯度幅值，其描述为：

(3)

其中的偏导数sx与sy用下式计算：

sx=(a0+2a3+a6)-(a2+2a5+a8)sy=(a0+2a1+a2)-(a6+2a7+a8)

(4)

Sobel算子，sx和sy可用卷积模板来实现：

(5)

通常，将式(3)近似表示为：

(6)

基于Sobel算子改进的CIF算法同样分为四个步骤：

(1) 确定特征点。考虑到图像中每一个像素点的相邻点不止一个，这里不使用相邻像素点的梯度差值，而是运用式(6)计算图像中每个像素点的梯度幅值mag(▽f)，如果这个矢量幅度大于预设的阈值threshhold，则定义该点为特征点pi。

(2) 建立局部坐标系。与CIF基本算法同理，定义一个局部坐标系Σpi，原点就是特征点pi，x轴方向与pi的Sobel算子计算得到的梯度方向一致，y轴与x轴垂直且向上，设梯度方向是Φ(x,y)，下式表示了其求解方法。

(7)

局部坐标系如图3所示。

图3 局部坐标系Σpi

(3) 绘制有向线段。图像中距离特征点最近的M个像素点一定分布在其周围固定位置，这样不能反映特征点附近二维形状信息。使用Sobel算子提取的特征点，通常位于图像边缘。因此，取特征点pi及邻域最近10个特征点(即M=10)求解图像中的CIF描述子，既能避免最近的M个像素点位置固定的问题，还能反映该特征点周围的二维形状信息。这里以特征点pi为起点，10个特征点为终点，绘制有向线段SP。如图4所示。

图4 SP线段示意

在第(1)步中确定的特征点，不具有如同CIF基本算法中的特定序列。因此，在图像中需要舍弃规定特征点特定序列的有向线段SD。

(4) 建立直方图。实际上，建立局部坐标系之后，求解SP线段的分布直方图可以简化为求解其余特征点分布的直方图。如图5所示，直方图的横坐标表示梯度方向-π～π。梯度的范围被平均分为十六个统计区间，每个统计区间的大小为π/8。统计特征点pi与其它特征点的夹角落在每一个区间的个数。将统计的直方图分布组成16维向量，其中每一维代表落入某一区间含有特征点夹角的数量，这16维向量就是特征点pi的CIF描述子。其中，SP表示有向线段之一，θ表示有向线段与x轴的夹角。

图5 改进CIF有向线段生成与直方图统计

1.3 特征点粗匹配与单应矩阵求解

定义输入帧特征点为qj，(其中j=1～Ni，且Ni表示输入帧中特征点的数量，i表示input frame输入帧)，参考帧特征点为pi(其中i=1～Nr且Nr表示参考帧中特征点的数量，r表示reference frame参考帧)，如果参考帧中的特征点pi与输入帧的特征点qj匹配，那么它们的CIF描述子应该是相似的。

定义输入帧特征点qj与参考帧特征点pi的CIF描述子分别为hi与hj，定义输入帧与参考帧之间CIF描述子的相似度量为Cij，它是16维向量的欧式距离，即：

(8)

式中，Cij表示特征点qj与 pi之间的相似性度量，hk表示CIF描述向量第k维的值。于是，可以将输入帧中的每一个特征点qj与参考帧中对应的特征点pi两两作比较，即比较两两特征点之间的相似度量。

遍历输入帧特征点与参考帧特征点pi的相似度量Cij(i=1～Nr)，寻找对应于特征点qj的最小相似度量Cj-min,为：

Cj-min=min{ C1j,c2j,…,CNrj}

(9)

随后，根据一定策略求解相似度阈值T，其作用在于初步排除不在重叠区域的点对(不匹配点对)。受不同环境影响，固定阈值会导致匹配结果不准确，因此求解相似度阈值T的策略如下：

(1) 遍历输入帧每个特征点的最小相似性度量Cj-min,，找出其中的最大值M，如式(10)所示：

M=max{C1-min,C2-min,C3-min,…,CNi-min}

(10)

(2) 根据第一步求得的最大值M，求解相似度阈值T，如式(11)所示：

T=k×M

(11)

其中，k是在区间(0,1]的常量，k取值0.25时，处理效果较好。

将输入帧中每一个特征点qj的最小相似度量Cj-min,与相似度量阈值T作比较，如果小于阈值T，则认为此特征点与参考帧中的特征点匹配，且同在重叠区域中，反之则排除不在重叠区域中的点对。

遍历完输入帧特征点对之后，如果在匹配点对中，包含相同的参考帧特征点，则舍弃相似度量较大的一对。这是为了防止输入帧中不同特征点与参考帧中同一个特征点产生的重复配对。特征点粗匹配算法过程如图6所示。

图6 特征点粗匹配过程

随机抽样一致RANSAC(RANdom SAmple Consensus)[13]算法最早由Fisher和Bolles提出，它是一种从一组包含异常值的观测数据集中估计数学模型的方法，同时也是一种迭代方法，通过反复选择数据中的一组随机子集来优化单应矩阵。假设点(x,y)经过空间变换矩阵H变换到点(x′,y′)，那么，由齐次坐标的性质可知，点(x,y)和点(x′,y′)之间的关系由式(12)表示：

(12)

在视频拼接过程中，由式(12)可知，可以选择4对匹配特征点使用直接线性变换来计算得到一个待修正的单应矩阵H。

RANSAC在评估单应矩阵的过程中具有很好的鲁棒性，这里它采用了一组随机抽样的特征点对(用来事先计算单应矩阵的4对点对除外)去评估变换矩阵，之后找到一个与匹配特征点对相符程度最高的单应矩阵。

按设定的有限次数，重复执行这个评估过程，每次产生的单应矩阵，要么因为与之相符的特征点对太少而被舍弃，要么因为比现有单应矩阵相符的点对更多而替换现有的单应矩阵。

在完成以上步骤之后，视频流的每一帧中每个像素的坐标投影只需与优化之后的单应矩阵进行一次乘法即可，从而大幅降低了坐标变换的计算量。

2 图像融合

通过上述操作，将输入帧的平面投影到参考平面，就可在视频帧之间的重合区域中根据连接缝的位置进行融合。在视频拼接中，如果一个运动物体从视频帧之间一条固定的连接缝的一边穿越到另一边，可能会引起移动物体上的重影。因此，在这种情况下，连接缝的位置应该能够动态改变。动态连接缝调整算法由以下步骤组成。

首先，求得不同视频帧重叠区域中每个像素点邻域的灰度差异之和，并根据像素点的坐标建立重叠区域灰度差异表。其中，每一个权值Diff(x,y)是重合区域点(x,y)邻域灰度差异值之和。如式(13)，BL和BR表示不同帧的灰度值，它们是计算不同像素块的灰度而不是单独的像素，这样可以减少由不同物体具有相同颜色而引起的误差。

(13)

(14)

其次，根据灰度差异表能够找出当前帧中差异最小的路径。其表明在这条路径上的元素有着更高的相似度。式(14)表示了利用递归方法获得每一帧的差异最小路径，其中W(x,y)表示始于一帧重叠区域顶端到点(x,y)的最小差异路径。如图7所示，R表示重叠区域的宽度；I表示输入视频的宽度；A(A′)、B(B′)、C(C′)、D(D′)、E(E′)表示的是出现在路径上的两帧对应的重合点。

图7 在重叠区域找到最好的连接缝

最后，考虑视频帧数较多，对每一帧计算不同阈值耗时较长，因此将当前帧连接缝的差异值与预设的阈值N作比较，如果当前差异值大于预设的阈值N，则用当前帧中新的连接缝来替代前一帧的连接缝。否则保持原连接缝不变。其中，预设阈值N取0.75时，处理效果较好。这种机制是为了防止由于快速变换连接缝而引起的当前全景视频的闪烁。动态连接缝调整算法过程如图8所示。

图8 动态连接缝调整算法

考虑到不同摄像头设置，或者因为外界光线强度不同引起的不同曝光时间，同一物体在不同视频帧中色调可能不一样。总的来说，严重的色差会导致在拼接结果中出现明显的连接缝。为了解决这个问题，运用一种基于特征的色调正常化方法来修正不同视频帧之间的色调失配，使得在图像的拼接处的颜色达到一种自然过渡的效果。

为此，通过运用视频帧之间匹配点对的RGB数据，求解一个线性方程参数来寻找能够使特征点的RGB值具有相近的关系。具体算法如式(15)所示。

(15)

式中，参数α是比例因子，而β则是微调常量。通过该色调正常化算法，能够得到具有相同颜色基的不同待拼接视频帧，从而降低了图像融合时的误差。

3 实验结果

实验场景选在了地下停车场，摄像头设置如图9所示。

图9 摄像头布局示意图

考虑到停车场摄像头布置的一般情况，要达到视频拼接的技术要求，相邻摄像头之间至少应有20%的重叠区域。本实验中一个摄像头监控约四个车位的区域(每个摄像头视角约120°，监控区域涵盖了车位旁的车道)，据此，摄像头与摄像头之间至少要有一个车位的重叠区域，才能满足拼接的基本要求。

主机参数配置如表1所示。

表1 主机配置

如图10所示，选取三个视频采集点的背景帧作为关键帧，选取中间帧作为参考帧。图11是运用改进CIF算法中利用Sobel算子提取特征点之后的图像处理效果。为了突出特征点的位置，按二值化处理，将梯度幅值大于100的点置为白色，其余置为黑色。放大图片，从中可以明显看出特征点的位置基本处在物体的边缘处，除有少量干扰像素外，其保留了图像中的绝大部分边缘信息。

图10 三个视频采集点的关键帧

图11 特征点二值化后的图像

图12给出了特征点对的粗匹配结果。其中不难看出，大部分点对都出现在重叠区域内，并且在边缘处，但也有少数匹配点对出现在了重叠区域之外。

图12 特征点对粗匹配结果

图13显示的是用RANSAC算法迭代优化后的图像拼接处理效果。经过优化，避免了误匹配特征点给单应矩阵的正确计算带来的干扰。

图13 RANSAC迭代优化结果

在图像融合的过程中，分别采用了三种不同的策略来进行处理后的效果对比。

策略1使用了固定的连接缝来进行视频拼接，如图14(a)所示，当汽车穿过重叠区域时，可以看到拼接效果中，重叠区域汽车尾部产生了明显的重影。

策略2使用了动态连接缝调整算法，但不使用色调正常化方法来进行视频拼接。如图14(b)所示，汽车尾部的重影消失了，但是如图中虚线部分所圈出的，在连接缝左右，色调差异较为明显，突出了连接缝的位置，但由于没有使用色调正常化算法，拼接效果并不平滑。

策略3使用了所有算法。如图14(c)所示，可以看到拼接结果既没有策略1出现的重影，也没有策略2中较为明显的连接缝。拼接结果较为平滑，效果较好。

图14 不同拼接策略产生的不同拼接效果

为评价改进算法在实时性方面的性能，考虑到实验结果具有可比性。特在同一台主机上，针对不同视频采样点，采用不同算法，分别进行了特征点的提取与匹配时间的实验，最终平均时间统计结果如表2所示。从实验结果可明显看出，ORB算法快于SURF算法，而改进CIF算法速度要略快于ORB算法。

表2 平均处理时间比较 单位：ms

4 结 语

在CIF算法的基础上，改进后的CIF视频拼接融合算法灵活运用了Sobel算子，成功地将CIF引入到图像的特征点提取与描述过程中，通过平均处理时间比较，改进的CIF算法的提取速度比传统ORB算法耗时缩短了(9.2-7.9)/9.2≈15%，与SURF算法相比缩短了(34.3-7.9)/34.3≈77%。在匹配时间上，改进的CIF算法与ORB相比，耗时缩短了(8.3-6.7)/8.3≈19%，与SURF相比缩短了(12.4-6.7)/12.4≈45%。尤其在此基础上，又运用动态连接缝隙调整算法，消除了重影，同时采用色调正常化算法，使拼接后的图像色调表现得更加自然，明显提高了图像拼接的质量。

[1] Fei Lei,Wenxue Wang.A Fast Method for Image Mosaic Based on SURF[C]//Proc.of the 9th Conference on Industrial Electronics and Applications.IEEE Press,2014:79-82.

[2] Ying Zhang,Lei Yang,Zhujun Wang.Research on Video Image Stitching Technology Based on SURF[C]//Proc. of 2012 Fifth International Symposium on Computational Intelligence and Design.IEEE Press,2012:335-338.

[3] David G Lowe.Object Recognition from Local Scale-Invariant Features[C]//Proc. of the International Conference on Computer Vision.IEEE Press,1999-9.

[4] Herbert Bay,Andreas Ess,Tinne Tuytelaars,et al.Speeded-Up Robust Features (SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-389.

[5] Dianyuan Han.A Standing Tree Image Mosaic Algorithm Based on SIFT[C]//Proc. of 2012 International Conference on Computer Science and Electronics Engineering.IEEE Press,2012:353-356.

[6] Dianyuan Han.A Method to Standing Tree Image Mosaic Based on SURF in Pocket PC[C]//Proc. of 2012 International Conference on Computer Science and Electronics Engineering.IEEE Press,2012:330-333.

[7] Rosten E,Drummond T.Machine Learning for High Speed Corner Detection[C]//Proc. of the 9th European Conference on Computer Vision.IEEE Press,2006:430-443.

[8] Rosten E,Porter R,Drummond T.Faster and Better:A Machine Learning Approach to Corner Detection[J].IEEE Trans. on Pattern Analysis and Machine Intelligence,2010,32(1):105-119.

[9] Rublee E,Rabaud V,Konolige K,et al.ORB:An Efficient Alternative to SIFT or SURF[C]//Proc. of International Conference on Computer Vision.IEEE Press,2011:2564-2571.

[10] Calonder M,Lepetit V,Strecha C,et al.Brief:Binary Robust Independent Elementary Features[C]//Proc. of European Conference on Computer Vision.IEEE Press,2010.

[11] Tian Fang,Shi Ping.Image Mosaic Using ORB Descriptor and Improved Blending Algorithm[C]//Proc.of the 7th International Congress on Image and Signal Processing.IEEE Press,2014:693-698.

[12] Takayuki Nakamura,Yuuichi Tashita.Congruence Transformation Invariant Feature Descriptor for Robust 2D Scan Matching[C]//Proc of International Conference on Systems,Man,and Cybernetics.IEEE Press,2013:1648-1653.

[13] 汤伯超.基于SIFT算法的图像特征描述方法研究[D].广州:广东工业大学,2012.

[14] 刘畅,金立左,费树岷,等.固定多摄像头的视频拼接技术[J].数据采集与处理,2014,29(1):126-133.

[15] 任结,周余,余耀,等.基于ORB自然特征的AR实时系统实现[J].计算机应用研究,2012,29(9):3594-3596.

[16] 时磊,谢晓芳,乔勇军,等.基于SURF算法的人脸跟踪技术研究[J].计算机仿真,2010,27(12):227-231.

[17] 刘永,王贵锦,姚安邦,等.基于自适应帧采样的视频拼接[J]清华大学学报:自然科学版,2010,50(1):108-112.

[18] 刘明杰,任帅,金城.基于自适应投影矩阵的实时视频拼接算法[J].计算机应用与软件,2012,29(5):81-85.

[19] 苗立刚.视频监控中的图像拼接与合成算法研究[J].仪器仪表学报,2009,30(4):858-861.

[20] 张春雨,王文,邱亚特,等.视频拼接中最优自适应单应性矩阵求解算法[J].吉林大学学报:工学版,20013,43(4):1116-1120.

[21] 吴健,兰时勇,黄飞虎.一种多路快速视频拼接系统设计与实现[J].计算机工程,2014,40(2):208-211.

[22] 赵斌,陈辉,董颖.一种基于压缩域的视频拼接方法[J].计算机应用,2007,27(11):2781-2785.

VIDEO STITCHING ALGORITHM BASED ON IMPROVED CONGRUENCE TRANSFORMATION INVARIANT FEATURE

Yang Yingjie1Yang Fan1Zeng Qingxi2

1(CollgeofInformationEngineering,NortheastDianliUniversity,Jilin132012,Jilin,China)2(DepartmentofVehicleEngineering,NanjingUniversityofAeronauticsandAstronautics,Nanjing210096,Jiangsu,China)

Smooth transition of video stitching is a nodus in image processing, in order to better solve this problem, the paper puts forward a video stitching algorithm which is based on CIF(Congruence transformation Invariant Feature) improved by Sobel operator. In the stage of image registration, we collected the key frames in video sequence, and extracted the features by using improved CIF algorithm firstly and matched them with key frames. Then, based on RANSAC algorithm we estimated and optimised the matrix of space transformation. In the stage of image blending, we used the dynamic adjusting algorithm of connect seam and colour tone normalisation algorithm to work collaboratively so as to eliminate the ghosting problem and colour differences in overlapped area between two parts of the image. Experiments showed that the proposed algorithm can achieve real-time video stitching, and can also resolve the smooth transition of video stitching.

Video stitching Congruence transformation invariant feature Sobel operator Feature points pair Dynamic adjusting algorithm of connect seam Image tone normalisation algorithm

2014-12-28。中央高校基本科研业务费专项(NS20130 16)；南京航空航天大学研究生创新基地(实验室)开放基金项目(kfjj201464)。杨英杰，副教授，主研领域：计算机技术应用。杨帆，硕士生。曾庆喜，讲师。

TP391.4

A

10.3969/j.issn.1000-386x.2016.04.046