Digital Image Processing - SIFT

---

SIFT

SIFT는 Scale Invariant Feature Transform의 줄임말이고 SIFT알고리즘의 마지막 부분 구조가 체같이 생겨서 "체로 거르다"라는 뜻을 가진 sift라는 동사도 염두해두고 지은 센스있는 이름이다.

David G. Lowe가 1999년 ICCV에서 소개하고 2004년 IJCV에서 확장하였다. SIFT 알고리즘은 feature detection 분야의 2000년대 초반을 섬렵한 기념비적인 알고리즘 이다. SIFT는 local feature를 추출하고 이를 normalized descriptor로 변환하여 Scale invariance를 갖춘 local feature extracting 알고리즘이다.

---

Scale Space Detection

아래와 같이 같은 부분인데 scale이 다르면 같은 local feature로 잡아내기 어려운 문제가 있다. 추출된 patch만 보면 같은 feature라고 잡아내기 어려운 이유를 알 수 있다.

이러한 문제를 해결하기 위해 다양한 scale을 고려하는 기법을 사용한다. 아래 그림을 보면 초록색으로 확장된 범위에서 추출된 patch는 좌측의 원본 patch와 비교했을 때 거의 유사한 것을 쉽게 잡아낼 수 있음을 예상할 수 있다.

Scale을 다양화해서 select하는 방법으로 가장 흔히 쓰이는 방법은 아래와 같은 LoG(Laplacian of Gaussian) 필터를 이용한 pyramid 구조를 이용하는 것이다.

이때 LoG필터를 한없이 키우면 연산량이 기하급수적으로 증가하여 비현실적인 기법이 된다. 따라서 SIFT를 제시한 논문에서는 LoG필터는 단계적으로 줄여주고 그 사이에 상대적인 크기 차이를 만들기 위해 가우시안 필터를 이용하여 사진의 크기를 점진적으로 줄여가며 필터링을 수행하여 결과적으로 수많은 사이즈의 LoG필터를 이용한 효과를 낸다. 이때 같은 사이즈의 LoG필터에 대해서 사진 사이즈를 바꿔가며 필터링 하는 한 파트를 옥타브(octave)라고 부른다.

또한 연산량이 적은 DoG(Difference of Gaussian)으로 근사하여 연산하는 장점도 존재한다.

이렇게 피라미드 구조를 만들어 놓고 3D NMS(Non Maximum Suppression)기법을 이용하여 주변 26개 픽셀보다 크지 않다면 0으로 만들어버리는 특징 추출을 진행한다.

그렇게 추출한 Local Extrema에서 Low Contrast인 feature를 제거하고 Ratio of principal curvature가 threshold보다 작은 feature들도 제거하여 핵심 local feature들만 남긴다.

화살표 방향은 Orientation Assignment 과정에서 추출된 주요 방향이다. 특징점에 가장 우세한 방향을 할당하여, 이미지가 회전되더라도 특징점을 일관되게 식별할 수 있게 한다. 이를 통해 알고리즘이 회전에 불변하도록 만든다. 특징점 주변에서 기울기 각도와 크기를 미리 계산하여 히스토그램을 만들고, 이를 평활화하여 정확한 방향을 결정한다. 이 히스토그램은 각도 0 0에서 2 𝜋 2π까지의 범위를 갖는다.

이때 아래 그림과 같이 두번째로 우세한 방향이 첫번째 기준으로 80%이상일때는 해당 값도 또다른 feature로 인정해준다.

이렇게 추출된 특징은 아래와 같이 나타난다.

마지막으로 객체간에 매칭을 진행하기 위해 Descriptor가 존재한다. Discriptor는 아래와 같이 추출된 local feature의 Image gradients들 중에서 4X4 형태의 Keypoint descriptor를 찾아낸다.

이떄 하나의 descriptor는 45도씩 차이나는 8개의 orientation으로만 표현하는데 결과적으로 8*4*4=128차원의 Feature vector로 Local Feature를 표현할 수 있게된다.

주요 Orientaion이 반영되어 표현되는 것을 확인할 수 있다.

각 Feature Vector에는 Scale, Orientation, Location이 모두 포함된 Local Feature에 대한 정보가 담겨있다고 할 수 있다.

---