1 概要
Cannyエッジ検出器 (Canny Edge Detector) とは，コンピュータビジョンで用いられる古典的な画像エッジ特徴の検出アルゴリズムである [Canny 1986]．微分フィルタを用いるだけの単純なエッジ検出と異なり，一筋に連なっった１画素幅のエッジ群を抽出できる．
この記事では，Cannyエッジ検出器の発想とアルゴリズムについて，簡潔に紹介したい．
CannyEdge検出器の利点は，抽出されたエッジは物体境界を含んでいることが多く，その後の高次な認式処理に用いやすいエッジ特徴になっているところにある．それまでは，SobelフィルタやPrewittフィルタで抽出していた生なエッジと比べると，Cannyエッジ検出器は綺麗に連なっていて１画素幅のエッジを抽出できる．
その後に，機械学習ベースのバウンダリー検出手法に取ってかわられるまで(例：probability boundary detector [Martin et al., 2004]] など)，エッジ特徴抽出のファーストチョイスとしてCannyエッジ検出器は重宝された．
2 Canny Edge Detector のアルゴリズム概要
(画像フィルタリングだけではない)発展的なエッジ検出のアルゴリズムの基本は，「勾配画像の利用」である．勾配画像の計算を通じて，以下の２つの情報をエッジ抽出に活用するのが基本的方針である：
- 勾配の大きさ(magnitude of gradient):
- 勾配が大きい画素ほど，大きな明暗差・落差があってエッジらしさが強い．
- 勾配の方向(orientation of gradient):
- 勾配は境界線なので，そのエッジ画素の垂直方向（エッジ線の局所法線方向）を示している．
この2つの情報を有効活用するアルゴリズムであるCannyエッジ検出器は，以下の2つのステージの処理を順に実行する構成である：
- ステージ1「エッジ方向ごとの細線化」：
- 勾配の強度(図1-b)と勾配の方向をもとに，法線方向でのNMS(非極大値抑制)(局所範囲での最大値)をおこなう
- それにより，幅が広い状態であったエッジを，1画素幅へ細線化(thinning)した「エッジ候補」群を計算する．
- ステージ2「ヒステリシス閾値処理」：
- ユーザーが設定した2個の閾値を用いて，ステージ1の出力の「エッジ候補」を，「弱エッジ(エッジとしての信頼度低い)」と「強エッジ(エッジとしての信頼度高い)」と「それ以外」に3分類する(図1-c)．
- そして「弱エッジ」のうち，周りに強エッジがあるものだけ，連結成分処理により「強エッジ」に連結して吸収させる(図1-d)．これにより，最終的なエッジを得る．
次の3節では，これら5つの処理の具体的な内容を，各節で順にみていく．
3. 各ステージの処理
Cannyエッジ検出器では，以下の各処理を順に行うことで，2ステージの処理によりエッジ検出を行うことができる：
- 3.1 平滑化 (ノイズ削減目的の前処理)
- 3.2 画像勾配の計算
- 3.3 勾配の強度・回転を計算．
- 3.4 (ステージ1の処理)「勾配方向上のNMS(非極大値抑制)」によるエッジ細線化
- 3.5 (ステージ2の処理)ヒステリシス閾値処理
入力画像を，グレー画像 $\bm{I} \in \mathbb{R}^{ h \times y}$ とする．出力のエッジ画像に向けて，以下の処理を順番に実行していく．
3.1 平滑化
ノイズに弱い画像フィルタリングによる勾配計算をおこなうので，その前処理としてノイズを減らしておくためにまず，元画像 $\bm{s}$ をガウシアンフィルタで平滑化した $\bm{G}$ を計算する．
3.2 画像勾配の計算
平滑化した $\bm{G}$ から，Sobelフィルタを用いて，x方向の微分画像 $\bm{G}_x$ とy方向の微分画像 $\bm{G}_y$ を計算する．
3.3 勾配の強度・方向を計算
次の処理4の準備として「勾配の大きさ(magnitude of gradient)」の画像 $\bm{M}$ と，「勾配の方向(orientation of gradient)」の画像 $\bm{O}$ を，それぞれ $\bm{G}_x$，$\bm{G}_y$ から計算する:
\begin{align}
\bm{M}(i,j) &= \sqrt{\bm{G}_x(i,j)^2 + \bm{G}_y(i,j)^2}\\
\bm{O}(i,j) &= \tan^{(-1)} \frac{\bm{G}_y(i,j)}{\bm{G}_x(i,j)}
\end{align}
勾配 $\bm{O}(x,y)$ は，元画像上のエッジに対して常に直行し，法線方向を示す．
3.4 「勾配方向上の非極大値抑制」によるエッジ細線化 (ステージ1)
この時点では，フィルタリングで勾配(ラフなエッジ)画像を計算しただけなので，それらのエッジは幅が大きい「稜線(ridge)」状態のものが多い．しかし，実際に主力として欲しいのは，幅の太いエッジのうち，その中心を通る点をつないだ細いエッジである．よって，ラフなエッジを縮ませて1画素幅に細線化して，ステージ2の入力である「エッジ候補」を抽出したい．
そこで「勾配方向上のNMS(Non-maximal suppression, 非極大値抑制)」をおこなう．具体的には，勾配方向(=エッジの法線方向)の狭めの範囲内で，勾配が $\bm{M}(i,j)$ 最大値になる座標を探し，局所範囲内のその座標以外の座標は全てエッジ破棄する処理を行う．
勾配方向に沿った画素へのアクセスを簡単化するために，勾配の方向 $\bm{O}(x,y)$ を，4方向 $\{0^{\circ}, 45^{\circ}, 90^{\circ} , 135^{\circ}\}$ に離散化する (より正確に行いたい場合は，連続値のまま内挿したサブピクセル位置で補間したMagnitude値で，極大値探索をおこなう)．
そして勾配画像 $\bm{M}$ の各座標 $(i,j)$ において，4つの該当する勾配方向上の狭い直線範囲内のうち，$\bm{M}(i,j)$ が最大値である座標のみを「エッジ候補」の座標として残す．一方，他の画素は全てエッジから破棄する．こうしてNMS 処理が完了し，エッジ方向に沿った勾配値が1画素幅の「エッジ候補」のみが，抽出される．
ここまでの 3.1~3.4節の処理により，ステージ1の「エッジ画像を細線化」が終わる．
3.5 ヒステリシス閾値処理 (ステージ2)
細線化されたエッジ群は，各エッジがバラバラの位置にバラバラの強度の塊として，断片的に表出している(図1-c)．それらの各エッジの塊のうち，強度が高い強エッジの塊は信頼できるゆえ，そのまま最終結果として出力する．一方，信頼度が低い弱エッジも強エッジに接続させることで，最終結果である「長く連なったエッジ」を合成したい．
そこで，勾配の強度値を2の閾値$\lambda_{\text{low}}, \lambda_{\text{high}}$をヒステリシス(調節範囲の境界値)として用いて，0-255の輝度値を3分割するヒステリシス閾値処理(Hysteresis Thresholding)を行う：
- まず，エッジ強度画像の各画素を「弱エッジ( $\leq \lambda_{\text{low}} \leq \bm{I}(x,y) \leq \lambda_{\text{high}}$ ) 」と「強エッジ($\lambda_{\text{high}} < \bm{I}(x,y) \leq 255$)」に分類して抽出する．
- 次に，「弱エッジ領域」のうち，近傍画素が強エッジになっている場合のみ，連結成分処理により，強エッジ領域に結合する(一方，短すぎる「弱エッジ」は，長さが足りなくてノイズとみなして全て破棄して連結しない）
- 各画素において，手順2の連結成分処理を，離散化した近傍4方向に対してそれぞれ行う．
処理が終了すると，最終出力の「長いエッジ」(図1-d) を得ることができる．以上でCannyエッジ検出器の処理は終了である．
４. まとめ
この記事ではCanny エッジ検出器についてアルゴリズムを紹介した：
- 勾配の強度と回転方向をもとに，各位置で法線方向にNMS処理をおこなうことで，細線化した候補エッジを抽出する．
- 2つの閾値を用いて候補エッジを3分類する（破棄するエッジ未満のもの < 閾値1 < 弱エッジ < 閾値2 < 強エッジ）．
- 強エッジに隣接している弱エッジのみを強エッジに連結することで，最終的な「長いエッジ」が作成できる．
昨今は画像からいきなりCNNに入力して，特徴(ベクトル)抽出はCNNが担当するが，かつてのコンピュータビジョンや画像処理では，Cannyエッジ検出器などで抽出したエッジ特徴画像をもとにパターン認識することが多かったので，Cannyエッジ検出はとても重要な前処理であった．
参考書籍
- Computer vision: models, learning, and inference, Prince, Simon JD., Cambridge University Press, 2012.
- ディジタル画像処理 [改訂第二版], ディジタル画像処理編集委員会, 2020.
- Concise Computer Vision: An Introduction into Theory and Algorithms (Undergraduate Topics in Computer Science) , Reinhard Klette, 2014.
References
- [Canny 1986] Canny, J. (1986). A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6), 679–698.
- [Martin et al., 2004] Martin, D. R., Fowlkes, C. C., & Malik, J. (2004). Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE transactions on pattern analysis and machine intelligence, 26(5), 530-549.