基于圖搜索策略的邊緣檢測方法

劉 煬,石文瑩，石鴿婭，王 靜，湯傳玲

（合肥工業大學，安徽 合肥230009）

圖像邊緣是圖像識別和計算機分析的關鍵信息。邊緣蘊含了豐富的內在信息，是圖像識別中抽取圖像特征的重要屬性。本質上說，圖像邊緣是圖像局部特性不連續性的反映，它標志著一個區域的終結和另一個區域的開始。邊緣提取首先檢出圖像局部特性的不連續性，然后再將這些不連續的邊緣像素連成完備的邊界。邊緣的特性是沿邊緣走向的像素變化平緩，而垂直于邊緣方向的像素變化劇烈。從這個意義上說，提取邊緣的算法就是檢出符合邊緣特性的邊緣像素的數學算子。

目前提取邊緣常采用邊緣算子法、內邊界檢測、圖搜索策略、曲面擬合法、模板匹配法和門限化等方法。

1 邊緣檢測算子法

在圖像分析中，邊緣一般用于尋找區域的邊界。假定區域具有均勻的亮度，其邊界就是圖像函數變化的位置，因此,在理想情況下,具有高邊緣幅值的像素中沒有噪聲，可見邊界與其組件（邊緣）的梯度方向垂直。

檢測小局部鄰域的單個梯度算子事實上是卷積，可以用卷積掩模來表達。能夠檢測邊緣方向的算子是用一組掩模來表達的，每個掩模對應一個方向。

1.1 Roberts算子

Roberts算子是最古老的算子之一,由于它只使用了當前像素的2×2鄰域，因此計算非常簡單。Roberts算子的卷積掩模為：

邊緣的幅值計算為：

Roberts算子的主要缺點是對噪聲高度敏感，因為它僅使用了很少幾個像素來近似梯度。

1.2 Laplace算子

Laplace算子▽2是近似只給出梯度幅值的二階導數的流行方法，Laplacian在數字圖像中用卷積和來近似。通常使用3×3來掩模h，對于4-鄰接和8-鄰接的鄰域分別定義為：

Laplace算子的缺點是它對圖像中的某些邊緣產生雙重響應。

1.3 Prewitt算子

近似圖像函數一階導數的算子由于具有確定梯度方向的能力，有時被稱作羅盤算子。對于每個算子,給出前面3×3掩模，其他可以通過簡單旋轉得到。

梯度方向由具有最大響應的掩模給出。對于以下所有的近似一階導數的算子也都是如此。

1.4 Sobel算子

Sobel算子通常用于水平和垂直邊緣的一個簡單檢測子，這時使用 h1和 h3。 如果 h1的響應是 y，h3的響應是x，則可以根據式(6)得出強度：

1.5 邊緣算子法實驗結果及分析

利用6種邊緣檢測算子檢測出的邊緣圖像如圖1所示。從實驗結果可以看出，Roberts算子檢測精度不夠，忽略了一部分邊界且有噪點；而 Log算子、Canny算子和高斯濾波后的Canny算子檢測結果邊界太過復雜，將很多背景像素識別成了邊界；Sobel和Prewitt算子檢測結果比較相近，但是Sobel算子檢測結果散點較多，相比之下，Prewitt算子檢測結果最令人滿意。Prewitt算子檢測的結果比另外5種算子的檢測結果邊界光滑、完整且散點少，因此本實驗中Prewitt算子的檢測結果被認為是這幅圖的最優邊緣，將它與其他方法得到的邊界比較，從而給出其他算法相對合理的評價，如圖2所示。其中，算子檢測結果越接近1,效果越好。

2 內邊界跟蹤及實驗分析

內邊界跟蹤對于超過一個像素大小的區域都有效（尋找單像素區域的邊界毫無意義）。該算法可以找到區域的邊界，但是不能找到區域孔的邊界。如果還要搜索孔的邊界，邊界跟蹤必須在每個區域或孔的邊界元素上開始，而該元素必須是以前從來沒有跟蹤過的邊界元素。尋找邊界元素搜索總是在當前跟蹤的邊界封閉之后才進行，而搜索“還沒有使用”的邊界元素的方法可依照搜索第一個邊界元素的方式進行。需要注意的是，如果物體是單像素寬，就需要增加一些條件；如果目標是檢測區域的外邊界,所給出的方法根據4-鄰接仍然可以用。

根據給定的兩個起始點和結束點搜索得到的邊界圖像如圖3所示。因為圖像中前景區域已被定義，所以檢測出來的邊界是唯一的。將該邊界與前面Prewitt算子檢測出的邊緣進行比較 (內邊界跟蹤圖像÷Prewitt算子邊界圖像)，得出評價值為2.562 8。內邊界跟蹤所得到的圖像的優點是沒有散點且圖像的連續性好，但是由于算法本身的原因，一部分邊界太粗了，不夠簡潔。

3 圖搜索的邊緣跟蹤

圖是由一組節點ni和節點間的弧(ni,nj)構成的一種普通結構?？紤]有方向的數值加權的弧，這些權稱為費用。邊界檢測過程被轉換為在加權圖中搜索最優路徑的問題，目的是找到連接兩個指定節點(即起點和終點)的最優路徑。該方法同樣適用于搜索費用最大化的路徑。

3.1 5種啟發函數

給定回溯路徑的費用，或者每步取最優路徑搜索，啟發函數會有不同的檢測范圍，邊界檢測的結果當然也不同。

(1)啟發函數 1

啟發函數1是利用灰度圖像灰度差值檢測實現的搜索，開始節點與子節點的灰度差值越小，這個子節點越可能是下一個邊界節點，將這些點連起來。其定義為：

其中，a、b都是圖像上的點，g(x)是圖像上點 x的灰度。圖4所示為啟發函數1的搜索范圍和檢測結果。

(2)啟發函數 2

啟發函數2是在啟發函數1的基礎上增加對節點距離判斷來進行的搜索，開始節點與子節點的距離越近，這個子節點越可能是下一個邊界節點，將這些點連起來。其定義為：

其中，a、b是圖像上的點，g(x)是圖像上點 x的灰度，d(x1,x2)是x1、x2兩點之間的距離。圖5所示為啟發函數2的搜索范圍和檢測結果。

(3)啟發函數 3

啟發函數3是對區域對比度最大值的判斷，它考慮中心點和周圍鄰接點之間的關系，將當前節點與以節點為中心的3×3鄰域的灰度總和進行比較，對比度為最大值的作為下一個節點，繼續上面操作。其定義為：

其中,Ω′是 3×3 的圖像矩陣鄰域，a 是 Ω′上的點，g(x)是圖像上點 x的灰度，∑g(x)是 Ω′中所有點的灰度總和。圖6所示為啟發函數3的搜索范圍和檢測結果。

(4)啟發函數 4

啟發函數4是對區域灰度最大值的判斷，節點灰度越大越可能是下一個邊界節點，其定義為：

圖7所示為啟發函數4的搜索范圍和檢測結果。

(5)啟發函數 5

啟發函數5是Laplace檢測子，它檢測像素是邊緣的可能性，越可能的點，回溯路徑的費用就越小。其定義為：

其 中 ，a∈L(I3×3)，L(I3×3)是 Laplace 檢 測 子;p(a)是 像 素 a的邊緣概率，p(a)≥thre，thre是給定的閾值，通常給定thre=0.5。圖8所示為啟發函數5的搜索范圍和檢測結果。

3.2 5種啟發函數對比

在每種啟發函數的檢測范圍中，將背景顏色設為0（即深藍色，見顏色表），起始點顏色設為 50，對每個檢測范圍進行標記，下一個檢測范圍顏色加1，這樣，可以很直觀地看出啟發函數的搜索路徑。將5種啟發函數檢測范圍做比較，很容易發現啟發函數4檢測的路徑非常明確，而且范圍不大，效率較高。

5種啟發函數檢測范圍的比較如圖9所示，顯然，啟發函數4的搜索范圍比其他4個小很多，它的搜索效率高于其他4個啟發函數。

5種啟發函數檢測精度的比較如圖10所示，啟發函數1和啟發函數2精度太低,而啟發函數3和啟發函數5雖然搜索精度也比較高，但是從視覺上就能發現其并不是所要的邊界；而啟發函數4的搜索精度達到了0.986 6,并且形狀與原圖非常相近。

本文分別用3種方法對圖像邊緣檢測進行了實驗，其中邊緣檢測算子是一組用于在亮度函數中定位變化的非常重要的局部圖像預處理方法，而邊緣是亮度函數發生急劇變化的位置。各邊緣檢測算子通過自己特有的卷積掩模與圖像做卷積，得出邊界圖像。在本文的邊緣檢測算子實驗中，Prewitt算子檢測結果最令人滿意。

內邊界檢測是通過給定起始點和結束點檢測二值圖像的，用每次最先找到的相同像素值的節點將起始點與結束點連接起來，如此反復，得出邊界圖像。這樣檢測出的圖像連續性好，但是會造成一部分邊界過粗。

基于圖搜索的邊緣跟蹤是對每條路徑進行判斷并找出最優路徑的過程，而啟發式搜索在搜索過程中加入了與問題有關的啟發性信息，用以指導搜索向著一個比較小的范圍內進行，加速獲得結果。本文實驗中，啟發函數4在搜索效率和精度上比其他啟發函數更令人滿意。

總體來說，各種方法都有其優勢及不足，在實際應用中，需要通過對圖像的分析進一步選擇合適的算法，以找出最理想的邊界圖像。在實際操作中，不同的圖像對啟發函數的要求也不一樣，如何找到最合理的啟發函數對圖像進行搜索有待研究。

[1]SCHETTINI R.A segmentation algorithm for color images[J].Pattern Recognition Letters,1993(14):499-506.

[2]PRIESE L,REHRMANN V.On hierarchical color segmentation and applications[C].IEEE Proceedings of Computer Vision and Pattern Recognition,1993:633-634.

[3]王耀南,李樹濤,毛建旭.計算機圖像處理與識別技術[M].北京：高等教育出版社,2001.

[4]孫慧,周紅霞.圖像處理中邊緣檢測技術的研究[J].電腦開發與應用,2002,15(10):7-9.

[5]趙雪松,陳淑珍.綜合全局二值化與邊緣檢測的圖像分割方法[J].計算機輔助設計與圖形學學報,2001,13(2):118-121.