單元六、邊緣偵測

陳慶瀚

2004-11-03

將影像切割成物件和背景是物件辨識和影像理解前的基本工作，這個工作主要的任務是找出物件的邊緣和線條。對人類視覺系統(human visual system)而言，這是一件輕而易舉的事，但在電腦視覺中，縱然是相當複雜的理論和演算法，都不容易模仿人類的這個行為能力。主要的困難來自以下問題：

─ 原始影像量化的誤差和感測的雜訊。此一因素導致偵測亮度變化但並非物件邊緣的區域，同時可能漏失一些物件邊緣但是沒有明顯亮度變化的區域；

─ 物件邊緣的正確位置會受到量化誤差和雜訊的影響而產生偏移；

─ 物件邊緣在影像中應表現出銳利的亮度變化，這就是它的高頻特性，所以任何想要降低影像雜訊的平滑濾波都會導致邊緣區域訊號的糊化(bluring)；

絕大多數的邊緣偵測方法都是採用微分的原理，因為微分會放大高頻訊號，但也會放大雜訊，因此平滑濾波總是需要的。平滑濾波的程度是根據濾波器的大小(size)和濾波的尺度(scale)，越大的尺度越能表現出大範圍的亮度變化，但也使得所偵測出來的邊緣位置精確度越差；較小的尺度雖能找出較為正確的位置，但又容易產多許多錯誤的邊緣點。不同影像的尺度影響也不相同，想要找出一個最佳的尺度適用在一張影像的全部邊緣是很困難的，想要找出一個最佳的尺度適用在所有影像更是不可能的事。

多尺度的邊緣偵測(multiscale edge detection)方法因此提供一個到目前為止最好的邊緣偵測方法。這種方法的核心概念是應用不同大小的平滑濾波器(例如高斯濾波器)與原始影像作迴旋積，得到不同scale的濾波影像，再對每一個scale的濾波影像抽取其邊緣，最後疊合所有scale的邊緣資訊為最終的邊緣影像。

 

1. Scale space濾波

尺度空間濾波是探討訊號(影像)隨尺度變化的濾波技術。

若有一維訊號f(x)以1-D高斯濾波器進行迴旋積濾波：

變化s，訊號f(x)在(x, s)平面上形成的圖形稱為scale--space image(尺度空間影像) F(x, s)：

F(x, s) = G(x, s)* f(x)

對於特定s0，曲線F(x, s0)的反曲點(inflection point)將滿足

 

將所有反曲點連線可作為一組(x, s)座標上的曲線，如下圖。s越小的方向表示scale較大的反曲點。

參考搜尋：IEEE Xplore關鍵字：scale space <and> edge

2. 邊緣(Edge)的特性

a. 階狀邊緣剖面；b. 平滑階狀邊緣剖面+white noise(a signal with a flat frequency spectrum); c.一階微分剖面；d.二階微分剖面；

a. 樓梯狀邊緣剖面；b.一階微分剖面呈現兩個maximum和一個minimum；d.二階微分剖面呈現三個zero-crossing；

3. Canny邊緣偵測

Canny, J.F., A computational approach

to edge detection. IEEE Trans Pattern Analysis and Machine Intelligence, 8(6): 679-698, Nov 1986.

 

Canny提出Edge Detection濾波器的評估準則：

1. 在平坦的影像區域沒有響應 => 濾波器係數和為零:

2. 等向性(Isotropy): 濾波器響應必須與edge方向無關。

3. 正確的edge偵測能力: 避免以下情形

─將雜訊誤判為edge，此為false positive

─未能找出真正edge，此為false negative

4. 好的定位(localization): 偵測的edge位置應儘可能接近真正edge位置

5. 單一響應(single response): 儘可能減少edge附近local maxima的數量。

Canny的邊緣偵測器原理：

1. 應用高斯濾波器在灰階影像f(x,y)，得到平滑影像g(x; y) = f(x; y) * wG(x; y; σ)

2. 應用微分濾波器▽g(x; y)計算邊緣強度(magnitude)和方向(orientation).

The scale parameter σ is selected based on

高斯濾波器參數σ決定邊緣偵測器的大小。決定適當σ應依下列需求：

─ 想要得到edge的細節程度(fine edges vs global edges);

─ 雜訊的多寡;

─ 偵測性定位/準確度trade off

Canny提出兩個方法來滿足邊緣偵測器單一響應和定位正確性的要求：

─ Non-maxima suppression

1. 對每一點C(x; y), 選定垂直於orientation方向兩個側邊的鄰近點，記作A和B；.

2. 如果M(A) > M(C) or M(B) > M(C), 則C不為edge(設定M(C(x,y))=0);

3. 輸出(edge)強度影像MNMS(x; y)

non-maxima suppression輸出仍會帶有一些非edge的local maxima，同時 connectivity性質不明顯的edge區域。Canny的Hysteresis thresholding方法提供了解決方案。

─ Hysteresis thresholding

1. 定義兩個thresholds, Thigh and Tlow，

像素(x; y) 如果MNMS (x; y) > Thigh，該像素就稱為strong，

像素(x; y) 如果MNMS (x; y)≦Tlow，該像素就稱為weak，

所有其他的像素稱為candidate；

2. 如果像素(x; y)是weak，則略去；如果是strong，則輸出為edge像素；

3. 如果像素(x; y)是candidate，而且MNMS > Tlow，則判斷是否沿著local maxima相連的edge方向有穿過(x,y)，若是，則輸出為edge；

4. 如果candidate像素(x; y)與一strong像素，則輸出該candidate為edge。

  • hysteresis thresholding的進一步說明：
    • If any edge response is above a high threshold, those pixels constitute definite output of the edge detector for a particular scale.
    • Individual weak responses usually correspond to noise.
    • Such connected pixels are treated as edge pixels if their response is above a low threshold.
    • The low and high thresholds are set according to an estimated signal to noise ratio.

Canny邊緣偵測器與scale space

n         The correct scale for the operator depends on the objects contained in the image.

n         The solution to this unknown is to use multiple scales and aggregate information from them.

n         Different scale for the Canny detector is represented by different standard deviationsσof the Gaussians.

n         There may be several scales of operators that give significant responses to edges (i.e., signal to noise ratio above the threshold); in this case the operator with the smallest scale is chosen as it gives the best localization of the edge.

Canny邊緣偵測濾波演算法：

  1. 變化σ重複步驟(2)到(6)；
  2. 以scale σ的高斯濾波器對image g執行迴旋積；

3.     估測每一像素的區域邊緣的正交方向n

4.     應用non-maximal suppression方法找出edges位置；

  1. 計算edges強度MNMS (x; y)
  2. 應用hysteresis thresholding消除edge毛邊，並接續edge斷點；
  3. 累積多重scale σ的edge資訊，合成最後的edge影像。

 

邊緣偵測作為一個設計最佳化的問題，其評估函數為：

1. Maximize the signal to noise ratio to give good detection. This favours the marking of true positives.

2. Achieve good localization to accurately mark edges.

3. Minimize the number of responses to a single edge. This favours the identification of true negatives, that is, non-edges are not marked.

 

Canny邊緣偵測器程式碼下載

 

本週習題：

1. 使用Canny邊緣偵測器，選定一組適當的 Thigh and Tlow，再分別以s=0.5, 1.0, 2.0, 3.0，求得ant(gray)600x400影像4個scale的edge影像，將其合成為一張最終的edge影像(不一定使用重疊相加(OR)的方式)。

2. 取出原始影像的其中一條水平profile，使用相同程式，求得如第一節所陳述的尺度空間影像。

線偵測(Line Detection)問題

線型態(line pattern)不同於邊緣型態(edge pattern)的特徵，在影像中，線型態經常表現在一些寬度很窄的valley/ridge紋路樣式或是手寫文字、繪圖影像中。如果它具有某種寬度，則藉由標準邊緣偵測方法常會找出兩條平行的線條，這是因為大部分的邊緣偵測方法都建立在階狀函數(step edge)的基礎。不同於edge總是位於二階微分的zero-crossing位置，line則於一階微分的zero-crossing的位置。

Steger提出使用Gaussian和一次微分的濾波方法作為線偵測器(cf. C. Steger : An unbiased Detector of Curvilinear Structure, IEEE Transaction on PAMI, 20(2), 1998); Ziou(Djemel Ziou : Optimal Line detection, 2000)則採用Canny的邊緣偵測評估準則，提出以IIR濾波器來偵測線特徵。

3. 請使用第五單元的Robinson一階導數濾波器求出finger300x300指紋影像的amplitude和orientation影像，(A)利用amplitude影像找出zero-crossing的像素後輸出zero-crossing影像(黑白影像)。(B)利用orientation影像資訊，畫出每一個zero-crossing位置的方向圖如下圖(b)；

         

(a)                          (b)

(C)應用Canny的non-maximal suppression和hysteresis thresholding方法作為線偵測後處理，輸出最後的line image。