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

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

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

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

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

周期線；模糊二值形態(tài)學；開運算；路徑

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

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

1 基本概念

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

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

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

2)開算子 結(jié)構(gòu)元S對圖像集合A作開運算記為A°S或γS(A),即:

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

1.2模糊二值開運算

圖3 不同的周期線實例

1.3周期線

周期線[5]pm,v的定義如下:

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

2 算法步驟

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

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

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

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

Step4 用2個像素的周期線對A1進行模糊二值形態(tài)學開運算,得到：

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

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

3 算法試驗

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

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

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

圖5 地圖M的2點路徑搜索

[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].計算機工程與應用, 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ù)學應用方法與圖像處理方面的研究工作。