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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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