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

甘蓉

(陜西工業(yè)職業(yè)技術(shù)學(xué)院，咸陽 712000)

0 引言

隨著互聯(lián)網(wǎng)和數(shù)字技術(shù)的的不斷發(fā)展，視頻分割算法在視頻領(lǐng)域得到了廣泛應(yīng)用。所謂的視頻分割就是將一段連續(xù)的視頻分成若干個鏡頭。一般認(rèn)為只要存在鏡頭切換就屬于不連續(xù)幀。目前已經(jīng)提出了許多視頻分割算法。但是，視頻水印技術(shù)要求具有分割算法具有較高的計算速度和較高的分割性能。

當(dāng)一段視頻內(nèi)的鏡頭緩慢變化時，其相鄰兩幀之間圖像具有緩慢變化特性；當(dāng)一段視頻內(nèi)的鏡頭急劇變化時，其相鄰兩幀之間圖像具有劇烈變化的特性。當(dāng)相鄰兩幀之間圖像的光照強度出現(xiàn)變化時，其圖像內(nèi)容變化不大，但整體圖像像素值會出現(xiàn)明顯變化。

研究表明，一幅圖像的特征點不隨圖像的光照強度變化而發(fā)生明顯變化。當(dāng)相鄰兩幀視頻之間的鏡頭緩慢變化時，其特征點變化也不大。因此，借鑒于該思想，本文建立一種基于改進(jìn)的SIFT特征點的視頻分割算法，可精確檢測鏡頭切邊，實現(xiàn)視頻分割。

1 Radon-SIFT特征點

從SIFT特征點的提取過程可看出，通過采用高斯模糊函數(shù)、高斯差分函數(shù)、以及極值點的選取能保證特征點不受噪聲、亮度的影響，同時還可以保證具有尺度不變性[1]。

然而，雖然傳統(tǒng)的SIFT特征點算法具有比較好的穩(wěn)定性，但是其計算復(fù)雜度較高，這是因為，在特征點的方向匹配中，需要用到直方圖運算，其特征向量的計算量非常大，而在特征點匹配時其計算量也非常大。本文通過減少生成特征描述符的計算量，并通過提高特征匹配速度來提高算法的計算速度。

借鑒于圖像的跡變換，本文采用改進(jìn)SIFT算法的特征點描述符。所謂的圖像跡變換就是用正交函數(shù)或正交矩陣表示圖像，對原始圖像做二維線性的可逆變換[9]。具體計算規(guī)則為：假設(shè)一幅圖像f，l表示一條直線，g表示某種變換。假設(shè)轉(zhuǎn)換規(guī)則為T，則l和f在該規(guī)則下的變換結(jié)果為g=T(l,f)。

如果轉(zhuǎn)換規(guī)則是T為積分型函數(shù)，則為Radon變換。其數(shù)學(xué)意義就是計算圖像在某個方向上的投影。假設(shè)一條直線l，坐標(biāo)原點到該直線的距離為d，該直線的方向角為α，一幅圖像f(x,y)，則對f(x,y)沿著不同直線做積分，可得到F(x,y)，則稱F(x,y)為f(x,y)的Radon變換。一般常用的直線為旋轉(zhuǎn)角度固定的直線，其計算公式如式(1)。

變換后新的坐標(biāo)點為：

Radon變換一般是用于中心對準(zhǔn)的兩幅圖像。SIFT提取的特征點是一個區(qū)域圖像，以特征點為中心。因此，需要對SIFT特征匹配算法進(jìn)行改進(jìn)。首先，提取SIFT特征點；然后，對圖像特征點作Radon變換，選取某些特定方向的直線計算圖像的Radon 變換值作為SIFT特征點。具體方法措施如下：

1) 增加乘積因子。如圖1所示。

圖1 基于Radon變換的SIFT特征向量

假設(shè)SIFT特征點主方向為y’，與y軸的夾角為θ。SIFT算法中的高斯模糊函數(shù)實際上是一個權(quán)重濾波，距離當(dāng)前位置點越近，比重最大；離得越遠(yuǎn)，比重越小。我們通過在Radon變換中增加一個乘積因子1/(1+|x|)，則可實現(xiàn)相同功能，其形式如式(2)。

(2)

其中，S表示以特征點為中心的積分區(qū)域。

2) 圖像I(x,y)在主方向直線y’上的Radon變換表示為式(3)

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

(3)

對于d維的SIFT特征向量，以特征點的主方向所在直線y’為準(zhǔn)，作其他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特征點基礎(chǔ)上，接下來對特征點進(jìn)行匹配。特征點匹配的過程如下：對于同一個空間點I，在相鄰兩視頻幀上的特征點為I1和I2，前一個視頻幀中的每個特征點I1，在后一個視頻幀中找出與之相對應(yīng)的特征點I2。

本文采用最鄰近法尋找匹配點。最鄰近法的思路是：對于一個特征點，假設(shè)d是該特征點的特征向量，則d的最鄰近點d’是所有特征點中與d歐式距離最小的。兩個k維特征向量d和s之間的歐氏距離為式(5)。

(5)

根據(jù)最鄰近法的思想，基于Radon-SIFT特征點匹配算法過程如下：對于兩個視頻幀，假設(shè)I表示前一個視頻幀的Radon-SIFT的特征點，接下來在后一個視頻幀的特征點里找到與特征點I最鄰近的特征點Il和次鄰近的特征點I2，并計算其歐氏距離的比率，如式(6)所示。

(6)

如果比率Radio小于閾值Th，則認(rèn)為I與Il匹配。閾值Th的取值會影響匹配準(zhǔn)確率，一般經(jīng)驗取值為0.8。

3 特征點匹配實驗仿真

3.1 尺度不變性

采用一副灰度圖像對算法的尺度不變性進(jìn)行仿真測試，如圖2所示。

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

圖2 不同尺度下的圖像

圖2(a)是原始圖像，圖2(b)、(c)和(d)分別為原始圖像的0.9、0.8和0.6倍大小。接下來，分別比較Radon-SIFT與SURF特征點匹配的準(zhǔn)確度。

Radon-SIFT和SURF算法在不同尺度下的特征點的匹配準(zhǔn)確度。如圖3所示。

圖3 不同尺度下的匹配準(zhǔn)確率

由圖3可知SIFT的特征點對數(shù)量基本保持不變，直至接近100%。而SURF特征點匹配準(zhǔn)確度在最大尺度處有所降低。這說明Radon-SIFT特征點匹配算法具有較高的準(zhǔn)確性。

3.2 噪聲不變性

接下來，采用一副灰度圖像對算法的噪聲不變性進(jìn)行仿真測試，如圖4所示。圖4(a)是原始圖像，圖4(b)、(c)和(d) 分別添加了2%、5%、10%不同程度的椒鹽噪聲，接下來，分別比較Radon-SIFT與SURF特征點匹配的準(zhǔn)確度。

圖5所示為Radon-SIFT和SURF算法在不同尺度下的特征點的匹配準(zhǔn)確度，如圖5所示。由圖5可知，在不同的椒鹽噪聲幅度下，兩種算法的特征點匹配率相差不大，Radon-SIFT特征點匹配率略高于SURF算法。這是因為。由于添加的噪聲并沒有影響兩者的高匹配率。這說明，Radon-SIFT特征點對于椒鹽噪聲具有較低的敏感性。

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

圖4 加入椒鹽噪聲下的圖像

圖5 不同椒鹽噪聲強度下的匹配準(zhǔn)確率

接下來分析高斯噪聲對匹配率的影響，如圖6所示。圖6(a)是原始圖像，圖6(b)、(c)和(d)分別表示添加了均值為零、差為2%、5%、10%的高斯白噪聲。接下來，分別比較Radon-SIFT與SURF特征點匹配的準(zhǔn)確度。

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

圖6 加入高斯噪聲下的圖像

圖7所示為Radon-SIFT和SURF算法在不同尺度下的特征點的匹配準(zhǔn)確度，如圖7所示。

圖7 不同高斯噪聲強度下的匹配準(zhǔn)確率

由圖7可知，在不同的高斯噪聲強度下，兩種算法的特征點匹配率相差不大，Radon-SIFT特征點匹配率略高于SURF算法。這是因為添加的噪聲并沒有影響兩者的高匹配率。上述例子說明，Radon-SIFT特征點對于高斯噪聲具有較低的敏感性。

3.3 旋轉(zhuǎn)不變性

接下來，采用一副灰度圖像對算法的旋轉(zhuǎn)不變性進(jìn)行仿真測試。原始圖像如圖6(a)所示，將原始圖像每間隔30度進(jìn)行一次旋轉(zhuǎn)，然后分別采用Radon-SIFT和SURF特征點匹配法與原始圖像進(jìn)行匹配，如圖8所示。

圖8 不同旋轉(zhuǎn)角度下的匹配準(zhǔn)確率

從圖8可看出，Radon-SIFT特征點匹配算法對于旋轉(zhuǎn)具有較低的敏感性。

3.4 光照不變性

下面來分析光照強度對特征點的匹配準(zhǔn)確度的影響。如圖9所示。

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

圖9 不同光照強度下的圖像

圖9(a)為原始圖像。圖9(b)、(c)和(d)分別為光照強度1.2倍、1.5倍、1.8倍下的圖像。

對應(yīng)光照強度下的匹配準(zhǔn)確率，如圖10所示?？梢钥闯?，Radon-SIFT及SURF特征點的匹配準(zhǔn)確度都能保持在95%以上。

圖10 不同光照強度下的匹配準(zhǔn)確率

3.5 計算速度比較

以3幅圖像作為原始圖像，分別以Radon-SIFT和SURF算法提取特征點。這3幅圖像的尺寸分別為600×400，640×480和1024×468。提取的特征點數(shù)和計算時間，如表1所示。從表中1可看出，對于相同的圖像，Radon-SIFT提取特征點的時間與SURF算法基本一樣，但提取的數(shù)目小于SURF算法，這說明Radon-SIFT提取特征點優(yōu)于SURF算法。

表1 計算時間比較

4 基于特征點匹配的視頻分割

在獲得匹配特征點后，根據(jù)特征點做視頻分割，提出以下基于Radon-SIFT特征點匹配的視頻分割算法。當(dāng)一個鏡頭切換時，視頻幀的內(nèi)容變化很大，因此其Radon-SIFT特征點也會發(fā)生很大變化，不同鏡頭的視頻Radon-SIFT特征點的匹配率會降低。相反的，同一鏡頭的Radon-SIFT特征點匹配率較高。因此，本文根據(jù)視頻幀特征點的匹配率來對鏡頭進(jìn)行分割。為了對視頻進(jìn)行分割，以每相鄰兩視頻幀之間的Radon-SIFT特征點匹配率作為視頻幀相似性度量。具體步驟如下：首先，對任意相鄰的兩個視頻幀，計算其各自的Radon-SIFT特征點匹配個數(shù)。接下來，從首幀開始計算相鄰兩視頻幀的Radon-SIFT特征點匹配率。最后得到一條征點匹配率隨幀變化的曲線。如果鏡頭發(fā)生切換，則Radon-SIFT特征點匹配率會急劇下降，此時就可認(rèn)為此處鏡頭發(fā)生切換。

選取的一段視頻經(jīng)過Radon-SIFT特征點匹配方法所得到的邊界幀。如圖11所示。圖11為選取的另一段視頻尋找出的邊界幀，這是明顯的鏡頭切換點。如圖12該段視頻特征點匹配率隨幀數(shù)n的變化曲線，如圖13所示。從圖中可以看出，匹配率在四個點處出現(xiàn)極小值，這表明這4個點為鏡頭切換點，這與圖14的視頻分割的結(jié)果一致。

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

圖11 視頻鏡頭邊界

該段視頻特征點匹配率隨幀數(shù)n的變化曲線。如圖12所示。

從圖12中可以看出，匹配率在4個點處出現(xiàn)極小值，這表明這4個點為鏡頭切換點，這與圖10的視頻分割的結(jié)果一致，如圖13、圖14所示。

從上面兩段視頻幀的鏡頭分割實驗結(jié)果可發(fā)現(xiàn)，本文方法基本可以準(zhǔn)確分割出鏡頭切換點。從仿真實驗中發(fā)現(xiàn)，對

圖12 特征點匹配率

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

圖13 視頻鏡頭邊界

圖14 特征點匹配率

鏡頭的漸變拉伸、攝影機(jī)的漸變運動、以及光亮強度的變化，基于Radon-SIFT特征點匹配率方法，均有較高的特征點匹配率。相反，如果是鏡頭的切換而出現(xiàn)的突變，特征點匹配率接近于零。這說明本文方法可用于視頻幀的分割，并且這種視頻分割技術(shù)具有尺度不變性、噪聲不變性和光照不變性。

[1] 萬崇瑋, 李煒明. 基于尺度不變特征的視頻鏡頭檢測[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2007, 19(9): 1094-1099.

[2] 肖尚勤. 魯棒數(shù)字水印算法研究[D]. 武漢: 華中科技大學(xué), 2008.

[3] 于麗莉, 戴青. 一種改進(jìn)的SIFT特征匹配算法[J]. 計算機(jī)工程, 2011, 37(2): 216-218.

[4] 毛運柳, 黃東軍. 基于SURF視頻分割的視頻水印算法[J]. 計算機(jī)工程, 2010.

[5] 陳真勇, 唐龍, 唐澤圣, 等. 以魯棒性為目標(biāo)的數(shù)字水印研究[J]. 計算機(jī)學(xué)報, 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.