张 燕，赵新灿，谭同德

（郑州大学 信息工程学院，河南 郑州450001）

0 引 言

由于单个摄像机表达的场景区域信息有限，而高清摄像机因价格昂贵又得不到普及，使得视频流拼接具有重要的实用价值。视频流拼接就是利用视频流拼接技术将几段有公共视野的视频流拼接为一整段视野范围更广的全景视频流。视频流拼接因其观赏直观性已经应用于视频点播、视频会议和三维视频等多个领域［1］。当前已出现多种视频流拼接方法，David Lowe于1999年提出并于2004年进行更深入发展和完善的局部特征描述子SIFT因其对平移、旋转、光照、尺度等具有较好的鲁棒性而得到广泛应用［2］，该算法能实现较好的拼接效果，缺点是算法复杂、计算量庞大，计算的复杂度过高就难以满足实时性需求，从而限制了其广泛应用。

近几年来，处理器领域最重要的变化之一就是图形处理器GPU的运算性能的倍速增长，其浮点运算能力已经大大超越了通用处理器。使用GPU对传统的通用计算和图像处理算法进行并行加速成为近年来两个新的热点研究领域。基于GPU的视频流拼接算法将视频流拼接的关键技术 （图像特征提取与特征匹配）在GPU上进行加速，大大提高了算法的执行速度，满足了系统实时性的要求。本文还通过实验对传统的基于CPU实现的视频流拼接算法和基于GPU实现的视频流拼接算法［3］进行了分析和对比。

1 基于GPU的视频流拼接总体设计

视频流的拼接总体上分为视频采集、帧图像提取、帧图像拼接3个过程，其中帧图像拼接又分为帧图像特征提取和特征匹配两个子过程。帧图像拼接是影响视频流拼接实时性的关键步骤，而帧图像特征提取和特征匹配又是影响帧图像拼接速度的关键步骤，所以在GPU上实现视频流拼接算法，需将算法的不同计算步骤映射到不同的片段程序上，对于每一步计算，适当的片段程序会与片段处理器绑定，然后调用相应的渲染操作达到加速的目的。然而全部算法在GPU上执行并不能达到最好的效率，因为CPU与GPU的结构不同，CPU的设计是使更多的晶体管用于数据缓存和流控制，所以CPU擅长的像操作系统、系统软件和通用应用程序这类拥有复杂调度指令、分支、循环、逻辑判断及执行的程序任务；而GPU大量的晶体管用于数据处理，所以GPU擅长处理图形类矩阵运算或是非图形类的高度并行数值计算。集成CPU和GPU的体系结构不仅使它们可以继续在各自擅长的领域发挥作用和减小在传输带宽上的花销，还可以使运行任务之间的分割、调配以及硬件资源的利用更加合理。例如让CPU更多的资源用于缓存或控制，GPU更多的资源则用于处理通用计算。经分析，基于GPU实现视频流拼接总体设计图如图1所示。

图1 基于GPU的视频流拼接总体设计

2 视频采集与帧图像提取

视频采集是视频流拼接的第一步，也是非常重要的一步，是利用DV （digital video camera，数码录像机）采集几段具有公共视野的视频流。具体采集过程如下［4］：将DV固定在操作台上，调整位置及方向使它们有部分公共视野，然后匀速推动操作台，这样就可以采集到具有相邻场景的视频流 （图2为采集两段视频流）。

图2 两段视频流采集

采集到视频后，我们通过程序实现帧图像的提取［4］，即每隔一段时间或每隔几帧提取一帧作为关键帧，这样就可以得到一系列的帧图像序列。

3 基于GPU的SIFT特征提取

GPU在处理算法密集、计算高度并行、控制简单和算法分多个阶段等这类需要时性能远超过CPU，所以为了在GPU上加速SIFT算法执行，需根据GPU的特点优化修改标准的David Lowe的SIFT算法的各个步骤使其顺利进入GPU的图形管道，进而充分发挥GPU的并行处理能力［5］。因此，研究的重点是如何重新构造SIFT算法的各个阶段使其适应GPU的纹理格式。基于GPU的SIFT算法将算法中的多个步骤用GPU并行来计算，算法流程图如图3所示。

图3 基于GPU的SIFT特征提取

3.1 纹理存储设计和尺度空间生成

RGBA纹理格式是GPU的物理存储结构，它包含R、G、B、A这4个颜色通道分量 （如图4所示），其中每个通道占一个数据存储空间。在使用RGBA纹理存储时，每个纹理可以保存4个数值，这样GPU既可以通过GPU上片段处理器的数量实现纹理间并行处理，还可以将纹理中的4个颜色通道分量作为一个向量进行并行处理。在基于GPU的SIFT特征提取中，我们将特征提取模块的数据存储设计为RGBA纹理格式，即将帧图像的灰度值、DOG值、梯度幅值和方向依次存入R通道、G通道、B通道和A通道中。

图4 RGBA纹理格式

构建尺度空间分两个阶段：

第一阶段：构建高斯尺度空间

（1）高斯滤波：同组中每一层图像是下一层图像的模糊结果。

（2）图像亚采样：将上一组中某一层的图像进行亚采样作为下一组图像的第一层。

其中高斯滤波是高斯尺度空间构建中最耗时的运算步骤，根据高斯卷积的可分离性，我们将高斯滤波也分为两个阶段，用水平方向和垂直方向的一维滤波来代替二维的高斯滤波。

对于图像I（x，y）与gx，y（t）进行卷积操作，得到下一层图像L （x，y），其中gx，y（t）代表先进行水平方向滤波，后进行垂直方向的滤波。

经过两次滤波处理后，得到下一层的高斯灰度图，将灰度值存入纹理单元R通道，采用这种方式，节省了大量的纹理存取时间。

第二阶段：构建DOG尺度空间

将高斯尺度空间中相邻尺度的高斯灰度图相减即可得到DOG尺度空间，将得到的DOG值放入纹理单元的G通道。

3.2 局部极值点检测和梯度计算

GPU的动态分支用于极值点检测的全过程，判断一个像素在DOG尺度空间是否是极值点分四步实现：

（1）根据像素点的亮度差阈值排除约50%的非极值点。

（2）将剩余的可能极值点与同尺度的8个相邻像素进行比较。

（3）将剩余的约0.6%可能极值点与相邻尺度的18个邻近像素进行比较。

（4）去除边缘和噪声影响。

利用动态分支节省了不必要的计算，提高了GPU的效能。另外将图像灰度、梯度和DOG值保存在RGBA纹理中，极值点检测就是在向量内部进行比较计算，而向量内部运算是相对省时的。获取的稳定的特征点如图5所示，红点代表特征点。检测特征点的同时还可以进行梯度幅值和方向计算，首先取出纹理R通道中存放的图像灰度值，然后计算梯度，最后将计算得到的梯度幅值与方向分别存入纹理单元B通道和A通道。

图5 稳定的特征点

由于CPU与GPU之间进行数据通信开销很大，因此，特征点列表的生成也同样在GPU上进行，生成的特征点列表存储在纹理中。在这里我们利用GPU的数据流缩减方法生成特征点列表。

3.3 特征点方向及特征向量

得到特征点以后，我们要为每个特征点指定一个主方向，使其具备旋转不变性。基于GPU的特征点方向计算与传统的SIFT算法类似，仍然采用梯度方向直方图统计法来确定特征点的方向，即统计以特征点为原点一定区域内的邻域图像像素的梯度方向分布特征，并用方向直方图表示，检测方向直方图的最高峰值点作为该特征点的主方向。在这里我们在GPU端生成方向直方图来统计特征点邻域像素的梯度方向，然后将方向直方图回读到CPU端，在CPU端检测方向直方图的最高峰值来确定特征点的方向 （如图6所示）。每个特征点将得到一个或一个以上的方向，从而得到带有特征点坐标和方向的特征点列表。

图6 特征点方向

特征点计算完成后，我们需要一组具有独特性、唯一性的向量来描述这个特征点，该向量将作为目标匹配的依据。特征向量的计算与计算特征点方向相似，都是统计特征点一定区域内对其有贡献的像素点，只不过这些像素点指定的方向是一致的。通过对特征点一定领域区域进行分块，如图7所示，邻域区域被均匀的分成了16块，每块大小为4像素×4像素，然后计算每个块的方向直方图，，每个块与8个方向相关联，加起来是一个128维的输出向量，如图7所示。

图7 SIFT特征向量生成

基于GPU的SIFT特征向量生成，这个操作不同于前面进行的操作，因为输入一个元素 （特征点）却输出128个元素。即使使用多目标渲染，这个操作也不能一起执行，因为不可能将一个直方图分开计算。特征向量的生成全部在GPU上进行计算不能够达到最好的效率，因此我们将特征向量的生成分割在GPU与CPU之间，重采样特征点的梯度向量块，在GPU端对其高斯加权，然后将加权后的梯度向量块回读到CPU端，在CPU端计算特征向量。

4 基于GPU的SIFT特征匹配

特征匹配是利用相关函数 （一般是各种距离函数）来评价两幅图像特征点邻域的相似性以确定对应点，而特征向量表示的就是特征点的邻域信息，所以比较特征向量的相似性即可得到潜在的匹配点。在实际应用中，我们用欧式距离作为特征向量的相似性度量，对于两幅帧图像，分别计算特征点及特征向量，利用K－D树进行优先搜索，找到每个特征点的两个最邻近特征点，计算该特征点到两个邻近特征点的欧式距离，如果最近的距离与次近的距离的比值小于我们设定的比例阈值，则接受这对匹配的特征点，其中D为长度为N的特征向量V1与V2的欧式距离。

基于GPU的SIFT特征匹配中，K－D树搜索和相应的特征向量相减都可以在GPU上并行执行。这样可以大大提高计算速度。最后用经典的去外点算法随机抽样算法去除错误匹配，得到稳定的正确的特征点匹配对 （如图8所示）。

图8 SIFT特征向量的匹配

5 基于GPU的视频流拼接

5.1 全景图拼接的实现

图像拼接是将一组重叠图像进行拼接构建一幅无缝的、高清晰的、视野开阔的全景图。图像配准是图像拼接中的关键技术，视频流的拼接效果也取决于每帧帧图像的快速配准，而图像配准的关键和核心又是帧图像的快速特征提取和匹配。传统基于CPU的视频流拼接过程中帧图像配准阶段花费的时间较长，显然不能达到实时稳定拼接的效果，而基于GPU的视频流拼接则很好的解决了这个问题，实现了视频流的快速稳定拼接。拼接效果如下：图9为4幅原始帧图像，图10为图像拼接的全景图。

5.2 算法性能及其分析

本文的实验平台为64位Windows XP操作系统，NVIDIA GeForce 6600GT着色器，编译器平台为Microsoft VS2005。实验中将视频流拼接算法中的图像配准SIFT算法的参数设置为：第一组图像大小均为512＊384，组数为6，每组层数为3；第二组中图像大小均为1024＊972，组数为6，每组层数为3。标准的视频流拼接算法与基于GPU的视频流拼接算法的运算时间及性能分析，对比数据如表1所示。

表1 两种方法数据对比

由表1数据可知，对同一幅图像，GPU实现在特征提取和特征匹配两个阶段的处理速度上得到大幅度提升，当图像越大越复杂时获得的这种加速比就越大，这使得视频流拼接过程中帧图像的处理速度得到加速，每秒处理的帧图像数大幅增加，从而使得视频流拼接的实时性得以提升。

6 结束语

本文利用图形处理器GPU实现了标准的视频流拼接算法，提高了系统的实时性并拓宽了算法的应用范围。算法利用CPU和GPU混合模式共同实现，怎样达到一种最优的计算分配方式是下一步研究方向。下一步主要尝试利用NVIDIA的统一设备架构 （compute unified device architecture，CUDA）来快速实现视频流拼接算法，因为CUDA提供了更直观的编程模型和优化原则，基于CUDA的算法实现充分运用了GPU的并行计算能力，可以使视频流拼接算法在实时性方面有更大的提升。

［1］WANG Xiaoqiang，CHEN Linqiang，LIANG Xu.Method of real time automatic video stitching［J］.Computer Engineering，2011，37 （5）：291－292 （in Chinese）. ［王小强，陈临强，梁旭.实时全自动视频拼接方法 ［J］.计算机工程，2011，37（5）：291－292.］

［2］ZHANG Chaowei，ZHOU Yan，WANG Yaokang，et al.Method of videos stitch with SIFT feature tracking and matching based ［J］.Computer Engineering and Applications，2008，44（10）：169－172 （in Chinese）.［张朝伟，周焰，王耀康，等.基于SIFT特征跟踪匹配的视频拼接方法 ［J］.计算机工程与应用，2008，44 （10）：169－172.］

［3］WANG Rui，LIANG Hua，CAI Xuanping.Study of SIFT feature extraction algorithm based on GPU ［J］. Modern Electronic Technology，2010，33 （15）：41－43 （in Chinese）. ［王瑞，梁华，蔡宣平.基于GPU的SIFT特征提取算法研究 ［J］.现代电子技术，2010，33 （15）：41－43.］

［4］WANG Tiejian，ZHAO Hongling，WANG Zongmin.Optimized frame selection algorithm for video stitching based on feature points ［J］.Computer Applications，2009，29 （3）：2112－2115（in Chinese）.［王铁建，赵红领，王宗敏.基于特征点的视频流拼接帧选择优化算法 ［J］.计算机应用，2009，29 （3）：2112－2115.］

［5］WU Changchang. SIFTGPU ［CP／OL］. ［2007－02－11］.http：／／www.cs.unc.edu／～ccwu／siftgpu／.

［6］Sinha S，Frahm J.GPU－based video feature tracking and matching ［C］.Workshop on EDGE，2006.

［7］Heymann S.SIFT implementation and optimization for generalpurpose GPU ［C］.Proceedings of the 15th WSCG，2007.

［8］Cornelis N，Van Gool L.Fast scale invariant feature detection and matching on programmable graphics hardware ［C］.Workshop on CVPR，2008.

［9］Bay H，Tuytelaars T，Van Gool L.SURF：Speeded up robust features ［C］.European Conference on Computer Vision pages，2006：404－417.

［10］Sinha S，Frahm J.Feature tracking and matching in video using programmable graphics hardware［J］.Machine Vision and Applications，2011，22（1）：207－217.

［11］ZHENG Mai，GUO Li.Research of multi－view panoramic video technology based on webcams［D］.Anhui：University of Science and Technology of China，2009：54－65 （in Chinese）.［郑迈，郭立.基于网络摄像头的多视全景视频技术研究 ［D］.合肥：中国科学技术大学，2009：54－65.］

［12］CHEN Jing，WANG Yongtian，LIU Yue，et al.System initialization algorithm based on SIFT key points for markerless augmented reality applications ［J］.Infrared and Laser Engineering，2007，36 （6）：949－953 （in Chinese）. ［陈靖，王涌天，刘越，等.基于SIFT关键点的增强现实初始化算法［J］.红外与激光工程，2007，36 （6）：949－953.］

［13］YUAN Xiuguo，PENG Guohua，WANG Lin.GPU－based real time image registration with variant SIFT ［J］.Computer Science，2011，38 （3）：300－303 （in Chinese）. ［袁修国，彭国华，王琳.基于GPU的变型SIFT算子实时图像配准［J］.计算机科学，2011，38 （3）：300－303.］

［14］HE Yang，WANG Xiaoe.An improved SIFT feature matching algorithm and its realization ［J］.Silicon Valley，2011，10 （6）：92－93（in Chinese）.［何扬，汪晓娥.一种改进的SIFT特征匹配算法及其实现 ［J］.硅谷，2011，10 （6）：92－93.］

［15］ZHAO Chunjiang.Typical examples of digital image processing algorithms with C＃ ［M］.Beijing：Posts ＆ Telecom Press，2009：21－248 （in Chinese）.［赵春江.C＃数字图像处理算法典型实例 ［M］.北京：人民邮电出版社，2009：21－248.］

［16］WANG Daoyin，HU Fangyu，Video sequence image registration based on improved scale－invariant feature transform algorithm［J］.Radio Engineering of China，2011，41 （2）：16－18（in Chinese）.［汪道寅，胡访宇.基于改进SIFT算法的视频序列图像配准 ［J］.无线电工程，2011，41 （2）：16－18.］

［17］QIAN Yue.Compute unified device architecture on graphics processors［J］.Computer ＆ Digital Engineering，2008，36（12）：177－180 （in Chinese）.［钱悦.图形处理器 CUDA 编程模型的应用研究 ［J］.计算机与数字工程，2008，36（12）：177－180.］

［18］TIAN Wen，XU Fan，WANG Hongyuan，et al.Fast scale invariant feature transform algorithm based on CUDA.Computer Engineering，2010，36 （8）：219－221 （in Chinese）.［田文，徐帆，王宏远，等.基于CUDA的尺度不变特征变换快速算法 ［J］.计算机工程，2010，36 （8）：219－221.］