連結成分ラベリング（CCL）は、連結成分分析、ブロブ抽出、領域ラベリング、またはブロブ発見とも呼ばれ、グラフ理論のアルゴリズム的応用であり、連結成分のサブセットが与えられたヒューリスティックに基づいて一意にラベル付けされる。コンピュータビジョンでは、バイナリデジタル画像内の連結領域を検出するために使用されるが、カラー画像や高次元データも処理可能である。CCLは画像セグメンテーションとは異なり、ブロブ抽出はブロブ検出とは関連するが異なるものである。
実際には、CCLは入力データから構築されたグラフ上で動作し、頂点はピクセルまたは要素を表し、エッジは近傍間の連結性を示す。アルゴリズムはグラフを走査し、連結性と相対値に基づいて頂点にラベルを割り当てる。ラベル付け後、グラフはサブセットに分割でき、元の情報を回復して、ブロブの計数、フィルタリング、追跡などのタスクに処理できる。
定義と用語
連結成分ラベリングという用語は学術文献で一貫して使用されるが、連結成分分析（CCA）は用語と問題定義の両方で異なる。RosenfeldらはCCLを、バイナリ入力画像の同じ連結成分に関連する位置が一意のラベルを持つラベル付き画像の作成と定義する。ShapiroらはCCLを、入力がバイナリ画像で出力がシンボリック画像であり、各ピクセルのラベルがその連結成分を一意に識別する整数である演算子と説明する。
CCAの定義についてはコンセンサスがなく、CCLと互換的に使用されることが多い。Shapiroらによるより広範な定義では、CCAは黒ピクセルの連結成分ラベリング、その後の成分領域のプロパティ測定、および意思決定から構成されると述べている。本記事では、これらの視点を組み込んだより広い解釈を採用する。
グラフ構築と連結性
関連する入力データからグラフが構築され、頂点には比較ヒューリスティックに必要な情報が含まれ、エッジは連結された近傍を示す。アルゴリズムはグラフを走査し、連結性と相対値に基づいて頂点にラベルを付ける。連結性は媒体によって決定され、画像グラフでは、一般的な近傍には4連結（北、南、東、西）と8連結（対角線を含む）がある。
ラベル付け後、グラフはサブセットに分割され、その後、元の情報を回復して処理できる。このアプローチは任意の次元に一般化されるが、時間と空間の複雑さはそれに応じて増加する。
一度に一成分アルゴリズム
一度に一成分アルゴリズムは高速で実装が簡単であり、グラフ走査法に基づいている。これはVincentとSoilleの流域セグメンテーションアルゴリズムの一部であり、他の実装も存在する。この方法はリンクリストを使用して連結ピクセルのインデックスを保持し、深さ優先探索または幅優先探索の選択はこのアプリケーションでは実質的な違いはない。
このアルゴリズムは、前景と背景のピクセルを持つバイナリ画像を想定し、前景の連結成分にラベルを付けることを目的とする。手順は以下の通り：
- 最初のピクセルから開始し、現在のラベルを1に設定する。
- ピクセルが前景で未ラベルなら、現在のラベルを割り当ててキューに追加する。それ以外の場合は次のピクセルに移動する。
- キューから要素をポップし、その近傍（連結タイプに基づく）を調べる。近傍が前景で未ラベルなら、現在のラベルを割り当ててキューに追加する。キューが空になるまで繰り返す。
- 次のピクセルに移動し、現在のラベルをインクリメントする。
ピクセルはキューに入る前にラベル付けされ、各前景ピクセルの近傍は一度だけチェックされ、背景ピクセルの近傍はチェックされない。疑似コードは2つのキューを使用してピクセル処理を管理し、効率的な走査を保証する。
コンピュータビジョンでの応用
CCLは、しきい値処理ステップの後などに、バイナリ画像内の連結領域を検出するためにコンピュータビジョンで広く使用される。ブロブ抽出はグレースケール画像やカラー画像にも適用できる。ブロブは計数、フィルタリング、追跡が可能であり、CCLは画像認識システムや人間とコンピュータの相互作用インターフェースで価値がある。
例えば、Machine learningパイプラインでは、CCLはオブジェクト検出やセグメンテーションタスクのために画像を前処理でき、U-Netアーキテクチャなどの技術を補完する。また、医療画像解析、産業検査、自動運転などのArtificial intelligenceシステムでも使用され、連結領域の識別が重要である。
関連概念と拡張
CCLはブロブ検出とは関連するが異なり、ブロブ検出は強度変動に基づく関心領域の識別に焦点を当てる。対照的に、CCLは連結性に基づいてすべての連結成分にラベルを付ける。このアルゴリズムは、医療画像の3Dボリュームなどの高次元データに拡張でき、計算コストは増加する。
Deep learningとNeural networkモデルの最近の進歩により、セグメンテーションの学習アプローチが生まれたが、CCLは後処理と解析のための基本的なツールであり続けている。その単純さと効率性から、コンピュータビジョンライブラリやフレームワークの定番であり、トレーニングパイプラインでData AugmentationやLoss Functionsと組み合わせて使用されることが多い。
関連項目
- コンピュータビジョン
- 画像セグメンテーション
- ブロブ検出
- グラフ理論