基于特征點(diǎn)的圖形檢索研究

唐 濤，高滿屯，何 波

（西北工業(yè)大學(xué)機(jī)電學(xué)院，陜西 西安710072）

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

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

1 圖形基準(zhǔn)的確定

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

1.1 圖形基準(zhǔn)點(diǎn)的確定

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

1.2 圖形基準(zhǔn)向量的確定

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

2 特征點(diǎn)的規(guī)范化

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

其中，表示基準(zhǔn)向量，表示型心與各個(gè)特征點(diǎn)構(gòu)成的向量。則基準(zhǔn)向量與向量的角度值為cos∠ACdB，向量的模為，則特征點(diǎn)A對(duì)應(yīng)于特征點(diǎn)B對(duì)應(yīng)于特征點(diǎn)C對(duì)應(yīng)于特征點(diǎn)D對(duì)應(yīng)于

圖1 型心與特征點(diǎn)的示意圖

3 數(shù)據(jù)的處理

3.1 圖形數(shù)組

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

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

3.2 圖形數(shù)組的規(guī)范化

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

其中m>=n

其中，函數(shù)min返回?cái)?shù)組中最小元素的被減數(shù)。則規(guī)范化后的Vector2如公式(13)所示。

3.3 檢索參數(shù)

在圖形數(shù)組的數(shù)字特征可以很好的將圖形數(shù)組的整體特性表示出來(lái)，即標(biāo)準(zhǔn)差Sn。標(biāo)準(zhǔn)差Sn描述的是圖形數(shù)組元素的緊湊性。標(biāo)準(zhǔn)差可以通過(guò)式(14)求得。當(dāng)差Sn在給定的模糊查找系數(shù)δ范圍內(nèi)時(shí)，向用戶返回檢索結(jié)果。

4 實(shí)驗(yàn)

4.1 選取相似點(diǎn)

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

輸入圖形特征點(diǎn)的坐標(biāo)是(0 2 2 4 4 20 20 4 4 2 2 0; 2 2 0 0 2 2 4 4 6 6 4 4);

相似圖形特征點(diǎn)的坐標(biāo)是(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 兩個(gè)圖形對(duì)比

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

4.2 檢索圖形

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

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

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

近似圖形3(圖3(c))的特征點(diǎn)為(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))的特征點(diǎn)為(0 20 45 30 45 20 0; 5 5 0 7 14 9 9)。

圖3 相似圖形與輸入圖形

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

除此之外，在每個(gè)相似圖形中，還標(biāo)出了與用戶輸入圖形最接近的點(diǎn)，并在形似圖形的基礎(chǔ)上形成與用戶圖形最接近的圖形，方便用戶對(duì)檢索到的圖形做后續(xù)處理。

4.3 旋轉(zhuǎn)和平移特性

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

圖4 對(duì)比圖

圖4(a)表示圖形旋轉(zhuǎn)后，依然可以進(jìn)行有效檢索。圖4(b)表示圖形經(jīng)過(guò)平移后，依然可以進(jìn)行有效檢索。

4.4 一般多邊形

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

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

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

4.5 檢索性能分析

本文在cpu corei3；內(nèi)存6G，window7的環(huán)境下進(jìn)行測(cè)試，測(cè)試對(duì)象為100張機(jī)械圖紙，得到圖5的查準(zhǔn)查全圖。其中縱坐標(biāo)為查準(zhǔn)率，橫坐標(biāo)為查全率。

圖5 查準(zhǔn)率、查全率全圖

5 總 結(jié)

在眾多基于圖形的檢索方法中，本方法的優(yōu)勢(shì)在于對(duì)圖形的預(yù)處理較為簡(jiǎn)單，檢索速度較快。但由于檢索指標(biāo)較為單一，對(duì)于復(fù)雜圖形來(lái)說(shuō)，檢索的準(zhǔn)確率會(huì)有所降低。

本文提出的圖形檢索方法，通過(guò)一個(gè)圖形數(shù)組來(lái)描述圖形，然后相似圖形數(shù)組的數(shù)字特征來(lái)完成檢索。在檢索系統(tǒng)中，對(duì)于每個(gè)圖形僅僅需要存儲(chǔ)一個(gè)數(shù)組，大大節(jié)約了存儲(chǔ)成本，提高了檢索速度。另外，可以通過(guò)提高存儲(chǔ)在數(shù)據(jù)庫(kù)中的檢索數(shù)據(jù)的精確度和降低模糊查找系數(shù)來(lái)避免檢索數(shù)據(jù)重復(fù)的問(wèn)題或?qū)崿F(xiàn)精確檢索的目的。經(jīng)過(guò)試驗(yàn)，本方法的具有較高的可靠性和有效性。

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

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

[3]余 淼.基于內(nèi)容的線畫(huà)圖形檢索研究進(jìn)展[J].電腦知識(shí)與技術(shù), 2008, 4(S2): 80-82.

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

[5]王炳忠.基于分層結(jié)構(gòu)的矢量圖元檢索方法[J].浙江工業(yè)大學(xué)學(xué)報(bào), 2008, 36(5): 499-508.

[6]夢(mèng)祥輝.基于內(nèi)角向量的二維圖形幾何相似性匹配方法[C]//2006年學(xué)術(shù)年會(huì).西安: 西安電子科技大學(xué), 2006.