邊緣檢測

邊緣檢測（Edge detection）是圖像處理和電腦視覺中的基本問題，邊緣檢測的目的是標識數字圖像中亮度變化明顯的點。圖像屬性中的顯著變化通常反映了屬性的重要事件和變化。這些包括（i）深度上的不連續、（ii）表面方向不連續、（iii）物質屬性變化和（iv）場景照明變化。

邊緣檢測是圖像處理和電腦視覺中，尤其是特徵檢測中的一個研究領域。

圖像邊緣檢測大幅度地減少了數據量，並且剔除了可以認為不相關的資訊，保留了圖像重要的結構屬性。有許多方法用於邊緣檢測，它們的絕大部分可以劃分為兩類：基於查找一類和基於零穿越的一類。基於查找的方法通過尋找圖像一階導數中的最大和最小值來檢測邊界，通常是將邊界定位在梯度最大的方向。基於零穿越的方法通過尋找圖像二階導數零穿越來尋找邊界，通常是Laplacian過零點或者非線性差分表示的過零點。

## 邊緣屬性

邊緣可能與視角有關——也就是說邊緣可能隨著視角不同而變化，典型地反映在場景、物體的幾何形狀一個將另一個遮擋起來，也可能與視角無關——這通常反映被觀察物體的屬性如表面紋理和表面形狀。在二維乃至更高維空間中，需要考慮透視投影的影響。

一個典型的邊界可能是（例如）一塊紅色和一塊黃色之間的邊界；與此相反的是邊線可能是在另外一種不變的背景上的少數不同顏色的點。在邊線的每一邊都有一個邊緣。在許多圖像處理的應用中邊緣都起著非常重要的作用。然而，在最近幾年，不明顯依賴於邊緣檢測作為預處理的電腦視覺處理方法研究取得了一些實質性（成功）的研究成果。

## 簡單邊緣模型

自然界圖像的邊緣並不總是理想的階梯邊緣。相反，它們通常受到一個或多個下面所列因素的影響：

- 有限場景深度帶來的聚焦模糊.
- 非零半徑光源產生的陰影帶來的半影模糊.
- 光滑物體邊緣的陰影.
- 物體邊緣附近的局部鏡面反射或者漫反射.

儘管下面的模型不很完美，但是誤差函數$\operatorname{erf}$還是常被用於實際應用中邊緣模糊效果的建模。

這樣，一個在位置$0$之邊界的一維圖像$f$可以用下面的模型來表示：

$$f(x) = \frac{I_r - I_l}{2} \left( \operatorname{erf}\left(\frac{x}{\sqrt{2}\sigma}\right) + 1\right) + I_l$$

這樣，在邊界的左側亮度是$I_l = \lim_{x \rightarrow -\infty} f(x)$，在右側亮度是$I_r = \lim_{x \rightarrow \infty} f(x)$；$\sigma$被稱為邊緣模糊度。

注意$f$可以寫為卷積$f = g_\sigma * u$，其中$g_\sigma$是標準偏差$\sigma$的高斯核，$u$是下面定義的一個階躍函數：

$$u(x) := \left\{ \begin{matrix} <pre> I_l, & \mathrm{if} \; x \leq 0\\ I_r, & \mathrm{otherwise} </pre> \end{matrix} \right.$$。

## 檢測邊緣不是一個簡單的問題

如果將邊緣認為是一定數量點亮度發生變化的地方，那麼邊緣檢測大體上就是計算這個亮度變化的導數。為簡化起見，我們可以先在一維空間分析邊緣檢測。在這個例子中，我們的數據是一行不同點亮度的數據。例如，在下面的1維數據中我們可以直觀地說在第4與第5個點之間有一個邊界：

5｜7｜6｜4｜152｜148｜149

除非場景中的物體非常簡單並且照明條件得到了很好的控制，否則確定一個用來判斷兩個相鄰點之間有多大的亮度變化才算是有邊界的閾值，並不是一件容易的事。實際上，這也是邊緣檢測不是一個簡單問題的原因之一。

## 邊緣檢測的方法

有許多用於邊緣檢測的方法，他們大致可分為兩類：基於搜索和基於零交叉.

基於搜索的邊緣檢測方法首先計算邊緣強度，通常用一階導數表示，例如梯度模;然後，用計算估計邊緣的局部方向，通常採用梯度的方向，並利用此方向找到局部梯度模的最大值.

基於零交叉的方法找到由圖像得到的二階導數的零交叉點來定位邊緣.通常用拉普拉斯算子或非線性微分方程的零交叉點，我們將在後面的小節中描述.

濾波做為邊緣檢測的預處理通常是必要的，通常採用高斯濾波.

已發表的邊緣檢測方法應用計算邊界強度的度量，這與平滑濾波有本質的不同.正如許多邊緣檢測方法依賴於圖像梯度的計算，他們用不同種類的濾波器來估計x-方向和y-方向的梯度.

### 計算一階導數

許多邊緣檢測操作都是基於亮度的一階導數——這樣就得到了原始數據亮度的梯度。使用這個資訊我們能夠在圖像的亮度梯度中搜尋峰值。

如果I（x）表示點x的亮度，I′（x）表示點x的一階導數（亮度梯度），這樣我們就會發現：

$$I'(x)=-1/2\cdot I(x-1) + 0 \cdot I(x) + 1/2 \cdot I(x+1).\,$$

對於更高性能的圖像處理來說，一階導數能夠通過帶有掩碼的原始數據（1維）卷積計算得到。

−1/2｜0｜1/2

### 計算二階導數

其它一些邊緣檢測操作是基於亮度的二階導數。這實質上是亮度梯度的變化率。在理想的連續變化情況下，在二階導數中檢測過零點將得到梯度中的局部最大值。另一方面，二階導數中的峰值檢測是邊線檢測，只要圖像操作使用一個合適的尺度表示。如上所述，邊線是雙重邊緣，這樣我們就可以在邊線的一邊看到一個亮度梯度，而在另一邊看到相反的梯度。這樣如果圖像中有邊線出現的話我們就能在亮度梯度上看到非常大的變化。為了找到這些邊線，我們可以在圖像亮度梯度的二階導數中尋找過零點。

如果I（x）表示點x的亮度，I′′（x）表示點x亮度的二階導數，那麼：

$$I''(x) = 1\cdot I(x-1) - 2 \cdot I(x) + 1 \cdot I(x+1).\,$$

同樣，許多演算法也使用卷積掩碼快速處理圖像數據：

+1｜−2｜+1

### 閾值確定

一旦我們計算出導數之後，下一步要做的就是給出一個閾值來確定哪裡是邊緣位置。閾值越低，能夠檢測出的邊線越多，結果也就越容易受到圖片雜訊的影響，並且越容易從圖像中挑出不相關的特性。與此相反，一個高的閾值將會遺失細的或者短的線段。

一個常用的這種方法是帶有滯後作用的閾值選擇。這個方法使用不同的閾值去尋找邊緣。首先使用一個閾值上限去尋找邊線開始的地方。一旦找到了一個開始點，我們在圖像上逐點跟蹤邊緣路徑，當大於門檻下限時一直紀錄邊緣位置，直到數值小於下限之後才停止紀錄。這種方法假設邊緣是連續的界線，並且我們能夠跟蹤前面所看到的邊緣的模糊部分，而不會將圖像中的雜訊點標記為邊緣。

## 邊緣檢測算子

- 一階：Roberts Cross算子, Prewitt算子, Sobel算子, Canny算子，羅盤算子
- 二階：Marr-Hildreth,在梯度方向的二階導數過零點。

目前，Canny算子（或者這個算子的變體）是最常用的邊緣檢測方法。

在Canny創造性的工作中，他研究了設計一個用於邊緣檢測最優預平滑濾波器中的問題，後來他說明這個濾波器能夠很好地被一階高斯導數核優化。另外Canny引入了非最大抑制概念，它是說邊緣定義為在梯度方向具有最大梯度值的點。

在一個離散矩陣中，非最大抑制階梯能夠通過一種方法來實現，首先預測一階導數方向、然後把它近似到45度的倍數、最後在預測的梯度方向比較梯度幅度。

一個獲得亞點精度邊緣的改進實現是通過檢測梯度方向上二階方向梯度的過零點來實現的：

$$L_x^2 \, L_{xx} + 2 \, L_x \, L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,$$ 它在梯度方向的三階方向梯度滿足符號條件

$$L_x^3 \, L_{xxx} + 3 \, L_x^2 \, L_y \, L_{xxy} + 3 \, L_x \, L_y^2 \, L_{xyy} + L_y^3 \, L_{yyy} < 0$$

其中，$L_x$, $L_y$ ... $L_{yyy}$表示從使用高斯核平滑原始圖像得到的尺度空間表示$L$計算出的偏微分。

按照這種方法，能夠自動得到亞點精度的連續曲線邊緣。

滯後門檻也可以用在這些差分邊緣片斷。

羅盤算子是史丹福大學的Ruzon在1999年提出的一個新的算子，據實驗以及報導，性能超過Canny算子。

## 參考文獻

### 來源

期刊文章

- (Includes the differential approach to non-maximum suppression.)

## 參見

- 霍夫變換（Hough Transform），用來做直線檢測.
- 原子線濾波器（atomic line filter），用來做直線檢測.