淺析區(qū)域填充算法

摘 要：區(qū)域填充算法廣泛應(yīng)用于各個領(lǐng)域，經(jīng)典的區(qū)域填充算法存在若干問題，在分析了兩種傳統(tǒng)區(qū)域填充算法的原理的基礎(chǔ)上，闡述了兩種改進(jìn)的區(qū)域填充算法。

關(guān)鍵詞：掃描線填充算法；種子填充算法；鏈隊列

中圖分類號：TP391.41

1 區(qū)域填充概述

區(qū)域填充指的是在輸出平面的閉合區(qū)域內(nèi)使用某種指定的顏色或圖案完整地進(jìn)行填充，通俗點講就是指定一個區(qū)域的邊界，用指定的顏色代碼賦予給邊界范圍內(nèi)的所有像素點。它是計算機(jī)圖形學(xué)的一項重要內(nèi)容，主要廣泛應(yīng)用于真實感圖形顯示、交互式圖形設(shè)計、計算機(jī)輔助設(shè)計等領(lǐng)域，至今依然是研究的熱點問題。

經(jīng)典的區(qū)域填充算法一般分兩大類，一類是掃描線填充；一類是種子填充。掃描線填充有一定難度，而種子填充在掌握了“棧”這一抽象數(shù)據(jù)類型的實現(xiàn)方法的前提下，比較容易完成。

2 經(jīng)典區(qū)域填充算法思想

2.1 掃描線填充算法

掃描線填充算法一般是通過確定橫跨區(qū)域的掃描線的覆蓋間隔來填充完成的算法。它主要用來填充比較簡單的標(biāo)準(zhǔn)多邊形區(qū)域，例如矩形、橢圓及其他一些簡單的多邊形，但是它對輪廓線的形狀有一定的要求，往往在處理復(fù)雜區(qū)域時失效。

掃描線填充算法基本原理是用水平掃描線自上而下對由點、線段構(gòu)成的多段多邊形進(jìn)行掃描，每根掃描線與多邊形每條邊都產(chǎn)生一系列交點，這些交點依照x坐標(biāo)進(jìn)行分類，然后成對取出分類后的交點，作為兩個端點，用所填的顏色畫水平直線，用此方法對多邊形進(jìn)行掃描，掃描完畢的同時也完成了填色。如何正確求得掃描線與區(qū)域內(nèi)外輪廓線的交點，將會成為算法成敗的關(guān)鍵問題，而采用合適的數(shù)據(jù)結(jié)構(gòu)可以簡化操作、提高算法的效率。

經(jīng)典掃描線算法一般采用鄰接鏈表的數(shù)據(jù)結(jié)構(gòu)，每條掃描線在該表中都對應(yīng)有一項，利用表OET與表AET記錄掃描線與多邊形相交的情況。本算法效率雖高，但填充結(jié)果的完備性不是很好，在處理復(fù)雜區(qū)域時，通常不能準(zhǔn)確填充。

2.2 種子填充算法

種子填充算法（又稱邊界填充算法）是從給定的位置開始填充直到指定的邊界為止的填充算法，使用該算法可以解決邊界比較復(fù)雜的多邊形區(qū)域填充問題。使用本算法需要首先確定一個或多個區(qū)域內(nèi)部的點作為種子點，并且賦予其填充色，然后以該像素點為起點，用四向連通方法（或八向連通方法）找到區(qū)域內(nèi)的所有像素點并填充。

種子填充算法基本原理是：從多邊形區(qū)域內(nèi)部的一個點開始，用指定的顏色畫點，由內(nèi)向外達(dá)到圖形邊界為止。

種子填充算法通常用兩種技術(shù)進(jìn)行填充操作：四連通技術(shù)和八連通技術(shù)。四連通算法是從多邊形區(qū)域內(nèi)一個像素點出發(fā)，分別通過向上、向下、向左、向右四個方向到達(dá)區(qū)域內(nèi)的任意像素點，以此達(dá)到填充的效果；八連通算法是從多邊形區(qū)域內(nèi)一個像素點出發(fā)，分別通過向上、向下、向左、向右、向左上、向左下、向右上和向右下八個方向到達(dá)區(qū)域內(nèi)的任意像素點，以此達(dá)到填充的效果。

2.3 經(jīng)典算法弊端

掃描線算法的一個明顯問題是在處理帶水平邊的凹拐點時不能準(zhǔn)確填充，然后基于掃描線上像素點之間的連貫性，因此本算法尚具有較高的效率。

而種子填充算法采用遞歸方法，需要進(jìn)行大量的出入棧操作，因此效率較低，在填充較大的區(qū)域時，要求分配較大的堆棧空間，這樣不僅浪費(fèi)了內(nèi)存，同時有可能出現(xiàn)堆棧溢出的現(xiàn)象。衡量區(qū)域填充算法的標(biāo)準(zhǔn)是填充結(jié)果的完備性和填充過程的高速高效性，針對以上問題在傳統(tǒng)區(qū)域填充算法的基礎(chǔ)上，很多文獻(xiàn)提出了更加正確高效的算法。

3 種子填充算法的改進(jìn)

3.1 基于掃描線種子填充算法的改進(jìn)

經(jīng)典的掃描線種子填充算法對搜索新種子點的操作和種子所在掃描線的填充是分別進(jìn)行的，這就需要對大量的像素點進(jìn)行重復(fù)判斷和讀取。為了搜索新種子像素點和對當(dāng)前的掃描線填充，因此需要對當(dāng)前的掃描線和與其相鄰的上、下掃描線進(jìn)行掃描，這就會造成多數(shù)掃描線被重復(fù)掃描，即便是該掃描線上的像素點已經(jīng)全部被填充也還是要被再次掃描，這樣就可能出現(xiàn)被掃描3次，降低了程序的效率和運(yùn)行速度。

此外，在該算法中堆棧操作頻繁，每搜到一個新的填充區(qū)間就要入棧，對每一條掃描線至少有一個區(qū)間入棧，每次開始另一條掃描線搜索都要先出棧，這不僅占用了大量的儲存空間，還降低了算法的效率。

對于經(jīng)典區(qū)域填充算法的欠缺，文獻(xiàn)[1]提出了一種新的區(qū)域填充掃描線算法。文獻(xiàn)[1]中所描述的算法在掃描時采用的是對于同一條掃描線上出現(xiàn)多個填充區(qū)域時，分成向上搜索和向下搜索兩種情況，每種情況又都可能出現(xiàn)多個搜索新區(qū)；在填充過程中，考慮到當(dāng)前區(qū)間上下相關(guān)性和左右連續(xù)性，只需將出現(xiàn)的新搜索區(qū)域壓入堆棧，不需要將相鄰的每根掃描線都壓入堆棧，進(jìn)而減少了像素點的重復(fù)判斷與讀取，同時也較少了回溯區(qū)的搜索時間，以此來避免不必要的進(jìn)出棧處理，提高填充效率。

3.2 基于鏈隊列的種子填充法

文獻(xiàn)[2]針對遞歸種子算法的提出了改進(jìn)算法，在該算法中使用鏈隊列而不是遞歸，而且采用了先填充后入隊列，減少了很多不必要的操作，使得改進(jìn)后的算法效率都大大優(yōu)于遞歸種子填充算法，無論是在時間上還是空間上，而且也可以填充任意大小、任意復(fù)雜邊界的區(qū)域。

經(jīng)典的遞歸種子填充算法，采用的是先入棧，然后出棧，再填充，也就是可以理解為當(dāng)填充某一個像素點時，無論它的四連通點是否已被填充，都是要進(jìn)入堆棧，因此會導(dǎo)致很多的冗余像素點進(jìn)入堆棧；改進(jìn)后的種子填充算法使用鏈隊列種子填充算法，首先進(jìn)行填充，然后再進(jìn)入鏈隊列，在入隊列之前需要判斷像素點是否已被填充，如果已經(jīng)被填充，并剛進(jìn)入隊列，則不予考慮，這樣將會減少進(jìn)入隊列的冗余像素點，也就是每一個像素點只入隊列一次。

上述改進(jìn)的算法避免了經(jīng)典遞歸種子填充算法因為一個像素點重復(fù)進(jìn)入堆棧操作，而導(dǎo)致速度過慢的問題。但經(jīng)過研究發(fā)現(xiàn)修改后的算法，仍存在很多冗余的檢測。繼而提出新的修改思路：分別設(shè)置4個鏈隊列用來記錄上、下、左、右4個方向的填充新種子像素點，如果此時正在出隊的像素點來自于記錄向上的那個隊列，則不要檢測該像素點的下面那個像素點，這樣在填充某個像素點時只需要檢測它的上、左、右3個連通像素點就可以了。

4 結(jié)束語

近年來計算機(jī)圖形學(xué)技術(shù)發(fā)展迅速，并在很多行業(yè)得以應(yīng)用，區(qū)域填充算法也因此在很多領(lǐng)域得到了廣泛應(yīng)用，這使得對填充算法的研究不僅局限于完備性和效率方面，如何實現(xiàn)填充的完全自動化將成為研究熱點。

參考文獻(xiàn)：

[1]張榮國，劉焜.新區(qū)入棧的區(qū)域填充掃描線算法[J].計算機(jī)工程，2006（05）：63-65.

[2]陳元琰，陳洪波.一種基于鏈隊列的種子填充法[J].廣西師范大學(xué)學(xué)報（自然科學(xué)版），2003（03）：31-33.

作者簡介：石燕（1981.01-），女，河南濟(jì)源人，教師，助教，碩士，研究方向：面向?qū)ο蟆?/p>

作者單位：河南牧業(yè)經(jīng)濟(jì)學(xué)院（英才校區(qū)） 計算機(jī)系，鄭州 450000