基于OBB包圍盒的圖形檢測(cè)算法

張 敏，鄭 哲，林君強(qiáng)

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

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

1 圖形對(duì)象的特殊性

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

表1 圖形對(duì)象的特殊性

2 圖形檢測(cè)的方法

2.1 圖形檢測(cè)包圍盒

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

圖1 包圍盒類別

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

2.2 OBB包圍盒理論

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

(1)

(2)

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

(3)

(4)

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

圖2 擴(kuò)展m距離后的包圍盒范圍

2.3 圖形檢測(cè)方法

2.3.1 同名點(diǎn)匹配檢測(cè)

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

圖3 房屋

依比例尺圖形對(duì)象檢測(cè)時(shí)須提取Closed值，值為1代表圖形封閉，值為0代表圖形不封閉。

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

2.3.2 以繪點(diǎn)順序?yàn)闇?zhǔn)的檢測(cè)

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

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

圖4 不同繪點(diǎn)順序生成的圖形

3 圖形檢測(cè)算法

3.1 圖形檢測(cè)算法實(shí)現(xiàn)

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

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

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

3.2 算法改進(jìn)

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

圖5 圖形對(duì)象的多語義

143301=143400,143302,143410

……

end

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(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屏幕分辨率。

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

圖6 圖形檢索情況

4.1 檢測(cè)時(shí)間分析

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

圖7 時(shí)間點(diǎn)圖

4.2 檢測(cè)結(jié)果的準(zhǔn)確性分析

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

圖8 圖形檢測(cè)的準(zhǔn)確率統(tǒng)計(jì)

5 結(jié)論

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