グラフカット

グラフカット
http://www.vision.cs.chubu.ac.jp/
2011年3月18日
藤吉研究室
中部大学工学部情報工学科
• グラフカットの概要
• グラフカットアルゴリズム
• C++による実装
• コンピュータビジョンへの応用例
Graph Cuts [Boykov, PAMI2004]
• できること
‒ 1階のマルコフ確率場(Markov Random Field)の
事後確率最大化（エネルギー最小化）する最適化アルゴリズム
• 特徴
‒ 2値ならば必ず大域解が求まる
• コンピュータビジョンへの応用例
‒ ラベリング問題
• Image Restoration, Stereo, Image Segmentation
etc...
ラベリング問題
• 各サイト(場所)にラベルを割り当てる問題
‒ Image Restoration → 輝度値
‒ Stereo → 視差
‒ Image Segmentation → カテゴリ(物体，背景 etc.)
入力画像
ラベリング結果(領域分割)
マルコフ確率場(Markov Random Field)
• 無向グラフで確率変数の間の依存関係を表した
グラフィカルモデル
• ラベルLが与えられたときのエネルギー関数E(L)
E(L) =
�
V1 (Li ) +
�
V2 (Li , Lj ) +
i,j∈P
i∈P
�
i,j,k∈P
V3 (Li , Lj , Lk ) + · · ·
• グラフカットでは1階のエネルギー関数を最適化可能
E(L) =
�
i∈P
V1 (Li ) +
�
V2 (Li , Lj )
i,j∈P
V1(Li)
Li
V2(Li,Lj)
エネルギー最小化問題
• エネルギー関数E(L)が最小となるLを求める問題
• 従来の最適化手法
‒ Iterated Conditional Model
→ 局所解に落ち込みやすい
‒ Simulated Annealing
→ 無限時間かかる可能性(NP困難)
• グラフカットアルゴリズム
‒ グラフ理論のネットワーク流問題の解法を利用
‒ オペレーションズリサーチで利用されていた
‒ ラベルが2値ならば大域最小化が保証
グラフカットアルゴリズム
グラフの基礎
•
•
•
•
Flow：流れ
Capacity：そのEdgeに流すことができるFlowの容量
Source：Flowが発生する場所
Sink：Flowが到着する場所
Network
Edge
Node
Flow
1/1
Source
Capacity
4/4
2/6
Sink
1/3
S
2/5
0/2
t
1/3
2/2
2/2
s-t cut
• エッジを切断してsとtの部分グラフへ分割
• カットの容量
‒ s-t cutの間に，sの集合からtの集合へ向かうエッジの容量
1+3+2+2=8
1+5+3=9
1+3+2=6
6+2=8
1
4
6
3
S
5
2
t
3
2
2
最小カットと最大フロー
• 目的
‒ 最小となるs-t cutを見つけた
→ 最小カット問題
• 最大フロー・最小カットの定理
‒ 最大フローの値 = 最小カットの値
→ 最大フロー問題と最小カット問題は同じ
（最大フローが求まれば最小カットも求められる）
ネットワーク流問題(最大流問題)
• 与えられたネットワークに対して，最大の流れを求める
問題
‒ Min-Cut/Max-Flow Algorithm
• フォードファルカーソン法 (Ford-Fulkerson s method)
• プッシュリラベル法 (Push-Relabel method)
• New Algorithm by Boykov, etc.
100M
10M
10M
10
sink
source
20M
100
10
10M
10
s
t
20
10
Ford-Fulkerson's method
• フローが最大のときの条件
‒ 残余ネットワーク上で s-t path が存在しない
→ s-t pathが存在すればフローは増加可能
Step1：全ての枝のフローを0で初期化
Step2：現在のフローに関する残余ネットワークを作成
Step3：残余ネットワークにs-t pathが存在場合は終了
Step4：残余ネットワークのs-t pathをひとつ求め、
それを用いて現在のフローを更新
Step5：Step2へ戻る
残余ネットワーク
• フローが流れているネットワークがあとどれだけの
フローを流せるかを表したネットワーク
1/1
4/4
2/6
1/3
S
2/5
0/2
1/3
2/2
2/2
1
2 2
0
2
S
0
4
0
4
残余ネットワーク
ネットワーク
t
2
1
2
3 2
0
2
1
0
t
Ford-Fulkerson‘s methodの例
0/4
0/3
0/2
S
0/3
t
0/2
4
ネットワーク
3
0
0
0
S
0
2
t
0
3
2
残余ネットワーク
Ford-Fulkerson‘s methodの例
3/4
3/3
0/2
S
0/3
t
0/2
1
ネットワーク
0
3
3
0
S
0
2
t
0
3
2
残余ネットワーク
Ford-Fulkerson‘s methodの例
4/4
3/3
1/2
S
0/3
t
1/2
0
ネットワーク
0
3
4
1
S
0
1
t
1
3
1
残余ネットワーク
Ford-Fulkerson‘s methodの例
4/4
3/3
1/2
S
1/3
t
2/2
0
ネットワーク
0
3
4
1
S
1
1
t
2
2
残余ネットワークにs-t pathが存在しない
→ 最大フロー 5
0
残余ネットワーク
2値MRF最小化のためのグラフ
• MRFのエネルギー関数E(L)をグラフで表現
E(L) =
�
V1 (Li ) +
i∈P
�
V2 (Li , Lj )
i,j∈P
t
t
V1(Li =0)
V2(Li,Lj)
V1(Li =1)
s
1次元データ
s
2次元データ
MRFのエネルギー関数とs-t cutの関係
E(L) =
�
V1 (Li ) +
i∈P
t
�
V2 (Li , Lj )
i,j∈P
V1(Li =0)
V2(Li,Lj)
V1(Li =0) ×6
V1(Li =1) ×1
V2(Li,Lj) ×1
V1(Li =1)
ラベル L
1
0
1
0
V1(Li =0) ×3
V1(Li =1) ×4
V2(Li,Lj) ×3
1
0
s
0
0
1
0
0
0
0
1
→ 最小カットからエネルギー関数を最小とするラベルを求められる
多値MRF最小化のためのグラフ
• 多値の大域最小化が可能
‒ 条件：平滑化項が凸
t
V1(Li =0)
t
V1(Li =1)
V1(Li =0)
V2(Li,Lj)
V1(Li =2)
V1(Li =3)
V1(Li =1)
s
2値グラフカット
s
多値グラフカット
Graph Cutsの拡張手法
• 多値の近似最小化
‒ 平滑化項が凸である必要がない
• α拡張
• α-β交換
• 高階MRFへの拡張
‒ 高階グラフカット [Ishikawa, CVPR2009]
C++による実装
例：2値画像ノイズ除去
• アイデア
‒ 入力画像との変化は小さい
‒ 近隣画素との変化は小さい
• エネルギー関数
‒ データ項：入力画像との差
‒ 平滑化項：近傍画素との差
E(X) =
�
i∈P
λ|Yi − Xi | +
データ項(data term)
�
(i,j)∈P
κ|Xi − Xj |
平滑化項(smoothing term)
Y :入力画像
X :出力結果
グラフカットライブラリの入手
• Yuri BoykovのMax-flow/min-cut
‒ http://vision.csd.uwo.ca/code/
‒ C++により実装
‒ グラフの作成，maxflowを求めることが可能
ライブラリの使い方
•
ヘッダーを読み込む
‒
•
#include graph.h
使うクラス，関数
‒
グラフクラス
• Graph<typename captype, typename tcaptype, typename flowtype>
‒
ノードの作成
• add_node(int num)
‒
データ項のエッジを作成
• add_tweights(node_id i, tcaptype cap_source, tcaptype cap_sink)
‒
平滑化項のエッジを作成
• void add_edge(node_id i, node_id j, captype cap, captype rev_cap)
‒
最大フローを求める
• maxflow(bool reuse_trees = false, Block<node_id>* changed_list = NULL)
‒
ノードがs側かt側かを判定
• what_segment(node_id i, termtype default_segm = SOURCE)
プログラム例 (1/3)
int Denoise(IplImage* img, IplImage* result)
{
// 入力画像情報
int width = img->width;
int height = img->height;
int wstep = img->widthStep;
int bpp = ((img->depth & 255) / 8) * img->nChannels;
unsigned char* image = (unsigned char*)img->imageData;
unsigned char* image_result = (unsigned char*)result->imageData;
// parameter
int lambda = 90;
int kappa = 25;
// グラフクラス (ノードサイズとエッジのサイズの大まかな数を指定)
typedef Graph<int, int, int> GraphType;
GraphType* g = new GraphType(width*height, width*height*4);
// ノードの作成
g->add_node(width*height);
プログラム例 (2/3)
int dx[4] = {1, -1, 0, 1};
int dy[4] = {0, 1, 1, 1};
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
// データ項の計算
int data1 = ( bin(image[ i*wstep + j*bpp]) ) * lambda;
int data2 = (1 - bin(image[ i*wstep + j*bpp]) ) * lambda;
g->add_tweights( i*width + j, data1, data2);
// 平滑化項の計算
for(int d = 0; d < 4; d++){
int x = j+dx[d];
int y = i+dy[d];
if(0 <= x && 0 <= 0 && x < width && y < height){
g->add_edge( i*width + j, y*width + x,
kappa, kappa);
}
}
}
}
プログラム例 (3/3)
// maxflow/mincut
int flow = g->maxflow();
// 出力結果
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(g->what_segment( i*width + j ) == GraphType::SOURCE){
image_result[ i*wstep + j*bpp] = 255;
}
else{
image_result[ i*wstep + j*bpp] = 0;
}
}
}
delete g;
return 0;
}
実行例
入力画像
λ=10, κ=25
λ=20, κ=25
λ=90, κ=25
λ=130, κ=25
コンピュータビジョンへの応用例
画像セグメンテーション
• エネルギー関数
‒ データ項：輝度値の前景 or 背景の確率
‒ 平滑化項：近傍ピクセルとの類似度
Edge
Weight
Condition
n-link {p, q}
B{p, q}
{p, q} N
t-link {p, s}
λ · Rp( bkg )
p P,
p OUB
t-link {p, t}
K
p O
0
p B
λ · Rp ( obj )
p P,
p OUB
0
p O
K
p B
画像セグメンテーション例
Lazy Snapping
ボクセルデータのセグメンテーション
セグメンテーションの高精度化
• GrabCut
[C. Rother et al , SIGGRAPH2004]
‒ セグメンテーションの繰り返し処理により色分布を再学習
• 平滑化処理の繰返しによるグラフカットを用いた
画像セグメンテーション[永橋, 情処論2008]
‒ 色と形状を段階的に繰り返し再学習
平滑化処理の繰返しによるグラフカット[永橋, 情処論2008]
ステレオ
• エネルギー関数
‒ ラベル：視差
‒ サイト：左画像の画素
‒ データ項：左画像と右画像のピクセル値の類似度
‒ 平滑化項：近傍ピクセルの視差が同じかどうか
E(L) =
�
D(IL , IR , i, j, d) +
�
λ · δ(Li,j , Li+x,j+y )
スレテオ結果例
!"#$%&'()*$(+&#&(,&)$()*$-%".&#)/010$()2334)5))67#'%8)*".1)91:);&9&<)=&.1>?))@:)A$BC$9)DEFGH?)I:)*#&-&#1)DE:)$+)A$((H?)/:)J$<-$K$#$9)DE*;H)
Multi-way graph cuts
テクスチャ合成
Graph-cut textures
(Kwatra, Schodl,
Essa,SIGGRAPH2003]
Bobick 2003)
• Graph-cut textures
[Kwatra,
"
!
$
#
"
!
$
#
&
!"#$%&'()*$(+&#&(,&)$()*$-%".&#)/010$()2334)5))67#'%8)*".1)91:);&9&<)=&.1>?))@:)A$BC$9)DEFGH?)I:)*#&-&#1)DE:)$+)A$((H?)/:)J$<-$K$#$9)DE*;H)
%
%
(
Graph cuts for video textures
(
'
&
'
*
)
)
*
Graph-cuts video textures
(Kwatra, Schodl, Essa, Bobick 2003)
similar to “image-quilting” (Efros & Freeman, 2001)
3&+4%
/
!"#$%&'()*#&+,(-
.
0#12&'()*#&+,(-
3D generalization of “image-quilting” (Efros & Freeman, 2001)
結果
• まとめ
• Graph Cuts
‒ グラフ理論を用いたMRFのエネルギー最小化
• 大域最小解が得られる
‒ 応用例
• 画像復元
• セグメンテーション
• ステレオ
• テクスチャ合成