1 Introduction

이미지를 분할 영역들로 나누는 가짓수는 여러가지가 있지만, 그 중 어느 한 가지가 정말 ‘맞게’ 나눈 것인지 판단하는 일은 정말 어려운 일이다. 이를 위해 미리 주어진 사전 정보를 통해 판단하려는 베이지안 기반의 방법이나, 픽셀 수준보다 높은 상위 단계의 지식을 이용하여 이를 판단하려는 시도도 있었지만, 여전히 어떤 사전 정보나 지식을 사용할 것인지를 정하는 것조차 어렵기만 하다.

한편, 클러스터링 쪽 사람들에게서 사용되던 알고리즘이 이미지에 적용되어 이미지를 분할하는데 사용되는 방법들이 있다. Markov Random Field (MRF) 같은 것이 대표적인데, 여전히 최적해를 찾는 것은 계산적으로 어려운 문제이다.

이러한 배경에서 MRF와 비슷한 그래프 이론을 가져다 쓰면서도 MRF와는 달리 전역적인 최적해를 찾고자 하는 알고리즘으로 등장한 것이 Normalized Cuts 이다.

먼저 그래프를 정의해보자.

$$G = (V, E)$$

$$V $$ 와 $$ E $$는 각각 픽셀과 이웃 픽셀들을 연결하는 에지들이다. 각 에지는 가중치 $$ w(i, j) $$ 를 가지는데, 이는 픽셀 i와 j가 얼마나 비슷한지를 나타내는 값을 가진다. 따라서 V의 부분 집합 $$ V_{1} $$, $$ V_2 $$, ..., $$ V_m $$ 들은 자신의 내부에서는 가중치의 합이 높고, 서로 다른 부분 집한끼리는 가중치가 낮을 것이다.

# 2 Grouping as Graph Partitioning
Graph cut 이란 방법은 기본적으로 이진 분할로, 그래프 G를 서로 겹치지 않는 A와 B, 두 개로 나누는 방법이다. 이 때, cut 이라는 것은 다음과 같이 정의된다.
$$ cut(A, B) = \sum_{u \in A, v \in B}{w(u,v)}$$

즉 A와 B를 분리하기 위해서 끊어버린 에지들이 있고, 이 에지들이 가지는 가중치들이 합이다. 이 가중치가 가장 적은 cut을 구하는 방법이 minimum cut 이라는 방법이 나와있었다. 하지만 단순히 가중치가 적은 부분을 잘라내려하다보니 외지게 떨어져 있는 작은 부분이 존재할 경우, 이러한 작은 부분과 나머지 큰 부분이 min-cut으로 구해지는 경향이 있었다. 이를 해결하기 위한 대안으로 이 논문에서 정규화된 cut(Normalzied cut)이 제안되기에 이른다. N-cut의 기준은 다음과 같다.

$$Ncut(A, B) = \frac{cut(A, B)}{assoc(A, V)} + \frac{cut(A, B)}{assoc(B, V)}$$

$$assoc(A, V) = \sum_{u \in A, t \in V}{w(u, t)}$$

각 A, B 내에서 연결된 전체 가중치들을 고려하는 부분이 분모로 포함되어있다. 따라서 이 N-cut을 최소화시키려면 분모에 있는 두 assoc 또한 커질 필요성이 있게 된 것이다.

2.1 Computing the Optimal Partition

사실 논문에서 장장 한 페이지 분량으로 위의 N-cut을 이리저리 풀어내어 행렬 식으로 유도를 해놓았지만 모두 생략하고 마지막만 살펴보자.

$$\min_{x} N cut(x) = \min_{y} \frac{y^T (D-W) y } {y^TDy}$$

$$\text{with the condition } y(i) \in \{1, -b\} \text{ and } y^TD 1 = 0$$

못보던 기호가 나왔으니 조금 더 풀어보자면,

$$D $$ 는 N x N 짜리 대각행렬로, N은 각 픽셀들의 갯수이니, 픽셀 수 x 픽셀 수 만큼의 행렬이다. $$ D $$ 의 요소들은 $$ d(i) = \sum_{j}{w(i, j)} $$ 으로 픽셀 i 와 연결된 이웃 픽셀들과의 가중치 합이다.
$$ W $$ 도 마찬가지로 N x N 짜리 행렬인데, 이는 행-열 끼리 대응하는 픽셀들의 가중치를 기록해놓은 행렬이다. 따라서 이는 대칭행렬이다.
마지막으로, $$ y= (1+x) - b(1- x) $$, $$ b = \frac{k}{1-k} $$ , $$ k = \frac{\sum_{x_i>0}d_{i}} { \sum_{i}{d_i}}$$

복잡해보이지만, 일단 $$ x_i $$ 는 각 픽셀의 레이블로 우리가 구하고자 하는 값인데, 두 영역의 레이블로 1과 -1로 정의하였다. 그렇다면 k는 전체 중 레이블 1을 갖는 픽셀들의 $$d_i$$가 차지하는 비율이다. 이로부터 b는 레이블 1과 -1의 비율이 되겠다.

이리저리 복잡하게 유도해놓았지만 우리가 해야될 일은 제일 위에 있는 식을 최소로 만드는 y를 구하면 된다. 이 때, 제일 위에 있는 식의 형태는 Reyleigh quotient 형태로 y가 실수라면 다음과 같은 아이겐 벡터 문제로 이를 최소화하는 값을 구할 수 있다.

$$(D-W)y = \lambda Dy$$

여기서 식에 붙은 조건 때문에, 가장 작은 아이겐 벡터는 해답이 아니고 두번째로 작은 아이겐 백터가 해답으로 뽑힌다.

3 The Grouping Algorithm

요약하자면,

1. 이미지로부터 그래프 $$ G = (V, E)를 구성한다.
2. $$ (D-W)x = \lambda D x $$ 로부터 아이겐 벡터를 구한다.
3. 두 번째로 작은 아이겐 벡터을 이용하여 이미지를 분할한다.
4. 3의 결과에서 더 나눌 필요가 있다면 반복적으로 더 분할한다.

1에서 가중치는 한 픽셀 주변에서 특정 반경 r 내에 존재하는 픽셀들에게만 아래와 같이 주어진다.

$$
w_{i, j} = e^{\frac{ - \| F_{(i)} - F_{(j)} \| ^ 2}{ \sigma_I^2}} * e^{\frac{ - \| X_{(i)} - X_{(j)} \| ^ 2}{ \sigma_X^2}}$$

이 때, X는 위치, F는 픽셀 값이다.

2에서의 식은 Generalized eigensystem으로 풀릴 수 있는데, 우리는 두 번째로 작은 아이겐벡터만 필요하니 Lanczos의 방법으로 효과적으로 풀어낼 수 있다.

아이겐벡터가 구해진다면 의도된 것과 같이 레이블이 1과 -1이 나오는 것은 아닌데, 이를 분할하기 위해서 0을 기준으로 나누거나, 중간값을 이용하여 나누는 방법이 제안되고 있다.

4에서처럼 꼭 둘로 나누란 법은 없다. 필요하다면 이 방법을 두번 세번 여러번 적용하면 이 것이 Recursive Two-Way Ncut이 되는 것이다. 이 와는 달리, 미리 K-Mean 등을 통해서 Over-segmentation 된 결과를 가지고 모든 Segmentation된 영역을 식에 집어넣어 이용하는 방법(Simulttanous K-Way Cut with Multiple Eigenvectors도 제안되고 있다.

4 Experiments

사실 피쳐(Feature)인 F는 픽셀 값 뿐만 아니라, HSV로부터 뽑아낸 Color 값, 또는 DOOG 필터링 후의 방법 또한 함께 제안되고 있는데, Similarity를 표현할 수 있는 다른 피쳐가 있다면 얼마든지 사용할 수 있다.

실제로 구현해본 경험으로는 이웃이 될 수 있는 범위는 4, 8-connected 정도로는 어림없고, 반경을 4 픽셀 정도로 해야 제대로된 결과를 볼 수 있었다. 여기서는 Generalized eigenvalue를 Standard eigenvalue 로 변환하는 방법을 소개했지만, Scipy나 MATLAB 등에서 Generalized 형식도 직접 풀 수 있도록 함수를 제공하고 있으므로 그것을 이용하여도 좋겠다.