キャニー境界検出器

良い一日！

最近、Habréで、Cannyの境界を抽出するためのアルゴリズム（驚いたことに、文字通りに翻訳する：トリッキー）がしばしば言及されました。したがって、私は成熟して、この検出器を実装した私の経験を公開しました。

自由時間には、独学の目的で、アルゴリズム（マシンビジョンを含む）を勉強します。私はこれを非専門的に行っており、主に科学文献または私自身のアルゴリズムによる解決策に固執しています。
一方ではコーディングを単純化し、他方ではブレインファックプログラミングの物語的なメモを提供するために、コンピューター代数環境Mathcad（アルゴリズムはバージョン13および14でテストされました）での実装を、可能な限り特定の組み込みメソッドを使用せずに示します。私の意見では、このアプローチはデモンストレーションの認識を改善し、他の設計/開発環境へのアルゴリズムの可能な転送を促進します。 Canny検出器操作のいくつかの段階は、さまざまな最適化（たとえば、プロセッサコマンドシステムのSIMD拡張を使用したSobelオペレーターのソフトウェア実装）だけでなく、一部のオペレーター（メソッド）を他のオペレーター（メソッド）に置き換える可能性（たとえば、Sobelオペレーターを置き換えることができる） RobertsまたはPruittによる演算子）、および演算子のパラメーターを指定する係数を変更する可能性。
このバージョンは、Mathcad環境での実装が最大限容易であるために、おそらく検出の速度と品質の点でパフォーマンスを損なうために作成され、Canny検出器の機能の主要な段階のデモとして提示されます。

境界キャニー

Kanni（John F. Canny; 1953）は、1つのエッジのいくつかの応答を分離、ローカライズ、および最小化するための基準に従って最適なフィルターを取得する数学的問題を研究しました。つまり、検出器は境界に応答する必要がありますが、偽の境界を無視し、境界線を（断片化せずに）正確に決定し、各境界に1回ずつ反応する必要があります。 Kanniは、非最大抑制の概念を導入しました。これは、境界のピクセルが、勾配ベクトルの方向で勾配の極大に達する点であることを意味します。
彼の仕事はコンピュータービジョン（1986年）の夜明けに行われましたが、キャニー境界検出器は依然として最高の検出器の1つです。特別な特別な場合に加えて、Canny検出器よりもはるかに優れた動作をする検出器を見つけることは困難です。

挑戦する

アルゴリズムのデモンストレーションとして、次の画像の境界線を強調表示するタスクが解決されます。

このアルゴリズムは、5つの個別のステップで構成されています。

スムージング 。画像をぼかしてノイズを除去します。
勾配を検索します。画像のグラデーションが最大値をとる場所に境界線がマークされます。
非最大値の抑制 。極大のみが境界としてマークされます。
二重しきい値フィルタリング 。潜在的な境界は、しきい値によって決定されます。
あいまいな領域をトレースします 。結果の境界は、特定の（強い）境界に関連しないすべてのエッジを抑制することによって決定されます。

検出器を使用する前に、計算コストを削減するために画像をグレーの濃淡に変換します。この段階は、多くの画像処理方法の特徴です。

グレースケールに変換

元の画像をグレースケールの画像に変換するには、その「明るさ」成分を取得する必要があります。このためには、YUVカラーモデル（またはHSL、HSV、その他）で画像を表示すると便利です。
最初に、画像はRGBカラーモデルで表示され、ダウンロード関数は単一のマトリックスの形式で3つのコンポーネントを返します。

画像をYUVモデルに転送するには、次の操作を実行します。
モデルのコンポーネント（R、G、B）を記述する行列を取得します。

YUVモデルのYコンポーネントを計算します。

変換係数（定数であり、人間の知覚の特性によって決定され、ここで境界を評価するのは正確に人の位置からです）：

変換結果：

スムージング

ノイズを抑制するには、画像ぼかしガウスフィルターを使用します。
2次元の場合のガウス関数：

パラメーターσでサイズsizeのフィルターコアを構成する方法：

手順、サイズsizeとパラメーターσのカーネルを持つフィルターをマトリックス画像マトリックスに適用する：

最適なノイズ低減を提供するフィルターパラメーターを選択する必要があります。ガウスフィルター処理中の相互のピクセルの影響は、ピクセル間の距離の2乗に反比例します。比例係数、したがって、ぼかしの度合いは、パラメーターσによって決まります。係数の過度の増加は、すべてのピクセルの均一な黒色までの平均化の増加につながります。

σ = 1.0を選択します。
フィルターコアは、ポイント（0、0）から遠ざかると非常に急速にゼロに減少するため、実際には（0、0）付近の小さなウィンドウで畳み込みに制限することができます（たとえば、3シグマルールによって導かれ、ウィンドウ半径は3σになります）。以下は、パラメーターσの固定値と異なるコアサイズ（パラメーターサイズ ）でフィルターを適用した結果です。

サイズ = 7を選択します。選択したパラメーターでフィルターを適用した結果を上の図に示します。

勾配検索

Sobel演算子は、境界抽出アルゴリズムでよく使用されます。実際、これは、画像の輝度勾配のおおよその値を計算する離散微分演算子です。画像の各点にSobel演算子を適用した結果は、その点の輝度勾配ベクトルまたはその標準です。 Sobel演算子は、垂直方向および水平方向の小さな整数フィルターを使用した画像の畳み込みに基づいているため、計算は比較的簡単です。一方、彼が使用する勾配近似はかなり粗く、これは特に画像の高周波振動に影響します。
フィルターコア：

実装（各ポイントを勾配ベクトルにマッピング）：

ベクトルの角度は45°で量子化されます-これらは、次の手順のいずれかに必要な値です。
次の図は、ぼやけた画像（A）と元の画像（グレースケール）（B）に演算子を適用した結果を示しています。

非最大値の抑制

境界ピクセルは、勾配ベクトルの方向で勾配の極大に達するピクセルです。方向の値は45°の倍数でなければなりません。

抑制の原理を上の図に示します。この例のほとんどすべてのピクセルは「上向き」であるため、これらのポイントの勾配値は、より低いピクセルと上流のピクセルと比較されます。白いアウトラインで囲まれたピクセルは結果の画像に残り、残りは抑制されます。
画像に属するためのポイントチェックの実装：

値の比較：

抑制の実装：

非最大値を抑制した後、エッジはより正確で薄くなりました。

下の最初の図では、元の（つまり抑制前の）画像全体の勾配のベクトルフィールド（角度は45°の倍数）が表示され、2番目の画像では小さな断片が表示されています。

デュアルしきい値フィルタリング

次のステップでは、しきい値を適用して、境界が画像の特定のポイントにあるかどうかを判断します。しきい値が低いほど境界が多くなりますが、ノイズの影響を受けやすくなり、過剰な画像データが強調表示されます。逆に、高いしきい値は弱いエッジを無視したり、境界線の断片を取得したりできます。
Kanni境界の選択には2つのフィルタリングしきい値が使用されます：ピクセル値が上境界線より上にある場合、最大値（境界線は信頼できると見なされます）を取り、下にある場合、ピクセルは抑制されます次のステップ）。
実装：

範囲の55％および60％のしきい値を使用した結果を次の図に示します。

曖昧性解消エリアのトレース

簡単に言えば、タスクは前の段階で中間値を受け取ったピクセルのグループを選択し、それらを境界に割り当てるか（設定された境界のいずれかに接続されている場合）、または抑制する（そうでない場合）です。 8つの方向のいずれかでグループと接触した場合、グループにピクセルが追加されます。
実装：

トレース結果：

ソースのリスト

開発プロセスでは、次のソースを使用しました（主に[1]）。

Canny Edge Detection www.cvmt.dk/education/teaching/f09/VGIS8/AIP
ウィキペディア エッジ検出 en.wikipedia.org/wiki/Edge_detection
ウィキペディア ソーベル演算子 ru.wikipedia.org/wiki/Sobel_Operator
ラスターグラフィックスのアルゴリズムの基本 www.intuit.ru/department/graphics/rastrgraph/8/rastrgraph_8.html

マシンビジョンの分野は私の専門的な活動とは関係がないため、批判とコメントを歓迎します。

updそして、ここに批判があります。アルゴリズムの基本的なエラーと記事へのリンクを指摘してくれたandreyivanoffに感謝します（こちら）。

ここでupd2 andreyivanoffはアルゴリズムに関する重要なコメントを与えます。