掃描線種子區(qū)域填充算法的研究與實(shí)現(xiàn)

王利祥

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

1 引言

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

2 研究背景及意義

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

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

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

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

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

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

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

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

3.2 種子填充算法

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

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

3.3 掃描線填充算法

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

3.4 邊界填充算法

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

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

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

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

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

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

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

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

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

5 結(jié)語

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