[CV] Scale-Invariant Feature Transform (SIFT)

Main Reference:
- Scale-Invariant-Feature Transform(SIFT) - 한국과학기술원 전기 및 전자공학과 최성필

📹 Introduction to SIFT

SIFT는 key point를 찾아 descriptor를 붙이는 단계, descriptor를 이용해 원본 이미지와 변환 이미지의 key point를 매칭하는 단계, 총 두 단계로 이루어져 있다. SIFT로 뽑은 key point의 특징으로는 Scale, Rotation, Illumunation, Noise 에 Invariant하다.

Scaling Problem

Original Image	Zoomed Image

Harris Corner Detector에서 보았듯이 기존 detector는 같은 코너를 검출한다 하더라도 대상의 scale에 따라 다른 detector를 사용해야 했다. 실제 이미지에서 물체의 크기는 카메라로부터 얼마나 떨어져 있냐에 의존한다. 예를 들어 위 그림의 오른쪽 이미지는 왼쪽 이미지의 일부분을 확대한 것에 불과하다. 왼쪽 계단과 오른쪽 계단이 동일한 대상임에도 서로 다른 detector를 사용해야 이들을 탐지할 수 있다는 의미이다.
SIFT는 ‘Gaussian Pyramid’라는 기법으로 이를 멋지게 해결한다. ML의 object detection을 공부할 때 보았던 Spatial Pyramid Pooling 기법이랑 매우 유사한데 SIFT는 무려 2004년에 발표된 논문이다. Vision 분야도 정말 똑똑한 사람들이 많았구나 싶다.

Algorithm

1. Detect Scale-Space Extrema
2. Accurate Key Point
3. Assign Orientation
4. Key Point Descriptor
5. Key Matching

📹 Detect Scale-Space Extrema

먼저 Scale-Invariant 특성을 위해 Gaussian Pyramid 기법을 이용한다. Bolb Detection 에서 봤듯이 특정 크기의 feature를 탐지하기 위해서는 Laplacian of Gaussian(LoG) 또는 Difference of Gaussian(DoG)를 이용해야 한다. 이때 Gaussian의 σ, 다시 말해 kernel scale이 blob scale과 일치해야 blob을 탐지할 수 있다. 따라서 같은 이미지 크기(same octave)에서 σ를 변경해가며 blob을 탐지하고, 이미지 전체를 down-sampling(next octave)한 후 다시 σ를 변경해가며 blob을 탐지해나간다. 결과적으로 임의의 scale에 대한 blob detection을 수행하는 것인데, σ를 아주 미세하게 나누는 것보다 훨씬 효율적인 방식이라 할 수 있다.

위 그림은 한 octave 내에서, DoG의 결과를 나타낸 것이다. σ가 작은 경우 작은 blob에 반응하며, σ가 점점 커짐에 따라 큰 blob에 반응하는 것을 볼 수 있다. 이런 방식으로 이미지 전체에서 임의의 크기에 대한 bolb을 먼저 탐지하게 된다.

Find Candidate Key Points

단순히 Bolb Detector에 반응한다고 해서 blob으로 잡아버리면 수많은 중복 탐지 현상이 나타날 것이다. 따라서 Non-max suppression과 같이 중복된 탐지를 제거해야 하는데 Gaussian Pyramid의 경우 DoG의 상위 층과 하위 층까지 모두 합쳐(3차원 cube 형태) 주변 26개의 pixel보다 큰 경우에만 blob으로 처리한다. 이 과정 이후 살아남은 blob들을 key point 후보들로 간주하여 다음 스텝으로 넘긴다.

📹 Accurate Key Point

위 과정에서 구한 key point의 후보들은 local maximum 기준이다. 이제 여기에서 두 가지 경우를 제외할 것이다. 첫째, local maximum 값이 특정 값(threshold)보다 작은 경우. 둘째, 해당 key point가 feature로서의 가치가 적은 edge인 경우.

Remove under threshold vaule

이 지점에서 우리가 알고 싶은 것은 local maximun의 실제 값이다. 하지만 주어진 DoG 값은 pixel별로 주어진 discrete한 값들이다. 따라서 2차 Taylor 전개로 interpolation함으로서 연속 함수로 만들어 주고 이 함수에서의 maximun 값을 기준으로 사용한다.

\[D(X) = D + \frac{\partial D^{T}}{\partial X} X + \frac{1}{2}X^{T}\frac{\partial ^{2}D}{\partial X^{2}}X\] \[\hat{X} = -\frac{\partial ^{2} D^{-1}}{\partial X^{2}} \frac{\partial D}{\partial X}\] \[D(\hat{X}) = D + \frac{1}{2}\frac{\partial D^{T}}{\partial \hat{X}}\] \[if \; \left| D(\hat{X}) \right| < 0.03 \to \textit{Discard key}\]

• Taylor 전개를 통해 DoG 표현
• D를 미분해서 0 나오는 x_hat 찾기
• x_hat 대입해서 최댓값 구하기
• 최댓값이 0.03보다 작으면 key point 후보에서 제외

Remove Edge Response

Edge 제거는 이전에 포스팅한 Harris Corner Detector를 이용하면 된다. 해당 key point의 R score가 적당한 threshold보다 작은 경우 key point 후보에서 제거한다.

• (a) : Original Image
• (b) : Original image에서 찾은 key point 후보 (832개)
• (c) : 최댓값이 threshold보다 작은 key point 후보 제거 (729개)
• (d) : Harris Detector로 찾은 Edge key point 제거 (536개)

📹 Assign Orientation

SIFT는 key point에 방향을 할당해주는 방식으로 rotation invariant를 달성한다. 이에 대한 자세한 내용은 Key Point Matching 파트에서 다루기로 하고, 지금은 방향을 어떻게 할당해주는지에 집중해보자.

\[m(x, y) = \sqrt{(L(x+1, y) - L(x-1, y))^{2} + (L(x, y+1) - L(x, y-1))^{2}}\] \[\theta(x,y) = tan^{-1} \frac{L(x+1, y) - L(x-1,y)}{L(x, y+1) - L(x, y-1)}\]

먼저 key point 기준으로 16x16 필셀을 gaussian blurring 한다. 그 후 각 필셀에 대해 gradient의 크기, 방향을 구해야 한다. 이때 위 수식을 이용해 계산하면 되고, L은 gaussian blurred image를 의미한다.

Gradient magnitude의 경우 그대로 사용하지 않고, gaussian weighted kernnel을 convolution 해준다. 즉, key point와 가까운 gradient일 수록 가중치를 준다는 의미이다. 이때 사용하는 gaussian kernel의 σ는 앞서 key point blurring에 사용했던 σ 의 1.5배 이다.

Key point의 방향을 결정하는 방법은 다음과 같다. 먼저 0° ~ 360°를 10° 구간으로 분류한 뒤 각 픽셀의 gradient를 담아주면 된다. 예를 들어 어떤 픽셀의 gradient가 20°방향, 10의 크기를 가진다면 10°~20° 구간에 10을 더해주면 된다. 이런식으로 모든 픽셀에 대한 gradient 히스토그램을 그리고, 가장 높은 값을 가지는 방향을 key point의 방향으로 설정하면 된다. 만약 이때 최댓값의 80% 이상인 또 하나의 peak가 존재한다면 서로 다른 두 개의 key point로 만들어준다.

📹 Key Point Descriptor

첫번째 그림에서 두 key point는 서로 방향만 다를뿐, 같은 feature를 나타낸다. 이들이 같은 feature라고 인식하기 위해서는 방향성을 제외한 특성을 두고 비교해야 하는데, 이 작업을 하기 위해 앞에서 key point의 방향을 할당한 것이다. 비유하자면 앞 단계에서 구한 key point의 방향은 상대적인 방향이라 할 수 있고, 매칭을 할 때에는 상대적인 위치 정보를 뺀 상태에서 비교를 하게 된다. 이를 나타내는 성질이 바로 Descriptor 이다.

• Descriptor도 key point 주변 16x16 픽셀에서 gaussian blurring 이후 gradient를 구해준다.
• 16x16 window를 4x4 grid cell로 분할한다(그림에서는 2x2).
• 이때 gradient의 방향은 360°를 8구간으로 나눈 값 중 하나로 들어간다. (45° 단위)
• gradient의 크기는 gaussian weighted 값으로
• 결과적으로 16 cells * 8 orientation, 128 dimensional vector descriptor가 생성된다.

이제 우리가 구한 descriptor에 몇 가지 후처리 과정만 거치면 된다. 첫째, rotation invariant를 위해 descriptor에서 key point orientation을 빼준다(상대적인 방향 제거). 둘째, illumination invariant를 위해 Normalize + Cliping 해준다. 이때 cliping은 normalized 이후 히스토그램의 가장 큰 값이 0.2를 초과하지 않도록 해준다.

📹 Key Matching

위에서 설명한 작업들을 마무리 하면, 각각의 key point들이 128차원 공간의 어느 점으로 대응될 것이다. 따라서 현재 이미지와 비교하고 싶은 이미지의 key point들을 같은 공간의 점으로 표현하면 된다. 이제 이들 사이의 유클리드 거리를 바탕으로 matching 하면 된다. 이때 단순한 거리를 가지고 threshold를 정하게 되면 오류가 크기 때문에 다른 방식을 사용한다. 실제 사용하는 방식은 가장 가까운 키와의 거리와 두번째로 가까운 키와의 거리 비율이 0.8보다 작은 경우 매칭한다.

맨 위로 이동하기

Vision 카테고리 내 다른 글 보러가기