基于四叉樹的矢量數(shù)據(jù)變化捕捉方法研究*

夏永華，張新長(zhǎng)，杜國(guó)明，郭泰圣

(中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院，廣東 廣州 510275)

我國(guó)基礎(chǔ)地理數(shù)據(jù)庫(kù)建設(shè)取得了巨大成績(jī)，為各類GIS 應(yīng)用工程提供了多比例尺的地理空間數(shù)據(jù)[1]。然而，隨著空間數(shù)據(jù)建設(shè)的逐步完成，人們逐漸意識(shí)到空間數(shù)據(jù)更新將代替空間數(shù)據(jù)獲取成為地理信息系統(tǒng)建設(shè)的瓶頸[2]，當(dāng)前地理信息系統(tǒng)研究的核心己從數(shù)據(jù)生產(chǎn)轉(zhuǎn)移到數(shù)據(jù)的更新，數(shù)據(jù)更新關(guān)系著地理信息系統(tǒng)的可持續(xù)發(fā)展[3]。

空間數(shù)據(jù)庫(kù)的更新模式一般包括增量式更新和版本式更新[4]。由于空間數(shù)據(jù)具有數(shù)據(jù)結(jié)構(gòu)復(fù)雜，數(shù)據(jù)量大的特點(diǎn)。采用增量式更新，能夠節(jié)省硬盤存儲(chǔ)，提高更新效率，對(duì)歷史數(shù)據(jù)進(jìn)行有效的管理。增量式更新以其方式靈活而且能夠更好的保證空間數(shù)據(jù)的現(xiàn)勢(shì)性的優(yōu)點(diǎn)，是未來空間數(shù)據(jù)庫(kù)更新的主要趨勢(shì)[5]?？臻g數(shù)據(jù)的變化捕捉過程是空間數(shù)據(jù)庫(kù)進(jìn)行增量式更新的首要環(huán)節(jié)[6-7]，也是近年來學(xué)術(shù)界研究的重點(diǎn)[8]，其精度和效率直接影響了數(shù)據(jù)庫(kù)更新的精度和效率。

目前主要的變化捕捉方法有快照差分法、時(shí)間戳法、觸發(fā)器法、日志法、API法等[9-11]。近年來，基于快照差分法的變化捕捉方法成為空間數(shù)據(jù)庫(kù)領(lǐng)域更新的主流，涌現(xiàn)了一系列的研究成果。文獻(xiàn)[12]對(duì)空間實(shí)體關(guān)系進(jìn)行研究分析，根據(jù)Egenhofer九交模型，提出基于基于自定義空間關(guān)系的空間查詢方法，進(jìn)行要素變化檢測(cè)。徐凱等[13]提出基于空間索引的搜索方法，利用基于規(guī)則網(wǎng)格的空間索引和基于對(duì)象的R樹家族索引進(jìn)行對(duì)象匹配，進(jìn)行變化信息檢測(cè)。而基于要素緩沖區(qū)疊加分析進(jìn)行搜索匹配的方法則是目前領(lǐng)域應(yīng)用中最為普遍的方法。然而這些變化檢測(cè)方法一般采用要素遍歷的方法，對(duì)于大范圍、多地物的矢量數(shù)據(jù)用遍歷法的運(yùn)算量很大，搜索效率低下，不能滿足實(shí)際的數(shù)據(jù)更新要求。本文在分析要素歷遍緩沖區(qū)疊加分析方法的基礎(chǔ)上，根據(jù)實(shí)際的工程化需求，提出基于四叉樹的變化捕捉方法，提高空間數(shù)據(jù)更新的效率。

1 緩沖區(qū)疊加分析變化捕捉機(jī)制研究

空間數(shù)據(jù)具有空間特征和屬性特征，通過要素歷遍，比較新舊版本要素的空間特征和屬性特征，采用幾何匹配的方法來對(duì)比新舊版本要素的要素變化情況[14]。根據(jù)匹配要素的結(jié)果要素變化類型可分為：新增、刪除、幾何信息修改、屬性信息修改、分解、合并、聚合[15]。具體關(guān)系如圖1。

圖1 要素匹配和變化類型之間的關(guān)系Fig.1 Relation between feature matching result and change type

緩沖區(qū)分析是地理信息系統(tǒng)重要和基本的空間操作功能之一。它是在給定空間對(duì)象或集合周圍建立一定距離(緩沖半徑)的多邊形實(shí)體，以確定這些物體對(duì)周圍環(huán)境的影響范圍或服務(wù)范圍[16]。對(duì)不同類型的目標(biāo)實(shí)體，所產(chǎn)生的緩沖區(qū)也不同。疊加分析則是地理信息系統(tǒng)最常用的提取空間隱含信息的手段之一?？臻g疊加分析是指在統(tǒng)一的空間參照系統(tǒng)條件下，把分散在不同層上的空間信息按相同的空間位置疊加到一起，產(chǎn)生新的特征(新的空間圖形或空間位置上的新屬性)的分析方法[17]，其結(jié)果綜合了原來兩層或多層地圖要素所具有的屬性。

通過對(duì)舊圖層要素進(jìn)行遍歷，建立舊要素緩沖區(qū)，并以此和新圖層進(jìn)行疊加分析，從而找到該舊要素的可能匹配的候選集，即利用舊要素的緩沖區(qū)，判斷目標(biāo)要素是否位于緩沖區(qū)內(nèi)，如是，則將目標(biāo)要素作為源要素的候選匹配要素，實(shí)現(xiàn)舊要素的粗匹配。并進(jìn)一步進(jìn)行要素精匹配，從而判斷舊要素變化類型。具體算法思路如下：

1)歷遍舊圖層要素，建立原要素的緩沖區(qū)，并通過空間查詢搜索與該要素緩沖區(qū)重疊的新要素。若搜索結(jié)果為空，則舊要素變化類型為1:0(刪除)的情況。

2)若搜索結(jié)果存在要素集，則歷遍要素集，建立的新要素的緩沖區(qū)，并搜索其區(qū)域重疊的舊要素圖層，并比較匹配要素的屬性信息，反復(fù)進(jìn)行則可以判定舊要素變化類型為1∶1(幾何修改、屬性修改、未變化),1∶M(分解),N∶1(合并),N∶M(聚合)的情況。

3)歷遍新圖層要素，建立新要素的緩沖區(qū)(buffer)，并搜索出與原要素?zé)o任何區(qū)域重疊的新要素。則為0:1(新增)的情況。

該算法思路簡(jiǎn)單直觀、易于理解，且精度較高，能夠準(zhǔn)確的搜索出新舊版本圖層的變化信息，確定要素的變化類型，建立精度較高的增量要素集，為后續(xù)數(shù)據(jù)更新打下基礎(chǔ)。然而該算法要求對(duì)新舊圖層的所有要素進(jìn)行多次要素歷遍，運(yùn)算量較大，使得更新效率較低，速度較慢，對(duì)硬件配置需求較高，并不能滿足工程化數(shù)據(jù)更新對(duì)于更新效率的要求。

2 基于四叉樹的變化捕捉方法研究

增量式更新側(cè)重獲取數(shù)據(jù)變化的增量信息，對(duì)圖層區(qū)域中不變區(qū)域進(jìn)行歷遍要素搜索匹配降低了增量信息提取的效率。在進(jìn)行歷遍要素搜索匹配之前，過濾掉不變區(qū)域會(huì)極大的提高變化捕捉的效率。本文結(jié)合實(shí)際，提出一種基于四叉樹的變化捕捉方法，根據(jù)四叉樹原理，對(duì)圖層進(jìn)行四叉樹剖分，計(jì)算區(qū)域內(nèi)的“節(jié)點(diǎn)-弧段”特征[18]，并進(jìn)行層次檢索，以快速定位到變化區(qū)域，再對(duì)該區(qū)域內(nèi)的要素進(jìn)行歷遍要素搜索匹配，確定其變化類型。從而大大減小歷遍要素次數(shù)，縮減計(jì)算量，提高變化捕捉的效率。

基于四叉樹的變化捕捉算法思路：

1)把更新數(shù)據(jù)中的所有對(duì)象集合的最小外接矩形區(qū)域作為四叉樹的根節(jié)點(diǎn)。

2)計(jì)算區(qū)域內(nèi)的空間要素的變化情況，要素的節(jié)點(diǎn)數(shù)與弧段數(shù)可以快速獲取，并對(duì)區(qū)域變化特征具有標(biāo)識(shí)作用。因此，本文結(jié)合要素的節(jié)點(diǎn)與弧段樹，提出區(qū)域要素變化特征評(píng)估模型：

F(Pf,Nf) =J(Pv,Nv)α1+H(Pe,Ne)α2

(1)

(2)

(3)

式(1)中，Pf，Nf分別為該區(qū)域范圍內(nèi)原數(shù)據(jù)和更新數(shù)據(jù)的集合，F(xiàn)(Pf,Nf)可反映要素的整體變化情況。Nv，Pv是新舊要素的結(jié)點(diǎn)集合。Ne，Pe為相應(yīng)的新舊弧段集合，也可表示為面圖層的邊界弧段集合。J(Pv,Nv)和H(Pe,Ne)分別用于表示區(qū)域內(nèi)新舊數(shù)據(jù)集的節(jié)點(diǎn)數(shù)與弧段長(zhǎng)度的變化情況。α1,α2表示結(jié)點(diǎn)變化指標(biāo)與弧段變化指標(biāo)所占的權(quán)重，取值在0-1之間且α1+α2=1。對(duì)于點(diǎn)圖層，由于無法計(jì)算弧段特征，故α2設(shè)為0。式(2)中，節(jié)點(diǎn)集的總數(shù)量通過函數(shù)Jcnt()來計(jì)算，式(3)中弧段集的總長(zhǎng)度通過Hlen()計(jì)算。

3)判斷區(qū)域內(nèi)數(shù)據(jù)是否發(fā)生變化。若F(Pf,Nf)的計(jì)算結(jié)果大于0說明該區(qū)域存在明顯的變化信息，需要進(jìn)行分割。分割的方法為：分別提取區(qū)域內(nèi)新舊要素重心的X，Y坐標(biāo)，并計(jì)算其均值PXa，PYa，NXa，NYa。以點(diǎn)((PXa+PYa)/2，(NXa+NYa)/2)為中心沿X軸，Y軸方向把原區(qū)域分劃為4個(gè)子區(qū)域。

4)重復(fù)執(zhí)行步驟2)、3)，直到劃分區(qū)域內(nèi)的要素?cái)?shù)目少于閾值為止。結(jié)束剖分后，記錄區(qū)域范圍及所包含的對(duì)象，以備進(jìn)行下一步對(duì)象的匹配。如圖2

圖2 四叉樹變化捕捉原理Fig.2 The principle of change detection on quad-tree

5)根據(jù)檢索出的變化區(qū)域，采用緩沖區(qū)疊加分析的方法進(jìn)行搜索匹配，進(jìn)行變化捕捉，確定要素變化類型。具體流程如圖3。

圖3 基于四叉樹的變化捕捉算法流程圖Fig.3 The flowchart of change detection based on quad-tree

該算法結(jié)合對(duì)象節(jié)點(diǎn)數(shù)和弧段長(zhǎng)度作為指標(biāo)快速檢測(cè)變化區(qū)域，利用四叉樹索引原理，對(duì)更新數(shù)據(jù)進(jìn)行分割，有助于數(shù)據(jù)的分步式并行處理，可以迅速定位變化區(qū)域。在數(shù)據(jù)量較大的矢量數(shù)據(jù)更新中，減少運(yùn)算量和內(nèi)存占用量，提高變化捕捉效率，以滿足工程化數(shù)據(jù)更新對(duì)于硬件配置和更新效率的需求。

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證算法實(shí)現(xiàn)效率，本文在Window系統(tǒng)下，利用Visual Studio 2008開發(fā)平臺(tái)，集成ArcEngine9.3進(jìn)行二次開發(fā)。系統(tǒng)分別實(shí)現(xiàn)要素歷遍和四叉樹變化捕捉兩種算法，以增城市1∶2 000矢量地形圖為示例數(shù)據(jù)，對(duì)比兩種算法的更新效率。如圖4。

實(shí)驗(yàn)選取點(diǎn)、線、面三種不同的幾何類型的地形圖數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分別進(jìn)行要素歷遍緩沖區(qū)疊加分析變化檢索和四叉樹變化捕捉實(shí)驗(yàn)，對(duì)比其消耗時(shí)間。實(shí)驗(yàn)結(jié)果如表1所示。

圖4 基于四叉樹的變化捕捉實(shí)驗(yàn)Fig.4 An experiment of change detection based on quad-tree

方法幾何類型更新要素個(gè)數(shù)平均計(jì)算時(shí)間/s歷遍要素檢索點(diǎn)56089四叉樹變化捕捉點(diǎn)56013歷遍要素檢索線1176327四叉樹變化捕捉線1176629歷遍要素檢索面98327654四叉樹變化捕捉面9835763

實(shí)驗(yàn)結(jié)果表明，四叉樹變化捕捉方法可以大幅度提高變化信息的檢測(cè)效率。矢量數(shù)據(jù)的屬性信息是存儲(chǔ)在二維表中，相對(duì)空間信息來說，較為容易檢索獲取，在對(duì)區(qū)域的“點(diǎn)-弧段”變化特征進(jìn)行計(jì)算時(shí)速度較快，能迅速定位至變化區(qū)域。在接下來的緩沖區(qū)疊加分析搜索匹配中，由于只對(duì)變化區(qū)域進(jìn)行要素搜索匹配，從而使得整個(gè)變化捕捉過程效率得到大幅提高。對(duì)于點(diǎn)要素，由于只需要計(jì)算節(jié)點(diǎn)的數(shù)目變化情況，無需衡量弧段的長(zhǎng)度變化情況。因此，計(jì)算效率提高得最明顯。對(duì)于線要素和面要素由于減少了對(duì)不變數(shù)據(jù)的搜索匹配與指標(biāo)計(jì)算，運(yùn)算效率也有大幅度的提高。特別是對(duì)于變化率較小的區(qū)域，算法的效率提高更明顯。在更新精度上，由于四叉樹變化捕捉在計(jì)算“點(diǎn)-弧段”變化特征時(shí)僅從幾何信息上進(jìn)行比較，忽略了幾何信息不變而屬性信息變化的情況，同時(shí)也忽略部分因矢量要素位移或旋轉(zhuǎn)等變化類型而使“點(diǎn)-弧段”不變的情況，使更新精度略低。

4 結(jié)論與展望

本文在分析要素歷遍變化捕捉方法的基礎(chǔ)上，從實(shí)際的空間數(shù)據(jù)更新需求出發(fā)，提出了基于四叉樹的變化捕捉方法。該方法通過“點(diǎn)-弧段”變化特征計(jì)算，進(jìn)行四叉樹分割快速定位到變化區(qū)域，使變化檢測(cè)更具有針對(duì)性，從而提高變化捕捉效率，滿足工程化數(shù)據(jù)更新的要求，為GIS的數(shù)據(jù)動(dòng)態(tài)更新提供有效的解決思路。最后通過開發(fā)系統(tǒng)對(duì)該理論方法進(jìn)行實(shí)現(xiàn)，結(jié)合實(shí)際更新數(shù)據(jù)進(jìn)行試驗(yàn)。試驗(yàn)結(jié)果也證明了該方法相比較于傳統(tǒng)的更新方式能大幅度夠提高變化捕捉的效率。

存在問題及下一步展望：四叉樹變化捕捉方法在計(jì)算變化特征時(shí)會(huì)忽略部分幾何信息不變而屬性信息變化的要素，造成精度略低，其次，部分要素由于發(fā)生位移或旋轉(zhuǎn)變化而導(dǎo)致區(qū)域的“點(diǎn)-弧段”特征沒有發(fā)生改變，從而忽略這種變化類型。另外，在要素搜索匹配中N:M的類型中，空間分割容易造成新舊要素處于不同的空間區(qū)域，影響更新結(jié)果。因此，下一步的研究工作包括： ① 添加對(duì)屬性信息變化的檢測(cè)，考慮部分幾何信息不變而屬性信息變化的要素，提高變化捕捉的精度。② 更為嚴(yán)密的考慮要素的變化類型。研究對(duì)于要素位移或旋轉(zhuǎn)等變化類型的有效檢測(cè)方法，從而提高變化捕捉的準(zhǔn)確度。③ 改進(jìn)變化區(qū)域的分割方法，把具有集聚特征的新舊要素更有效地劃分在同一區(qū)域，減少區(qū)域邊界對(duì)變化捕捉的影響。

參考文獻(xiàn)：

[1] 陳軍. 論數(shù)字化地理空間基礎(chǔ)框架的建設(shè)與應(yīng)用[J]. 測(cè)繪工程, 2002, (03): 1-6.

[2] UITERMARK H T，VAN OOSTEROM P J M，MARS N J I．Propagating updates: Finding corresponding objects in a multi-source environment[C]// Proceedings of the 8th International Symposium on Spatial Data Handling, Vancouver, Canada, 1998：580-591.

[3] FRITSCH D. GIS data revision-visions and reality[C]//Note speech in joint ISPRS commission workshop on dynamic and multi-dimensional GIS. Beijing:NGCC,1999.

[4] 熊湘琛, 張新長(zhǎng), 曹凱濱. 城市基礎(chǔ)地形數(shù)據(jù)增量更新研究[J]. 測(cè)繪通報(bào), 2009, (03): 24-26.

[5] 孫英杰. 基于變化信息文件的增量更新方法研究 [D]. 長(zhǎng)沙: 中南大學(xué), 2008.

[6] 李德仁. 利用遙感影像進(jìn)行變化檢測(cè)[J]. 武漢大學(xué)學(xué)報(bào):信息科學(xué)版, 2003, (S1): 7-12.

[7] 張劍清, 朱麗娜, 潘勵(lì). 基于遙感影像和矢量數(shù)據(jù)的水系變化檢測(cè)[J]. 武漢大學(xué)學(xué)報(bào):信息科學(xué)版, 2007, (8): 663-666.

[8] 張新長(zhǎng),郭泰圣,唐鐵. 一種自適應(yīng)的矢量數(shù)據(jù)增量更新方法研究[J]. 測(cè)繪學(xué)報(bào),2012,41(4):613-619.

[9] 鐘巧華. 數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)抽取技術(shù)研究[J]. 計(jì)算機(jī)工程, 2004, (S1): 62-63.

[10] 章水鑫, 徐宏炳, 于立. 增量式ETL工具的研究與實(shí)現(xiàn)[J]. 現(xiàn)代計(jì)算機(jī):專業(yè)版, 2005, (03): 6-10.

[11] 劉偉, 佟俐鵑. 異構(gòu)數(shù)據(jù)庫(kù)集成中的變化捕獲方案設(shè)計(jì)[J]. 計(jì)算機(jī)應(yīng)用研究, 2005, (07): 213-215.

[12] 吳建華, 傅仲良. 數(shù)據(jù)更新中要素變化檢測(cè)與匹配方法[J]. 計(jì)算機(jī)應(yīng)用, 2008, (06): 1612-1615.

[13] 徐凱. 基于網(wǎng)格索引的幾何匹配算法研究[D]. 長(zhǎng)沙: 中南大學(xué), 2009.

[14] 萬遠(yuǎn), 李霖, 應(yīng)申. 地理信息數(shù)據(jù)變化檢測(cè)系統(tǒng)的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程, 2010, (09): 4-6+13.

[15] 王育紅, 陳軍. GIS客戶數(shù)據(jù)庫(kù)更新的基本問題[J]. 地理信息世界, 2008, (01): 5-12.

[16] 湯國(guó)安, 楊昕. ArcGIS地理信息系統(tǒng)空間分析實(shí)驗(yàn)教程[M].2版.北京:科學(xué)出版社, 2012, 153.

[17] 黃杏元, 馬勁松, 湯勤. 地理信息系統(tǒng)概論[M].修訂版. 北京: 高等教育出版社, 2001.

[18] CHENG C, LU F, CAI J A. Quantitative scale-setting approach for building multi-scale spatial databases[J]. Computers and Geosciences, 2009, 35(11): 2204-2209.