基于改進種子填充算法的地物快速填充應(yīng)用研究

宋華平，郭鑫，李晉川

(1.重慶數(shù)字城市科技有限公司，重慶 400020； 2.重慶郵電大學(xué)光纖通信重點實驗室，重慶 400065)

基于改進種子填充算法的地物快速填充應(yīng)用研究

宋華平1?，郭鑫2，李晉川1

(1.重慶數(shù)字城市科技有限公司，重慶 400020； 2.重慶郵電大學(xué)光纖通信重點實驗室，重慶 400065)

地形圖向GIS數(shù)據(jù)轉(zhuǎn)換工作量巨大，在建筑物面狀化處理過程中尤為突出。本文通過對此類工作特點的總結(jié)，以傳統(tǒng)的種子填充法和掃描線種子填充法為理論基礎(chǔ)，提出一種邊搜索邊填充、先填充再根據(jù)方向滿行入棧的改進種子填充算法。通過仿真實驗，對比傳統(tǒng)種子填充算法，得出該算法具有解決重復(fù)出入棧問題、降低使用堆棧大小，

改進種子填充算法；區(qū)域填充；二次開發(fā)

1 引 言

建筑物面填充是GIS數(shù)據(jù)建庫很重要的步驟，其所運用的給定區(qū)域快速填充算法是計算機圖形處理中的一個重要課題。在進行圖形處理時，不僅要畫出圖形的邊界，常常還需要將邊界范圍內(nèi)的所有像素單元都修改為指定的顏色。它在真實圖形生成、計算機藝術(shù)、圖像處理、高精度字體顯示等多個領(lǐng)域中有著重要的應(yīng)用[1]。因此，區(qū)域填充算法在計算機圖形學(xué)領(lǐng)域地位舉足輕重。

目前，最常用的區(qū)域填充是多邊形填色，傳統(tǒng)的區(qū)域填充算法有兩種:一種是采用鄰接鏈表的數(shù)據(jù)結(jié)構(gòu)，通過確定區(qū)域邊界的掃描線覆蓋間隔來填充的掃描線(Scan Line)算法；另一種是采用遞歸方法，從給定的位置開始填充，到指定邊界為止的種子填充(Seed Filling)算法。文獻[2]提到的掃描線算法主要用于填充由簡單邊組成的規(guī)則區(qū)域，比如圓、橢圓以及其他一些標準的多邊形，它在填充時對輪廓線的形狀有一定的要求，需要預(yù)先知道區(qū)域的邊界。在很多實際應(yīng)用中，一個需要填充的復(fù)雜區(qū)域的邊界事先并不知道，因此掃描線算法在處理帶水平邊的凹拐點時不能正確填充，但其利用了掃描線上像素之間的連貫性，因此具有較高的效率。胡云等[3]提出的種子填充算法不要求事先知道待填充區(qū)域的邊界，就可解決邊界比較復(fù)雜的和填充帶有內(nèi)孔的多邊形區(qū)域填充問題。其原理是只要在某個區(qū)域(邊界)內(nèi)已知一個像素，并賦予填充色，以該點為起點，用4向連通方法或8向連通方法，就能從此像素出發(fā)找到區(qū)域內(nèi)的所有像素點進行填充。簡單直觀的種子填充算法，由于進行大量的出入棧操作，因此效率很低，在特殊應(yīng)用中填充速度就滿足不了要求。在填充較大的區(qū)域時，要求分配較大的堆棧空間，不僅浪費了內(nèi)存，還會出現(xiàn)堆棧溢出現(xiàn)象[4]。

鑒于以上的問題，本文吸取了種子填充算法的某些思想，提出一種邊搜索邊填充、先填充再根據(jù)方向滿行入棧的改進種子填充算法，算法避免了堆棧大小的問題，將填充的點包括邊界輪廓都存放在Filled隊列鏈表中，用于下一步的輪廓識別。該算法通過VC++ 6.0平臺的仿真驗證，得出其進出堆棧次數(shù)遠遠低于經(jīng)典的種子填充算法。在執(zhí)行效率和占有?？臻g大小方面也得到很好的改進。最后，利用Bentley MicroStation軟件平臺的二次開發(fā)工具，在某市勘測院GIS建庫項目中實施該改進算法，發(fā)現(xiàn)填充速度很快，填充效果也能滿足實際空間數(shù)據(jù)編輯管理的應(yīng)用需求。

2 種子填充法及其改進思想

種子填充算法是從填充區(qū)域內(nèi)部一點開始，并由此出發(fā)找到區(qū)域內(nèi)的所有像素。算法從給定種子(X，Y)開始，先檢測該點的顏色，如果它與邊界色和填充色都不相同，就用填充色來填充該點，然后檢測相鄰位置，以確定它們是否是邊界色和填充色，若不是，就采用遞歸算法填充該相鄰點，直到此過程檢測完整區(qū)域邊界范圍內(nèi)的所有像素為止[5]。

2.1 種子填充算法

根據(jù)填充區(qū)域的特性，種子填充法可分為4向連通和8向連通兩種。4向連通區(qū)域是指從區(qū)域中任意一點出發(fā)，在不越出區(qū)域邊界的前提下，通過上、下、左、右4個方向的移動組合，搜索到達區(qū)域內(nèi)的任意像素，這種填充方法就稱為“4-連通算法”。8向連通區(qū)域是指從區(qū)域中某一點出發(fā)，在不越出區(qū)域邊界的前提下，通過上、下、左、右、左上、左下、右上和右下全部8個方向到達區(qū)域內(nèi)的任意像素，這種填充方法就稱為“8-連通算法”?；趹?yīng)用需要，本文只分析“4-連通算法”。

圖1 連通方向示意圖

如圖1所示，假設(shè)中心的黃色點是當(dāng)前處理的點，如果是“4-聯(lián)通算法”，則只搜索處理周圍紅色標識的4個點，如果是“8-聯(lián)通算法”則除了處理上、下、左、右4個紅色標識的點，還搜索處理4個藍色標識的點，但有時會出現(xiàn)越出邊界的問題。

2.2 改進種子填充算法思想

為了使算法適用于任意復(fù)雜圖形，并且具有較快的填充速度，本文采用邊搜索邊填充、先填充再滿行入棧的方法。在入棧之前要判斷行像素點是否已被填充，若已被填充才入棧，否則不予考慮。這樣將會減少入棧的冗余像素，即每一個像素行只入棧一次。為此，種子填充算法改進如下:建立一個隊列Filled和一個標志數(shù)組Flag來實現(xiàn)區(qū)域填充。

為了存儲對每個新的子區(qū)域進行搜索填充的起始位置以及搜索填充的方向，定義一個堆棧，其存儲結(jié)構(gòu)體如下:

struct node{

int Xl；//當(dāng)前掃描行填充區(qū)間的左邊界X坐標intXr；//當(dāng)前掃描行填充區(qū)間的右邊界X坐標int Y；//當(dāng)前掃描行Y

int Direction_4；//搜索填充的方向{-1，0}向左搜索，{1，0}向右搜索，{0，1}向上搜索，{0，-1}向下搜索

}

Link_Stack；

在算法的實現(xiàn)過程中我們可用for循環(huán)遍歷定義好的方向即可實現(xiàn)遞歸搜索。

Direction_8[]={{-1，0}，{-1，1}，{0，1}，{1，1}，{1，0}，{1，-1}，{0，-1}，{-1，-1}}；//8個連通方向

Direction_4[]={{-1，0}，{0，1}，{1，0}，{0，-1}}；//4個連通方向

算法步驟如下:

①找出該區(qū)域內(nèi)部任意一點，作為填充種子。Flag[Y]標志掃描第Y行是否全部填充過，若是，則Flag[Y]=true，否則Flag[Y]=false。對Y行進行掃描時，先檢查Flag[Y]，當(dāng)Flag[Y]=false時才填充該點。

②對Y行進行左、右方向搜索，并把填充后種子點存入隊列Filled。Xl[Y]和Xr[Y]分別表示Y行最左端點和最右端點，這樣掃描的種子像素時范圍僅限于Xl[Y]≤x≤Xr[Y](x∈Filled)，此時滿足Flag[Y] =true。

③將{{Xl[Y]，Xr[Y]}，Y，{0，1}}和{{Xl[Y]，Xr[Y]}，Y，{0，-1}}分別壓入堆棧，作為向上搜索填充和向下搜索填充的起始信息。其中{Xl[Y]，Xr [Y]}為搜索區(qū)間，Y為搜索指定行，{0，1}和{0，-1}分別表示向上、向下的搜索方向。

④若堆棧為空，則填充過程完成，程序結(jié)束。否則繼續(xù)執(zhí)行以下步驟:

⑤棧頂元素出棧，將出棧信息作為新區(qū)域搜索和填充的起始信息。保留起始信息的左右端點至Xpl和Xpr中，根據(jù)起始信息中記錄的方向在區(qū)間[Xpl，Xpr]內(nèi)搜索下一條掃描行，若搜索到未填充點，則以其為種子點，重復(fù)②步驟。若在區(qū)間[Xpl，Xpr]內(nèi)所有點都為邊界像素或已填充像素，則說明當(dāng)前連續(xù)區(qū)域已填充完畢，轉(zhuǎn)步驟③。

圖2 改進種子填充算法流程圖

改進的掃描行種子填充算法如圖2所示，對上述搜索上方掃描行未填充的像素作為種子像素點入棧的操作進行細化，算法描述如下:

InitStack()//初始化棧，并使它為空；

Setpixel()//給指定像素點賦色

Filledpoint()//存儲已填充點

StackEmpty()//棧的判空函數(shù)

//算法開始:

while(!StackEmpty())

point=Pop()；

if(Flag[Y]==false)

if(point的最左點不為填充色也不為邊界色)

{Setpixel(point的最左點)；Filledpoint(point的最左點)；}

if(point的最右點不為填充色也不為邊界色)

{Setpixel(point的最右點)；Filledpoint(point的最右點)；}

else

Push({{Xl[Y]，Xr[Y]}，Y，{0，1}})；

Push({{Xl[Y]，Xr[Y]}，Y，{0，-1}})；

該算法中，對種子所在掃描行分上下兩個方向進行分別逐行掃描，取標志數(shù)組和左右端點的數(shù)組.增加一個全局的結(jié)構(gòu)體用以區(qū)分掃描方向，如此又可以減少對每條掃描行判定是否掃描過的步驟，提高效率。

上述算法的難點在于找到掃描行Y的未被填色的最左端點Xl和最右端點Xr后對其填色?？梢苑治龅那樾斡腥N，如圖3所示:包括行單區(qū)間連續(xù)(圖3之a(chǎn))；行多區(qū)間連續(xù)(圖3之b)；行多區(qū)間不連續(xù)(圖3之c)。采用兩端逼近的算法來解決，最終解決的時間復(fù)雜度都為O(n)。

圖3 掃描行端點區(qū)間分類情況

3 算法比較

為了驗證上述改進算法?？臻g大小、進出棧次數(shù)、算法執(zhí)行時間方面的改進，我們在計算機上進行了實驗，該實驗是在配置為Pentium4 1.4GHz/512MB/Windows XP/VC++6.0的虛擬機環(huán)境下完成的。具體實驗數(shù)據(jù)如表1所示。

運行結(jié)果對比表 表1

由表1可以看出:①在棧所用空間大小方面，改進算法的?？臻g大小大概是傳統(tǒng)種子填充算法的棧空間大小的20%左右；②從進出棧的次數(shù)來看，傳統(tǒng)種子填充算法的進出棧次數(shù)是改進算法的2.5倍；③利用改進算法對區(qū)域進行填充，可以大大加快填充速度，提高效率。

4 示范應(yīng)用

隨著GIS應(yīng)用領(lǐng)域的不斷擴大，應(yīng)用功能的不斷增強，系統(tǒng)對空間數(shù)據(jù)的要求也越來越高。在GIS數(shù)據(jù)建庫的過程中，必須充分考慮成果的低成本、數(shù)據(jù)的真實性、建庫的高效性等特點。本文算法在某市勘測院的地圖整理編制應(yīng)用過程中，利用Bentley MicroStation軟件平臺的二次開發(fā)功能[6]，很好地解決了建筑輪廓查找與構(gòu)面的問題。其基本思想為:首先查找到建筑物結(jié)構(gòu)的關(guān)鍵字(如“磚”、“砼”等)，然后以關(guān)鍵字為基礎(chǔ)，搜索包含此文字的最小外接多邊形，應(yīng)用改進種子填充算法，將建筑物輪廓圍合而成區(qū)域構(gòu)成建筑物的面。如圖4所示，填充粉色為一般建筑物，填充淺綠色為棚屋建筑物。

圖4 算法實例效果圖

利用查找建筑物結(jié)構(gòu)關(guān)鍵字和改進的種子填充算法的建筑物構(gòu)面過程，驗證了改進種子填充算法的完整性和高效性，此方法大大地提高了大比例尺地形圖建筑物構(gòu)面的工作效率，也為大比例尺地形圖中建筑物建庫工作提供另一種可行技術(shù)手段。

5 結(jié) 論

市場經(jīng)濟的發(fā)展和行業(yè)的激烈競爭要求我們以“服務(wù)”的理念和姿態(tài)做事，這種服務(wù)也必須與時俱進、動態(tài)變化。這使得地理信息數(shù)據(jù)建庫的方式、管理的過程都亟待變革，基于改進種子填充算法的GIS數(shù)據(jù)建筑物構(gòu)面建庫處理方式具有高效率、高精度、低成本等優(yōu)點，彌補了傳統(tǒng)AutoCAD建庫方面的不足，大大減少了人機交互工作，所得成果令人滿意。但我們在建庫過程中也發(fā)現(xiàn)了一些不足，如程序處理對原始測繪數(shù)據(jù)要求較高，成果中有漏填充或錯誤填充現(xiàn)象。未來，我們將進一步優(yōu)化該建筑物填充方法，以便將該方法更好的應(yīng)用于GIS建庫。

[1] Chang Fu，Chen Chunjen，Lu Chijen.A linear time component labehng algorithm using contour tracing technique[J]. Computer Vision and Image Understanding，2004，93(2): 206～220.

[2] 施一軍.基于GIS技術(shù)建立地圖數(shù)據(jù)庫的構(gòu)想和實現(xiàn)[J].測繪通報，2011(11):71～73.

[3] 胡云，李盤榮.一種改進的種子填充算法[J].無錫市廣播電視大學(xué)學(xué)報，2008(2)；31～34.

[4] 孫家廣，楊長貴.計算機圖形學(xué)[M].北京:清華大學(xué)出版社，2003:234～247.

[5] 秦曉薇.區(qū)域填充算法的研究[J].赤峰學(xué)院學(xué)報:自然科學(xué)版，2011(6):47～49.

[6] Winters.學(xué)習(xí)MicroStation VBA[M].北京:中國水利水電出版社，2007:194～231.

App lication research ofmodified Seed Filling Algorithm in the Fast Filling Process for Ground Object Data

Song Huaping1，Guo Xin2，Li Jinchuan1
(1.Chongqing Cybercity Sci-tech Co.，Ltd.Chongqing 400020，China； 2.Key Laboratory of Optical Fiber Communication Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)

The data conversion from topographicmaps to GIShas a hugeworkload，especially in the process of building Poindirtize.According to a summary of the characteristics of this type ofworks and the theoretical basis of traditional Seed Filling Algorithm and Scan-Line Seed Filling Algorithm，this paper proposes a modified Seed Filling Algorithm which can realize searching and filling simultaneously and firstly filling then full row accessing the stack according to the direction.By comparing with traditional Seed Filling Algorithm，simulation results show that the new algorithm has the ability to solve the problem of repeated accessing stack.What’smore，new algorithm can reduce the number of requiring stacks，and speed up the building(ground object filling)process.Finally，this paper uses Bentley MicroStation software platform secondary development tool to realize the fast library setting bymodified Seed Filling Algorithm.

modified seed filling algorithm；region filling；secondary development

1672-8262(2013)04-49-04

P208.2，P209

B

2012—10—07

宋華平(1979—)，男，助理工程師，主要從事地理信息系統(tǒng)開發(fā)及數(shù)據(jù)處理等工作。

加快地物building填充速度等優(yōu)點。最后，利用Bentley MicroStation軟件平臺二次開發(fā)工具，實現(xiàn)了改進種子填充算法對建筑物的快速建庫處理。