Cannyアルゴリズムとは？画像から輪郭を検出する原理と計算方法についてまとめました。
Cannyアルゴリズムとは
Cannyアルゴリズムは、画像の輪郭（エッジ）部分を検出するアルゴリズムです。
輪郭を検出する他の有名なアルゴリズムとしては「ソーベルフィルタ」「ラプラシアンフィルタ」などがありますが、それらと比較して細かい輪郭を検出でき、ノイズにも強いという優れた特徴があります。
以下の画像は、Cannyアルゴリズムで輪郭検出した結果です。
■入力画像（左）、出力画像（右）
「Cannyアルゴリズム」「ソーベルフィルタ」「ラプラシアンフィルタ」で作成した輪郭画像を目の部分を拡大して見比べると以下のようになります。
■Cannyアルゴリズム（左）、ラプラシアンフィルタ（中央）、ソーベルフィルタ（右）
ラプラシアンフィルタはノイズに弱いため、ごま塩ノイズが目立ちます。
Sobelフィルタはごま塩ノイズは見られないものの、細かい輪郭は検出できていないことがわかります。
Cannyアルゴリズムはごま塩ノイズが見られず、細かい輪郭も検出できていることがわかります。
ただし、次節で解説するように、Cannyアルゴリズムは複数のステップを踏んで処理を行うため計算コストが高く、パラメータの調整が必要という欠点もあります。
Cannyアルゴリズムの処理手順
Cannyアルゴリズムの処理手順は以下の通りです。
- Gaussianフィルタで画像を平滑化する。
- 平滑化された画像の微分を計算する。
- 微分画像から勾配の大きさと方向を計算する。
- Non maximum Suppression処理をする。(輪郭を細線化)
- Hysteresis Threshold処理をする。(輪郭の信頼性を評価し、輪郭でないと評価した部分を除去)
次節で各手順について詳しく解説します。
手順① ガウシアンフィルタで平滑化処理
ガウシアンフィルタは、画像の平滑化処理に用いられているフィルタです。
このフィルタは、処理をかける画素の周りの画素値とガウス分布の重み付けを利用することで自然な平滑化をおこなうことができます。
入力画像を$I$、ガウシアンフィルタのカーネルを$K_g$とすると、平滑化画像を$G$は次式で計算します。
$$G=I*K_g$$
*は畳み込み積分を表しています。
手順② 平滑化画像を微分
平滑化画像$G$をソーベルフィルタなどで微分します。
ソーベルフィルタの水平方向微分、および垂直方向微分のカーネルを$K_x, K_y$とします。
このとき、水平方向、及び垂直方向の微分画像 $G_x, G_y$ は次式で計算できます。
$$ G_x=G * K_x \\ G_y=G * K_y $$
手順③ 微分画像から勾配の大きさ・方向の計算
微分画像$G$から勾配の大きさ $|G|$ と方向 $\theta$ を次式で計算します。
$$ | G |=\sqrt{G_x^2+G_y^2}\\ \theta = tan^{-1}\frac{G_y}{G_x}=atan2(G_y, G_x) $$
手順④ Non maximum Suppression処理
Non maximum Suppression処理により、手順③で求めた微分画像の勾配の大きさ $|G|$ の輪郭を細線化します。
注目画素の画素値と、輪郭の勾配方向 $\theta$ に隣り合う2つの画素値を比較します。そして、3つの中で注目画素の画素値が最大でない場合、画素値を0(黒)に置き換えます。
$$ |G|(x,y) = \begin{cases} |G|(x,y) & \text{if } |G|(x,y) \geq |G|(x+d_x, y+d_y) \text{ and } |G|(x,y) \geq |G|(x-d_x, y-d_y) \\ 0 & \text{otherwise} \end{cases} $$
計算例1
単純な計算例として、以下のような$3\times 3$の微分画像の勾配の大きさ$|G|$について考えます。
$$ |G|=\begin{bmatrix} 100 & 100 & 100 \\ 0 & 100 & 0 \\ 100 & 100 & 100 \end{bmatrix} $$
注目画素$|G|(1,1)=100$の勾配方向$\theta$は「水平方向（$d_x=1, d_y=0$）」となります。（勾配方向=画素値の変化がある方向）
また、注目画素$|G|(1,1)$の水平方向に隣接する画素値は$|G|(0,1)=0, |G|(2,1)=0$です。したがって、注目画素と隣接する2つの画素の中で、最大の画素値をもつのは注目画素なので、画素値はそのままとします。
計算例2
単純な計算例として、以下のような$3\times 3$の微分画像の勾配の大きさ$|G|$について考えます。
$$ |G|=\begin{bmatrix} 10 & 10 & 10 \\ 20 & 10 & 50 \\ 10 & 10 & 10 \end{bmatrix} $$
注目画素 $|G|(1,1)=10$ の勾配方向 $\theta$ は「水平方向」となります。（勾配方向=画素値の変化がある方向）
また、注目画素 $|G|(1,1)$ の水平方向に隣接する画素値は $|G|(0,1)=20, |G|(2,1)=50$ です。したがって、注目画素と隣接する2つの画素の中で、最大の画素値をもつのは$|G|(2,1)$なので、注目画素の画素値は0とします。
$$ |G|=\begin{bmatrix} 10 & 10 & 10 \\ 20 & 0 & 50 \\ 10 & 10 & 10 \end{bmatrix} $$
手順⑤ Hysteresis Threshold処理
Hysteresis Threshold処理では、2つの閾値（最大閾値・最小閾値）で「信頼性の高い輪郭」と「信頼性の低い輪郭」を選びます。具体的には、手順④で生成した細線画像の画素値と2つの閾値から、次のように輪郭の信頼性を評価します。
| 画素値 | 評価 |
|---|---|
| 最小閾値より小さい | 信頼性の低い輪郭と評価して除去する。 |
| 最小閾値～最大閾値の間 | 信頼性の高い輪郭が隣にあれば信頼性の高い輪郭として残す。違えば信頼性の低い輪郭として除去する。 |
| 最大閾値より大きい | 信頼性の高い輪郭と評価して残す |
最小閾値 $t_{min}$ 、最大閾値 $t_{max}$ とのとき、上記を計算式で表すと以下のようになります。
$$ |G’|(x, y) = \begin{cases} 255 & \text{if } |G|(x, y) \geq t_{max} \\ 0 & \text{if } |G|(x, y) < t_{min} \\ 255 & \text{if } t_{min} \leq |G|(x, y) < t_{max} \text{ and any neighbour } \geq t_{max} \\ 0 & \text{otherwise} \end{cases} $$
仮に、最小閾値 $t_{min} = 75$ 、最大閾値 $t_{max}=150$ と設定した場合、画素値が以下の通りの場合、以下のようになります。
- 注目画素の値が160 → 信頼性の高い輪郭（255）
- 注目画素の値が50 → 信頼性の低い輪郭（0）
- 注目画素の値が100、近隣に160の画素が存在 → 信頼性の高い輪郭（255）
- 注目画素の値が100、近隣に信頼性の高い画素が存在しない → 信頼性の低い輪郭（0）
上記手順により、輪郭ではない部分(ノイズなど)を除去しながら、同時に途切れてしまっている輪郭を繋げることができます。
関連ページ
CannyアルゴリズムをPythonで実装する方法について以下ページで解説しています。
その他の画像処理アルゴリズムについては以下ページにまとめています。
コメント