Medical Image Segmentation - Segmentation using graph model

1. Graph Model

Graph model은 foreground와 background를 분리하는 수학적 모델이다. 위 그림에서 보라색 부분이 foreground, 나머지가 background이다.

이 때 $P(x_1,x_2,\ldots,x_N/z_1,z_2,\ldots,z_N)$을 최대로 하는 $x$를 찾는 것이 목표이다.

위 식을 posterior probability라고 하는데 이를 바로 얻는 것은 어렵다. 따라서 bayes rule을 따라 likelihood와 prior probability term으로 구성된 식으로 변형한다.

$P(x_1,x_2,\ldots,x_N/z_1,z_2,\ldots,z_N)=\cfrac{P(z_1,\ldots,z_N|x_1,\ldots,x_N)P(x_1,\ldots,x_N)}{P(z_1,\ldots,z_N)}$

이 때 각 sample은 서로 독립이라고 가정하면 다음과 같이 변경이 가능하다.

$P(x_1,x_2,\ldots,x_N/z_1,z_2,\ldots,z_N)\propto\prod\limits_{i}^NP(z_i|x_i)\prod\limits_{i,j}P(x_i,x_j)$

그리고 markov random field를 적용해 해당 pixel의 주변에 위치한 pixel의 label $x_j$만 고려한다.

2. Optimization

최적화 문제를 풀기 위해서 앞서 구한 식을 변형할 필요가 있다. 아래 식과 같이 전체 항에 -log를 취하여 likelihood, prior probability term의 합으로 변형한다. 곱셈이 아니기 때문에 연산량 측면에서 유리하다.

$E=-\log(\prod\limits_{i}^NP(z_i|x_i)\prod\limits_{i,j}P(x_i,x_j))=\sum\limits_{i}^N\theta_i(z_i|x_i)+\sum\limits_{i,j}\theta_{i,j}(x_i,x_j)$

$-\log$의 부호가 음수이므로 반대로 $E$를 최소로 하는 $x$를 구하는 것이 최적이다.

$\argmin\limits_{x_1,\ldots,x_N}E$

3. Graph Cut - Max flow / Min cut

만약 $x$의 개수 $N$이 100라고 가정하면 모든 경우의 수는 $2^{100}$이다. 고려해야 할 경우의 수가 너무 많기 때문에 최적을 찾기가 어렵다. 이를 해결하기 위해 적절한 알고리즘을 사용할 필요가 있다. 그 중 하나가 Max flow / Min cut 알고리즘이다.

Source부터 Sink까지 낮은 capacity를 채워가며 가상의 물이 흐르고, 이 물에 의해 공간이 나뉜다고 생각하면 된다.

위 그림에서 source, sink와 연결된 화살표가 likelihood이고 동그라미끼리 서로 연결된 화살표가 prior probability이다. 먼저 좌측의 1, 6 path를 따라 Sink로 물이 흐르고, 해당 path의 capacity는 1만큼 감소한다. 좌상단의 1 path는 0으로 바뀌게 되므로, 이 path는 끊기게 된다.

다음으로 우측 9, 3 path를 따라 물이 흐르게 되고, 해당 path는 capacity가 감소한다. 그 결과, 우 하단의 3 path는 0이 되어 끊기게 된다.

같은 방식으로 가운데 위치한 1 path도 끊기게 되면 두 개로 즉, foreground/background로 분리가 된다.