[CV] Scale-Invariant Feature Transform (SIFT)

들어가면서

Edge, corner, blob을 배우면서 corner를 detection 할 수 있는 알고리즘 중 Harris corner detection을 배웠었다. Harris corner detection의 경우 rotation invarian(불변) 즉 한 이미지를 오른쪽으로 회전해서 corner를 detection했을 경우에도 corner를 인식할 수 있었지만 scale을 작게 했을 경우에는 corner라고 검출이 안되기 때문이다.

SIFT 알고리즘 순서도

SIFT 알고리즘 순서도는 위 그림과 같다.
위 순서에 따라 알고리즘을 설명을 해보겠다!

SIFT 알고리즘

1. Scale-space extrema detection

이 과정은 scale과 orientation(회전) 에 invarient(불변) 할 거라 추측되는 Interest point들을 검출하는 과정이다.

지난 포스팅에 적은 Laplacian of Gaussian(LoG)와 같은 개념으로 나오는 Difference of Gaussian(DoG)을 사용하여 검출을 한다.

Difference of Gaussian (DoG)
말 그대로 가우시안의 차이를 계산한다. 서로 다른 $\sigma$를 가지는 가우시안 커널의 차를 이용한다. 그렇다면 가우시안 커널의 차는 무엇일까? 가우시안 커널의 차는 LoG의 근사값을 의미한다.

위 그림과 같이, Scale에 불변하기 위해서 $\sigma$값을 다르게 해서 각 이미지에 대해서 가우시안 피라미드를 생성한 후에 DoG를 구한다.
DoG를 구한 것을 토대로 극점인 부분들은 feature point의 후보자로 잡아준다.
DoG의 상위와 하위 층까지 모두 합쳐서 주변 26개보다 크거나 모두 작을 때만 특징점 후보자로 검출을 한다.
이 때, 특징점을 Scale별로 구하게 되기 때문에 target 물체가 작아져도 인식할 수 있는 장점이 있음

2. Keypoint Localization

테일러 급수를 사용해서 더 정확한 extrema(극점)을 찾는다.
찾은 후에 테일러 급수를 사용해서 interpolation 방법을 통해 해당 점의 값을 구하고 feature point의 후보자 중에서 정확하지 않는 feature point를 제거한다.

3. Orientation Assignment

주요한 방향을 할당해주는 단계이다.
특징점 주변으로 16x16 영역 할당한 후에 가우시안 블러링 적용하면 특징점 주변의 영역에 대한 gradient의 방향 크기가 결정된다.
이를 구하면 orientation histogram을 형성하고 이 중에 가장 값이 큰 것을 해당 orientation으로 결정한다.
이 때, 물체가 회전해도 orientation 정보가 있기 때문에 인식할 수 있다는 장점이 존재한다.

4. Keypoint Descriptor

각 특징점 마다 descriptor를 생성해주는 단계이다.
Gaussian weight function을 활용해서 생성해주고, 16x16 pixel의 영역을 할당하여 image gradients를 구하고 window 크기의 1/2의 값을 gaussian weighted function에 곱해준다.

+추가적으로)
histogram을 그려줄 때는 orientation 값을 뺀 다음에 descriptor가 회전에 불변하도록 만들어준다.
객체 인식할 때 DB의 각 특징점의 descriptor를 가지고 인식할 물체 영상의 descriptor와 비교를 하게 된다.
비슷하면 데이터가 비슷하게 나오고 이 거리는 유클리드 거리 계산식을 사용한다.

$\theta(x, y) = tan^{-1}(\frac{G(x+1, y)-G(x-1, y)}{G(x, y+1)-G(x, y-1)})$

출처

SIFT 알고리즘 순서도 image: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=laonple&logNo=220879911249
SIFT: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=laonple&logNo=220879911249
https://hello-stella.tistory.com/21
DoG: https://sunshower76.github.io/cv(computervision)/2020/03/23/Laplacian-of-Gaussian(LoG)-&-Difference-of-Gaussian(DoG)/