基于判別力分析和結構約束的Logo檢測方法

收稿日期：2013-05-02

基金項目：國家自然科學基金重點項目（61133003）；國家自然科學基金面上項目（61071180）。

作者簡介：許鵬飛（1982-），男，內蒙古興安盟人，博士研究生，主要研究方向：圖像檢索、多媒體處理、圖像特征表達；

姚鴻勛（1965-），女，浙江杭州人，博士，教授，博士生導師，主要研究方向：計算機視覺、多媒體計算、人機交互等。

基于判別力分析和結構約束的Logo檢測方法

許鵬飛， 姚鴻勛（哈爾濱工業大學 計算機科學與技術學院，哈爾濱 150001）摘要：圖像中的Logo檢測對于分析圖像的內容、進行品牌廣告投放和廣告推薦具有重要的意義。針對現有的Logo檢測方法存在的準確率低、處理速度慢的問題，提出了基于特征判別力分析和結構約束的Logo檢測方法。首先，提出了基于出現頻率的判別力分析方法；其次，提出了基于特征之間相對距離、相對主方向和相對尺度的結構關系表示方法，并構建出Logo表示模型；最后，提出了由粗到精的Logo檢測方法，采用視覺單詞判別力分析獲得候選區域，并采用結構關系來進行精確匹配，確定最終的Logo區域。在一個包含100種Logo的10，000張圖像的Logo數據集上的Logo檢測實驗中表明，所提出的方法在準確率、召回率和處理速度上均明顯優于當前主流的Logo檢測方法，證明了所提出方法的有效性和高效性。

關鍵詞：Logo檢測； 特征表達； 判別力分析； 結構約束

中圖分類號：TP391 文獻標識碼：A文章編號：2095-2163（2013）04-0047-04

A Discrimination Analysis and Structure Constraint based Logo Detection Method

XU Pengfei， YAO Hongxun

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract：Logo detection in images is useful to image understanding， advertisement embedding and recommendation. Existing Logo detection methods suffer the problems of low accuracy and low processing speed. To address the problems， this paper proposes a visual word discrimination analysis and structure constraint based Logo detection method. First， this paper presents a frequency based discriminative power analysis method. Second， with analysis of the relative distance， relative principle orientation and relative scale of two local features， this paper proposes a structure based representation， and combines the discriminative visual words and structure constrain to build a Logo representation model. Finally， this paper presents a coarse-to-fine framework for efficiently detecting the logo region in images. A Logo detection experiments on a 10，000 images （100 Logo types） dataset is conducted， and the proposed method outperforms the state-of-the-art methods in terms of precision， recall and processing speed， which demonstrates the effectiveness and efficiency of the proposed method.

Key words：Logo Detection； Feature Representation； Discrimination Analysis； Structure Constraint

0引言

Logo通常意指某商品、企業或組織結構的標志圖形和圖像。圖像和視頻中的Logo檢測會帶來許多潛在的應用，如根據圖像或視頻中的Logo進行廣告投放，通過Logo輔助分析和理解圖像與視頻的內容[1]，通過對車輛的Logo識別來有效管理車輛等。

本文將以圖像中的Logo檢測為研究點，對指定圖像中是否包含給定集合中的Logo快速、準確地做出判斷，如包含，則對圖像中Logo所在的位置實現準確定位并標示Logo的名稱。圖像拍攝條件的變化會給Logo檢測帶來一定的執行難度，具體可表現為部分區域的遮擋、噪聲干擾、光照變化和拍攝視角變化等。

針對如上討論，研究者們提出了多種方法進行圖像中的Logo檢測。根據其采用特征的不同，現有方法可分為基于全局特征的方法和基于局部特征的方法。

基于全局特征的方法主要是采用全局特征來描述Logo，并與待檢測圖像中的特征進行對比，確定Logo的位置及其類型[2-5]。基于輪廓特征的方法[2]是采用輪廓模板來描述Logo，并與由待檢測圖像中提取的輪廓區域進行對比，而定位得出Logo的位置。Jain等人采用邊緣方向直方圖和不變性矩特征來匹配Logo模板并定位Logo[3]。在文獻[4]中，顯著的邊緣集合用來分析和比較Logo的表觀信息。文獻[5]則采用顏色直方圖來檢測候選Logo區域，并使用多維感受直方圖來進一步提高檢測的性能。

基于局部特征的方法使用圖像的局部特征（如，SIFT特征[6]）描述Logo的表觀性狀，并與待檢測圖像中的局部特征進行對比，由此定位得到圖像中Logo位置[7-10]。LogoSeeker[7]是比較典型的基于局部特征的Logo檢測方法，通過采用SIFT特征來描述Logo信息，并與待檢測圖像中提取的SIFT特征集合進行對比，獲得候選Logo區域，再進一步采用基于特征密度的方法來提高檢測的準確性。Bagdanov等[8]提出了基于壓縮局部特征包模型的方法來檢測和檢索運動視頻中的Logo區域。Ballan等[9]又提出了基于SIFT特征包的半自動的Logo檢測方法。而在文獻[10]中，基于空間金字塔挖掘的方法則是利用局部特征形成的空間共生來完成Logo的定位。

現有的方法中，基于全局特征的方法具有表達簡單、處理高效等特點，但該類方法卻常常容易受到噪聲干擾、遮擋等因素的影響而限制了其性能的提高。基于局部特征的方法所采用的局部特征能夠克服拍攝條件變化的影響，而取得了當前文獻中可見的最優性能[7]。然而，現有的方法中，仍然存在如下兩個問題：

（1）一個圖像中的局部特征數量可多達幾千（甚至上萬），就使得在特征匹配時，將具有較高的計算復雜度，而限制了當前算法速度的提高；

（2）在使用局部特征進行表達時，特征之間的結構關系將被忽略，因而妨礙了其準確率的進一步提高，雖然已經提出了基于空間共生的方法，但卻僅僅考慮了特征的空間位置關系，而其他的結構信息，如尺度相關性和方向相關性等均未做以有效考量。第4期許鵬飛，等：基于判別力分析和結構約束的Logo檢測方法智能計算機與應用第3卷

為了解決上述問題，本文提出了特征判別力分析和空間結構約束的快速Logo檢測方法，有效地利用了局部特征的判別力特性和特征之間的結構關系進行Logo描述和檢測，提高其準確率，并將其融入到由粗到精的檢測框架中，提高其處理速度。在模型構建階段，根據訓練樣本的分布，本文要分析不同的SIFT特征對于每一Logo類別的判別力的差異，使用每個類別中判別力高的SIFT特征來描述對應的Logo。同時，進一步利用特征之間的結構關系，如空間位置、尺度相關性、方向相關性等因素，來描述Logo中局部特征的結構信息。在檢測階段，首先根據從待檢測圖像中提取的特征與不同Logo類別的相關性，獲得候選Logo區域。進而，對每個候選區域中的局部特征的結構相似性進行理論推算，最終定位得出待檢圖像中的相關類型的Logo區域。

為了驗證所提出的方法的性能，本文在一個包含100種Logo的10 000張圖像的數據集上進行了仿真實驗。實驗結果表明，所提出的方法在準確率和處理速度上均明顯優于當前主流的方法，證明了所提出方法的有效性和高效性。

1基于特征判別力分析和空間約束的Logo模型

構建方法

本節首先進行SIFT特征判別力分析，進而介紹結構約束信息提取方法，最后介紹基于特征判別力和結構信息的Logo模型表達方法。

1.1特征判別力分析

給定訓練圖像集合S={Ii}Ni=1和圖像樣本的標注集合L={（Ij，rj，cj）}Mj=1，其中Ij∈S為訓練圖像，cj∈C為Logo的類別信息，而rj是類別為cj的Logo在圖像Ij中出現的位置（采用矩形框表示）。為了有效刻畫圖像的信息，并降低后續運算的復雜度，采用視覺單詞來表示SIFT特征。首先，提取訓練樣本集合中全部圖像的SIFT特征[6]，F={fk}Pk=1， fk=（pk，sk，θk），其中，pk、sk、θk分別為特征fk在對應圖像中的位置、尺度和主方向信息。其后采用k-means算法對全部的SIFT特征進行聚類，并針對每個SIFT特征歸屬不同的聚類類別的性質，使用視覺單詞的標號來表示對應的SIFT特征。

與tf-idf思想相類似，對某個類別的Logo判別力較高的視覺單詞，應該是在該類別的區域中出現的次數較多，而在其他類別的Logo中以及背景區域中出現的次數較少。在此，定義了視覺單詞vi相對于Logo的類別ck的判別力，其計算公式如下：

dVik=NikNi（1）

其中，Nik為視覺單詞vi在類型為ck的區域中出現的次數，而Ni為視覺單詞vi在全部訓練樣本中出現的總次數。

通過公式（1），計算得出了每個視覺單詞跟各個Logo的類別的相關度，而這種相關度也反映了該視覺單詞在相應類別的Logo的判別能力。

1.2結構約束信息提取

上述方法中所評估的是單個局部特征與Logo類別的相關度，而不同特征之間的結構信息則對于區分不同的Logo類型以及背景區域也具有重要的作用。因此，將進一步提取局部特征之間的結構約束信息來描述Logo并用其區分不同的Logo以及背景區域。

本文所定義的結構信息不單有兩個局部特征之間的描述子共生關系，而且還具有兩個結構特征的尺度、方向等信息。

對于在圖像區域r中的兩個特征fi和fj，其對應的視覺單詞為vi和vj，則提取視覺單詞vi和vj之間的結構信息如下：

gij=（dij，pij，sij）（2）

其中， pij=l（pi，pj）λsi， θij=θi-θj， 而sij=sjsi， l（pi，pj）為位置pi和pj之間的L2距離， 而λ為常數。從公式（2）可以看出，兩個視覺單詞的結構信息綜合了特定的兩個特征的相對距離、相對的尺度變化以及相對的尺度信息，這些信息對于刻畫兩個特征之間的結構信息具有重要的作用。

1.3基于結構信息的Logo模型

不同的特征對于不同類型的Logo的判別能力也各不相同，而每一特征與其他特征的結構信息均和相對應的Logo的結構信息相關，因此在進行Logo信息模型的表示時，既需要判別力較高的視覺單詞，又需要各個局部特征之間的結構信息。

定義結構gij相對于類型為ck的Logo的判別力為：

dGijk=dVik×dVjk（3）

同時，可以獲得結構gij在類型為ck的Logo區域中所有出現的平均模式為：

gijk=（dij， θij， sij）（4）

其中， dij、θij和sij分別為結構gij在類型為ck的Logo區域中出現的所有情況的相對距離、相對角度和相對尺度的平均值。

因此，可使用如下信息以構成類型為ck的Logo的表示模型為：

Vk={（vi， dVik）}（5）

Gk={（gijk， dGijk）}（6）

為了有效降低存儲上述信息的內存開銷，可分別保留判別力較高的前Nk個視覺單詞和前Mk個結構信息。

2Logo檢測方法

為了快速定位給定圖像中的Logo所在位置和Logo隸屬類型，可采用由粗到精的策略來進行Logo檢測。在粗定位階段，根據圖像中局部特征與各個類型的Logo的判別力的關系，確定置信度高的區域作為候選Logo區域；在精確定位階段，采用結構相似性對候選區域與對應的Logo的結構信息進行對比，得以最終確定Logo的定位結果。

2.1基于特征判別力的快速定位方法

不同的局部特征與不同類型的Logo具有不同的相關度，由此就可以根據圖像中局部特征的分布，確定得到一定區域內與其相關度較高的某個類型的Logo。

對于給定圖像，首先提取圖像中的SIFT特征，并根據訓練集合所獲得的碼本來獲得每個SIFT特征的視覺單詞。其次，使用已經獲得的各個類型的Logo的模型來判斷每個視覺單詞與對應的Logo的類型的相關度。對于待檢測圖像I，構建與Logo的種類數目相同的相關度模板，每個模板的大小與待檢測圖像大小相同，并將每個位置初始化為0。而后分別計算圖像中全部特征與每個類型的相關度，在這里，由于每個特征表示的是圖像中的一個區域，因此，可將特征的相關度累加到該特征對應區域的每個像素位置之中。最終，即可獲得K個相關度圖。

綜上所述，通過閾值分割的方法，獲取每個相關度圖中大于一定閾值各個連通區域，完成對特征的粗定位。可以看出，文中的粗定位方法是根據特征的相關度，將相關度高的區域獲取出來。

2.2基于結構約束的精確定位方法

在使用粗定位獲得了各個類型的Logo的候選區域后，卻由于噪聲等影響，還需要對每個候選區域實行進一步的判斷，來提高定位的準確性，在此，采用的是基于結構約束的精確定位方法。

對于獲得的候選區域r，計算r中的各個特征直接映射的結構信息gij=（dij， θij， sij），并且計算該結構信息與對應的平均結構的相似度，計算公式為：

SGijk=exp（-λ1|dij-dijk|-λ2|θij-θijk|-λ3|sij-sijk|）（7）

其中，λ1，λ2和λ3為常數，是用于調節相對距離、相對方向和相對尺度三者對于最終結構相似性的影響的權值。

由此，可獲得候選區域r與類型k之間的相關度，具體計算公式為：

s（r，k）=∑gij∈rdGijk×SGijk（8）

從公式（8）可以看出，候選區域r與類型k之間的相關度是由區域r內的全部結構信息與類型k內的相似度最終確定。

最后，如果s（r，k）tk，tk為預先定義的閾值，則可確定候選區域為類型k的Logo的精確位置，并輸出Logo的類型。

3實驗結果

為了驗證所提出方法的有效性，在一個較大規模的圖像數據集合上進行了Logo檢測的實驗，并與當前主流的Logo檢測方法進行了對比。

3.1實驗設置

實驗所使用的汽車Logo數據集為從互聯網上收集的包含100個類型的主要汽車品牌Logo的10 000張圖像（100張/Logo），每個圖像中含有某個類型的Logo標志1個，均采用矩形框人工標注出來。圖像中Logo的區域存在尺度、旋轉、拍攝視角和光照等變化的影響，這些給Logo檢測和識別帶來了很大的困難。圖1展示了數據集合中100個Logo的例子。

為了有效評估不同方法的Logo檢測的性能，對圖像Ii根據每個算法所輸出的定位區域ri′和Logo類型ci′與已標注區域的ri和Logo類型ci進行對比，確定是否定位正確，

δi（ri′，ri）=1ci′=ci并且o（ri′，ri）≥t2

0ci′=ci并且o（ri′，ri）≥t2（9）

其中，o（ri′，ri）=|ri′∩r||ri′∪r|為兩個區域相重疊的面積與兩個區域的并集的面積比值，t2為閾值。

對于測試圖像集合S，檢測結果集合R′和真實結果集合R，采用定位準確率和召回率來評估每個方法的性能，其計算公式如下：

p=1|R′|∑ri′∈R′δi（ri′，ri）（10）

r=1|R|∑ri∈Rδi（ri′，ri）（11）

同時，使用綜合性能f，來評估每個方法的綜合性能，其計算公式為：

f=p*rp+r（12）

3.2與主流方法的對比

為了驗證所提出方法的有效性，與當前主流的方法進行了對比。對比方法包括：

（1）基線方法。采用直接的SIFT碼本量化，并進行基于視覺單詞匹配的確定匹配區域，同時保留包含密度較高區域的全部點的矩形框作為檢測區域；

（2）基于判別力的視覺單詞方法。與所提出的粗定位方法相同，直接將定位得到的候選區域進行輸出；

（3）LogoSeeker方法[7]。該方法采用SIFT特征進行匹配，并采用RANSAC方法進行空間驗證，最終獲得密度最高的匹配區域，作為檢測到的Logo區域輸出，進行評估；

（4）空間金字塔挖掘的方法[10]。通過統計視覺的單詞在不同的Logo之中出現的空間共生模式，檢測并定位得到Logo的位置。

圖2展示了不同方法在所采用的數據集上的準確率-召回率曲線。

由圖2中可以得到如下觀測結果：

（1）基于判別力的視覺單詞的方法優于基線方法，這是因為判別力視覺單詞的方法區分了不同視覺單詞的判別力，進而能夠更為準確地定位出所要檢測的Logo區域。這也證明了所提出的基于判別力的視覺單詞的表示方法的有效性；

（2）所提出的方法在準確率和召回率上明顯優于基線方法和基于判別力的視覺單詞的方法，這是由于所提出的方法考慮了特征之間的結構關系對于視覺判別力的影響，故而取得了較好的性能。這也證明了所提出的結構描述方法的有效性；

（3）所提出的方法優于LogoSeeker的方法和空間金字塔挖掘的方法，雖然另外兩種方法也使用了空間信息來增強檢測的準確率，但是所提出的方法通過區分不同的視覺單詞的判別力，同時又一并考慮了結構信息的影響，因此達到了更好的性能，也證明了所提出的由粗到精的框架的有效性。

3.3處理速度分析

為了驗證所提出方法的高效性，對比了各個方法取得最優綜合性能時的處理速度（秒/圖像），如表1所示，上述結果是在酷睿3.0 CPU和4G內存的PC機上測量的，其中的時間不包括SIFT特征提取和量化時間。

由表1可以看出，所提出的方法在準確率提高24%、召回率提高15%、綜合性能提高19%時，處理速度則比其他方法提升30%以上，這是因為所提出的基于判別力的粗定位方法能夠快速定位候選的Logo區域以提高處理速度，由此采用基于結構化約束的精確定位方法只需處理已檢測到的候選區域并確定所檢測的區域即可提高檢測精度。這個結果再次證明了所提出的由粗到精的框架的有效性。

表1各個方法處理時間（秒/圖像）和綜合性能的對比

Tab.1 Processing speeds （second/image） and

performance of different methods方法prf時間基線方法0.4420.3470.3890.86基于判別力特征方法0.5440.3800.4470.24LogoSeeker方法0.5600.4550.5021.21空間金字塔挖掘方法0.6160.5410.5760.53所提出的方法0.7630.6230.6860.37

4結束語

本文提出了一個基于特征判別力分析和結構約束的Logo檢測方法，將視覺單詞的判別力與結構約束結合起來構建了一個由粗到精的檢測框架。與當前主流的方法相比，所提出的方法有如下幾個優點：

（1）所提出的視覺單詞判別力分析的方法能夠有效分析視覺單詞的判別能力，能夠實現較快速準確的粗定位；

（2）所提出的結構約束，有效刻畫了特征之間的結構約束關系，由此能夠有效區分Logo區域和其他干擾區域；

（3）所提出的由粗到精的檢測框架將基于判別力分析的方法和基于結構約束的方法聯系起來，在保證處理精度的同時，亦有效地提高了處理速度。在一個包含100種Logo的10 000張圖像規模的數據集合上進行實驗所得的結果中，文中提出的方法在綜合性能和處理速度方面均明顯優于其他方法，證明了所提出方法的有效性和高效性。

參考文獻：

[1]SCHIETSE J， EAKINS J P， VELTKAMP R C.Practice and challenges in trademark image retrieval. CIVR， 2007： 518-524.

[2]DEN HOLLANDER R J M， HANJALIC A. Logo recognition in Video stills by string matching.ICIP ， 2003： 517-520.

[3]JAIN A K， VAILAYA A. Shape-based retrieval： a case study with trademark image databases. PR， 1998，31（9）：1369-1390.

[4]KOVAR B， HANJALIC A. Logo appearance statistics in a sport video： video indexing for sponsorship revenue control. SPIE， 2002.

[5]PELISSON F， HALL D， RIFF O. Brand identification using Gaussian derivative histograms. MVA， 2003（16）：41–46.

[6]LOWE D G. Distinctive image features from scale-invariant keypoints. IJCV， 2004，60（2）：91-110.

[7]SANYAL S， SENGAMEDU S H. Logoseeker： a system for detecting and matching Logos in natural images. ACM MM， 2007：166-167.

[8]BAGDANOV D， BALLAN L， BERTINI M.Trademark matching and retrieval in sports video databases. MIR， 2007：79-86.

[9]BALLAN L， BERTINI M， JAIN A. A system for automatic detection and recognition of advertising trademarks in sports videos. ACM MM， 2008：991-992.

[10]KLEBAN J， XIE X， MA W. Spatial pyramid mining for Logo detection in natural scenes. ICME ， 2008：1077-1080.