Fast Approximate Energy Minimization via Graph Cuts
[cite] 10.1109/34.969114 [/cite]
지난 번 정리했던 수퍼픽셀 외의 다른 분야에서도 많이 참조되고 있는 alpha-beta swap, alpha expansion 방법에 대해 정리해보고 넘어가도록 하자.
1 Energy minimization in early vision
픽셀 $ p \in P $ 와 지역적으로 변하는 레이블 $ l \in L $ 을 할당하는 문제는 모션 추적이나 스테레오, 이미지 복원에서 많이 정의되는 모델이다. 레이블링 된 한 상태 f 에서 각 픽셀 p는 레이블 $ f_p \in L $ 로 할당된다. 이 상태 f의 에너지는,
$$E(f) = E_{smooth}(f) + E_{data}(f) \\
= \sum_{\{p, q\}\in N}{V_{p, q}(f_p, f_q)} + \sum_{p \in P}{D_p(f_p)}$$
로 정의된다. 두번째 항은 Data 항으로 픽셀 p가 레이블 $ f_p $로 할당될 때의 페널티를 나타낸다. 즉, 픽셀 p에 할당된 레이블에 대한 평가를 뜻한다고 볼 수도 있겠다. 첫번째 항은 이웃인 픽셀 p, q에 대해 그 레이블이 서로 불연속인 것에 대한 페널티로 해결하려는 문제에 따라 그 의미가 약간씩 달라지고 정의하는 방법에 따라 알고리즘의 성능에 영향을 많이 미친다.
이제 우리가 해야할 일은, 문제에 따라 적절한 모델을 선택하고 이 에너지를 최소화하는 상태 f를 찾는 것이다. 하지만 늘 그렇듯, 완벽한 해를 찾는 문제는 NP-hard 문제다.
2 Related works
기존의 Iterated Conditional Modes (ICM)과 같은 방법들은 standard move, 즉 레이블의 상태가 하나씩 바뀌는 방법으로 그 속도가 느리고, 그 결과도 local minimum에 빠지가 쉬웠다.
이제 이야기할 swap move, expansion move 두 알고리즘은 standard move가 아닌 한번에 많은 수의 레이블 상태가 바뀌는 large move 방법으로 비교적 빠르면서도 에너지의 global minimum에 가까운 상태를 계산해보고자 한다.
3 Overview of our algorithms
먼저 논문에서 이야기 하는 alpha-beta-swap, alpha-expansion이 무엇인지 정의하고 넘어가자. 이미지는 이미 각 픽셀에 레이블 $ f_p \in L $ 이 할당되어있는 상태이다.
두개의 레이블을 콕 집어서 둘간의 레이블을 교환하면 alpha-beta-swap이다. 즉 두개의 레이블 a, b를 선택하였을 때, 레이블 a 픽셀의 일부는 b로, 레이블 b의 픽셀 일부는 a로 교체되는 move를 alpha-beta-swap 이라 한다. 다른 레이블은 변경되지 않는다.
한편, 하나의 레이블 a를 선택하여, 이미 레이블 3으로 지정된 픽셀은 다른 레이블로 변경되지 않고, 레이블 a가 아닌 픽셀 중 일부가 3으로 변경된다면 이를 alpha-expansion 이라고 한다. 즉, 이는 레이블 a가 확장되는 것처럼 보인다.
위의 swap 혹은 expansion 알고리즘을 반복적으로 수행함으로써 에너지가 최소화되는 레이블 상태를 찾을 것이다. 알고리즘은 아래와 같다.
- Start with an arbitrary labeling $ f $
- success := 0
- For each pair of labels $ \{ \alpha, \beta \} \in L $
- Find $ \hat{f} = \mbox{argmin }E(f') $ among $ f' $ within one alpha-beta-swap of $ f $
- If $ E( \hat{f} ) \lt E(f) $, set $ f := \hat{f} $ and success := 1
- If success = 1 goto 2
- return $ f $
- Start with an arbitrary labeling $ f $
- success := 0
- For each labels $ \alpha \in L $
- Find $ \hat{f} = \mbox{argmin }E(f') $ among $ f' $ within one alpha-expansion of $ f $
- If $ E(\hat{f}) \lt E(f) $, set $ f := \hat{f} $ and success := 1
- If success = 1 goto 2
- return $ f $
쉽게 이야기 하면, 모든 alpha-beta 혹은 alpha에 대하여 swap 혹은 expansion 알고리즘을 수행하여 에너지가 더 이상 낮아지지 않을 때 까지 반복한다.
4 Finding the optimal swap move
그렇다면 위의 알고리즘에서 alpha-beta swap은 어떻게 이루어질 것인가? 그 해답은 적절한 그래프를 구성한 뒤 Graph cuts, 정확히 말하면 s-t cut을 이용하여 구할 수 있다.
먼저 s-t cut 방법에 따라 source, sink 노드 2개를 추가한다. 그리고 swap하고자 하는 두개의 레이블 alpha, beta에 해당하는 노드(픽셀)들을 두 노드에 모두 연결(t-link)한다. 이 때, source에 연결된 노드의 가중치는 $ t_p^{\alpha} $, sink에 연결된 노드의 가중치는 $ t_p^\beta $ 라고 한다. 그리고 픽셀들 끼리의 가중치는 $ e_{\{p, q\}} $ 라고 하자.
모델에 따라 다음의 가중치를 사용하여 그래프를 구성하고 s-t cut을 수행한다.
| edge | weight | for |
|---|---|---|
| $ t_p^{\alpha } $ | $ D_p(\alpha) + \sum_{ q \in N_p \mbox{ and } q \notin P_{\alpha \mbox{ or } \beta} } V(\alpha, f_q) $ | $ p \in P_{\alpha} \mbox{ or } P_{\beta} $ |
| $ t_p^{\beta } $ | $ D_p(\beta) + \sum_{ q \in N_p \mbox{ and } q \notin P_{\alpha \mbox{ or } \beta} } V(\beta, f_q) $ | $ p \in P_{\alpha} \mbox{ or } P_{\beta} $ |
| $ e_{p, q} $ | $ V(\alpha, \beta) $ | $ \{p, q\} \in N \\ p, q \in P_{\alpha, \beta} $ |
s-t cut 방법에 따라 t-link가 cut이 되었는지 여부에 따라 alpha, beta 레이블의 상태가 결정된다.
5 Finding the optimal expansion move
expansion도 swap와 매우 비슷한 구성이다. alpha-beta-swap에서 beta 대신 non-alpha, 즉 alpha가 아닌 모든 노드를 beta로 묶어 생각하면 된다. 한가지 차이가 있다면, alpha와 non-alpha 레이블이 서로 이웃해 있는 노드 p, q가 있을 때의 경우이다. 이때는 둘을 연결한 link를 삭제하고 중간에 auxiliary 노드 x를 추가한다. 그리고 p - x, x - q, x - sink를 연결하는 link 3개를 추가한다. 이들의 가중치는 $ e_{\{p, x\}} $, $ e_{\{x, q\}} $, $ t_{x}^{\bar{\alpha}} $ 이다. 다 만들어진 그래프는 alpha와 non-alpha 사이에 막이 하나 있는 것 같은 모양새가 될 것이다. 그래프의 각 가중치는 아래와 같이 설정한다.
| edge | weight | for |
|---|---|---|
| $ t_p^{\bar{\alpha} } $ | $ \infty $ | $ p \in P_{\alpha} $ |
| $ t_p^{\bar{\alpha} }$ | $ D_p(f_p) $ | $ p \notin P_{\alpha} $ |
| $ t_p^{\alpha}$ | $ D_p(\alpha) $ | $ p \in P $ |
| $ e_{\{p, x\}} $ | $ V(f_p, \alpha) $ | $ \{p, q\} \in N \mbox{, } f_p \neq f_q $ |
| $ e_{\{x, q\}} $ | $ V(\alpha, f_p) $ | $ \{p, q\} \in N \mbox{, } f_p \neq f_q $ |
| $ t_{x}{\bar{\alpha}} $ | $ V(f_q, f_p) $ | $ \{p, q\} \in N \mbox{, } f_p \neq f_q $ |
| $ e_{\{p, q\}} $ | $ V(f_p, \alpha) $ | $ \{p, q\} \in N \mbox{, } f_p = f_q $ |
alpha 노드에 대해서는 무한대의 가중치가 붙어있으므로 cut에 포함되지 못하기 때문에 alpha 레이블의 픽셀은 줄어들지 않고 확장될 수 밖에 없다.
마찬가지로 s-t cut의 결과에 따라 확장된 alpha 레이블을 알아낼 수 있다.
9 Conclusions
모델을 어떻게 설정하느냐에 따라 결과가 매우 달라지는데, 사용되는 목적도 다르므로 수식을 잘 설정하여야 한다. 또한 이 모델은 swap 알고리즘은 semi-metric, expansion은 metric 성질을 만족해야 하는데 이는 논문을 참고하도록 하자.