基于主方向模板的視頻中角標廣告檢測算法

徐 聰， 杜秀華， 曹雪昭， 曹 俊

(1. 上海交通大學 自動化系 系統(tǒng)控制與信息處理教育部重點實驗室，上海200240;2. 上海東方娛樂傳媒集團 廣告經營中心，上海200041)

0 引 言

電視節(jié)目中的角標廣告是一種新穎的廣告形式，它通過在視頻內容的邊緣位置播放特定的圖標，以實現(xiàn)為企業(yè)或組織提供廣告宣傳的目的，圖1 為某電視臺包含角標廣告的視頻截圖。角標廣告形式多樣，圖標形狀或不規(guī)則，或鏤空等有不同的外形特點，對角標廣告的檢測是用圖像處理和識別方法自動檢測視頻中角標廣告的時長和位置。

圖1 某電視臺視頻截圖及角標廣告

角標廣告的檢測問題比較新，但對角標的檢測算法可借鑒基于內容的視頻檢索［1］(CBOR)的已有成果。CBOR 中的圖像識別算法可分為基于全局特征的方法和基于局部特征的方法。基于全局特征的方法如利用距離分布直方圖［2］或基于輪廓的距離變換［3］等實現(xiàn)圖像的檢索，但這些方法均因速度較慢、魯棒性不強，或是缺乏準確性而難以用于實際的視頻檢索。而基于局部特征的算法，如SIFT［4-6］、SURF［7］，這類算法所基于的特征點與描述子通常很穩(wěn)定，但是特征向量的提取以及匹配都非常依賴于局部區(qū)域像素的梯度方向，描述子方向的不準確會造成特征匹配的誤差放大，而且檢索的效率也依賴于特征點的數(shù)量。

模板匹配方法［8］一般使用全局特征，它的優(yōu)點在于可方便添加不同的模板，定位過程比較簡單。但是，由于模板遍歷的計算復雜度較高，因此在視頻檢索中的應用受到了限制。Hinterstoisser 等提出了主方向模板(Dominant Orientation Template，DOT)算法，加快了模板特征的提取和匹配速度［9］，使模板匹配方法受到了新的關注。DOT 借鑒了HOG［10］算法，將目標圖像分割為網(wǎng)格，定義“主梯度方向”對圖像特征進行壓縮，并對主梯度方向采用位編碼法大幅度降低了特征提取和匹配的計算復雜度，在圖像匹配的魯棒性上也顯示了較好的性能。但是DOT 也存在不少局限，它以搜索窗口的全局得分作為檢索窗口是否存在目標圖像的標準，對于存在鏤空、不規(guī)則形狀的圖像，這種簡單的處理方式會造成錯檢與漏檢。本文針對角標圖像的多樣性的需求特點，以DOT 為基礎，提出了一般角標的檢測算法，在保證實時處理能力的前提下提高了檢測率，達到了角標廣告的檢測要求。

1 基于主方向模板的角標檢測算法

1.1 主方向模板算法

DOT 算法［9］是一種基于全局特征的模板匹配算法，該算法將目標圖像分割為網(wǎng)格并采用主梯度方向作為特征。

(1)特征提取過程。該算法依次對每個網(wǎng)格的梯度進行統(tǒng)計，將網(wǎng)格內最大的k 個梯度所對應的方向量化到n0個方向域，并用一個n0+1 位整型保存。其中低n0位對應每一個方向域，若主梯度方向落入此域內則相應位置1;若網(wǎng)格內最大的k 個梯度都小于給定閾值時，則將最高位置1(表明網(wǎng)格過于平滑)。這種處理方式對圖像的特征進行了充分的壓縮，大幅度降低了特征提取與匹配的復雜度。

(2)算法的匹配過程。定義相似性度量函數(shù)(Similarity Measure Function)［9］如下，該函數(shù)具有良好的魯棒性，并返回輸入圖像當前窗口模板與目標圖像模板兩者之間對應網(wǎng)格的匹配結果。

式中:δ(P)是二值函數(shù)，P 為真時返回1，為假時則返回0;O、I 分別代表目標圖像(Object Image)和輸入圖像(Input Image);do(I，c +R)為返回的是輸入圖像I位于位置c 處的網(wǎng)格R 中值最大的梯度;DO(w(O，M)，R)為返回目標圖像的網(wǎng)格R 中較大值梯度的集合;w(O，m)為使目標圖像O 對小尺度平移魯棒的處理;M 表示處理范圍，大小為［－t/2，t/2］2。

目標檢測過程中，對輸入圖像以對應目標圖像大小的窗口進行遍歷，并獲取當前窗口的主方向模板，根據(jù)式(1)依次對當前窗口圖像與目標圖像的主方向模板的對應網(wǎng)格進行匹配，最終返回一個搜索窗口的全局得分并與給定閾值比較，以此作為評價該窗口是否存在檢測目標的標準。分別記目標圖像與窗口圖像對應網(wǎng)格的主梯度方向值為L 和D，上述的匹配過程［9］可以概括為

1.2 角標圖像檢測算法的思路

對于一幅常規(guī)的待檢測角標圖像，通常由角標部分與背景部分組成，如圖1 所示。設角標圖像對應的主方向模板為T(O)m×n=(oij)m×n(1≤i≤m，1≤j≤n)，輸入圖像當前窗口的主方向模板為T(I)m×n=(iij)m×n。其中，oij代表第i 行、j 列的網(wǎng)格所表示的主梯度方向。根據(jù)“位與”原則，如果僅希望角標部分參與運算，那么只需要將背景部分的數(shù)據(jù)清零，而角標部分的數(shù)據(jù)保持不變即可，即:

此外，DOT 算法簡單采用每個網(wǎng)格的貢獻對搜索窗口的全局得分相同，這種方法簡單易行但易混入錯誤匹配的窗口。對于角標圖像而言，角標部分的邊緣網(wǎng)格得分非常敏感，很容易受到頻繁變換背景的干擾。為了抑制這種干擾，本文采用加權模板為每個網(wǎng)格分配得分權重，通過弱化角標部分邊緣網(wǎng)格的得分從而在一定程度上降低其可能造成的誤匹配。

1.3 角標圖像檢測算法

角標圖像檢測算法的實現(xiàn)過程可以用圖2 的流程圖表示。

圖2 角標廣告檢測算法框架

具體算法描述如下，定義視頻幀當前窗口的主方向模板為T (I)m×n，目標圖像的主方向模板為T(O)m×n，匹 配 模 板 為 T (M)m×n，加 權 模 板 為G(M)m×n，窗口全局得分為Ws，匹配模板屏蔽網(wǎng)格數(shù)為b，匹配率

算法的處理步驟如下:

(1)根據(jù)目標圖像初始化匹配模板T(M)m×n，其中待屏蔽網(wǎng)格值設為0，剩余網(wǎng)格值設為并按照T(M)m×n依次生成不同尺度下的T(M')m×n。

(2)根據(jù)T(M')m×n生成當前尺度下的加權模板G(M')m×n。G(M')m×n的初始化過程如下:

①對當前尺度下的匹配模板進行T(M')m×n4－N距離變換［11］，生成G(M)m×n。

③對G(M)m×n作截斷閾值化處理:

④為保持變換后全局總得分不變，令g'(i，j)=kg(i，j)，其中，

(3)讀入輸入圖像I 和目標圖像O，按照提取兩幅圖像的主方向模板特征，得到T(I)m×n與T(O)m×n。

(4)將T(M)m×n分別與T(I)m×n、T(O)m×n作“與”操作后，后述兩者再作“與”操作，并將返回的模板與加權模板相卷積，得到當前窗口的全局得分Ws。根據(jù)之前定義的匹配率公式可以得到兩者的匹配率為:

其中

(5)設遍歷輸入圖像后存在匹配率滿足閾值的窗口，則標記對應窗口所在的位置，并讀取下一幀圖像并返回(3)。

1.4 算法復雜度分析

設輸入圖像大小為U ×V，目標圖像大小為M ×N，網(wǎng)格大小為r×r。算法第(1)、(2)步的計算復雜度是O(MN)，而主要的計算量在第(3)～(5)步，第(3)步的計算復雜度為:

第(4)、(5)步的計算復雜度:

在本文大多數(shù)的實例測試中，目標圖像大小MN＜104，該情況下算法計算復雜度正比于O(UV)，通過SSE2 指令集對數(shù)據(jù)并行處理后，能達到對目標圖像的實時檢測。

2 實例分析及討論

本文對DOT 算法與本文提出的改進DOT 算法在CPU:Intel i5 處理器(2.4 GHz)、RAM:4 GB、Visual C+ +2008、OpenCV2.3 的環(huán)境下進行了實現(xiàn)。以某電視臺的實際視頻進行了大量的實驗，這里列選了7 種角標廣告的檢測查準率如表1 所示，其中加權因子q=2;改進后算法的每幀平均運算時間為22.1 ms，原DOT 算法為18.2 ms。

表1 改進DOT、DOT 的查準率比較 %

表中的實驗數(shù)據(jù)表明，改進算法的查準率始終大于原DOT 算法。當角標廣告背景復雜時，改進算法的檢測效果明顯優(yōu)于原DOT 算法，可以達到實際檢測精確度要求。但是改進算法運算時間略有增加，這主要是由于改進算法引入了匹配模板、加權模板而增加了計算量，但改進后的算法仍然能夠實現(xiàn)對目標圖像的實時檢測。

3 結 語

視頻中的圖像檢測作為一個新興的研究領域，正受到人們越來越多的關注。本文針對角標廣告的檢測問題，提出了一種新穎的基于主方向模板的角標廣告檢測算法。該算法以主方向模板為基礎，利用反映角標形狀的匹配模板和加權模板有效抑制了復雜背景的干擾。通過大量的實例運行表明了算法的適應性、準確性和實時性。本文算法為復雜圖像的檢測提供了一種解決方法，在相關應用領域具有一定的推廣應用價值。

［1］ Christoph H Lampert. Detecting objects in large image collections and videos by efficient subimage retrieval［C］//Proceedings of IEEE International Conference on Computer Vision. Kyoto:IEEE，2009:987-994.

［2］ 郭 麗，孫興華，黃元元，等.距離分布直方圖及其在商標圖案檢索中的應用［J］. 中國圖象圖形學報(A 卷)，2002，7(10):1027-1031.GUO Li，SUN Xing-hua，HUANG Yuan-yuan，et al. Distance Distribution Histogram and its Application in Trademark Image Retrieval［J］. Journal of Image and Graphics，2002，7A(10):1027-1031.

［3］ Olson C F，Huttenlocher D P. Automatic target recognition by matching oriented edge pixels［J］. IEEE Transactions on Image Processing，1997，66(1):103-113.

［4］ Lowe D. Distinctive Image Features from Scale-Invariant Keypoints［J］. International Journal of Computer Vision，2004，60(2):91-110.

［5］ 林傳力，趙宇明. 基于Sift 特征的商標檢索算法［J］. 計算機工程，2008，34(23):275-277.LIN Chuan-li，ZHAO Yu-ming. Trademark Retrieval Algorithm Based on Sift Feature［J］. Computer Engineering，2008，34(23):275-277.

［6］ 孫 林，吳相林，周 莉，等. 對扭轉魯棒的SIFT 圖像匹配在商標識別中的應用［J］. 計算機工程與設計，2011，32(4):1406-1410.SUN Lin，WU Xiang-lin，ZHOU Li，et al. Application of affine invariant SIFT matching for automatic logo recognition［J］. Computer Engineering and Design，2011，32(4):1406-1410.

［7］ Herbert Bay，Andreas Ess，Tinne Tuytelaars，et al. SURF:Speeded up Robust Features［J］. Computer Vision and Image Understanding，2008，110(3):346-359.

［8］ 洪朝群，朱建科，李 娜，等. 金字塔評分改進主方向模板匹配的實時目標檢索［J］. 中國圖像圖形學報，2012，17(5):700-706.HONG Chao-qun，ZHU Jian-ke，LI Na，et al. Real-time object retrieval with dominant orientation template matching improved by pyramid scoring［J］. Journal of Image and Graphics，2012，17(5):700-706.

［9］ Hinterstoisser S，Lepetit V，Ilic S，et al. Dominant Orientation Temp-lates for Real-Time Detection of Texture-Less Object［C］//IEEE Conference on Computer Vision and Pattern Recognition. New York:IEEE，2010:2257-2264.

［10］ Dalal N，Triggs B. Histograms of Oriented Gradients for Human Detection［C］//International Conference on Computer Vision and Pattern Recognition. New York:IEEE，2005:886-893.

［11］ Borgefors G. Distance Transformation in digital images［J］.Computer Vision，Graph-ics，and Image Processing，1986，34(3):344-371.

［12］ Lampert C H，Blaschko H，Hofmann T. Efficient Subwindow Search:A Branch and Bound Framework for Object Localization［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(12):2129-2142.

［13］ Lu C Y，Roh M C，Kang S Y，et al. Automatic logo transition detection in digital video contents［J］. Pattern Analysis and Applications，2012，15(2):175-187.

［14］ Arafat S Y，Husain S A，Niaz I A，et al. Logo detection and recognition in video stream［C］//2010 Fifth International Conference on Digital Information Management. Thunder Bay:IEEE，2010:163-168.

［15］ 卜 江，老松楊，白 亮，等. 一種體育視頻中廣告牌商標的實時識別算法［J］. 自動化學報，2011，37(4):418-426.BU Jiang，LAO Song-yang，BAI Liang，et al. A Real-time Billboard Trademark Recognition Algorithm in Sports Video［J］. Acta Automatica Sinica，2011，37(4):418-426.