Superpixel Algorithm(1): Normalized Cut

(2000) Normalized Cuts and Image Segmentation by Jianbo Shi and Jitendra Malik

 

Graph Based 기법 중에서 가장 오래된 기법이며 그럼에도 아직까지 언급은 되고 있는 기법이다.

....사실 더 이상 실용성이 있다고 말하기는 조금 힘들다.

 

이 알고리즘의 목적은 위의 Noramlized cut의 값을 minimize하는 것이고

이를 계산하기 위해서 Generalized Eigenvalue Problem으로 근사하여 접근하는 방식을 택한다.

Cameraman.tif에 Normalized cut을 적용해서 분할해나가는 과정이다.

처음 이미지를 둘로 나누고, 그 후에 둘로 나뉘 조각을 다시 둘로 나누고, 그것을 다시 둘로 나누고

이를 반복해서 만들어낸 것이 맨 오른쪽의 이미지이다.

(참고로 위의 이미지는 직접 구현해서 돌린 결과물이다.) 

 

이 알고리즘의 장점은 Local이 아닌 Global Property를 기반으로 한다는 것,

그리고 그 결과물로 상당히 Compact하고 거의 비슷한 크기의 Superpixel을 만들어낸다는 것이다.

게다가 2000년에 나온 기법치고 Boundary를 준수하게 잡아준다.

 

단점은 속도와 메모리 소모량,

사실 eigenvalue problem은 원래 컴퓨터로 문제를 푸는 입장에서 별로 선호되는 문제가 아니다.

Python 기반으로 128*128 정도의 이미지의 되어도 하루 종일 걸리고,

SLIC 논문에서 Ncut을 512*512 이미지에 적용했더니 메모리 부족으로 알고리즘이 돌아가지도 않는다고 언급이 될 정도로 메모리 문제가 극심하다.

 

장점이 없진 않지만 요즘은 이보다 훨씬 빠르고 성능도 괜찮은 알고리즘이 많아서 실용성이 없다고 생각한다.