甘蓉

(陕西工业职业技术学院，咸阳 712000)

0 引言

随着互联网和数字技术的的不断发展，视频分割算法在视频领域得到了广泛应用。所谓的视频分割就是将一段连续的视频分成若干个镜头。一般认为只要存在镜头切换就属于不连续帧。目前已经提出了许多视频分割算法。但是，视频水印技术要求具有分割算法具有较高的计算速度和较高的分割性能。

当一段视频内的镜头缓慢变化时，其相邻两帧之间图像具有缓慢变化特性；当一段视频内的镜头急剧变化时，其相邻两帧之间图像具有剧烈变化的特性。当相邻两帧之间图像的光照强度出现变化时，其图像内容变化不大，但整体图像像素值会出现明显变化。

研究表明，一幅图像的特征点不随图像的光照强度变化而发生明显变化。当相邻两帧视频之间的镜头缓慢变化时，其特征点变化也不大。因此，借鉴于该思想，本文建立一种基于改进的SIFT特征点的视频分割算法，可精确检测镜头切边，实现视频分割。

1 Radon-SIFT特征点

从SIFT特征点的提取过程可看出，通过采用高斯模糊函数、高斯差分函数、以及极值点的选取能保证特征点不受噪声、亮度的影响，同时还可以保证具有尺度不变性[1]。

然而，虽然传统的SIFT特征点算法具有比较好的稳定性，但是其计算复杂度较高，这是因为，在特征点的方向匹配中，需要用到直方图运算，其特征向量的计算量非常大，而在特征点匹配时其计算量也非常大。本文通过减少生成特征描述符的计算量，并通过提高特征匹配速度来提高算法的计算速度。

借鉴于图像的迹变换，本文采用改进SIFT算法的特征点描述符。所谓的图像迹变换就是用正交函数或正交矩阵表示图像，对原始图像做二维线性的可逆变换[9]。具体计算规则为：假设一幅图像f，l表示一条直线，g表示某种变换。假设转换规则为T，则l和f在该规则下的变换结果为g=T(l,f)。

如果转换规则是T为积分型函数，则为Radon变换。其数学意义就是计算图像在某个方向上的投影。假设一条直线l，坐标原点到该直线的距离为d，该直线的方向角为α，一幅图像f(x,y)，则对f(x,y)沿着不同直线做积分，可得到F(x,y)，则称F(x,y)为f(x,y)的Radon变换。一般常用的直线为旋转角度固定的直线，其计算公式如式(1)。

变换后新的坐标点为：

Radon变换一般是用于中心对准的两幅图像。SIFT提取的特征点是一个区域图像，以特征点为中心。因此，需要对SIFT特征匹配算法进行改进。首先，提取SIFT特征点；然后，对图像特征点作Radon变换，选取某些特定方向的直线计算图像的Radon 变换值作为SIFT特征点。具体方法措施如下：

1) 增加乘积因子。如图1所示。

图1 基于Radon变换的SIFT特征向量

假设SIFT特征点主方向为y’，与y轴的夹角为θ。SIFT算法中的高斯模糊函数实际上是一个权重滤波，距离当前位置点越近，比重最大；离得越远，比重越小。我们通过在Radon变换中增加一个乘积因子1/(1+|x|)，则可实现相同功能，其形式如式(2)。

(2)

其中，S表示以特征点为中心的积分区域。

2) 图像I(x,y)在主方向直线y’上的Radon变换表示为式(3)

I(x′cosθ-y′sinθ,x′sinθ+y′cosθ)dy

(3)

对于d维的SIFT特征向量，以特征点的主方向所在直线y’为准，作其他d-1条直线l1,l2,…,ld-1，如图1所示，则相邻两条直线的夹角为α=2π/d，则图像在这些直线上的Radon变换如式(4)

I(xlncosωn-ylnsinθ,xlnsinθ+ylncosθ)dyln

(4)

其中，ωn=θ+nα,n=1,2,…,d-1。

3) 对SIFT特征向量长度做归一化处理，可生成d维Radon-SIFT 特征点描述符，表示为(Rθx′,Rω1xl1,Rω1xl1,…,Rωdxld-1)。

2 特征点匹配

在得到上面Radon-SIFT特征点基础上，接下来对特征点进行匹配。特征点匹配的过程如下：对于同一个空间点I，在相邻两视频帧上的特征点为I1和I2，前一个视频帧中的每个特征点I1，在后一个视频帧中找出与之相对应的特征点I2。

本文采用最邻近法寻找匹配点。最邻近法的思路是：对于一个特征点，假设d是该特征点的特征向量，则d的最邻近点d’是所有特征点中与d欧式距离最小的。两个k维特征向量d和s之间的欧氏距离为式(5)。

(5)

根据最邻近法的思想，基于Radon-SIFT特征点匹配算法过程如下：对于两个视频帧，假设I表示前一个视频帧的Radon-SIFT的特征点，接下来在后一个视频帧的特征点里找到与特征点I最邻近的特征点Il和次邻近的特征点I2，并计算其欧氏距离的比率，如式(6)所示。

(6)

如果比率Radio小于阈值Th，则认为I与Il匹配。阈值Th的取值会影响匹配准确率，一般经验取值为0.8。

3 特征点匹配实验仿真

3.1 尺度不变性

采用一副灰度图像对算法的尺度不变性进行仿真测试，如图2所示。

(a)(b)(c)(d)

图2 不同尺度下的图像

图2(a)是原始图像，图2(b)、(c)和(d)分别为原始图像的0.9、0.8和0.6倍大小。接下来，分别比较Radon-SIFT与SURF特征点匹配的准确度。

Radon-SIFT和SURF算法在不同尺度下的特征点的匹配准确度。如图3所示。

图3 不同尺度下的匹配准确率

由图3可知SIFT的特征点对数量基本保持不变，直至接近100%。而SURF特征点匹配准确度在最大尺度处有所降低。这说明Radon-SIFT特征点匹配算法具有较高的准确性。

3.2 噪声不变性

接下来，采用一副灰度图像对算法的噪声不变性进行仿真测试，如图4所示。图4(a)是原始图像，图4(b)、(c)和(d) 分别添加了2%、5%、10%不同程度的椒盐噪声，接下来，分别比较Radon-SIFT与SURF特征点匹配的准确度。

图5所示为Radon-SIFT和SURF算法在不同尺度下的特征点的匹配准确度，如图5所示。由图5可知，在不同的椒盐噪声幅度下，两种算法的特征点匹配率相差不大，Radon-SIFT特征点匹配率略高于SURF算法。这是因为。由于添加的噪声并没有影响两者的高匹配率。这说明，Radon-SIFT特征点对于椒盐噪声具有较低的敏感性。

(a)(b)(c)(d)

图4 加入椒盐噪声下的图像

图5 不同椒盐噪声强度下的匹配准确率

接下来分析高斯噪声对匹配率的影响，如图6所示。图6(a)是原始图像，图6(b)、(c)和(d)分别表示添加了均值为零、差为2%、5%、10%的高斯白噪声。接下来，分别比较Radon-SIFT与SURF特征点匹配的准确度。

(a)(b)(c)(d)

图6 加入高斯噪声下的图像

图7所示为Radon-SIFT和SURF算法在不同尺度下的特征点的匹配准确度，如图7所示。

图7 不同高斯噪声强度下的匹配准确率

由图7可知，在不同的高斯噪声强度下，两种算法的特征点匹配率相差不大，Radon-SIFT特征点匹配率略高于SURF算法。这是因为添加的噪声并没有影响两者的高匹配率。上述例子说明，Radon-SIFT特征点对于高斯噪声具有较低的敏感性。

3.3 旋转不变性

接下来，采用一副灰度图像对算法的旋转不变性进行仿真测试。原始图像如图6(a)所示，将原始图像每间隔30度进行一次旋转，然后分别采用Radon-SIFT和SURF特征点匹配法与原始图像进行匹配，如图8所示。

图8 不同旋转角度下的匹配准确率

从图8可看出，Radon-SIFT特征点匹配算法对于旋转具有较低的敏感性。

3.4 光照不变性

下面来分析光照强度对特征点的匹配准确度的影响。如图9所示。

(a)(b)(c)(d)

图9 不同光照强度下的图像

图9(a)为原始图像。图9(b)、(c)和(d)分别为光照强度1.2倍、1.5倍、1.8倍下的图像。

对应光照强度下的匹配准确率，如图10所示。可以看出，Radon-SIFT及SURF特征点的匹配准确度都能保持在95%以上。

图10 不同光照强度下的匹配准确率

3.5 计算速度比较

以3幅图像作为原始图像，分别以Radon-SIFT和SURF算法提取特征点。这3幅图像的尺寸分别为600×400，640×480和1024×468。提取的特征点数和计算时间，如表1所示。从表中1可看出，对于相同的图像，Radon-SIFT提取特征点的时间与SURF算法基本一样，但提取的数目小于SURF算法，这说明Radon-SIFT提取特征点优于SURF算法。

表1 计算时间比较

4 基于特征点匹配的视频分割

在获得匹配特征点后，根据特征点做视频分割，提出以下基于Radon-SIFT特征点匹配的视频分割算法。当一个镜头切换时，视频帧的内容变化很大，因此其Radon-SIFT特征点也会发生很大变化，不同镜头的视频Radon-SIFT特征点的匹配率会降低。相反的，同一镜头的Radon-SIFT特征点匹配率较高。因此，本文根据视频帧特征点的匹配率来对镜头进行分割。为了对视频进行分割，以每相邻两视频帧之间的Radon-SIFT特征点匹配率作为视频帧相似性度量。具体步骤如下：首先，对任意相邻的两个视频帧，计算其各自的Radon-SIFT特征点匹配个数。接下来，从首帧开始计算相邻两视频帧的Radon-SIFT特征点匹配率。最后得到一条征点匹配率随帧变化的曲线。如果镜头发生切换，则Radon-SIFT特征点匹配率会急剧下降，此时就可认为此处镜头发生切换。

选取的一段视频经过Radon-SIFT特征点匹配方法所得到的边界帧。如图11所示。图11为选取的另一段视频寻找出的边界帧，这是明显的镜头切换点。如图12该段视频特征点匹配率随帧数n的变化曲线，如图13所示。从图中可以看出，匹配率在四个点处出现极小值，这表明这4个点为镜头切换点，这与图14的视频分割的结果一致。

(a)(b)(c)(d)

图11 视频镜头边界

该段视频特征点匹配率随帧数n的变化曲线。如图12所示。

从图12中可以看出，匹配率在4个点处出现极小值，这表明这4个点为镜头切换点，这与图10的视频分割的结果一致，如图13、图14所示。

从上面两段视频帧的镜头分割实验结果可发现，本文方法基本可以准确分割出镜头切换点。从仿真实验中发现，对

图12 特征点匹配率

(a)(b)(c)(d)

图13 视频镜头边界

图14 特征点匹配率

镜头的渐变拉伸、摄影机的渐变运动、以及光亮强度的变化，基于Radon-SIFT特征点匹配率方法，均有较高的特征点匹配率。相反，如果是镜头的切换而出现的突变，特征点匹配率接近于零。这说明本文方法可用于视频帧的分割，并且这种视频分割技术具有尺度不变性、噪声不变性和光照不变性。

[1] 万崇玮, 李炜明. 基于尺度不变特征的视频镜头检测[J]. 计算机辅助设计与图形学学报, 2007, 19(9): 1094-1099.

[2] 肖尚勤. 鲁棒数字水印算法研究[D]. 武汉: 华中科技大学, 2008.

[3] 于丽莉, 戴青. 一种改进的SIFT特征匹配算法[J]. 计算机工程, 2011, 37(2): 216-218.

[4] 毛运柳, 黄东军. 基于SURF视频分割的视频水印算法[J]. 计算机工程, 2010.

[5] 陈真勇, 唐龙, 唐泽圣, 等. 以鲁棒性为目标的数字水印研究[J]. 计算机学报, 2006, 29(11): 2037-2042.

[6] Kuo TY. Lo YC. Fragile video watermarking technique by motion field embedding with rate distortion monition[J]. Journal of Communication and Computer, 2009, 6(1): 16-23.