基于獨(dú)立單元的高精度曲面建模方法

空間插值方法廣泛應(yīng)用于gis和3d成像系統(tǒng)的路塹建模。通常使用ksig、idw、spline、自然elephone等方法。它的精度一直是研究的重點(diǎn)。Robinson等的研究表明,這些方法計(jì)算結(jié)果的精度相當(dāng),均方根誤差值(RMSE)接近。Chaplot等認(rèn)為,當(dāng)采樣點(diǎn)密度很高時(shí)(實(shí)驗(yàn)采樣率最高為9692×106/km2),這些方法的精度沒(méi)有明顯差異,與模擬區(qū)域、采樣數(shù)據(jù)的變異性和數(shù)據(jù)的空間結(jié)構(gòu)無(wú)關(guān);而當(dāng)采樣點(diǎn)密度、數(shù)據(jù)空間結(jié)構(gòu)和數(shù)據(jù)變異性發(fā)生變化時(shí),這些方法的精度會(huì)有所差異。George等提出了適應(yīng)性的IDW方法,數(shù)據(jù)交叉驗(yàn)證表明該方法的精度優(yōu)于定參數(shù)的IDW方法。即使采樣數(shù)據(jù)的空間結(jié)構(gòu)無(wú)法以函數(shù)關(guān)系進(jìn)行描述時(shí),其精度也高于普通Kriging方法。高精度曲面建模(HASM)方法是以微分幾何的曲面論為基礎(chǔ),根據(jù)曲面的決定因素——第一、二類基本量,在Gauss-Codazzi曲面方程的約束下進(jìn)行建模[4,5,6,7,8,9,10,11,12,13,14]。所完成的數(shù)據(jù)實(shí)驗(yàn)表明,高精度曲面建模方法HASM具有比Kriging、IDW、Spline和TIN等GIS傳統(tǒng)空間插值方法更高的模擬精度。1有限元方程的最小二乘根據(jù)微分幾何中曲面論,空間曲面由其第一基本形式和第二基本形式唯一確定,曲面的第一類基本量和第二類基本量可以唯一確定一個(gè)空間曲面。而Gauss-Codazzi方程是曲面的第一類基本量和第二類基本量必須滿足的相容方程。高精度曲面建模方法(HASM)前期的計(jì)算模型是以位于網(wǎng)格上的采樣點(diǎn)數(shù)據(jù)作為約束條件,對(duì)計(jì)算域內(nèi)的網(wǎng)格點(diǎn)數(shù)據(jù)進(jìn)行求解。在實(shí)際計(jì)算過(guò)程中,HASM的數(shù)值模擬問(wèn)題被轉(zhuǎn)化為等式約束的最小二乘問(wèn)題來(lái)求解。從高斯曲面方程的有限差分形可知,在一個(gè)獨(dú)立的5×5格網(wǎng)數(shù)據(jù)的單元內(nèi),可建立3+U個(gè)約束條件,解算模型系數(shù)陣的最高階數(shù)也為3+U。U為計(jì)算域網(wǎng)格化后,計(jì)算單元內(nèi)位于網(wǎng)格上的實(shí)際采樣數(shù)據(jù)點(diǎn)數(shù)(0≤U≤9),其最大值為9(即獨(dú)立計(jì)算單元上所有采樣點(diǎn)都位于網(wǎng)格上,在這種情況下,單元內(nèi)的網(wǎng)格點(diǎn)數(shù)據(jù)不需要進(jìn)行求解)。計(jì)算模型對(duì)位于單元中心的9個(gè)網(wǎng)格點(diǎn)數(shù)據(jù)進(jìn)行求解;而單元邊界上的12個(gè)網(wǎng)格數(shù)據(jù)只是參與曲面基本量的計(jì)算,如圖1所示。對(duì)于一個(gè)獨(dú)立計(jì)算單元而言,其解算方程的最高階數(shù)不超過(guò)12;整個(gè)計(jì)算區(qū)域內(nèi)所能建立的數(shù)值方程組,由區(qū)域中所有的計(jì)算單元列立的方程組成。按上述方法計(jì)算的結(jié)果,在滿足Gauss-Codazzi曲面方程和實(shí)際采樣約束下,與實(shí)際曲面偏離最小。隨著計(jì)算區(qū)域的增大,計(jì)算區(qū)域內(nèi)所形成的計(jì)算單元數(shù)將快速增加,其數(shù)量約為15×(n-1)×(m-1)+n×m≈16n×m(n,m為區(qū)域橫向及縱向不重疊單元個(gè)數(shù)),待解算的方程個(gè)數(shù)也增為48×n×m+k(k為高精度的實(shí)測(cè)點(diǎn)個(gè)數(shù))。當(dāng)處理區(qū)域規(guī)模較大時(shí),對(duì)所有的數(shù)值方程進(jìn)行整體求解將變得十分困難。2計(jì)算方法的時(shí)間復(fù)雜度HASM-AD的計(jì)算過(guò)程中采用新的方法,在不損失模擬結(jié)果精度的同時(shí),降低計(jì)算過(guò)程中對(duì)計(jì)算資源的占用,降低算法的時(shí)間復(fù)雜度,提高計(jì)算速度。對(duì)大型數(shù)值方程組求解一般可通過(guò)分組,將其分割為多個(gè)小型方程組進(jìn)行解算。數(shù)據(jù)平差理論中的逐次最小二乘估計(jì)正是利用矩陣分塊法則,將數(shù)值方程分為兩組或多組,對(duì)各分組內(nèi)的方程進(jìn)行求解。對(duì)每個(gè)分組求取解向量,并將其作為虛擬觀測(cè)值;對(duì)下一分組方程進(jìn)行解算,得到后續(xù)解,直至方程的最終解;而分組解算的結(jié)果與整體解算的結(jié)果相同。如圖2所示,在指定的計(jì)算域中,所有16個(gè)分組的中心起始坐標(biāo)位于圖中標(biāo)注圓圈的16個(gè)格網(wǎng)點(diǎn)上。而在同一分組中,相鄰的計(jì)算單元中心間隔相同,因此,可以根據(jù)每個(gè)分組中起始單元的中心位置和偏移量對(duì)整個(gè)分組中的單元進(jìn)行處理。圖2中標(biāo)注三角形的格網(wǎng)點(diǎn),為同一分組中相鄰計(jì)算單元的中心位置。對(duì)每個(gè)分組的求解可簡(jiǎn)化為對(duì)該分組內(nèi)各個(gè)獨(dú)立計(jì)算單元的求解,與分組內(nèi)各計(jì)算單元的解向量線性無(wú)關(guān)。因此,HASM-AD方法在計(jì)算過(guò)程中,無(wú)需將所有數(shù)值方程的計(jì)算數(shù)據(jù)輸入計(jì)算機(jī),而是以獨(dú)立計(jì)算單元為單位進(jìn)行實(shí)時(shí)讀取、處理,從而大幅降低計(jì)算過(guò)程中對(duì)內(nèi)存空間的占用。對(duì)每個(gè)分組的解算,被轉(zhuǎn)化為對(duì)該分組中所有獨(dú)立單元的計(jì)算。對(duì)整個(gè)區(qū)域的模擬,可按圖2所示的分組方法,轉(zhuǎn)化為對(duì)16個(gè)分組的逐次求解。HASM-AD的模擬過(guò)程可根據(jù)上述的分組原則對(duì)計(jì)算域進(jìn)行分組解算。HASM-AD算法在模擬過(guò)程中,對(duì)計(jì)算方程進(jìn)行分組處理,其計(jì)算時(shí)間應(yīng)為所有分組處理時(shí)間之和,而每個(gè)分組的計(jì)算時(shí)間等于該分組內(nèi)所有獨(dú)立計(jì)算單元的處理時(shí)間之和。因此,HASM-AD算法的計(jì)算時(shí)間應(yīng)為模擬區(qū)域中所有計(jì)算單元的處理時(shí)間之和,即T=∑i=1NtiΤ=∑i=1Νti(N為模擬區(qū)域所有計(jì)算單元數(shù)目,ti為第i個(gè)計(jì)算單元的處理時(shí)間)。所有計(jì)算單元法方程的秩沒(méi)有太大差異,處理時(shí)間接近,算法的時(shí)間復(fù)雜度為O(N)。對(duì)于一個(gè)m×n的區(qū)域,其中所包含的計(jì)算單元數(shù)N≈(m×n)/16。因此,HASM-AD算法的時(shí)間復(fù)雜度與模擬區(qū)域的格網(wǎng)點(diǎn)數(shù)相關(guān),為O(n)(n為計(jì)算區(qū)域中所包含的格網(wǎng)數(shù))。與高精度曲面建模方法(HASM)前期所使用的整體迭代算法相比(時(shí)間復(fù)雜度一般為O(n3)),HASM-AD方法顯著降低了計(jì)算的時(shí)間復(fù)雜度。使用不同計(jì)算區(qū)域、不同規(guī)模的數(shù)據(jù)對(duì)該方法的時(shí)間復(fù)雜度進(jìn)行驗(yàn)證,采用SPSS統(tǒng)計(jì)分析軟件對(duì)數(shù)據(jù)規(guī)模及計(jì)算時(shí)間進(jìn)行了線性和二次回歸分析,如表1、表2所示。從表2可看出,雖然二次曲線模型的擬合精度要高于線性模型,但二次曲線模型中時(shí)間消耗的回歸系數(shù)數(shù)值極小且為負(fù)值,這與實(shí)際情況不符合,因此,二次曲線模型不可采納。數(shù)據(jù)實(shí)驗(yàn)證明,該方法的時(shí)間復(fù)雜度與模擬區(qū)域的格網(wǎng)點(diǎn)數(shù)相關(guān),為O(n)(n為計(jì)算區(qū)域中所包含的格網(wǎng)數(shù))。HASM-AD方法將整體求解轉(zhuǎn)化為對(duì)所有計(jì)算單元的逐次計(jì)算,降低了計(jì)算的時(shí)間復(fù)雜度。同時(shí)計(jì)算過(guò)程是基于解向量相互獨(dú)立的計(jì)算單元,因此,在實(shí)際計(jì)算中,無(wú)需為所有計(jì)算數(shù)據(jù)開辟存儲(chǔ)空間,而只需將當(dāng)前處理單元導(dǎo)入內(nèi)存即可。采用實(shí)時(shí)讀取方法對(duì)數(shù)據(jù)進(jìn)行動(dòng)態(tài)操作,則在計(jì)算過(guò)程中空間復(fù)雜度與數(shù)據(jù)規(guī)模無(wú)關(guān)。理論上該方法的空間復(fù)雜度為O(1)。但為了提高處理效率,實(shí)際編程中,設(shè)立了數(shù)據(jù)緩沖區(qū)以降低頻繁讀取數(shù)據(jù)。故該方法的實(shí)際空間復(fù)雜度與數(shù)據(jù)緩沖區(qū)的大小相關(guān),在最不利的情況下為O(n√)Ο(n)。3數(shù)據(jù)篩選和結(jié)果分析3.1分辨率模擬結(jié)果精度檢驗(yàn)空間插值方法的精度通常使用交叉驗(yàn)證的方法進(jìn)行檢驗(yàn),它能有效地消除冗余數(shù)據(jù)信息。對(duì)于空間插值的所有采樣數(shù)據(jù),通過(guò)計(jì)算估計(jì)值和實(shí)際值的差異,對(duì)不同的方法進(jìn)行精度檢驗(yàn)。本實(shí)驗(yàn)通過(guò)實(shí)地采樣數(shù)據(jù),使用不同方法模擬真實(shí)地形表面,并采用交叉驗(yàn)證的方法對(duì)不同方法的模擬結(jié)果進(jìn)行驗(yàn)證。實(shí)驗(yàn)區(qū)域位于北京市通州區(qū)(圖3),為矩形區(qū)域,東西長(zhǎng)0.5km,南北約0.4km,驗(yàn)證區(qū)域面積為0.2km2。北運(yùn)河從北向南流經(jīng)該區(qū)域,將該區(qū)域分為東西兩個(gè)部分。區(qū)域地形較為平坦,高程介于14～22m。采用全站儀對(duì)該區(qū)域進(jìn)行實(shí)地采樣,獲得采樣點(diǎn)395個(gè),數(shù)據(jù)精度為±0.01m。使用347個(gè)采樣數(shù)據(jù)進(jìn)行模擬,將剩余的48個(gè)點(diǎn)對(duì)擬合結(jié)果進(jìn)行精度檢驗(yàn)。在驗(yàn)證過(guò)程中,使用5m和10m的兩種數(shù)據(jù)分辨率對(duì)采樣數(shù)據(jù)進(jìn)行了模擬、驗(yàn)證。5m分辨率模擬結(jié)果精度檢驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)如表3所示。5m分辨率數(shù)據(jù)的精度檢驗(yàn)結(jié)果表明,傳統(tǒng)的空間插值方法中,IDW方法模擬的結(jié)果優(yōu)于其他兩種方法,具有最小的誤差均值和均方根差?；诘貙W(xué)統(tǒng)計(jì)理論的Kriging方法與Spline方法模擬結(jié)果精度相當(dāng),而Spline方法模擬結(jié)果具有最大的誤差分布區(qū)間。較傳統(tǒng)的空間插值方法而言,HASM-AD方法綜合考慮了數(shù)據(jù)鄰域相關(guān)性和采樣點(diǎn)數(shù)據(jù)精度對(duì)模擬結(jié)果的影響,獲得了與實(shí)際空間曲面符合最好的模擬結(jié)果。其模擬結(jié)果在誤差分布區(qū)間、平均誤差和均方根差統(tǒng)計(jì)指標(biāo)上均優(yōu)于傳統(tǒng)的空間插值方法。10m分辨率模擬結(jié)果精度檢驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)如表4所示。10m分辨率數(shù)據(jù)的精度檢驗(yàn)結(jié)果跟5m分辨率數(shù)據(jù)的結(jié)果相同,基于數(shù)據(jù)鄰域相關(guān)性的方法IDW方法模擬精度優(yōu)于Spline和Kriging方法。10m分辨率接近于數(shù)據(jù)平均采樣間距(30m)的一半,數(shù)據(jù)空間連續(xù)性的增強(qiáng),使其空間結(jié)構(gòu)得以加強(qiáng),因此,Kriging方法的模擬精度得到提高。而對(duì)于IDW方法而言,由于實(shí)驗(yàn)區(qū)域地形平坦,起伏較小,高程的變化趨勢(shì)平緩,增大數(shù)據(jù)處理的分辨率對(duì)模擬曲面的變化趨勢(shì)影響不顯著。因而,該方法10m分辨率結(jié)果的精度與5m分辨率結(jié)果相當(dāng)。分辨率的增大使地形細(xì)節(jié)被均化,從而造成局部地形變化偏差,Spline方法的模擬結(jié)果在高程極值區(qū)域偏離了實(shí)際地形,其模擬精度低于其他的方法。同樣,對(duì)于HASM-AD方法,數(shù)據(jù)分辨率變大降低了模擬結(jié)果的精度,使誤差的分布區(qū)間變大,但該方法模擬結(jié)果的精度仍高于傳統(tǒng)的空間插值方法。在本實(shí)驗(yàn)中,由于采樣區(qū)域地形平坦,高程變化趨勢(shì)平緩,數(shù)據(jù)的空間結(jié)構(gòu)較弱,因此數(shù)據(jù)鄰域相關(guān)性對(duì)模擬結(jié)果的影響更為顯著。這也正是在兩種不同數(shù)據(jù)分辨率下,考慮數(shù)據(jù)鄰域相關(guān)性的方法模擬結(jié)果優(yōu)于基于彈性力學(xué)機(jī)制和地學(xué)統(tǒng)計(jì)理論方法的原因。從圖4中可看出,在所比較的方法中,Spline和HASM-AD方法很好地模擬出了區(qū)域地形,尤其這兩種方法都較好地模擬出了河流的基本形狀,而IDW和Kriging方法的模擬結(jié)果沒(méi)能反映出河流的基本位置和形狀。對(duì)不同方法的模擬結(jié)果進(jìn)行對(duì)比,發(fā)現(xiàn)Spline方法在兩種分辨率下,其模擬結(jié)果都出現(xiàn)了對(duì)高程極值低估的現(xiàn)象。Spline方法用于模擬地形時(shí),需注意該方法對(duì)峰、谷等高程極值區(qū)域的低估。使用IDW和Kriging方法雖然獲得了較高精度的模擬結(jié)果,但卻未能模擬出河流的形狀,這或許是因?yàn)橛糜跈z驗(yàn)的點(diǎn)都位于陸地上,使精度偏離實(shí)際。在本實(shí)驗(yàn)中,由于對(duì)河流支流的采樣點(diǎn)較少,所以幾種方法都未能有效地模擬出支流的形狀。3.2區(qū)域地形地貌變化使用SRTM3′×3′分辨率數(shù)據(jù)作為數(shù)據(jù)源,對(duì)HASM-AD與GIS經(jīng)典插值方法的計(jì)算效率進(jìn)行驗(yàn)證。數(shù)據(jù)文件編號(hào)為SRTM_57_06,數(shù)據(jù)區(qū)域范圍為100°E～105°E,30°N～35°N,柵格數(shù)據(jù)為6000×6000。數(shù)據(jù)區(qū)域位置如圖5所示。數(shù)據(jù)區(qū)域位于青海、甘肅和四川三省交界的地方,區(qū)域西北部為青藏高原東緣,經(jīng)岷山山脈和橫斷山脈,地勢(shì)從4000m左右下降到海拔1000～2000m左右。區(qū)域中部地形起伏顯著,溝壑縱橫,相對(duì)高差較大,串狀盆地和小盆地廣泛分布。在區(qū)域東南部橫斷山系,其東南側(cè)是地形舒坦的川西平原,地形地勢(shì)變化平緩,并逐漸向丘陵地帶過(guò)渡。區(qū)域東北部則是甘南高原向黃土高原、隴南山地的過(guò)渡地帶。在相同的計(jì)算平臺(tái)上對(duì)不同方法進(jìn)行了效率檢驗(yàn),計(jì)算機(jī)配置為:Intelcoreduo主頻為2.67,內(nèi)存2G,主板處理芯片為P35,操作系統(tǒng)為WindowXP,.NETFramework2.0。表5中數(shù)據(jù)表明,在進(jìn)行比較的幾種經(jīng)典內(nèi)插方法中,IDW方法和Spline