張 敏，鄭 哲，林君強

(1.福建信息職業(yè)技術學院建筑工程系，福建 福州 350003;2.福建省地質(zhì)測繪院，福建 福州 350011)

眾多學者在基礎地理信息數(shù)據(jù)領域中對圖形檢測的方法進行了大量研究，車秋鋒對4D產(chǎn)品的檢測進行綜合性功能設計[1]，蔡建德、何鑫星等人設計圖形精度檢查系統(tǒng)[2-3]，伍素貞等人基于AutoCAD和RTK進行數(shù)學精度檢測[4]。這些圖形檢測方法中更多關注的是數(shù)學信息，而忽略對象的圖形特征和屬性問題，必須人工逐一查看圖形的繪制方法、圖形的表達、圖形的屬性是否正確。這種人工檢測的方式能夠保證檢測的準確性，但是檢測效率較低。包圍盒是一種求解離散點集最優(yōu)包圍空間的算法，較多地用于圖形的碰撞檢測中，利用體積略大而幾何特性簡單的包圍盒近似地描述相對復雜的虛擬對象，以剔除大量不可能產(chǎn)生碰撞的物體對象[5-7]。因此本文基于包圍盒的思路，在圖形對象特性的基礎上探索一種既能保證檢測的準確性又能保證檢測效率的圖形快速檢索算法。

1 圖形對象的特殊性

在基礎地理信息領域，圖形對象主要劃分為8大類，依據(jù)地物的大小或長寬是否跟隨比例尺的變化而變化的特征，本文將圖形檢索的對象類別劃分為：不依比例尺對象、半依比例尺對象、依比例尺對象。每一個圖形對象都由多個圖形要素組合而成，不依比例尺圖形對象內(nèi)部封裝成點狀，一般以塊的形式存在；半依比例尺圖形對象內(nèi)部封裝成線狀；依比例尺圖形對象內(nèi)部封裝成面狀。從數(shù)據(jù)類別來看，所有類別的圖形對象的特征一般包含幾何特征和屬性特征，幾何特征側重從數(shù)學方面進行描述，屬性特征側重用文字表述型數(shù)據(jù)進行描述，除了幾何特征和屬性特征以外，還應該要關注圖形對象本身存在的特殊的圖形特征。因此在進行圖形檢測時按照不同對象類別進行檢測，每個圖形對象遍歷其圖形要素組成，而在檢測過程中同時注意不同類別圖形對象的特殊性(表1)，主要集中在圖形對象的旋轉性、指向性、封閉性，其中部分不依比例尺圖形對象具有旋轉特征；半依比例尺圖形對象中的復合圖形不同的繪制順序具有不同的指向性；依比例尺圖形對象是首尾相連的線，在圖形檢測時應考慮圖形對象的封閉性。

表1 圖形對象的特殊性

2 圖形檢測的方法

2.1 圖形檢測包圍盒

傳統(tǒng)的圖形檢測是采用統(tǒng)一的網(wǎng)格劃分或者定義固定大小的盒子進行算法實現(xiàn)，這種算法實現(xiàn)簡單、可操作性強，但沒有考慮圖形對象的完整性，極易造成圖形對象的分割或不完整，并且因無法評估圖形對象的大小，網(wǎng)格尺寸和盒子大小一般設計較大，圖形檢測的搜索范圍也就較大。為了保證圖形對象的完整性和檢測效率，需要定義一個合適大小的物體來包裹圖形對象。包圍盒的基本思想就是利用某種形狀簡單的幾何體來緊密包裹對象物體[8-14]。幾何體常常是球體或長方體，因此本文借鑒包圍盒的思路來探究圖形檢測的方法，由于基礎地理信息領域的研究對象是二維平面圖形，本文采用圓形、矩形包圍盒(圖1)，其中矩形包圍盒分為軸對齊包圍盒(axially aligned bounding box,AABB)[15-16]和有向包圍盒((oriented bounding box, OBB)[17-21]。

圖1 包圍盒類別

從圖1中可以看出，圓形包圍盒和AABB包圍盒有較大的空間縫隙，造成空間冗余，為了有效地利用內(nèi)存空間，并考慮到對象的圖形特征，本文確定基于OBB包圍盒進行圖形檢測。

2.2 OBB包圍盒理論

Ci,j=Cov(xi,yj)=E[(xi-ui)(yi-uj)]i,j=1,2,…,n

(1)

(2)

之后將坐標點投影到方向向量上，找到x、y分量在每個方向上的最大值和最小值，記為vkmin、vkmax，k=0,1，由式(3)可得包圍盒的中心，由式(4)可得包圍盒半長。

(3)

(4)

以上方法得到的是圖形對象的最小OBB包圍盒，由于檢測圖形和被檢測圖形之間允許存在一定的誤差，本文設置誤差參數(shù)為m(單位：m)，將生成的最小OBB包圍盒沿著軸方向向外擴展m距離，進而得到圖形檢測的包圍盒范圍(圖2)，圖2中虛線為生成的最小包圍盒范圍，實線為擴展m距離后的包圍盒范圍，擴展后的范圍即為圖形檢測的搜索范圍。

圖2 擴展m距離后的包圍盒范圍

2.3 圖形檢測方法

2.3.1 同名點匹配檢測

同名點匹配即基于相同的坐標和屬性進行匹配。以房屋為例(圖3)，按照2.2講述的方法建立圖形檢測范圍，由于在建立圖形檢測范圍時已經(jīng)提取了圖形對象的坐標序列(x1,y1),(x2,y2),...,(x8,y8)和屬性信息，則進入被檢測圖幅時將鼠標指針逐點定位到相應的坐標位置上，在范圍內(nèi)搜索離原坐標點最近、屬性一致的圖形對象。該方法適合所有圖形對象的檢測，尤其是常規(guī)的圖形對象。

圖3 房屋

依比例尺圖形對象檢測時須提取Closed值，值為1代表圖形封閉，值為0代表圖形不封閉。

不依比例尺圖形對象的基點位置有中心和非中心的區(qū)別。在進行圖形檢測時鼠標指針直接定位到該對象的基點位置(對于基點在中心的則直接定位到包圍盒中心)，搜索距離基點最近、屬性一致、angle值(旋轉角，誤差允許范圍假設為5°)一致的圖形對象，angle值根據(jù)包圍盒的2個主方向得到。

2.3.2 以繪點順序為準的檢測

主要針對半依比例尺圖形對象中的復合圖形，該類復合圖形對象通過繪點順序和坐標判斷圖形的繪制方向和開角方向。以圍墻為例，如圖4(a)所示，在圖形檢測范圍內(nèi)首先按照順序提取架構線坐標(x1,y1),(x2,y2)，依據(jù)繪點順序和坐標判定繪制方向，此時計算圍墻邊線的坐標和架構線坐標的差值，大于0則圍墻邊線沿著方向生成在架構線的左邊，小于0則圍墻邊線沿著方向生成在架構線的右邊，這種規(guī)則我們稱之為“左+右-”，以此來判定此類圖形對象的指向性。

對于開角方向驗證，圖4(b)為無開角短線的懸空通廊，按照繪點順序，1—2點連線為對象邊線，開角在2—3點間，不同繪點順序，開角方向不同，上圖表示指向南北為通行方向，下圖表示指向東西為通行方向；圖4(c)為無開角短線的臺階類，開角在起-閉點間，開角方向與繪點順序無關，只與起、閉點的位置有關；圖4(d)為有開角短線的復合圖形對象比如人行橋，按照繪點順序，1—2點連線為對象邊線，開角在2—3點間，開角指向含義與懸空通廊相同，但開角短線方向略有不同，左圖為正確開角的人行橋，右圖為錯誤開角的人行橋，正確開角的繪點順序應是按照順時針方向進行。因此在此類圖形對象檢測時，讀取每個對象的繪點順序、坐標確定對象邊線、開角方向、開角短線方向。

圖4 不同繪點順序生成的圖形

3 圖形檢測算法

3.1 圖形檢測算法實現(xiàn)

1)所有的檢測對象按照對象類別創(chuàng)建對象列表Objcetlist[j]和屬性列表Attributelist[j]，其中j=0表示是不依比例尺對象列表，j=1表示是半依比例尺對象列表，j=2表示是依比例尺對象列表。每個檢測對象均按照繪點順序號提取坐標序列(xi,yi)。以下以某一個檢測對象為例進行說明。

4)協(xié)方差矩陣對角化，由CP=λP求解C的特征值λ以及對應特征值λ的特征向量P，滿足PCPT=λ，λ為對角矩陣。取最大特征值對應的特征向量作為OBB包圍盒的方向，該特征向量就是OBB包圍盒的坐標軸，假設為M。

7)進入被檢圖幅開始檢測，首先定位到該檢測對象的圖形檢測范圍內(nèi)進行檢索，判斷哪些圖形對象落在包圍盒內(nèi)，落在包圍盒內(nèi)的圖形對象均將被檢索并分別創(chuàng)建檢測列表Checklist[j]，保存其坐標集合；根據(jù)提取的圖形對象屬性信息Attributelist[j]確定進一步可能的圖形對象集合Object_Checklist[j]。之后根據(jù)檢測對象的坐標序列按照同名點匹配的方法逐點進行坐標匹配，此時離檢測對象坐標點最近、屬性一致的圖形將被檢索到。特別地，j=0的，搜索距離基點最近、屬性一致、angle在符合范圍內(nèi)的圖形對象；j=1的，根據(jù)繪點順序和坐標判斷圖形的生成方向或開角方向；j=2的，提取closed是否為1。

3.2 算法改進

3.1小節(jié)中通過檢測對象的屬性信息來確定被檢測的圖形對象是否符合檢測條件，但圖形對象存在多語義問題，如圖5所示，以臺階為例，該圖形對象在實際中既可以表示臺階，也可以表示室外樓梯，若有邊亦可表示成有邊臺階；對于不規(guī)則的臺階，圖形對象可表示成臺階、室外樓梯或不規(guī)則樓梯，此時同一對象有不同的表示方法，也就有了不同的屬性信息，造成圖形對象的多語義問題。顯然按照檢測圖形對象的屬性信息進行圖形檢測，必然造成匹配結果不完整，可能丟失部分圖形對象。因此對上述圖形檢測算法進行改進，事先創(chuàng)建屬性匹配文件，在進入被檢圖幅時，預先讀取屬性匹配文件，在進行圖形檢索時遍歷該文件，以便更為完善地進行圖形檢測。屬性匹配文件格式如下：

圖5 圖形對象的多語義

143301=143400,143302,143410

……

end

4 實驗結果

實驗環(huán)境：Microsoft Windows 7 操作系統(tǒng)，Intel(R) Core(TM)i5-3230 CPU @2.60 GHz處理器，NVIDIA GeForce 610 M顯卡，4.00 GB內(nèi)存，1 366×768屏幕分辨率。

實驗情況：在檢索圖幅中確定10個檢索的圖形對象對100個圖幅進行檢索，因篇幅有限，圖6中僅列出其中一個圖形對象的檢索情況，為了圖形顯示更直觀在±m(xù)誤差位置各生成一條控制邊界，實線是+m誤差的控制線，虛線是-m誤差的控制線。從檢索情況來看，情形1檢索出的圖形對象在[-m,+m]控制范圍內(nèi)，情形2檢索出的圖形對象其中一個角點超出+m的范圍，情形3檢索出的圖形對象超出+m的范圍，情形4檢索出的圖形對象超出-m的范圍。

圖6 圖形檢索情況

4.1 檢測時間分析

應用Matlab對算法的執(zhí)行效率進行測試，System函數(shù)直接調(diào)用程序執(zhí)行，利用tic、toc組合函數(shù)計算每一次程序循環(huán)執(zhí)行的時間，統(tǒng)計每一幅圖的檢測時間繪制時間離散點圖。圖7(a)的時間離散點圖中平均每一幅圖的檢測時間為9.746 s，圖7(b)的殘差圖中可看出基本上時間殘差控制在[-5 s,+5 s]，但是存在幾個異常點，其主要原因在于圖形檢測時未匹配到相關圖形對象，導致程序在遍歷屬性匹配文件，直到遍歷結束為止，但每一幅圖的檢測時間基本控制在20 s以內(nèi)[22]。

圖7 時間點圖

4.2 檢測結果的準確性分析

采用人工檢測的方式，在排除人為因素(如人為錯誤采集檢測圖形對象的標準點、檢測點數(shù)據(jù)等)的前提下，人工檢測能保證100%的準確率；而基于動態(tài)包圍盒的圖形檢測算法進行圖形檢測的準確率如圖8所示，基本上圖形檢測的準確率能達到70%以上，最高達到100%，也存在部分圖形檢測準確率較低，最低為20%，其原因在于圖形存在多語義問題，容易造成計算機誤判，因此應事先編輯屬性匹配文件，若編碼文件較為全面、完善，可確保檢測結果的準確性。

圖8 圖形檢測的準確率統(tǒng)計

5 結論

從實驗結果來看，使用基于動態(tài)包圍盒的圖形檢索算法進行圖形檢測能大大提高圖形檢測的效率，但是初始使用該算法，由于圖形屬性匹配文件考慮不足，圖形檢測結果的準確性尚不如人意，對于計算機誤判的圖形需要人工進行糾錯，因此初始使用建議“算法+人工”的方式既保證了圖形檢測的效率又保證了圖形檢測的準確性，不過隨著圖形屬性匹配文件的不斷完善，該算法的圖形檢測結果會越來越可靠。同時圖形有比例尺之分，但是該算法卻不受比例尺的限制，只要標準圖幅和受檢圖幅比例尺一致即可完成圖形檢測。