キャニーエッジ検出器

Cannyエッジ検出器は、多段階アルゴリズムを使用して画像内のさまざまなエッジを検出するエッジ検出演算子です。これは 1986 年にJohn F. Cannyによって開発されました。Canny は、この手法が機能する理由を説明するエッジ検出の計算理論も作成しました。

Canny エッジ検出は、さまざまな視覚オブジェクトから有用な構造情報を抽出し、処理するデータの量を大幅に削減する技術です。さまざまなコンピューター ビジョンシステムに広く適用されています。Canny は、さまざまなビジョン システムでのエッジ検出の適用要件が比較的似ていることを発見しました。したがって、これらの要件に対応するエッジ検出ソリューションは、さまざまな状況で実装できます。エッジ検出の一般的な基準は次のとおりです。

1. 低いエラー率でエッジを検出します。つまり、検出は画像に表示されるエッジをできるだけ正確に捉える必要があります。
2. オペレータから検出されたエッジ ポイントは、エッジの中心に正確に位置付けられる必要があります。
3. 画像内の特定のエッジは 1 回だけマークする必要があり、可能な場合は、画像ノイズによって誤ったエッジが作成されないようにする必要があります。

これらの要件を満たすために、キャニーは変分法を使用しました。これは、与えられた関数を最適化する関数を見つける手法です。キャニーの検出器における最適関数は、4 つの指数項の合計で記述されますが、ガウス分布の1次導関数で近似できます。

これまでに開発されたエッジ検出方法の中で、Canny エッジ検出アルゴリズムは、優れた信頼性の高い検出を提供する最も厳密に定義された方法の 1 つです。エッジ検出の 3 つの基準を満たす最適性と実装プロセスの単純さにより、このアルゴリズムはエッジ検出の最も人気のあるアルゴリズムの 1 つになりました。

Canny エッジ検出アルゴリズムのプロセスは、次の 5 つのステップに分けられます。

1. ノイズを除去するためにガウスフィルタを適用して画像を滑らかにします
2. 画像の強度勾配を見つける
3. エッジ検出に対する誤った応答を取り除くために、勾配振幅閾値または下限カットオフ抑制を適用する
4. 潜在的なエッジを決定するために二重しきい値を適用する
5. ヒステリシスによるエッジの追跡: 弱いエッジや強いエッジに接続されていない他のすべてのエッジを抑制して、エッジの検出を完了します。

すべてのエッジ検出結果は画像内のノイズの影響を受けやすいため、ノイズによる誤検出を防ぐためにノイズを除去することが重要です。画像を滑らかにするには、ガウス フィルター カーネルを画像に畳み込みます。この手順により、画像がわずかに滑らかになり、エッジ検出器に対する明らかなノイズの影響が軽減されます。サイズ (2 k +1)×(2 k +1) のガウス フィルター カーネルの式は、次のようになります。

${\displaystyle H_{ij}={\frac {1}{2\pi \sigma ^{2}}}\exp \left(-{\frac {(i-(k+1))^{2}+(j-(k+1))^{2}}{2\sigma ^{2}}}\right);1\leq i,j\leq (2k+1)}$

以下は、 = 2 の隣接画像を作成するために使用される 5×5 ガウス フィルターの例です。(アスタリスクは畳み込み演算を示します。) ${\displaystyle \sigma}$

${\displaystyle \mathbf {B} ={\frac {1}{159}}{\begin{bmatrix}2&4&5&4&2\\4&9&12&9&4\\5&12&15&12&5\\4&9&12&9&4\\2&4&5&4&2\end{bmatrix}}*\mathbf {A} .}$

ガウス カーネルのサイズの選択は検出器のパフォーマンスに影響することを理解することが重要です。サイズが大きいほど、検出器のノイズに対する感度は低くなります。さらに、ガウス フィルター カーネルのサイズが大きくなると、エッジを検出するための位置特定エラーがわずかに増加します。ほとんどの場合、5×5 が適切なサイズですが、特定の状況によっても異なります。

画像のエッジはさまざまな方向を向いている可能性があるため、Canny アルゴリズムでは 4 つのフィルターを使用して、ぼやけた画像の水平、垂直、対角のエッジを検出します。エッジ検出演算子( Roberts、Prewitt、Sobelなど) は、水平方向 (G _x ) と垂直方向 (G _y )の 1 次導関数の値を返します。これにより、エッジの勾配と方向を判断できます。

${\displaystyle \mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^{2}}}}$

${\displaystyle \mathbf {\Theta } =\operatorname {atan2} \left(\mathbf {G} _{y},\mathbf {G} _{x}\right)}$、

ここで、G はhypot関数を使用して計算でき、 atan2 は2 つの引数を持つ逆正接関数です。エッジ方向の角度は、垂直、水平、および 2 つの対角線 (0°、45°、90°、および 135°) を表す 4 つの角度のいずれかに丸められます。各色領域に該当するエッジ方向は、特定の角度値に設定されます。たとえば、[0°、22.5°] または [157.5°、180°] の θ は 0° にマップされます。

勾配の大きさの最小カットオフ抑制、または下限しきい値設定は、エッジを細くする手法です。

下限カットオフ抑制は、強度値の変化が最も急激な場所を見つけるために適用されます。グラデーション画像の各ピクセルのアルゴリズムは次のとおりです。

1. 現在のピクセルのエッジ強度を、正のグラデーション方向と負のグラデーション方向のピクセルのエッジ強度と比較します。
2. 現在のピクセルのエッジ強度が、マスク内の同じ方向の他のピクセルと比較して最大である場合 (たとえば、y 方向を指しているピクセルは、垂直軸でその上下のピクセルと比較されます)、値は保持されます。それ以外の場合、値は抑制されます。

いくつかの実装では、アルゴリズムは連続勾配方向を離散方向の小さなセットに分類し、前のステップの出力（つまり、エッジ強度と勾配方向）に 3x3 フィルターを移動します。すべてのピクセルで、中心ピクセルのエッジ強度が勾配方向の 2 つの隣接ピクセルの強度より大きくない場合は、その値を 0 に設定して中心ピクセルのエッジ強度を抑制します。たとえば、

• 丸められた勾配角度が0°（つまり、エッジが南北方向にある）の場合、その点の勾配の大きさが東西方向のピクセルの大きさより大きい場合、その点はエッジ上にあるとみなされます。
• 丸められた勾配角度が90°（つまり、エッジが東西方向にある）の場合、その点の勾配の大きさが北方向と南方向のピクセルの大きさより大きい場合、その点はエッジ上にあるとみなされます。
• 丸められた勾配角度が135°（つまり、エッジが北東から南西の方向にある）の場合、その点の勾配の大きさが北西と南東の方向のピクセルの大きさより大きい場合、その点はエッジ上にあるとみなされます。
• 丸められたグラデーション角度が 45° の場合 (つまり、エッジが北西から南東の方向にある場合)、ポイントのグラデーションの大きさが北東方向と南西方向のピクセルの大きさよりも大きい場合、ポイントはエッジ上にあると見なされます。

より正確な実装では、グラデーションの方向をまたぐ 2 つの隣接するピクセル間で線形補間が使用されます。たとえば、グラデーションの角度が 89° から 180° の間である場合、北と北東のピクセルのグラデーション間の補間によって 1 つの補間値が得られ、南と南西のピクセル間の補間によってもう 1 つの補間値が得られます (最後の段落の規則を使用)。中央のピクセルのグラデーションの大きさは、エッジとしてマークされるには、これら両方よりも大きくなければなりません。

方向の符号は無関係であることに注意してください。つまり、南北は南北と同じになります。

非最大抑制を適用した後、残りのエッジ ピクセルは、画像内の実際のエッジをより正確に表現します。ただし、ノイズや色の変化によって生じたエッジ ピクセルがいくつか残ります。これらの誤った応答を考慮するには、弱い勾配値を持つエッジ ピクセルをフィルター処理し、高い勾配値を持つエッジ ピクセルを保持することが重要です。これは、高いしきい値と低いしきい値を選択することで実現されます。エッジ ピクセルの勾配値が高しきい値よりも高い場合、強いエッジ ピクセルとしてマークされます。エッジ ピクセルの勾配値が高しきい値よりも小さく、低しきい値よりも大きい場合、弱いエッジ ピクセルとしてマークされます。エッジ ピクセルの勾配値が低しきい値よりも小さい場合、抑制されます。2 つのしきい値は経験的に決定され、その定義は特定の入力画像の内容によって異なります。

強いエッジ ピクセルは最終的なエッジ画像に確実に含まれるはずで、画像内の真のエッジから来ているものと見なされます。ただし、弱いエッジ ピクセルについては議論の余地があります。これらのピクセルが真のエッジから来ているのか、ノイズ/色の変化から来ているのかを判別する必要があります。後者の場合、弱いエッジ ピクセルは考慮から除外する必要があります。このアルゴリズムは、真のエッジからの弱いエッジ ピクセルは (通常) 強いエッジ ピクセルに接続され、ノイズ応答は接続されていないという考えに基づいています。エッジ接続を追跡するために、弱いエッジ ピクセルとその 8 つの接続された近傍ピクセルを調べるブロブ分析が適用されます。ブロブに含まれる強いエッジ ピクセルが 1 つある限り、その弱いエッジ ポイントは保存する必要があるものとして識別できます。これらの弱いエッジ ピクセルは強いエッジになり、隣接する弱いエッジ ピクセルが保存される原因となります。

このセクションでは、5 つのステップそれぞれにおける画像の進行を示します。

従来のCannyエッジ検出は、エッジ検出問題に対して比較的単純だが正確な方法論を提供しますが、検出の精度と堅牢性に対する要求がより厳しくなると、従来のアルゴリズムでは困難なエッジ検出タスクを処理できなくなります。従来のアルゴリズムの主な欠陥は次のようにまとめることができます。^[1]

1. ガウス フィルターはノイズを滑らかにするために適用されますが、高周波の特徴とみなされるエッジも滑らかにします。これにより、弱いエッジが失われる可能性が高まり、結果に孤立したエッジが表示されるようになります。
2. 勾配振幅の計算では、古い Canny エッジ検出アルゴリズムは、小さな 2×2 近傍ウィンドウの中心を使用して、勾配振幅を表す差分平均値を計算します。この方法はノイズに敏感で、誤ったエッジを検出し、実際のエッジを見失いやすくなります。
3. 従来の Canny エッジ検出アルゴリズムでは、偽のエッジを除外するために 2 つの固定グローバルしきい値が存在します。しかし、画像が複雑になるにつれて、実際のエッジを正確に検出するには、異なるローカル領域で非常に異なるしきい値が必要になります。さらに、従来の方法では、グローバルしきい値は実験を通じて手動で決定されるため、多数の異なる画像を処理する必要がある場合、計算が複雑になります。
4. 従来の検出の結果では、各エッジに対して単一の応答という満足できる高い精度に到達できず、複数ポイントの応答が表示されます。

これらの欠陥に対処するために、次の段落ではキャニー エッジ アルゴリズムの改良について説明します。

エッジとノイズは両方とも高周波信号として識別されるため、単純なガウス フィルターは両方に滑らかな効果を追加します。ただし、実際のエッジの検出精度を高めるには、ノイズにはより滑らかな効果を適用し、エッジにはより滑らかな効果を追加しないことが予想されます。長沙理工大学の Bing Wang 氏と Shaosheng Fan 氏は、各ピクセルのグレースケール値間の不連続性を評価する適応フィルターを開発しました。^[要出典]不連続性が高いほど、その時点での滑らかなフィルターの重み値は低くなります。逆に、グレースケール値間の不連続性が低いほど、フィルターに設定される重み値は高くなります。この適応フィルターを実装するプロセスは、次の 5 つのステップにまとめることができます。

1. K = 1、反復回数nとエッジの振幅係数hを設定します。

2. 勾配値を計算し、${\displaystyle G_{x}(x,y)}$${\displaystyle G_{y}(x,y)}$

3. 以下の式に従って重量を計算します。

${\displaystyle d(x,y)={\sqrt {G_{x}(x,y)^{2}+G_{y}(x,y)^{2}}}}$

${\displaystyle w(x,y)=\exp \left(-{\frac {\sqrt {d(x,y)}}{2h^{2}}}\right)}$

4. 適応フィルタの定義は次のとおりです。

${\displaystyle f(x,y)={\frac {1}{N}}\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}f(x+i,y+j)w(x+i,y+j)}$

画像を滑らかにするために、

${\displaystyle N=\sum \limits _{i=-1}^{1}\sum \limits _{j=-1}^{1}w(x+i,y+j)}$

5. K = nのときは反復を停止し、そうでない場合はk = k+1のときは2番目のステップを続行する。

勾配の大きさと方向は、さまざまなエッジ検出演算子を使用して計算できますが、演算子の選択によって結果の品質が左右されることがあります。最も一般的に選択されるのは 3x3 Sobelフィルターです。ただし、ノイズが軽減される 5x5 Sobel フィルターや、回転対称性が優れているScharrフィルターなど、他のフィルターの方が適している場合もあります。その他の一般的な選択肢としては、 Prewitt (Zhou ^[2]が使用) やRoberts Crossがあります。

二重閾値を経験的に決定することが難しいという課題を解決するために、最大でない抑制勾配振幅画像に対して大津法^[3]を使用して高閾値を生成することができる。この場合、低閾値は通常、高閾値の1/2に設定される。勾配振幅画像は明確に定義された最大値のない連続値であるため、大津法は完​​全なヒストグラムの代わりに値/カウントのペアを使用するように適応させる必要がある。

従来のCannyエッジ検出は最初の2つの基準を満たす優れた検出結果を実装していますが、エッジごとに単一の応答を厳密に満たしていません。検出されたエッジを細くする数学的形態学技術は、Mallat SとZhongによって開発されました。^[4]

カーブレットは、ガウスフィルタと勾配推定の代わりに使用され、方向と大きさが画像内のエッジの方向と強度を近似するベクトル場を計算し、その後、Cannyアルゴリズムのステップ3〜5を適用します。カーブレットは信号を異なるスケールの個別のコンポーネントに分解し、より細かいスケールのコンポーネントを削除することでノイズを減らすことができます。^[5]

サブピクセル精度でエッジを取得するためのより洗練されたアプローチは、差分エッジ検出です。この方法では、非最大抑制の要件が、スケール空間表現から計算された 2 次および 3 次導関数によって定式化されます(Lindeberg 1998)。詳細な説明については、 エッジ検出に関する記事を参照してください。

Canny エッジ検出器の主な要素、つまり勾配方向に沿った 2 次導関数のゼロ交差を見つけることに対する変分法による説明は、エッジと勾配場の整列の積分を最大化しながら、クロンロッド-ミンコフスキー関数を最小化する結果であることが示されました (Kimmel および Bruckstein 2003)。詳細な説明については、正規化されたラプラシアン ゼロ交差とその他の最適なエッジ積分器に関する記事を参照してください。

Canny アルゴリズムには、アルゴリズムの計算時間と有効性に影響を与える可能性のある、調整可能なパラメーターが多数含まれています。

• ガウス フィルターのサイズ: 最初のステージで使用される平滑化フィルターは、Canny アルゴリズムの結果に直接影響します。フィルターが小さいほどぼかしが少なくなり、小さくてシャープな線を検出できます。フィルターが大きいほどぼかしが大きくなり、特定のピクセルの値が画像のより広い領域に広がります。ぼかし半径が大きいほど、より大きくて滑らかなエッジ (たとえば、虹のエッジ) を検出するのに役立ちます。
• しきい値: ヒステリシスのある 2 つのしきい値を使用すると、単一のしきい値を使用する方法よりも柔軟性が高まりますが、しきい値設定方法の一般的な問題は依然として適用されます。しきい値の設定が高すぎると、重要な情報が見逃される可能性があります。一方、しきい値の設定が低すぎると、無関係な情報 (ノイズなど) が誤って重要であると識別されます。すべての画像で適切に機能する一般的なしきい値を設定することは困難です。この問題に対する試行錯誤されたアプローチはまだ存在しません。

Canny アルゴリズムは、さまざまな環境に適応できます。そのパラメータにより、特定の実装の要件に応じて、異なる特性のエッジを認識できるように調整できます。Canny の元の論文では、最適なフィルタの導出によって有限インパルス応答フィルタが導き出されましたが、必要なスムージングの量が重要である場合、空間領域での計算に時間がかかる可能性があります (その場合、フィルタは大きな空間サポートを持ちます)。このため、Rachid Deriche の Canny フィルタの無限インパルス応答形式 ( Canny-Deriche 検出器) を使用することが推奨されることがよくあります。これは再帰的であり、必要なスムージングの量に対して短い固定時間で計算できます。2 番目の形式は、FPGAやDSP、または非常に高速な組み込み PC でのリアルタイム実装に適しています。ただし、このコンテキストでは、Canny 演算子の通常の再帰実装では回転対称性の適切な近似が得られず、水平エッジと垂直エッジに偏ります。

• コンピュータービジョン
• デジタル画像処理
• 特徴検出（コンピュータビジョン）
• 特徴抽出
• 尾根検出
• ロビンソンコンパスマスク
• スケールスペース

• ジョン・キャニーのホームページ
• ラシッド・デリシェの出版物リスト
• ロン・キンメルのジャーナル出版物
• C++ OpenCV での Canny エッジ検出
• Python OpenCV での Canny エッジ検出 2014-04-29 にWayback Machineでアーカイブされました
• Canny Edge World - サンプルビデオ