基于改進Chamfer匹配的臺標識別

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

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

1 概述

電視機視頻中的臺標是標識該電視臺臺名、節目取義的重要信息。臺標識別是基于內容的視頻圖像分析、檢索領域[1]的熱門研究方向之一。臺標正確識別的首要前提是臺標的正確分類，目前大陸電視臺臺標主要分為3類：

(1)靜態不透明臺標，像湖南衛視、江蘇衛視等大部分頻道。

(2)靜態半透明臺標，以中央電視臺為典型代表。

(3)極少數的動態臺標，本文不考慮此類臺標。

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

2 臺標識別分析

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

采用加權疊加平均法結合自適應閾值法[6]分割湖南衛視頻道的一段視頻，處理結果如圖1所示。

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

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

3 本文方法原理

3.1 方法分析

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

圖2 臺標識別方法框架

3.2 Chamfer匹配原理

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

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

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

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

其中，x為模板在目標圖上的偏移量。

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

3.3 本文匹配原理

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

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

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

同理計算上面的式子也可以通過圖像 E的距離變換來實現：

顯然，臺標匹配的位置越精確，Ci、Fi越小；反之越大。圖3為CGCM計算原理。

圖3 CGCM計算原理

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

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

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

3.4 臺標邊緣梯度方向和顏色的提取

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

圖5 Canny算子提取的臺標模板邊緣

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

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

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

3.5 臺標識別

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

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

圖6 復雜背景下2種方法的仿真結果對比

從圖6可以看出，對于復雜背景下，由于丟失了顏色信息和邊緣方向，因此傳統Chamfer匹配方法會出現明顯誤判。

4 實驗結果與分析

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

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

圖7 臺標識別結果

表1 部分頻道在線測試結果

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

5 結束語

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

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

[2]史迎春, 周獻中, 方鵬飛.綜合利用形狀和顏色特征的臺標識別[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]周獻中, 史迎春, 王 韜.基于 HSV 顏色空間加權 Hu不變矩的臺標識別[J].南京理工大學學報, 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]管偉光, 馬頌德.統一化的快速距離變換[J].計算機學報, 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.