Superpixel의 분류(1) - Graph 기반의 Superpixel

Graph의 분류는 올해 Computer Vision and Image Understanding에 실린

Superpixels: An evaluation of the state-of-the-art를 기준으로 하였습니다.

 

 

Graph 기반의 Superpixel 기법은 이미지를 undirected graph로 바꾸어서

이 graph를 K개의 서로 연결되지 않은 작은 graph로 나누는 문제를 푸는 접근법을 택한다.

이 때, 각각의 pixel은 vortex가 되고 두 pixel의 유사성이 edge의 weight가 된다.

 

문제는 이를 완벽하게 푸는 것이 NP-Hard 문제라고 증명되었다는 것이다.

따라서 위의 문제는 근사해서 풀거나 Greedy Algorithm으로 바꾸어서 풀어야 하며

보통 FH, ERS, POISE처럼 edge가 하나도 없는 상태에서 하나씩 추가하는 bottom-up 방식과

NC, CIS, PB처럼 edge를 전부 가지고 시작해서 제거해나가는 elimination 방식으로 나눌 수 있다.  

 

이 분류의 기법들이 가장 큰 문제는 느리다는 점이다.

일단 Graph 생성 과정이 있기 때문에 시간적으로 많이 불리하다.

모든 pixel 사이의 유사성을 계산하는 것은 (pixel^2)/2번을 계산해야 하니 말도 안 되고,

각각의 pixel마다 주위의 고정된 k개의 pixel 간의 유사성을 계산해도 pixel*k번의 연산이 필요하다.

거기에 edge가 추가되거나 삭제될 때 graph 업데이트까지 고려하면 구조적으로 빠르기 힘들다. 

 

장점은 비슷한 시기의 논문끼리 비교해보면 segmentation의 성능이 우수하다는 점이다.

즉, 요약하면 전체적으로 느리지만 segmentation 성능이 괜찮은 알고리즘들이다.

 

다만 요즈음 전체적으로 빠른 기법들을 바탕으로 segmentation 성능을 올리는 쪽으로 연구가 진행되는 것이 트렌드이기 때문에 graph-based 기법은 그다지 인기가 높다고 보기 힘들다. 심지어 몇몇 논문에서는 대놓고 시대에 뒤떨어졌다고 언급되기도 한다.

그러나 확실한 장점이 있는 기법들이기 때문에 몇몇 분야에서는 여전히 사용된다.