基于膨脹和腐蝕的迭代優(yōu)化算法

蒲 石, 龍文光,2*

(1. 內(nèi)江師范學(xué)院 現(xiàn)代教育技術(shù)中心, 四川 內(nèi)江 641100; 2. 內(nèi)江師范學(xué)院 計算機(jī)科學(xué)學(xué)院, 四川 內(nèi)江 641100)

膨脹和腐蝕是數(shù)學(xué)形態(tài)學(xué)中最重要的2個基本操作,也是開、閉等其他操作的基礎(chǔ).當(dāng)圖像和結(jié)構(gòu)元素比較大時,膨脹和腐蝕操作是非常耗時的,其時間復(fù)雜度為O(n4).因此,如何優(yōu)化這2種運(yùn)算一直是研究的熱點(diǎn)問題[1-4].

根據(jù)公開的文獻(xiàn)資料,膨脹和腐蝕的優(yōu)化方法可以分為兩大類.第一類方法根據(jù)鏈?zhǔn)椒▌t將一個大的結(jié)構(gòu)元素分解成為一系列較小的結(jié)構(gòu)元素.許多學(xué)者提出了各自的優(yōu)化算法.X. Zhuang等[3]提出了一種樹形搜索算法,算法能將任意的結(jié)構(gòu)元素分解成只包含2個像素的結(jié)構(gòu)元素.X. Xu[4]提出的優(yōu)化算法能將凸結(jié)構(gòu)元素分解成3×3的結(jié)構(gòu).H. Park等[5]提出一種分解凸結(jié)構(gòu)元素的優(yōu)化算法,該算法可以快速的并發(fā)執(zhí)行.R. F. Hashimoto等[6]提出一種可分離的、對稱的凸結(jié)構(gòu)元素模版.X. Zhuang[7]等發(fā)展了一種組合的優(yōu)化技術(shù),實(shí)現(xiàn)了對結(jié)構(gòu)元素的連續(xù)分解.如果這種分解存在,該方法的性能可以達(dá)到或超過文獻(xiàn)[3-5]的性能.其他的一些作者[8-13]也提出了一些分解算法,但這些算法都局限于凸或其他形狀的結(jié)構(gòu)元素.文獻(xiàn)[11]提出一種能將任意形狀的結(jié)構(gòu)元素分解成3×3結(jié)構(gòu)的分解算法,但一般而言,并不是所有的結(jié)構(gòu)元素都有這樣的一系列分解[4,7,11].此外,文獻(xiàn)[10]的研究表明,通用的形態(tài)學(xué)模版分解問題是一個NP-complete問題.因此,結(jié)構(gòu)元素分解方法適合離線的應(yīng)用和小圖像問題.第二類方法將結(jié)構(gòu)元素看作一個整體而不進(jìn)行分解[14].和第一類方法相比,這類方法適合任何一種簡單連接的結(jié)構(gòu)元素和在線應(yīng)用[15-17].

本文提出一種基于第二類方法的改進(jìn)膨脹和腐蝕迭代優(yōu)化算法.通過定義結(jié)構(gòu)元素的邊界,一個簡單連接的結(jié)構(gòu)元素可以被看成由邊界和內(nèi)部點(diǎn)組成.在改進(jìn)的優(yōu)化算法中,膨脹和腐蝕操作被定義為一系列的迭代操作以降低算法時間復(fù)雜度.

1 基本概念

定義P∈Rv×w和S∈Rm×n分別是二值圖像和結(jié)構(gòu)元素,(x,y)表示一個像素.假設(shè)S的左上角像素為(0,0),那么可以定義以下概念.

定義1如果集合Sup滿足以下條件

Sup={(x,y)|(x,y)∈

S∩(x,y-1)?S},

(1)

那么Sup是S的上邊界.

定義2如果集合Slow滿足以下條件

Slow={(x,y)|(x,y)∈

S∩(x,y+1)?S},

(2)

那么Slow是S的下邊界.

定義3如果集合Sleft滿足以下條件

Sleft={(x,y)|(x,y)∈

S∩(x-1,y)?S},

(3)

那么Sleft是S的左邊界.

定義4如果集合Sright滿足以下條件

Sright={(x,y)|(x,y)∈

S∩(x+1,y)?S},

(4)

那么Sright是S的右邊界.

定義5如果集合Sinner滿足以下條件,

Sinner={(x,y)|(x,y)∈S∩((x,y)?

(Sup∪Slow)∪(x,y)?(Sleft∪Sright))},

(5)

那么Sinner是S的內(nèi)部點(diǎn).

以上定義中,定義5是由定義1和定義2,或定義3和定義4確定的.也就是說,定義5是一個相對概念,即使對于同一個S,由Sup和Slow確定的Sinner也可能和由Sleft和Sright確定的Sinner不同.

圖1給出了關(guān)于以上概念的一個例子.圖1(a)是一個任意形狀的結(jié)構(gòu)元素S,根據(jù)圖1(b)和(c)中分別定義的左、右邊界,用“⊙”標(biāo)記的點(diǎn)屬于Sinner.但是,根據(jù)圖1(d)和(e)中分別定義的上、下邊界,這個帶“⊙”標(biāo)記的點(diǎn)不屬于Sinner.圖1所示的例子說明Sinner是一個由邊界確定的相對概念.此外,圖1(d)和(e)還表明(x,y)可能同時屬于Sup和Slow,或同時屬于Sleft和Sright.

2 一種邊界檢測算法和時間復(fù)雜度

定義了邊界和內(nèi)部點(diǎn)的概念后,接下來的問題是如何檢測邊界.因?yàn)镾inner是一個相對概念,顯然,Sup和Slow,或Sleft和Sright應(yīng)該同時檢測.以檢測Sup和Slow為例,邊界檢測算法定義如下.

輸入：任意形狀的結(jié)構(gòu)元素S.

步驟1選擇S中一個未處理的列.

步驟2自上而下掃描當(dāng)前列,如果相鄰2個點(diǎn)的值發(fā)生了變化,例如(x,y-1)和(x,y),記錄下所有這樣的相鄰點(diǎn).

步驟3如果(x,y)的值為1,那么(x,y)∈Sup.

步驟4如果(x,y-1)的值為1,那么(x,y-1)∈Slow.

步驟5如果S中還有未處理的列,執(zhí)行步驟1.

步驟6結(jié)束.

輸出：Sup和Slow.

類似地,如果對S逐行進(jìn)行掃描,該算法可以同時檢測出Sleft和Sright.

3 一種改進(jìn)的膨脹和腐蝕優(yōu)化算法

3.1膨脹和腐蝕的定義和時間復(fù)雜度本質(zhì)上,膨脹和腐蝕是一種空域?yàn)V波,S對應(yīng)濾波器.對于(x,y),濾波器的輸出記為f(x,y),那么

(6)

其中

0≤x≤v-1, 0≤y≤w-1,

a=(m-1)/2,b=(n-1)/2,

S(x,y)和P(x,y)分別是S和P中的像素(x,y).如果P(x,y)按下列公式更新

(7)

其中

0≤x≤v-1, 0≤y≤w-1,

那么,(6)和(7)式定義的操作就是膨脹.如果P(x,y)按下列公式更新

(8)

其中

0≤x≤v-1, 0≤y≤w-1,

‖S‖是S中1的個數(shù).由(6)和(8)式定義的操作就是腐蝕.

從膨脹和腐蝕的定義可以看出,如果按照定義去計算膨脹和腐蝕操作(標(biāo)準(zhǔn)算法),算法的時間復(fù)雜度為O(v×w×m×n).

3.2一種改進(jìn)的膨脹和腐蝕優(yōu)化算法及時間復(fù)雜度如果P和S比較大的話,在(6)式中需要對P和S逐個像素地進(jìn)行計算,因此膨脹和腐蝕是非常耗時的操作.同時,通過前面的分析可以看出,(6)式中有些像素的計算是沒有必要的.如圖2所示,如果S從左向右水平方向移動,t時刻和t+1時刻濾波器的輸出分別為f(x,y)和f(x+1,y).假設(shè)Pleft(t)是t時刻P中和Sleft重疊的像素.類似地,可以定義Pright(t)、Pup(t)、Plow(t).從圖2可以得到

f(x+1,y)=f(x,y)+

‖Pright(t+1)‖-‖Pleft(t)‖.

(9)

相反,如果S從右向左水平方向移動,t時刻和t+1時刻濾波器的輸出分別為f(x,y)和f(x-1,y).類似地可以得到

f(x-1,y)=f(x,y)+

‖Pleft(t+1)‖-‖Pright(t)‖.

(10)

最后,如果S從上自下垂直方向移動,t時刻和t+1時刻濾波器的輸出分別為f(x,y)和f(x,y+1),那么可以得

f(x,y+1)=f(x,y)+

‖Plow(t+1)‖-‖Pup(t)‖.

(11)

圖2中S從左向右水平方向移動,Pleft、Pleft(t+1)、Pright和Pright(t+1)的變化情況.陰影區(qū)域表示t時刻和S重疊的P(x,y).顯然,在t時刻,Pleft、Pleft(t+1)和Pright(t)位于陰影區(qū)域；在t+1時刻,Pleft(t+1)、Pright(t)和Pright(t+1)位于陰影區(qū)域.也就是說,從t時刻到t+1時刻,Pleft移出了陰影區(qū)域而Pright(t+1)移進(jìn)了陰影區(qū)域.

(9)～(11)式意味著如果S連續(xù)地在P上逐個像素的移動,膨脹和腐蝕可以被定義為迭代操作.進(jìn)一步,如果S在P上的移動路徑如圖3所示,根據(jù)S的移動方向,(9)～(11)式中始終有且僅有一個等式適合當(dāng)前的迭代計算,除f(0,0)的計算例外.事實(shí)上,f(0,0)的初始化計算可以按照(6)式進(jìn)行.顯然,因?yàn)橹挥幸粋€像素需要這樣計算,所以f(0,0)的初始化并不會提高膨脹和腐蝕優(yōu)化算法的時間復(fù)雜度.

膨脹和腐蝕的優(yōu)化算法完整地描述如下：

輸入：S和P.

步驟1調(diào)用邊界檢測算法,檢測得到Sup、Slow、Sleft和Sright.

步驟2根據(jù)(6)式計算f(0,0).

步驟3如果P(x,y)處理完成,跳轉(zhuǎn)到步驟9.

步驟4如果S從左向右水平方向移動,根據(jù)(9)式計算f(x,y).

步驟5如果S從右向左水平方向移動,根據(jù)(10)式計算f(x,y).

步驟6如果S從上向下垂直方向移動,根據(jù)(11)式計算f(x,y).

步驟7根據(jù)(7)或(8)式更新P(x,y).

步驟8跳轉(zhuǎn)到步驟3.

步驟9結(jié)束.

輸出：P.

在上述優(yōu)化算法中,步驟3對應(yīng)一個二重循環(huán),時間復(fù)雜度為O(v×w)；因?yàn)椴襟E4～6中可以直接調(diào)用邊界檢測算法的結(jié)果,所以時間復(fù)雜度為O(m)或O(n).整體而言,膨脹和腐蝕優(yōu)化算法對應(yīng)一個三重循環(huán),時間復(fù)雜度不會超過O(n3),n=max{v,w,m,n}.

4 實(shí)驗(yàn)和結(jié)果

在實(shí)驗(yàn)中,P和S采用隨機(jī)方式初始化為二值矩陣.同時,為了簡化實(shí)驗(yàn)參數(shù)的設(shè)置,不失一般性,重新定義P∈Rv×w和S∈Rm×n.通過記錄算法在不同參數(shù)條件下運(yùn)行所需要的時鐘脈沖數(shù),優(yōu)化算法和標(biāo)準(zhǔn)算法、Yang算法[14]進(jìn)行對比.在實(shí)驗(yàn)中,采用的硬件平臺為：CPU為酷睿i3,主頻2.4 GHz,16 G DDR2 RAM,工作頻率1 200 MHz.算法采用Visual Studio 2008編碼實(shí)現(xiàn).3種算法都采用C語言實(shí)現(xiàn),同時,在C語言中,1 s包含了1 000個脈沖,因此實(shí)驗(yàn)結(jié)果精度為0.001 s.

3種算法的對比結(jié)果如圖4和圖5所示.圖4顯示w對算法執(zhí)行時間的影響.根據(jù)(6)式,對標(biāo)準(zhǔn)的膨脹和腐蝕算法而言,算法執(zhí)行時間和w應(yīng)該是二次函數(shù)關(guān)系,圖4(a)證實(shí)了這一結(jié)論.類似地,根據(jù)圖4(b)和圖4(c),這一結(jié)論同樣適合Yang算法和迭代優(yōu)化算法.此外,從圖4中還可以看出,當(dāng)m取不同值時,優(yōu)化算法的曲線最靠近,標(biāo)準(zhǔn)算法的曲線最分散,Yang算法的結(jié)果介于兩者之間.這種現(xiàn)象說明在優(yōu)化算法中,參數(shù)m對算法執(zhí)行時間的影響最小.

5 小結(jié)

本文對數(shù)學(xué)形態(tài)學(xué)中的膨脹和腐蝕操作進(jìn)行了研究.膨脹和腐蝕是數(shù)學(xué)形態(tài)學(xué)中最基礎(chǔ)的2個操作,如果按照膨脹和腐蝕的定義去操作,算法的時間復(fù)雜度為O(n4).在本文中,通過定義結(jié)構(gòu)元素的邊界和內(nèi)部點(diǎn),膨脹和腐蝕操作被定義為一系列迭代計算.在此基礎(chǔ)上,提出一種膨脹和腐蝕的迭代優(yōu)化算法.該算法能利用上一次計算的結(jié)果,僅需要對邊界進(jìn)行重新計算.算法分析和實(shí)驗(yàn)結(jié)果都表明,迭代優(yōu)化算法的時間復(fù)雜度為O(n3).實(shí)驗(yàn)結(jié)果同時還表明,當(dāng)w≥300時,迭代優(yōu)化算法的性能優(yōu)于Yang算法的性能.

[1] Pitas I, Venetsanpoulos A N. Morphological shape decomposition[J]. IEEE Trans Pattern Anal Machine Intell,1990,12(1):38-45.

[2] Haralick R M, Stemberg S R, Zhuang X. Image analysis using mathematical morphology[J]. IEEE Trans Pattern Anal Machine Intell,1987,9(4):532-550.

[3] Zhuang X, Haralick R M. Morphological structuring element decomposition[J]. Comput Vision,Graphics,Image Processing,1986,35(9):370-382.

[4] Xu X. Decomposition of convex polygonal morphological structuring elements into neighborhood subsets[J]. IEEE Trans Pattern Anal Machine Intell,1991,13(2):153-162.

[5] Park H, Chin R T. Optimal decomposition of convex morphological structuring elements for 4-connected parallel array processors[J]. IEEE Trans Pattern Anal Machine Intell,1994,16(3):304-313.

[6] Hashimoto R F, Barrera J, Ferreira C E. A combinatorial optimization technique for the sequential decomposition of erosions and dilations[J]. J Math Imaging Vision,2000,13(1):17-33.

[7] Zhuang X. Decomposition of morphological structuring elements[J]. J Math Imaging Vision,1994,4(1):5-18.

[8] Pardalos P M, Sussner P, Ritter G X. On integer programming approaches for morphological template decomposition problems in computer vision[J]. J Combinatorial Optimization,1997,1(2):165-178.

[9] Park H, Chin R T. Decomposition of arbitrarily shaped morphological structuring elements[J]. IEEE Trans Pattern Anal Machine Intell,1995,17(1):2-15.

[10] 楊琨,曾立波,王殿成. 數(shù)學(xué)形態(tài)學(xué)腐蝕膨脹運(yùn)算的快速算法[J]. 計算機(jī)工程與應(yīng)用,2005,41(34):54-56.

[11] Anelli G, Broggi A, Destri G. Decomposition of arbitrarily shaped binary morphological structruing elements using genetic algorithm[J]. IEEE Trans Pattern Anal Machine Intell,1998,20(2):217-224.

[12] Hashimoto R F, Barrera J. A note on Park and Chin’s algorithm[J]. IEEE Trans Pattern Anal Machine Intell,2002,24(1):139-144.

[13] 景小平,鄧方源,易世君,等. 基于形態(tài)小波變換的指紋圖像識別預(yù)處理的應(yīng)用研究[J]. 四川師范大學(xué)學(xué)報:自然科學(xué)版,2009,32(5):694-697.

[14] 林江莉,汪天富,彭玉蘭,等. 乳腺腫瘤超聲圖像形態(tài)特征選擇[J]. 四川師范大學(xué)學(xué)報:自然科學(xué)版,2005,28(5):615-618.

[15] 王賢秋,李詠紅,陳順玲. 基于形狀和結(jié)構(gòu)特征的白酒識別方法研究[J]. 四川師范大學(xué)學(xué)報:自然科學(xué)版,2011,34(4):593-596.

[16] 王大海,靳冰,賈玉珍. 基于雙結(jié)構(gòu)元素的數(shù)學(xué)形態(tài)學(xué)邊緣檢測方法[J]. 西華大學(xué)學(xué)報:自然科學(xué)版,2010,29(5):42-44.

[17] 高國明,黃漢明,李莉. 一種分形和形態(tài)學(xué)結(jié)合的圖像邊緣檢測算法[J]. 廣西師范大學(xué)大學(xué)學(xué)報:自然科學(xué)版,2012,30(3):50-54.