#10 Image Segmentation

1. Graph Cuts for Segmentation

Graph Cuts는 이미지에서 Background와 Object를 분리하는 방법으로 그래프 이론과 Energy Minimization에 기반한다. 이 과정에서 각 픽셀은 그래프의 노드로 표현되며 노드 간 연결(엣지)을 통해 관계를 정의한다.

1.1. 그래프 정의

1.1.1. 노드(Node)

각 픽셀은 그래프의 노드가 되며, Source(S)와 Sink(T) 노드가 추가로 정의된다.

• Source 노드(S): Object를 나타내는 노드.
• Sink 노드(T): Background를 나타내는 노드.

1.1.2. 엣지(Edge)

두 종류의 엣지가 있다.

t-link (Terminal Link)

• 각 픽셀 노드가 Source(S)나 Sink(T)와 연결되는 엣지.
• t-link의 가중치는 해당 픽셀이 Object 또는 Background에 속할 확률로 설정된다.

n-link (Neighbor Link)

• 인접 픽셀들 간의 연결을 나타내는 엣지.
• n-link의 가중치는 두 픽셀 간의 유사성(색상, 밝기 등)을 기반으로 설정된다.

1.2. Energy Function on a Graph

Energy Function은 Segmentation 품질을 평가하는 기준으로, 두 가지 항목으로 구성된다.

1.2.1. Data Term

• 각 픽셀이 Object(Source)나 Background(Sink)에 속할 확률에 기반하여 결정된다.
• 예: 픽셀 값(색상, 밝기 등)을 기반으로 Histogram 또는 Gaussian 모델로 Source와 Sink의 확률 분포를 계산하여 비용을 설정.
• 직관적으로, 픽셀이 Source에 가까울수록 Dp​(1)이 작고, Sink에 가까울수록 Dp​(0)이 작다.

1.2.2. Smoothness Term

• 이웃 픽셀 간의 관계를 표현하며, 경계의 부드러움을 유지하는 역할을 한다.
• 일반적으로 두 픽셀 ppp와 qqq의 색상 차이에 반비례하여 설정된다.

1.3. Min-Cut을 통한 최적화

위 Energy Function E(L)를 최소화하기 위해 그래프의 t-link와 n-link를 사용하여 Min-Cut 알고리즘을 수행한다. 결과적으로, Dp(Lp)는 개별 픽셀의 Source/Sink 소속을 결정하며, Vp,q​(Lp​,Lq​)는 이웃 픽셀 간 경계를 부드럽게 유지한다.

 

무방향 그래프에서의 Min-Cut은 그래프를 두 개의 부분으로 나누는 컷들 중에서 컷의 가중치 합이 가장 작은 것을 찾아야 한다.

 

2. K-means Clustering

1. 데이터를 k개의 군집으로 나눈다.
2. 데이터 중 k개를 랜덤하게 중심으로 잡는다.
3. 각 중심에서 데이터까지의 유클리디안 거리를 기준으로 데이터를 각각의 군집으로 나눈다.
4. 각 군집에 대해 평균(중심)을 계산하여 새로운 중심으로 설정한다.
5. 기존의 중심과 새로운 중심의 차이가 특정 기준 이하가 되면 반복을 멈춘다.

초기 seed 값이 K-Means의 최종 결과에 중요한 영향을 미치며, 동일한 데이터를 사용해도 여러 번 실행할 경우 결과가 다를 수 있다.

3. SLIC Superpixels

SLIC(Superpixel Linear Iterative Clustering)은 K-means Clustering을 이미지 처리에 맞게 변형한 방법이다. 이를 알아보자.

3.1. K-means Clustering과 SLIC Superpixels의 차이점

K-means Clustering은 다음과 같은 특징이 있고 이는 SLIC Superpixels와 다른 점이다.

• 전체 pixel을 대상으로 각 pixel이 어떤 cluster에 속할지 결정한다.
• 단순히 pixel값(예: RGB와 같은 color 값)만을 기준으로 clustering한다.

3.2. 이미지의 특성에 맞게 변형된 SLIC Superpixels

3.2.1. K개의 Superpixels 생성: K개의 Cluster, 크기는 S

K개의 superpixels를 생성한다면 K개의 cluster가 생긴다는 것이다. 즉, K값이 클수록 각각의 Superpixel의 크기가 작아지며 세부적으로 나뉘게 된다.

 

처음에 SLIC는 K개의 Superpixel로 나누기 위해 각 Superpixel의 초기 중심을 설정한다. 이 초기 중심들은 각 S×S 크기 격자의 중심에 배치된다.

S의 크기, N은 전체 pixel의 수

3.2.2. Superpixel을 결정하는 탐색 범위: 2Sx2S

K-means가 전체 pixel을 비교하는 것과 달리 SLIC은 Superpixel의 중심에서 반경 2S내의 영역만 탐색한다.

 

반복 과정에서 각 Superpixel의 중심점은 cluster에 속한 pixels의 평균 위치로 이동한다. 중심점이 이동하면 Superpixel의 크기와 모양이 변경될 수 있다.

3.2.3. 거리 계산: 색상 차이뿐만 아니라 공간적 위치도 고려

SLIC은 pixel 간의 clustering 기준으로 단순히 색상 차이뿐만 아니라 공간적 위치도 고려한다. 이 때 각 요소가 dominant하지 않게 정규화 계수를 적용한다.

• Color 계산: 컬러 차이는 값이 클 수 있으므로 Regularizer (m)를 사용해 조정
• Spatial 계산: 위치 차이는 Superpixel 크기 S를 이용해 정규화

3.3. 거리 계산식

K-means Clustering은 전체 pixel에 대해서 했지만 얘는 다르다. 일단 K개로 나눈다했으면 K개의 superpixel이 있는 거다. 그만큼 크기로 K가 커지면 superpixel의 크기도 작아진다. 

3.4. 예제

다음과 같은 점을 주의하자.

• 거리에 대해 계산할 때 아마 시험에서는 color가 아닌 grayscale로 나올 듯 하다. color 이미지 상에서 거리를 계산하라는 문제가 나올 수 있음
• color와 spatial term에 대해 각각 분모가 컬러에는 m, spatial에는 S가 나눠줘있었는데 m이 분자로 올라오는 거 인지
• SxS가 원래는 기본으로 되어있다가 2Sx2S만큼 탐색해서 값이 바뀌는 거 인지. 이후 새 중심 위치가 몇이면 그만하겠죠~
• m이 클수록 정규화가 잘된다는 것은 spatial 차이를 더 우세하게 계산되므로 superpixel이 더욱 정규적이고 고른 크기를 유지하기 때문이다.