基于特征點匹配的視頻分割算法研究

甘蓉

(陜西工業職業技術學院，咸陽 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.