沈定濤，王結(jié)臣，張 煜，黃 俊，胡承芳

1．江蘇省地理信息技術(shù)重點實驗室，江蘇 南京 210046；2．南京大學(xué) 地理信息科學(xué)系，江蘇 南京 210046；3．長江水利委員會長江科學(xué)院空間信息技術(shù)應(yīng)用研究所，湖北 武漢 430010

一種面向海量數(shù)字高程模型數(shù)據(jù)的洪水淹沒區(qū)快速生成算法

沈定濤1，2，3，王結(jié)臣1，2，張 煜3，黃 俊3，胡承芳3

1．江蘇省地理信息技術(shù)重點實驗室，江蘇 南京 210046；2．南京大學(xué) 地理信息科學(xué)系，江蘇 南京 210046；3．長江水利委員會長江科學(xué)院空間信息技術(shù)應(yīng)用研究所，湖北 武漢 430010

常見種子點填充算法在實現(xiàn)數(shù)字高程模型（digital elevation model，DEM）數(shù)據(jù)下的洪水淹沒區(qū)生成時，具有難以處理大數(shù)據(jù)量、過多的遞歸計算易導(dǎo)致算法效率較低等缺點。針對此問題，本文提出一種面向海量DEM數(shù)據(jù)的洪水淹沒區(qū)生成算法分塊壓縮追蹤法，該算法采用條帶分塊和實時柵格壓縮存儲技術(shù)，以解決海量地形數(shù)據(jù)下的淹沒分析計算問題。最后，通過將本算法與常見種子點填充算法和分塊種子點填充算法進(jìn)行了對比測試，試驗結(jié)果表明本算法不僅較好地解決了海量DEM數(shù)據(jù)下的洪水淹沒區(qū)生成問題，與常規(guī)種子點填充算法和分塊種子點填充算法相比亦具有較高的計算效率。

海量地形數(shù)據(jù)；淹沒分析；種子填充；壓縮存儲；數(shù)字高程模型

1 前 言

洪水淹沒分析是進(jìn)行水文預(yù)測預(yù)報、洪水災(zāi)害評估的一項重要內(nèi)容，也是GIS地形三維仿真系統(tǒng)中的一個重要功能［1－3］。洪水淹沒分析主要基于DEM數(shù)據(jù)，結(jié)合水文水動力學(xué)構(gòu)建的洪水演進(jìn)模型或根據(jù)設(shè)定的靜態(tài)“水位面”進(jìn)行計算。前者可以較精確地模擬洪水在不同時間段下的淹沒區(qū)變化過程，但是洪水演進(jìn)模型的構(gòu)建需要較多的水文水力參數(shù)條件，其處理較為復(fù)雜［4－8］?；陟o水位下的洪水淹沒分析是對洪水淹沒過程達(dá)到最終平衡狀態(tài)的近似模擬，盡管沒有洪水演進(jìn)模型方法精確，但其計算簡單、實用，能夠快速地確定洪水淹沒區(qū)和水深分布，得到了廣泛的應(yīng)用。靜水位下洪水淹沒分析主要分為無源淹沒和有源淹沒兩種，其中無源淹沒相對簡單，只需遍歷全部網(wǎng)格即可得出淹沒范圍，而有源淹沒需要考慮如環(huán)形山、堤壩等障礙，其計算相對復(fù)雜，是洪水淹沒分析算法研究的重點。現(xiàn)有洪水淹沒分析算法的研究主要來源于圖像處理中的種子填充法及其變形，通過給定淹沒起算點，在DEM網(wǎng)格中按照四鄰域或八鄰域進(jìn)行擴散，可以較好地模擬實際的地表徑流淹沒過程，以及自動提取淹沒區(qū)。如文獻(xiàn)［9—10］提出的基于GIS的復(fù)雜地形淹沒分析及其災(zāi)害評估；文獻(xiàn)［11］提出的基于GIS格網(wǎng)模型的洪水淹沒分析；文獻(xiàn)［12］提出的基于DEM的“環(huán)形”洪水淹沒算法；文獻(xiàn)［13］提出的基于DEM的洪水淹沒分析等。

由于無法預(yù)先判斷洪水淹沒的大致范圍，常規(guī)種子點填充算法必須將DEM數(shù)據(jù)一次性載入內(nèi)存進(jìn)行計算，其所能載入的數(shù)據(jù)量依賴于計算機內(nèi)存配置。一般三維仿真系統(tǒng)中用于地形表達(dá)的DEM數(shù)據(jù)常常達(dá)到幾GB甚至幾十GB，這在目前個人計算機內(nèi)存配置條件下是難以全部讀入內(nèi)存的，當(dāng)進(jìn)行洪水淹沒分析時，容易受到內(nèi)存的限制導(dǎo)致計算失敗。另一方面，當(dāng)DEM數(shù)據(jù)較大，淹沒范圍較廣時，種子填充算法中大量的遞歸操作常導(dǎo)致算法效率急劇降低，同時容易出現(xiàn)堆棧溢出等問題，這極大地限制了種子點填充淹沒分析算法的應(yīng)用范圍。因此，在進(jìn)行大規(guī)模DEM數(shù)據(jù)的洪水淹沒分析時，如何避免大量耗時的文件讀寫操作，同時又能在內(nèi)存中高效地處理大數(shù)據(jù)量DEM，是實現(xiàn)高效、大范圍、高精度和自動化洪水淹沒分析的關(guān)鍵。

2 算法設(shè)計思路

2．1 分塊種子點填充算法設(shè)計思路

針對上述問題，研究人員亦提出了一些優(yōu)化算法，如文獻(xiàn)［11］提出將DEM數(shù)據(jù)轉(zhuǎn)換為不規(guī)則多邊形格網(wǎng)和三角網(wǎng)，在多邊形和三角形格網(wǎng)的基礎(chǔ)上按照種子點擴散方法進(jìn)行淹沒范圍計算。文獻(xiàn)［14］提出為DEM數(shù)據(jù)構(gòu)建瓦片金字塔，在大區(qū)域場景下用上層金字塔數(shù)據(jù)進(jìn)行淹沒分析，以實現(xiàn)快速三維實時顯示。這類方法通過對DEM數(shù)據(jù)進(jìn)行簡化，以簡化數(shù)據(jù)實現(xiàn)快速種子點填充計算，在一定程度上降低了算法對內(nèi)存的依賴，提升了計算速度，但是淹沒區(qū)范圍計算精度會直接受到簡化數(shù)據(jù)影響，同時針對海量DEM數(shù)據(jù)的處理仍然有限。

一種較為有效的策略是對DEM數(shù)據(jù)進(jìn)行條帶分塊讀取，并實時計算淹沒區(qū)。以分塊種子點填充算法為例，其基本思路為：首先對原DEM數(shù)據(jù)進(jìn)行條帶劃分，在每個條帶上采用種子點填充算法計算所有潛在淹沒區(qū)并編號，然后對相鄰條帶間潛在淹沒區(qū)執(zhí)行連通域檢測，查找屬于同一連通域的潛在淹沒區(qū)并構(gòu)建關(guān)聯(lián)表，最后通過初始種子點所在淹沒區(qū)編號和關(guān)聯(lián)表提取整個淹沒區(qū)。如圖1所示，DEM數(shù)據(jù)被劃分為3個條帶，圖中灰色填充網(wǎng)格代表各條帶上的潛在淹沒區(qū)。通過對比相鄰條帶間對應(yīng)網(wǎng)格單元所在的淹沒區(qū)編號，執(zhí)行連通域檢測并構(gòu)建關(guān)聯(lián)表，如條帶2上的1、2號淹沒區(qū)和條帶3上3號淹沒區(qū)屬于同一個連通域，它們是相互關(guān)聯(lián)的。最后，根據(jù)種子點所對應(yīng)的1號淹沒區(qū)，逐個條帶查找關(guān)聯(lián)表信息并提取其他關(guān)聯(lián)淹沒區(qū)，構(gòu)建洪水淹沒范圍。

圖1 分塊種子點填充法示意圖Fig．1 Strip－divide seed filling algorithm

上述連通域標(biāo)記方法在執(zhí)行條帶種子點填充算法后可以及時清空分塊數(shù)據(jù)，降低了對內(nèi)存的依賴，使得處理海量柵格數(shù)據(jù)成為可能，在遙感及圖像處理領(lǐng)域得到了一定的應(yīng)用［15－18］。但將其用于淹沒分析時，主要弊端在于：①為進(jìn)行連通域判定，必須在條帶中執(zhí)行種子點填充算法提取所有潛在淹沒區(qū)，而大部分潛在淹沒區(qū)都不是實際淹沒范圍，這一處理過程較為低效；②條帶上種子填充計算結(jié)果無法保存在內(nèi)存中，因此需要預(yù)先生成一個與原DEM大小相同的空值柵格文件，及時寫入分塊條帶的計算結(jié)果，而在進(jìn)行連通域判定時則要多次讀取此淹沒結(jié)果文件；③當(dāng)淹沒區(qū)范圍遠(yuǎn)小于原DEM范圍時，大量條帶數(shù)據(jù)的讀取、計算和連通域判定是沒有必要的。

2．2 分塊壓縮追蹤算法設(shè)計思路

考慮到條帶中每個網(wǎng)格單元只有潛在淹沒和未淹沒兩種狀態(tài)，若在讀取條帶數(shù)據(jù)后直接將每行中高程值低于設(shè)定水位的相鄰網(wǎng)格單元按照游程編碼方法進(jìn)行壓縮，則可以較大程度上降低柵格數(shù)據(jù)量，進(jìn)而將潛在淹沒區(qū)存儲進(jìn)內(nèi)存。為避免盲目地讀取所有條帶數(shù)據(jù)，可以先讀取種子點所在條帶數(shù)據(jù)，實現(xiàn)壓縮存儲并以種子點所在壓縮單元進(jìn)行邊界追蹤標(biāo)記，然后向上和向下擴展讀取新條帶并壓縮，每讀取一個新條帶都以其相鄰條帶頂柵格行或底柵格行中被追蹤過的壓縮單元兩側(cè)作為追蹤邊，在新條帶上執(zhí)行邊界追蹤，最后提取柵格場上被追蹤過的所有壓縮單元即可構(gòu)建淹沒區(qū)，可以稱之為分塊壓縮追蹤法。

如圖2所示，首先讀取條帶2并壓縮存儲，以種子點所在壓縮單元兩側(cè)追蹤得到淹沒區(qū)1，該條帶底柵格行和頂柵格行都有被追蹤過的壓縮單元，因此分別讀取條帶1和條帶3并進(jìn)行壓縮存儲，分別以條帶2底柵格行和頂柵格行上被追蹤過的壓縮單元兩側(cè)作為追蹤邊向下和向上追蹤得到條帶1的淹沒區(qū)1和條帶3的淹沒區(qū)3并進(jìn)而追蹤得到條帶2上的淹沒區(qū)2。因條帶1的底柵格行和條帶3的頂柵格行都沒有被追蹤過的壓縮單元，停止讀取新條帶，最后提取所有被追蹤過的壓縮單元生成洪水淹沒范圍。

與分塊種子點填充法相比，本算法的主要優(yōu)勢在于：①對分塊條帶直接進(jìn)行柵格壓縮存儲，避免了效率低下的種子點填充計算，而將潛在淹沒區(qū)存儲于內(nèi)存比存儲于文件效率更高；②條帶上潛在淹沒區(qū)以壓縮單元形式存儲于內(nèi)存，針對某壓縮單元的邊界追蹤可以跨越多個條帶，從而規(guī)避了復(fù)雜的連通域標(biāo)記過程；③按照向上和向下擴展讀取新條帶并及時追蹤壓縮單元，讀取的條帶數(shù)目與實際淹沒范圍直接相關(guān)，沒有洪水淹沒的條帶則不會讀入內(nèi)存，避免了大量無效條帶數(shù)據(jù)的讀取與計算。

3 分塊壓縮追蹤法關(guān)鍵技術(shù)及其實現(xiàn)

3．1 算法總體流程

按照上述算法設(shè)計思路，分塊壓縮追蹤法的總體算法流程圖如圖3所示。

3．2 條帶壓縮與邊界追蹤標(biāo)記

條帶壓縮與邊界追蹤標(biāo)記包含了算法流程中的步驟（1）—步驟（3）。DEM數(shù)據(jù)條帶劃分示意圖如圖4所示，假定某DEM數(shù)據(jù)有24行、32列，設(shè)定條帶規(guī)格為8行，則DEM數(shù)據(jù)被劃分為3個條帶。為便于說明，將網(wǎng)格上的高程值以整數(shù)進(jìn)行表達(dá)，以1—8的數(shù)字代表高程值，數(shù)字越大表示高程值越高。

圖4 柵格條帶分塊示意圖Fig．4 Raster strip－divide diagram

種子點所在網(wǎng)格位于DEM數(shù)據(jù)的第10行、第14列，屬于條帶2的第2行第14列，其高程值為3。假定淹沒水位為4，圖中以灰色填充的網(wǎng)格為種子點所在條帶的潛在淹沒范圍，其高程值均小于或等于設(shè)定水位值。

條帶數(shù)據(jù)的壓縮方法為：

（1）在內(nèi)存中生成一個以鏈表為元素的數(shù)組，數(shù)組大小為原DEM柵格行數(shù)目，鏈表的結(jié)點為壓縮單元，該鏈表結(jié)構(gòu)用于條帶數(shù)據(jù)壓縮后存儲對應(yīng)柵格行的所有壓縮單元。

（2）在條帶上按行遍歷，依次將柵格行上高程值小于或等于設(shè)定淹沒水位的相鄰網(wǎng)格采用游程編碼方法進(jìn)行壓縮，生成一個壓縮單元結(jié)構(gòu)，該壓縮單元標(biāo)記了潛在淹沒網(wǎng)格在此柵格行上跨越的起始列和終止列。

（3）每生成一個新的壓縮單元，則將該壓縮單元插入對應(yīng)行上壓縮單元鏈表尾部，最后完成整個條帶數(shù)據(jù)的壓縮存儲。圖5是種子點所在條帶壓縮存儲示意，以圖中第9行的壓縮單元為例，該壓縮單元標(biāo)記了1和18兩個值，表示該壓縮單元跨越了第1—18列。

圖5 條帶壓縮與邊界追蹤Fig．5 Strip compression and boundary tracing

條帶數(shù)據(jù)的壓縮存儲尚未標(biāo)記每個壓縮單元與淹沒源種子點的連通性，可以通過對種子點所在的壓縮單元進(jìn)行邊界追蹤以標(biāo)記與種子點連通的其他壓縮單元。主要步驟為：首先為每個鏈表設(shè)置一個標(biāo)記數(shù)組，數(shù)組元素的個數(shù)是鏈表中壓縮單元的兩倍，數(shù)組依次存儲了每個壓縮單元的左側(cè)和右側(cè)兩個標(biāo)記，默認(rèn)將所有的標(biāo)記數(shù)組元素設(shè)置為false，即表示所有壓縮單元兩側(cè)都未被追蹤過。其次，查找初始種子點所在的壓縮單元，分別以該壓縮單元左側(cè)和右側(cè)邊界作為起始追蹤邊，按照四方向追蹤法［19－20］進(jìn)行柵格邊界追蹤，每追蹤到新的壓縮單元左側(cè)或右側(cè)，就將該行上對應(yīng)的標(biāo)記數(shù)組元素值由false設(shè)置為true，當(dāng)追蹤到某側(cè)標(biāo)記為true的壓縮單元則停止追蹤。最后，循環(huán)遍歷初始種子點所在柵格行上所有壓縮單元，若某壓縮單元一側(cè)被追蹤過而另一側(cè)未被追蹤，則以未被追蹤一側(cè)作為起始追蹤邊進(jìn)行邊界追蹤，直到該行上所有被追蹤過的壓縮單元滿足兩側(cè)都被追蹤。圖5顯示了壓縮單元邊界追蹤結(jié)果，追蹤邊界如圖中粗線所示。

3．3 依條帶擴展存儲

依條帶擴展存儲包含了算法流程中的步驟（5）—步驟（12），此步驟是一個循環(huán)過程，其循環(huán)結(jié)束條件為步驟（13）。因為可以預(yù)先知道當(dāng)前已讀取過哪些條帶數(shù)據(jù)，為便于描述，按照每個條帶所處的空間位置，將讀取的位于最上方的條帶稱為最上條帶，將位于最下方的條帶稱為最下條帶，將每個條帶中最上一柵格行稱為該條帶的頂柵格行，最下一柵格行稱為該條帶的底柵格行。在完成種子點所在條帶的壓縮存儲后，可以將該條帶同時設(shè)定為最上條帶和最下條帶。

此時可以向上和向下擴展讀取新的條帶，并按照前述方法進(jìn)行條帶壓縮與邊界追蹤。其原理為：對最上條帶和最下條帶而言，需要繼續(xù)向上和向下讀取新條帶的唯一條件就是其頂柵格行或底柵格行上有被追蹤過的壓縮單元，表示淹沒區(qū)還未到達(dá)實際邊界。當(dāng)最上條帶頂柵格行上有被追蹤過的壓縮單元時，可以將該行所有被追蹤過壓縮單元的兩側(cè)標(biāo)記為起始追蹤邊，讀取最上條帶的上一條帶作為新的最上條帶，并進(jìn)行壓縮存儲，此時以標(biāo)記的起始追蹤邊向上追蹤即可得到當(dāng)前最上條帶的淹沒區(qū)，同理對最下條帶執(zhí)行此過程。不斷循環(huán)執(zhí)行最上條帶和最下條帶的擴展存儲，當(dāng)最上條帶頂柵格行和最下條帶底柵格行都沒有被追蹤的壓縮單元，或都已到達(dá)DEM邊界則停止循環(huán)。

如圖5所示，鏈表數(shù)組中只存儲了一個條帶的壓縮數(shù)據(jù)，其頂柵格行（第16行）有兩個壓縮單元且都被追蹤過，因此需要從原DEM中讀取當(dāng)前條帶的上一條帶，并執(zhí)行游程壓縮存儲。圖6顯示了讀取上一條帶后的鏈表數(shù)組變化，在第17—24行上新增加了壓縮單元。此時分別以第16行被追蹤過邊界的兩個壓縮單元的左側(cè)和右側(cè)為起始追蹤邊向上進(jìn)行邊界追蹤，圖中以粗線條顯示的為邊界追蹤結(jié)果。當(dāng)前最下條帶底柵格行位于第9行，有一個壓縮單元，且兩側(cè)已經(jīng)被追蹤過，需要讀取DEM中對應(yīng)的下一條帶并進(jìn)行壓縮存儲，結(jié)果如圖7所示。此時以第9行壓縮單元兩側(cè)作為追蹤邊，執(zhí)行向下追蹤，由于第10行上壓縮單元與第9行壓縮單元并不相連，追蹤停止。

圖6 上一條帶壓縮存儲及邊界追蹤Fig．6 Upper strip compression and boundary tracing

圖7 下一條帶壓縮存儲及邊界追蹤Fig．7 Lower strip compression and boundary tracing

3．4 淹沒區(qū)孤島處理

淹沒區(qū)孤島處理對應(yīng)算法流程圖中步驟（14）。在完成擴展條帶壓縮存儲及邊界追蹤標(biāo)記后，需要追蹤部分未被標(biāo)記的孤島。如圖7所示，淹沒區(qū)中仍然有兩個孤島未被追蹤出來，其中一個孤島橫跨第12—15行，另一個孤島橫跨第19—22行?？梢灾鹦斜闅v追蹤標(biāo)記數(shù)組，并兩兩取值對比，該值代表對應(yīng)壓縮單元的左側(cè)和右側(cè)追蹤情況。若兩個標(biāo)記值分別為true和false，則需對標(biāo)記值為false的一側(cè)進(jìn)行追蹤。如圖7中第12行第一個壓縮單元，其左側(cè)已經(jīng)被追蹤，但是右側(cè)未被追蹤過，此時以該側(cè)為起始追蹤邊進(jìn)行邊界追蹤標(biāo)記，將孤島邊界追蹤出來。按照此方法，最后追蹤結(jié)果如圖8所示，此時整個淹沒區(qū)外側(cè)邊界和內(nèi)側(cè)邊界已經(jīng)全部追蹤出來。

圖8 淹沒區(qū)孤島提取Fig．8 Island extracting in flood region

4 試驗與分析

基于上述算法設(shè)計原理，筆者采用C＃語言實現(xiàn)了洪水淹沒區(qū)生成算法，并在“金沙江水文泥沙信息三維可視化系統(tǒng)”中得到應(yīng)用。圖9是金沙江流域研究區(qū)DEM數(shù)據(jù)，該數(shù)據(jù)包含的網(wǎng)格行列數(shù)為19 719行×19 454列，數(shù)據(jù)文件大小為1．43 GB，網(wǎng)格寬度25 m，圖10顯示了淹沒源水位上升50米時的洪水淹沒區(qū)范圍。

圖9 研究區(qū)DEMFig．9 Study area of DEM data

圖10 淹沒范圍示意圖Fig．10 Flood region diagram

為驗證算法效率，筆者分別采用常規(guī)種子填充算法、分塊種子點填充算法和本文提出的分塊壓縮追蹤法進(jìn)行了測試，其中常規(guī)種子填充算法因為內(nèi)存不足導(dǎo)致計算失敗。表1給出了分塊壓縮追蹤法與分塊種子點填充法的算法耗時對比。測試結(jié)果表明，在相同的條帶規(guī)格下，分塊壓縮追蹤法耗時遠(yuǎn)小于分塊種子填充法耗時。試驗中設(shè)定淹沒水深為定值，將單個條帶的行數(shù)從50逐步擴展到2000，當(dāng)一次讀入的條帶范圍變大時，由于減少了分塊數(shù)量，同時降低了分塊間連通性判定的次數(shù)，因此分塊種子點填充法耗時是隨著分塊條帶數(shù)據(jù)的逐步變大而降低的，其最佳算法運行條件為分塊條帶能剛好被計算機一次性讀入內(nèi)存。分塊壓縮追蹤法是依條帶進(jìn)行擴展讀取的，其讀取的條帶總體范圍與實際淹沒范圍直接相關(guān)，盡管在條帶分塊更小時讀取的條帶數(shù)目更多，但是其實際讀取的數(shù)據(jù)范圍可能更小，即文件I／O耗時更少，在條帶分塊較大時這種差別更明顯。而壓縮單元邊界追蹤在不同分塊情形下的差別并不大，因為邊界追蹤需要搜索的壓縮單元數(shù)目是一致的。隨著條帶行數(shù)的逐步增大，算法總耗時增加并不顯著，相反在條帶行數(shù)較少時算法耗時更少，條帶行數(shù)從50擴大到2000時算法耗時僅增加了26 s，而讀取每個分塊條帶數(shù)據(jù)所占據(jù)的內(nèi)存則從8 MB（50行×2萬列×8字節(jié)）增加到320 MB（2000行×2萬列×8字節(jié)）。在條帶分塊策略方面，只要分塊數(shù)據(jù)能夠一次性讀入內(nèi)存都是可以滿足算法要求的，但分塊條帶更小時可減少文件I／O耗時，且在一定程度上降低了內(nèi)存峰值，是較優(yōu)的選擇。

表1 分塊壓縮追蹤法與分塊種子點填充法算法耗時對比Tab．1 Time comparison of divide compression tracing and stripe－divide seed filling algorithm

在內(nèi)存占用方面，常規(guī)種子點填充算法需要讀取整個DEM數(shù)據(jù)，以本算法測試數(shù)據(jù)為例，其需要占用內(nèi)存約3．2 GB（2萬行×2萬列×8字節(jié)）的數(shù)據(jù)量，這在目前個人計算機上是難以做到的。分塊種子點填充法與分塊壓縮追蹤法較好地解決了這一問題，在讀取條帶數(shù)據(jù)后通過計算潛在淹沒區(qū)，可以及時清空分塊條帶數(shù)據(jù)所占用的內(nèi)存，其內(nèi)存占用的峰值主要來自于條帶數(shù)據(jù)的讀入，如條帶行數(shù)為1000時占用的內(nèi)存也僅160 MB。分塊壓縮追蹤法將潛在淹沒區(qū)都存儲在內(nèi)存中，測試中整個柵格場共生成了258 557個壓縮單元，按照每個壓縮單元存儲起始列和終止列兩個字段計算，需要8字節(jié)的數(shù)據(jù)量，則總數(shù)據(jù)量僅為2 MB。若按此柵格數(shù)據(jù)壓縮比進(jìn)行計算，當(dāng)柵格數(shù)據(jù)量達(dá)到3．2 TB（20萬行×200萬列×8字節(jié)）時，需存儲的壓縮單元數(shù)據(jù)量約為2 GB。隨著64位操作系統(tǒng)的普及，個人計算機內(nèi)存配置將逐步過渡到4—8 GB，本算法將具備處理TB級數(shù)據(jù)的應(yīng)用潛力。

5 結(jié) 論

本文針對常規(guī)種子點填充算法難以用于海量DEM數(shù)據(jù)淹沒分析問題，提出采用分塊壓縮追蹤法進(jìn)行淹沒區(qū)生成。通過將DEM數(shù)據(jù)進(jìn)行條帶劃分，并將條帶中柵格行上連續(xù)多個淹沒單元進(jìn)行壓縮存儲，以降低數(shù)據(jù)量，最后采用壓縮單元邊界追蹤標(biāo)記方法提取淹沒范圍，從而實現(xiàn)了復(fù)雜地形條件下的淹沒區(qū)生成。與常見種子點填充方法相比，本文方法使用較小的內(nèi)存配置處理了較大的柵格數(shù)據(jù)量，同時避免了種子填充法中的大量遞歸判斷，提升了計算速度，具有一定的實用性。

［1］ LI Yun，F(xiàn)AN Ziwu，WU Shiqiang，et al．Numerical Simulation and 3D Visualization of Flood Propagation in Large－scale Detection Basins［J］．Journal of Hydraulic Engineering，2005（10）：1158－1164．（李云，范子武，吳時強，等．大型蓄滯洪區(qū)洪水演進(jìn)數(shù)值模擬與三維可視化技術(shù)［J］．水利學(xué)報，2005（10）：1158－1164．）

［2］ DONG Wenfeng，YUAN Yanbin，DU Yingze，et al．Simulation of 3D Terrain and Dynamic Simulation of Flood Routing Method［J］．Water Resources and Power，2001，19（3）：37－39．（董文鋒，袁艷斌，杜迎澤，等．流域三維地形仿真及洪水演進(jìn)動態(tài)模擬［J］．水電能源科學(xué)，2001，19（3）：37－39．）

［3］ JIANG Jie，WU Lingda，XU Jiangbin．Digital Earth Based Flood Routing Model Visualization［J］．Computer Engineering and Applications，2009，45（36）：1－4．（蔣杰，吳玲達(dá)，徐江斌．基于數(shù)字地球的洪災(zāi)演進(jìn)模型表現(xiàn)［J］．計算機工程與應(yīng)用，2009，45（36）：1－4．）

［4］ WANG Zhili，GENG Yanfen，JIN Sheng．The Two－dimen－sional Flood Routing Simulation［J］．Chinese Journal of Computational Mechanics，2007，24（4）：533－538．（王志力，耿艷芬，金生．二維洪水演進(jìn)數(shù)值模擬［J］．計算力學(xué)學(xué)報，2007，24（4）：533－538．）

［5］ LI Daming，LIN Yi，XU Yanan，et al．Numerical Model of Flood Propagation［J］．Journal of Tianjin University，2009，42（1）：47－55．（李大鳴，林毅，徐亞男，等．河道、滯洪區(qū)洪水演進(jìn)數(shù)學(xué)模型［J］．天津大學(xué)學(xué)報，2009，42（1）：47－55．）

［6］ WEI Wenli，SHEN Yongming，SUN Guangcai，et al．Numerical Simulation of 2D Dam－break Flood Wave［J］．Journal of Hydraulic Engineering，2003（9）：43－47．（魏文禮，沈永明，孫廣才，等．二維潰壩洪水波演進(jìn)的數(shù)值模擬［J］．水利學(xué)報，2003（9）：43－47．）

［7］ ZHANG Xibing，LU Jinyou，F(xiàn)AN Beilin，et al．Dam Break Flood Routing and Drainage Process Modeling for the Tangjiashan Barrier Lake［J］．Yangtze River，2008，39（22）：21－22．（張細(xì)兵，盧金友，范北林，等．唐家山堰塞湖潰壩洪水演進(jìn)及下泄過程復(fù)演［J］．人民長江，2008，39（22）：21－22．）

［8］ LI Guangchi，WANG Chuanhai．Universal Algorithm for River Basin Flood Routing Model［J］．Journal of Hohai University，2005，33（6）：624－628．（李光熾，王船海．流域洪水演進(jìn)模型通用算法研究［J］．河海大學(xué)學(xué)報：自然科學(xué)版，2005，33（6）：624－628．）

［9］ LIU Renyi，LIU Nan．A GIS Based Model for Calculating of Flood Area［J］．Acta Geographica Sinica，2001，56（1）：1－6．（劉仁義，劉南．基于GIS的復(fù)雜地形洪水淹沒區(qū)計算方法［J］．地理學(xué)報，2001，56（1）：1－6．）

［10］ LIU Renyi，LIU Nan．A New DEM－based Method for Flood Area Calculation and Damage Evaluation［J］．Journal of Image and Graphics，2001，6（2）：118－122．（劉仁義，劉南．一種基于數(shù)字高程模型DEM的淹沒區(qū)災(zāi)害評估方法［J］．中國圖像圖形學(xué)報，2001，6（2）：118－122．）

［11］ DING Zhixiong，LI Jiren，LI Lin．Method for Flood Submergence Analysis Based on GIS Grid Model［J］．Journal of Hydraulic Engineering，2004（6）：56－67．（丁志雄，李紀(jì)仁，李琳．基于GIS格網(wǎng)模型的洪水淹沒分析方法［J］．水利學(xué)報，2004（6）：56－67．）

［12］ SUN Hai，WANG Cheng．A“Ring”Method for Flood Submergence Based on DEM［J］．Geomatics and Information Science of Wuhan University，2009，34（8）：948－951．（孫海，王乘．利用DEM的“環(huán)形”洪水淹沒算法研究［J］．武漢大學(xué)學(xué)報：信息科學(xué)版，2009，34（8）：948－951．）

［13］ GUO Lihua，LONG Yi．Analysis of Flood Submerging Based on DEM［J］．Bulletin of Surveying and Mapping，2002（11）：25－30．（郭利華，龍毅．基于DEM的洪水淹沒分析［J］．測繪通報，2002（11）：25－30．）Binary Pictures［J］．Journal of Image and Graphics，2003，8（2）：198－202．（張修軍，郭霞，金心宇．帶標(biāo)記矯正的二值圖像連通域像素標(biāo)記算法［J］．中國圖像圖形學(xué)報，2003，8（2）：198－202．）

［19］ XIE Shunping，DU Jinkang，WANG Jiechen．Method for Tracing Run－length Outline to Implement Vectorization of Raster Graphics and Image Data［J］．Journal of Remote Sensing，2004，8（5）：465－470．（謝順平，都金康，王結(jié)臣．實現(xiàn)柵格圖形和圖像數(shù)據(jù)矢量化提取的游程輪廓追蹤法．遙感學(xué)報，2004，8（5）：465－470．）

［20］ XIE Shunping，DU Jinkang，WANG Lachun，et al．Approach of Vectorization for GIS Raster Data Based on Run－length Encoding System［J］．Acta Geodaetica et Cartographica Sinica，2004，33（4）：323－327．（謝順平，都金康，王臘春，等．基于游程編碼的GIS柵格數(shù)據(jù)矢量化方法［J］．測繪學(xué)報，2004，33（4）：323－327．）

（責(zé)任編輯：陳品馨）

［14］ JIANG Rengui，XIE Jiancang，LI Jianxun，et al．Analysis and Simulation of Flood Inundation Based on Digital Earth［J］．Engineering and Application，2011，47（13）：219－222．（姜仁貴，解建倉，李建勛，等．基于數(shù)字地球的洪水淹沒分析及仿真研究［J］．計算機工程與應(yīng)用，2011，47（13）：219－222．）

［15］ MA Jianglin，ZHAO Zhongming，MENG Yu，et al．Connected Component Labelling for Massive Remote Sensing Classification Image［J］．Computer Engineering，2008，34（1）：262－264．（馬江林，趙忠明，孟瑜，等．海量遙感分類圖連通域標(biāo)記方法［J］．計算機工程，2008，34（1）：262－264．）

［16］ WANG Jing，ZHANG Yanning，LUO Jiancheng，et al．Improved Connected Component Labeling on High－resolution Remote Sensing Image［J］．Computer Engineering and Applications，2005，41（10）：37－39．（王晶，張艷寧，駱劍承，等．針對高分辨率遙感影像分割的改進(jìn)連通域標(biāo)記方法［J］．計算機工程與應(yīng)用，2005，41（10）：37－39．）

［17］ ZHAO Fei，ZHANG Lu，ZHANG Zhiyong，et al．A Hardware Acceleration Based Algorithm for Real－time Binary Image Connected－component Labeling［J］．Journal of Electronics＆Information Technology，2011，33（5）：1069－1075．（趙菲，張路，張志勇，等．基于硬件加速的實時二值圖像連通域標(biāo)記算法［J］，電子與信息學(xué)報，2011，33（5）：1069－1075．）

［18］ ZHANG Xiujun，GUO Xia，JIN Xinyu．The Pixel Labeled Algorithm with Label Rectified of Connecting Area in

A Quick Flood Inundation Algorithm Based on Massive DEM Data

SHEN Dingtao1，2，3，WANG Jiechen1，2，ZHANG Yu3，HUANG Jun3，HU Chengfang3
1．Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology，Nanjing，210046，China；2．Department of Geographic Information Science，Nanjing University，Nanjing 210046，China；3．Spatial Information Technology Application Institute，Changjiang River Scientific Research Institute，Changjiang Water Resources Commission，Wuhan 430010，China

The conventional flood inundation methods based on DEM data usually have some disadvantages．For example，the seed filling method which is a popular flood inundation method can not get better result when the data amount is huge，and also it reflects low computational efficiency due to too many recursive operations．To resolve this problem，this paper proposes a quick flood inundation algorithm based on massive DEM data．It focuses on strip－divide method and real time raster compression storage technology．The paper makes the comparison between the common seed filling algorithm and strip－divide seed filling algorithm，the results show that this algorithm greatly improves the computational efficiency．At the same time，it resolves the problem of massive DEM data analysis．

massive DEM data；flood inundation；seed fill；compressed storage；digital elevation model

SHEN Dingtao（1983—），male，engineer，PhD candidate，majors in hydroinformatics and geographical information science．

P208

A

1001－1595（2014）06－0645－08

國家自然科學(xué)基金（41101408；41301435）；中央級公益性科研院所基本科研業(yè)務(wù)費項目（CKSF2013016／KJ；CKSF2014031／KJ）；水利部公益性行業(yè)科研專項（201201051）；教育部新世紀(jì)優(yōu)秀人才支持計劃（NCET－13－0280）

2013－03－20

沈定濤（1983—），男，工程師，博士生，主要研究方向為水信息學(xué)和GIS。

SHEN Dingtao，WANG Jiechen，ZHANG Yu，et al．A Quick Flood Inundation Algorithm Based on Massive DEM Data［J］．Acta Geodaetica et Cartographica Sinica，2014，43（6）：645－652．（沈定濤，王結(jié)臣，張煜，等．一種面向海量數(shù)字高程模型數(shù)據(jù)的洪水淹沒區(qū)快速生成算法［J］．測繪學(xué)報，2014，43（6）：645－652．）

10．13485／j．cnki．11－2089．2014．0104

修回日期：2014－02－16