Superpixels (슈퍼 픽셀 알고리즘)

슈퍼 픽셀은 영상 분할 및 Object Tracking 분야에서 자주 사용되는 방법이다. 슈퍼 픽셀을 이용하여 영상에서 특성이 비슷한 픽셀들을 묶음으로 표현할 수 있다. 슈퍼 픽셀은 영상을 특징이 비슷한 작은 균일한 영역으로 나누고 이 작은 영역들을 기본단위로 하여 영상처리를 하는데, 여기서 나누어진 균일 영역을 슈퍼 픽셀이라고 한다.

정리하면 다음과 같다.

• 픽셀보다 더 많은 정보를 제공한다.
• 슈퍼 픽셀은 주어진 슈퍼 픽셀에 속하는 픽셀이 유사한 시각적 특징을 공유하기 때문에 perceptual한 의미를 갖는다.
• 계산적으로 까다로운 문제에 매우 유용할 수 있는 편리하고 간결한 이미지 representation을 제공한다.

슈퍼 픽셀 생성을 위한 SLIC(Simple Linear Iterative Clustering) 알고리즘

SLIC 알고리즘은 이미지 평면에서 색상 유사성과 근접성을 기반으로 픽셀을 클러스터링 하여 슈퍼 픽셀을 생성한다. SLIC는 5차원 [labxy] 공간에서 연산된다. 여기서 [lab]는 CIELAB 색상 공간의 픽셀 색상 벡터이고 [xy]는 픽셀 위치를 의미한다. 이 5D 공간에서 Euclidean distance를 사용하려면 spatial 거리를 normalize해야 하는데, 그 이유는 CIELAB 공간에서 두 색상 사이의 가능한 최대 거리는 제한되어 있지만 xy 평면의 spatial 거리는 이미지 크기에 따라 다르기 때문이다. 따라서 5D 공간에서 픽셀을 클러스터링 하기 위해 슈퍼 픽셀 크기를 고려한 새로운 거리 측정이 방법이 필요하다.

 

먼저 슈퍼 픽셀의 개수를 $K$라고 하면 먼저 슈퍼 픽셀의 클러스터 중심은 $k=\left [1, k \right]$에서 $C _ { k } = \left [ l _ { k } ,a _ { k } ,b _ { k } ,x _ { k } ,y _ { k } \right ]$로 주어진다. 일정한 그리드 간격인 $S= \sqrt { \frac{ N } { K } }$에서 슈퍼 픽셀의 공간 범위는 대략 $S ^ { 2 }$ (슈퍼 픽셀의 대력적인 면적) 이므로 이 클러스터 중심과 관련된 픽셀은  xy 평면의 슈퍼 픽셀 주변의 $2S \times 2S$ 영역 내에 있다고 가정할 수 있다. 5D 공간에서 사용되는 normalized distance ($D _ { s }$)는 다음과 같이 정의된다.

 

$D _ { s } =d _ { lab } + \left ( \frac{ m } { S } \right ) \times d _ { xy }$

 

이때 $d _ {lab} = \sqrt { \left ( \left ( l _ { k } -l _ { i } \right ) ^ { 2 } + \left ( a _ { k } -a _ { i } \right ) ^ { 2 } + \left ( b _ { k } -b _ { i } \right ) ^ { 2 } \right ) }$이고 $d _ { xy } = \sqrt { \left ( \left ( x _ { k } -x _ { i } \right ) ^ { 2 } + \left ( y _ { k } -y _ { i } \right ) ^ { 2 } \right ) }$이며 $D_s$는 lab 거리 $d _ { lab }$ 와 그리드 간격 $S$로 정규화된 xy 평면 거리 $d _ { xy }$의 합이다. 변수 $m$은 $Ds$에 작용하여 슈퍼픽셀의 크기를 결정한다. $m$의 값이 클수록 클러스터가 더 조밀해진다. 

 

SLIC 알고리즘은 $K$개의 규칙적인 간격의 클러스터 중심을 샘플링하고 3 × 3 이웃에서 가장 낮은 기울기 위치에 해당하는 시드 위치로 이동하는 것으로 시작한다. (이는 가장자리에 배치하는 것을 방지하고 노이즈가 많은 픽셀을 선택할 가능성을 줄이기 위해 수행된다.) 이미지 기울기는 다음과 같이 계산된다.

 

$G \left ( x,y \right ) = \left \| I \left ( x+1,y \right ) -I \left ( x-1,y \right ) \right \| ^ { 2 } + \left \| I \left ( x,y+1 \right ) -I \left ( x,y-1 \right ) \right \| ^ { 2 }$

 

여기서 $I \left ( x,y \right )$는 위치 $\left ( x,y \right )$의 픽셀에 해당하는 lab 벡터이고 $\left \| . \right \|$는 L2 norm인데, 이는 색상과 intensity 정보를 모두 고려한다. 이미지의 각 픽셀은 탐색 영역이 이 픽셀과 겹치는 가장 가까운 클러스터 중심과 연결된다. 모든 픽셀이 가장 가까운 클러스터 중심과 연결된 후 새 중심은 클러스터에 속한 모든 픽셀의 평균 labxy 벡터로 계산된다.

 

픽셀을 가장 가까운 클러스터 중심과 연결하고 클러스터 중심을 다시 계산하는 과정은 이 과정이 수렴될 때까지 반복된다. SLIC 알고리즘은 다음과 같이 요약할 수 있다.

 

http://www.kev-smith.com/papers/SLIC_Superpixels.pdf

 

[참고 자료]

https://darshita1405.medium.com/superpixels-and-slic-6b2d8a6e4f08