论文部分内容阅读
摘 要：文章主要在限定的特征点提取区域，用改进的SIFT特征匹配算法进行帧图像的并行双向搜索匹配，缩短视频帧图像的匹配时间达到视频拼接的目的。
关键词：SIFT；帧图像匹配；视频拼接
中图分类号：TP391.41 文献标识码：A 文章编号：1006-8937（2011）22-0070-02
1 视频帧图像拼接
1.1 SIFT算法
SIFT算法由D.G.Lowe 1999年提出，后来Y.Ke进行完善。主要有四个步骤：第一，建立尺度空间。尺度空间理论的主要思想是利用高斯对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列。为了得到在不同尺度空间下的稳定特征点，主要是构建高斯金字塔和DOG金字塔，然后在DOG金字塔里面进行极值检测。第二，精确定位极值点。由于DOG值对噪声和边缘较敏感，通过上面的方法所检测到的局部极值点还要经过进一步的检验才能精确定位为特征点。通过三维二次函数拟合来精确确定极值点的位置和尺度。第三，特征点指定方向参数。用直方图统计邻域像素的梯度方向，梯度直方图的范围是0～360°，其中每10°一个柱，总共36个柱。直方图的峰值则代表了该特征点处邻域梯度的主方向，作为该特征点的方向。第四，特征向量的生成。在窗口中用箭头方向来代表该像素的梯度方向，箭头长度来代表梯度模值，在窗口上用一个圆圈代表高斯加权的范围。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。
1.2 SIFT特征向量的匹配
本文采用欧氏距离作为两幅图像间的相似性度量。获取SIFT特征向量后，采用K-D树进行优先搜索来查找每个特征点的2近似最近邻特征点。在这两个特征点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。
1.3 图像的配准与融合
在上述的SIFT算法过程中获得的特征点和有效匹配对的基础上，进行图像间变换参数估计。以视频图像V1为参照系，将视频图像V2变换到V1所在的坐标系，记变换后的图像为V2'，其对应关系如公式（1）所示：
x2'y2'1=t11 t12 t13t21 t22 t23t31 t32 1x2y21=Tx2y21 （1）
式（1）中有8个参数，仅需要四对匹配点即可计算变换图像V2'，即V2'=TV2
图像配准后，图像间的变换关系就得到了唯一确定。本文采用加权平均的融合方法进行图像平滑过渡，从而达到图像的无缝拼接。
2 实际问题框架
本文主要工作是将倒车时所拍摄的实时视频进行拼接，具体步骤如下：
①获取两组视频同一时刻的帧图像。在汽车尾部对称的两侧安装视角范围大小为60°的摄像头，并在同一时刻分别抓取视频帧图像。
②对同一时刻的帧图像进行拼接。摄像头的位置和角度固定以后，抓取图片的相对位置也就固定，重叠区域也相对固定了，如图 1所示。其中l是车身后面两摄像头之间的距离，L是摄像头与车身后面场景的距离，O点是摄像头视线交叉点，OO1是O点到摄像头的距离，OO3是O点到驾驶员视线范围的距离。重叠区域即A与B之间的部分，其宽度为H，通过公式（2）得到。
（3）
③对拼接好的帧图像按时序进行视频格式的播放。把同一时刻的两张帧图像拼接成的一幅图像，进行校正后按照时序用视频格式输出。此时驾驶员根据视频所反映的车身后面的场景来进行倒车。
3 算法优化
3.1 特征点提取区域的限定
本文中视频帧图像的拼接是基于特征点的拼接，提取特征点是拼接的关键，为了达到视频拼接的实时要求本文提出选取特征点时只在限定的区域进行，如图2所示。即右边摄像头所获取的视频帧图像其特征点提取区域即为图1中CO2之间的部分，它们之间的距离为l/2，左边摄像头所获取的视频帧图像其特征点提取区域即为图1中O2C'之间的部分，它们之间的距离为l/2。
3.2 K-D树优先搜素算法
在SIFT算法中，特征向量的匹配先采用欧氏距离进行了相似性度量，再采用K-D树进行优先搜索来查找每个特征点的2近似最近邻特征点。树的顶层结点按一维进行划分，下一层结点按另一维进行划分，以此类推，各个维循环往复。划分要使得存储在子树中大约一半的结点落入一侧，而另一半落入另一侧。当一个结点中的点数少于给定的最大点数时，划分结束。在SIFT算法中实际运用中是采用的一种K-D树搜索算法基础上改进的搜索算法，即BBF（best-bin-first）算法来搜索样本特征点的最近邻和次近邻特征点，其中BBF搜索算法是在四维空间，即k=4的K-D树基础上用一个优先级队列实现以结点和被查询结点距离递增的顺序来搜索结点，结点和被查询结点的距离是指他们之间的最短距离。
3.3 改进的K-D树优先搜素算法
本文提出双向并行搜索的策略，即以特征集A中所有的特征点基准点在特征集B中采用K-D树进行优先搜索，找到与特征点最近邻和次近邻的两点bi1、bi2，如果bi1、bi2之间的距离比值小于某一个设定的比例阈值，则接受这一对匹配点；同时又以特征集B中的所有特征点为基准点在特征集A中采用K-D树进行优先搜索，找到与特征点最近邻和次近邻的两点aj1、aj2，如果aj1、aj2之间的距离比值小于某一个设定的比例阈值，则接受这一对匹配点。如图 3所示。
如果以A中的点ai为基准点搜索时，在B中找到了点bj与其匹配，并且在B中以bj点为基准点，在A中进行搜索时，恰好又与A中的点ai匹配的话，则从A中去除点ai，从B中去除点bj；
算法步骤如下：第一，同时输入特征点集A和B以及集合总数m和n，使i=0，j=0。第二，若i＜m或j＜n，或n＜0，则ai去B中找匹配点，bj去A中找匹配点。第三，若ai找到匹配点bp，bj找到匹配点aq则保存这样的匹配对。第四，从集合A和B中减去已经配对的点，然后进入步骤2。
通过本文改进算法的分析，对两个2×2的特征点矩阵进行匹配，如图 4所示。用改进的K-D搜索策略，A集合与B集合中的特征点是同时进行，即第一步，a1用4次找到b3匹配，同时b1用4次找到a4匹配；第二步，a2用4次找到b2匹配，同时b2用4次找到a2匹配，此时a2与b2双向都匹配上了，所以在A中去除a2，在B中去除b2；第三步，a3用3次没有找到匹配点，同时b3用3次找到a1匹配，此时a1与b3构成了双向匹配上了，所以同时去除a1，b3；第四步，a4用2次找到b1，同时b4用2次找到a3匹配。至此所有的点搜索完毕，K-D树搜索方法共用了16次，而改进的K-D树搜索方法共用了13次。
4 实验结果与分析
本实验采用两个设置相同焦距、色度等参数的摄像头，以某场景进行实验。根据上述的理论，通过VC++和Opencv编程实现视频拼接。
参考文献：
[1] 周颜军.数据结构[M].长春:吉林科学技术出版社,2003.
关键词：SIFT；帧图像匹配；视频拼接
中图分类号：TP391.41 文献标识码：A 文章编号：1006-8937（2011）22-0070-02
1 视频帧图像拼接
1.1 SIFT算法
SIFT算法由D.G.Lowe 1999年提出，后来Y.Ke进行完善。主要有四个步骤：第一，建立尺度空间。尺度空间理论的主要思想是利用高斯对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列。为了得到在不同尺度空间下的稳定特征点，主要是构建高斯金字塔和DOG金字塔，然后在DOG金字塔里面进行极值检测。第二，精确定位极值点。由于DOG值对噪声和边缘较敏感，通过上面的方法所检测到的局部极值点还要经过进一步的检验才能精确定位为特征点。通过三维二次函数拟合来精确确定极值点的位置和尺度。第三，特征点指定方向参数。用直方图统计邻域像素的梯度方向，梯度直方图的范围是0～360°，其中每10°一个柱，总共36个柱。直方图的峰值则代表了该特征点处邻域梯度的主方向，作为该特征点的方向。第四，特征向量的生成。在窗口中用箭头方向来代表该像素的梯度方向，箭头长度来代表梯度模值，在窗口上用一个圆圈代表高斯加权的范围。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。
1.2 SIFT特征向量的匹配
本文采用欧氏距离作为两幅图像间的相似性度量。获取SIFT特征向量后，采用K-D树进行优先搜索来查找每个特征点的2近似最近邻特征点。在这两个特征点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。
1.3 图像的配准与融合
在上述的SIFT算法过程中获得的特征点和有效匹配对的基础上，进行图像间变换参数估计。以视频图像V1为参照系，将视频图像V2变换到V1所在的坐标系，记变换后的图像为V2'，其对应关系如公式（1）所示：
x2'y2'1=t11 t12 t13t21 t22 t23t31 t32 1x2y21=Tx2y21 （1）
式（1）中有8个参数，仅需要四对匹配点即可计算变换图像V2'，即V2'=TV2
图像配准后，图像间的变换关系就得到了唯一确定。本文采用加权平均的融合方法进行图像平滑过渡，从而达到图像的无缝拼接。
2 实际问题框架
本文主要工作是将倒车时所拍摄的实时视频进行拼接，具体步骤如下：
①获取两组视频同一时刻的帧图像。在汽车尾部对称的两侧安装视角范围大小为60°的摄像头，并在同一时刻分别抓取视频帧图像。
②对同一时刻的帧图像进行拼接。摄像头的位置和角度固定以后，抓取图片的相对位置也就固定，重叠区域也相对固定了，如图 1所示。其中l是车身后面两摄像头之间的距离，L是摄像头与车身后面场景的距离，O点是摄像头视线交叉点，OO1是O点到摄像头的距离，OO3是O点到驾驶员视线范围的距离。重叠区域即A与B之间的部分，其宽度为H，通过公式（2）得到。
（3）
③对拼接好的帧图像按时序进行视频格式的播放。把同一时刻的两张帧图像拼接成的一幅图像，进行校正后按照时序用视频格式输出。此时驾驶员根据视频所反映的车身后面的场景来进行倒车。
3 算法优化
3.1 特征点提取区域的限定
本文中视频帧图像的拼接是基于特征点的拼接，提取特征点是拼接的关键，为了达到视频拼接的实时要求本文提出选取特征点时只在限定的区域进行，如图2所示。即右边摄像头所获取的视频帧图像其特征点提取区域即为图1中CO2之间的部分，它们之间的距离为l/2，左边摄像头所获取的视频帧图像其特征点提取区域即为图1中O2C'之间的部分，它们之间的距离为l/2。
3.2 K-D树优先搜素算法
在SIFT算法中，特征向量的匹配先采用欧氏距离进行了相似性度量，再采用K-D树进行优先搜索来查找每个特征点的2近似最近邻特征点。树的顶层结点按一维进行划分，下一层结点按另一维进行划分，以此类推，各个维循环往复。划分要使得存储在子树中大约一半的结点落入一侧，而另一半落入另一侧。当一个结点中的点数少于给定的最大点数时，划分结束。在SIFT算法中实际运用中是采用的一种K-D树搜索算法基础上改进的搜索算法，即BBF（best-bin-first）算法来搜索样本特征点的最近邻和次近邻特征点，其中BBF搜索算法是在四维空间，即k=4的K-D树基础上用一个优先级队列实现以结点和被查询结点距离递增的顺序来搜索结点，结点和被查询结点的距离是指他们之间的最短距离。
3.3 改进的K-D树优先搜素算法
本文提出双向并行搜索的策略，即以特征集A中所有的特征点基准点在特征集B中采用K-D树进行优先搜索，找到与特征点最近邻和次近邻的两点bi1、bi2，如果bi1、bi2之间的距离比值小于某一个设定的比例阈值，则接受这一对匹配点；同时又以特征集B中的所有特征点为基准点在特征集A中采用K-D树进行优先搜索，找到与特征点最近邻和次近邻的两点aj1、aj2，如果aj1、aj2之间的距离比值小于某一个设定的比例阈值，则接受这一对匹配点。如图 3所示。
如果以A中的点ai为基准点搜索时，在B中找到了点bj与其匹配，并且在B中以bj点为基准点，在A中进行搜索时，恰好又与A中的点ai匹配的话，则从A中去除点ai，从B中去除点bj；
算法步骤如下：第一，同时输入特征点集A和B以及集合总数m和n，使i=0，j=0。第二，若i＜m或j＜n，或n＜0，则ai去B中找匹配点，bj去A中找匹配点。第三，若ai找到匹配点bp，bj找到匹配点aq则保存这样的匹配对。第四，从集合A和B中减去已经配对的点，然后进入步骤2。
通过本文改进算法的分析，对两个2×2的特征点矩阵进行匹配，如图 4所示。用改进的K-D搜索策略，A集合与B集合中的特征点是同时进行，即第一步，a1用4次找到b3匹配，同时b1用4次找到a4匹配；第二步，a2用4次找到b2匹配，同时b2用4次找到a2匹配，此时a2与b2双向都匹配上了，所以在A中去除a2，在B中去除b2；第三步，a3用3次没有找到匹配点，同时b3用3次找到a1匹配，此时a1与b3构成了双向匹配上了，所以同时去除a1，b3；第四步，a4用2次找到b1，同时b4用2次找到a3匹配。至此所有的点搜索完毕，K-D树搜索方法共用了16次，而改进的K-D树搜索方法共用了13次。
4 实验结果与分析
本实验采用两个设置相同焦距、色度等参数的摄像头，以某场景进行实验。根据上述的理论，通过VC++和Opencv编程实现视频拼接。
参考文献：
[1] 周颜军.数据结构[M].长春:吉林科学技术出版社,2003.