논문

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

Superpixels and Supervoxels in an Energy Optimization Framework

[cite]10.1007/978-3-642-15555-0_16[/cite]

1. Introduction

컴퓨터비전이나 영상처리에서 수퍼픽셀은 여러 장점을 가지지만 그중에서도 가장 매력적인 것은 계산량의 감소일 것이다.

수퍼픽셀은 그 존재 이유 상, 비슷한 색이나 텍스쳐 등을 갖져야 하기 때문에 실제 물리적으로도 같은 물체에 속해 있을 가능성이 높다. 때문에 수퍼픽셀을 만드는 방법은 세그멘테이션 알고리즘을 이용하는 것들이 많은데, 이를테면 Mean-shift나, 그래프 기반의 방법들, 또하는 Normalized cut 등의 방법 들이 제안되어 왔다. 주로 이들 방법들을 과하게 적용하여 oversegmentation을 시켜버리는 식으로 수퍼픽셀을 생성하지만, 본래 태생이 세그멘테이션 알고리즘이다보니 그 크기와 모양이 제각각인 수퍼픽셀이 생성되어버린다.

하지만 모양과 크기가 일정한 수퍼픽셀은 장점이 있다. 물체의 경계가 복잡하더라도 수퍼픽셀의 크기를 일정하게 유지하도록 조절할 수 있어 객체의 경계를 넘지 않도록 제어가 가능하다.

Olga Veksler는 이 논문에서 에너지 최소화 프레임워크 (Energy minimization framework)에 기반하여 수퍼픽셀을 계산하는 방법을 제안하였다. 인접하는 두 픽셀들이 다른 수퍼픽셀에 속하면 패널티를 갖도록 하는 모델을 생성하고, 패널티를 두 픽셀 값 차이에 반비례하도록 설정하여 수퍼픽셀의 경계가 에지를 따라 생성되도록 유도하였다.

2. Superpixel Segmentation

먼저 사용된 그래프 컷을 이용한 Energy Minimization을 간단히 알아보자.

2.1 Energy Minimization with Graph Cuts

익히 잘 알려진 그래프에서의 에너지 함수는 아래와 같다. 이미지에서는 보통 한 픽셀이 한 노드에 대응하도록 그래프를 구성한다.

$$E(f) = \sum_{p \in P}{D_{p} ( f_{p} ) + \lambda \sum_{p, q \in N} { w_{p q} \cdot V_{pq} ( f_{p}, f_{q})}}$$

첫번째 항은 Unary term으로 각 노드(픽셀) 그 자체에 대한 페널티값을 나타낸다.두번째 항인 Pairwise term은, 한 노드와 그 이웃하는 노드끼리의 패널티를 나타낸다. 그래프에 존재하는 두 패널티를 모두 더하면 그것이 그래프의 상태 에너지 값이 된다.

이 논문에서 다루고자 하는 것은 픽셀 $ p $ 와 그 픽셀에 할당되는 레이블 $ l $ 에 관한 것을 다시 상기해보자.
$ f_p $ 는 픽셀 p에 할당된 레이블 $ l \in L $ 을 뜻한다.

$$\mbox{}$$

이제 다시 식을 쳐다보면, Unary term은 픽셀 p가 레이블 $ f_{p} $ 로 할당 되었을 때의 패널티를, Pairwise term은 인접해 있는 픽셀 p, q에 부여된 레이블들끼리 인접해 있는 것에 대한 패널티이다. 추가적으로 픽셀 p, q에 대한 Weight 부분도 들어있다.

위의 모델을 적용하여 Yuri Boykov의 alpha-expansion 알고리즘을 이용하여 레이블을 할당해보도록 하자.

2 Compact Superpixels

일단 일정한 크기를 갖는 정사각형 패치를 생각해보자. 이 패치는 계산이 끝난 후에는 각 수퍼픽셀이 될 것이며 각 패치마다 레이블 번호 $ l $ 을 가진다. 이러한 패치로 수퍼픽셀을 생성할 영상을 모두 덮도록 패치를 생성하여 위치시키는데, 패치끼리는 일정 부분을 서로 겹치도록 해야한다. 이 때 설정한 패치의 크기는 수퍼픽셀이 가질 수 있는 최대 크기가 된다.

이제 Expansion 알고리즘을 사용하기 위한 식을 정의하여 보자. 먼저 Unary term 부터,

$$D_{p}(l) = \begin{cases} 1 & \mbox{if } p \in S(l) \\ \infty & \mbox{otherwise} \end{cases}$$

$ S(l) $ 은 패치 $ l $ 속하는 픽셀의 집합을 나타낸다. 따라서 앞서 겹치는 패치들이 서로 겹치는 부분의 픽셀은 두 패치에 대해서 모두 1의 값을 가지게 된다.

$$\mbox{}$$

Boykov의 Expansion 알고리즘은, 한 레이블 $ \alpha $를 선택하고 이를 나머지 $ \bar{\alpha} $ 레이블의 일부 영역으로 확장시키는 방법이다. 이때 위와 같이 Unary term을 선택함으로써 페널티가 무한대인 부분으로는 확장될 수 없고 서로 겹친 부분에서만 확장이 가능하게끔 제한한다. 따라서 레이블의 확장은 무한히 이루어지지 못하고 처음 주어진 패치의 크기를 벗어나지 못한다.

이제 Pairwise term을 보자.

$$V_{pq} (f_{p}, f_{q}) = min(1, |f_{p} - f{q}|^{1})$$

$$w_{pq} = exp(-\frac{(I_p - I_q)^2}{dist(p, q) \cdot 2 \sigma ^ 2})$$

Potts model을 사용하고 8-connected grid를 사용하였다.
논문에서는 8-connected grid와 Potts model $$ 을 사용하였다. 만약 두 픽셀의 레이블이 다를 경우, 픽셀 값의 차이가 작으면 큰 페널티를 가지게 되어있다. 반대로 말하면 두 픽셀의 레이블이 다르면서 픽셀 값의 차이가 클 때 페널티가 적게 되므로 두 레이블간의 경계는 이미지의 에지 부분으로 가도록 유도될 것이다.

위의 모델을 사용하여 Expansion 알고리즘을 모든 레이블에 대해 반복해서 두어번 적용하면 수퍼픽셀을 생성할 수 있다.

2.4 Constant Intensity Superpixels

식에 조금 변형을 가해보자. 앞의 식에서 Unary term은 패치에 속하기만 하면 같은 페널티를 갖기 때문에 수퍼픽셀내에서의 색이 어떤지는 생각지 않고 레이블의 경계부분에 대해서만 고려하고 있다. Unary term을 아래와 같이 수정해보자.

$$D_p(l) = \begin{cases} |I_p - I_c(l)| & \mbox{if } p \in S(l) \\ \infty & \mbox{otherwise} \end{cases}$$

$ I_c(l) $ 은 패치 l의 중심 픽셀 값으로 중심 픽셀과의 차이를 패널티로 사용한 것이다. 이제 각 수퍼픽셀은 패치의 중심 픽셀과 비슷한 값을 같도록 유도될 것이다.

4 Experimental Results

간단히 구현을 해보니 Compact Superpixel은 수퍼픽셀로써 성능이 썩 좋질 않았다. 아무래도 픽셀 자체의 값보다는 무작위로 생성된 패치를 기준으로 생성된 것이다보니 수퍼픽셀 레이블의 경계 부분만으로는 좋은 결과가 나오기 힘들었던 것 같다. Constant Intensity superpixels 방법은 조금 나은 결과를 보이나 중심 픽셀의 값에 따라서 협소한 영역에서는 불규칙적인 모양을 갖는 문제도 보였다.
가장 큰 문제는 시간으로 기존의 Normalized cut이 느리다고는 하나 여전히 패치의 수만큼 expansion 방법(s-t cut)을 사용해야한다는 점은 단점으로 작용한다. expansion 방법 특성상 최소 에너지 상태에 도달하려면 그 자체를 다시 여러번 반복해야 하므로 시간적으로 좋은 접근법은 아닐 것이다.


Add a Comment Trackback