Markov Random fields with Efficient Approximations
[cite]10.1109/CVPR.1998.698673[/cite]
오래전 글의 백업입니다.
2011년 12월 20일
기존의 binary segmenation에서 사용되는 min-cut/max-flow을 확장하여 multi-way cut problem을 이용하고 있습니다.
즉, foreground/background의 binary가 아닌 여러 영역의 segmentation을 고려한 방법이나 이는 NP-Complete problem으로 이야기를 하며 이를 approximation 하기 위하여 iterative 한 방법을 소개하고 있습니다.
segmentation label간의 쌍을 구성하고 각 반복마다 각 label쌍에 대해서 min-cut/max-flow를 반복적으로 수행하여 local minimum을 얻는 것이 주요 내용입니다.
주요 알고리즘은 아래와 같습니다.
alpha-beta swap
--------------------------
1. arbitrary labeling f 에서 시작
2. 각 pair of label alpha, beta 에 대해서
2.1 alpha beta swap (min cut) 을 수행
2.2 낮은 것을 찾으면 저장하고 다른 pair 에 대해서 2를 반복
3. 2단계에서 한번도 낮을 것을 찾지 못하면 종료
a-expansion
1. arbitrary labeling f 에서 시작
2. 각 label에 대해서 다음을 반복
2.1 a-expansion 수행 (선택된 label, alpha 와 나머지 것들 alpha bar 에 대하여 min-cut)
2.2 낮은 것을 찾으면 저장하고 다른 label에 대해서 2를 반복
3. 2단계에서 낮을 것을 찾지 못하면 종료