Digital Image Processing - MRF / Graph Cuts

---

Spatial similarity

검은 배경에 흰색 디스크가 있는 이미지를 각 픽셀의 색을 확률에 따라 독립적으로 칠하면 아래와 같이 noise가 굉장히 많이 나타난다. 이러한 결과는 이미지는 공간적인 관점에서 연속적이라는 사실을 반영하지 않았기 때문이다.

이러한 문제를 해결하기 위해 인접한 픽셀과의 관계를 반영한 아래의 식을 이용하면 픽셀의 label을 더욱 잘 예상할 수 있다.

Individual predictions 부분을 보면 말 그대로 각 픽셀 단위의 연산이다. yi는 0(background) 또는 1(foreground)로 labeling되는 픽셀 값이고 theta는 알고리즘의 매개변수, data는 raw image 자체이다.

Pairwise predictions 부분은 yi(해당 픽셀), yj(인접한 픽셀)을 이용하여 edge 단위로 픽셀간의 관계를 파악하는 부분이다.

Π는 모든 원소의 곱을 표현하는 기호이다.

위와 같이 -log를 취하는 방식으로 그전에 살펴본 식을 확률의 최대화 과정에서 에너지 최소화 과정으로 바꿔준다. 또한 log를 씌우면 모든 원소의 곱을 이용하는 식을 모든 원소의 합을 이용하는 식으로 단순화하는 효과도 있다.

---

Markov Random Fields

Markov Random Fields(MRF)는 아래와 같이 각 node와 node간의 관계를 말하는 edge를 이용하여 표현하는 그래프 표현이다. 

위의 예시에서 12개의 node가 있어서 2^12가지의 경우가 있고 해당 조합들을 분석을 해야하는데 이는 벌써 4096개의 case이다. 이를 현실의 500x500 pixel 이미지를 기준으로 생각해보면 2^250000인데 이는 생각하기도 어려운 수이다. 이러한 연산은 불가능하다. 이를 해결하기 위해 Graph Cuts 기법을 이용한다.

---

Graph Cuts

Graph Cuts는 그래프 이론을 기반으로 하며, 노드들 사이의 edge을 특정 기준에 따라 cutting하는 방식으로 문제를 해결한다.

Graph Cuts는 그래프의 노드를 두 개의 집합으로 나눈다. 이때, 각 집합은 그래프의 source node와 sink node에 대응된다. 목표는 소스와 싱크 사이의 edge를 끊을 때, 그 edge들의 가중치 합이 최소가 되도록 하는 것이다. 이렇게 하여 그래프를 최적으로 분할한다.

이러한 알고리즘을 활용한 GrabCut기법에 대해서 살펴보자.

---

GrabCut

GrabCut Segmantation은 아래와 같이 사용자가 rough하게 틀을 잡아주면 해당 구역에서 segmentation을 해내는 2000년대 초반을 풍미한 segmentation 기법이다.

Graph Cuts를 이용한 기법은 지속적으로 발전해왔는데 결국 2004년 공개된 GrabCut이 평정하게 되었다.

예시를 좀더 살펴보자.

아래와 같은 경우에는 segmentation 성능이 떨어진다.

GrabCut을 활용하여 조금 변형한 Lazy Snapping이란 기법도 있다.

 

결국 Graph Cuts은 Deep Learning에게 자리를 뺐겼지만 여전히 고성능의 알고리즘임은 틀림이 없다.

마지막으로 Graph Cuts의 장단점을 살펴보고 마치자.
장점
1. 빠른 추론 속도: Graph Cuts는 계산적으로 효율적이며 빠른 추론을 가능하게 한다.
2. 데이터 가능성 및 사전 정보 통합: 이 방법은 데이터의 가능성(likelihood)과 사전 지식(priors)을 모델에 통합할 수 있어, 보다 정확한 결과를 도출할 수 있다.
3. 다양한 문제에 적용 가능: 스테레오 비전, 이미지 라벨링, 인식 등 다양한 문제에 적용할 수 있는 범용성을 가지고 있다.

단점
1. 항상 적용 가능한 것은 아님: 모든 유형의 문제나 데이터에 적합하지 않을 수 있다.
2. 단항항 필요: Graph Cuts는 주로 단항항(unary terms)을 필요로 한다. 이는 하향식 세분화(bottom-up segmentation)에는 사용되지 않는다는 것을 의미한다.

---