논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

GrabCut – Interactive Foreground Extraction using Iterated Graph Cuts

(10.1145/1186562.1015720)

1 Introduction

주어진 이미지를 foreground와 background로 분리하는 작업은 이미지 편집에서 아주 중요한 작업입니다. 저자는 복잡한 이미지에서도 효과적으로 잘 작동하는 interactive 방식의 foreground와 background의 분리를 한 방법을 제안합니다. 분리된 foreground는 배경과 잘 어우러지도록 투명도를 갖는 alpha-matte를 가지고 있게 됩니다. 이 방법은 최대한 사용자의 입력을 적게 함과 동시에 최대한의 성능을 내는 것을 목표로 하였습니다.

1.1 Previous approaches to interative matting

먼저 기존의 잘 알려진 방법들을 간단히 살펴보도록 하겠습니다.

Magic Wand 사용자가 특정 위치나 영역을 지정하면, 그와 연결된 픽셀들 중 그 차이가 특정 값 이내인 픽셀들을 선택하는 방법입니다. background와 foreground의 픽셀 값 분포가 서로 겹치면 곤란해집니다.

Intelligent Scissors Mortensen, Barret의 제안한 방법으로 마우스를 움직여가며 대강의 포인트를 seed로 지정하여 영역을 선택하는 방법입니다. 실시간으로 현재 커서의 위치와 직전 seed 위치 사이의 minimum cost path를 계산하여 실시간으로 보여줍니다. 현재 표시되는 경로가 마음에 들면 경로를 고정하고 현재 위치를 다음 seed로 지정합니다. 이를 반복하여 영역을 선택하게 됩니다. 이 바업의 경우 텍스쳐가 복잡한 영역이거나 아예 텍스쳐가 없는 영역의 경우 minimum cost path가 유일하지 않아 문제가 됩니다.

Bayes matting 사용자가 정의한 trimap ( $$ T = { T_B, T_U, T_F } $$ )을 바탕으로 투명도를 갖도록 컬러 분포를 모델링합니다. 사용자의 안쪽 영역과 바깥 영역 입력의 사용자 입력이 필요합니다.

Knockout 2 Trimap을 사용하는 Bayes matting과 비슷한 방법입니다.

Graph Cut Bayes Matting과 trimap, 확률 컬러 모델을 모두 갖는 방법입니다. 후에 따로 설명하도록 하겠습니다.

Level sets 편미분 방정식을 이용하여 에너지 최소화 방법을 통하여 풀어냅니다. 에너지를 정의하는 방법이나, 초기화 방법에 따라 결과가 달라질 수 있습니다.

1.2 Proposted system

Alpha matting 방법은 Trimap 중에서 $ T_u $ 영역에 대하여 연속적인 값을 갖도록 투명도를 할당하기 위해 사용하는 방법입니다. 이 방법을 이용하여 연기나 머리카락, 나무 등의 경계가 애매하거나 복잡한 텍스쳐를 갖기 때문에 배경과 물체를 정확하게 구분할 수 없는 물체에 대해서도 대응할 수 있게 됩니다.

이 논문에서는 반복적인 graph cut 방법을 이용하여 투명도가 적용되지 않은 hard segmentation을 먼저 수행한 후에, border matting 방법을 적용하여 foreground의 경계 부분에 투명도를 할당한 다음, 나머지 배경 부분은 완전히 투명하게 만드는 것으로 물체를 분리해낼 것입니다.

2 Image segmenation by graph cut

먼저 Boykov, Jolly의 graph cut 방법을 설명하고자 합니다. 후에 GrabCut에서는 이 방법의 확장된 버전을 사용할 것입니다. 사전에 주어진 trimap $ T $ 를 바탕으로 흑백 이미지에서 segmentation 작업을 시작합니다.

각 픽셀 $ \mathbf{z} = ( z_1, …, z_n , … , z_N) $는 gray 값을 가지며, segmentation 결과로 각각 투명도 값 $ \underline{\alpha} = (\alpha_1, …, \alpha_N) $을 갖습니다. 투명도는 보통 0 에서 1 사이의 값을 갖지만, hard segmentation의 경우 0 아니면 1의 값이 할당됩니다. 이미지의 background와 foreground 분포에 대한 파라미터는 다음과 같이 히스토그램으로 표현됩니다.

$$\underline{\theta} = \{ h(z; \alpha), \alpha = 0, 1 \}$$

이제 이미지와 $ \underline{theta} $가 주어졌을 때, 적절한 $ \underline{ \alpha } $를 찾기 위해서 energy minimisation 방법을 사용할 것입니다.

우리가 최소화할 에너지 E는 Gibbs 에너지 형태로 다음과 같이 표현됩니다.

$$\mathbf{E}(\underline{\alpha}, \underline{\theta}, \mathbf{z}) = U(\underline{\alpha}, \underline{\theta}, \mathbf{z}) + V(\underline{\alpha}, \mathbf{z})$$

Data term $ U $는 투명도가 이미지의 히스토그램에 얼마나 잘 부합하는지를 평가합니다. 식에 따르면 한 색상이 일관되게 같은 레이블로 할당될 수록 그 에너지가 감소하도록 되어있습니다.

$$U(\underline{\alpha}, \underline{\theta}, \mathbf{z}) = \sum_{n} – \log h(z_n ; \alpha_n)$$

smoothness term인 $ V $는 다른 레이블로 구분된 이웃 간의 픽셀 값 차이가 클 수록 에너지가 감소합니다.

$$V(\underline{\alpha}, \mathbf{z}) = \gamma \sum_{(m, n) \in C} dis(m, n)^{-1} [\alpha_n \neq \alpha_m] \exp( -\beta (z_m – z_n)^2)$$

$$\beta = (2 \text{ expectation}((z_m – z_n)^2) )^{-1}$$

이제 주어진 이미지에 대하여 이 식으로 표현되는 에너지가 적은 상태를 찾으면 background와 foreground를 분리할 수 있습니다. 이것은 주로 minimum cut 알고리즘을 이용하여 찾을 수 있습니다.

$$\hat{\underline{\alpha}} = \arg \min_{\underline{\alpha}} E(\underline{\alpha}, \underline{\theta})$$

지금부터 이 graph cut을 변경하여 GrabCut으로 확장하고자 합니다. Gray 이미지를 Gaussian Mixture Model (GMM) 을 이용하여 컬러 히스토그램을 사용하고, 최적 에너지 상태를 찾기 위해서 반복적인 방법으로 교체를 할 것입니다. 그리고 초기값으로 받는 사용자의 입력을 배경에 대한 정보 $ T_B $ 만을 받도록 하여 좀 더 편리하게 만들 것입니다.

3 The GrabCut segmentation algorithm

3.1 Colour data modelling

이미지가 RGB 컬러 $ z_n $ 값을 갖게 되면 이전과 같이 히스토그램을 사용하는 것이 힘들어집니다. 따라서 각 background와 foreground를 위하여 2개의 GMM을 사용합니다. 각 GMM은 full-covariance를 갖는 K개의 Gaussian mixture로 구성되어 있습니다. 각 픽셀은 K개의 Gaussian 중 하나에만 속하도록 할당되며 이를 표현하기 위해 파라미터 벡터 $ \mathbf{k} = \{ k_1, …, k_n, … k_N \}, k_n \in \{1, … K\} $ 를 추가하여 사용합니다.

이제 Gibbs energy는 아래와 같이 수정되었습니다.

$$\mathbf{E}(\underline{\alpha}, \mathbf{k}, \underline{\theta}, \mathbf{z}) = U(\underline{\alpha}, \mathbf{k}, \underline{\theta}, \mathbf{z}) + V(\underline{\alpha}, \mathbf{z})$$

$$U(\underline{\alpha}, \mathbf{k}, \underline{\theta}, \mathbf{z}) = \sum_{n} – \log p(z_n | \alpha_n, k_n, \underline{\theta}) – \log \pi(\alpha_n, k_n)$$

$$V(\underline{\alpha}, \mathbf{z}) = \gamma \sum_{(m, n) \in C} [\alpha_n \neq \alpha_m] \exp( -\beta (z_m – z_n)^2)$$

여기서 $ p(\cdot) $ 은 Gaussian 확률 분포이고, $ \pi(\cdot) $는 Gaussian의 mixture weighting coefficients입니다. 사용하는 파라미터는 $ \underline{\theta} = \{ \pi, \mu, \Sigma, \alpha, k \} $ 입니다.

3.2 Segmentation by iterative energy minimzation

상태 에너지 함수가 결정되었으니 최적화 방법을 알아볼 차례입니다. 기존의 한번 계산으로 결정되는 방법 대신 계산을 반복하면서 투명도를 정교하게 만드는 방법을 사용할 것입니다.

먼저 초기 값으로 background에 해당하는 $ T_B $를 입력받은 상태입니다. $ T_F = \emptyset, T_U = \bar{T_B} $로 설정합니다. $ T_B $의 투명도는 0, $ T_U $는 1로 초기화합니다. background와 foreground의 GMM 또한 $ T_B$$ T_U $로부터 계산하여 초기화합니다.

첫번째 단계로 $ T_U $의 픽셀들을 GMM에서 가장 높은 확률을 갖는 Gaussian component에 속하도록 $ k_n $을 할당합니다. 다음, 할당된 픽셀들을 이용하여 각 Gaussian component 확률 분포의 파라미터를 갱신합니다. weights $ \pi(\alpha, k) $는 k component에 해당하는 픽셀 수를 normalize하여 사용합니다. 마지막으로 $ T_U $의 픽셀들에 대하여 minimum cut을 이용하여 최적화 과정을 수행합니다. 이 과정을 반복하면 Expectation maximization (EM) 에 따라 지역 최적해에 수렴하게 됩니다.

3.3 User Interaction and incomplete trimaps

GrabCut은 사전 입력으로 $ T_B $ 의 정보만이 필요하기 때문에 사용자 입력이 최소화 장점을 가지고 있습니다. 이는 foreground로 잘라내길 원하는 물체를 포함하도록 사각형을 그리는 것으로 간단히 이루어지는데, 사각형의 외부 영역을 $ T_B $로 할당해버리는 것으로 작업이 끝나버리는 것입니다. 그리고 이 영역은 background 영역으로 완전히 고정되어 변경되지 않고 내부 사각형 영역만 계산을 반복함으로써 최적의 상태를 찾아가게 됩니다.

이 방법을 사용하였더라도 일부분이 빠지는 등의 결과가 좋지 않을 때는, 추가적으로 사용자 입력을 받도록 합니다. brush 툴을 사용하여 background나 foreground에 속하는 픽셀들을 칠하도록 하여 이를 고정시킨 뒤, 다시 한 번 세번째 최적화 방법을 적용합니다.

4 Transparency

background와 foreground가 결정되었으면 이제 테두리부분의 투명도를 결정할 차례입니다. background, foreground를 결정 짓는 테두리 $ C $를 따라 좁은 띠 형태로 영역을 지정하고, 이 영역에 대해서는 투명도를 적용할 것입니다.

4.1 Border Matting

3의 결과에서 새로운 trimap $ \{ T_B, T_U, T_F \} $를 생성합니다. 기존 영역에서 $C$를 따라 띠의 너비 $ \pm w $ 만큼의 영역을 $T_U$로 지정합니다. 그리고 이 $ T_U $ 영역에 대해서만 투명도 $ \alpha_n $을 계산할 것입니다.

먼저 $ C $의 각 위치를 $ t = 1, …, T $로 표현하고, 픽셀 $ n \in T_U $는 어느 한 t에 속하도록 ($ t(n) $) 합니다. 투명도는 soft step function $ g(r_n; \Delta_{t(n)}, \sigma_{t(n)}) $에 의하여 결정됩니다. $r_n$은 픽셀 $ n $$ C $로부터 떨어진 거리를 나타내는데 foreground에 가까우면 음수를, background에 가까우면 양수 값을 가집니다. $ \Delta, \sigma $는 step function의 중심과 0에서 1로 얼마나 빨리 변화할지를 나타내는 파라미터입니다. 이 함수는 논문의 그림 6 (c)이 잘 나와있습니다.

테두리 C의 한 위치 t에 따라 같은 step function을 가진다고 가정하고, $ \Delta_1, \sigma_1, …, \Delta_T, \sigma_T $에 대해 dynamic programming (DP) 을 사용하여 최적화를 수행합니다.

$$E = \sum_{n \in T_U } \tilde{D}_n (\alpha_n) + \sum_{t=1}^T \tilde{V} (\Delta_t, \sigma_t, \Delta_{t+1} \sigma_{t+1})$$

Data term은 step function으로부터 결정된 \alpha 값이 주변 컬러 값을 고려하였을 때 에 얼마나 적당한지를 판단하는 역할을 합니다. 먼저 t 위치에서 L * L 크기의 사각 영역 $ S_t $를 정의하고, $ F_t = S_t \cap T_F, F_b = S_t \cap T_B $를 정의합니다. 그리고 이 두 영역의 Gaussian 분포 모델을 생성하여 각각 $ \mu_t(\alpha), \Sigma_t(\alpha), \alpha = 0, 1 $를 계산합니다. 이렇게 생성된 Gaussian 모델을 이용하여 새로운 Gaussian 함수 $ N(\cdot) $을 계산합니다.

$$\tilde{D}_n (\alpha_n) = -\log N(z_n ; \mu_{t(n)}(\alpha_n), \Sigma_{t(n)}(\alpha_n))$$

$$\mu_t(\alpha) = (1-\alpha) \mu_t(0) + \alpha \mu_t(1)$$

$$\Sigma_t(\alpha) = (1-\alpha)^2\Sigma_t(0) + \alpha^2 \Sigma_t(1)$$

Smoothing term은 직전 t 위치에 따라 step function이 급격하게 변하는 것을 막도록 하는 역할을 합니다.

$$\tilde{V} (\Delta_t, \sigma_t, \Delta_{t+1} \sigma_{t+1}) = \lambda_1 (\Delta – \Delta’)^2 + \lambda_2(\sigma – \sigma’)^2$$

4.2 Foreground estimation

마지막으로 border matting 과정에서 정확하게 모델에 들어맞지 않아 튀는 색들을 제거합니다. 먼저 Chuang의 방법을 이용하여 픽셀 $ n \in T_U $의 foreground 색 $ \hat{f}_n $ 을 얻고, $ F_{t(n)} $ 내에서 $ \hat{f}_n $과 가장 비슷한 색을 선택하여 값을 변경합니다.

5 Results and Conclusions

구현에 사용한 값들은 다음과 같습니다.

$$K = 5, w = 4, L = 5$$

결과에서는 주로 GrahpCut과 GrabCut의 결과를 비교하였습니다.

Bibliography


Add a Comment Trackback