このアルゴリズムは、視差画像Dの以下のグローバルエネルギー関数Eの最小値を求めます。

E D = ∑ p C p , D p + ∑ q ∈ N p P 1 I D p - D q = 1 + ∑ q ∈ N p P 2 I D p - D q > 1

このとき、P2≥P1とします。

ここで
  • E(D)は視差画像Dのエネルギー、
  • p, qは画像内のピクセルの指標、
  • Npはピクセルpの近傍、
  • C(p, Dp)は、Dpの視差を持つピクセルマッチングのコストです。
  • P1は、隣接するピクセル間の視差の変化に対してユーザが渡すペナルティです。
  • P2は、1より大きい値による近接ピクセル間の視差の変化に対してユーザが渡すペナルティです。
  • I[.]は、引数がTRUEの場合1を返し、それ以外の場合0を返す関数です。最小化された関数は、パラメータP1およびP2によって統制される、スムージングを伴う完全な視差マップを生成します。ただし、2D画像空間に対する関数の最小化はNP完了問題です。

セミグローバルマッチング関数は、複数の1D（または線形）最小化を行うことで2D最小化の近似値を求めます。マッチング関数は、検査対象のピクセルを収束する複数のパスのコストを集計します。コストは最小視差と視差パラメータで定義される視差範囲において計算されます。マッチングアルゴリズムは、デフォルトでは5つの方向のコストを集計します。フルダイナミックプログラミングパラメータをTRUEに設定すると、アルゴリズムは8方向のコストを集計します。S(p, d)がピクセルp、視差dの集計コストであるとします。

その場合は

S p , d = ∑ L r p , d r

ここで、r はピクセルp を収束する方向、Lr(p, d) は (視差d のピクセルp) からのr 方向へのパスの最小コストです。Lr(p, d) は以下の式で求められます。

この式では、現在のコストC(p, d)を、方向rの前のピクセルに加算して視差を計算する際に、以下のコストを使用します。

  • 視差dの前のピクセルの最小コスト
  • 視差d - 1およびd + 1、追加ペナルティP1の前のピクセルのコスト、
  • 視差がd - 1より小さくd + 1より大きい、追加ペナルティP2の前のピクセルのコスト値

パス上の増加し続けるLr(p, d)の値を制限するために、前のピクセルの最小値を減算します。Lr(p, d) の上限値は、Cmax + P2 によって制限されます。ここで、Cmax はコスト C の最大値です。コスト関数 C(p, d) は次のように計算されます。

ここで、ILとIRはそれぞれ左と右の平行化された画像です。

Cの値はユーザ定義サイズの窓にわたって集計されます[1]1 Birchfield and C. Tomasi, Depth Discontinuities by Pixel-to-Pixel Stereo, IJCV, vol. 35(3), pp. 269-293, 1999.。各視差dの各ピクセルpに対してS(p, d)を計算後、アルゴリズムはそのピクセルに対してコストが最小となる視差を選択します。

このアルゴリズムの複雑度は以下の式で求められます。

O w · h · n

ここで
  • wは平行化された画像の幅と等しく、
  • hは平行化された画像の高さ、
  • nは視差の数です。

1 Birchfield and C. Tomasi, Depth Discontinuities by Pixel-to-Pixel Stereo, IJCV, vol. 35(3), pp. 269-293, 1999.