グラフカットは、コンピュータビジョンや人工知能で生じるエネルギー最小化問題を解くために用いられる、組合せ最適化手法の一族である。その核心となる考え方は、ラベリングやセグメンテーションの問題をグラフとして表現することであり、ノードは画素やデータ点に対応し、エッジはペアごとの関係を符号化する。問題を解くことは、グラフの最小カットを見つけることに帰着し、これによりノードをコスト関数を最小化しながら互いに素な集合に分割する。この手法は、前景・背景セグメンテーションなどの二値ラベリング問題に特に効果的であり、α展開などの手法を通じて多ラベル問題にも拡張できる。
グラフカットの数学的基盤は、最大フロー最小カット定理にあり、ネットワークにおけるソースからシンクへの最大フローが、それらを分離するカットの最小容量に等しいことを述べている。コンピュータビジョンでは、この定理を利用して、二つのラベルを表す特別な終端ノード（ソースとシンク）を持つグラフを構築する。各画素は両方の終端にエッジで接続され、その容量はその画素を各ラベルに割り当てる単項コストを反映する。さらに、隣接画素間のエッジは平滑性ペナルティを符号化し、一貫性のある領域を促進する。最小カットは、データの忠実性と空間的規則性のバランスを取る最適なラベリングを導き出す。
歴史的発展
コンピュータビジョンにおけるグラフカットの利用は、1990年代後半から2000年代初頭にかけて注目を集め、それ以前の組合せ最適化の研究に基づいていた。主要な貢献は、ユーリ・ボイコフやウラジミール・コルモゴロフなどの研究者によってもたらされ、彼らはビジョン問題における最小カット計算の効率的なアルゴリズムを導入した。彼らの2001年の対話的画像セグメンテーションに関する論文は、ユーザーが前景と背景の領域をマークできるようにしたもので、非常に影響力を持つようになった。ほぼ同時期に、グラフカットとマルコフ確率場（MRF）との関連が形式化され、ペアごとの項を持つ多くのエネルギー関数が、グラフベースの手法を用いて正確にまたは近似的に最小化できることが示された。
コンピュータビジョンへの応用
グラフカットは、幅広いビジョンタスクに適用されてきた。画像セグメンテーションでは、しばしばユーザーの操作をガイドとして用いて、物体を背景から分離するために使用される。医用画像処理では、CTやMRIスキャンにおける臓器の輪郭抽出にグラフカットが役立ち、境界情報と領域情報を組み込むこの手法の能力が価値を持つ。二つの画像から深度を推定するステレオマッチングも、グラフカットを用いて視差ラベルを割り当てながら平滑性を強制する。その他の応用には、ノイズのある観測からクリーンな画像を復元することを目的とする画像デノイジングや、複数のカメラ視点から3D表面を融合するのにグラフカットが役立つマルチビュー再構成がある。
エネルギー最小化との関連
人工知能において、グラフカットはエネルギーに基づくモデルの特定の例であり、その目標は大域的なコストを最小化する構成を見つけることである。エネルギーは通常、単一の変数にラベルを割り当てるコストを測る単項項と、隣接する変数にラベルを割り当てるコストを測るペア項からなる。劣モジュラなペアポテンシャルを持つ二値変数の場合、最小値はグラフカットを用いて多項式時間で正確に見つけることができる。多ラベル問題では、α展開やα-βスワップなどの近似アルゴリズムが、二値部分問題を反復的に解くことで良好な解を提供する。これらの手法は、機械学習における構造化予測タスク、例えば深層学習パイプラインにおけるセマンティックセグメンテーションで広く使用されている。
現代の文脈と代替手法
ニューラルネットワークベースのアプローチ、特にU-Netアーキテクチャや残差ネットワークモデルの台頭により、グラフカットはエンドツーエンド学習においてかつてほど支配的ではない。しかし、後処理ステップやハイブリッドシステムの微分可能なコンポーネントとして、それらは依然として関連性を持つ。例えば、グラフカットは深層学習モデルの粗い出力を精緻化して空間的一貫性を強制できる。また、データ拡張パイプラインでトレーニングラベルを生成するためにも使用される。Boykov-Kolmogorovなどのライブラリに実装された現代の最大フローアルゴリズムの計算効率は、リアルタイムアプリケーションに実用的である。生成AIや大規模言語モデルシステムが高次元の離散問題に焦点を移す一方で、グラフカットは構造化出力空間における基礎的なツールとして機能し続けている。
制限と拡張
グラフカットは、正確な解を得るための劣モジュラ性への依存によって制限される。特定のビジョンタスクで生じる非劣モジュラエネルギーは、二次擬ブール最適化や移動生成アルゴリズムなどの代替手法を必要とし、それらは最適性を保証しない場合がある。メモリと時間の複雑さも画像サイズとともに増大するが、GPU上の並列実装によって緩和されている。拡張には、グラフを増分的に更新するビデオシーケンス用の動的グラフカットや、より複雑な相互作用を捉える高次ポテンシャルが含まれる。グラフカットを強化学習や他のAIパラダイムと統合する研究が続いているが、核となる手法は、組合せ最適化が知覚と交差する古典的な例であり続けている。