基于特征點的圖形檢索研究

唐 濤，高滿屯，何 波

（西北工業大學機電學院，陜西 西安710072）

與文字相比，圖形具有更形象，更直觀的特性，不僅可以彌補文字對客觀事務描述的不足，還可以輔助科研工程人員進行數據分析、工程實施：從對客觀數據的直觀顯示，比如直方圖，折線圖等，到機械零件的設計加工，比如使用CAD軟件完成的設計圖紙，再到房屋、橋梁、航空器的建造，施工，圖形正以前所未有的速度進入我們的工作與生活[1]。管理好、利用好海量的圖形信息將極大地推動各項工作的進步。因此，對于圖形檢索的研究具有十分重要的工程應用價值。

當前，在圖形檢索領域，使用最廣泛的是基于關鍵字的檢索(Keywords-Based Retrieval)[2]，它需要在檢索之前，通過人工將圖形的主要信息概括為關鍵字，然后對圖形進行標注。檢索過程就是將用戶輸入的關鍵字與數據庫中存儲的關鍵字進行匹配的過程，不具有模糊查找性[3]。另外一種廣泛使用的檢索技術是基于圖元之間拓撲關系的檢索。即將圖形分解為線段、圓弧等基本圖元，然后將圖元之間的關系定義為鄰接、包含、相觸等近十種拓撲關系，根據圖元之間的拓撲關系完成檢索[4]。雖然這種方法可以較好的實現圖形的檢索，具有一定的模糊性，但將圖形分解成基本圖元、然后分析圖元之間關系的過程費時費力，不利于大規模圖形的檢索。本文提出一種基于特征點的圖形檢索方法，可以根據不同的任務需求，設定不同的模糊量，并且被檢索到的圖形具有平移不變性和旋轉不變形。該方法主要以圖形自身作為研究對象，從圖形本身中確定一個基準點和基準向量，分析其他特征點與基準點和基準向量之間的關系，從而完成檢索。

1 圖形基準的確定

圖形由基本的圖元構成：點，線段，圓弧，圓等[5]。而線段可以由兩個點唯一確定。圓弧可以由圓心和圓弧兩端的點唯一確定，圓可以由圓心和圓上任意一點確定。任意折線可以用若干首位相接的線段進行近似。任意曲線可以通過若干規則的圓弧或者通過若干首位相接的線段進行近似。綜上可以得出這樣的結論：任何圖形都可以通過有限的特征點進行描述。若圖形與圖形之間的特征點完全相同，則兩個圖形相似。

1.1 圖形基準點的確定

將圖形看成是若干特征點的集合，則這些特征點可以視為是圍繞在圖形型心附近的點。特征點與型心之間的關系，例如特征點的松散程度，與型心的緊密程度，可以被用以描述圖形。因此將圖形的型心定義為圖形的基準點(Xc,Yc)。圖形的型心可以通過公式(1)~(5)計算得到。

1.2 圖形基準向量的確定

基準向量的確定是為了將圖形中的特征點單獨唯一的表征出來。從眾多的特征點中確定出與型心距離最近的特征點。基準向量由型心與該特征點構成，方向指向特征點。如圖1所示。特征點為A(X1,Y1)，B(X2,Y2)，C(X3,→Y3)，D(X4,Y4)。型心為Cd(Xc,Yc)。基準向量P由型心Cd(Xc,Yc)與最近的特征點B(X2,Y2)構成，由公式(6)計算得到。

2 特征點的規范化

為了進行圖形檢索，所有的圖形必須經過規劃化處理，即以統一格式的數據信息表征圖形。特征點規范化后由角度值cosθ和距離值L組成。當兩個圖形規范化后的數據信息滿足檢索條件時，系統從數據庫中把該圖形輸出。特征點的規范化以圖形的基準向量作為基準。圖形型心與每個特征點都可以構成一個向量，如圖1所示，各個向量分別為其中，將向量定義為基準向量。將這些向量以與基準向量之間的夾角作為特征點規范化后的角度值cosθ，將向量的模作為距離值L，計算如公式(7)所示。

其中，表示基準向量，表示型心與各個特征點構成的向量。則基準向量與向量的角度值為cos∠ACdB，向量的模為，則特征點A對應于特征點B對應于特征點C對應于特征點D對應于

圖1 型心與特征點的示意圖

3 數據的處理

3.1 圖形數組

從以上論述可知，圖形中的每個特征點對應于一組數據：角度值和距離值。取角度值和距離值之積，不僅可以將兩個數據合并為一個數據，減少后續檢索過程中的計算量，而且還能擴大圖形與圖形之間相應特征點的差異程度。因此，本文將圖形中特征點的一組數據簡化為一個數據進行處理，計算如公式(8)所示。

其中，cosθ為特征點規范化后的角度值，為特征點規范化后的距離值。從以上的論述可知，Value可以唯一確定特征點在圖形中的位置。因此，一個元素數目與特征點數目相等的數組就可以完整地描述一個圖形。圖形的檢索則是尋找一個與已知數組相似的數組。本文把該數組定義為圖形數組。圖形數組的表示方式如式(9)所示。

3.2 圖形數組的規范化

在進行檢索的過程中，用戶輸入圖形的特征點與數據庫中圖形的特征點的數目在大多數情況下并不相等。因此，在進行圖形檢索之前，要對圖形數組進行規范化操作，即：在與用戶輸入圖形進行比對之前，在相似圖形的特征點中選取與輸入圖形特征點相同數目的特征點。由于之前的步驟已經將圖形簡化為一個圖形數組，因此，選取特征點的操作就等同于在相似圖形的圖形數組中選取元素。這些元素需要滿足以下兩個約束條件：① 元素的數目與用戶輸入圖形的圖形數組中元素的數目相等；② 元素與在用戶輸入圖形的圖形數組中的元素最接近。在實際檢索中，滿足這兩個約束條件的圖形是：在相似圖形中尋找與用戶輸入圖形在形狀上最接近的部分。規范化的過程如公式(10)~(12)所示。

其中m>=n

其中，函數min返回數組中最小元素的被減數。則規范化后的Vector2如公式(13)所示。

3.3 檢索參數

在圖形數組的數字特征可以很好的將圖形數組的整體特性表示出來，即標準差Sn。標準差Sn描述的是圖形數組元素的緊湊性。標準差可以通過式(14)求得。當差Sn在給定的模糊查找系數δ范圍內時，向用戶返回檢索結果。

4 實驗

4.1 選取相似點

在實際檢索過程中，大多數情況是用戶輸入圖形的特征點的數目與相似圖形的特征點的數目不相一致。檢索的第一步就是從相似圖形中選取與用戶輸入圖形最接近的特征點。

輸入圖形特征點的坐標是(0 2 2 4 4 20 20 4 4 2 2 0; 2 2 0 0 2 2 4 4 6 6 4 4);

相似圖形特征點的坐標是(0 2 2 4 4 17 17 19 19 20 20 19 19 17 17 4 4 2 2 0; 2 2 0 0 2 2 1 1 2 2 4 4 5 5 4 4 6 6 4 4)。

圖2 兩個圖形對比

從圖2中兩個圖形的對比圖可以看出，相似圖形比用戶輸入圖形多出了兩個矩形區域。采用本文所提出的方法后，正確的從相似圖形的特征點中選取了與輸入圖形特征點近似的點。

4.2 檢索圖形

用戶輸入圖形特征點的坐標為(0 20 15 30 15 20 0; 5 5 0 7 14 9 9)。

近似圖形1（圖3(a)）的特征點為(0 20 15 28 28 15 20 0; 5 5 0 5 9 14 9 9)；

近似圖形2(圖3(b))的特征點為(0 30 15 50 15 30 0; 5 5 0 7 14 9 9)；

近似圖形3(圖3(c))的特征點為(0 4 4 20 15 30 15 20 4 4 0; 5 3 5 5 0 7 14 9 9 11 9)；

近似圖形4(圖3(d))的特征點為(0 20 45 30 45 20 0; 5 5 0 7 14 9 9)。

圖3 相似圖形與輸入圖形

用戶輸入圖形與相似圖形1, 2, 3, 4的標準差Sn的值分別是：0.0395，0.6780，0.0148，0.3696。因此，圖3(c)與用戶輸入圖形最為接近，與直觀感受相同。

除此之外，在每個相似圖形中，還標出了與用戶輸入圖形最接近的點，并在形似圖形的基礎上形成與用戶圖形最接近的圖形，方便用戶對檢索到的圖形做后續處理。

4.3 旋轉和平移特性

在檢索過程中，相似圖形的放置方式可能與用戶輸入圖形不一致，如圖4所示。

圖4 對比圖

圖4(a)表示圖形旋轉后，依然可以進行有效檢索。圖4(b)表示圖形經過平移后，依然可以進行有效檢索。

4.4 一般多邊形

為更加普遍的驗證該方法，現對一般多邊形[6]進行驗證。表1公布了各個圖形的Sn值，通過查閱此表，便可得出圖形和圖形之間的相似程度，從而判斷出是否為相同圖形。

表1 圖形Sn值之間相似程度比較

從表1可以看出，即使是相近的圖形，Sn值也相差較大，通過控制不同圖形之間Sn值之差，可以方便地控制檢索的近似度。

4.5 檢索性能分析

本文在cpu corei3；內存6G，window7的環境下進行測試，測試對象為100張機械圖紙，得到圖5的查準查全圖。其中縱坐標為查準率，橫坐標為查全率。

圖5 查準率、查全率全圖

5 總 結

在眾多基于圖形的檢索方法中，本方法的優勢在于對圖形的預處理較為簡單，檢索速度較快。但由于檢索指標較為單一，對于復雜圖形來說，檢索的準確率會有所降低。

本文提出的圖形檢索方法，通過一個圖形數組來描述圖形，然后相似圖形數組的數字特征來完成檢索。在檢索系統中，對于每個圖形僅僅需要存儲一個數組，大大節約了存儲成本，提高了檢索速度。另外，可以通過提高存儲在數據庫中的檢索數據的精確度和降低模糊查找系數來避免檢索數據重復的問題或實現精確檢索的目的。經過試驗，本方法的具有較高的可靠性和有效性。

[1]王林軍.基于STEP零件屬性圖形的檢索和對比研究[J].甘肅科學學報, 2007, 19(3): 96-99.

[2]沈蘭蓀, 張 菁, 李曉光.圖像檢索與壓縮域處理技術的研究[M].北京: 人民郵電出版社, 2008: 12.

[3]余 淼.基于內容的線畫圖形檢索研究進展[J].電腦知識與技術, 2008, 4(S2): 80-82.

[4]王 樺.基于分層和反饋技術的矢量圖形檢索研究[EB/OL].http://cdmd.cnki.com.cn/Article/CDMD-10335-2006033216.htm.2006.

[5]王炳忠.基于分層結構的矢量圖元檢索方法[J].浙江工業大學學報, 2008, 36(5): 499-508.

[6]夢祥輝.基于內角向量的二維圖形幾何相似性匹配方法[C]//2006年學術年會.西安: 西安電子科技大學, 2006.