논문

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

SLIC Superpixels Compared to State-of-the-art Superpixel Methods

[cite]10.1109/TPAMI.2012.120[/cite]

1. Introdution

Radhakrishna Achanta의 SLIC (Simple linear iterative clustering) 방법은 k-means clustering 방법을 수퍼픽셀 문제로 변형한 방법이다.
Radhakrishna는 수퍼픽셀에서 요구되는 기능으로,

  1. 이미지의 경계와 붙어있어야 한다.
  2. 다른 알고리즘을 적용할 때 계산 복잡도를 줄이기 위해서 전처리 단계에서 수퍼픽셀을 사용하기 위해서 그 처리가 속도가 빨라야 하고 메모리 사용이 적어야 하며, 사용하기 쉬와야 한다.
  3. 세그멘테이션 목적으로 사용된다면, 사용하지 않았을 때보다 속도가 빨라져야 하며 그 결과물의 질 또한 좋아야 한다.
    를 들고 있으며, 위의 관점에서 SLIC를 평가하였을 때, 기존 방버들 보다 빠른 속도와 적은 메모리 사용을 특징으로 한다.

2. Existing superpixel methods

수퍼픽셀 알고리즘은 크게 그래프 기반 알고리즘과 Gradient ascent 방법으로 나눌 수 있다.

A. Graph-based algorithms

그래프 기반의 알고리즘은 각 픽셀을 그래프의 한 노드로, 노드간 에지는 픽셀간 유사도에 비레하게 설정하여 그래프를 구성한다. 그래고 이 그래프의 cost를 최소화하는 상태를 게산하여 수퍼픽셀을 생성한다.
이에 해당하는 방법은 Normalized cut (NC05), Felzenszwalb와 Huttenlocher의 그래프 기반 Segmentation (GS04), Superpixel Lattices(SL08), 그리고 Veksler의 Super pixels (GC10) 등을 들 수 있다.

그래프 기반의 방법들은 이미지 크기에 비례하는 거대한 그래프 덕분에 대체로 속도가 느리고 (NC05, SL08), 본래 수퍼픽셀으로 제안된 방법들이 아닌 것들은그 크기와 모양이 불규칙적이며 그것들의 조절이 쉽지 않다 (GS04).

B. Gradient-ascent-based algorithms

그래디언트 기반의 방법은, 미리 대충 나눠진 픽셀에서 시작하여 반복적으로 클러스터링을 갱신하면서 결과과 어느 기준에 도달할 때까지 계산을 하는 방법이다.
이에 해당하는 방법은 mean-shift (MS02), quick-shift (QS08), watershed 알고리즘 (WS91), Turbopixel 방법 (TP09) 등이 있다.

분포의 Mode를 찾는 방법으로 제안된 MS02와 QS08은 마찬가지로 그 속도가 느리고 불규칙적인 모양이며 (MS02), 크기와 양을 조절할 수 있는 방법이 없다 (MS02, QS08, WS91).

3. SLIC superpixels

이제 논문의 SLIC을 살펴보자.
SLIC은 k-means에서 변형된 방법으로 두가지 특별한 차이가 있는데,

  1. 매 반복마다 계산에 사용되는 샘플의 범위를 제한하여 계산의 수를 줄였다.
  2. 컬러와 지역 정보의 차이에 대하여 가중치를 다르게 적용하여 이를 조절하여 수퍼픽셀의 크기와 compactness를 조절할 수 있다.

A. Algorithm

먼저 이미지 공간에서 k개의 클러스터 중심을 초기화하도록 하자. k는 유일하게 사용되는 파라미터로 생성할 수퍼픽셀의 수를 나타낸다. 생성된 수퍼픽셀은 가로 세로가 비슷한 크기를 갖게되므로 각 수퍼픽셀의 간격은 $ S = \sqrt{N / k} $ 으로 계산할 수 있다. 따라서 클러스터 중심 $ C_i = [ l_i a_i b_i x_i y_i ] $ 는 일정한 간격 S를 갖는 격자무늬의 위치와 CIELAB 공간에서의 픽셀 값으로 초기화하자. 논문에서는 CIELAB 공간을 사용하였지만 실험결과 gray 값을 사용해도 무방하다. 그 뒤에 각 클러스터 중심에서 그래디언트가 가장 작은 위치로 중심을 이동시켜준다. 이것은 노이즈 때문에 수퍼픽셀의 중심이 에지에 붙어있는 것을 방지하고자 함이다.

이제 이미지의 모든 픽셀에 대하여, 그 픽셀에 영향을 끼칠 수 있는 클러스터 중 가장 거리가 가까운 클러스터로 레이블링을 한다. 이때 영향을 끼칠 수 있는 클러스터는 그 픽셀로부터 그 중심의 위치가 S 이내의 것들이다. 따라서 필요한 몇개의 클러스터만 계산하면 된다는 점이 k-means에 비해 속도가 향상될 수 있는 키포인트이다. 픽셀과 클러스터 중심과의 거리 D는 뒤에서 이야기하도록 하자.

모든 픽셀들이 레이블이 할당되면, k-means에서와 같이 클러스터 i에 할당된 모든 픽셀들을 평균하여 새로운 클러스터 중심 $ [l a b x y]^T $ 를 계산하여 갱신하도록 하자. 그리고 새로운 중심과 이전의 중심과의 L2 norm, E를 residual error로 정의하자.

위의 레이블링 할당과 갱신 단계를 반복하며 E가 수렴할 때까지 반복하도록 하자. 논문에서는 대강 10번 정도면 만족할 만한 결과를 얻을 수 있었다고 한다.

마지막으로 연결되지 못하고 동떨어진 픽셀을 근처 가까운 픽셀로 연결시켜주어 작업을 마무리한다.

B. Distance measure

클러스터와 픽셀의 거리 D는 CIELAB 컬러 공간에서의 l, a, b와 픽셀 위치의 x, y를 사용한다. 하지만 픽셀 위치 차이는 이미지 크기에 영향을 받으므로 컬러 공간과의 스케일 차이가 발생한다. 따라서 두 가지를 통합하기 위해 가중치를 사용하도록 하자.
$ d_c $ 를 컬러 공간의 L2 norm, $ d_s $ 를 위치 공간에서의 L2 norm이라고 하고, D’ 는,

$$D' = \sqrt{ ( \frac{d_c}{N_c})^2 + (\frac{d_s}{S})^2 } $$로 정의하여보자. 이 때, $ N_S = S $ 이고, $ N_c $는 컬러 공간에서 가장 큰 거리이지만 이는 클러스터나 이미지마다 매우 다른 양상을 가진다. 따라서 위의 식을 변형하여,
$$ D = \sqrt{ d_c^2 + ( \frac{d_s}{S} )^2 m^2}$$

으로 정의하여, 컬러와 지역 거리 사이의 중요도의 비로 나타내도록 하자. 따라서 m이 크다면 지역성이 강조되어 수퍼픽셀은 compact해질 것이고, m이 작으면 이미지 경계에 더 붙는 경향을 보일 것이다.

C. Post-processing

앞에서 설명한 것과 같이 혼자 클러스터에 붙지 못하고 떨어진 픽셀은 connected components alogrithm을 통하여 가장 가가운 클러스터로 재할당 해준다.

4. Comparison with state-of-the-art

기존 방법들과의 비교는 논문을 참고하도록 하고, 거리 D를 구하는 방법을 변형한 몇가지 사례를 알아보자.

E. More complex distance measure

ASLIC (Adaptive-SLIC)은 상수 m 대신, 각 클러스터의 컬러와 지역적 최대 거리 $ m_c $, $ m_s $ 를 구하여 $ N_c $, $ S $ 대신 사용한 것이다.

GSLCI (Geodesic-SLIC)은 D를 L2 norm대신 geodesic distance로 계산한 방법이다.

6. Conclusion

SLIC은 k-mean을 변경하여 비교적 간단한 방법으로 수퍼픽셀을 구현하였으며, 시간 대비 성능 또한 다른 방법보다 월등히 뛰어난 편이다. k-means에서의 파라미터 k 선택의 어려움은 원하는 수퍼픽셀의 수를 설정함으로써 간단히 해결된다. 클러스터 중심과 각 픽셀 간의 거리를 계산하는 모델 교체도 가능하여 다른 알고리즘과 통합한 방법도 고려가능한 것으로 보인다.


Add a Comment Trackback