Loading article…
画像セグメンテーションは、デジタル画像を均質性などの類似した特性を持つピクセルの領域に分割することを目指します。[ 1 ]領域表現の高レベル化により、オブジェクトのカウントや変化の検出などの画像解析タスクが簡素化されます。これは、領域の属性（平均強度や形状[ 2 ]など）を、生のピクセルよりも容易に比較できるためです。
大きな画像のセグメンテーションを高速化するために、処理を複数のCPUに分割することができます。これを実現する方法の 1 つは、画像を独立して処理されるタイルに分割することです。ただし、断片がセグメンテーション アルゴリズムの最小サイズ要件を満たさない場合、タイル境界をまたぐ領域が分割されたり失われたりする可能性があります。簡単な回避策としては、タイルを重ね合わせる、つまり各プロセッサがタイル境界の周囲に追加のピクセルを考慮できるようにする方法があります。残念ながら、タイル境界の両側のプロセッサが冗長な作業を実行するため、計算負荷が増加します。また、タイルの重なりよりも小さいオブジェクトのみが保持されることが保証されるため、航空写真の川のような長いオブジェクトは依然として分割される可能性があります。場合によっては、独立したタイルの結果を融合して、真の結果を近似することができます。[ 3 ] グラフベースのセグメンテーション手法という代替手段があります。グラフに固有の接続情報により、元の画像の一部に対して独立した作業を実行し、それらを再接続して、処理が全体的に行われたかのように正確な結果を得ることができます。
独立したサブ画像を結合できる可能性から、ピクセルに接続情報を追加する動機が生まれます。これはグラフとして考えることができ、ノードはピクセル、エッジはピクセル間の接続を表します。この単純で比較的スペース効率の良いバリアントはグリッドグラフであり、各ピクセルは4つの主要な方向で隣接するピクセルに接続されます。ピクセルの隣接関係は対称であるため、結果として得られるグラフは無向グラフとなり、エッジの半分（たとえば、各ピクセルの東と南の隣接ピクセル）だけを保存すれば済みます。最後のステップでは、ピクセルの類似性情報をエッジの重みにエンコードする必要があるため、元の画像は不要になります。最も単純なケースでは、エッジの重みはピクセル強度の差として計算されます。
最小全域木(MST) は、すべてのノードが接続されるグラフのエッジの最小重みでサイクルのない部分集合です。2004 年に、Felzenszwalb はKruskal の MST アルゴリズムに基づくセグメンテーション手法[ 4 ]を導入しました。エッジは重みの昇順で考慮され、グラフにサイクルが発生しない場合、かつピクセルが既存の領域のピクセルと「類似」している場合は、その終点ピクセルが領域にマージされます。サイクルの検出は、非連結集合データ構造[ 5 ]を利用することでほぼ定数時間で可能です。ピクセルの類似性は、重みをセグメントごとの閾値と比較するヒューリスティックによって判断されます。このアルゴリズムは、複数の非連結 MST、つまりフォレストを出力します。各ツリーはセグメントに対応します。エッジのソートは計数ソートによって線形時間で可能なので、アルゴリズムの複雑さは準線形です。
2009年、Wassenbergらは、複数の独立した最小全域フォレストを計算し、それらを結合するアルゴリズム[ 6 ]を開発した。これにより、タイル境界でオブジェクトを分割することなく並列処理が可能になる。固定の重み閾値の代わりに、初期の連結成分ラベル付けを使用して閾値の下限を推定し、過剰分割と過少分割の両方を減らすことができる。測定結果によると、この実装はFelzenszwalbの逐次アルゴリズムよりも桁違いに優れている。
2017年、SaglamとBaykanはPrimの最小全域木の逐次表現を使用し、画像分割のための新しいカット基準を提案した。[ 7 ]彼らはFibonacci Heapデータ構造を使用してPrimのMSTアルゴリズムでMSTを構築した。この方法はテスト画像で高速実行時間で大きな成功を収めた。