基于周期線(xiàn)的模糊二值形態(tài)開(kāi)路徑算法

申雪利,張成斌 (中南民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430074)

基于周期線(xiàn)的模糊二值形態(tài)開(kāi)路徑算法

申雪利,張成斌 (中南民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430074)

數(shù)學(xué)形態(tài)學(xué)作為一門(mén)新的自動(dòng)搜索圖形中2點(diǎn)之間的最短路徑技術(shù)引起了廣泛的關(guān)注。傳統(tǒng)形態(tài)學(xué)路徑算法由于結(jié)構(gòu)元方向的不變性,并不能獲取圖形中2點(diǎn)之間的最短路徑。針對(duì)路徑的方向變化特征,提出了利用不同方向的周期線(xiàn)結(jié)構(gòu)元的模糊二值形態(tài)開(kāi)路徑算法,該算法不僅可獲取圖形中2點(diǎn)間的最短路徑,省略了Lin算法中的距離變換復(fù)雜過(guò)程,而且該算法簡(jiǎn)單、易操作。

周期線(xiàn)；模糊二值形態(tài)學(xué)；開(kāi)運(yùn)算；路徑

圖1 文獻(xiàn)[3]算法得到的s點(diǎn)到e點(diǎn)的最短路徑 圖2 改變結(jié)構(gòu)元方向得到的s點(diǎn)到e點(diǎn)的最短路徑

數(shù)學(xué)形態(tài)學(xué)采用以結(jié)構(gòu)元與圖像的結(jié)構(gòu)匹配程度來(lái)獲取圖像的結(jié)構(gòu)信息,在圖像處理和分析中,得到了很好的結(jié)果。近年來(lái),數(shù)學(xué)形態(tài)學(xué)[1-2]作為一種新的路徑搜索技術(shù)引起了很多學(xué)者的關(guān)注,在文獻(xiàn)[3]中Lin提出了采用形態(tài)學(xué)變換來(lái)獲取圖形中2點(diǎn)間的路徑[4]算法,而該算法根據(jù)傳統(tǒng)的數(shù)學(xué)形態(tài)學(xué)變換,獲取的路徑并不是最短的,如圖1所示。在C處,如果改變結(jié)構(gòu)元的方向,便可通過(guò),獲取s點(diǎn)到e點(diǎn)更短的2點(diǎn)路徑，如圖2所示。針對(duì)文獻(xiàn)[3]中的形態(tài)學(xué)路徑最短問(wèn)題,根據(jù)路徑的方向變化特征以及周期線(xiàn)結(jié)構(gòu)元的定義,筆者利用不同方向的連通周期線(xiàn)結(jié)構(gòu)元的形態(tài)開(kāi)運(yùn)算結(jié)果取并集,獲取圖形中的2點(diǎn)間的最短路徑。

1 基本概念

1.1數(shù)學(xué)形態(tài)學(xué)的基本算子

1)腐蝕與膨脹算子 結(jié)構(gòu)元S對(duì)圖像集合A進(jìn)行腐蝕記為AΘS:

結(jié)構(gòu)元S對(duì)圖像集合A進(jìn)行膨脹記為A⊕S:

2)開(kāi)算子 結(jié)構(gòu)元S對(duì)圖像集合A作開(kāi)運(yùn)算記為A°S或γS(A),即:

A°S=γS(A)=(AΘS)⊕S

1.2模糊二值開(kāi)運(yùn)算

圖3 不同的周期線(xiàn)實(shí)例

1.3周期線(xiàn)

周期線(xiàn)[5]pm,v的定義如下:

式中，m為周期線(xiàn)上的像素點(diǎn)的數(shù)目；v表示常數(shù)矢量,矢量v=(a,b),其中a∈Z,b∈Z；周期T=max(|a|,|b|),如圖3所示,顯示不同的周期線(xiàn)結(jié)構(gòu)元,其中黑色為周期線(xiàn)的原點(diǎn)。

2 算法步驟

基于周期線(xiàn)結(jié)構(gòu)元的模糊二值形態(tài)學(xué)開(kāi)運(yùn)算最短路徑算法步驟如下:

Step1 把地圖M中障礙物的灰度值設(shè)定為1,空白(可通行)區(qū)域的灰度值為0,把含有障礙物的地圖轉(zhuǎn)化為二值圖像A。

Step3HN={x|x∈{γpNm(A)∩γpNk(A),m,k*≤M且m≠k}}

式中，pNm、pNk表示不同方向的N個(gè)像素的連通周期線(xiàn)結(jié)構(gòu)元。

Step4 用2個(gè)像素的周期線(xiàn)對(duì)A1進(jìn)行模糊二值形態(tài)學(xué)開(kāi)運(yùn)算,得到：

式中，p2m、p2k分別表示為垂直和水平方向的連通周期線(xiàn)。

Step5H=HN∪H2, 在H中搜索始點(diǎn)s點(diǎn)到終點(diǎn)e點(diǎn)的像素?cái)?shù)總和最小的連通折線(xiàn)段l便是2點(diǎn)之間的最短路徑,否則s點(diǎn)到終點(diǎn)e點(diǎn)之間不存在路徑;算法結(jié)束。

3 算法試驗(yàn)

利用上述的算法對(duì)圖4(a)中的二值圖像A搜索始點(diǎn)s點(diǎn)到終點(diǎn)e點(diǎn)的路徑, 從圖4的結(jié)果(d)中可獲得(a)中s點(diǎn)到e點(diǎn)的可通行區(qū)域H,并在可通行區(qū)域中,從起點(diǎn)到終點(diǎn)的像素?cái)?shù)最少的連通路徑便是該算法得到的最短路徑。

圖4 基于周期線(xiàn)的模糊二值形態(tài)開(kāi)路徑算法實(shí)現(xiàn)

采用上述的基于周期線(xiàn)的模糊二值形態(tài)開(kāi)路徑算法與Lin算法,分別對(duì)圖5(a)、(b)和(c)中不同的s點(diǎn)到e點(diǎn)的路徑進(jìn)行搜索。由圖5(d)、(e)和(f)分別與圖5(g)、(h)和(i)進(jìn)行比較,可得出采用旋轉(zhuǎn)結(jié)構(gòu)元的形態(tài)開(kāi)運(yùn)算獲取的路徑較短,而且基于周期線(xiàn)的模糊形態(tài)開(kāi)運(yùn)算的算法簡(jiǎn)單,只要采用結(jié)構(gòu)元的不同方向?qū)D進(jìn)行開(kāi)運(yùn)算,并對(duì)不同方向結(jié)構(gòu)元的形態(tài)開(kāi)運(yùn)算結(jié)果取并集以及增加2個(gè)像素的周期線(xiàn)進(jìn)行模糊開(kāi)運(yùn)算取并集結(jié)果,得到了1條連通的實(shí)用路徑，省去了采用Lin算法中的距離變換的復(fù)雜過(guò)程。

圖5 地圖M的2點(diǎn)路徑搜索

[1]Serra J. Image Analysis and Mathematical Morphology[M]. New York：Academic Press, 1982:30-50.

[2] Serra J. Image Analysis and Mathematical Morphology: Theoretical Advances [M]. New York：Academic Press, 1988:15-45.

[3] Lin P L,Chang S. A shortest path algorithm for a nonrotating object among obstacles of arbitrary shapes[J],IEEE Trans Systems, Man and Cybernetics, 1993,23(8):825-833.

[4] 宣士斌.基于分流算法的最短路徑求解算法[J].計(jì)算機(jī)工程與應(yīng)用, 2004 (20):74-76.

[5] Jones R, Soille P.Periodic lines and their application to granulometries[A]. Maragos P, Schafer W, Butt M.Mathematical Morphology and its Application to Image and Signal Processing[C]. Kluwer Academic Publishers,1996:264-272

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.07.026

TP391.41

A

1673-1409(2011)07-0073-03

2011-05-27

申雪利，女，碩士生，現(xiàn)主要從事數(shù)學(xué)應(yīng)用方法與圖像處理方面的研究工作。