基于膨脹和腐蝕的迭代優化算法

蒲 石, 龍文光,2*

(1. 內江師范學院 現代教育技術中心, 四川 內江 641100; 2. 內江師范學院 計算機科學學院, 四川 內江 641100)

膨脹和腐蝕是數學形態學中最重要的2個基本操作,也是開、閉等其他操作的基礎.當圖像和結構元素比較大時,膨脹和腐蝕操作是非常耗時的,其時間復雜度為O(n4).因此,如何優化這2種運算一直是研究的熱點問題[1-4].

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

本文提出一種基于第二類方法的改進膨脹和腐蝕迭代優化算法.通過定義結構元素的邊界,一個簡單連接的結構元素可以被看成由邊界和內部點組成.在改進的優化算法中,膨脹和腐蝕操作被定義為一系列的迭代操作以降低算法時間復雜度.

1 基本概念

定義P∈Rv×w和S∈Rm×n分別是二值圖像和結構元素,(x,y)表示一個像素.假設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的內部點.

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

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

2 一種邊界檢測算法和時間復雜度

定義了邊界和內部點的概念后,接下來的問題是如何檢測邊界.因為Sinner是一個相對概念,顯然,Sup和Slow,或Sleft和Sright應該同時檢測.以檢測Sup和Slow為例,邊界檢測算法定義如下.

輸入：任意形狀的結構元素S.

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

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

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

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

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

步驟6結束.

輸出：Sup和Slow.

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

3 一種改進的膨脹和腐蝕優化算法

3.1膨脹和腐蝕的定義和時間復雜度本質上,膨脹和腐蝕是一種空域濾波,S對應濾波器.對于(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的個數.由(6)和(8)式定義的操作就是腐蝕.

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

3.2一種改進的膨脹和腐蝕優化算法及時間復雜度如果P和S比較大的話,在(6)式中需要對P和S逐個像素地進行計算,因此膨脹和腐蝕是非常耗時的操作.同時,通過前面的分析可以看出,(6)式中有些像素的計算是沒有必要的.如圖2所示,如果S從左向右水平方向移動,t時刻和t+1時刻濾波器的輸出分別為f(x,y)和f(x+1,y).假設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)的變化情況.陰影區域表示t時刻和S重疊的P(x,y).顯然,在t時刻,Pleft、Pleft(t+1)和Pright(t)位于陰影區域；在t+1時刻,Pleft(t+1)、Pright(t)和Pright(t+1)位于陰影區域.也就是說,從t時刻到t+1時刻,Pleft移出了陰影區域而Pright(t+1)移進了陰影區域.

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

膨脹和腐蝕的優化算法完整地描述如下：

輸入：S和P.

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

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

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

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

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

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

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

步驟8跳轉到步驟3.

步驟9結束.

輸出：P.

在上述優化算法中,步驟3對應一個二重循環,時間復雜度為O(v×w)；因為步驟4～6中可以直接調用邊界檢測算法的結果,所以時間復雜度為O(m)或O(n).整體而言,膨脹和腐蝕優化算法對應一個三重循環,時間復雜度不會超過O(n3),n=max{v,w,m,n}.

4 實驗和結果

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

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

5 小結

本文對數學形態學中的膨脹和腐蝕操作進行了研究.膨脹和腐蝕是數學形態學中最基礎的2個操作,如果按照膨脹和腐蝕的定義去操作,算法的時間復雜度為O(n4).在本文中,通過定義結構元素的邊界和內部點,膨脹和腐蝕操作被定義為一系列迭代計算.在此基礎上,提出一種膨脹和腐蝕的迭代優化算法.該算法能利用上一次計算的結果,僅需要對邊界進行重新計算.算法分析和實驗結果都表明,迭代優化算法的時間復雜度為O(n3).實驗結果同時還表明,當w≥300時,迭代優化算法的性能優于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] 楊琨,曾立波,王殿成. 數學形態學腐蝕膨脹運算的快速算法[J]. 計算機工程與應用,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] 景小平,鄧方源,易世君,等. 基于形態小波變換的指紋圖像識別預處理的應用研究[J]. 四川師范大學學報:自然科學版,2009,32(5):694-697.

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

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

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

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