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

宋華平，郭鑫，李晉川

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

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

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

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

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

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

1 引 言

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

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

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

2 種子填充法及其改進(jìn)思想

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

2.1 種子填充算法

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

圖1 連通方向示意圖

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

2.2 改進(jìn)種子填充算法思想

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

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

struct node{

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

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

}

Link_Stack；

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

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

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

算法步驟如下:

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

②對(duì)Y行進(jìn)行左、右方向搜索，并把填充后種子點(diǎn)存入隊(duì)列Filled。Xl[Y]和Xr[Y]分別表示Y行最左端點(diǎn)和最右端點(diǎn)，這樣掃描的種子像素時(shí)范圍僅限于Xl[Y]≤x≤Xr[Y](x∈Filled)，此時(shí)滿足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ū)域搜索和填充的起始信息。保留起始信息的左右端點(diǎn)至Xpl和Xpr中，根據(jù)起始信息中記錄的方向在區(qū)間[Xpl，Xpr]內(nèi)搜索下一條掃描行，若搜索到未填充點(diǎn)，則以其為種子點(diǎn)，重復(fù)②步驟。若在區(qū)間[Xpl，Xpr]內(nèi)所有點(diǎn)都為邊界像素或已填充像素，則說明當(dāng)前連續(xù)區(qū)域已填充完畢，轉(zhuǎn)步驟③。

圖2 改進(jìn)種子填充算法流程圖

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

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

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

Filledpoint()//存儲(chǔ)已填充點(diǎn)

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

//算法開始:

while(!StackEmpty())

point=Pop()；

if(Flag[Y]==false)

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

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

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

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

else

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

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

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

上述算法的難點(diǎn)在于找到掃描行Y的未被填色的最左端點(diǎn)Xl和最右端點(diǎn)Xr后對(duì)其填色。可以分析的情形有三種，如圖3所示:包括行單區(qū)間連續(xù)(圖3之a(chǎn))；行多區(qū)間連續(xù)(圖3之b)；行多區(qū)間不連續(xù)(圖3之c)。采用兩端逼近的算法來解決，最終解決的時(shí)間復(fù)雜度都為O(n)。

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

3 算法比較

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

運(yùn)行結(jié)果對(duì)比表 表1

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

4 示范應(yīng)用

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

圖4 算法實(shí)例效果圖

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

5 結(jié) 論

市場經(jīng)濟(jì)的發(fā)展和行業(yè)的激烈競爭要求我們以“服務(wù)”的理念和姿態(tài)做事，這種服務(wù)也必須與時(shí)俱進(jìn)、動(dòng)態(tài)變化。這使得地理信息數(shù)據(jù)建庫的方式、管理的過程都亟待變革，基于改進(jìn)種子填充算法的GIS數(shù)據(jù)建筑物構(gòu)面建庫處理方式具有高效率、高精度、低成本等優(yōu)點(diǎn)，彌補(bǔ)了傳統(tǒng)AutoCAD建庫方面的不足，大大減少了人機(jī)交互工作，所得成果令人滿意。但我們?cè)诮◣爝^程中也發(fā)現(xiàn)了一些不足，如程序處理對(duì)原始測繪數(shù)據(jù)要求較高，成果中有漏填充或錯(cuò)誤填充現(xiàn)象。未來，我們將進(jì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)想和實(shí)現(xiàn)[J].測繪通報(bào)，2011(11):71～73.

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

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

[5] 秦曉薇.區(qū)域填充算法的研究[J].赤峰學(xué)院學(xué)報(bào):自然科學(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)點(diǎn)。最后，利用Bentley MicroStation軟件平臺(tái)二次開發(fā)工具，實(shí)現(xiàn)了改進(jìn)種子填充算法對(duì)建筑物的快速建庫處理。