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

(1. 上海交通大學(xué) 自動(dòng)化系 系統(tǒng)控制與信息處理教育部重點(diǎn)實(shí)驗(yàn)室，上海200240;2. 上海東方娛樂(lè)傳媒集團(tuán) 廣告經(jīng)營(yíng)中心，上海200041)

0 引 言

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

圖1 某電視臺(tái)視頻截圖及角標(biāo)廣告

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

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

1 基于主方向模板的角標(biāo)檢測(cè)算法

1.1 主方向模板算法

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

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

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

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

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

1.2 角標(biāo)圖像檢測(cè)算法的思路

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

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

1.3 角標(biāo)圖像檢測(cè)算法

角標(biāo)圖像檢測(cè)算法的實(shí)現(xiàn)過(guò)程可以用圖2 的流程圖表示。

圖2 角標(biāo)廣告檢測(cè)算法框架

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

算法的處理步驟如下:

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

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

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

③對(duì)G(M)m×n作截?cái)嚅撝祷幚?

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

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

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

其中

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

1.4 算法復(fù)雜度分析

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

第(4)、(5)步的計(jì)算復(fù)雜度:

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

2 實(shí)例分析及討論

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

表1 改進(jìn)DOT、DOT 的查準(zhǔn)率比較 %

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

3 結(jié) 語(yǔ)

視頻中的圖像檢測(cè)作為一個(gè)新興的研究領(lǐng)域，正受到人們?cè)絹?lái)越多的關(guān)注。本文針對(duì)角標(biāo)廣告的檢測(cè)問(wèn)題，提出了一種新穎的基于主方向模板的角標(biāo)廣告檢測(cè)算法。該算法以主方向模板為基礎(chǔ)，利用反映角標(biāo)形狀的匹配模板和加權(quán)模板有效抑制了復(fù)雜背景的干擾。通過(guò)大量的實(shí)例運(yùn)行表明了算法的適應(yīng)性、準(zhǔn)確性和實(shí)時(shí)性。本文算法為復(fù)雜圖像的檢測(cè)提供了一種解決方法，在相關(guān)應(yīng)用領(lǐng)域具有一定的推廣應(yīng)用價(jià)值。

［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］ 郭 麗，孫興華，黃元元，等.距離分布直方圖及其在商標(biāo)圖案檢索中的應(yīng)用［J］. 中國(guó)圖象圖形學(xué)報(bào)(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 特征的商標(biāo)檢索算法［J］. 計(jì)算機(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］ 孫 林，吳相林，周 莉，等. 對(duì)扭轉(zhuǎn)魯棒的SIFT 圖像匹配在商標(biāo)識(shí)別中的應(yīng)用［J］. 計(jì)算機(jī)工程與設(shè)計(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］ 洪朝群，朱建科，李 娜，等. 金字塔評(píng)分改進(jìn)主方向模板匹配的實(shí)時(shí)目標(biāo)檢索［J］. 中國(guó)圖像圖形學(xué)報(bào)，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］ 卜 江，老松楊，白 亮，等. 一種體育視頻中廣告牌商標(biāo)的實(shí)時(shí)識(shí)別算法［J］. 自動(dòng)化學(xué)報(bào)，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.