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

1、圖形學(xué)期末作業(yè)區(qū)域填充算法的探究1摘要本文旨在通過探究區(qū)域填充算法尤其是掃描線種子填充算法和種子填充算法近年來的發(fā)展?fàn)顩r，比較它們之間的優(yōu)點(diǎn)與不足，對(duì)圖形學(xué)的區(qū)域填充算法有更深入的理解。在準(zhǔn)備本報(bào)告的同時(shí)還加以實(shí)驗(yàn)環(huán)節(jié)，選用掃描線填充算法和掃描線種子填充算法來對(duì)算法加以驗(yàn)證、調(diào)試和理解。2 區(qū)域填充基本知識(shí)點(diǎn)介紹2.1多邊形掃描轉(zhuǎn)換在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。頂點(diǎn)表示是用多邊形的頂點(diǎn)序列來表示多邊形，特點(diǎn)直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換，但由于它沒有明確指出哪些像素在多邊形內(nèi)，故不能直接用于面著色。點(diǎn)陣表示是用位于多邊形內(nèi)的像素集合來刻畫多邊形

2、。這種表示丟失了許多幾何信息，但便于幀緩沖器表示圖形，是面著色所需要的圖形表示形式。光柵圖形的一個(gè)基本問題是把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換。多邊形可分為凸多邊形、凹多邊形、含內(nèi)環(huán)多邊形。（1）凸多邊形：任意兩頂點(diǎn)間的連線均在多邊形內(nèi)。（2）凹多邊形：任意兩頂點(diǎn)間的連線有不在多邊形內(nèi)的部分。（3）含內(nèi)環(huán)多邊形：多邊形內(nèi)包含有封閉多邊形。掃描線多邊形區(qū)域填充算法是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素。區(qū)間的端點(diǎn)可以通過計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。對(duì)于一條掃描線，多邊形的填充過程可以分為4個(gè)步驟。（1）求交：計(jì)算掃描線與

3、多邊形各邊的交點(diǎn)。（2）排序：把所有交點(diǎn)按x值遞增順序排序。（3）配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等，每對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)相交區(qū)間。（4）填色：把相交區(qū)間內(nèi)的像素置成多邊形顏色，把相交區(qū)間外的像素置成背景色。多邊形掃描轉(zhuǎn)換算法步驟如下：（1）初始化：構(gòu)造邊表。（2）對(duì)邊表進(jìn)行排序，構(gòu)造活性邊表。（3）對(duì)每條掃描線對(duì)應(yīng)的活性邊表中求交點(diǎn)。（4）判斷交點(diǎn)類型，并兩兩配對(duì)。（5）對(duì)符合條件的交點(diǎn)之間用畫線方式填充。（6）下一條掃描線，直至滿足掃描結(jié)束條件。2.2區(qū)域填充算法這里的區(qū)域指已表示成點(diǎn)陣形式的填充圖形，是像素的集合。區(qū)域有兩種表示形式：內(nèi)點(diǎn)表示和邊界表示，如圖2-1所示。內(nèi)

4、點(diǎn)表示，即區(qū)域內(nèi)的所有像素有相同顏色；邊界表示，即區(qū)域的邊界點(diǎn)有相同顏色。區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。 圖2-1 區(qū)域的內(nèi)點(diǎn)表示和邊界表示 圖2-2 4連通區(qū)域和8連通區(qū)域區(qū)域填充算法要求區(qū)域是連通的。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域，如圖2-2所示。4向連通區(qū)域指的是從區(qū)域上一點(diǎn)出發(fā)，可通過四個(gè)方向，即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素；8向連通區(qū)域指的是從區(qū)域內(nèi)每一像素出發(fā)，可通過8個(gè)方向，即上、下、左、右、左上、右上、左下、右下這八個(gè)方向的移動(dòng)的組合來到達(dá)。2.2.1區(qū)域填充的掃描線算法算法的基本過程如下

5、：給定種子點(diǎn)（x，y），首先填充種子點(diǎn)所在掃描線上給定區(qū)域的一個(gè)區(qū)段，然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個(gè)過程，直到填充結(jié)束。 求出ymin ymax開始結(jié)束ymin yy+1 y求出由掃描線y確定的水平線與多邊形兩個(gè)交點(diǎn)（x1，y），（x2，y）將（x1，y）與（x2，y）連接y>ymaxNY圖2-3掃描線填充算法流程圖區(qū)域填充的掃描線算法可由下列3個(gè)步驟實(shí)現(xiàn)。Step1：求出每條水平掃描線與多邊形各邊的交點(diǎn)。Step2：將每條水平掃描線上的交點(diǎn)按X值遞增的順序排列。Step3：將交點(diǎn)的交點(diǎn)配成“交點(diǎn)對(duì)”。Step4：在交點(diǎn)對(duì)間填色

6、。2.2.2區(qū)域填充的種子算法種子填充算法又稱為邊界填充算法。其基本思想是：從多邊形區(qū)域的一個(gè)內(nèi)點(diǎn)開始，由內(nèi)向外用給定的顏色畫點(diǎn)直到邊界為止。如果邊界是以一種顏色指定的，則種子填充算法可逐個(gè)像素地處理直到遇到邊界顏色為止。種子填充算法常用四連通域和八連通域技術(shù)進(jìn)行填充操作。從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素。用這種方法填充的區(qū)域就稱為四連通域；這種填充方法稱為四向連通算法。從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右、左上、左下、右上和右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素。用這種方法填充的區(qū)域就稱為八連通域；這種填充方法稱為八向連通算法。 a) 連通域及其內(nèi)點(diǎn) b)

7、填充四連通域 圖2-4 四向連通填充算法一般來說，八向連通算法可以填充四向連通區(qū)域，而四向連通算法有時(shí)不能填充八向連通區(qū)域。例如，八向連通填充算法能夠正確填充如圖2-4a所示的區(qū)域的內(nèi)部，而四向連通填充算法只能完成如圖2-4b的部分填充。3區(qū)域填充算法日新月異的發(fā)展 上面所提到的區(qū)域填充算法，掃描線算法和種子填充算法適用條件苛刻，要么對(duì)所要填充的多邊形有一定的局限性，要么就是由于采用遞歸次數(shù)太多，區(qū)域內(nèi)的每個(gè)像素都引起一次遞歸，即系統(tǒng)堆棧的一次進(jìn)出操作，費(fèi)時(shí)費(fèi)內(nèi)存。因而許多改進(jìn)的算法便從減少遞歸的次數(shù)入手來提高算法的效率，區(qū)域填充的掃描線種子算法就是其中具有代表性的一個(gè)。3.1掃描線種子填充算

8、法3.1.1掃描線種子填充算法的基本思想首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來。反復(fù)這個(gè)過程，直到所保存的各區(qū)段都填充完畢。3.1.2掃描線種子填充算法實(shí)現(xiàn)步驟如下：1、初始化堆棧。2、種子壓入堆棧。3、while（堆棧非空）(1)從堆棧彈出種子象素。(2)如果種子象素尚未填充，則： a.求出種子區(qū)段：xleft、xright;b.填充整個(gè)區(qū)段。c.檢查相鄰的上掃描線的xleftxxright區(qū)間內(nèi),是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright

9、范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。d.檢查相鄰的下掃描線的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。 3.1.3掃描線種子填充算法的特點(diǎn)1、該算法考慮了掃描線上象素的相關(guān)性，種子象素不再代表一個(gè)孤立的象素，而是代表一個(gè)尚未填充的區(qū)段。2、進(jìn)棧時(shí)，只將每個(gè)區(qū)段選一個(gè)象素進(jìn)棧（每個(gè)區(qū)段最右邊或最左邊的象素），這樣解決了堆棧溢出的問題。3、種子出棧時(shí)，則填充整個(gè)區(qū)段。4、這樣有機(jī)的結(jié)合：一邊對(duì)尚未填充象素的登記（象素進(jìn)棧），一邊進(jìn)行填充（象素出棧），既可以節(jié)省堆

10、?？臻g，又可以實(shí)施快速填充。3.2基于掃描線種子填充算法的改進(jìn) 由3.1的描述可以看出，對(duì)種子所在掃描線的填充與搜索新種子點(diǎn)的操作是分別進(jìn)行的，這就需要對(duì)大量的像素進(jìn)行重復(fù)判讀。為了對(duì)當(dāng)前的掃描線填充和搜索新種子像素，需要對(duì)當(dāng)前掃描線以及其相鄰的上下掃描線等3條掃描線進(jìn)行掃描，這就使得多數(shù)掃描線被重復(fù)掃描，即使該掃描線上的像素已經(jīng)全部填充也要被再次掃描。甚至掃描3次，大大降低了程序的效率和運(yùn)行速度。另外，在該算法中堆棧操作頻繁，每搜到一個(gè)新的填充區(qū)間就要入棧，對(duì)每一條掃描線至少有一個(gè)區(qū)間入棧每次開始另一條掃描線搜索都要先出棧，這不僅占用了大量的儲(chǔ)存空間，還降低了算法的效率。針對(duì)重復(fù)掃描的問題，

11、文獻(xiàn)【1】根據(jù)當(dāng)前掃描線與相鄰掃描線間的位置關(guān)系以及區(qū)間端點(diǎn)的坐標(biāo)大小減少了不必要的重復(fù)掃描，縮小了重復(fù)掃描區(qū)間范圍，但是所提出的算法仍然將填充與搜索新種子點(diǎn)的操作分別進(jìn)行，沒有克服堆棧頻繁操作的缺點(diǎn)，文獻(xiàn)【2】將種子點(diǎn)入棧改為新舊區(qū)間端點(diǎn)入棧，并將區(qū)間填充與搜索新區(qū)間合并進(jìn)行，進(jìn)一步減少了重復(fù)掃描但是算法中并沒有減少堆棧操作的頻率，并且對(duì)每一條當(dāng)前掃描線都要判斷其相鄰的兩條掃描線是否需要重復(fù)掃描【3】。針對(duì)傳統(tǒng)區(qū)域填充的一些欠缺，文獻(xiàn)【4】提出了一種新的區(qū)域填充掃描線算法。該算法在處理同一條掃描線上的多個(gè)填充區(qū)域時(shí)，分成向上搜索和向下搜索兩種情況進(jìn)行，每種情況又都可能出現(xiàn)多個(gè)搜索新區(qū)；在填充

12、過程中，考慮到當(dāng)前區(qū)間左右連續(xù)性和上下相關(guān)性，只需將出現(xiàn)的新搜索區(qū)壓入堆棧，不需要將相鄰的每根掃描線都?jí)喝攵褩?，從而減少了像素的重復(fù)判讀和會(huì)回溯區(qū)的搜索時(shí)間，避免了不必要的進(jìn)出棧處理，提高了填充效率。為了存儲(chǔ)對(duì)每個(gè)新區(qū)進(jìn)行搜索的起始位置，定義一個(gè)棧用以存放其信息，存儲(chǔ)結(jié)構(gòu)如下：Typedf Struct Stack_nodeInt xleft;/左邊界X坐標(biāo)Int xright;/ 右邊界X坐標(biāo)Int yscan;/掃描線Y坐標(biāo)Int direction;/搜索方向Struct Stack_node *next；*Link_Stack;Link_Stack S; 新區(qū)入棧的區(qū)域填充掃描算法的步

13、驟：Step1:對(duì)存儲(chǔ)新區(qū)信息的堆棧進(jìn)行初始化；Step2：給定填充區(qū)域內(nèi)一點(diǎn)作為種子點(diǎn)，左搜索左填充，得到左邊界xl；右搜索右填充，得到右邊界xr ； 將向上搜索的起始信息（xl，xr，y，1）；右搜索右填充得到起始信息（xl，xr，y，-1）分別壓入堆棧。Step3：若?？?，則填充過程完成，程序結(jié)束；否則，執(zhí)行以下步驟。Step4：判斷當(dāng)前的搜索過程是在主搜索區(qū)還是在新區(qū)，若在新區(qū)，則將棧頂元素出棧，并將出棧信息作為新區(qū)的起始搜索信息；若在主搜索區(qū)，則將上次搜索的結(jié)果作為對(duì)下條掃描線進(jìn)行填充的信息；Step5：判斷當(dāng)前搜索點(diǎn)是否已經(jīng)達(dá)到該掃描線區(qū)域的最右端，若是轉(zhuǎn)Step8，否則，執(zhí)行以下

14、步驟；Step6：若當(dāng)前搜索點(diǎn)時(shí)區(qū)域內(nèi)的一點(diǎn)，并且未填充，則以其為種子點(diǎn)，左搜索左填充，得到左邊界xl；右搜索右填充得到右邊界xr；Step7：若找到的第一個(gè)可填充區(qū)域，則記錄下該區(qū)的左右邊界；若找到多個(gè)可填充區(qū)域，則將除了第一個(gè)以外的其他區(qū)壓入堆棧；Step8：將向上搜索過程中可能出現(xiàn)的下回溯區(qū)和向下搜索過程中可能出現(xiàn)的上回溯區(qū)作為搜索新區(qū)分別入棧；然后轉(zhuǎn)Step3【4】。3.3 一種基于鏈隊(duì)列的種子填充法文獻(xiàn)【5】提出了遞歸種子算法的改進(jìn)算法，在該算法中使用鏈隊(duì)列而不是遞歸，而且采用先填充后入隊(duì)列，減少了很多不必要的操作，使得改進(jìn)后的算法無論是時(shí)間還是空間效率都遠(yuǎn)遠(yuǎn)優(yōu)于遞歸種子填充算法，而

15、且也可以填充任意大小、任意復(fù)雜邊界的區(qū)域。3.3.1 種子算法的改進(jìn)之一 算法基本思想思路是：從鏈隊(duì)列中獲得一個(gè)像素點(diǎn)，判斷其四連通像素點(diǎn)，若沒有填充，則填充它，并將它入隊(duì)列，如此循環(huán)，直到隊(duì)列空為止。對(duì)遞歸種子填充算法的改進(jìn)之處為： 在遞歸種子填充算法中堆棧是系統(tǒng)預(yù)先設(shè)定的，其大小和存儲(chǔ)區(qū)域已經(jīng)確定，這對(duì)填充的區(qū)域大小有明顯的限制，當(dāng)堆棧溢出時(shí)，程序就會(huì)出錯(cuò)，若堆棧設(shè)定很大，又會(huì)導(dǎo)致在填充區(qū)域不大的情況下，浪費(fèi)了很多計(jì)算機(jī)資源，本算法不使用遞歸，而使用鏈隊(duì)列，是因?yàn)殒滉?duì)列有兩個(gè)特點(diǎn)：一是當(dāng)鏈隊(duì)列為空時(shí)，它不占用存儲(chǔ)空間，只有當(dāng)數(shù)據(jù)入鏈隊(duì)列時(shí)才分配存儲(chǔ)空間給它。二是由于在定義鏈隊(duì)列前沒有限定它

16、的大小，所以從理論上看，有多大的可使用存儲(chǔ)空間，就可以建立多大的鏈隊(duì)列。 在遞歸種子填充算法中，采用的是先入棧，出棧后再填充，即當(dāng)填充某像素點(diǎn)時(shí)，不管它的四連通點(diǎn)是否已被填充，都要進(jìn)入堆棧，這會(huì)導(dǎo)致很多的冗余像素點(diǎn)入棧，而本文算法采用的是先填充再入鏈隊(duì)列，在入隊(duì)列之前要判斷像素點(diǎn)是否已被填充 若已被填充才入隊(duì)列 否則不予考慮。這樣將會(huì)減少入隊(duì)列的冗余像素，即每一個(gè)像素點(diǎn)只入隊(duì)列一次。3.3.2 種子算法的改進(jìn)之二 以上算法的改進(jìn)克服了遞歸種子填充算法由于一個(gè)像素點(diǎn)重復(fù)入棧操作而導(dǎo)致速度很慢的問題，但經(jīng)過研究發(fā)現(xiàn)以上改進(jìn)之后，仍存在很多冗余的檢測(cè)。如圖3-1所示，當(dāng)像素P出隊(duì)列時(shí)，要檢測(cè)像素1，

17、3，5，7的顏色是否是填充色或邊界色。而當(dāng)像素1出隊(duì)列時(shí)顯然P像素已經(jīng)被填充，而仍要檢測(cè)像素P的顏色。同理，當(dāng)像素3，5，7出隊(duì)列時(shí)分別也要檢測(cè)像素P的顏色，這樣也會(huì)浪費(fèi)一些時(shí)間。所以我們?cè)诟倪M(jìn)一的基礎(chǔ)上進(jìn)一步提出改進(jìn)二的算法。改進(jìn)的思路是這樣的，設(shè)置4個(gè)鏈隊(duì)列分別記錄向上、向下、向左、向右4個(gè)方向的填充新種子像素點(diǎn).若當(dāng)正在出隊(duì)的像素點(diǎn)是來自于記錄向上的那個(gè)隊(duì)列，不要檢測(cè)它的下面那個(gè)像素點(diǎn)，則在處理某個(gè)像素點(diǎn)時(shí)只要檢測(cè)3個(gè)連通像素點(diǎn)。這里設(shè)置了4個(gè)鏈隊(duì)列，是否增加了程序的存儲(chǔ)開銷呢？答案是否定的。因?yàn)椴捎玫氖擎滉?duì)列，只有當(dāng)像素入隊(duì)列時(shí)才會(huì)占用存儲(chǔ)空間。經(jīng)過對(duì)程序的測(cè)試可得，第一次改進(jìn)時(shí)，每個(gè)

18、像素只入隊(duì)列一次，同樣設(shè)4個(gè)鏈隊(duì)列，每個(gè)像素點(diǎn)也只入一次隊(duì)列，所以總的入隊(duì)列次數(shù)是一樣的【5】。圖3-2 第一次改進(jìn)后的像素監(jiān)測(cè) 4程序運(yùn)行調(diào)試作為本次區(qū)域填充算法探究的實(shí)踐部分我選擇掃描線種子填充算法和掃描線算法進(jìn)行調(diào)試觀測(cè)，經(jīng)過查閱紙質(zhì)資料、互聯(lián)網(wǎng)相關(guān)內(nèi)容以及朋友的協(xié)助下，最終調(diào)試運(yùn)行成功。5結(jié)束語通過查閱大量的圖形學(xué)區(qū)域填充相關(guān)資料，總結(jié)了近年來在區(qū)域填充方面一些算法，并且闡述各自的優(yōu)劣。分別以掃描線種子填充算法和種子填充算法兩條主線探究圖形學(xué)方面的專家逐步改善區(qū)域填充算法提高算法效率的過程。經(jīng)過近三周的對(duì)區(qū)域填充算法的進(jìn)一步學(xué)習(xí)、整理和總結(jié)，更加熟悉了算法本身以及大家一直在試圖改善算法的入手點(diǎn)。在整個(gè)準(zhǔn)備的過程中既有自己的努力，也有他人的幫助，感謝老師本學(xué)期給我的指導(dǎo)，同時(shí)也感謝兩位師兄，他們?cè)?/p>