局部特征的局部敏感哈希專利二值化圖像檢索

董小靈

（國家知識產(chǎn)權(quán)局專利局 專利文獻(xiàn)部，北京 100083）

0 引 言

用文字與圖像相結(jié)合的方式來記載技術(shù)創(chuàng)新成果信息，文字部分用以客觀、準(zhǔn)確地描述整體技術(shù)專利說明書，是以方案為特征，圖像部分是對文字部分描述的直觀形象化補充。傳統(tǒng)的專利檢索技術(shù)是以文本內(nèi)容為基礎(chǔ)提供檢索功能，而圖像內(nèi)容幾乎不參與檢索。換言之，傳統(tǒng)的專利檢索過程幾乎忽略了圖像內(nèi)容信息。事實上，“一圖勝萬言”，圖像等非文本數(shù)據(jù)能夠在專利檢索中發(fā)揮舉足輕重的作用。

專利圖像不包括外觀設(shè)計圖像，幾乎全部是二值化圖像（黑與白）[1]，無色且大多數(shù)無紋理，僅有少數(shù)是低紋理。一方面，專利二值化圖像源于矢量圖像光柵化或者手工繪圖的掃描數(shù)字化，經(jīng)過這樣的過程，原始圖像的顯著幾何信息如紋理等幾近消失；另一方面，專利二值化圖像是由多種畫法創(chuàng)建的繪圖，如線的粗細(xì)、點虛線等，均取決于制圖者的偏好或者技術(shù)領(lǐng)域的特性。因此，形狀特征成為表述專利二值化圖像內(nèi)容信息的唯一圖像特征。

形狀特征是實現(xiàn)專利二值化圖像檢索的最為重要的低層視覺特征[2]。鑒于專利二值化圖像的特殊性質(zhì)并結(jié)合專利審查員的檢索需求，本文運用局部特征技術(shù)提取專利二值化圖像的特征描述矢量并對特征描述矢量進(jìn)行必要簡化，在此基礎(chǔ)上，對專利二值化圖像的特征描述矢量進(jìn)行二值化處理，并結(jié)合局部敏感哈希方法設(shè)計檢索索引結(jié)構(gòu)，從而實現(xiàn)基于內(nèi)容的專利二值化圖像檢索。

1 基于SIFT 的專利二值化圖像特征提取與簡化

尺度不變特征轉(zhuǎn)換（Scale Invariant Feature Transform，SIFT）算法[3-4]是以特征點為基礎(chǔ)的局部特征圖像算法。運用此算法可以提取專利二值化圖像的特征點，在此基礎(chǔ)上，通過幾何變換的方法縮減圖像中對幾何變換敏感的特征點數(shù)量，剔除專利二值化圖像的冗余與無效特征點，壓縮專利二值化圖像特征點的數(shù)量規(guī)模，從而降低專利二值化圖像的檢索匹配復(fù)雜度。

1.1 基于SIFT 的專利二值化圖像特征提取

運用SIFT 特征算法生成專利二值化圖像特征向量的過程大體上可以劃分為4 個主要步驟[5-6]。

第一步是尺度空間極值點檢測，主要是檢測圖像在不同尺度中所有可能的特征點位置，運用高斯函數(shù)處理，對模糊化的圖像做尺度變化，使圖像在不同尺度獲取代表性特征點。

第二步是過濾特征點與方向定位。為了取得穩(wěn)定的特征點，除了將低對比度的候選特征點濾除之外，還需要將邊緣處低對比度的特征點濾除。

第三步是為特征點分配適當(dāng)?shù)姆较?，主要是確定特征點的主要方向，將圖像特征點的主要方向轉(zhuǎn)換一致，達(dá)成旋轉(zhuǎn)不變性。

第四步是建立特征點的特征向量，在找出特征點的位置、尺度與主要方向的基礎(chǔ)上，形成特征點的特征向量。

1.1.1 尺度空間極值點檢測

一幅專利二值化圖像的尺度空間定位計算如下：

式中：(x,y)是空間坐標(biāo)，L(x,y)是尺度坐標(biāo)，I(x,y)表示原始圖像，*為卷積運算，G(x,y)為高斯函數(shù)。

完成專利二值化圖像的尺度空間定位后，采用高斯差分函數(shù)（Differential of Gaussian，DoG）[7-8]，利用高斯差分函數(shù)中的不同參數(shù)對圖像進(jìn)行濾波并相減，得到高斯差分函數(shù)的DoG 關(guān)系公式（3），其中D(x,y)的關(guān)系由公式（4）推導(dǎo)而來。

式中：k為常數(shù)。

利用差分近似值替代微積分值，式（4）可寫為式（5）的形式：

則有式（6）：

建立高斯差分（DOG）化后的金字塔，即在DoG 尺度空間中檢測極值點。極值點的檢測是在DoG 尺度空間中，取某一像素點與相鄰的8 個像素以及金字塔上下兩層相鄰的9 個像素等26 個像素進(jìn)行比較，觀察該像素為最大值或最小值時，則為極值點。

1.1.2 特征點位置的確定

為找出專利二值化圖像的準(zhǔn)確的特征點，利用擬合三維二次函數(shù)（3D Quadratic Function）刪除若干不穩(wěn)定的特征點，其中包括低對比度特征點和位于邊緣的點，實現(xiàn)對特征點位置與尺度的精準(zhǔn)定位，提升特征點的穩(wěn)定性與抗噪能力。

對于低對比度特征點，基本上是以一個三維二次函數(shù)計算亞像素極大值。具體做法是將尺度空間函數(shù)D(x)依據(jù)泰勒級數(shù)展開（最高到二次項），如式（7）所示：

式中：D為DoG 的結(jié)果，x為特征點。根據(jù)D可以得到一個偏移量如式（8）所示：

如果x^ 值任何一個方向上都大于0.5，則意味著極值與附加采樣點的偏移量非常接近，就會改變此采樣點。這時候就需要通過差值來取代該采樣點，x^ 值就會被添加到其他采樣點上，這樣就可以獲取極值點的差值估算值。如式（9）所示：

為濾除邊緣處的低對比特征點，將使用這些主曲率來判斷特征點是否在邊緣上。主曲率透過一個2×2 的Hessian 矩陣H求出，如式（10）所示：

導(dǎo)數(shù)可以由取樣點相鄰差估計求得D的主曲率和H的特征值（Eigen value）成正比。假設(shè)H的兩個特征值分別為α、β，可以推導(dǎo)出矩陣Tr(H)對角線元素之和為兩特征值的和，矩陣H行列值Det(H)為兩特征值的積，如式（11）、式（12）所示：

令α=γβ，如式（13）所示，則有：

(γ+1)2/γ的結(jié)果在兩個特征值相等時最小，隨著γ增加，(γ+1)2/γ的值也會隨著增加。當(dāng)γ比較大的時候，就表示特征值的差異較大，則表示特征點位于圖像的邊緣部分。要判斷特征點是否在圖像的邊緣上，需計算特征點在尺度空間中是否有較大的主曲率。因此，為了確定主曲率間比值的門檻值γ，采用式（14）進(jìn)行計算：

在本研究中，計算出主曲率間的比值大于10[9]，則該點被視為落入邊緣點位，即將該點予以濾除。

1.1.3 特征點方向確定

為了在后續(xù)描述專利二值化圖像特征點時準(zhǔn)確描述圖像特征點的方向，并且在圖像特征點匹配時可以將圖像特征點轉(zhuǎn)變?yōu)橹魈荻确较颍赃_(dá)到圖像特征點具有旋轉(zhuǎn)不變性的特性，必須對各個圖像特征點計算向量方向和大小，賦予一個主梯度方向。

以圖像的特征點為中心，取一區(qū)域為16×16像素大小的鄰域，再將其均勻分為16 個4×4 像素的子區(qū)域。對每個子區(qū)域進(jìn)行區(qū)域內(nèi)所有梯度強度與方向計算，梯度計算由式（15）、式（16）說明：式中：m(x,y)代表坐標(biāo)位置上的梯度強度，(x,y)代表坐標(biāo)位置上的梯度方向，L表示該區(qū)域內(nèi)所有的像 素 位 置，L(x,y+1)，L(x,y-1)，L(x-1,y)，L(x+1,y)分別代表特征點(x,y)上、下、左、右4 個相鄰域像素點的灰度值。

依據(jù)上述式（15）、式（16）對每一個所提取的特征點作計算，可以得到特征點的梯度強度值與方向值。接下來計算每個特征點的主要方向。方向可以化作方向直方圖的統(tǒng)計方式進(jìn)行計算，其范圍是[0,2π]，則每個柱表示為10°共有36 個柱。統(tǒng)計出來的直方圖結(jié)果峰值為這個特征點的像素梯度的方向。

方向直方圖中峰值代表特征點的方向。確認(rèn)方向直方圖的最大值后，如果方向直方圖的統(tǒng)計中，峰值在最大值80%以上，則可以歸類為主梯度方向，即將所有高峰值最大值的80%的描述方向都列為主梯度方向。若梯度方向直方圖超過80%的峰值不是只有一個，則屬于多重方向的情形。大約僅有15%的特征點會被賦予多個方向，這些點可以加強特征點匹配的穩(wěn)定性。

1.1.4 特征點描述向量

經(jīng)過前述三個步驟，檢測到所需要的圖像穩(wěn)定特征點，并且獲得圖像每一個穩(wěn)定特征點的相關(guān)特性，即坐標(biāo)位置、尺度空間及方向強度。在此基礎(chǔ)上，對圖像的穩(wěn)定特征點進(jìn)行特征描述，構(gòu)成特征向量。以特征點為中心提取4×4 大小的區(qū)域，每個特征點所在的區(qū)域可以劃分為16 個子區(qū)域。分別統(tǒng)計每個子區(qū)域內(nèi)的方向直方圖。每個子區(qū)域共計有8個方向，因此，每一個特征點的向量維度全部共有4×4×8=128 維。

1.2 基于SIFT 的專利二值化圖像特征簡化

用SIFT 算法提取專利二值化圖像得到的特征點數(shù)量較多[10]，對于專利二值化圖像的描述相當(dāng)充分，能夠全面表述專利二值化圖像的內(nèi)容。但是過多的圖像特征點也會產(chǎn)生冗余信息，直接影響專利二值化圖像的檢索匹配速度與效果。為了刪除專利二值圖像不必要與扭曲的SIFT 關(guān)鍵特征點，運用特征點簡化算法去除關(guān)鍵點數(shù)量，僅保留具有高幾何可變性的健壯關(guān)鍵特征點，以保持后續(xù)專利二值化圖像檢索的速度與準(zhǔn)確度，其算法過程代碼如下：

輸入：

Tij：第i幅訓(xùn)練專利二值化圖像的第j個關(guān)鍵特征點

變量：

R90ik：第i幅訓(xùn)練專利二值化圖像90°旋轉(zhuǎn)后第k個關(guān)鍵特征點

R180ik：第i幅訓(xùn)練專利二值化圖像180°旋轉(zhuǎn)后第k個關(guān)鍵特征點

S2ik：第i幅訓(xùn)練專利二值化圖像尺寸擴大2 倍后第k個關(guān)鍵特征點

S0.5ik：第i幅訓(xùn)練專利二值化圖像尺寸縮小一半后第k個關(guān)鍵特征點

Fi：簡化后所保留的專利二值化圖像關(guān)鍵特征點

程序：

//Pi訓(xùn)練專利二值化圖像的關(guān)鍵特征點數(shù)量

//Gis是訓(xùn)練專利二值化圖像不同幾何變換的關(guān)鍵特征點數(shù)量

如果Tij能夠同時實現(xiàn)R90ik、R180ik、S2ik和S0.5ik四種幾何變換的匹配，則保存Tij在Fi中。

首先，對訓(xùn)練專利二值化圖像集合中每1 件圖像進(jìn)行幾何旋轉(zhuǎn)與縮放。使用4 種幾何變換：旋轉(zhuǎn)90°，旋轉(zhuǎn)180°，尺寸擴大2 倍，尺寸縮小1/2。從變換圖像中提取特征點并且與原始圖像進(jìn)行比較。如果變換圖像與原始圖像相同特征點匹配（歐幾里德距離小于3 000），則該特征點被視為對幾何可變性具有魯棒性。通過保留魯棒特征點，可以高效減少專利二值化圖像特征點數(shù)據(jù)庫規(guī)模。然而，有可能一些圖像提取很少魯棒特征點，這使得圖像匹配相當(dāng)困難。因此設(shè)定每張專利二值化圖像最少特征點閾值F相當(dāng)重要。具體閾值F決定可參見式（19）。其中x-是訓(xùn)練專利二值化圖像數(shù)據(jù)集合關(guān)鍵特征點的平均數(shù)量，σ是訓(xùn)練專利二值化圖像數(shù)據(jù)集合關(guān)鍵特征點的標(biāo)準(zhǔn)方差，具體計算參見式（17）和式（18）。

式中：n是訓(xùn)練專利二值化圖像數(shù)據(jù)集合數(shù)量（本集合中數(shù)量為1 000 000 件）是所有訓(xùn)練專利二值化圖像的關(guān)鍵特征數(shù)量平均值。對于本訓(xùn)練集合而言是141 個，σ是90 個。注意在關(guān)鍵點簡化過程后決定這些值。每個訓(xùn)練圖像閾值的確定如下：

式中：R是在F的關(guān)鍵點數(shù)量。offset是從原始圖像中隨機選取的關(guān)鍵點數(shù)量直至通過這樣的調(diào)整機制，可以確保每個訓(xùn)練圖像的關(guān)鍵點數(shù)目在平均值與方差值之和范圍內(nèi)。如果R是在范圍內(nèi)，則R是F。如果R大于，減少R中關(guān)鍵特征點數(shù)量直至F等于

本研究中訓(xùn)練專利二值化圖像數(shù)量是1 000 000件，原始特征點共有216，734，674 個。在應(yīng)用特征點去除程序后，關(guān)鍵特征點數(shù)量減少到43，324，865。關(guān)鍵特征點數(shù)量減少近80%。

2 基于LSH 的專利二值化圖像索引機制

SIFT 算法能夠很好地表達(dá)描述專利二值化圖像的內(nèi)容特征。但是專利二值化圖像SIFT 特征的匹配時間過長，導(dǎo)致整個專利二值圖像檢索耗時冗長。為了減少專利二值化圖像檢索時間并且不影響檢索準(zhǔn)確度，對專利二值化圖像的SIFT 特征進(jìn)行二值化并結(jié)合局部敏感哈希（LSH）建立索引結(jié)構(gòu)[11-12]，以提升整個專利二值化圖像檢索系統(tǒng)的檢索速度與效率。

2.1 產(chǎn)生二值化描述符

針對專利二值化圖像的SIFT 特征點描述符計算8 個方向的平均值[13]，接著依據(jù)每個方向的平均值分別對描述符內(nèi)所對應(yīng)的數(shù)值進(jìn)行二值化。假設(shè)SIFT 特征點描述為F={fi|i=0,…,127}，然后分類成8個序列Fd={f8j+d|i=0,…,15}，d=0,…,7，其中d表示8個方向。算出8 個方向類別的平均值為Dd，計算公式為式（20）。最后比較其方向大小，判斷是否為0或1，計算公式為式（21），共產(chǎn)生128 維度的二值化描述符B={bi|i=0,…,127}。

2.2 哈希函數(shù)的計算

根據(jù)專利二值化圖像的SIFT 特征描述符特性產(chǎn)生哈希函數(shù)算法[14]H(M1,M2)，如式（22）所示，其中M1和M2都是利用專利二值化圖像SIFT 特征描述符的8 個方向所產(chǎn)生的平均值。

M1的產(chǎn)生是利用專利二值化圖像SIFT 特征描述符9 個方向的平均值，兩兩比較其大小去判斷是否為0 或1，如式（23）所示，接著把8 個0 或1 的比較結(jié)果合并成M1，如式（24）所示。

M2的產(chǎn)生也是利用專利二值化圖像SIFT 特征描述符8 個方向的平均值，依照每個方向的平均值與其他兩個鄰近的平均值做累加并產(chǎn)生8 個累加值，如式（25）所示，然后在8 個里面找出其最大值的累加值編號，如式（26）所示。

2.3 哈希表的建立

依據(jù)哈希函數(shù)將專利二值化圖像的SIFT 特征描述符存入哈希表中。但是若僅存儲SIFT 特征描述B，則不能分辨出該特征描述符是屬于哪一幅專利二值化圖像，所以應(yīng)當(dāng)將每幅專利二值化圖像的SIFT 特征描述符二值化后，經(jīng)過哈希函數(shù)計算，將二值化描述符B與圖像的ID，(B,In)，共同存入哈希表中，其中I={In|n=1,…,N}，N為專利二值化圖像數(shù)量，下述為具體方法代碼。

Input：F={fm|m=1,…,M}：專利二值化圖像的SIFT 特征描述符集合

Output：T={TX|x=0,…,2 047}：哈希表的2 048個桶集合

For 每張專利二值化圖像SIFT 特征描述符fm

ComputerD0,…,D7by（20）

將專利二值化圖像SIFT 特征描述符轉(zhuǎn)化為二值描述符

2.4 圖像檢索匹配

對專利二值化圖像SIFT 特征描述符經(jīng)過上述3 個步驟處理后，依據(jù)每個特征描述符經(jīng)過哈希計算的結(jié)果，檢索對應(yīng)哈希表桶內(nèi)的全部二值化描述，接著對測試的專利二值化圖像與哈希表桶內(nèi)的二值化描述符做海明距離比較[15-16]，設(shè)定海明距離的閾值為T。若比較結(jié)果小于或等于閾值T，就判定該哈希表桶內(nèi)的二值化描述符為相似描述符，并且記錄對應(yīng)的專利二值化圖像ID。當(dāng)計算完測試圖像的所有特征描述符后，統(tǒng)計相似特征描述符數(shù)量最多的專利二值化圖像為相似圖像，下述為具體方法代碼。

Input：F={fy|y=1,…,Y}：測試圖像的特征描述符集合

C={Cn|n=1,…,N}：目標(biāo)數(shù)據(jù)庫圖像集合，初始值為0

T：海明距離的閾值

Output：C={Cn|n=1,…,N}：目標(biāo)數(shù)據(jù)庫圖像更新結(jié)合

For 測試圖像的特征描述符fy

將專利二值化圖像SIFT 特征描述符fm轉(zhuǎn)化為二值描述符B′

從哈希表T 的桶內(nèi)檢索數(shù)據(jù)

從桶中產(chǎn)生一系列(B,In)

計算B′與B的海明距離

3 專利二值化圖像檢索算法的實驗

為了驗證上文所述的專利二值化圖像檢索算法的性能，選擇專利二值化圖像進(jìn)行實驗測試。開展本實驗測試所搭建的基本硬件配置為Intel CPU Q9550 2.83 GHz，4 GB DDR2 800 內(nèi)存。選擇2010年至2020 年期間中國發(fā)明專利申請說明書與實用新型專利說明書的相關(guān)附圖作為實驗的圖像數(shù)據(jù)集。作為實驗的圖像數(shù)據(jù)集主要包括測試圖像集、查詢圖像集及目標(biāo)圖像集3 個部分。

測試圖像集是指進(jìn)行查詢的專利二值化圖像數(shù)據(jù)集合，在本實驗測試中選擇1 000 000 幅專利附圖圖像作為測試數(shù)據(jù)集，圖像大小的范圍為256×384 ～1 024×768。查詢圖像集是指作為查詢輸入的專利二值化圖像數(shù)據(jù)集合，在本實驗測試中從測試圖像集中人工選取200 幅專利二值化圖像數(shù)據(jù)。目標(biāo)圖像集是根據(jù)查詢圖像集200 幅專利二值化圖像數(shù)據(jù)在測試圖像集中人工確定的相似專利二值化圖像數(shù)據(jù)，這部分?jǐn)?shù)據(jù)是中國專利文獻(xiàn)深加工項目的產(chǎn)物。

通過對測試圖像集的專利二值化圖像進(jìn)行SIFT 特征提取與簡化，形成優(yōu)化的專利二值化圖像關(guān)鍵特征點。在此基礎(chǔ)上，對專利二值化圖像關(guān)鍵特征點進(jìn)行二值化后利于哈希算法形成不同規(guī)模大小的局部敏感哈希索引表，具體如表1 所示。從表1可知，隨著專利二值化圖像訓(xùn)練數(shù)據(jù)集合規(guī)模數(shù)量的變動，局部敏感哈希索引表大小也線性變動。

表1 不同規(guī)模專利二值化圖像集合的哈希索引表大小

在對所述的專利二值化圖像進(jìn)行測試實驗過程中，以查詢圖像集所包含的200 幅專利二值化圖像作為作為查詢圖像用例在測試圖像集中進(jìn)行專利二值化圖像檢索的測試。首先，運用SIFT 算法提取專利二值化查詢圖像的特征點，再利用幾何變換算法對專利二值化查詢圖像所提取的SIFT 特征點進(jìn)行簡化。其次，對簡化后的專利二值化查詢圖像SIFT特征點進(jìn)行二值化處理形成新的專利二值化圖像的二值特征向量。隨后，根據(jù)哈希函數(shù)對專利二值化圖像的二值特征向量構(gòu)建局部敏感哈希索引，最后，基于投票方式統(tǒng)計相似特征描述符數(shù)量最多的專利二值化圖像為相似圖像并返回圖像標(biāo)識號碼。

根據(jù)專利二值化圖像測試集合不同規(guī)模進(jìn)行檢索，本實驗選用的專利二值化圖像測試集合有6 種規(guī)模，分別是50 000，100 000，200 000，500 000，800 000 及1 000 000。不同規(guī)模的專利二值化圖像測試集合的關(guān)鍵特征點數(shù)量簡化前后數(shù)值如表2 所示。表3 表示200 幅專利二值化查詢圖像在不同規(guī)模的專利二值化圖像測試集合中特征簡化前后檢索匹配具體時間值。從表3 可知，專利二值化圖像特征簡化前的檢索匹配時間要長于特征簡化后的檢索匹配時間。換言之，專利二值化圖像特征簡化提升了整個專利二值化圖像的檢索匹配速度。

表2 不同規(guī)模專利二值化圖像簡化前后的SIFT 特征點數(shù)量

表3 專利二值化圖像特征簡化前后檢索匹配時間值

表4表示200 幅專利二值化查詢圖像在不同規(guī)模的專利二值化圖像測試集合中特征簡化前后檢索匹配查全率。從表4 可以發(fā)現(xiàn)，專利二值化查詢圖像檢索匹配查全率在圖像特征簡化前要高于圖像特征簡化后，并且兩者都隨著專利二值化測試圖像集合規(guī)模的增加而逐步降低。盡管專利二值化測試圖像集合規(guī)模達(dá)到百萬級，但是專利二值化圖像檢索特征簡化前后匹配查全率并沒有大幅度變化，并且最低匹配查全率仍然保持在85%以上。這樣的測試結(jié)果表明，本研究所提出的專利二值化圖像檢索算法具有較高的查全率與較快的檢索速度，可以運用在現(xiàn)實的專利二值化圖像檢索中。

表4 專利二值化圖像特征簡化前后檢索匹配查全率比值

4 結(jié) 語

專利二值化圖像自身內(nèi)在的復(fù)雜性與特殊性使得基于形狀特征的專利二值化圖像檢索更具挑戰(zhàn)性。通過對現(xiàn)有基于內(nèi)容的圖像檢索技術(shù)系統(tǒng)研究，認(rèn)識到局部特征提取技術(shù)對于構(gòu)建專利二值化圖像檢索算法具有重要意義。針對SIFT 算法在專利二值化圖像檢索算法實際應(yīng)用過程中所產(chǎn)生的特征矢量數(shù)量過多與特征矢量維度過高等兩大問題，本文提出了專利二值化圖像SIFT 特征向量的簡化算法和索引構(gòu)建機制。下一步將在改進(jìn)專利二值化圖像的局部特征提取算法和圖像相似度量比較算法基礎(chǔ)上，優(yōu)化索引結(jié)構(gòu)，來提升專利二值化圖像檢索算法的運行效率。