[發明專利]一種解決種子填充算法中像素多次出入棧問題的方法

無效

• 申請號: 201210139736.8
• 申請日: 2012-05-08
• 公開（公告）號: CN102693525A
• 公開（公告）日: 2012-09-26
• 發明（設計）人: 毛峽;劉運龍;薛雨麗;陳立江
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06T1/60
• 分類號: G06T1/60;G06T11/40
• 代理公司: 暫無信息
• 代理人: 暫無信息

（一）技術領域

本發明涉及一種解決簡單的種子填充算法中存在某些像素多次出入棧結構問題的方法，屬于計算機圖形學區域填充領域。

（二）背景技術

區域填充是指根據區域輪廓線，將其圍成的封閉區域用不同的顏色、灰度、線條或者符號進行填充，該區域可以是帶孔的也可以是不帶孔的。區域填充一般分為兩步進行：第一，確定需要進行填充的像素有哪些；第二，確定用什么顏色值進行填充。區域填充是計算機圖形學圖形生成領域中的一項重要而基本的內容，在交互式圖形設計、圖形分析等領域中有著廣泛的應用，因此一直是計算機圖形學研究的熱點問題之一。

在光柵顯示系統中有兩種傳統的區域填充算法，一種是通過確定橫越區域的掃描線的覆蓋間隔來填充的掃描線算法，另一種是從給定的位置開始填充直到指定的邊界為止的種子填充算法。掃描線算法主要用來填充比較簡單的多邊形區域，比如一些簡單的多邊形和圓，該算法對輪廓線的形狀有一定的要求，在處理復雜區域時往往失效。而種子填充算法則可以很好地解決邊界比較復雜的區域填充問題，該算法通過事先確定需要填充區域內的一些點，這些點被稱為種子點，然后以這些點為起點，用四向連通方法或者八向連通方法尋找區域內的所有點并進行填充。

種子填充算法及在其基礎上進行改進形成的算法目前已經是區域填充的主流算法。可以使用棧結構實現簡單的種子填充算法，算法原理如下：種子像素入棧；當棧非空時重復執行如下三步操作：

(1)棧頂像素出棧；

(2)將出棧像素進行顏色填充；

(3)按順序檢查與出棧像素相鄰的四個像素(四向連通方法)或者八個像素(八向連通方法)，

若其中某個像素不在邊界且未進行顏色填充，則把該像素入棧。

簡單的種子填充算法把太多的像素壓入棧結構，有些像素甚至會多次出入棧結構，一方面在很大程度上降低了算法執行的效率，另一方法還要求很大的存儲空間來實現棧結構。

如果能對已經進入過棧結構的像素進行標志，使得該像素不會再次進入棧結構，這將能很好地解決某些像素多次出入棧結構的問題，在一定程度上降低算法對存儲空間的要求，并提高算法的執行效率。

通過對現有國內資料的分析，發現目前還缺少從實現種子填充算法的三個步驟著手進行分析解決某些像素多次出入棧結構的問題的方法。本發明正是通過分析實現種子填充算法的三個步驟相互之間的關系，提出一種可以簡單有效地解決某些像素多次出入棧結構問題的方法。

（三）發明內容

本發明的目的在于提出一種可以簡單有效地解決種子填充算法中某些像素多次出入棧結構問題的方法，可用于提高傳統種子填充算法執行效率和減少實現棧結構所需要的存儲空間。

本發明的目的通過如下措施來達到：首先，將種子像素置成填充區域所要求的顏色(簡稱區域填充顏色)，并壓入棧結構；然后，當棧非空時重復執行如下兩個步驟：

(1)棧頂像素出棧；

(2)按左、上、右、下的順序檢查與出棧像素相鄰的四個像素，若其中某個像素未置成區域填充顏色且不屬于邊界像素，則將該像素置成區域填充顏色，并入棧。

（四）附圖說明

圖1為傳統的簡單種子填充算法流程圖。

圖2為本發明提出的經過改進后的種子填充算法流程圖。

圖3中的A、B、C、D為出棧像素根據四向連通算法確定的四個像素。

圖4中的白點為對大小為128×128像素的正方形區域進行填充之前確定的種子點。

圖5給出需要進行填充的區域輪廓，輪廓內部的白點表示選擇的種子點。

圖6給出圖5運行本發明算法后的結果。

（五）具體實施方式

下面結合附圖對本發明的技術方案作進一步的詳細描述。

本發明設計了一種解決簡單種子填充算法中存在的對某些像素進行多次出入棧操作問題的方法。經過該方法改進后的種子填充算法相比于未改進的簡單種子填充算法，無論在算法的執行效率還是實現棧結構所需要的存儲空間都有一定程度的優化。傳統的種子填充算法流程如圖1所示，本發明的算法流程如圖2所示，現以圖5給定的需要進行填充的區域為具體實例詳細說明具體實施步驟。

(1)對區域輪廓像素進行標志

該步驟的具體方法是，對圖像中的所有像素均設置一個標志值，例如對于像素(x,y)，其對應的標志值為Flag(x,y)，如像素(x,y)屬于區域輪廓，則令Flag(x,y)=1，否則令Flag(x,y)=0。

(2)確定種子點