境界の追跡

2 進デジタル領域の境界トレーシング(輪郭トレーシングとも呼ばれる)は、デジタル領域の境界ピクセルを識別するセグメンテーション手法と考えることができます。境界トレーシングは、その領域を分析するための重要な最初のステップです。境界は位相的な概念です。ただし、デジタル画像は位相空間ではありません。したがって、デジタル画像内の境界の概念を数学的に正確に定義することは不可能です。デジタル画像 I のサブセット S の境界のトレーシングに関するほとんどの出版物では、S に属し、その直接の近傍に S とその補集合 I - S の両方に属するピクセルを持つピクセルのセットを見つけるアルゴリズムについて説明しています。この定義によると、サブセット S の境界は補集合 I - S の境界とは異なり、これは位相的なパラドックスです。

境界を正しく定義するには、与えられたデジタル画像に対応する位相空間を導入する必要があります。このような空間は、2 次元の抽象セル複合体になります。この空間には、3 次元のセルが含まれます。デジタル画像のピクセルに対応する 2 次元セル、隣接する 2 つのピクセルの間にある短い線を表す 1 次元セルまたは「亀裂」、ピクセルの角に対応する 0 次元セルまたは「点」です。サブセット S の境界は、一連の亀裂と点であり、これらの亀裂と点の近傍は、サブセット S とその補集合 I – S の両方と交差します。

このように定義された境界は、位相的な定義と正確に一致し、境界に関する私たちの直感的な想像とも一致します。なぜなら、S の境界には、S の要素もその補集合の要素も含まれないからです。境界には、S と補集合の間にある要素だけが含まれる必要があります。これがまさに複合体の亀裂と点です。

この境界をトレースする方法は、ウラジミール・A・コヴァレフスキーの著書^[1]とウェブサイト^{[2]で説明されています。}

• ピクセル追跡: セルを歩いて記録します。通常は外側の境界のみをトレースし、スペースのサイズを変更する場合は後処理が必要です。実装が最も簡単です。
• 頂点追跡法: エッジをたどり、エッジとコーナーを記録します。通常は外側の境界のみをトレースします。連続したエッジは削除してデータを簡素化できます。
• 実行データベース: 空間内のすべてのセルを処理します。画像内のすべての境界をトレースします。すべてのセルを処理する必要があるため、小さな単一境界の場合は他のタイプよりも効率が低くなります。個々のセルあたりのステップは通常他のタイプよりも少ないため、大きく複雑な画像の場合はより効率的です^[3]

境界追跡に使用されるアルゴリズム: ^[4]

• 正方形トレースアルゴリズム。^[5] 4連結（非対角）パターンにのみ使用でき、開始セルに開始と同じ方向に入ることが停止基準となります。
• ムーア近傍トレースアルゴリズムは、同様の弱点を持つスクエアトレースアルゴリズムに似ていますが、8接続（対角）パターンで機能します。
• ラジアルスイープ^[6]
• テオ・パブリディスのアルゴリズム^[7]は前方の3つのセルをテストしますが、チェックは短絡される可能性があります。一部のパターンでは失敗する可能性があります。
• 境界のトレースにベクトル代数を用いた一般的なアプローチは^{[8]で見つけることができます。}
• 境界トレースの拡張により、トレースされた境界を開いた部分と閉じた部分に分割する方法が^{[9]で説明されている。}

マーチング スクエアは、 2 次元フィールド内のすべてのセルのすべてのコーナーをチェックして輪郭を抽出します。初期位置は使用せず、輪郭を順序付けられたシーケンスとして生成しないため、輪郭を「トレース」しません。4 つの隣接セルすべての各コーナーをチェックする必要がありますが、チェックは独立しているため、並列処理によってパフォーマンスを簡単に向上できます。

正方形トレース アルゴリズムはシンプルですが、効果的です。その動作は、黒のセルか白のセル (白のセルが図形の一部であると仮定) のどちらにいるかによって決まります。まず、左上から右へ、1 行ずつスキャンします。最初の白のセルに入ると、アルゴリズムの核心が動き出します。これは主に 2 つのルールで構成されます。

• 白いセルにいる場合は、左に進みます。
• 黒いセルにいる場合は、右に進みます。

左と右を定義できるように、現在のセルにどのように入力したかが重要であることに注意してください。

public void GetBoundary ( byte [,] image ) { for ( int j = 0 ; j < image . GetLength ( 1 ); j ++ ) for ( int i = 0 ; i < image . GetLength ( 0 ); i ++ ) if ( image [ i , j ] == 255 ) // 最初の白いピクセルが見つかりましたSquareTrace ( new Point ( i , j )); }   

            
                
                               
                  


public void SquareTrace ( Point start ) { HashSet < Point > boundaryPoints = new HashSet < Point > (); // 重複発生を防ぐため HashSet を使用する// 少なくとも 1 つのピクセルboundaryPointsが見つかりました。Add ( start );   

          
    
    

    // 最初に遭遇するピクセルは定義上白なので、左に進みます。
// この例では、慣例とは異なり、Point コンストラクターの引数は y、x です。// 最初の方向は左から右だったので、(1, 0) です。Point nextStep = GoLeft ( new Point ( 1 , 0 )); Point next = start + nextStep ; while ( next != start ) { // 黒いセルを見つけたので、右に進み、このセルを HashSet に追加しません。if ( image [ next . x , next . y ] == 0 ) { next = next - nextStep ; nextStep = GoRight ( nextStep ); next = next + nextStep ; } // 代わりに、白いセルを見つけたので、これを HashSet に追加します。else { boundaryPoints . Add ( next ); nextStep = GoLeft ( nextStep ); next = next + nextStep ; } } }    
    
                        
         
       
    
        
            
        
                
              
                
        
        
        
        
            
              
                
        
    


プライベートPoint GoLeft ( Point p ) =>新しいPoint ( p . y , - p . x );プライベートPoint GoRight ( Point p ) =>新しいPoint ( - p . y , p . x );       
       

ラジアル スイープ アルゴリズムは、文献ではより一般的に知られているムーア近傍トレーシングと並んでよく取り上げられており、画像処理における輪郭トレーシングに対する一見単純なアプローチを示しています。アルゴリズムの命名法は複雑に感じられるかもしれませんが、その基本原理はよく知られているムーア近傍トレーシング手法と密接に一致しています。

ムーア近傍トレーシングは、デジタル画像内の境界を描写するための一般的な方法で、指定された境界ピクセルのムーア近傍を所定の方向（通常は時計回り）に移動します。黒いピクセルに遭遇すると、このピクセルを新しい境界点として指定し、繰り返し処理を進めます。

ただし、ラジアル スイープ アルゴリズムは、機能的にはムーア近傍トレーシングと同等ですが、特定の境界点のムーア近傍内の次の黒いピクセルを識別するための新しい視点を導入します。

このアルゴリズムの革新性は、次の境界ピクセルを正確に特定するアプローチにあります。新しい境界ピクセル（P と表記）を識別すると、アルゴリズムはそれを現在の関心点として設定します。次に、点 P と前の境界ピクセルを結ぶ仮想線分を作成します。その後、アルゴリズムはこの線分を点 P を中心に時計回りに、P のムーア近傍内の黒いピクセルと交差するまで系統的に回転させます。^[10]事実上、この回転運動は、ムーア近傍内の点 P を囲む各ピクセルを検査するプロセスを反映しています。

この方法を採用することで、ラジアル スイープ アルゴリズムは、デジタル画像内の境界ピクセルをトラバースするための独特の戦略を提供します。基本的にはムーア近傍トレーシングに似ていますが、回転探索に重点を置くことで、画像分析やコンピューター ビジョンアプリケーションにおける輪郭トレーシング手法に興味深い視点をもたらします。

テオ・パブリディスのアルゴリズムは、バイナリ画像の輪郭追跡によく知られた手法で、関連するコンポーネントの境界を系統的に検出して追跡するように設計されています。この手法は、通常、画像を上から下、左から右にスキャンしたときに最初に表示される黒ピクセルである最初の境界ピクセルを見つけることから始まります。現在のピクセルの周辺を調べて次の境界ピクセルを見つけることから始まり、境界を構成する次の黒ピクセルを見つけるために時計回りに進むことがよくあります。^[10]

プログラムは、各境界ピクセルを 1 回だけアクセスするように、1 つの境界ピクセルから次の境界ピクセルに移動して輪郭をトレースします。この体系的な手法により、計算効率が向上します。トレース プロセスは、アルゴリズムが最初の境界ピクセルに戻るまで継続され、アイテムの輪郭が完成します。このアプローチは実装が比較的簡単なため、コンピューター ビジョンや画像処理タスクにおけるオブジェクト検出、形状分析、パターン認識など、さまざまなアプリケーションでよく使用されます。

Theo Pavlidis のアルゴリズムは、そのシンプルさ、効率性、および回復力で有名です。バイナリ画像内のさまざまなオブジェクトの形状とサイズを処理できるため、さまざまな画像処理アプリケーションに役立ちます。

• パスファインディング
• 曲線のスケッチ
• チェーンコード
• ピクセル接続
• 最適化問題