1. 現在のラベルβを初期化
2. 階層ラベルAを作成
3. グラフの総コストEを初期化
4. 階層の深さdepthだけ以下をループ
   1. グラフを初期化
   2. ノードを追加
   3. 全ての画素kに対して
      1. 現在の深さiの階層ラベルA[i]のうち最もβ[k]に最も近い値 をαkに設定
      2. ノードのソース側にD(βk)，シンク側にD(αk)を設定
   4. 全てのエッジに対して，(以下では，画素p, qのエッジ)
      1. 現在の深さiの階層ラベルA[i]のうち最もβ[p]に最も近い値をαpに設定
      2. 現在の深さiの階層ラベルA[i]のうち最もβ[q]に最も近い値をαqに設定
      3. ノードaソース側にV(βp, βq)，シンク側にV(αp, αq)を設定
      4. もし，V(βp, βq) ≦ V(αp, αq)ならば，
         1. ノードaからノードpへのエッジの重みに10000(比較的大きい数)を設定
         2. ノードaからノードqへのエッジの重みに10000(比較的大きい数)を設定
         3. ノードpからノードaへのエッジの重みに，V(αp, βq)-V(βp, βq)か0のうち大きいほうを設定
         4. ノードqからノードaへのエッジの重みに，V(βp, αq)-V(βp, βq)か0のうち大きいほうを設定
      5. もし，V(βp, βq) ≧ V(αp, αq)ならば，
         1. ノードpからノードaへのエッジの重みに10000(比較的大きい数)を設定
         2. ノードqからノードaへのエッジの重みに10000(比較的大きい数)を設定
         3. ノードaからノードpへのエッジの重みに，V(αp, βq)-V(αp, αq)か0のうち大きいほうを設定
         4. ノードaからノードqへのエッジの重みに，V(βp, αq)-V(αp, αq)か0のうち大きいほうを設定
      6. 最大流・最小カットアルゴリズムを適用し，総コストE'を計算
      7. もし，E > E' ならば
         1. 現在のラベルβkを求まったラベル更新
         2. 総コストの更新(E = E')
   5. グラフの消去
5. 総コストが収束するまで4を繰り返す

コスト関数

コスト関数は，アルファ拡張，階層グラフカットのどちらも講義で紹介されたものを参考にした．

• データコスト
  • 出力画像fpが入力画像Ipに出来るだけ近くなるようにする項
  • D(β) = SAD(β) = Σ|I(x, y) - I(x - β, y)|
• スムーズコスト
  • 隣り合った画素fp，fqの明るさが出来るだけ近くなるようにする項
  • V(fp) = |fp - fq|