MRF and MAP Inference

 

* 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Interactive Segmentation

물체의 foreground, background pixel을 구분하는 프로그램을 구현해보자. 무엇이 foreground인지 알려주지 않으면 어렵기 때문에 아래처럼 사람이 부분적으로 labeling을 한다.

 

 

 

 

 

그리고 labeling한 pixel에 대해 color space상에 둬서 distribution을 알 수 있다. 그 다음에 labeling하지 않은 pixel에 대해서 MLE(Maximum likelihood estimation)을 사용하면 pixel마다 classify가 가능하다.

 

 

 

 

하지만 위의 그림처럼 noise가 많이 나오게 되는데, 위의 방법이 주변 pixel간의 관계를 고려하지 않고 pixel별로 independent하게 estimation을 진행하기 때문이다. 이를 해결하기 위해 MRF(Markov Random Field)가 제안된다.

 

 

 

Markov Random Field

서로 다른 노드들이 fully connected인 노드의 집합을 clique라 하고, 그것이 최대의 노드 개수로 이루어지면 maximal clique라고 한다. 아래의 grid에서는 인접한 pixel pair가 maximal clique이다. 한 픽셀의 probability distribution은 주변 4개의 maximal clique의 곱으로 나타낼 수 있다. K가 커질수록 옆에 있는 pixel 분포와 비슷하게 만들어진다. 

 

 

 

 

위에서 더 발전하여 observation에 대한 확률을 추가하면 joint probability는 아래와 같다.

 

 

F는 likelihood, G는 prior에 해당된다. 그리고 전체 p를 최대화하는 posterior를 maximize하는 문제이다.

-> MAP(Maximum a Posteriori)

 

결국 hidden state x를 찾는 문제인데, 위의 식에서 log를 취해 energy minimziation 문제로 만들 수 있다.

 

 

Segmentation 문제 뿐만 아니라 대부분의 컴퓨터 비젼 문제는 Engergy minimization 문제로 변환할 수 있으며, 이를 푸는 방법에는 Belief Propagation, Graph Cuts 등의 방법이 있다.

 

 

 

Belief Propagation Algorithm

Reparameterization

 

 

 

 

위의 그래프에서 각 노드의 숫자는 해당 label을 가졌을 때 unary term 이고, 노드 간에 이어진 line의 숫자는 pairwise term이다. 오른쪽 표처럼, label의 경우에 따라 생기는 energy를 계산할 수 있다. 빨간색으로 표시한 숫자처럼, 하나의 노드에 전체적으로 같은 에너지를 더하고 나머지에 같은 에너지를 빼면 전체 에너지의 변화는 없다. 이런 식으로, 전체 energy의 변화없이 새롭게 parameter를 구성하는 것을 reparamterization이라 한다. 

 

여기서 이전 노드에 대해 energy 합을 0으로 둔다면 그 전 노드에 대해 고려하지 않고 다음을 계산할 수 있을 것이다.

 

 

Min-marginal

 

 

 

 

위의 그림에서 전체 energy를 최소로 하는 label은 $x_i = 1, x_j = 0$이다. 이처럼 전체 그래프를 두 개의 노드간의 에너지 최소화 (min-marginal) sub problem으로 나눌 수 있다.

 

 

Three variables

 

 

 

 

위와 같이 3개의 node에 대한 energy term이 있다 하자. $x_j =1$은 $x_i = 1$을 선택하는게, $x_j = 0$은 $x_i = 1$을 선택하는 것이 energy가 작다. 이를 선택하고 reparameterization을 진행하면 아래와 같다.

 

 

 

 

위와 같은 방법으로, $x_k = 1$은 $x_j = 1$, $x_k = 0$은 $x_j = 0$을 선택한다. 이를 통해 reparameterization을 진행하면 아래와 같다.

 

 

 

 

최종적으로, energy가 작은 조합은 $x_i = 1, x_j = 0, x_k = 0$이다.

 

하지만, Belief propagation algorithm의 경우 cycle이 존재할 경우, 수렴이 되지 않을 수 있다. 즉, convergency를 보장해주지 않는다. 그리고 image의 경우 4개의 neighborhood가 있는데 무엇을 먼저 결정하는지도 중요하다.

 

 

 

Graph Cuts Algorithm

st-Mincut problem

아래 그림처럼 가상의 source, sink(target)을 두고 하나의 cut을 정해보자. 그러면 source에 포함된 노드는 1로 assign, target에 포함된 노드는 0으로 assign하면 cut에 해당되는 cost들이 energy가 될 것이다. 즉, 이는 minimum cut problem을 푸는 것과 동일한 문제가 된다.

 

 

 

 

 

 

Min cut을 푸는 문제는 Max flow를 푸는 문제와 같으며, 이는 Ford-Fulkerson algorithm등의 augmenting path based algorithm으로 풀 수 있다. 이 알고리즘은 요약하면 아래와 같다.

 

1. Source에서 sink로 가는 positive capacity를 가지는 augumenting path를 찾는다.

2. 찾은 path에 capacity가 허용될 때까지 flow를 push한다.

3. 더이상 augumenting path가 없을 때까지 반복한다.

 

 

예를 들어, 두개의 노드간의 에너지 관계식이 아래와 같을 때 그래프는 다음과 같다.

 

 

 

 

 

Graph cuts for multi-label problems

위의 maximum flow 문제는 bianary label 에 대한 문제로 한정되어 있다. 통상적으로 Moving making algorithm을 사용하여 multi-label 문제에 대해서도 푼다.

 

 

 

 

 

위의 그림처럼 search window를 설정하여 그 window내에서 local minima를 찾는다. Multi label 문제에 대해서도 move space를 bianary label 문제로 축소하여 local minima를 찾을 수 있다.

 

 

 

 

기존 solution $x_1$과 Move하여 두번째 solution $x_2$를 얻어냈을 때 새로운 solution은 다음과 같다.

 

$x = t x_1 + (1-t) x_2$

 

 

Move를 하는 방식은 두개의 방법이 존재한다.

 

1. Expansion move : 기존 label을 유지할 것인지 새로운 label을 assign할 것인지 결정하는 방법

2. Swap move : Label을 바꿀지 말지를 결정하는 방법

 

 

 

위에서 설명한 Graph cut 알고리즘을 이용해 stereo matching 등의 다양한 컴퓨터비젼 문제에 활용 가능하다. 아래처럼 MRF를 어떻게 설정하느냐에 따라 다르게 추정된다.