王利祥

（河南護(hù)理職業(yè)學(xué)院 河南 安陽 455000）

1 引言

隨著社會科學(xué)技術(shù)的飛速發(fā)展，數(shù)字圖像處理技術(shù)也得到了很快的發(fā)展，尤其是計算機和網(wǎng)絡(luò)技術(shù)出現(xiàn)以后，數(shù)字圖像處理技術(shù)漸漸的占據(jù)了圖像處理技術(shù)領(lǐng)域的整個區(qū)域。隨著數(shù)字圖像在社會生活和工作中扮演的角色越來越重要，圖像處理理論和技術(shù)研究也越來越受到了各個領(lǐng)域的廣泛關(guān)注。與此同時，伴隨著4G+以及互聯(lián)網(wǎng)+時代的到來，移動終端設(shè)備比如手機、pad、筆記本電腦等的高速發(fā)展，特別是手機的功能逐漸強大，人們對圖形圖像處理的實時性和智能化提出了更高的要求。因此研究和完善并且使用更加高效的區(qū)域填充算法[1]仍然具有很高的研究價值和應(yīng)用市場。

2 研究背景及意義

在計算機對現(xiàn)實中的圖形圖像進(jìn)行存儲時，只是對圖形圖像的邊緣以及內(nèi)部填充的顏色進(jìn)行存儲，當(dāng)計算機對這些數(shù)據(jù)處理時，需要對存儲的這些數(shù)據(jù)進(jìn)行復(fù)原。在復(fù)原的過程中，首先要判斷出圖形圖像元素的邊界線或簡單的特定區(qū)域，然后對邊界線內(nèi)部進(jìn)行渲染，整個過程我們稱之為區(qū)域填充。

區(qū)域填充算法屬于計算機圖形學(xué)應(yīng)用和研究中的基本算法之一，屬于計算機圖形學(xué)與圖像處理兩大學(xué)科領(lǐng)域交叉的基本問題之一，它在實際應(yīng)用廣泛應(yīng)用圖像處理、目標(biāo)分析以及計算機圖形學(xué)中的其他領(lǐng)域。

3 區(qū)域填充算法的研究

傳統(tǒng)的區(qū)域填充算法主要有邊界標(biāo)志區(qū)域填充算法、種子區(qū)域填充算法、邊界區(qū)域填充算法和掃描線區(qū)域填充算法。

3.1 邊界標(biāo)志填充算法

該算法又稱為邊標(biāo)志算法，其大致思想為：首先使用直線光柵化算法繪制出圖形圖像的邊界線，在此過程中會得到掃描區(qū)域中橫縱坐標(biāo)的最大值和最小值，即掃描線的方形掃描區(qū)域，然后對掃描區(qū)域進(jìn)行掃描填充，即可得到復(fù)原的圖形圖像。該算法的優(yōu)點在于：

（1）不需要對像素點進(jìn)行求交集運算以及對每個邊界線的交點也不需要進(jìn)行排序；

（2）對掃描區(qū)域中的每個像素點只訪問一次，因此計算效率高、時間復(fù)雜度小。

3.2 種子填充算法

傳統(tǒng)的種子填充算法，無論是基本的簡單種子填充算法還是基于掃描線來實現(xiàn)的掃描線種子填充算法，其大致思想是基本類似的：首先從多邊形區(qū)域內(nèi)部選擇某一個像素點，該像素點我們稱之為種子點，然后以該種子點作為起點，依次訪問種子點上下左右連通的四個點，當(dāng)訪問所有的像素點之后，分別依次使用四周的點作為新的種子點，使用相同的方法進(jìn)行訪問，直至整個多邊形區(qū)域都被填充。種子填充算法的優(yōu)點是由于經(jīng)過多次遞歸，其實現(xiàn)原理和程序都比較簡單。缺點是算法遞歸次數(shù)較多，進(jìn)出棧比較頻繁，因此執(zhí)行效率不高，占用內(nèi)存較大、空間復(fù)雜度較大；第一個種子點的尋找難度比較大；存在有的像素點會被重復(fù)訪問的現(xiàn)象。

種子填充算法根據(jù)區(qū)域連通性的不同可以分為八連通區(qū)域和四連通區(qū)域，因此在實際使用過程中，經(jīng)常使用到的種子填充算法有邊界表示的八連通區(qū)域種子填充算法、內(nèi)點表示的八連通區(qū)域種子填充算法、內(nèi)點表示的四連通區(qū)域種子填充算法、邊界表示的四連通區(qū)域種子填充算法。

3.3 掃描線填充算法

該算法適合對適量圖形進(jìn)行填充，只需要確定多邊形區(qū)域的幾何位置即可，算法的核心是求交運算。基本思想大致為：首先使用水平掃描線依次從橫坐標(biāo)最小的掃描線到橫坐標(biāo)最大的掃描線掃描，每條掃描線都會與多邊形的某些邊界線產(chǎn)生一系列交點，然后將這些交點按照橫坐標(biāo)的值進(jìn)行排序，將排序之后的點兩兩配對，作為線段的兩個端點，最后將兩個端點之間的線段填充所需要的顏色即可。該算法經(jīng)常與種子填充算法結(jié)合使用，稱為掃描線種子填充算法。該算法的優(yōu)點在于實現(xiàn)簡單方便，缺點為求交運算量大、需要對點進(jìn)行排序、空間復(fù)雜度較大。

3.4 邊界填充算法

該算法的基本思想是從指定位置開始，將所有連通區(qū)域內(nèi)某種指定顏色的點都替換成另一種顏色，從而實現(xiàn)填充效果。該算法在實現(xiàn)時對于邊界以內(nèi)的像素點無論是需要填充為什么顏色，都替換為指定的顏色。鑒于邊界填充算法對邊界線的要求比較明顯，因此在實際應(yīng)用中也是非常廣泛的，比如圖形處理軟件中經(jīng)常使用到的“油漆桶”功能就是邊界填充算法使用的一個很好的例子。它的優(yōu)點在于實現(xiàn)簡單，而且與邊的順序沒有關(guān)系；缺點有：存在有些像素點會被重復(fù)訪問的想象，同樣也需要對每條掃描線與多邊形區(qū)域[2]的某些邊界進(jìn)行求交運算。

4 掃描線區(qū)域填充算法的實現(xiàn)

本文在深入研究大多數(shù)區(qū)域填充算法的基礎(chǔ)上，經(jīng)過對上述傳統(tǒng)填充算法的對比，最終選擇一種將掃描線填充算法和種子填充算法相結(jié)合的掃描線種子填充算法[3]作為更深入的研究點，然后進(jìn)行了算法的實現(xiàn)。該算法不再使用遞歸的方式來處理八連通區(qū)域和四連通區(qū)域的相鄰像素點，這樣在算法處理過程中只需要將每個水平像素段的起始點存放到一個棧中，這樣的話就不需要像使用遞歸算法那樣將當(dāng)前像素點周圍的所有相鄰像素點全部進(jìn)棧，從而節(jié)省內(nèi)存空間，降低算法的空間復(fù)雜度，而是沿水平掃描線填充像素段，一段一段的來處理四連通區(qū)域和八連通區(qū)域的相鄰像素點。

算法的基本過程如下：假設(shè)給定的種子點為(x，y)，首先以該種子點為中心，分別向種子點的左右兩個方向填充所需要的填充色，確定當(dāng)前種子點所在的掃描線位于掃描區(qū)域內(nèi)的像素點范圍，并記為[X_Left，Y_Right]，由左右范圍即可確定這一段區(qū)域的連通性，然后確定該連通區(qū)域上、下掃描線位于需要填充區(qū)域的像素點，然后對這些像素點依次進(jìn)棧保存。重復(fù)上述的過程，直至整個填充區(qū)域的像素點都被填充為止。

算法的實現(xiàn)步驟大致可由下列四步實現(xiàn)：

（1）在內(nèi)存中定義一個空棧，其作用是為了存放掃描過程中的種子點，首先將已知的種子點(x，y)進(jìn)棧；

（2）在每次進(jìn)行出棧操作時都要判斷當(dāng)前棧是否為空棧，如果為空棧，表示需要填充的區(qū)域已經(jīng)填充完畢，此時終止算法即可，否則棧頂元素出棧并作為新的種子點進(jìn)行掃描；

（3）從當(dāng)前種子點出發(fā)，分別沿著當(dāng)前的掃描線向種子點的左右兩個方向?qū)呙杈€上的相鄰像素點進(jìn)行填充。直到遇到多邊形區(qū)域的邊界線為止，此時分別標(biāo)記當(dāng)前區(qū)段的左右兩個端點的橫坐標(biāo)為X_Left和X_Right；

（4）分別檢查與當(dāng)前掃描線相鄰的上下兩條掃描線在區(qū)間[X_Left，X_Right]中的像素點，此時從X_Left開始向X_Right方向?qū)τ龅降南袼攸c進(jìn)行填充，如果遇到非邊界像素點而且是未填充的，則找到這些像素點相鄰的最右側(cè)的一個，并將其作為種子點進(jìn)棧，然后重新執(zhí)行第（2）步。

5 結(jié)語

區(qū)域填充算法在圖形圖像處理中經(jīng)常用到，具有很高的理論和應(yīng)用價值。因此對各種場景提出不同的有針對性的區(qū)域填充算法的研究一直備受關(guān)注。本文首先闡述了區(qū)域填充算法的應(yīng)用背景及研究意義，對區(qū)域填充算法的定義進(jìn)行了闡述，然后針對傳統(tǒng)的區(qū)域填充算法進(jìn)行了深入研究，分別論述了四種不同填充算法的實現(xiàn)思想和優(yōu)缺點，最后選擇了掃描線填充算法和種子填充算法作為結(jié)合體，并對掃描線種子填充算法進(jìn)行了實現(xiàn)，并列舉出實現(xiàn)過程。為后續(xù)的研究奠定了一定的基礎(chǔ)。