基于曲線二叉樹的微弱邊緣檢測方法

王 會(huì)，余 陽

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

0 引 言

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

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

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

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

1 本文算法

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

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

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

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

(1)

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

(2)

圖1 曲線二叉樹

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

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

1.2 邊界檢測算法

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

然后，根據(jù)j+1層的響應(yīng)向量，計(jì)算下一個(gè)粗糙層(第j層)的響應(yīng)。本文通過連接兄弟分塊實(shí)現(xiàn)該過程，具體如下所述。令分塊V1和V2為第j+1層的兄弟分塊，V為第j層的母分塊，所有像素對遵循p1∈?V1∩?V，p2∈?V2∩?V。則對于每對像素(p1,p2)，所有像素均在連接線V12=?V1∩?V2中。對于每個(gè)像素p3∈V12，通過連接p1到p3、p3到p2的兩條曲線，計(jì)算其曲線響應(yīng)向量。在所有這些連接曲線中，存儲(chǔ)得分最高的那條曲線。該粗糙處理過程的偽碼如算法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)計(jì)可能性越高。該邊界圖像E的生成具體如下所述。初始設(shè)定E的所有像素值均為0，對于每個(gè)響應(yīng)變量Φ(λ)，分配一個(gè)重要性得分，取決于其均值對比度C和長度L，一個(gè)正得分表示該曲線可能為邊界。然后，將該曲線二叉樹中所有正得分的曲線從大到小排序。對于該排序列表中的每條曲線λ和每個(gè)像素p∈P，設(shè)定E(p)記錄λ的得分。為了處理正得分的重合曲線，本文應(yīng)用非極大值抑制方法：如果某些像素p的當(dāng)前E(p)為正值，則該得分不再減??；如果，P中的大多數(shù)像素已經(jīng)被之前得分較高的曲線標(biāo)記，則丟棄當(dāng)前曲線λ，不將其像素添加到E中。

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

2.1 算法復(fù)雜度分析

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

(3)

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

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

(4)

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

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

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

(5)

當(dāng)j為奇數(shù)時(shí)，該層的運(yùn)行的總次數(shù)為

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

(6)

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

(7)

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

(8)

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 模擬圖像

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

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

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

(9)

式中：RC(recall)表示查全率，PR(precision)表示查準(zhǔn)率。同時(shí)，本文一般算法、優(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)化算法在大幅度提高運(yùn)算時(shí)間的同時(shí)，可以有效保持檢測精度。由表1可以看出，當(dāng)圖像中只含有噪聲(SRN=0)時(shí)，所有算法的FM均很低，即不能探測到邊界，并且本文兩種算法具有更低的FM值，說明本文算法具有更好的抗噪性能。當(dāng)圖像的SNR為低級(jí)(SNR=0.8)時(shí)，本文兩種算法的FM值為0.4以上，明顯高于傳統(tǒng)兩種方法，說明本文方法檢測微弱邊界的性能有明顯提高。當(dāng)圖像的SNR為中級(jí)(SNR=1.4)和高級(jí)(SNR=2.0)時(shí)，本文兩種算法的FM值分別達(dá)到0.8和0.9以上，比傳統(tǒng)方法有很大提高，說明本文方法具有良好的邊緣檢測性能。

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

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

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

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

3.2 真實(shí)圖像

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

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

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

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

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

4 結(jié)束語

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

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