胡星火，姚劍敏，林志賢，郭太良

(福州大學(xué)物理與信息工程學(xué)院，福州 350002)

1 概述

電視機(jī)視頻中的臺標(biāo)是標(biāo)識該電視臺臺名、節(jié)目取義的重要信息。臺標(biāo)識別是基于內(nèi)容的視頻圖像分析、檢索領(lǐng)域[1]的熱門研究方向之一。臺標(biāo)正確識別的首要前提是臺標(biāo)的正確分類，目前大陸電視臺臺標(biāo)主要分為3類：

(1)靜態(tài)不透明臺標(biāo)，像湖南衛(wèi)視、江蘇衛(wèi)視等大部分頻道。

(2)靜態(tài)半透明臺標(biāo)，以中央電視臺為典型代表。

(3)極少數(shù)的動(dòng)態(tài)臺標(biāo)，本文不考慮此類臺標(biāo)。

臺標(biāo)識別主要包括2個(gè)方面的內(nèi)容：臺標(biāo)的檢測，臺標(biāo)的特征的提取和識別。目前，國內(nèi)外已有的技術(shù)多是基于視頻流作幀間差[2]和視頻流加權(quán)疊加求平均[3]方法來分割臺標(biāo)。該原理只對靜態(tài)不透明臺標(biāo)成立，對半透明臺標(biāo)則不成立。另外，基于視頻流的方法不能實(shí)現(xiàn)臺標(biāo)的實(shí)時(shí)檢測識別。因此，本文提出一種基于改進(jìn)Chamfer匹配的臺標(biāo)識別方法。

2 臺標(biāo)識別分析

臺標(biāo)識別的關(guān)鍵在于臺標(biāo)的檢測分割，傳統(tǒng)視頻流法主要利用臺標(biāo)的時(shí)空不變性，即臺標(biāo)區(qū)域的像素值穩(wěn)定不變，非臺標(biāo)區(qū)域像素值發(fā)生均勻或者非均勻變化。顯然，該方法存在3個(gè)缺陷：(1)當(dāng)背景長時(shí)間不變或變化很小時(shí)，將不能分割出臺標(biāo)或分割效果不理想。(2)由于半透明臺標(biāo)區(qū)域的像素值會(huì)隨背景的變化而變化，因此對半透明臺標(biāo)識別效果不理想。(3)由于視頻流中相鄰幀圖像相似性極高，一般至少每隔 30幀抽取一幀做幀間差[4]或加權(quán)疊加[5]時(shí)算法才有效，因此實(shí)時(shí)性差。

采用加權(quán)疊加平均法結(jié)合自適應(yīng)閾值法[6]分割湖南衛(wèi)視頻道的一段視頻，處理結(jié)果如圖1所示。

從圖1可以看出，疊加的幀數(shù)越多，分割效果越好，但實(shí)時(shí)性越差，這在實(shí)際中是無法忍受的。

另外，許多電視臺在播放電影時(shí)，畫面的上邊沿會(huì)出現(xiàn)一個(gè)固定寬度的黑邊，此時(shí)，基于視頻流法無效。總的來說，視頻流法依賴于背景的變化，而本文方法不依賴背景，可實(shí)現(xiàn)單幀圖像識別。

3 本文方法原理

3.1 方法分析

當(dāng)視頻背景分布較均勻的時(shí)，Canny[7]算子提取的臺標(biāo)邊緣效果較好，而實(shí)際情況多為背景復(fù)雜，用Canny算子檢測出的臺標(biāo)邊緣存在大量的背景干擾邊緣。這種情況下，僅依靠臺標(biāo)邊緣信息，匹配的效果較差，也就是說單純使用形狀特征，丟失邊緣方向和顏色信息，容易誤判。為克服背景邊緣的干擾，本文采用融合臺標(biāo)邊緣梯度方向和顏色分量的Chamfer匹配[8-9]。該方法克服了視頻流作差或疊加時(shí)效性差的缺點(diǎn)，只需一幀包含臺標(biāo)的圖像，即可準(zhǔn)確的檢測并識別出臺標(biāo)，本文臺標(biāo)識別方法框架如圖2所示。其中，三角形為臺標(biāo)；圓形和正方形為假設(shè)的背景干擾邊緣；δ為距離閾值；CGCM(Color Gradient Chamfer Matching)。與傳統(tǒng)Chamfer匹配方法相比，本文方法魯棒性更好，適應(yīng)場所更廣泛。

圖2 臺標(biāo)識別方法框架

3.2 Chamfer匹配原理

本文方法的基礎(chǔ)是傳統(tǒng)Chamfer匹配方法，傳統(tǒng)方法通過計(jì)算2個(gè)輪廓距離的方法，來度量它們的相似性。這種方法在目標(biāo)發(fā)生小幅旋轉(zhuǎn)、畸變以及非對稱的情況下，仍能檢測出目標(biāo)物[10-11]，具有良好的魯棒性，其基本計(jì)算公式如下：

其中，T={ti}為模板圖像的邊緣點(diǎn)集合；|T|表示集合T的點(diǎn)數(shù)；E={ej}為目標(biāo)圖像的邊緣點(diǎn)集合；ti和 ej分別為T和E中的第i個(gè)、第j個(gè)邊緣點(diǎn)；dT(T,E)為模板 T中的邊緣點(diǎn)到圖像 E中最近像素點(diǎn)的平均距離；T和E 2個(gè)邊緣相似度越高，dT(T,E)的值將越小，當(dāng)T和E是完全相同的邊緣的話dT(T,E)=0。

而在實(shí)際情況當(dāng)中，dT(T,E)都是通過E的邊緣距離變換來計(jì)算的，E的距離變換公式如下：

那么dT(x)可以寫成下面的形式：

其中，x為模板在目標(biāo)圖上的偏移量。

若直接按照式(3)計(jì)算，dT(x)時(shí)間復(fù)雜度非常高。為了計(jì)算簡單，通常長采用所謂3-4法則[12-13]來近似歐氏距離用于計(jì)算，只需循環(huán)2次就可以完成距離變換的計(jì)算，大大加快計(jì)算速度，2次循環(huán)分別為：第1次是前向循環(huán)：從左至右，從上到下；第2次是反向循環(huán)：從右到左，從下到上；這樣形成的距離值與真實(shí)的歐氏距離值最大誤差是 8%。具體詳細(xì)過程可以參考文獻(xiàn)[12]。

3.3 本文匹配原理

廣播電視畫面復(fù)雜多變，且具有隨機(jī)性，使用Canny算子提取臺標(biāo)邊緣，通常不可避免會(huì)有背景邊緣的干擾；再者由于傳統(tǒng)Chamfer匹配方法自身的局限性，抗干擾能力較差，因此為了克服雜亂背景邊緣的干擾，本文對Chamfer匹配方法進(jìn)行了改進(jìn)，引入邊緣梯度方向θ和邊緣顏色分量c。

其中，ti和ei分別為臺標(biāo)模板T和目標(biāo)圖像E中的邊緣點(diǎn)；θ(ti)、θ(ei)邊緣點(diǎn)梯度方向；c(ti)、c(ei)為邊緣點(diǎn)顏色；α和β分別為邊緣梯度方向和顏色的權(quán)重。引進(jìn)方向分量α是為了克服非臺標(biāo)邊緣的干擾；引進(jìn)顏色分量β是為了區(qū)分形狀相似、顏色相異的臺標(biāo)。

綜合式(3)～式(8)得：

同理計(jì)算上面的式子也可以通過圖像 E的距離變換來實(shí)現(xiàn)：

顯然，臺標(biāo)匹配的位置越精確，Ci、Fi越??；反之越大。圖3為CGCM計(jì)算原理。

圖3 CGCM計(jì)算原理

模板T是由一序列邊緣點(diǎn)構(gòu)成的點(diǎn)集，因此，為了進(jìn)一步加快計(jì)算速度、節(jié)約存儲空間，本文使用RANSAC[13]算法對模板T的邊緣點(diǎn)進(jìn)行優(yōu)化，濾去一些雜點(diǎn)。設(shè)優(yōu)化前模板點(diǎn)集為T={ti}(i=1,2,…, N)，優(yōu)化擬合后點(diǎn)集可以表示為Tr={li[si,ei]}，(i=1,2,…,M)，其中，M遠(yuǎn)小于N；li表示集合T的第i個(gè)子集；si、ei分別表示子集li的起點(diǎn)和終點(diǎn)，子集里的點(diǎn)都具有相同的梯度方向θi，經(jīng)過優(yōu)化擬合后的點(diǎn)集可以節(jié)約存儲空間，顯著提高計(jì)算速度。RANSAC算法擬合邊緣圖本質(zhì)上是對邊緣梯度方向進(jìn)行量化。圖 4為RANSAC算法擬合前后的模板邊緣。

圖4 RANSAC算法擬合前后的模板邊緣

由此，式(10)最終可以改寫為：

3.4 臺標(biāo)邊緣梯度方向和顏色的提取

臺標(biāo)的形狀和顏色是臺標(biāo)最直觀的特征，現(xiàn)有的大部分臺標(biāo)都具有豐富的顏色和獨(dú)特的形狀。現(xiàn)有的形狀描述法主要有2種，即基于邊緣的形狀和基于區(qū)域的形狀，考慮到半透明臺標(biāo)顏色易受背景影響，因此，臺標(biāo)形狀不宜采用基于區(qū)域的形狀。通常，無論是不透明還是半透明臺標(biāo)，都會(huì)與背景形成鮮明的邊緣，且邊緣顏色比較穩(wěn)定。一般情況下，臺標(biāo)總能與背景形成清晰可見的邊緣，臺標(biāo)邊緣檢測的好壞直接影響到臺標(biāo)的檢測識別；Canny算子是目前邊緣檢測方法中最好的，具有良好的信噪比和檢測精度；因此，本文利用Canny算子提取邊緣梯度方向θ和邊緣顏色分量c，Canny算子提取的臺標(biāo)模板邊緣如圖5所示。

圖5 Canny算子提取的臺標(biāo)模板邊緣

關(guān)于邊緣顏色特征提取的方法很多，常用的方法有顏色直方圖、顏色統(tǒng)計(jì)矩、顏色信息熵等方法。在實(shí)際中，往往都是針對不同場所采用不同的方法。臺標(biāo)的邊緣是與背景形成的，由于視頻背景的隨機(jī)變法特點(diǎn)以及視頻噪聲等，每次形成的臺標(biāo)邊緣會(huì)有一些差異，因此對臺標(biāo)邊緣顏色特征提取方法不宜過于精細(xì)，過于精細(xì)不僅計(jì)算復(fù)雜，且存儲空間迅速膨脹，對噪聲特別敏感。

基于以上因素考慮，本文采用常用的色度、飽和度、純度(Hue Saturation Value, HSV)顏色空間對臺標(biāo)邊緣分量c非均勻量化，具體量化過程參考文獻(xiàn)[14]，不再贅述。

色度H量化分為8個(gè)相似區(qū)間：[316,20]，[21,40]，[41,75]，[76,155]，[156,190]，[191,270]，[271,295]，[296,315]；飽和度 S量化為 3個(gè)區(qū)間：[0,0.2]，[0.2,0.7]，[0.7,1]；對純度V量化為2個(gè)區(qū)間：[0,0.2]，[0.2,1]。

3.5 臺標(biāo)識別

臺標(biāo)識別就是在臺標(biāo)邊緣特征提取的基礎(chǔ)上，所進(jìn)行的特征匹配。其過程為：首先，建立標(biāo)準(zhǔn)的臺標(biāo)模板庫，臺標(biāo)模板是通過軟件和必要的手動(dòng)修改完成的。臺標(biāo)的相似性度量是采用改進(jìn)型的Chamfer匹配距離度量，類似于歐氏距離最小準(zhǔn)則，本文稱作CGCM 距離最短準(zhǔn)則。dTr(Tr,E)(x(θ,c))越小，匹配度越高。本文采用多次識別的方法，即統(tǒng)計(jì)概率最大準(zhǔn)則來提高識別精度。方法是對多幀進(jìn)行臺標(biāo)識別，若某一臺標(biāo)被選的次數(shù)超過總識別次數(shù)的 60%(包含60%)，則認(rèn)為該臺標(biāo)為最終識別的結(jié)果。

如圖 6所示為復(fù)雜背景下本文方法和 Chamfer匹配方法仿真結(jié)果對比。

圖6 復(fù)雜背景下2種方法的仿真結(jié)果對比

從圖6可以看出，對于復(fù)雜背景下，由于丟失了顏色信息和邊緣方向，因此傳統(tǒng)Chamfer匹配方法會(huì)出現(xiàn)明顯誤判。

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

本文實(shí)驗(yàn)的硬件平臺是Intel(R) Core(TM)2 Quad CPU Q83 00、華為公司的InfoLink C2510有線數(shù)字機(jī)頂盒、同三維公司的T650E視頻采集卡、軟件平臺為Windows XP操作系統(tǒng)、微軟VS2008、Open-CV2.0，臺標(biāo)庫的臺標(biāo)數(shù)為77。

根據(jù)經(jīng)驗(yàn)，大陸電視臺標(biāo)一般都在電視臺的左上角，因此，為了節(jié)省搜索時(shí)間，每次只搜索視頻畫面左上角部分大小為(640/3)×(480/4)的部分，即占整個(gè)視頻畫面的 1/12大小。本文在識別時(shí)間和識別精度上做了折中，即對每個(gè)電視臺識別10次，如果6次識別正確，即表示最終識別結(jié)果正確。實(shí)驗(yàn)方式為在線對每一個(gè)頻道不間斷測試 3 h，臺標(biāo)識別結(jié)果如圖7所示，表1為部分頻道在線測試結(jié)果。

圖7 臺標(biāo)識別結(jié)果

表1 部分頻道在線測試結(jié)果

本文方法實(shí)現(xiàn)了單幀識別，不依賴于連續(xù)變化的視頻流，因此，基本滿足實(shí)時(shí)檢測識別，由表1可知，平均識別時(shí)間為801 ms，平均識別率為97.7%。

5 結(jié)束語

綜合分析臺標(biāo)特征，本文提出一種基于改進(jìn)Chamfer匹配的臺標(biāo)識別方法。該方法不依賴于背景視頻的連續(xù)變化，能實(shí)現(xiàn)單幀圖像的臺標(biāo)實(shí)時(shí)檢測，具有較好的魯棒性，能夠滿足國內(nèi)主要電視臺臺標(biāo)的識別。然而隨著臺標(biāo)庫中臺標(biāo)數(shù)量的增加，匹配時(shí)間會(huì)越來越長，且其還無法對動(dòng)態(tài)臺標(biāo)進(jìn)行識別，因此，今后將繼續(xù)研究如何提高計(jì)算速度和匹配精度。

[1]胡振興, 夏利民.基于視頻片段的視頻檢索[J].中南大學(xué)學(xué)報(bào): 自然科學(xué)版, 2010, 14(3): 1010-1014.

[2]史迎春, 周獻(xiàn)中, 方鵬飛.綜合利用形狀和顏色特征的臺標(biāo)識別[J].人工智能與模式識別, 2005, 18(2): 216-222.

[3]Albiol A, Fulla M J, Albiol A, et al.Detection of TV Commercials[C]//Proc.of the IEEE International Conference on Acoustics Speech, and Signal Processing.Montreal, Canada: [s.n.], 2004.

[4]周獻(xiàn)中, 史迎春, 王 韜.基于 HSV 顏色空間加權(quán) Hu不變矩的臺標(biāo)識別[J].南京理工大學(xué)學(xué)報(bào), 2005, 29(3):364-367.

[5]Chattopadhyay T, Aniruddha S, Arpan P, et al.Recognition of Channel Logos from Streamed Video for Value Added Services in Connected TV[C]//Proc.of IEEE International Conference on Consumer Electronics.Las Vegas, USA:[S.l.]: 2011.

[6]Ozay N, Sankur B.Automatic TV Logo Detection and Classification in Broadcast Videos[C]//Proc.of the 17th European Signal Processing Conference.Glasgow, UK:[s.n.], 2009.

[7]Canny J.A Computational Approach to Edge Detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, 8(6): 236-241.

[8]Gavrila D M, Daimler A G.Multi-feature Hierarchical Template Matching Using Distance Transforms[C]//Proc.of IEEE International Conference on Pattern Recognition.Brisbane, Austrila: [s.n.], 1998.

[9]Borgefors G.Distance Transformations in Arbitrary Dimensions[J].Computer Vision, Graphics, and Image Processing, 1984, 27(3): 321-345.

[10]Shotton J, Blake A, Cipolla R.Multi-scale Categorical Object Recognition Using Contour Fragments[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008, 30(7): 1270-1281.

[11]Belongie S, Malik J, Puzicha J.Shape Matching and Object Recognition Using Shape Contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4):509-522.

[12]管偉光, 馬頌德.統(tǒng)一化的快速距離變換[J].計(jì)算機(jī)學(xué)報(bào), 1995, 18(8): 625-635.

[13]Martin A F, Robert C B.Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communications of the ACM, 1981, 24(6): 381-395.

[14]王向陽, 陳景偉, 于永健.一種基于彩色邊緣綜合特征的圖像檢索算法[J].人工智能與模式識別, 2010, 23(2):216-221.