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

董小靈

（國家知識產權局專利局 專利文獻部，北京 100083）

0 引 言

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

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

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

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

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

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

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

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

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

第三步是為特征點分配適當的方向，主要是確定特征點的主要方向，將圖像特征點的主要方向轉換一致，達成旋轉不變性。

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

1.1.1 尺度空間極值點檢測

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

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

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

式中：k為常數。

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

則有式（6）：

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

1.1.2 特征點位置的確定

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

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

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

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

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

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

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

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

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

1.1.3 特征點方向確定

為了在后續描述專利二值化圖像特征點時準確描述圖像特征點的方向，并且在圖像特征點匹配時可以將圖像特征點轉變為主梯度方向，以達到圖像特征點具有旋轉不變性的特性，必須對各個圖像特征點計算向量方向和大小，賦予一個主梯度方向。

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

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

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

1.1.4 特征點描述向量

經過前述三個步驟，檢測到所需要的圖像穩定特征點，并且獲得圖像每一個穩定特征點的相關特性，即坐標位置、尺度空間及方向強度。在此基礎上，對圖像的穩定特征點進行特征描述，構成特征向量。以特征點為中心提取4×4 大小的區域，每個特征點所在的區域可以劃分為16 個子區域。分別統計每個子區域內的方向直方圖。每個子區域共計有8個方向，因此，每一個特征點的向量維度全部共有4×4×8=128 維。

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

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

輸入：

Tij：第i幅訓練專利二值化圖像的第j個關鍵特征點

變量：

R90ik：第i幅訓練專利二值化圖像90°旋轉后第k個關鍵特征點

R180ik：第i幅訓練專利二值化圖像180°旋轉后第k個關鍵特征點

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

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

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

程序：

//Pi訓練專利二值化圖像的關鍵特征點數量

//Gis是訓練專利二值化圖像不同幾何變換的關鍵特征點數量

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

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

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

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

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

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

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

2.1 產生二值化描述符

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

2.2 哈希函數的計算

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

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

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

2.3 哈希表的建立

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

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

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

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

ComputerD0,…,D7by（20）

將專利二值化圖像SIFT 特征描述符轉化為二值描述符

2.4 圖像檢索匹配

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

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

C={Cn|n=1,…,N}：目標數據庫圖像集合，初始值為0

T：海明距離的閾值

Output：C={Cn|n=1,…,N}：目標數據庫圖像更新結合

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

將專利二值化圖像SIFT 特征描述符fm轉化為二值描述符B′

從哈希表T 的桶內檢索數據

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

計算B′與B的海明距離

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

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

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

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

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

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

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

表2 不同規模專利二值化圖像簡化前后的SIFT 特征點數量

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

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

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

4 結 語

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