基于Ｐｒｅｗｉｔｔ理論的自適應邊緣檢測算法

摘 要：利用Prewitt基本原理定義了新的算法模板，根據待檢測像素周圍的3×3鄰域的像素平均灰度值，結合人眼的視覺特征自適應地生成動態閾值，不僅保留了原Prewitt算法可并行處理、能夠抑制噪聲等優點，還提高了運算速度。同時，針對Prewitt算法邊緣檢測相對粗糙、邊緣細化算法效率較低的問題，分析和改進了原有邊緣細化算法，改進算法先對含有噪聲的圖像進行邊緣檢測，過濾了偽邊緣，再對圖像邊緣進行細化，從而得到單像素邊緣。通過實驗比較，所提算法能夠自適應地生成動態閾值，并在保持Prewitt算法具有抑制噪聲性能優點的基礎上，提高了運算速度，而且可以獲得更加細膩光滑的邊緣。

關鍵詞：Prewitt算法； 圖像處理； 邊緣檢測； 自適應閾值

中圖分類號：TP391.41文獻標志碼：A

文章編號：1001-3695(2009)06-2383-04

doi:10.3969/j.issn.1001-3695.2009.06.116

Adaptive edge-detection method based on Prewitt algorithm

KANG Mu1， XU Qing-gong2

(1.Academy of Information Technology， Luoyang Normal University， Luoyang Henan 471022， China; 2.Dept. of Computer， Luoyang Institute of Science Technology， Luoyang Henan 471003， China）

Abstract:

For the slow calculation speed and given threshold of Prewitt algorithm， this paper proposed an adaptive of edge detection method. It used the basic principle of the Prewitt algorithm and defined the new template of algorithm. The algorithm got adaptively automatic threshold according to the mean value of the 3×3 area pixels around the detecting pixel and the pro-perty of people’s vision. It not only can keep the original advantages such as parallel process and restrain noise， but also can quick calculation speed. For the edge that Prewitt algorithm detected was comparatively thick， and the efficiency of original edge-thin algorithm was lower， analyzed and improved the original edge-thin algorithm. The improved algorithm firstly detected the edge of the image in which there existed noise and filters the fake edge， then thinned the edge of the image， and finally got the single pixel edge. By comparing the test result of the adaptive edge-detection algorithm with that of original Prewitt algorithm， the adaptive edge-detection method could get adaptively automatic threshold. Besides the original Prewitt algorithm property of restraining noise， it has quicked the calculation speed and gotten more smooth edge than original algorithm.

Key words：Prewitt algorithm; image processing; edge-detection; adaptive threshold

邊緣檢測是圖像處理、目標識別和計算機視覺等領域中最經典的研究內容之一，已有較長的研究歷史，邊緣檢測是所有基于邊界分割方法的第一步。經典的邊緣檢測方法是對原始圖像按像素的某鄰域構造邊緣檢測算子。 應用邊緣檢測的算法是基于邊界的分割方法，常用的邊緣檢測算子有Roberts 、Sobel 、Kirsch、Prewitt以及Laplace等。其中Prewitt算子通過對圖像進行八個方向的邊緣檢測，將其中方向響應最大的作為邊緣幅度圖像的邊緣，且對噪聲具有平滑作用^[1~3]。傳統的邊緣檢測算子的噪聲平滑能力和邊緣定位能力是矛盾的。為了克服這個不足，正確地得到圖像的邊緣信息，已經提出了很多方法，其中邊緣檢測和邊緣細化相結合可以有效地調節噪聲平滑和邊緣定位能力的矛盾。

在本文中利用Prewitt算子的基本原理，改變了一些檢測模板的系數，根據待檢測像素周圍3×3鄰域的像素平均灰度值，結合人眼的視覺特征自適應地生成動態閾值。本算法對噪聲具有一定的抑制作用，對含有噪聲的圖像進行檢測也不會得到過多的偽邊緣，再對得到的圖像邊緣進行細化，可以得到細膩光滑的單像素邊緣。

1 Prewitt 邊緣檢測算法

1.1 傳統的Prewitt 邊緣檢測算法

Prewitt 邊緣檢測算法是一種類似Sobel邊緣檢測算法的邊緣模板算法，通過對圖像進行八個方向的邊緣檢測，將其中方向響應最大的作為邊緣幅度圖像的邊緣。Prewitt邊緣檢測算法的邊緣檢測模板定義如圖1所示。



Prewitt邊緣檢測算子并不把重點放在相鄰的像素上，它對噪聲具有平滑作用。

1.2 Prewitt 邊緣檢測算法的缺陷

a）與Sobel邊緣檢測算子一樣，它檢測出的邊緣比較粗，定位精度比較低，容易損失如角點這樣的邊緣信息。

b）由于Prewitt邊緣檢測算子是通過八個方向模板對圖像進行卷積運算，顯然其運算量是比較大的，影響了邊緣檢測的速度。

c）需要人為指定閾值，自動化程度不高。

本文提出的Prewitt 自適應邊緣檢測算法是針對傳統Prewitt 算法的三個缺陷進行改進，取得了良好的實驗效果。

2 Prewitt自適應邊緣檢測算法

2.1 改進的邊緣檢測模板

針對Prewitt算法運算量大的缺點，把正東和正西方向模板用一個東西方向模板表示，正南、正北方向模板用南北方向模板表示，西南、東北方向模板用東北西南方向模板表示。西北、東南方向模板用東南西北方向表示，定義的新模板如圖2所示。



因為Prewitt原算法在計算一個像素點時需要求八個方向的卷積運算，如在求像素點f(i，j)正西方向卷積運算時用式（1）計算：

Pwest=f(i-1，j-1）+f(i-1，j)+f(i-1，j+1)+f(i，j-1)-2f(i，j)+f(i，j+1)-f(i+1，j-1)-f(i+1，j)-f(i+1，j+1) （1）

改進的算法在求像素點f(i，j)東西方向卷積運算時用式（2）計算：

Peast-west=f(i-1，j-1)+f(i-1，j)+f(i-1，j+1)-f(i+1，j-1)-f(i+1，j)-f(i+1，j+1)（2）

其他幾個方向上的卷積運算的式子與以上兩式大同小異。

a）改進的模板在檢測邊緣時，可以獲得與原Prewitt模板相同的梯度值。

例如，對于南北（或垂直）方向的邊緣，設f(i-1，j-1）、f(i-1，j)、 f(i-1，j+1)、f(i，j-1)、f(i，j)、f(i，j+1)的灰度值為255，f(i+1，j-1)、f(i+1，j)、f(i+1，j+1)的灰度值為0，將它們代入式（1）得Pwest=765，將它們代入式（2）得Peast-west=765。如果取f(i-1，j-1）、f(i-1，j)、f(i-1，j+1)、f(i，j-1)、f(i，j)、f(i，j+1)的灰度值為0，f(i+1，j-1)、f(i+1，j)、f(i+1，j+1)的灰度值為255，將它們代入式（1）得Pwest=-765，將它們代入式（2）得Peast-west=-765。這里假設邊緣上各點的灰度值相同（這與現實中的邊緣相吻合），對于其他幾種模板以及取其他的灰度值，都有相同的結論。

b）改進的模板比原Prewitt模板具有更強的平滑噪聲能力。

例如，中心點f(i，j)的灰度值為0，其周圍各點的灰度值為255，也就是說中心點是黑色點，而周圍都是白色點，這樣的點f(i，j)一般情況下是噪聲點。用原Prewitt的各個模板計算得到的邊緣幅度值均為510，用改進的各個模板得到的邊緣幅度值為0。

另外，對于a）中的例子，如果令f(i-1，j-1）、f(i-1，j)、f(i-1，j+1)、f(i，j-1)、f(i，j)、f(i，j+1)的灰度值為127，f(i+1，j-1)、f(i+1，j)、f(i+1，j+1)的灰度值為0，也就是說邊緣的左邊是灰度為127的區域，右邊是黑色區域，將它們代入式（1）得Pwest=381（原Prewitt的其他模板得到的邊緣幅度值將會更小），它比510還要小，這說明原Prewitt模板要想檢測到這樣的邊緣，必然會將噪聲點當做邊緣點保留下來。故原Prewitt模板平滑噪聲的能力不如改進的模板。

加法和減法運算^[4]的速度相同，因此不區分它們，統統用加法運算表示。在計算機上執行一條乘法^[4]需要10個時鐘周期，執行一條加法指令或減法指令^[4]需要3個時鐘周期，在計算式（1）時需要8次加法（把減法也當成加法）、1次乘法，一個像素點需要計算8個這樣的模板，故一個像素點需要64次加法、8次乘法，需要272個時鐘周期。對于一幅N×N的圖像總共需要64N2次加法、8N2乘法，272N2個時鐘周期。

在計算式（2）時需要5次加法（減法也當成加法），計算4個這樣的模板，故一個像素點需要20次加法，60個時鐘周期。對于一幅N×N的圖像總共需要20N2次加法，60N2個時鐘周期。兩種算法處理時間指標的比較如表1所示。

表1 兩種算法處理時間指標比較

檢測圖像規模檢測算法加法運算次數乘法次數需時鐘周期數

N×N Prewitt算法64N28N2272N2

改進算法20N2060N2

由表1可知，改進后算法的執行時間大約是原來的60/272=0.220 6，效率提高了3.53倍（是原來的4.53倍）。

2.2 自適應的動態閾值方法

針對傳統Prewitt算法需要人為設定閾值的缺陷， 提出了一種自適應動態閾值方法。基于文獻[5]中二維閾值分割算法中應用鄰域平均灰度的思想，這里也使用3×3鄰域平均值來計算待檢測點的閾值：

x=（1/9）×∑2i=0 ∑2j=0f(i，j)(3)

如果設定固定的閾值，若設置得小，容易產生偽邊緣，設置得大又容易使邊緣間斷。人眼對灰度的分辨能力^[6]，當圖像灰度很高或很低時人眼對灰度的分辨率較差，當圖像灰度適中時人眼的分辨率較強；并且人眼對在圖像平緩部分的噪聲比在細節部分的噪聲更敏感。人類視覺系統在亮區域具有比暗區域小的噪聲敏感度， 該性質被稱為韋伯法則(Weber’s law)；視覺系統在邊緣或結構化區域具有比平滑區域小的噪聲敏感度，該性質稱為結構噪聲掩模^[7]。根據人眼的視覺特性，在視覺分辨率高的區域；閾值設置得小一些（因為人眼容易分辨出它們的不同）；在視覺分辨率低的區域閾值設置得大一些（因為人眼不容易分辨出它們的不同），也就是說相同的灰度差在不同的區域有的被認為是邊緣，有的被認為不是邊緣。由實際經驗和實驗結果可知：在白色區域人眼分辨率最低，其次是黑色區域，再次是灰度值在127左右，比較敏感的區域是灰度值在48和206左右時。人眼睛對灰度值的敏感度不是隨著灰度值的變化呈線性變化的，根據經驗可知，采用拋物線計算閾值比較合理，于是在區域[0，48]、（48，206）和[206，255]中分別定義一個拋物線方程:g(x)=ax2+bx+c。在區域[0，48]中，當x=0時，g(x)=30，當x=-48時，g(x)=8，當x=48時，g(x)=8，可計算出a=-0.009549，b=0，c=30。在區域（48，206）中，當x=127時，g(x)=12，當x=48時，g(x)=8，當x=206時，g(x)=8，可計算出a=-0.000641，b=0.162794，c=1.662554。在區域[206，255]中，當x=255時，g(x)=50，當x=206時，g(x)=8，當x=304時，g(x)=8，可計算出a=-0.017493，b=8.921283，c=-1087.463557（注：這里的參數會有一些誤差）。這里確定閾值的方法是基于人眼的視覺特性，對于所有的灰度圖像都是適用的。檢測閾值threshold用式（4）計算，threshold的圖形如圖3所示

g(x)=-0.009549x2+300≤x≤48

-0.000641x2+0.162794x+1.66255448

-0.017493x2+8.921283x-1087.463557206



在實際檢測邊緣時，可以根據具體情況在threshold前面乘一個系數β（在后面的實驗中取β=6.5），這樣就可以在一幅圖像的不同區域使用不同的閾值來檢測邊緣，比設定固定的閾值要好得多(注：這里用拋物線方程來計算閾值，實驗效果比較好，究竟是否合理，筆者現在還不能從理論上加以證明)。

2.3 邊緣細化

1）文獻[8]中的細化算法

設圖像中已知目標點標記為1、背景點標記為0，定義邊緣點為本身標記為1而其八連通鄰域中至少有一個標記為0的點。本細化算法對邊緣點進行如下操作：

a）考慮以邊緣點為中心的八鄰域，記中心點為qq，其鄰域的八個點順時針繞中心點分別記為q0，q1，q2，…，q7。其中q0在qq的左上方。 首先標記同時滿足下列條件的邊緣點：

（a）2≤N（qq）≤6；（b）S（qq）=1;（c）q1*q3*q5 =0;（d）q3*q5*q7 =0。

其中：N（qq）是中心點qq非0鄰點的個數；S（qq）是以q0，q1，q2，…q7，q0為序時這些點的值從0到1變化的次數。當對所有邊緣點都檢驗完畢后，除去所有標記了的點。

b）標記同時滿足下列條件的邊緣點：

（a）2≤N（qq）≤6 ;（b）S（qq）=1;（c）q1*q3*q7=0; （d）q1*q5*q7 =0

同樣當對所有邊緣點都檢驗完畢后，將所有標記了的點除去。

以上兩步操作構成一次迭代，算法反復迭代直至沒有點再滿足標記條件為止，這時剩下的點便是經過該細化算法得到的圖像單像素邊緣。

2)文獻[8]中算法的缺陷

a）保留了孤立的邊緣點。因為條件a）.(a)和b）.(a)要求2≤N（qq）≤6，也就是中心點qq非0鄰點的個數大于等于2且小于等于6，而孤立點的非0鄰點的個數為0，不滿足這兩個條件，故孤立點沒有除去，而孤立點很可能是噪聲點。

b）運算量大。假設檢測點qq滿足條件a).(a)(b)和b)，且q1、q3、q5為1，q7為0，則需要進行10次比較運算、8次乘法運算。

3)文獻[8]中算法的分析與改進

仔細分析文獻[8]中的細化算法，對于一個像素點是滿足a）中的條件被刪除還是滿足b）中的條件被刪除沒有什么區別；條件a）中（a）(b)與b）中（a）(b)相同，條件a）.(a)或b）.(a)要求qq非0鄰點的個數大于等于2且小于等于6，條件a）.(b)或b).(b)要求這些非0鄰點在q0，q1，q2，…，q7，q0這個序列中是連續的（因為S（qq）=1，所以在q0，q1，q2，…，q7，q0序列中為1的qi，i=0~7，一定是連續的）。顯然如果條件a）.(b)或b）.(b)滿足，則qq的0鄰點也是連續的，且0鄰點的個數也是大于等于2且小于等于6，故至少有一個奇0鄰點qi(i=1，3，5，7)。假設在滿足條件a）.(a)(b)或b）.(a)(b)的前提下，q1=0時，則條件b）.(c)(d)得到滿足，則qq應該除去；同理，當q3=0或q5=0時，條件a）.(c)(d)滿足，q7=0時，條件b）.(c)(d)滿足。故只要條件a）.(a)(b)或b).(a)（b）滿足，則點qq肯定被刪除，而不用再考慮條件a).(c)(d)或b).(c)(d)。

經過以上分析，條件a).(c)(d)和b).(c)(d)是多余的，條件a）.(a)(b)和b).(a)(b)相同，保留一個即可。

故對文獻[8]中的細化算法進行如下改進：

a）如果N（qq）=0，則除去該點。

b）如果2≤N（qq）≤6且S（qq）=1，則除去該點。

以上兩步操作構成一次迭代，第二步反復迭代直至沒有點再滿足標記條件為止。這時剩下的點便是經過該細化算法得到的圖像單像素邊緣（噪聲點一次迭代即可除去，故第一步不需要反復迭代）。

不同圖像的邊緣細化時各個邊緣點排列情況不完全一樣，在求出 N（qq）和S（qq）前提下，按最壞的情況考慮，文獻[8]中的算法需要比較運算10次（注：條件a).(a)和b）.(a)各2次，a）.(b)和b).(b)各1次，a).(c)和b).(c)各1次，a）.(d)和b).(d) 各1次），乘法運算8次；改進的算法在不考慮孤立點的情況下，只需要3次比較運算，0次乘法運算。比較運算需要1個時鐘周期，乘法運算需要10個時鐘周期^[5]。兩種算法復雜度的比較如表2所示。

表2 兩種算法復雜度的比較

細化算法比較運算次數乘法運算次數需時鐘周期數

文獻[8]算法10次8次90

改進算法3次0次3

從表2可知，改進后算法的復雜度要比改進前算法的復雜度降低很多倍。

3 實驗結果及分析

本文分別用傳統的Prewitt算法、未用自適應閾值算法、使用自適應閾值算法及對這三種情況進行細化的算法，對Lena圖像進行邊緣檢測實驗，實驗結果如圖4所示。為了節省文章篇幅，對實驗圖片縮小了尺寸，圖片尺寸較大時效果將會更明顯。



對于含有均值=0，標準方差σ=20的高斯白噪聲的Lena圖像重做上述實驗（其他參數不變），實驗結果如圖5所示。



通過對圖4的結果進行對比分析可知，在細化前三種算法的邊緣檢測效果相當，肉眼幾乎看不出它們的區別；細化以后，可以從各自的邊緣圖像中左邊白色柱子的邊緣部分看出三種算法具有明顯不同的效果，改進算法（包括使用和不使用自適應閾值兩種情況）要比傳統Prewitt算法所得圖像的該部分邊緣細膩光滑得多。文中使用自適應閾值和不使用自適應閾值算法所得圖像中該部分內容非常相似，這說明改進的邊緣檢測模板要比傳統Prewitt算子模板的效果稍微好一些；結合2.1節中的例子還說明改進的邊緣檢測模板是可行的，也是合理的。另外，原圖像中左側面部下方的邊緣，在傳統Prewitt算法和沒有使用自適應閾值算法所得圖像的這部分邊緣已經間斷不連續，而使用自適應閾值算法則是連續且光滑的。這說明定義的自適應閾值是合理的，也是有效的。圖4的結果說明了改進的Prewitt算子模板要比原Prewitt算子模板的效果好，也充分說明了文中提出的自適應閾值方法不但檢測到的邊緣更細膩光滑，且可以檢測到比較弱的邊緣，因而是可行的，也是有效的。

通過對圖5的結果進行對比分析可知，圖片右邊黑色帶子區及黑色帶子右下方的白色區域中，傳統Prewitt算法的結果圖片中噪聲點非常多，而改進的算法（包括使用和不使用自適應閾值兩種情況）噪聲點則少了許多，細化后這些噪聲點看得更清楚（圖片尺寸較大時效果更明顯）。另外細化后的邊緣圖像中左邊白色柱子的邊緣部分，在傳統Prewitt算法的結果中非常粗糙，對噪聲比較敏感，改進算法（包括使用和不使用自適應閾值兩種情況）的該部分邊緣要比傳統Prewitt算法細膩光滑得多，而使用自適應閾值方法又比不使用自適應閾值方法所得的該部分邊緣稍微光滑一些。這說明改進的Prewitt算子比傳統Prewitt算子具有更強的抑制噪聲的能力。在含有噪聲的情況下，原圖像中左側面部下方的邊緣，在傳統Prewitt算法和沒有使用自適應閾值算法所得圖像的這部分邊緣已經間斷不連續，而使用自適應閾值算法所得圖像的這部分邊緣則是連續且光滑的。

綜合比較圖4、5的結果，充分說明改進的Prewitt自適應閾值算法與傳統Prewitt算法相比具有更優良的性能。改進的Prewitt自適應邊緣檢測算法具有更強的抑制噪聲能力，從其算子模板的結構中可看出，傳統的Prewitt算子模板在與邊緣方向垂直的方向上的三個系數分別是1、-2、1。這一方面使待檢測點直接參與運算，另一方面又影響了邊緣方向的對稱性，故對噪聲敏感；而改進的算子模板對應的三個系數都為0，這一方面可以避免待檢測點參與運算，另一方面又保證了邊緣方向的對稱性。結合2.1節a）b)中具體例子的分析表明，改進的算子模板具有與原Prewitt算子相同的邊緣檢測能力，且抑制噪聲的能力更強；采用自適應閾值后，由于考慮到人眼的視覺特性，又可以進一步減少噪聲產生的影響且可以檢測到弱邊緣。對得到的圖像邊緣用文獻[8]中的細化算法進行細化，可得到單像素邊緣，其效果可以與文獻[9，10]中的效果相媲美。文中算法檢測到的邊緣用于圖像目標識別、目標定位以及用于文獻[11]中所說的檢驗圖像目標是否合格等特殊場合都是可以的。

4 結束語

經過對各種圖像進行實驗可知，本文結合人眼的視覺特性，提出的Prewitt自適應邊緣檢測算法普遍適用于各類圖像的邊緣提取，細化后又可得到單像素邊緣，且提高了抑制噪聲的能力、運算速度，還可以檢測到弱邊緣。本文也對文獻[8]中的細化算法進行了優化，提高了運算速度，也可根據具體的使用目的而決定是否進行細化。總之，本文提出的算法明顯比傳統的Prewitt算法好，更重要的是本算法結合人眼的視覺特性，能夠自適應地生成動態閾值來檢測圖像邊緣，自動化程度高，為實現自動匹配進行了有益的探索。另外，本文提出的自適應閾值方法也可以用于如Kirsch、Robert、Robinson等算法中也可以檢測到弱邊緣，也就是說本文提出的自適應閾值方法有一定的普遍性。

參考文獻：

[1]PREWITT J.Object enhancement and extraction[M]//LIPKIN B， ROSEENFELD A. Picture processing and psychohistories.New York:Academic Press，1970:75-149.

[2]李弼程，彭天強，彭波，等.智能圖像處理技術[M].北京：電子工業出版社，2004：149-173.

[3]何東健，耿楠，張義寬，等.數字圖像處理[M].西安：西安電子科技大學出版社，2003：95-97.

[4]沈美明，溫冬嬋.IBM-PC匯編語言程序設計[M].2版.北京：清華大學出版社，2001：435-481.

[5]王，王秋光.基于圖像邊緣信息的2維閾值分割方法 [J] .中國圖象圖形學報，2007，12(1)：78-81.

[6]冷寒冰，王先，劉上乾，等. 基于人眼視覺特性的鄰域自適應模糊增強算法[J]. 光電工程，2004，31（1）: 62-65.

[7]吳穎謙， 方濤， 李聰亮，等. 一種基于小波分析和人眼視覺特性的圖像增強方法[J].數據采集與處理，2003，18（1）:17-21.

[8]劉煜，李言俊，張科，等.一種多像素圖像邊緣提取方法[J] .光子學報，2007，36（2）：380-384.

[9]王植，賀賽先.一種基于Canny 理論的自適應邊緣檢測方法 [J] .中國圖象圖形學報，2004，9（8）：957-962.

[10]ZHANG Ren-yan， ZHAO Guo-ling， SU Li. A new edge detection method in image processing[C]//Proc of IEEE International Symposium on Communications and Information Technology. 2005:445- 448.

[11]左建中，尹輝，陳賢青，等.小波變換在螺紋邊緣檢測中的應用[J] .制造業自動化2007，29(1)：33-34.