基于雙堆棧的區(qū)域標記算法

陳　沖，管庶安

(武漢輕工大學 數(shù)學與計算機學院，湖北 武漢 430023 )

?

基于雙堆棧的區(qū)域標記算法

陳沖，管庶安

(武漢輕工大學 數(shù)學與計算機學院，湖北 武漢 430023 )

摘要：二值圖像的區(qū)域標記是圖像分析中的基本操作。提出了一種基于雙堆棧的二值圖像區(qū)域標記算法，并且在理論與實驗結果上與傳統(tǒng)的單堆棧算法和遞歸算法進行了對比，發(fā)現(xiàn)雙堆棧算法在空間復雜度和時間復雜度方面都得到了極大的改進。

關鍵詞：二值圖像；區(qū)域標記；雙堆棧；空間復雜度

1引言

區(qū)域標記是二值圖像分析中的最基本操作之一，由于圖像數(shù)據(jù)量很大，因此要盡可能降低算法復雜度，以便用于實時處理場合。目前常用的算法有：(1)基于遞歸的二值圖像連通域像素標記算法[1-2]，該算法的優(yōu)點是源程序直觀簡捷，但空間復雜度較高。(2)優(yōu)化路徑的種子填充算法[3],該算法基于單一堆棧存儲周轉像素，并盡可能減少入棧種子點的數(shù)量，提高了程序效率，但算法的控制結構較復雜，堆棧空間的減少量有限。此外，國內對區(qū)域標記算法研究還有游程編碼方法[4-6]，線的區(qū)域標記算法[7]，順序法[7]，R C L 算法[8],二值連通圖像快速算法[9],基于鏈表的二值圖像標記算法[10]等，這些算法都是基于現(xiàn)有算法改進的，對復雜度問題的改進不顯著，筆者在現(xiàn)有算法的基礎上提出了一種雙堆棧的區(qū)域標記算法。

2常用的連通區(qū)域標記算法

2.1遞歸的區(qū)域標記算法

不失一般性，設二值圖像中的像素標記連通區(qū)為n×n像素矩形尺寸為n×n像素，考慮到標記標記量很大的情況，設連通區(qū)域中的像素在標記前各像素的標記值為1，標記后為M(M≠0,1),遞歸函數(shù)的結構如下：

Mark_1(p0)

{將p0點的像素標記為M；

for(p0的4鄰域點pi，i=1,2,3,4)

{if (pi為標記的點) 則用pi作實參調用Mark_1(pi)；

}

}

圖1為p0的4-鄰域。

圖1　p0的4-鄰域

該算法的空間復雜度分析：每當函數(shù)遞進調用一次，就要新建一對形參變量(x0,y0)；當返回一次，才會釋放本次建立的變量。在調用中，當p0的4鄰域不存在未標記的點時，函數(shù)將返回，否則，函數(shù)繼續(xù)向前遞進，圖2表示一個7×7連通區(qū)的標記過程，設左上角的點最先標記，一旦標記開始，將一直調用向前遞進，直到所有點標記完畢后，才開始從圖2右下角處，沿圖中的箭頭相反的路徑返回到終點。

圖2　遞歸算法下的7×7連通區(qū)標記過程

由以上分析可知，遞歸算法的空間復雜度，主要為每次遞進調用時新增加形參變量空間總量以及每次調用函數(shù)時系統(tǒng)保留CPU運行現(xiàn)場需要的堆棧空間。其復雜度可記為OR(n2)。

該算法時間復雜度：利用系統(tǒng)的一個硬件計數(shù)器可測量算法的時間開銷，調用前后，獲得該計數(shù)器的計數(shù)值T1和T2，則運行時間=T2-T1)/FS，其中FS為系統(tǒng)計數(shù)器的時鐘頻率，可由QueryPerformancecounter() 函數(shù)得到。

2.2單堆棧的區(qū)域標記算法

該算法采用一個堆棧來存儲標記過程中搜索到待標記點，設S為一個堆棧，p0為待標記區(qū)域的起點，算法如下：

對p0進行標記，并將其壓入S;

do{

for(p0點的4-鄰域點pi，i=1,2,3,4)

{if(pi為待標記點){對pi進行標記，并將pi壓入S；}

}

從S中彈出一點，作為p0；

}while(S非空);

圖3　單堆棧算法下的操作過程

該算法時間復雜度分析：由于該算法不需要保護現(xiàn)場和恢復現(xiàn)場，所以時間復雜度比遞歸時間復雜度稍小，也可以采用測量遞歸時間復雜度的方法測出。

3雙堆棧的區(qū)域標記算法

雙堆棧算法采用了兩個堆棧，其中一個進行彈出，另一個進行壓入，彈出時搜索彈出點的4-鄰域沒有標記的點，一一壓入另一個堆棧，彈出?？蘸?，交換兩堆棧。算法如下：

首先建立兩個堆棧S1,S2，分別用于壓入和彈出點。設p0為種子點

①將p0其壓入S1，并將其標記為M,并將其壓入S1，置S2為空；

② 交換 S1和 S2;

③ 從S2中逐一彈出壓入的點。每彈出一點，立即搜索該點4鄰域未標記的點，并將其標記改為M，并將其壓入S1;

④ 在③中，若沒有壓入任何點，則結束連通區(qū)搜索；否則，轉到②。

圖4是運用雙堆棧算法對一個7×7矩形連通區(qū)進行標記的過程，其中空心點和實心點分別對應壓入S1和S2中的像素。箭頭總是指向下一個彈出的點。顯然，當箭頭開始指向斜對向線的端點時，S1達到最大深度，而S2可達到最大深度為6。一般地，當對于n×n 矩形連通區(qū)，兩個堆棧的最大堆棧深度之和為2n-1。其空間復雜度為O2s(n)。

該算法時間復雜度分析：可以采用遞歸時間復雜度方法測出。

圖4　雙堆棧算法下的標記過程

4三種算法實驗結果

為了驗證以上分析，特對一個二值圖像中的尺寸為620×460的連通區(qū)域記性標記。并且采用VC++ 2010進行仿真，計算機配置為：Intel Celeron CPU 2.6 GHz，內存4 GB；64位win10 操作系統(tǒng)。所測得的數(shù)據(jù)如表1所示，表1中，時間消耗是利用系統(tǒng)的一個硬件計數(shù)器測量的，取10次測量數(shù)據(jù)的平均值為所需要的數(shù)據(jù)。表1中所需內存由編程時設置系統(tǒng)堆棧大小實現(xiàn)。

表1三標記種算法的時間以及占用的存儲空間

算法時間消耗/ms所需內存/M字節(jié)遞歸11.442100單堆棧2.24011.09雙堆棧3.0740.007

由表1可以看出雙堆棧算法占用的空間比單堆棧算法占用的空間小102多倍，比遞歸算法空間小104多倍，所耗用的時間和單堆棧算法差不多，但比遞歸時間小的多。通過實驗結果，驗證了理論理論分析的結論，證明雙堆棧算法在空間復雜度上遠優(yōu)于單堆棧算法和遞歸算法，在時間復雜度上和單堆棧算法差不多，但比遞歸算法消耗時間少的多。

5結束語

區(qū)域標記在圖像分析與識別中是一種必不可少的操作。筆者提出的雙堆棧標記算法，與現(xiàn)有遞歸算法和單堆棧算法對比，在時間復雜度與空間復雜度上有了很大的改進。在基于視覺測量的工業(yè)產品品質在線實時檢測中有較高的應用價值。

參考文獻:

[1]徐正光,鮑東來,張利欣,等.基于遞歸的二值圖像連通域像素標記算法[J].計算機工程,2006,32(24):186-188.

[2]喻杰,許化溪,WANG Sheng-jun,等.一種易于實現(xiàn)的適于細胞圖像連通區(qū)域的標記算法[J].江蘇大學學報(醫(yī)學版),2005,15(2):152-153.

[3]孫遠志,孫衛(wèi)紅.優(yōu)化路徑的種子填充算法[J].東華大學學報(自然科學版),2007,33(3):378-381.

[4]劉奇琦,龔曉峰.一種二值圖像連通區(qū)域標記的新方法[J].計算機工程與應用,2012,48(11):178-180.

[5]沈喬楠,安雪暉.基于游程遞歸的連通區(qū)域標記算法[J].計算機應用,2010,30(6):1616-1618.

[6]徐利華,陳早生.二值圖像中的游程編碼區(qū)域標記[J].光電工程,2004,31(6):63-65.

[7]曹長虎,李亞非.一種二值圖像連通區(qū)域標記快速算法[J].科學技術與工程,2010,10(33):8168-8171.

[8]張云哲,趙海,宋純賀,等.一種新的連通區(qū)域標記算法[J].計算機應用研究,2010,27(11):4335-4337.

[9]高紅波,王衛(wèi)星.一種二值圖像連通區(qū)域標記的新算法[J].計算機應用,2007,27(11):2776-2777.

[10]馮海文,牛連強,劉曉明,等.高效的一遍掃描式連通區(qū)域標記算法[J].計算機工程與應用,2014(23):31-35.

Region marking algorithm based on double stack

CHENChong,GUANshu-an

(School of Mathematics and Computer Science，Wuhan Polytechnic University，Wuhan 430023， China)

Abstract：Binary image region marking is a basic operation in image analysis. The paper presents a binary image region marking dual-stack algorithm, and the results are compared with the traditional single stack algorithm and recursive algorithm ,it is found that the dual- stack algorithm has been improved greatly in space complexity and time complexity.

Key words：binary image ;region marking;dual-stack ;space complexity

中圖分類號：TP 391.413

文獻標識碼：A

DOI:10.3969/j.issn.2095-7386.2016.01.020

文章編號：2095-7386(2016)01-0092-03

作者簡介：陳沖(1990-),男,碩士研究生,E-mail:546606432@qq.com.通信作者：管庶安(1956-)，男,教授, E-mail:jsj-g@163.com.

收稿日期：2015-11-02.修回日期:2015-12-24.