オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

トップ > 【画像処理】グラフカット / Grab Cut

【画像処理】グラフカット / Grab Cut

Index

グラフカット / GrabCut

各画素を対象と背景に分割する問題を各画素のラベル付け問題として解く方法を扱う.

ある画像において、あらかじめ対象 (object: "obj")と背景 (background: "bkg")の一部の位置が与えられている条件下で、 対象と背景が隣接する画像には画素値に違いがあるという仮定の元で、全画素を「対象」と「背景」の2種類にラベル付けする問題を考える. 適切にラベル付けされたときに、最小となるコスト関数を与え、コスト最小となるラベルの組み合わせを効率よく求める方法がグラフカットである.

コスト関数

コスト関数 E(L) を以下に定義する.

コスト関数

E(L)\ =\ R(L)\ +\ \lambda\ \cdot\ B(L)



  • \lambda\ \geq\ 0
    • R(L) と B(L) の相対的重要度の重み
  • L\ =\ \{"obj",\ "bkg"\} : ラベルの集合



第1項 (領域項 / データ項) について.

R(L)\ =\ \displaystyle \sum_{p\ \in\ P}\ R_{p} (L_{p})


  • P : 画素の全集合
    • p : P の要素、ある画素
  • L_{p} : ある画素 p のラベル
  • R_{p}(L_{p}) : ある画素 p が L_{p} でない度合い


R_{p} は、あらかじめ対象と背景の一部を教示した領域から計算される. 例えば、指定された領域から画素値ヒストグラムを作成しておき、任意の画素 p について、 その画素値から対象あるいは背景の要素である確率を計算し、確率が高いときに小さな値をとなるようなコスト関数.



第2項 (境界項 / 平滑化項) について.

B(L)\ =\ \displaystyle \sum_{\{p,\ q\}\ \in\ N}\ B_{\{p,\ q\}}\ \cdot\ \delta(L_{p},\ L_{q})

\delta(L_{p},\ L_{q})\ =\ \left\{ \begin{array}{ll} 1 & (L_{p}\ \neq\ L_{q}) \\ 0 & (L_{p}\ =\ L_{q}) \end{array} \right.


  • N : 隣接する画素どうしの組の全集合
    • \{p,\ q\} : 隣接するある画素の組
  • L_{p} : ある画素 p のラベル
  • L_{q} : ある画素 q のラベル
  • B_{\{p,\ q\}} : ある画素の組 \{p,\ q\} が異ならない度合い


B_{\{p,\ q\}} は画素 p と q の両画素が異なるほど小さな値をとるコスト関数. たとえば、輝度の勾配に基づく関数で勾配が大きいほど小さな値をとるようなコスト関数.

コスト関数の例

指定された対象と背景の領域からそれぞれ画素値のヒストグラム Pr(I\ |\ L) を作成する. \sum Pr\ =\ 1 になるように正規化すると、 Pr(I\ |\ bkg) は背景に属する画素の画素値 I が観測される確率となる.

その確率密度関数を用いて、領域項 R(L) を以下のようなコスト関数とする.

領域項 R

\begin{align} R_{p}(obj)&\ =\ - \ln\ Pr(I_{p}\ |\ obj)\\ R_{p}(bkg)&\ =\ - \ln\ Pr(I_{p}\ |\ bkg) \end{align}



R_{p}(bkg) は、画素 p のラベルが背景 bkg で、その画素値 I_{p} となる確率密度関数の対数をとり-1倍したコストである.



次に、境界項を以下のコスト関数にする.

境界項 B

\begin{align} B_{\{p,\ q\}}&\ =\ \exp\left(-\ \displaystyle \frac{(I_{p}\ -\ I_{q})^{2}}{2 \sigma^{2}}\ \cdot\ \displaystyle \frac{1}{dist(p,\ q)} \right)\\ \delta(L_{p},\ L_{q})&\ =\ \left\{ \begin{array}{ll} 1 & (L_{p}\ \neq\ L_{q}) \\ 0 & (L_{p}\ =\ L_{q}) \end{array} \right. \end{align}



  • dist(p,\ q) : p,\ q 間の距離

参考

書籍

Web サイト

動画

  • 【数分解説】GrabCut(GraphCut): 指定された領域やヒントで画像から物体を切出したい【画像処理/グラブカット】