向雷，肖詩斌，2，林春雨，2，呂學強，2

1.北京信息科技大學中文信息處理研究中心，北京 100101

2.北京拓爾思信息技術股份有限公司，北京 100101

基于輪廓與SIFT特征組合的商標圖像檢索

向雷1，肖詩斌1，2，林春雨1，2，呂學強1，2

1.北京信息科技大學中文信息處理研究中心，北京 100101

2.北京拓爾思信息技術股份有限公司，北京 100101

1 引言

商標圖像的自動檢索對于保護注冊商標的合法權益具有重要的意義。在對新的商標圖像進行注冊時，需要查詢已有的商標庫中是否存在重復或類似的商標圖像，從而決定其是否具有注冊資格[1]。近年來，由于注冊商標的數(shù)目不斷增加，人工檢索的方式已經(jīng)難以勝任大量商標的相似性比較。因此，為了加強商標的管理，建立一種準確高效的商標自動檢索系統(tǒng)具有非常重要的意義。

商標檢索的方法可分為基于類目檢索商標、基于文本檢索商標、基于內(nèi)容檢索商標。隨著商標數(shù)目的不斷增長，前兩種檢索的弊端逐漸顯露，而近年來發(fā)展的基于內(nèi)容的檢索方法突破了前兩種方法的局限?；趦?nèi)容的檢索方法包括顏色特征、紋理特征和形狀特征。對于商標圖像來說，顏色信息只能作為輔助特征，不能作為判斷兩幅圖像是否相似的準則。另外，由于商標一般比較簡單，紋理信息較少，因而對于它們的檢索，形狀特征顯得尤為重要。

對于形狀的表示和描述是基于形狀的商標圖像檢索的核心問題，現(xiàn)有的對形狀的描述方法大體可以分為基于輪廓和基于區(qū)域兩大類。以輪廓為基礎的特征提取方面，F(xiàn)reeman[2]等人提出用鏈碼來描述商標圖像的形狀特征；Iivarinen[3]在前人的基礎上又提出鏈碼直方圖的特征表示方法；姚玉榮[4]等人利用小波變換提取圖像邊緣，然后用邊界矩對圖像的邊緣進行描述，具有較好的平移、尺度和旋轉(zhuǎn)不變性。以區(qū)域為基礎的特征提取方面，馬躍先[5]等提出了利用7個不變矩特征進行圖像檢索的方法，滿足圖像的平移、尺度和旋轉(zhuǎn)不變性；孫興華[6]等提出了利用子圖像特征進行商標檢索，先對商標圖像進行子圖像分割和抽取，然后提出子圖像特征進行檢索；Guo[7]等提出在四叉樹分解子塊上進行形狀特征提取，使檢索精度有了進一步的提高。

大部分性狀描述方法都是把形狀作為一個整體來考慮。在這些方法中，圖像的相似度都是通過直接計算直方圖或者特征向量的距離而得到的。這樣做可以從整體上分析形狀的特點，計算比較簡單，但是對于局部的描述并不充分。有些商標圖像可能是另一些商標圖像的形變，這些商標圖像整體相似度可能有差異，但在某些局部相似度仍然很高。因此在進行形狀分析時，不但要考慮全局的相似性，還要考慮局部的相似性。為了提高檢索的精度，提出了一種基于輪廓和SIFT特征的商標圖像檢索方法。

2 SIFT特征提取

SIFT算法的本質(zhì)就是從圖像中提取SIFT關鍵點的過程。它的提取算法包塊3個關鍵步驟[8]：尺度空間極值檢測；關鍵點方向參數(shù)的確定；特征向量描述。

2.1 尺度空間極值點檢測

為了檢測尺度空間的極值，首先必須建立適當?shù)某叨瓤臻g。圖1為Gaussian金字塔和DoG尺度空間的建立過程（左邊表示的是Gaussian尺度空間，右邊表示的是DoG尺度空間）。

圖1 （a）Gaussian和DoG尺度空間的建立過程

圖1 （b）局部極值點檢測

DoG尺度空間是利用高斯差分（DoG）來建立的，DoG算子定義如式（1）：

為了檢測局部極值點，需要比較DoG尺度空間圖像中的每一個像素與它鄰近26個像素（上一個尺度空間圖像的9個像素點，同尺度空間圖像的8個點，下一個尺度空間圖像的9個像素點）的值，如圖1中圖（b）所示。若一個像素(x，y)是局部極值點，則它必須是與鄰近的26個像素中比較后得出的極值點。所有這樣得到的局部極值點，就是算法所需的SIFT候選的關鍵點的集合。

2.2 關鍵點方向參數(shù)確定

在獲得了比較穩(wěn)定和具有抗噪能力的特征點后，為了能讓特征點具有旋轉(zhuǎn)不變性，應該計算這些特征點的主方向，讓特征描述子在這個主方向上生成，這樣就可以消除因為旋轉(zhuǎn)而產(chǎn)生的不一致性了。對每個特征點來說，先要計算高斯濾波后的商標圖像在該特征點鄰域內(nèi)（一般為該特征點尺度的1.5倍）所有點的梯度模值和梯度方向，這里可以使用差分運算來近似梯度的求導運算，如式（2）和式（3）所示[9]：

實際計算時，在高斯空間內(nèi)特征點的領域內(nèi)采樣，創(chuàng)建梯度方向直方圖。直方圖每10°為一個格子（bin），共36個格子。然后將領域內(nèi)的每個采樣點按梯度方向歸入適當?shù)腷in，以梯度模作為貢獻的權重。最后選擇直方圖的主峰值作為特征點的主方向，選取量值達主峰值80%以上的局部峰值作為輔助方向。這樣，一個特征點可能會被指定具有多個方向，可以增強匹配的魯棒性。

2.3 特征向量描述

接下來需要為每個檢測到的特征點生成SIFT特征描述子，具體步驟如下[10]：

（1）首先以特征點為中心取16×16的鄰域作為采樣窗口。

（2）將采樣窗口中各像素點的根據(jù)坐標按高斯加權歸入4×4的位置網(wǎng)格（每個格子即為描述子的一維），窗口中所有點對同一網(wǎng)格的貢獻之和作為描述子在該維的值。

（3）將采樣點與特征點的相對方向按高斯加權后歸入包含8個格子（bin）的方向直方圖（每個格子同樣作為描述子的一維），所有點對同一格子的貢獻之和作為描述子在該維的值。這里注意創(chuàng)建方向直方圖使用的是采樣點和特征點的相對方向，從而可以使SIFT特征具有旋轉(zhuǎn)不變性。

（4）由（2）、（3）即獲得4×4×8共128維的SIFT描述子。

如圖2描述了一個8×8的窗口采樣的情形。

圖2 關鍵點特征向量描述

3 輪廓特征提取

對商標圖像的輪廓特征提取可以分為三步：

（1）對商標圖像進行輪廓提??；

（2）對輪廓的點集進行采樣，并將采樣點作為商標圖像的輪廓特征點集；

（3）對該特征點集進行特征描述，并將對特征點集的描述作為商標圖像的全局輪廓特征描述。

3.1 輪廓提取

提取圖像輪廓即對圖像進行邊緣提取，而提取圖像邊緣又首先要通過邊緣檢測算法計算圖像的邊緣值。常用的邊緣檢測算法大多是以原始圖像的灰度值為基礎，通過考察圖像的每個像素的某個領域內(nèi)灰度的變化，利用一階或二階導數(shù)的規(guī)律來檢測邊緣。

Sobel算子是邊緣檢測中最常用的算子之一，它首先進行領域平均或加權平均，然后進行一階微分處理，檢測出邊緣點。通常用式（4）中的兩個卷積核h1和h2，分別對圖像進行水平和垂直邊緣的檢測[11]：

如果h1響應的是x，h2響應是y，則可得出幅值：其方向是arctan()，運算結果是一副邊緣幅度圖像。如圖3為進行Sobel算子的輪廓提取效果圖。

3.3 參考點特征描述

圖3 Sobel算子輪廓提取效果圖

3.2 輪廓分解

3.2.1 分解起始點求取

分解起始點要求通過規(guī)則算法得到輪廓上的某一固定點。下面給出計算輪廓起始點的規(guī)則算法[11]：

（1）計算圖像的中心點坐標。通過階矩計算圖像的中心點坐標(ˉ，ˉ)，計算公式如式（5）：

（2）計算圖像的主方向軸斜率K。對于圖像而言，無論其做何角度的旋轉(zhuǎn)，主方向軸都是唯一的。圖像的主方向軸與水平方向的夾角β可以根據(jù)圖像的中心矩計算得到，如式（6）：

（3）通過主方向軸與水平方向的夾角得到主方向軸的斜率k，如式（7）：

（4）計算主方向軸。通過中心點位置和主方向軸斜率可以得到主方向軸y=Kx+B，如式（8）：

（5）得到輪廓分解起始點。將主方向軸與輪廓的交點集中，與中心點距離最近的點作為輪廓分解的起始點。

3.2.2 參考點求取

采用等角度劃分方法來對輪廓進行分解，該方法從分解起始點開始，每隔相同角度畫一條過中心點坐標的方向軸，方向軸與輪廓的交點就成為一個采樣點。提取的是商標圖像最外層輪廓，因此當方向軸與輪廓有多個交點時，選取距離中心點距離最遠的點作為采樣點。這樣如果將[0，360°]的范圍劃分為m個區(qū)間，所選取的采樣點的個數(shù)即為m。本文將360°區(qū)間劃分為20個等級，即選取的采樣點個數(shù)m=20。

在對商標圖像進行輪廓點集的采樣后，對這些采樣點進行特征描述。因為孤立地考慮單個采樣點是沒有意義的，較為普遍的做法是考慮以該采樣點為中心的一段弧線段，對其進行特征描述。設輪廓點個數(shù)為n，采樣點數(shù)目為m，以采樣點d為中心，n/m為長度選取輪廓上的弧線段L，則可以將L作為采樣點d對應的弧線段，因此對L的特征描述就可以作為采樣點d的特征描述。

在采樣點和弧線段之間可以建立一個向量集合，這個向量集合可以詳細地描述弧線段L。為了能使獲得的特征便于比較，同時具有不變性，采用Fourier變換來處理這個向量集合。

從采樣點d到弧線段L的每個點引一個向量v=(x，y)，將向量v=(x，y)表示為復數(shù)形式為v=x+jy，這樣便可以得到包含N/M個向量的向量集V(k)=xk+jyk。因為Fourier變換處理的是周期函數(shù)，為了使V(k)滿足周期性，將V(k)中的值取反取一邊，得到新的向量集V(k)=xk+jyk，對V(k)進行Fourier變換，如式（9）所示：

復系數(shù)a(u)為弧線段L的Fourier形狀描述子。由于信號量的能量主要集中在低頻部分，所以只需取前面p個系數(shù)即可較好地反映被描述弧線段的整體形狀了，本文取p=12，即一個特征點用12維的傅里葉描述符來表示。

4 特征匹配與相似性度量

根據(jù)第2章和3章中的特征提取，可以得到的商標圖像的輪廓特征向量GF和SIFT特征向量LF。在得到商標圖像的輪廓特征向量GF和SIFT特征向量LF后，就可以通過對GF和LF進行多特征融合技術來得到所需要的組合特征MF。

使用D來表示兩幅商標圖像之間組合特征MF的距離大小，如果D1表示商標圖像輪廓特征向量之間的距離大小，D2表示商標圖像SIFT特征向量之間的距離大小，則融合輪廓特征向量GF和SIFT特征向量LF的計算表達，如式（10）所示：

從商標圖像組合特征公式中可以看出，w1、w2分別表示商標圖像全局特征和局部特征的權值大小，對于w1、w2的設定將采用用戶反饋的方式來進行最優(yōu)化。下面就用戶反饋最優(yōu)化權值w1、w2進行算法描述：

（1）初始設定權值{ω1，ω2}的大小。

（2）得到用戶對第一次檢索結果中最滿意的前m幅圖片，并分別計算每幅圖片與待查詢圖片的輪廓特征距離D1(i)i=1，2，…，m，SIFT特征距離D2(i)i=1，2，…，m。

（3）分別計算上面輪廓特征距離，以及SIFT特征距離的平均值-D1和-D2。如果-Di平均距離越大，則表示特征i對于用戶體驗來說相對不是很重要，可以降低它的權值大小。

圖4 商標庫截圖

（4）組合特征距離公式中，距離越小，圖像越相似。因此，如果哪個特征不重要，那么應該分配較小的權值，因此權值{ω1，ω2}可由式（11）進行修正：

（5）用戶根據(jù)修改的權值，進行下一次的檢索，循環(huán)第（2）步，直到用戶滿意為止。

5 實驗設計與結果分析

5.1 實驗設計

查準率和查全率都是信息檢索中標準的性能評價方法，能夠很好地說明系統(tǒng)的性能。查準率定義為檢索返回的相關圖像與檢索返回的所有圖像的比率；查全率定義為檢索返回的相關圖像與圖像庫中所有圖像的比率。查準率用于測量系統(tǒng)排出無關圖像的能力，查全率用于測量檢索相關圖像的能力。查準率和查全率結合起來，描述了系統(tǒng)的檢索成功率[12]。

查準率定義如式（12）：

為了對本文的組合特征進行有效性驗證，共選取了10幅商標圖像（分別表示為I1，I2，…，I10）作為目標圖像進行檢索，圖像庫為1 000幅商標（搜集了福布斯2010世界500強以及中國最具價值500企業(yè)的商標圖像，如圖4），返回50張結果圖像。

首先，為了驗證多特征組合對縮放、平移和旋轉(zhuǎn)不變性，對10幅圖像進行了多比例縮放和多角度旋轉(zhuǎn)。這樣，每幅圖像產(chǎn)生10幅縮放圖像和10幅旋轉(zhuǎn)圖像。商標圖像庫則有1 200幅商標圖像，將該組實驗為設為實驗A。

其次，為了驗證區(qū)域特征對于圖像扭曲、遮擋和噪聲的支持效果，選取的10幅圖像進行扭曲、遮擋和加噪的處理，同樣產(chǎn)生10幅扭曲圖像和10幅遮擋、噪聲效果圖像，商標圖像庫仍為1 200，將該組實驗設為實驗B。

最后，為了驗證組合特征的實用性，找到了一張仿“阿迪達斯”商標的“萬達奴”商標（如圖5），對“萬奴達”商標圖像和“阿迪達斯”商標圖像分別進行了旋轉(zhuǎn)和縮放處理，目標圖像仍為20幅，將該組實驗設為實驗C。在實驗C的基礎上，可以進一步的測試用戶反饋機制對于實驗的提升效果，即在多特征組合的實驗中多次通過用戶滿意度來調(diào)整各特征權值，最后達到穩(wěn)定的效果。

圖5 仿“阿迪達斯”商標的“萬達奴”商標

5.2 實驗結果與分析

（1）實驗A實驗結果與分析

圖6是組合特征對實驗A檢索結果效果圖（“東風日產(chǎn)”商標圖像）；表1是10組實驗樣本各自檢索結果的查準率與查全率。

從實驗結果中可以看到，結果集基本滿足了返回全部正確的基準圖像，且都排在最前面。平均查準率和平均查全率分別為0.808和0.778，查準率和查全率都相對較高，說明該組合特征對于圖像縮放和旋轉(zhuǎn)有較好的支持。

圖6 “東風日產(chǎn)”商標圖像旋轉(zhuǎn)性效果圖

表1 旋轉(zhuǎn)和伸縮樣本查全率和查準率表

（2）實驗B實驗結果與分析

圖7是組合特征對實驗B檢索結果效果圖；表2是10組實驗樣本各自檢索結果的查準率與查全率。

圖7 “東風日產(chǎn)”商標圖像扭曲性效果圖

表2 扭曲樣本查全率和查準率表

從實驗結果數(shù)據(jù)統(tǒng)計中可以看到，平均查準率和平均查全率分別為0.584和0.602。相對圖像旋轉(zhuǎn)性支持，區(qū)域組合特征對于圖像的扭曲效果相對較弱，但也基本能夠滿足人們對于檢索結果的滿意度。

（3）實驗C實驗結果與分析

圖8是實驗C檢索結果的效果圖，其查準率和查全率分別為0.60和0.59。

0.60的查準率和0.59查全率只能算基本合格，但在結果商標圖像集中前幾幅結果圖像返回了正確的“阿迪達斯”商標，這樣實際上已經(jīng)滿足了用戶對于檢索結果的要求。因為計算機的商標檢索應該是輔助作用，只是將被仿商標從海量的商標圖像庫中提取出來并展示給用戶，評判標準通常帶有一定的主觀性，所以在機器檢索之后還應該有一個用戶主觀評判的過程。

圖8 仿“阿迪達斯”商標檢索效果圖

為了進一步提高檢索精度，采用了一般性的用戶反饋機制對實驗C進行權值調(diào)整。根據(jù)用戶的反饋調(diào)整權重值，然后重新計算精度和查全率。圖9是經(jīng)過多次反饋的性能曲線。實驗結果表明，當2～3次反饋后檢索可以達到一個比較平穩(wěn)的效果，為別為0.80和0.77。

圖9 用戶反饋檢索效果圖

同時為了更好地體現(xiàn)實驗效果，加入了橫向?qū)Ρ?，即用已有的單一特征與組合特征對比，結果如表3所示。從表中可以看出，基于輪廓和SIFT組合特征的商標圖像檢索的查準率和查全率較其他幾種方法有一定的提高。

表3 組合特征與常用形狀特征查準率和查全率對比

6 結語

提出了一種基于輪廓和SIFT的組合特征提取和檢索商標圖像策略。與已有文獻中形狀的整體描述方法相比，本文的方法不但考慮了形狀的局部特性在更加細致的層面上對形狀進行了描述，而且對于圖像的輪廓有更好的描述。從實驗結果可以看出，該方法是一種行之有效的方法，檢索精度有所提高，能夠達到較理想的檢索效果。在今后的工作中，還需要對一些方面進行思考和改進，比如考慮是否有更優(yōu)的分解方法來對輪廓進行優(yōu)化分解，對每一類輪廓找到一個最優(yōu)的分解點數(shù)目。

[1]洪凡.商標及商標檢索的意義[J].情報探索，1995（4）：6-7.

[2]Freeman H.Computer processing of line-drawing images[J]. Computing Surveys，1974，6（1）：57-97.

[3]Iivarinen J，Peura M，Srel J，et al.Comparison of combined shape descriptors for irregular objects in A F C[C]//Proceedings of the 8th British Machine Vision Conference，1997，2：430-439.

[4]姚玉榮，章毓晉.利用小波和矩進行基于形狀的圖像檢索[J].中國圖象圖形學報，2000，5（3）：206-208.

[5]馬躍先.二值商標圖像檢索系統(tǒng)[J].山西大學學報：自然科學版，1998，2l（2）：137-143.

[6]孫興華.商標圖像檢索中子圖像特征融合準則研究[J].南京理工大學學報，2002，26（5）：509-512.

[7]Guo Li，Huang Yuanyuan，Yang Jingyu.Using sub—block image features to retrieve trademark image[J].Journal of Computer-Aided Design&Computer Graphics，2004，16（7）：969-970.

[8]Smyths J R，Chang S F.Transform feature for texture classification and disseminations in large database[C]//Proc of IEEE Int Conf on Image Processing，Austin，Texas，1994.

[9]Rui Y，Huang T S，Mehrotra S.Relevance feedback：a power tool for interactive content-based image retrieval[J].IEEE Trans on Circuits and Systems for Video Technology，1998，8（5）：644-655.

[10]何斌，馬天宇.VISua1 C++數(shù)字圖像處理[M].北京：人民郵電出版社，2001：380-400.

[11]楊曉東，吳玲達，周文.利用輪廓分解和局部描述的二值圖像檢索[J].小型微型計算機系統(tǒng)，2010（11）：2260-2264.

[12]茹立云，彭瀟，蘇中，等.基于內(nèi)容圖像檢索中的特征性能評價[J].計算機研究與發(fā)展，2003，40（11）：1566-1570.

XIANG Lei1,XIAO Shibin1，2,LIN Chunyu1，2,LV Xueqiang1，2

1.Chinese Information Processing Research Center,Beijing Information Science and Technology University,Beijing 100101,China
2.Beijing TRS Information Technology Co.,Ltd.,Beijing 100101,China

For the limitations of the description on single feature trademark image,a method of trademark image retrieval which is based on profile and SIFT characteristics is proposed.In this method,first step is to get profile by making trademark image to binary image,then contour decomposes the image using rule algorithm and does the Fourier transform on set of reference points of the decomposition.The Fourier coefficient is the profile feature of reference point.Then it detects extreme points on scale space of the trademark image,and describes the extreme points with feature which is SIFT characteristics description of trademark image.Finally,SIFT features is combined with profile features as a new feature for feature description of trademark image. Key words：profile feature;SIFT feature;contour extraction;profile decomposition;Fourier transform

針對單一特征對商標圖像描述的局限性，提出了一種基于輪廓和SIFT特征組合的商標圖像檢索方法。該方法對二值化的商標圖像進行輪廓提取，采用規(guī)則算法對其進行輪廓分解，對分解的參考點集進行Fourier變換，將得到的Fourier系數(shù)作為參考點的輪廓特征。針對商標圖像的尺度空間進行極值點檢測，并對檢測到的極值點進行特征描述，該特征描述即為商標圖像的SIFT特征描述。最后，SIFT特征與輪廓特征進行特征融合，并將融合后的組合特征作為對商標圖像的特征描述。

輪廓特征；SIFT特征；輪廓提??；輪廓分解；Fourier變換

A

TP391

10.3778/j.issn.1002-8331.1112-0552

XIANG Lei,XIAO Shibin,LIN Chunyu,et al.Trademark images retrieval based on SIFT feature and profile feature. Computer Engineering and Applications,2013,49（19）：167-172.

國家自然科學基金（No.60872133）；北京市教委科技發(fā)展計劃項目（No.KM201110772021）；國家科技支撐計劃課題（No.2011BAH11B03）。

向雷（1987—），男，碩士生，主要研究領域為數(shù)字圖像處理。E-mail：xiangleixu@126.com

2012-01-04

2012-03-23

1002-8331（2013）19-0167-06

CNKI出版日期：2012-05-31http://www.cnki.net/kcms/detail/11.2127.TP.20120531.1542.002.html

book=172,ebook=177