基于SURF和SIFT特征的视频镜头分割算法

张昊骕，朱晓龙，胡新洲，任洪娥,2*

(1. 东北林业大学 信息与计算机工程学院，黑龙江 哈尔滨 150040；2. 黑龙江省林业智能装备工程研究中心，黑龙江 哈尔滨 150040)

1 引 言

视频镜头分割是视频处理中的第一步，它的任务是准确找出镜头之间的边界，这对视频的后续处理如关键帧提取等起着至关重要的作用。视频镜头边界主要分为两种[1]，一种是切变镜头，指的是前一个镜头直接切入到下一个镜头，镜头之间变化明显，也比较容易检测。另一种是渐变镜头，指的是前一个镜头通过几帧甚至几十帧缓慢过度到下一个镜头，镜头之间变化缓慢，检测比较困难。近些年来，为了解决镜头边界检测的问题，很多种用于镜头边界检测的方法被提出，并取得了显著效果。Kikukawa等[2]提出了像素帧差法，它采用前后相邻两帧的对应像素的色度并比较其差值来查找镜头边界。Zhang等[3]提出了直方图帧差法，采用度量临近帧之间直方图的差异来查找镜头的边界。杨瑞琴等[4]提取Hu不变矩特征进行初检选出候选边界，然后利用三维颜色直方图进行复检。于俊清等[5]通过构造回放因子特征来改进情感激励模型从而实现了镜头边界检测。李小琛等[6]利用SIFT特征融合CSIFT颜色不变量特征进行镜头边界检测，有效地弥补了SIFT算法丢失色彩信息的缺陷。蔡轶珩等[7]提出一种融合了色彩特征和改进的SURF特征的镜头分割算法，通过减少匹配点数量，加快了算法运算速度，通过使用自适应阈值，以及融入颜色特征等方式，提高了算法准确率。除此之外，还有很多类似的方法。简而言之，这些方法从不同的角度实现了对镜头识别分割这一过程。然而，在上述算法中，有些算法仅仅利用了全局特征，虽然速度较快但是准确率较差。有些算法虽然融合了局部特征和全局特征，但是融合方式不紧密导致可能会出现漏检。

SIFT特征是一种经典的特征点提取描述算法。并且它已被大量应用于图像、视频分析等领域中，它具有对尺度变换、旋转变换、仿射变换、视角变换、噪声的不变性等诸多优点，然而由于其特征点提取过程比较复杂，导致效率低下，不适用于数据量大和具有实时性要求的场合，而且由于算法使用灰度图像进行特征点的检测，缺乏图像色彩信息，所以对于视频检测来说容易造成误检。

相比之下，SURF特征比SIFT特征的速度快很多，并且对亮度等变化不太敏感。所以，本文针对以上文献中存在的高效性与准确性不平衡的问题，从SIFT特征效率较低的特点入手，提出了基于SURF和SIFT特征的镜头分割技术。首先判断两帧的颜色特征距离，如果大于设定的自适应阈值，则加入候选帧，否则提取出SURF特征并与颜色特征进行特征融合，然后使用滑动窗口技术计算当前帧与后续帧的特征距离并使用阈值筛选出候选切变镜头和渐变镜头。最后采用SIFT特征用来进行复选，从而去掉误检镜头。

2 基于多特征融合的镜头分割算法

由于SIFT特征效率低下，显然不能直接使用SIFT进行镜头分割，所以在镜头边界帧初选阶段我们引入SURF特征来替代SIFT特征以实现高效分割。

2.1 SURF特征点提取

SURF特征即加速稳健特征，是一种局部特征点的提取和描述算法[8]，它基于SIFT特征并改良了其特征点提取和描述方式，所以SURF也具有SIFT特征的对尺度、旋转等不变性的特性，而且SURF由于采用了Harr小波特征和积分图像的方法，运行效率相较SIFT有了大幅度的提升。

SURF特征点的提取过程如下：

(1)假设图像用函数f(x,y)来表示。首先利用黑塞矩阵获取特征点，则图像中相应点的黑塞矩阵为：

(1)

从而有判别式：

(2)

经过高斯滤波的对应矩阵为：

(3)

在计算黑塞矩阵之前，应该使用二阶标准高斯函数进行滤波，这是因为它可以使求得的特征点具备尺度无关特性。用I(x,y)代替点(x,y)，L(x,t)为高斯函数G(t)在点(x,y)处卷积的结果：

L(x,t)=G(t)·I(x,y)，

(4)

其中，高斯核G(t)为：

(5)

为了加快计算速度，SURF算法改变了以往先进行高斯滤波，然后求二阶导数，进而求取黑塞矩阵的方式，转而采用了盒式滤波来近似高斯滤波。设在经过盒式滤波之后，用Pxx、Pyy、Pxy来代表Lxx、Lyy、Lxy，所以有判别式：

det(H)=PxxPyy-(0.9Pxy)2，

(6)

其中，0.9为经验值。根据判定结果的符号,若det(H)>0,则此点为极值点。

(2)生成尺度空间，如图1所示。

图1 尺度空间的建立Fig.1 Building of a scale space

在SURF特征中，图像尺度是不变的，通过对图像进行不同尺度的盒式滤波来生成尺度空间的每一层。

(3)利用非最大抑制来定位特征点，如图2所示。

图2 定位特征点Fig.2 Location feature points

经过黑塞矩阵处理过的每个特征点与相邻的26个点进行大小比较，如果最大或最小，则保留下来做备选点。然后，采用3维线性插值法进一步得到亚像素级的特征点，同时也去掉一些较弱或错误的特征点，通过控制极值大小来控制特征点数量，最终仅留下一些较强的特征点。

(4)为特征点选取主方向，如图3所示。

图3 选取特征点主方向Fig.3 Selection of the main direction of feature points

SURF特征统计了以特征点为中心，在固定半径大小的圆形区域内以一定间隔转动的扇形内全部点的Harr小波特征，并将取得最大值的扇形方向设定为主方向。这样，通过计算每一个特征点，得到每一个特征点的主方向。

(5)构成特征点的描述算子，如图4所示。在特征点邻域选取一个矩形框并将其分成4×4个子区域，然后统计每个区域中共25个像素的Haar小波特征来得到描述子。

图4 构成特征点描述子Fig.4 Constitution of the descriptor of feature points

2.2 改进的SURF特征匹配及特征融合算法

特征点匹配一般采用FLANN算法。FLANN算法基于KD树，可以根据数据集的分布特点，来推荐索引类型和检索参数[9]。该算法首先根据得到的特征点，计算图像中某一特征点x与另一图像中特征点y的欧式距离，接着采用欧式距离比值法进行匹配[10]，最后筛选经过配对的特征点，仅保留符合要求的点。

为了提升SURF特征的准确性，本文改进了特征点的匹配方式。传统的匹配方式通常为使用固定阈值或者设定阈值为最小匹配距离Dmin的N倍来进行匹配，但是，如果使用固定阈值将可能无法满足不同类型视频匹配的要求，如果设定阈值为最小匹配距离的N倍，在某些情况下，最小匹配距离可能为0，而其他匹配点的匹配距离可能并不为0，从而导致误检。为解决这个问题，使用最大匹配距离Dmax和颜色特征距离Dc并采用线性结合权重的自适应阈值的方法，如式7所示。

Dt=ρ·D+(1-ρ)·Dc，

(7)

其中：Dc为颜色特征距离，D为特征点距离，Dt为融合后的距离。

对于两幅图像而言，式(7)中融合了相同的颜色特征信息，只有D是可变的，因此经过融合后的最大距离Dtmax与最小距离Dtmin的比值应该与Dmax和Dmin的比值相等。设Dtmin=ρ·Dmin+(1-ρ)·Dc，所以有式(8):

(8)

令Dmax/Dmin=M，设优秀匹配点阈值Dm为融合后最大距离Dtmax的K倍(K∈(0,1))，如式(9)所示。

Dm=K·(ρ·Dmax+(1-ρ)·M·Dc).

(9)

经过大量实验证明，在SURF检测器阈值为3 000，K值为0.4时，这种方法尤其对切变镜头有较高的匹配率。在本文中的SIFT特征匹配方式也是按照相似的方式进行的。

对于特征融合算法，传统的特征融合方式包括串行融合和并行融合两种[11]。串行融合是指新的特征向量是由两组特征向量通过串行连接成的。其优点是构造方法简单，几乎不需要进行运算，缺点是特征向量γ的维数可能急剧增加。并行融合是利用复向量，将特征向量在复向量空间进行融合。如果两个向量维数不同，则通过补0来对齐。其优点是对比串行融合方式，有效地降低了特征向量的维数，缺点是计算量可能较大。

为了尽可能减小计算量，避免维度剧烈增加，本文采用式7的方式通过赋予每种特征的特征向量之间的距离以相应的权重，再求其和进而表示特征融合后两图之间的距离。通过此公式融入FLANN匹配算法来获得优秀的匹配点，实验证明，权重ρ在取值为0.6时准确率最高。

2.3 改进的颜色特征的检测算法

SURF特征是一种局部特征，它反映了图像的部份像素间的关系，然而仅仅使用局部特征还不能对图像精确地描述。全局特征可以表达出整张图像的信息，而且它的速度比局部特征要快，所以为了增加速度和准确性，本文使用了全局特征及全局特征融合局部特征的方式进行镜头检测。

颜色直方图是一种常用的全局特征，主要因为其算法简单，对匹配图像的旋转、变形、模糊变换具有不变性的优势，并且对噪声、镜头位置、分辨率等也并不敏感，所以在图像、视频处理系统中被广泛应用。而在这其中HSV空间是直方图最常用的颜色空间，它包含色相H、饱和度S和亮度V3个分量，同时，它也是最适合人类的视觉系统。

计算颜色直方图首先需要量化颜色。颜色量化即是将颜色空间分为若干区间(bin)，然后计算处于每个区间的像素个数即可得到颜色直方图。

为了减少计算复杂度，首先将直方图分为64个bin，H范围为(0,44),(45,89),(90,134),(135,179),S范围为(0,63),(64,127),(128,191),(191,255),V范围为(0,63),(64,127),(128,191),(191,255)，并将其归一化，即将每个bin值除以图像像素数量。最后得到颜色特征向量：

(10)

其中:S为图像像素数量，Mn代表bin元素数量。

为了后续的特征融合阶段，本文中使用欧式距离作为HSV直方图的距离对比方式：

(11)

这里M,N是两帧图像的HSV颜色直方图Mi、Ni是颜色直方图第i个bin的元素个数。

算法主要是通过比较前后两帧颜色直方图距离与某一阈值的大小来寻找镜头边界。传统的判别方法使用固定阈值，然而固定阈值对于不同类型的视频来说阈值设定不尽相同，且需要大量的实验来确定，很容易发生漏检、误检现象，所以本文通过使用自适应阈值来判断切变镜头。对于渐变镜头，其变化过程多样，单一颜色特征检测渐变镜头较难判定，容易造成误检。所以并未采用单一颜色特征来判定渐变镜头。本节算法过程为：

首先提取视频的相邻两帧图像，然后分别把这两帧图像从RGB空间转换成HSV空间并将进行颜色量化，接着分别计算这两帧图像的HSV直方图，最后计算它们的颜色特征距离，如果颜色距离大于自适应阈值T，则判定切变镜头。根据实验得到的经验，对于一般情形，前后两帧的信息具有一定连续性，颜色变化程度较小，所以相应颜色特征距离不会超过其与零向量的欧式距离。所以，将自适应阈值选择为两帧中第一帧的颜色特征向量与零向量欧氏距离的0.8倍(式(12))。经过实验检验，本节算法对检测切变镜头有较高的准确性。

(12)

2.4 基于颜色和SURF特征的镜头分割算法

本节算法过程为：首先提取颜色特征，使用上述基于颜色特征的检测算法判断当前帧是否为切变镜头，如果是则进入下一帧，否则提取SURF特征，然后将改进的融合模式用于特征融合，并筛选优秀的匹配点，接着计算相邻两帧之间的匹配度，如果帧间匹配度小于阈值T1，则将其判定为切变镜头。如果匹配度大于阈值T2，则判定为无变化。如果匹配度处于T1与T2之间，则有可能存在渐变镜头。针对切变和渐变两种镜头边界的差别，我们使用了滑动窗口的检测手段。维持一个窗口，设定它的最初大小w为0，它的起始位置为当前帧c，并不断向右侧拓展，并不断比较帧Fc和Fc-w的匹配度，如果两帧匹配度小于阈值T1，那么将其认定为渐变镜头，并加入候选帧，然后恢复最初设定。若在此窗口扩展中检测到相邻两帧存在切变镜头或无变化，则直接初始化设定。重复如此过程，直到检测完所有帧。经过大量实验，确定阈值T1=0.3，T2=0.8时准确率最高。算法流程如图5所示。

通过应用信息化科学技术可以实现土木工程设计和管理的优化，充分将建筑美学表达出来，实现土木管理的精细化。随着各项新的技术、设备逐渐研发，新的管理模式以及应用平台的更新，土木工程建设如果不能做到与时俱进势必会被社会淘汰，只有不断将适应现代化社会发展的需求，逐步提升管理水平，才能促进土木工程施工建设可持续发展。

图5 基于颜色特征和SURF特征的镜头分割算法流程图Fig.5 Flowchart of shot segmentation algorithm based on color feature and SURF feature

2.5 SIFT特征匹配

虽然颜色特征结合SURF特征可以满足要求，但是根据Juan等人对SURF和SIFT等特征的实验比较来看，SIFT特征可以获得数量更多的特征点，而且SURF特征对于尺度和旋转变换等方面相比检测效果略差[12]，综合来看SIFT特征的检测效果要强于SURF特征，此外，在渐变镜头检测中由于滑动窗口未限定尺寸，有可能产生误检，为了提高算法准确性，我们通过构造SIFT特征来去除一些由于尺度、旋转等方面误检的候选帧，如图6所示。

图6 镜头放大造成的误检Fig.6 Misdetection caused by lens enlargement

SIFT特征的全称是尺度不变的特征变换[13], 它具有许多优点，例如对旋转、尺度、视角变化、仿射、噪声等变换的不变性。SIFT特征与SURF特征的主要区别在于：

(1)SIFT是在高斯差分图像金字塔中对每一层图像进行高斯滤波求取图像差来求取特征点。

(2)SIFT算法通过计算梯度直方图，然后查找其最大方向或大于80%处的最大bin方向来确定相应特征点的主方向。

(3)在确定特征描述子方面，SIFT算法采用了在16×16的邻域内分成4×4的区域，每个区域取8个方向，即特征向量维数=4×4×8=128维。

SIFT特征复选的算法如下：对候选帧首先计算其前一帧和后一帧的SIFT距离，如果匹配度小于阈值T3，则判定为切变镜头，反之计算其前后4帧的SIFT距离，如果匹配度小于阈值T4，则判定为渐变镜头，若匹配度大于T4，则说明既不是切变镜头也不是渐变镜头，去除即可。经过大量实验，确定阈值T3=0.3，T4=0.5时准确率最高。

3 实验流程和结果对比评价

3.1 实验环境

本实验硬件环境是CPU为Intel Core I7 6700，内存为4 GB，软件环境是操作系统为Windows 10 64位，编程环境为Visual Studio.NET 2015、OpenCV 2.4.13。测试视频数量为70个，分辨率均为320×240，码率均为326 kb/s。

3.2 实验数据

3.3 实验流程

本文算法实施流程如下：

(1)读取视频文件。

(2)读取成功进入下一步，失败则退出。

(3)读取下一帧，计算其HSV颜色特征，通过是否大于自适应阈值判断是否为切变镜头，若是，则将此帧加入候选帧，直接进入下一帧，否则进入下一步。

(4)结合SURF特征与HSV颜色特征，通过设定滑动窗口来判断此帧是否为切变镜头或渐变镜头，如果是，则加入候选帧。然后回到第二步。

(5)使用SIFT特征，通过对其前后帧及前后四帧的特征距离进行判断，筛选候选帧，剔除伪渐变镜头和伪切变镜头。

(6)保存并输出分割结果。

3.4 实验结果及评价

本文使用查准率和查全率作为评价指标,如式(13)、式(14)所示。

(13)

(14)

将视频数据通过图5算法流程进行分割，将得到的视频帧内容及帧数输出，与该视频数据人工标注帧对比，并计算其查准率和查全率，进而得到本文算法的综合指标。本节选取了几个视频片段在本文算法下的部份分割结果：

视频1长度为59 s，总帧数为1 798帧。视频2长度为7 min 43 s，总帧数为13 888帧。由于篇幅有限，仅选部份结果进行展示。视频片段1和视频片段2的镜头分割输出结果如图7、8所示。

(a) 切变镜头输出结果(a) Output of shear shot

(b) 渐变镜头输出结果(b) Output of gradual shot图7 视频片段1输出结果Fig.7 Output of shot segmentation in video clip 1

(a) 切变镜头输出结果(a) Output of shear shot

(b) 渐变镜头输出结果(b) Output of gradual shot图8 视频片段2输出结果Fig.8 Output of shot segmentation in video clip 2

本文算法与其他算法的精准度比较如表1所示。

由图7、图8可以看出，算法能够对切变镜头和渐变镜头进行有效的识别，为了说明本文算法的优势，我们通过使用70个视频数据测试本文算法与其它几种单一特征算法或文章中提到的一些算法进行比对,通过比较其平均查准率和平均查全率，显示了本文的方法无论在查准率还是查全率上都要稍高于其他算法。另外，通过和单一特征算法的单帧平均运行时间比较表明，融合后的特征比单一特征更为均衡，兼顾性能和准确性。

表1 本文算法与其他算法的精准度比较Tab.1 Comparion of the accuracy of the proposed algorithm with that of other algorithms

本文算法与其他算法的平均单帧运行时间比较如表2所示。

表2 本文算法与其他算法的平均单帧运行时间比较

Tab.2 Comparison of the average simgle frame run time between the proposed algorithm and other algorithms

算法单帧平均运行时间/sSIFT1.46SURF0.14HSV直方图0.05本文算法0.26

4 结 论

本文实现了一种基于SURF和SIFT特征的视频镜头分割算法.通过在初选阶段引入颜色和SURF特征并进行了特征融合，精巧地解决了SIFT特征效率不高的难题，同时增加了算法的准确性。在复选阶段使用SIFT进行筛选，又利用了SIFT特征的优势，进一步加强了算法的准确性。该算法有效地结合了局部特征和全局特征，可以精准快速地识别镜头边界，对切变镜头的查全率达到95%，查准率达到93%，对渐变镜头的检测查全率达到90%，查准率达到76%，并且平均单帧运行时间为0.26s。实验结果表明，通过特征融合，融合后的特征同时具备了两种特征的优点，而弥补了相应的缺点，起到了扬长补短的作用。此外，对于算法中SURF、SIFT特征检测器的阈值以及两帧匹配度的判定阈值均为实验所得的固定阈值，可以通过加入无监督学习来进一步优化。