SURF算法和RANSAC算法相結合的臺標檢測與識別

吳月鳳，何小海，張 峰，滕奇志

(四川大學電子信息學院，四川成都 610064)

電視臺的臺標［1］是確定電視臺的臺名、節目取義的重要信息，是區分不同電視臺唯一標志。為了聲明視頻的所有權，往往會在播放的視頻中加入臺標。若用人工來識別則工作量很繁重。目前主要存在基于顏色直方圖［2］和普通Hu不變矩［3］兩類臺標自動檢測與識別［4］。

近年來，基于特征點的匹配方法越來越被廣泛的運用，SIFT［5－6］(Scale Invariant Feature Transform)是由 D.G.Lowe在1999年提出來的，之后Y.Ke對其算法進行改進，提出了 PAC － SIFT。Herbert Bay 在 SURF［7－8］(Speeded Up Robust Feature)中利用Integral和Hessian矩陣對其進行加速。

直接用SURF算法得到的匹配點對數，會出現很多錯誤的匹配，直接影響著匹配結果。本文融合了SURF算法與RANSAC［9］算法的各自優點，提出了只對感興趣區域利用SURF提取特征，對得到的特征點對用RANSAC進行分類。首先需要用SURF算法創建一個臺標特征點庫。第二步得到視頻中感興趣的區域，即臺標可能出現的位置，同樣用SURF算法提取它的特征點。第三步將視頻幀中提取的特征點與庫中提取的特征點進行預匹配。最后通過RANSAC算法將錯誤匹配的特征點去掉，得到最終的匹配結果，計算出匹配率并進行排序，得到最大的結果與設定的閾值進行比較，從而識別出視頻中的臺標。

1 SURF匹配

為了保證旋轉不變性和尺度不變性，SURF提取的特征信息由矩陣Hessian得到的極值點，同時還增加了一個包含主方向的特征描述符。

1.1 SURF特征提取

為提高運算速度，利用積分方式實現圖像卷積。積分圖像定義如下:設X=(x，y)表示圖像I(X)中某一像素點，則積分圖像IΣ(X)是由點X=(x，y)與原點為對角頂點組成的矩形框內的所有像素點之和，即

因為在積分時只需要遍歷一次原始圖像即可，計算積分圖像時它的運算非常小。假如矩形由A、B、C和D四個頂點構成，則矩形的窗口內的總灰度為Σ=A－B C+D。

給定圖像I中的一個點X=(x，y)，Hessian矩陣H(x，σ)在x處尺度為σ的定義如下

式中:參數ω是一個調節參數，用于平衡Hessian行列式表達式，計算如下

由H矩陣的特征值得到判別式的值，在判定結果的基礎上將所有的點進行分類，根據判別式取值判斷是否是極值點。然后將低于預先設定極值的取值丟棄，實現特征點精確定位，通過增加極值以減少特征點數，最后留下最強的特征點。

1.2 特征點的匹配

當計算得到所需要的特征點之后，計算出該點的主方向，然后提取特征描述符，找出圖像中與之對應特征點的位置。只有確定圖像之間特征點的關系，才能完成對后續兩幅圖像的關系進行判斷。特征點是否匹配成功是用特征描述符之間的相似度來判別的。

設n1，n2為圖像Q，T的特征數，Qi(i=1，2，…，n1)為查詢圖像的任意特征點，Ti(j=1，2，…，n2)為目標圖像的任意特征點，則定義Qi與Ti之間的相似度為

根據式(5)，把查詢圖像的Qi與目標圖像中的所有特征點計算一遍，如果單純地取它們之間的最小值作為兩個特征點匹配的依據，則會出現錯誤匹配。因此對視頻幀中臺標的某一特征點，在臺標庫中找出和它歐氏距離最近的兩個特征點，d1表示兩者之間的最近距離，d2表示兩者之間的次近距離，為了消除背景或遮擋帶來的干擾而產生的無對應關系的特征點，Lowe提出用d1和d2相比較的方法，匹配準則是當d1＜a×d2時(其中a為比例系數，取值范圍在0～1)，若滿足匹配準則即可認為該點對成功配對。顯然，當a越小，匹配成功的點對越少，但相對更加穩定;當a越大，則錯誤匹配的幾率就有可能增加。

1.3 計算感興趣的區域

不同于其他類型的圖像，國內的電視臺標一般置于4個角附近的矩形區域［11］內，基于臺標這一特殊位置的特點，本文提出了先獲得視頻幀中感興趣區域。為了提高算法的魯棒性，假設臺標在感興趣區域中的偏移量為δ個像素，即臺標的左上角位置位于(xi－δ，yi－δ)和(xi+δ，yi+δ)的矩形區域內。本文的感興趣區域采用式(6)表示

對待測試圖像的感興趣區域［11］為

式中:ROIi表示第i個待識別圖像的感興趣區域;MIN表示最小值;MAX表示最大值。只對感興趣區域提取特征點很大程度上提高了識別的速度。

2 RANSAC算法

RANSAC［12－13］(Random Sample Consensus)算法是基于一組包含異常數據的樣本數據集，通過迭代方式估計數學模型的參數，得到有效樣本數據的算法。它于1981年由Fischler和Bolles最先提出。RANSAC基本思想是先任意取兩個特征點畫一條直線，用事先確定的誤差計算直線包含的點數，包含在直線上的點稱為內點，根據所謂的內點重新得出一條直線，不斷重復直到內點數不再變化，最后得出RANSAC算法的擬合結果。

3 判決準則

3.1 匹配點對的過濾

本文對SURF算法所得到的匹配點對進行排序，得到匹配最多的特征點對可能是視頻幀中的臺標，所以需要設定對應的判決標準。在用SURF進行特征點配對時，根據1.2節中設定的系數a來判斷點對是否匹配成功。本文在實驗中遇到多個特征點對應一個特征點的情況(如圖1所示)，如果沒有進行透視轉換關系，下文中提到的匹配率有可能大于1，這對于正確的臺標匹配是不合理的。

因此單純地將SURF提取的特征點進行匹配得到的對數作為臺標的排序是不合理的，所以很有必要使用RANSAC隨機抽樣方法來計算預匹配點對之間的透視變換關系。為提高匹配的正確率，首先必須實現臺標的正確定位。因此本文首先用SURF提取臺標的特征點與臺標庫中的臺標特征點進行預匹配，然后進行透視變換去除錯誤的點對，濾除后的點對作為它的最終匹配點對數，將點對進行排序得到最多對數，計算出匹配率再與設定的閾值比較，最后得出它的識別結果。

圖1 點對過濾效果圖(截圖)

3.2 匹配率

對于臺標的特征點參差不一的情況，無法通過設定對數閾值來判斷是否匹配成功，所以可以用一個比值來表達相同的含義，于是引入了匹配率。本文定義匹配率T為

式中:C表示經過RANSAC算法后得到的匹配成功最多的對數;Stemp表示在待識別臺標中提取的特征點數;T表示臺標中匹配成功最多的對數與待測臺標特征點數的比值。

4 算法的流程描述

本文算法的流程圖如圖2所示。首先從視頻中獲取一幀圖像，然后計算感興趣區域并只對感興趣區域提取SURF特征，與臺標庫提取的SURF特征預匹配，再用RANSAC算法過濾匹配點對，接下來對匹配成功的點對數進行排序，得到匹配最多的對數，計算出它的匹配率，最后將得算出的匹配率與設定好的閾值比較大小，識別出視頻幀中的臺標是否存在于臺標庫中。

圖2 實驗流程圖

5 實驗結果與分析

本文在實驗中首先選擇一些背景干擾比較少的電視臺的臺標提取特征信息。然后提取一些包含臺標和不包含臺標的視頻幀，將它們一部分存檔一部分不存檔。實驗中的測試目標包括CCTV2、CCTV4、CCTV7、安徽衛視、河南衛視、東南衛視、兵團衛視、甘肅衛視、西藏衛視、云南衛視、湖北衛視等25個電視臺標，每個臺標的視頻提取20幀作為樣本。實驗采用C++與OPENCV庫相結合的方式進行臺標的檢測與識別。測試機器為雙核酷睿i3，主頻2.1 GHz。

表1為實驗中用透視變換關系與不用透視變換關系得到的統計識別率情況。經過多次實驗得到當設定的最近距離與次近距離的比例因子a為0.6、匹配率的閾值T為0.13時識別率最高。識別率的統計方法為

表1 實驗中臺標識別結果

匹配率T是臺標識別的判斷標準，它的大小會直接影響著臺標識別的結果。據實驗統計，匹配率T的值對正確識別率的影響關系如圖3所示，可以看出當T=0.13左右時，識別的正確率最高。

圖3 T值對識別結果的影響

圖4為部分實驗結果，其中圖4a～圖4e為正確識別出的臺標，圖4f為臺標庫中未存檔的臺標，圖4g、圖4h為未識別出。

圖4 部分臺標匹配的結果(截圖)

由表2知，將本文使用的識別方法與常用的模板匹配的方法進行比較，可以看出對于透明的臺標，本文使用的方法比模板匹配的識別率要高。另外用本文的方法可以保證旋轉不變和尺度不變的優點。而模板匹配則沒有這個優點。

本文只提取感興趣區域的特征點以提高識別速度。為更充分說明這點，本文分別在使用ROI與不使用ROI的情況下，統計了部分臺標在識別過程所消耗的時間，表3是兩種情況下每個臺標與一個視頻幀匹配所消耗的時間。先計算感興趣區域，在很大程度上減少了臺標識別所用時間。

表2 本文算法與模板匹配算法識別結果的對比

表3 部分臺標識別所消耗的時間 ms

6 結論

本文提出一種基于SURF算法與RANSAC算法相結合的臺標檢測與識別，首先對視頻幀中感興趣區域用SURF算法提取特征點，并與臺標庫中的特征點進行預匹配，再利用RANSAC算法對匹配的特征點對過濾，得到最后的匹配點對。實驗取得了令人滿意的正確率，較好地實現了視頻幀中的臺標檢測與識別。實驗表明本文算法對標在識別率以及識別速度上都取得了很好的效果。

:

［1］張重德.電視信號自動檢測與報警系統［D］.合肥:合肥工業大學，2008.

［2］秦劍鵬，符茂勝，涂錚錚，等.基于顏色直方圖變化率的視頻鏡頭檢測［J］. 計算機應用與軟件，2011，28(4):17－20.

［3］王振海.融合HU不變矩和SIFT特征的商標檢索［J］.計算機工程與應用，2012，48(1):187－190.

［4］YAN W，WANG J，MOHAN S.Automatic video logo detection and removal［J］.Multi－media System，2005，10(5):379.

［5］郭振成，梁鳳梅.一種改進的SIFT特征點匹配算法［J］.電視技術，2014，38(1):23－25.

［6］YANG Z，GUO B.Image mosaic based on SIFT［C］//Proc.International Conference on Intelligent Information Hiding and Multimedia Signal Processing.［S.l.］:IEEE Press，2008:1422－1425.

［7］BAY H，ESS A，TUYTELAARS T，et al.Surf:speed up robust feature［EB/OL］.［2014－02－02］.http://www.vision.ee.ethz.ch/～ surf/.

［8］張鵬雁，趙耀，朱振峰.基于商標匹配的視頻廣告識別［J］.信號處理，2012，28(8):1083－1089.

［9］LUO C，JAMES H.Robust geolocation estimation using adaptive RANSAC algorithm［J］.IEEE Geosci.Remote Sens.Lett. ，2010，9(3):3862－3865.

［10］LOWE D.Object recognition from local scale－invariant features［C］//Proc.the 7th IEEE International Conference on Computer Vision.［S.l.］:IEEE Press，1999:1150－1157.

［11］侯勝偉，何小海，滕奇志.臺標的自動檢測與識別［J］.四川大學學報:自然科學版，2013，50(3):521－526.

［12］LIU K，JIE Q，YANG R.Block matching algorithm based on RANSAC algorithm［C］//Proc.IASP 2010.［S.l.］:IEEE Press，2010:223－227.

［13］MARTIN A，ROBERT C.Random sample consensus:a paradigm for modelfitting with applications to image analysis and automated cartography［J］.Communications of the ACM，1981，24(6):381－395.