[Technique] Graph cut

※이 내용은 edwith의 Medical Image Analysis강의를 참조하였음을 미리 밝힙니다.※

 

의료영상 segmentation에서 주로 쓰이는 기법으로 Graph cut과 Active contour model이 많이 쓰이고 있다. 그 중 graph cut에 대해서 자세히 알아보자.

 

핵심아이디어

 

 

먼저, 주어진 이미지에서 각 픽셀에 대한 컬러값을 observation으로 $z_i$로 표기하며 segmentation의 label값을 $x_i$이라 하자. 이제 $z_i$들과 $x_i$들은 변수로 작용하여 graph model에 적용하여 이들간의 상호 의존관계를 식($P(x_1, x_2, ..., x_n | z_1, z_2, ..., z_n)$)으로 표현할 수 있게 된다.

 

 

이 graph model의 식을 최적화하는 과정에서 Min cut / Max flow 방법을 통해 segmentatioin result를 구하는 방법이 graph cut이다.

 

최적화 과정 

 

$z_i$가 주어질 때 $x_i$의 확률을 구하는 것이므로 위의 식을 사후 확률(posterior probability)로 볼 수 있다. 이럴 경우 Bayes' rule에 의하여 가능도(likelihood = $P(z_1, z_2, ..., z_9 | x_1, x_2, ..., x_9)$)와 사전 확률(prior probability = $P(x_1, x_2, ..., x_9)$)의 곱을 $P(z_1, z_2, ..., z_9)$로 나눈 식으로 변환이 가능하다. 우리는 사후 확률을 최대화 시키는 $x_i$의 값들에 관심이 있는 것이기 때문에 고정되어 있는 $P(z_1, z_2, ..., z_n)$들의 값을 제외하고 가능도와 사전확률을 최대화 시키는 값을 고려하면 된다. 

 

가능도 (likelihood)

$P(z_1, z_2, ..., z_9 | x_1, x_2, ..., x_9)$ => Naive bayes assumption => $\prod P(z_i | x_i)$

가능도의 값을 구하는 것도 복잡한 과정이기에 하나의 가정을 추가한다. 바로 $x_i$들이 서로 독립적이라는 가정이라는 Naive bayes assumption이다. 이를 통해 가능도의 식은 $\prod P(z_i | x_i)$와 같이 나타낼 수 있게 된다.

 

사전확률 (prior probability)

$P(x_1, x_2, ..., x_9)$ => Markov reception field => $\prod_{(i,j)} P(x_i, x_j)$

사전확률을 구하는 과정도 내부에 많은 변수들이 존재하기 때문에 구하는 과정이 복잡하다. 따라서, $x_i$의 값 하나를 구할 때 $x_i$의 주변에 있는 값들 $x_{i-1}$, $x_{i+1}$ 등을 고려해주는 Markov random field를 적용해준다.

 

이를 적용해줌으로써 한 label의 상하좌우 대각선 label이 1값을 갖으나 중심의 label이 0이 되는 상황을 방지할 수 있도록 해준다. 

 

전반적으로 다시 한번 식을 보게 되면 $z_i$라는 관측값들이 주어짐과 동시에 $x_i$라는 label들이 값을 갖게 되고 (= likelihood term), 이때 $x_i$들의 label값들이 smooth하게 되어야 한다는 것(= prior term)이다. 

 

위의 사후확률을 최대화하는 $x_i$값들만 구하는 것이기에 사후확률의 식을 단조증가함수나 단조감소함수를 통해 나타내어도 상관이 없다. 사후확률의 식을 아래와 같이 지수로 나타내면

곱으로 나타내어지던 가능도와 사전확률이 합으로 나타내게 되어진다. 이를 통해 좀 더 쉽게 접근할 수 있게 되었다.

 

likelihood term

픽셀의 값($z_i$)이 blue일 때 label($x_i$)의 값이 0일 것이라는 하나의 가정하에서 $x_i$의 값이 0인 경우 값이 작아지도록 likelihood term이 나오게 된다.

 

prior term

boundary(픽셀값들의 차이가 큰 경우)에서는 값이 작아지고 아닌 경우에는 작아지도록 prior term이 나오게 된다.

 

Min cut / Max flow

픽셀값들을 노드로 하여 그래프 모델에 적용해보자. 픽셀값들에 대한 label이 0이 나오는 경우는 source로 1이 나오는 경우는 target로 보면 아래의 그림과 같이 나타낼 수 있다.

source에서 물을 흘려보내주어 아래로 침수되는 과정을 생각해보자. 중간의 노드들간에 이동이 이루어질 수 있다. 

 

노드들 간의 이동이 이루어질 수 있는 횟수가 있는데 0이 되면 cut이 된다. 최종적으로 이들의 cut된 부분으 segmentation이 이루어지는 것이다.

 

 

 

 

-히비스서커스-