影象處理：邊緣檢測
引言
在對影象的處理中，我們常常需要識別影象中的邊緣：列如在自動化駕駛中，需要對道路的邊線進行識別檢測；在特徵提取的時候，我們也需要識別出特定物體的邊緣，方便後續進行特徵提取。邊緣檢測是影象處理中的重要一環，本篇文章將圍繞邊緣檢測進行討論。
1、邊緣檢測的原理
影象的邊緣也就是影象中畫素灰度值發生變化的畫素點的集合。對於一幅影象，如果我們將影象畫素的每一行和每一列的灰度值都描述成一個函式（圖1），那麼就可以通過計算函式導數的方式來找到灰度值發生變化的點。導數值大，則說明灰度值變化大；導數值等於0，則說明灰度值沒有發生變化；導數值小，則說明灰度值變化小。影象邊緣也就是對應著灰度函式影象中函式值發生突然改變的區域（點的集合）。
圖1：將影象中的一行畫素的灰度值描述成一個函式
可能讀者會注意到：上文提到的導數——也就是影象的梯度——是微分中的概念，而微分針對於連續可導的函式，但我們的畫素灰度值實際上只是一個離散的函式，因此對應著差分。微分和差分的核心思想一致，我們在邊緣檢測的過程中，會運用微分的思想來進行指導，但在實際操作中，我們會用差分的方式來實現邊緣檢測。
導數（梯度）的表示式：
$$
\frac{∂f(x,y)}{∂x}=\lim_{\epsilon \to 0}\frac{f(x+\epsilon,y)-f(x,y)}{\epsilon}
\
\frac{∂f(x,y)}{∂y}=\lim_{\epsilon \to 0}\frac{f(x,y+\epsilon)-f(x,y)}{\epsilon}.\tag{1}
$$
將微分導數的概念引入到影象處理，$x$代表畫素點的位置（只考慮一個方向，$y$方向同理），那麼當前畫素沿$x$軸的灰度梯度值就等於後一個畫素的灰度值減去當前畫素的灰度值（前向差分）：
$$
\frac{∂f}{∂x}=f'(x)=f(x+1)-f(x).\tag{2}
$$
反向差分：
$$
\frac{∂f}{∂x}=f'(x)=f(x)-f(x-1).\tag{3}
$$
中心差分：
$$
\frac{∂f}{∂x}=f'(x)=\frac{f(x+1)-f(x-1)}{2}.\tag{4}
$$
二階導數是一階導數的導數，描述一階導數的變化趨勢，因此，我們可以根據一階導數推出：
$$
\frac{∂^2f(x)}{∂x^2}=f''(x)=f(x+1)-f(x)-[f(x)-f(x-1)]\
\quad\quad\quad\quad\,\,=f(x+1)+f(x-1)-2f(x).\tag{5}
$$
計算影象中每個畫素灰度的一階導數和二階導數的方法是影象卷積。給定圖2中的3x3運算元來說，其影象卷積的過程就是計算運算元係數與核覆蓋區域的灰度值的乘積之和。（注：波器、掩膜、掩碼、核、卷積核、模板、視窗、運算元等，其實都是一個東西，在不同的領域叫法不同。在訊號領域稱為濾波器，在數學裡稱為核、運算元，在影象處理領域稱為掩膜、掩碼，在深度學習領域稱為卷積核，在本文中我們統一稱為運算元）
圖2：3x3的運算元
也就是說對應運算元中心點的梯度值為： $$ Z=w_1z_1+w_2z_2+…+w_9z_9=\sum_{k=1}^{9}w_kz_k.\tag{6} $$ $w_k$是對應的係數，$z_k$為畫素點的灰度值。
2、運算元分類
運算元就是邊緣檢測的核心，在進行邊緣檢測的時候，我們常常會根據實際情況選擇合理的運算元來進行邊緣檢測，接下來我們將深入討論各類運算元。
2.1、Roberts交叉運算元
以對角差分為例，即Robert交叉運算元，它可以描述為使用兩個2x2的卷積模板對影像進行處理： $$ G_x = \begin{bmatrix} 1 & 0\ 0 & -1 \end{bmatrix} * f\quad\quad\quad\quad G_y = \begin{bmatrix} 0 & 1\ -1 & 0 \end{bmatrix} * f.\tag{7} $$ 由公式7展開： $$ g_x=\frac{∂f}{∂x}=f(x+1,y+1)-f(x,y)\ g_y=\frac{∂f}{∂y}=f(x+1,y)-f(x,y+1).\tag{8} $$ 運算元模板（圖3）：
圖3：Roberts交叉運算元模板
2.2、Prewitt運算元
Prewitt運算元是一種一階微分運算元的邊緣檢測，利用畫素點上下、左右鄰點的灰度差，在邊緣處達到極值檢測邊緣，去掉部分偽邊緣，對噪聲具有平滑作用 。其原理是在影象空間利用兩個方向模板與影象進行鄰域卷積來完成的，這兩個方向模板一個檢測水平邊緣，一個檢測垂直邊緣。
prewitt運算元定義：
$$
G_x =
\begin{bmatrix}
-1 & -1 & -1\
0 & 0 & 0\
1 & 1 & 1
\end{bmatrix} * f
\quad\quad\quad\quad
G_y =
\begin{bmatrix}
-1 & 0 & 1\
-1 & 0 & 1\
-1 & 0 & 1
\end{bmatrix} * f
.\tag{7}
$$
水平方向的梯度： $$ g_x=\frac{∂f}{∂x}=(z_7+z_8+z_9)-(z_1+z_2+z_3).\tag{8} $$ 垂直方向的梯度： $$ g_y=\frac{∂f}{∂y}=(z_3+z_6+z_9)-(z_1+z_4+z_7).\tag{9} $$ 對角線方向的梯度： $$ g_x=(z_2+z_3+z_6)-(z_4+z_7+z_8)\ g_y=(z_6+z_8+z_9)-(z_1+z_2+z_4).\tag{10} $$ Prewitt運算元的模板：
圖4：Prewitt運算元模板
2.3、Sobel運算元
Sobel運算元是在Prewitt運算元的基礎上改進而來：在中心繫數上使用一個權值2，相比較Prewitt運算元，Sobel運算元能夠較好地抑制（平滑）噪聲。Sobel運算元的定義： $$ S_x= \begin{bmatrix} 1 & 0 & -1\ 2 & 0 & -2\ 1 & 0 & -1 \end{bmatrix} * f \quad\quad\quad\quad S_y= \begin{bmatrix} 1 & 2 & 1\ 0 & 0 & 0\ -1 & -2 & -1 \end{bmatrix} * f .\tag{11} $$ 水平梯度： $$ g_x=\frac{∂f}{∂x}=(z_7+z_8+z_9)-(z_1+z_2+z_3).\tag{12} $$ 垂直梯度： $$ g_y=\frac{∂f}{∂y}=(z_3+z_6+z_9)-(z_1+z_4+z_7).\tag{13} $$ Robel運算元的模板：
圖5：Robel運算元模板
2.4、Laplacian運算元
拉普拉斯運算元（Laplacian Operator）是歐氏空間中的一個二階微分運算元。如果$f$是二維空間的二階可微的實函式，則$f$的拉普拉斯運算元定義為： $$ Δf=\nabla\,^2f=\frac{\partial\,^2f}{\partial\,x^2}+\frac{\partial\,^2f}{\partial\,y^2}.\tag{14} $$ 將上面的微分轉換為差分形式： $$ Δf=[f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)]-4f(x,y).\tag{15} $$
運算元模板： $$ \begin{bmatrix} 0 & 1 & 0\ 1 & -4 & 1\ 0 & 1 & 0 \end{bmatrix} \quad\quad\quad\quad \begin{bmatrix} 1 & 1 & 1\ 1 & -8 & 1\ 1 & 1 & 1 \end{bmatrix} $$
2.5、各類運算元的效果比對
圖6：運算元效果對比
3、Canny邊緣檢測演算法
Canny邊緣檢測於1986年由JOHN CANNY首次提出。Canny發現，在不同視覺系統上對邊緣檢測的要求較為類似，因此，可以實現一種具有廣泛應用意義的邊緣檢測技術。Canny邊緣檢測不是一種運算元，而是基於各類運算元基礎上的一套邊緣檢測的演算法。Canny邊緣檢測演算法可以分為以下5個步驟：
1、使用高斯濾波器，平滑影象，濾除噪聲： $$ G(x,y)=e^{\frac{x^2+y^2}{2\sigma}}\ f_s(x,y)=G(x,y)\otimes\,f(x,y).\tag{16} $$ 2、計算影象中每個畫素點的梯度強度和方向： $$ g_x=\frac{\partial\,f_s}{\partial\,x} \quad\quad\quad\quad g_y=\frac{\partial\,f_s}{\partial\,y}\ M(x,y)=\sqrt{g^2_x+g^2_y} \quad\quad\quad\quad \alpha(x,y)=tan^{-1}[\frac{g_y}{g_x}] .\tag{17} $$ 其中M(x,y)為梯度強度，α(x,y)為梯度方向。
3、應用非極大值抑制，消除邊緣檢測帶來的雜散響應：
（1）將當前畫素的梯度強度與沿正負方向上的兩個畫素進行比較；
（3）如果當前畫素的梯度強度與另外兩個畫素相比最大，則該畫素點保留為邊緣點，否則該畫素點將被抑制。
非極大值抑制是一種邊緣稀疏技術，主要作用在於"廋邊"。
4、應用雙閾值檢測來確定真實的和潛在的邊緣：
在施加非極大值抑制之後，剩餘的畫素可以更準確地表示影象中的實際邊緣。然而，仍然存在由於噪聲和顏色變化引起的一些邊 緣畫素。用弱梯度值過濾邊緣畫素，並保留具有高梯度值的邊緣畫素。如果邊緣畫素的梯度值高於高閾值，則將其標記為強邊緣像 素；如果邊緣畫素的梯度值小於高閾值並且大於低閾值，則將其標記為弱邊緣畫素；如果邊緣畫素的梯度值小於低閾值，則會被抑 制。
5、連線分析，抑制孤立的弱邊緣：
被劃分為強邊緣的畫素點已經被確定為邊緣，因為它們是從影象中的真實邊緣中提取出來的。對於弱邊緣畫素，可以從真實邊緣 提取也可以是因噪聲或顏色變化引起的。通常，真實邊緣引起的弱邊緣畫素能夠連線到強邊緣畫素，而噪聲響應無法連線。為了進行 邊緣連線分析，我們可以通過檢視弱邊緣畫素及其8個鄰域畫素，只要其中一個為強邊緣畫素，則該弱邊緣點就保留為真實的邊緣。
參考文獻
2、數字影象處理（第四版）Digital Image Processing，Fourth Edition (Rafael C.Gonzalez, Richard E.Woods) (z-lib.org)—10章影象分割