王 會，余 陽

(1.成都東軟學院 計算機科學與技術(shù)學院，四川 成都 611844； 2.成都東軟學院 電子商務與信息管理系，四川 成都 611844)

0 引 言

傳統(tǒng)的邊界檢測[1.2]方法多基于微分技術(shù)，如基于一階導數(shù)的Roberts算子、sobel算子、Prewitt算子、基于二階導數(shù)的Laplacian算子[3]。這些方法對噪聲敏感，檢測精度不高。然而，實際圖像的信噪比(signal noise ratio，SNR)并不高，如生物醫(yī)學圖像、遙感衛(wèi)星圖像、水下生物圖像等[4]。因此，對低SNR圖像進行準確地邊緣檢測一直是研究熱點。

為了提高傳統(tǒng)梯度算子的邊緣檢測性能，Duan等[5]提出了改進的canny算子，先對圖像進行高斯平滑，再由一階導數(shù)的極大值確定邊緣點，但canny算子會引入偽邊緣點?；诟咚篂V波的二維拉普拉斯(Laplacian of Gaussian，LOG)[6,7]零交叉邊緣檢測方法應用廣泛，該局部探測方法效率很高。然而，在低SNR情況下檢測效果較差。為了消除噪聲對邊緣檢測的影響，首先需要圖像去噪，然后邊緣檢測。去噪方法包括雙向濾波[8]、各向異性擴散[9]、非局部均值[10]等。然而，這些方法并非為邊界探測專門定制，從而使邊緣模糊，微弱的邊界檢測更加困難。

近些年根據(jù)自然圖像的特點，提出基于多特征和模糊推理的邊緣檢測方法[11,12]。這類方法雖在一定程度上提高了自然圖像的邊緣檢測準確性，但比較復雜，且對微弱邊界檢測性能有限。根據(jù)噪聲與邊緣均為高頻信息的特性，基于多尺度方法得到應用，最常見的有小波變換[13]。由于小波變換的非奇異性，其不能夠適應真實彎曲邊界的形狀。也有使用匹配濾波器來提高微弱邊界的檢測性能的，如Tsantis等[14]利用改進的模糊c均值實現(xiàn)超聲圖像的斑點噪聲圖像的檢測；Wang等[15]利用光束曲線金字塔(beam curve pyramid，BCP)數(shù)據(jù)結(jié)構(gòu)和次線性算法檢測低信噪比邊緣。雖然這些方法實現(xiàn)多尺度匹配，但時間復雜度較高，應用困難。

針對傳統(tǒng)方法對微弱邊界檢測性能較低、時間復雜度較高的問題，本文基于人類視覺系統(tǒng)的特性，利用匹配濾波器探測微弱彎曲邊界，但僅保留那些在統(tǒng)計學上很重要的彎曲邊界。其主要工作包括：①設計多尺度匹配濾波器檢測長邊緣的微弱邊界，提高檢測準確性；②采用多線程和自下而上的搜索策略，提高邊緣檢測速度。

1 本文算法

本文的核心是通過曲線二叉樹的方法構(gòu)建多尺度匹配濾波器。

1.1 基本結(jié)構(gòu)

為了方便闡述本文算法的理論，假設無噪圖像I高度與寬度相等，邊界為一條非交叉曲線λ，圖像像素灰度值表現(xiàn)為階躍不連續(xù)。對于總長度L，通過一系列像素集合P的每條候選曲線λ，其響應向量為

Φ(λ)=[R,L,C,P]

(1)

式中：R為響應值，由曲線λ相對應的匹配濾波器所決定，表示該曲線兩邊像素和之間的差異性；C=R/m(L)，表示沿著曲線方向的平均對比度，其中m(L)為長度L的匹配濾波器包含的像素總數(shù)。令λ1和λ2為兩條具有公共端點的曲線，其相對應的響應向量為Φ(λi)=[Ri,Li,Ci,Pi],i=1,2，則其連接的響應向量為

(2)

圖1 曲線二叉樹

在每個分塊V中，對于在其邊界?V上的每一對像素p1和p2，曲線二叉樹數(shù)據(jù)結(jié)構(gòu)CBT存儲其相應的響應向量Φ(λ)，每一個響應向量確定p1和p2之間的一個單曲線λ，其很可能為一條邊界。之后根據(jù)檢測閾值，分配邊界得分，確定邊界曲線。

本文的分塊基本原則是：子分塊近似等于原分塊區(qū)域的一半，分割邊界的長度近似等于其面積的平方根。

1.2 邊界檢測算法

算法1給出CBT的構(gòu)建偽碼，其中注意分塊V的最大邊長為n。算法1中，各種曲線的匹配濾波響應是自下而上的方式計算得到，即從樹葉到樹根。如果n

然后，根據(jù)j+1層的響應向量，計算下一個粗糙層(第j層)的響應。本文通過連接兄弟分塊實現(xiàn)該過程，具體如下所述。令分塊V1和V2為第j+1層的兄弟分塊，V為第j層的母分塊，所有像素對遵循p1∈?V1∩?V，p2∈?V2∩?V。則對于每對像素(p1,p2)，所有像素均在連接線V12=?V1∩?V2中。對于每個像素p3∈V12，通過連接p1到p3、p3到p2的兩條曲線，計算其曲線響應向量。在所有這些連接曲線中，存儲得分最高的那條曲線。該粗糙處理過程的偽碼如算法3所示。

算法1：構(gòu)建曲線二叉樹CurveBinaryTree(V)

Ifn

CBT←BottomProcess(V)

else

V1,V2←SubTiles(V)

CBT1←CurveBinaryTree(V1)

CBT2←CurveBinaryTree(V2)

CBT←CoarserProcess(V,V1,V2,CBT1,CBT2)

end

returnCBT

算法2：底層處理BottomProcess(V)

CBT←EmptySet

for ?p1,p2∈?V

λ← straight line fromP1toP2

CBT.add(Φ(λ))

end

returnCBT

算法3：粗糙處理CoarserProcess(V,V1,V2,CBT1,CBT2)

CBT←CBT1∪CBT2

if (Basic-Mode==1) then

InterfaceSet←?V1∩?V2

else if(Optimized-Mode==1) then

InterfaceSet←BestPixels(?V1∩?V2)

end

for ?p1,p2:p1∈?V∩?V1,p2∈?V∩?V2

AllResponses←EmptySet

for ?p3∈InterfaceSet

λ1← curve fromP1toP3in setCBT1

λ2←curve fromP3toP2in setCBT2

Φ(λ)←concatenate(Φ(λ1),Φ(λ2))

AllResponses.add(Φ(λ))

end

CBT.add(AllResponses.bestResponse())

end

returnCBT

本文算法最終輸出為模糊邊界圖像Ei,j=0表示沒有邊界通過像素(i,j)。Ei,j值越大，表示邊界通過的統(tǒng)計可能性越高。該邊界圖像E的生成具體如下所述。初始設定E的所有像素值均為0，對于每個響應變量Φ(λ)，分配一個重要性得分，取決于其均值對比度C和長度L，一個正得分表示該曲線可能為邊界。然后，將該曲線二叉樹中所有正得分的曲線從大到小排序。對于該排序列表中的每條曲線λ和每個像素p∈P，設定E(p)記錄λ的得分。為了處理正得分的重合曲線，本文應用非極大值抑制方法：如果某些像素p的當前E(p)為正值，則該得分不再減??；如果，P中的大多數(shù)像素已經(jīng)被之前得分較高的曲線標記，則丟棄當前曲線λ，不將其像素添加到E中。

2 算法分析與優(yōu)化

2.1 算法復雜度分析

t(S)=2t(S/2)+O(S1.5)

(3)

根據(jù)主定理(master theorem)，總復雜度t(S)可轉(zhuǎn)換為標準形式，如式(4)所示

t(n)=at(n/b)+f(n)

(4)

下面針對分塊過程，計算其具體復雜度。第j=0層即根節(jié)點表示整個尺寸為n×n圖像，第j=1層為兩個尺寸為n×n/2矩形，第j=2層為4個尺寸為n/2×n/2的正方形。所以，當j為偶數(shù)時，該層包含尺寸為n/2j/2×n/2j/2的方塊；當j為奇數(shù)時，該層包括尺寸為n/2(j-1)/2×n/2(j+1)/2的矩形。

在底層，對于每個葉分塊，掃描所有從分塊的一端開始到另一端結(jié)束的直線。這些響應值所需要的運算次數(shù)與圖像的總像素個數(shù)N有關，所以該層運算次數(shù)的總數(shù)為O(N)。然后，在每個粗糙層j，通過連接j+1層兩條短線來構(gòu)建每條曲線，每條曲線在連接線上有一個公共點。所以當j為偶數(shù)時，該層的運行的總次數(shù)為

6N×n/2j/2=6N1.5×2-j/2

(5)

當j為奇數(shù)時，該層的運行的總次數(shù)為

6N×n/2(j+1)/2=6N1.5×2-(j+1)/2

(6)

將各層的運算次數(shù)進行求和，得到本文算法的總運算復雜度AC(N)，如式(7)所示

(7)

其中，jb為底層層號，即層數(shù)，jeven表示所有偶數(shù)層，jodd表示所有奇數(shù)層。對式(7)進行轉(zhuǎn)換，得到式(8)，說明本文算法的復雜度小于18N1.5

(8)

2.2 算法復雜度優(yōu)化

當處理大尺寸圖像時，O(N1.5)的運算時間復雜度仍較大，效率較低，因此，需要開發(fā)效率更高的算法。

與之前一樣，第j層分塊V的兩個子分塊V1和V2，像素對p1、p2∈?V。優(yōu)化算法仍然以p1和p2之間最佳響應計算邊界曲線。然而并非在連接線V12=?V1∩?V2中遍歷所有的像素，而是僅考慮包括k個像素的子集。為得到該子集，對每個像素p3∈V12，本文尋找最高響應值的曲線，與之前一樣，從?V1或?V2開始，至p3結(jié)束。然后，僅保留最高響應值的k個像素。

對于6N對起點和終點中的每一對，在連接線上只有最優(yōu)的k個像素，所以，在第j層共有6Nk條曲線。另外，新增的運算是選擇最優(yōu)的k個像素。由于分塊數(shù)目等于2j，連接線的長度約等于n/2j/2，所以對于第j層，該選擇步驟的運算量由logk·2j·n/2j/2

3 實驗結(jié)果與分析

本部分實驗以visual studio c++(版本2012)為平臺，應用多線程方式，處理器：英特爾Core i7 4800 M 2.9 GHz；CUP：16 G；操作系統(tǒng)64為Windows。利用模擬圖像和真實圖像檢驗本文算法的性能，并與傳統(tǒng)的BCP算法和LOG邊緣檢測方法進行對比。

3.1 模擬圖像

首先比較本文一般算法(算法復雜度為O(N1.5))與本文優(yōu)化算法(算法復雜度為O(NlogN))的時間情況。對于尺寸128×128的圖像，本文一般算法時間為0.25 s，本文優(yōu)化算法時間為0.19 s；對于尺寸512×512的圖像，本文一般算法時間為7.3 s，優(yōu)化算法為3.1 s。兩種算法的邊緣檢測時間與圖像尺寸大小的變化關系，如圖2所示。可以看出，本文優(yōu)化算法所用時間遠低于本文一般算法，同時，隨著圖像尺寸的增大，優(yōu)化算法節(jié)省的時間越多。

圖2 本文一般算法和優(yōu)化算法時間對比

下面對圖3(a)所示的模擬圖像進行實驗。該模擬圖像包括狹長三角形、直線、同心圓和“S”形。為了驗證本文算法的有效性，對該圖像進行高斯加噪處理，使得SNR范圍為0～2，間隔為0.2，同時添加影響程度2%的椒鹽噪聲。本部分利用F-Measure(FM)[16]評價標準量化算法的邊界檢測性能，定義如下式

(9)

式中：RC(recall)表示查全率，PR(precision)表示查準率。同時，本文一般算法、優(yōu)化算法同傳統(tǒng)的BCP算法和LOG算法相比較。不同算法的FM值隨SNR的變化曲線如圖4所示，其中SNR=0(純噪聲)、0.8(低SNR)、1.4(中SNR)、2.0(高SNR)的不同算法的FM值見表1。

圖3 模擬圖像

圖4 不同算法FM值隨SNR的變化曲線

算法00.81.42.0本文一般算法0.0010.430.850.93本文優(yōu)化算法0.0010.400.830.92BCP算法0.0030.300.700.85LOG算法0.0050.170.520.68

由圖4可以看出，本文兩種算法的FM值比傳統(tǒng)邊緣檢測算法有明顯提高，本文優(yōu)化算法的結(jié)果稍微低于本文一般算法，但非常接近。說明本文優(yōu)化算法在大幅度提高運算時間的同時，可以有效保持檢測精度。由表1可以看出，當圖像中只含有噪聲(SRN=0)時，所有算法的FM均很低，即不能探測到邊界，并且本文兩種算法具有更低的FM值，說明本文算法具有更好的抗噪性能。當圖像的SNR為低級(SNR=0.8)時，本文兩種算法的FM值為0.4以上，明顯高于傳統(tǒng)兩種方法，說明本文方法檢測微弱邊界的性能有明顯提高。當圖像的SNR為中級(SNR=1.4)和高級(SNR=2.0)時，本文兩種算法的FM值分別達到0.8和0.9以上，比傳統(tǒng)方法有很大提高，說明本文方法具有良好的邊緣檢測性能。

圖3(b)和圖3(c)分別給出SNR=1.4和SNR=2.0時，模擬圖像的加噪結(jié)果。圖5和圖6分別給出兩種模擬加噪圖像，本文優(yōu)化算法和兩種傳統(tǒng)方法的邊緣檢測結(jié)果。

圖5 SNR=1.4的邊緣檢測結(jié)果

圖6 SNR=2.0的邊緣檢測結(jié)果

由圖5可以看出，當SNR=1.4時，本文方法可以有效檢測出圖像中含有的邊界信息，尤其是可以較好地檢測出短直線；傳統(tǒng)的BCP算法并不能檢測出短直線和完整的圓；傳統(tǒng)的LOG算法則不能有效檢測到邊界。由圖6可以看出，當SNR=2.0時，本文算法可良好地檢測到圖像中的所有邊界；傳統(tǒng)的BCP算法仍不能檢測到短直線，LOG算法的檢測效果雖有所提高，但整體仍較差。說明本文算法對于微弱邊界的檢測效果明顯優(yōu)于傳統(tǒng)方法，具有很好的抗噪性能。但是本文算法顯得過于注重微弱邊界，所以檢測到的圓中含有較多短條紋。

3.2 真實圖像

為了進一步說明本文算法良好的邊緣檢測性能，對真實自然圖像進行實驗。首先對自然景觀圖像進行邊緣檢測，然后對生物醫(yī)學圖像進行邊緣檢測。同時比較本文優(yōu)化算法和傳統(tǒng)BCP算法和LOG算法的檢測結(jié)果。

3種方法對自然景觀的檢測結(jié)果如圖7所示，分別對樹干年輪、樹葉葉脈、河提和大橋4種自然景觀圖像進行檢測?？梢钥闯?，本文算法可以有效的檢測出不同自然景觀中的細小紋理，尤其是對年輪的檢測，幾乎可以檢測出所有的年輪。而傳統(tǒng)方法只能檢測部分紋理邊緣，對細節(jié)檢測能力較弱。

圖7 自然景觀圖像檢測結(jié)果

生物醫(yī)學圖像多屬于微觀世界，所含的邊緣紛繁復雜、細小微弱，對其進行有效邊緣檢測具有十分重要的意義。本實驗分別對神經(jīng)元、視網(wǎng)膜血管、微生物、細胞結(jié)構(gòu)4種生物醫(yī)學圖像進行檢測，檢測結(jié)果如圖8所示?？梢钥闯?，本文算法可以良好地檢測到傳統(tǒng)方法難以檢測到的細節(jié)。本文算法對生物醫(yī)學圖像細節(jié)的良好檢測性能，可以為目前生物醫(yī)學領域的研究做出重要貢獻。

圖8 生物醫(yī)學圖像檢測結(jié)果

4 結(jié)束語

本文主要研究在噪聲圖像中實現(xiàn)微弱邊界檢測的算法。設計多尺度匹配濾波器，檢測任意形狀和長度的微弱邊界，使本文算法對不同應用的圖像均可以實現(xiàn)良好的檢測；利用多線程和自下而上的搜索策略提高邊緣檢測速度；同時只保留有效中間元素，對算法進行優(yōu)化。通過對模擬加噪圖像和自然景觀、生物醫(yī)學的真實圖像進行實驗，本文算法對微弱邊界可實現(xiàn)有效的檢測。

由于本文算法的焦點多集中于微弱邊界的探測，所以對于噪聲圖像，有時會出現(xiàn)細小的偽邊緣。如何更好地處理該種情況，進一步提高邊緣檢測性能，是下一步研究的重點。