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

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

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

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

直接用SURF算法得到的匹配點(diǎn)對數(shù)，會(huì)出現(xiàn)很多錯(cuò)誤的匹配，直接影響著匹配結(jié)果。本文融合了SURF算法與RANSAC［9］算法的各自優(yōu)點(diǎn)，提出了只對感興趣區(qū)域利用SURF提取特征，對得到的特征點(diǎn)對用RANSAC進(jìn)行分類。首先需要用SURF算法創(chuàng)建一個(gè)臺(tái)標(biāo)特征點(diǎn)庫。第二步得到視頻中感興趣的區(qū)域，即臺(tái)標(biāo)可能出現(xiàn)的位置，同樣用SURF算法提取它的特征點(diǎn)。第三步將視頻幀中提取的特征點(diǎn)與庫中提取的特征點(diǎn)進(jìn)行預(yù)匹配。最后通過RANSAC算法將錯(cuò)誤匹配的特征點(diǎn)去掉，得到最終的匹配結(jié)果，計(jì)算出匹配率并進(jìn)行排序，得到最大的結(jié)果與設(shè)定的閾值進(jìn)行比較，從而識別出視頻中的臺(tái)標(biāo)。

1 SURF匹配

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

1.1 SURF特征提取

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

因?yàn)樵诜e分時(shí)只需要遍歷一次原始圖像即可，計(jì)算積分圖像時(shí)它的運(yùn)算非常小。假如矩形由A、B、C和D四個(gè)頂點(diǎn)構(gòu)成，則矩形的窗口內(nèi)的總灰度為Σ=A－B C+D。

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

式中:參數(shù)ω是一個(gè)調(diào)節(jié)參數(shù)，用于平衡Hessian行列式表達(dá)式，計(jì)算如下

由H矩陣的特征值得到判別式的值，在判定結(jié)果的基礎(chǔ)上將所有的點(diǎn)進(jìn)行分類，根據(jù)判別式取值判斷是否是極值點(diǎn)。然后將低于預(yù)先設(shè)定極值的取值丟棄，實(shí)現(xiàn)特征點(diǎn)精確定位，通過增加極值以減少特征點(diǎn)數(shù)，最后留下最強(qiáng)的特征點(diǎn)。

1.2 特征點(diǎn)的匹配

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

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

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

1.3 計(jì)算感興趣的區(qū)域

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

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

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

2 RANSAC算法

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

3 判決準(zhǔn)則

3.1 匹配點(diǎn)對的過濾

本文對SURF算法所得到的匹配點(diǎn)對進(jìn)行排序，得到匹配最多的特征點(diǎn)對可能是視頻幀中的臺(tái)標(biāo)，所以需要設(shè)定對應(yīng)的判決標(biāo)準(zhǔn)。在用SURF進(jìn)行特征點(diǎn)配對時(shí)，根據(jù)1.2節(jié)中設(shè)定的系數(shù)a來判斷點(diǎn)對是否匹配成功。本文在實(shí)驗(yàn)中遇到多個(gè)特征點(diǎn)對應(yīng)一個(gè)特征點(diǎn)的情況(如圖1所示)，如果沒有進(jìn)行透視轉(zhuǎn)換關(guān)系，下文中提到的匹配率有可能大于1，這對于正確的臺(tái)標(biāo)匹配是不合理的。

因此單純地將SURF提取的特征點(diǎn)進(jìn)行匹配得到的對數(shù)作為臺(tái)標(biāo)的排序是不合理的，所以很有必要使用RANSAC隨機(jī)抽樣方法來計(jì)算預(yù)匹配點(diǎn)對之間的透視變換關(guān)系。為提高匹配的正確率，首先必須實(shí)現(xiàn)臺(tái)標(biāo)的正確定位。因此本文首先用SURF提取臺(tái)標(biāo)的特征點(diǎn)與臺(tái)標(biāo)庫中的臺(tái)標(biāo)特征點(diǎn)進(jìn)行預(yù)匹配，然后進(jìn)行透視變換去除錯(cuò)誤的點(diǎn)對，濾除后的點(diǎn)對作為它的最終匹配點(diǎn)對數(shù)，將點(diǎn)對進(jìn)行排序得到最多對數(shù)，計(jì)算出匹配率再與設(shè)定的閾值比較，最后得出它的識別結(jié)果。

圖1 點(diǎn)對過濾效果圖(截圖)

3.2 匹配率

對于臺(tái)標(biāo)的特征點(diǎn)參差不一的情況，無法通過設(shè)定對數(shù)閾值來判斷是否匹配成功，所以可以用一個(gè)比值來表達(dá)相同的含義，于是引入了匹配率。本文定義匹配率T為

式中:C表示經(jīng)過RANSAC算法后得到的匹配成功最多的對數(shù);Stemp表示在待識別臺(tái)標(biāo)中提取的特征點(diǎn)數(shù);T表示臺(tái)標(biāo)中匹配成功最多的對數(shù)與待測臺(tái)標(biāo)特征點(diǎn)數(shù)的比值。

4 算法的流程描述

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

圖2 實(shí)驗(yàn)流程圖

5 實(shí)驗(yàn)結(jié)果與分析

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

表1為實(shí)驗(yàn)中用透視變換關(guān)系與不用透視變換關(guān)系得到的統(tǒng)計(jì)識別率情況。經(jīng)過多次實(shí)驗(yàn)得到當(dāng)設(shè)定的最近距離與次近距離的比例因子a為0.6、匹配率的閾值T為0.13時(shí)識別率最高。識別率的統(tǒng)計(jì)方法為

表1 實(shí)驗(yàn)中臺(tái)標(biāo)識別結(jié)果

匹配率T是臺(tái)標(biāo)識別的判斷標(biāo)準(zhǔn)，它的大小會(huì)直接影響著臺(tái)標(biāo)識別的結(jié)果。據(jù)實(shí)驗(yàn)統(tǒng)計(jì)，匹配率T的值對正確識別率的影響關(guān)系如圖3所示，可以看出當(dāng)T=0.13左右時(shí)，識別的正確率最高。

圖3 T值對識別結(jié)果的影響

圖4為部分實(shí)驗(yàn)結(jié)果，其中圖4a～圖4e為正確識別出的臺(tái)標(biāo)，圖4f為臺(tái)標(biāo)庫中未存檔的臺(tái)標(biāo)，圖4g、圖4h為未識別出。

圖4 部分臺(tái)標(biāo)匹配的結(jié)果(截圖)

由表2知，將本文使用的識別方法與常用的模板匹配的方法進(jìn)行比較，可以看出對于透明的臺(tái)標(biāo)，本文使用的方法比模板匹配的識別率要高。另外用本文的方法可以保證旋轉(zhuǎn)不變和尺度不變的優(yōu)點(diǎn)。而模板匹配則沒有這個(gè)優(yōu)點(diǎn)。

本文只提取感興趣區(qū)域的特征點(diǎn)以提高識別速度。為更充分說明這點(diǎn)，本文分別在使用ROI與不使用ROI的情況下，統(tǒng)計(jì)了部分臺(tái)標(biāo)在識別過程所消耗的時(shí)間，表3是兩種情況下每個(gè)臺(tái)標(biāo)與一個(gè)視頻幀匹配所消耗的時(shí)間。先計(jì)算感興趣區(qū)域，在很大程度上減少了臺(tái)標(biāo)識別所用時(shí)間。

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

表3 部分臺(tái)標(biāo)識別所消耗的時(shí)間 ms

6 結(jié)論

本文提出一種基于SURF算法與RANSAC算法相結(jié)合的臺(tái)標(biāo)檢測與識別，首先對視頻幀中感興趣區(qū)域用SURF算法提取特征點(diǎn)，并與臺(tái)標(biāo)庫中的特征點(diǎn)進(jìn)行預(yù)匹配，再利用RANSAC算法對匹配的特征點(diǎn)對過濾，得到最后的匹配點(diǎn)對。實(shí)驗(yàn)取得了令人滿意的正確率，較好地實(shí)現(xiàn)了視頻幀中的臺(tái)標(biāo)檢測與識別。實(shí)驗(yàn)表明本文算法對標(biāo)在識別率以及識別速度上都取得了很好的效果。

:

［1］張重德.電視信號自動(dòng)檢測與報(bào)警系統(tǒng)［D］.合肥:合肥工業(yè)大學(xué)，2008.

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

［3］王振海.融合HU不變矩和SIFT特征的商標(biāo)檢索［J］.計(jì)算機(jī)工程與應(yīng)用，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］郭振成，梁鳳梅.一種改進(jìn)的SIFT特征點(diǎn)匹配算法［J］.電視技術(shù)，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］張鵬雁，趙耀，朱振峰.基于商標(biāo)匹配的視頻廣告識別［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］侯勝偉，何小海，滕奇志.臺(tái)標(biāo)的自動(dòng)檢測與識別［J］.四川大學(xué)學(xué)報(bào):自然科學(xué)版，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.