用于Canny算子邊緣檢測(cè)的廣度優(yōu)先算法研究

肖瑞瑩，楊 帆，董正宏

(1.裝備學(xué)院 研究生管理大隊(duì)，北京 101416；2.裝備學(xué)院 信息裝備系，北京 101416)

0 引 言

圖像的邊緣檢測(cè)通過(guò)在噪聲背景中識(shí)別目標(biāo)物體邊界點(diǎn)與邊界線段，提取出圖像的邊緣輪廓。圖像邊緣廣泛存在于目標(biāo)物體基本單元之間以及目標(biāo)物體與圖像背景之間，圖像邊緣的檢測(cè)是圖像視覺領(lǐng)域從底層向頂層推理的重要基礎(chǔ)，包含著圖像重要信息與圖像特征。邊緣檢測(cè)算法作為圖像視覺領(lǐng)域的研究基礎(chǔ)，在軍事、醫(yī)學(xué)、環(huán)境學(xué)等領(lǐng)域發(fā)揮著重要作用。

高效的邊緣檢測(cè)算法可以提高后續(xù)圖像處理的正確率，基于此許多針對(duì)邊緣檢測(cè)的算法研究相繼展開[1-4]。實(shí)際檢測(cè)算法中常用到一階與二階導(dǎo)數(shù)算法。Canny算子[5]通過(guò)一階梯度算法計(jì)算得到梯度變化極大值點(diǎn)，具有高信噪比的檢測(cè)特點(diǎn)，但是檢測(cè)結(jié)果具有較多斷裂的線段，圖像的邊緣不能構(gòu)成較為完整的輪廓。二階梯度算法如Log算子[6]利用二階導(dǎo)數(shù)過(guò)零點(diǎn)，進(jìn)一步檢測(cè)出圖像邊緣點(diǎn)。二階算法可以檢測(cè)出突變像素點(diǎn)作為邊緣點(diǎn)，便于進(jìn)行后續(xù)圖像處理，但二階導(dǎo)數(shù)算法易受噪聲影響，在檢測(cè)中容易損失部分圖像信息[7]。

針對(duì)一階導(dǎo)數(shù)Canny算子存在較多斷裂點(diǎn)、圖像邊緣不完整的缺點(diǎn)，可以在提取圖像邊緣之后應(yīng)用邊緣連接方法將不完整的邊緣進(jìn)行處理，優(yōu)化圖像邊緣，提高邊緣檢測(cè)正確率。目前對(duì)于已經(jīng)提取得到的圖像邊緣進(jìn)行邊緣連接提出的優(yōu)化算法不斷涌現(xiàn)。如基于人類感知的邊緣連接法[8]，將人工設(shè)定閾值改進(jìn)為自適應(yīng)求閾值，通過(guò)求得的自適應(yīng)高低兩個(gè)閾值分別得到兩幅閾值圖像，對(duì)高閾值圖像的邊緣點(diǎn)進(jìn)行鄰域搜索，尋找低閾值圖像中是否存在與其相連的像素點(diǎn)，符合判別條件的點(diǎn)都存入最終將輸出的圖像數(shù)組中。另外，基于穩(wěn)健擬合的直線邊緣連接法[9]，使用卡爾曼濾波器對(duì)圖像檢測(cè)得到的邊緣點(diǎn)進(jìn)行搜索，找到部分遺漏的微小信息，再利用穩(wěn)健法代替?zhèn)鹘y(tǒng)的最小二乘法，對(duì)圖像邊緣點(diǎn)進(jìn)行擬合主要針對(duì)直線的邊緣線段有著較好的連接效果。然而在實(shí)際應(yīng)用中需要一種具有一般適用性的邊緣連接算法，以提高圖像連通性。

文中設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)二維圖像的邊緣檢測(cè)系統(tǒng)，在Canny算子的基礎(chǔ)上實(shí)現(xiàn)了邊緣的優(yōu)化。采用基于廣度優(yōu)先算法[10]的邊緣連接算法減少斷裂點(diǎn)，從而提高邊緣的連續(xù)性和圖像的連通性，并定量分析圖像邊緣查全率和連通分量。

1 Canny算子實(shí)現(xiàn)圖像檢測(cè)

利用Canny算子檢測(cè)圖像[11]時(shí)，需要首先對(duì)圖像進(jìn)行灰度化處理。對(duì)初始彩色圖像進(jìn)行灰度化處理的方法是將每個(gè)像素點(diǎn)的RGB格式像素通過(guò)公式轉(zhuǎn)化為灰度像素：

Gray=0.299R+0.587G+0.114B

(1)

式1考慮到人眼識(shí)別圖像的特點(diǎn)，對(duì)RGB像素進(jìn)行了加權(quán)平均。

其次對(duì)灰度圖像進(jìn)行高斯平滑濾波，即使用高斯濾波器對(duì)初始圖像進(jìn)行平滑濾波去噪。這里H(χ,y)為高斯平滑函數(shù)。

(2)

與待檢測(cè)圖像f(χ,y)做卷積可得到平滑圖像G(χ,y)。

G(χ,y)=f(χ,y)*H(χ,y)

(3)

使用一階偏導(dǎo)數(shù)計(jì)算梯度幅值和方向，得到x和y兩個(gè)方向的偏導(dǎo)數(shù)矩陣：

(4)

梯度幅值和方向?yàn)椋?/p>

ψ1(m,n)=f(m,n)*H1(m,n)

(5)

ψ2(m,n)=f(m,n)*H2(m,n)

(6)

(7)

(8)

最后對(duì)梯度幅值進(jìn)行極大值抑制，排除非邊緣點(diǎn)像素點(diǎn)。

經(jīng)過(guò)上述處理，篩選所得像素點(diǎn)還需通過(guò)非極大值抑制排除非邊緣的像素點(diǎn)。對(duì)當(dāng)前像素點(diǎn)集合進(jìn)行附近八鄰域像素點(diǎn)比較，如果該點(diǎn)不是九個(gè)像素點(diǎn)中梯度幅值最大的點(diǎn)，則從邊緣點(diǎn)集合中剔除。使用該方法遍歷集合中所有點(diǎn)，即可實(shí)現(xiàn)非極大值點(diǎn)抑制。

八鄰域點(diǎn)位置如圖1所示。

32140567

圖1 八鄰域點(diǎn)示意圖

為減少檢測(cè)圖像的斷裂點(diǎn)，Canny算子本身采用了手動(dòng)設(shè)定的雙閾值檢測(cè)與邊緣連接。選取使用高低兩個(gè)閾值，并利用兩個(gè)閾值對(duì)圖像進(jìn)行閾值分割，可以得到兩幅閾值分割圖。以高閾值分割的圖像噪音少，但邊緣斷點(diǎn)相對(duì)多，而以低閾值分割的圖像包括了較多的邊緣信息。由此可利用低閾值分割圖像對(duì)高閾值分割圖像進(jìn)行補(bǔ)充，在高閾值分割圖像的端點(diǎn)處通過(guò)八鄰域搜索算法搜索周圍是否存在高于低閾值的點(diǎn)，如果存在，則將兩點(diǎn)相連，并對(duì)下一個(gè)點(diǎn)繼續(xù)進(jìn)行搜索，直到搜索結(jié)束，再對(duì)另一個(gè)高閾值圖像中的端點(diǎn)進(jìn)行新一輪的搜索，最終使得圖像邊緣連接成一個(gè)完整的輪廓。

使用Canny算子邊緣檢測(cè)算法，檢測(cè)結(jié)果的圖像對(duì)較弱邊緣也可做出較好的響應(yīng)，但檢測(cè)圖片中圖像邊緣仍存在較多斷裂處。Canny算子對(duì)邊緣進(jìn)行連接的效果不理想，圖像邊緣不能構(gòu)成較為完整的輪廓。

2 Canny算子的邊緣優(yōu)化

2.1 基于廣度優(yōu)先的邊緣連接算法基本原理

文中采用基于廣度優(yōu)先的邊緣連接算法進(jìn)行優(yōu)化圖像連通性的設(shè)計(jì)與實(shí)現(xiàn)。該算法首先使用基于人類感知連接法中相同原理判斷像素點(diǎn)是否為端點(diǎn)，之后采取廣度優(yōu)先的搜索算法將圖像端點(diǎn)相連。對(duì)檢測(cè)圖像中的端點(diǎn)進(jìn)行連接前，首先應(yīng)判斷哪些點(diǎn)是端點(diǎn)，這里采取的辦法仍是對(duì)邊緣點(diǎn)八鄰域進(jìn)行搜索，如果鄰域中有一個(gè)點(diǎn)與之相連則該點(diǎn)是端點(diǎn)，否則其他情況均不是端點(diǎn)。

一個(gè)像素點(diǎn)的八鄰域指圖1所示的0至7八個(gè)點(diǎn)。要建立3×3的鄰域拓?fù)鋱D。

判斷一個(gè)像素點(diǎn)的八鄰域點(diǎn)，相連情況一共有四種：沒(méi)有點(diǎn)與其相連則該像素點(diǎn)為孤立點(diǎn)，有一個(gè)點(diǎn)相連為端點(diǎn)，有兩個(gè)點(diǎn)相連為邊緣線中的一點(diǎn)，有四個(gè)點(diǎn)相連為兩條邊緣線交叉點(diǎn)。

在對(duì)每一個(gè)像素點(diǎn)進(jìn)行判斷后，將屬于端點(diǎn)的像素點(diǎn)存入端點(diǎn)數(shù)組中。然后對(duì)端點(diǎn)數(shù)組中的像素點(diǎn)進(jìn)行搜索，搜到同為端點(diǎn)的像素點(diǎn)時(shí)將兩者相連完成閉合即可。當(dāng)滿足停止條件，即搜索長(zhǎng)度大于最大閾值或搜索到另一個(gè)端點(diǎn)時(shí)，標(biāo)記搜索路徑完成閉合，隨后再?gòu)闹袛嗵幹匦麻_始掃描。

該算法具體步驟如下：

(1)將每個(gè)輪廓像素的鄰域Xi添加一個(gè)從0至7的整數(shù)標(biāo)號(hào)，如圖1所示。

每個(gè)輪廓像素通過(guò)編碼方式V分配鄰域配置：

(9)

(2)建立一張查閱表T，查閱表中的每一個(gè)元素由V定址。當(dāng)編碼的配置是一個(gè)端點(diǎn)時(shí)，將T[V]設(shè)置為1。首先確認(rèn)它的編碼配置V0，然后判斷T[V0]的值是否為1，滿足T[V0]=1的點(diǎn)就可以判定為端點(diǎn)。圖2給出了一幅V=4的典型配置極點(diǎn)示意圖，該標(biāo)記方塊表明了一個(gè)邊界像素，且標(biāo)號(hào)為5、6、7的方塊表明該像素將包括在搜索過(guò)程中。

圖2 V=4搜索示意圖

為了建立閉合路徑，需要檢查圖2中選中像素點(diǎn)的3個(gè)拓?fù)溧徲颉Ｏ鄬?duì)靠近中央?yún)^(qū)域的點(diǎn)的鄰域坐標(biāo)與T[V]連接，一個(gè)端點(diǎn)則是樹的一個(gè)根節(jié)點(diǎn)，樹的分支代表了所有可能的閉合路徑。每個(gè)節(jié)點(diǎn)代表一個(gè)像素且被梯度值標(biāo)號(hào)。一條路徑的代價(jià)為該路徑所有節(jié)點(diǎn)標(biāo)號(hào)值之和。

使用廣度優(yōu)先算法挑出端點(diǎn)中最佳后繼[12]，這里對(duì)廣度優(yōu)先算法進(jìn)行優(yōu)化，最佳后繼點(diǎn)不可同屬于同一連通分量[13]，即將搜索到非同一連通分量的端點(diǎn)相連，減少錯(cuò)邊。將選中點(diǎn)標(biāo)記為一個(gè)輪廓點(diǎn)，則上文所述的過(guò)程開始后，就開始建立閉合路徑，直到滿足停止搜索的條件。停止搜索條件為：路徑的長(zhǎng)度比給定的最大閾值要大，路徑搜索中得到了可連接的一個(gè)端點(diǎn)。

其中，廣度優(yōu)先搜索算法的步驟如下[14]：

(1)把被搜索的像素點(diǎn)作為起點(diǎn)，對(duì)起點(diǎn)進(jìn)行第一層搜索，如搜索到端點(diǎn)則結(jié)束，對(duì)下一個(gè)像素點(diǎn)重復(fù)進(jìn)行搜索；否則進(jìn)行步驟2。

(2)若步驟1中未搜索到目標(biāo)點(diǎn)，則進(jìn)行第二層搜索，第二層為第一層搜索逐個(gè)擴(kuò)展得到的點(diǎn)，重復(fù)對(duì)每個(gè)點(diǎn)進(jìn)行搜索，如搜索到端點(diǎn)則結(jié)束，對(duì)下一個(gè)像素點(diǎn)進(jìn)行相同搜索步驟；否則判斷搜索層數(shù)是否超過(guò)預(yù)設(shè)的最高搜索閾值，如果超過(guò)則本次搜索結(jié)束，對(duì)下一個(gè)像素進(jìn)行廣度優(yōu)先搜索，如果未超則對(duì)第二層像素點(diǎn)繼續(xù)擴(kuò)展并重復(fù)步驟1。

2.2 實(shí)驗(yàn)結(jié)果和評(píng)價(jià)

采取基于廣度優(yōu)先的邊緣連接算法對(duì)Canny邊緣檢測(cè)結(jié)果進(jìn)行邊緣連接，通過(guò)對(duì)比原圖與連接后的圖像，對(duì)基于廣度優(yōu)先的邊緣連接算法的實(shí)驗(yàn)結(jié)果進(jìn)行分析。

2.2.1 邊緣連接圖像展示

如圖3所示，實(shí)驗(yàn)對(duì)邊緣連接前后圖像進(jìn)行上色，連接起來(lái)的邊緣點(diǎn)用相同顏色進(jìn)行標(biāo)記，相同顏色線條表明其為完整無(wú)斷裂的線條。顏色數(shù)量越少，圖像斷裂處越少。對(duì)比圖像實(shí)現(xiàn)邊緣連接前后的邊緣線顏色，可以看到經(jīng)過(guò)廣度優(yōu)先算法優(yōu)化后的邊緣連接圖像取得了較為理想的結(jié)果。

圖3 圖像對(duì)比

從圖3明顯看出邊緣圖像中顏色顯著減少，即連通在一起的線段大幅增加，觀察到圖像中長(zhǎng)頸鹿圖形已經(jīng)連接成為一個(gè)整體。由于廣度優(yōu)先的邊緣連接算法事先定義了一個(gè)最大閾值，當(dāng)對(duì)于一個(gè)端點(diǎn)的鄰域搜索大于定義閾值時(shí)將不再進(jìn)行搜索，也即該點(diǎn)不再與其他端點(diǎn)相連。因此可以看到圖中距離較遠(yuǎn)的線條未被連接，從而保持了邊緣圖像的正確性。最大閾值的設(shè)置可嘗試由大至小，低閾值連接范圍小，連接的端點(diǎn)數(shù)會(huì)少于高閾值結(jié)果，但相應(yīng)地，高閾值連接圖中出現(xiàn)的假邊緣錯(cuò)邊緣概率也有可能增大。

該算法需要選擇設(shè)置較優(yōu)化的閾值，才使得圖像端點(diǎn)既能得以較好連接，同時(shí)不會(huì)大幅增加假邊錯(cuò)邊的數(shù)量，此外搜索長(zhǎng)度超出最大閾值時(shí)算法將放棄對(duì)該點(diǎn)的邊緣連接，可能使得圖像仍存在小部分?jǐn)嗔腰c(diǎn)。在實(shí)驗(yàn)結(jié)果中，最大閾值設(shè)為5，可以看到這種設(shè)定對(duì)于文中用到的圖像有較好的效果。

2.2.2 邊緣連接算法評(píng)估

為了對(duì)邊緣連接算法進(jìn)行定量的性能分析，需要將邊緣連接前后的邊緣點(diǎn)查全率R(也稱召回率，Recall)[15]與連通分量進(jìn)行計(jì)算與比較。查全率反映了檢測(cè)結(jié)果的正確率，查全率越高，說(shuō)明檢測(cè)結(jié)果正確率越高，連通分量的數(shù)值反映了圖像的連通性，連通分量越小，說(shuō)明圖像的連通性越好。

查全率R定義如下：

(10)

其中，Correctmun為通過(guò)Canny算子檢測(cè)得到的邊緣點(diǎn)正確個(gè)數(shù)之和，也即Canny檢測(cè)結(jié)果中也屬于標(biāo)準(zhǔn)邊緣的像素點(diǎn)個(gè)數(shù)之和；Edgemun為標(biāo)準(zhǔn)正確邊緣圖像中邊緣點(diǎn)的個(gè)數(shù)總和。

文中實(shí)現(xiàn)查全率檢測(cè)的算法步驟如下：

(1)將待評(píng)估圖像與正確邊緣圖像分別灰度化，易知不是白色像素點(diǎn)，即灰度值不為255的像素點(diǎn)即為兩圖邊緣點(diǎn)。遍歷每一個(gè)像素點(diǎn)，統(tǒng)計(jì)得到標(biāo)準(zhǔn)正確邊緣圖像中邊緣點(diǎn)的個(gè)數(shù)總和Edgemun，同時(shí)初始化Correctmun值為0。

(2)對(duì)兩圖相同像素位置點(diǎn)進(jìn)行判斷，若待評(píng)估圖像中為邊緣點(diǎn)的像素點(diǎn)同時(shí)也為正確圖像中的邊緣點(diǎn)，則Correctmun加1。

(3)遍歷每一個(gè)像素點(diǎn)，輸出最終Correctmun值。

(4)使用式10計(jì)算出R值。

對(duì)連通分量的定義如下：無(wú)向圖V中，若兩個(gè)頂點(diǎn)相連，則稱兩頂點(diǎn)是連通的，整幅圖像每個(gè)點(diǎn)之間都是兩兩相連的則稱其為連通圖，否則稱為非連通圖。一個(gè)非連通圖的極大連通子圖就是該圖的一個(gè)連通分量。將每一個(gè)極大連通子圖分別用不同色彩標(biāo)記，可直觀判斷出實(shí)現(xiàn)邊緣連接算法之后的圖像連通分量的數(shù)量是否減少。

文中采用了ETHZ Shape Classes-V1.2數(shù)據(jù)庫(kù)中的圖像及其人工標(biāo)記出的相應(yīng)圖像的邊緣作為判別標(biāo)準(zhǔn)。對(duì)經(jīng)過(guò)邊緣連接的Canny算法和本節(jié)邊緣連接算法優(yōu)化后的10幅圖像分別計(jì)算查全率與聯(lián)通分量，并對(duì)結(jié)果求平均值，結(jié)果如表1所示。

由表1可知，在使用邊緣連接算法后圖像查全率均有所提高，而優(yōu)化后邊緣圖像連通分量均大幅降低。由此可以得出，基于廣度優(yōu)先的邊緣連接算法能夠?qū)anny算子進(jìn)行優(yōu)化改進(jìn)，對(duì)提高圖像連通性起到了較為理想的效果。

3 結(jié)束語(yǔ)

文中采用基于廣度優(yōu)先的邊緣檢測(cè)算法，在Canny算子的基礎(chǔ)上實(shí)現(xiàn)了邊緣優(yōu)化，采用基于廣度優(yōu)先的邊緣連接算法，減少斷裂點(diǎn)，從而提高邊緣連續(xù)性和圖像連通性?；趶V度優(yōu)先的邊緣連接算法在優(yōu)化閾值選取時(shí)可以針對(duì)邊緣圖像斷裂處主動(dòng)進(jìn)行邊緣預(yù)測(cè)，不依賴于圖像梯度和圖像自身，從而成功連接大部分細(xì)小的斷裂邊緣。研究結(jié)果證明了該算法的有效性。

參考文獻(xiàn)：

[1] ARAGHI L F,ARVAN M R.An implementation image edge and feature detection using neural network[C]//Proceedings of the international multi conference of engineers and computer scientists.[s.l.]:[s.n.],2009:18-20.

[2] 廖劍利.基于小波變換的圖像邊緣檢測(cè)方法研究[D].長(zhǎng)沙：湖南大學(xué)，2005.

[3] KONISHI S,YUILLE A,COUGHLAN J.A statistical approach to multi-scale edge detection[J].Image and Vision Computing,2003,21(1):37-48.

[4] 蔣 偉,陳 輝.基于分?jǐn)?shù)階微分和Sobel算子的邊緣檢測(cè)新模型[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(4):182-185.

[5] 薛麗霞,李 濤,王佐成.一種自適應(yīng)的Canny邊緣檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(9):3588-3590.

[6] 賀 強(qiáng),晏 立.基于LOG和Canny算子的邊緣檢測(cè)算法[J].計(jì)算機(jī)工程,2011,37(3): 210-212.

[7] 譚 艷,王宇俊,李飛龍,等.幾種典型的圖像邊緣檢測(cè)算法的分析比較[J].電腦知識(shí)與技術(shù),2012,8(3):1604-1608.

[8] 賀賽先,唐 艷.一種基于人類感知的邊緣連接方法[J].紅外技術(shù),2005,27(4):338-342.

[9] 文貢堅(jiān),王潤(rùn)生.一種穩(wěn)健的直線提取算法[J].軟件學(xué)報(bào),2001,12(11):1660-1666.

[10] 楊智明.圖的廣度優(yōu)先搜索遍歷算法的分析與實(shí)現(xiàn)[J].農(nóng)業(yè)網(wǎng)絡(luò)信息,2009(12):136-137.

[11] 曾 俊.圖像邊緣檢測(cè)技術(shù)及其應(yīng)用研究[D].武漢:華中科技大學(xué),2012.

[12] GLIANNAROU S,TANIA S.A novel framework for object recognition under severe occlusion[J].Computational Intelligence,2013,410:235-258.

[13] GEORGIEVA P,MIHAYLOVA L,JAIN L C.Advances in intelligent signal processing and data mining:theory and applications[M].Berlin:Springer,2013.

[14] 張 研,韓 露.用廣度優(yōu)先搜索算法實(shí)現(xiàn)路徑搜索[J].電腦編程技巧與維護(hù),2012(19):78-81.

[15] SMEULDERS A W M,SANTINI S,WORRING M,et al.Content based image retrieval at the end of the early years[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(12):1349-1380.