이미지의 크기와 회전에 불변하는 특징을 추출하는 알고리즘.
두 이미지에서 SIFT feature를 추출하여 매칭한 뒤, 대응되는 부분을 찾음.

---

1. Scale Space

scale은 사람의 시각과 관련된 개념.
큰 scale : 멀리 떨어져서 전체적인 이미지를 봄.
작은 scale : 가까이서 세부적인 이미지를 봄.

Scale space : 단 하나의 scale이 아닌 여러 scale의 이미지들

Scale 키우기
1) 이미지 크기를 줄임.
2) 이미지 크기는 유지하면서 블러링↑.

Scale 줄이기
1) 이미지 크기를 키움.
2) 이미지 크기는 유지하면서 블러링↓.

Gaussian FIlter
블러링을 위한 필터 중 하나.

$g_{\sigma}(x,y)=$$1\over2\pi\sigma^2$$e^{-(x^2+y^2)/2\sigma^2}$

$\sigma$ : 블러링을 결정하는 param. 스케일 파라미터라고도 부름.

이미지의 크기를 $1\over2$, $1\over4$, $1\over8$$\ ···$로 만들고, 같은 이미지 크기 (Octave) 내에서 스케일 param을 조정하여 다양한 scale과 다양한 blur의 이미지를 만듦.

$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$

$L(x,y,\sigma)$ : Blurred image
$G(x,y,\sigma)$ : Gaussian filter
$I(x,y)$ : Image

이는 이미지 크기의 불변성을 갖음.

---

2. Difference of Gaussian (DoG)

DoG는 이미지에서 edge와 corner와 같은 feature은 추출하는 방법.
같은 octave 내에서 인접한 이미지들을 빼줌.

---

3. Extrema Detection

Keypoint : DoG 이미지 내에서의 극값 픽셀.

한 픽셀에서의 극값을 찾기 위해서는 octave 내에서 이웃한 두 장의 DoG 이미지 필요.
비교할 픽셀의 수는 26 (= 8 + 2 $\times$ 9)개.
26개의 픽셀보다 작거나 크다면 keypoint.

Subpixel

진짜 극값은 픽셀 사이에 위치할 가능성이 높음.
따라서 테일러 2차 다항식을 통해 subpixel의 위치를 추정.
이는 좀 더 안정적인 성능.

---

4. Orientation Assignment

keypoint는 scale invariance 상태.
vectorization을 통해 rotation invariance 부여.

keypoint를 중심으로 이웃한 픽셀 ($16\times16$ patch)의 gradient 크기와 방향 고려.

크기
$m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y))^2+(L(x,y+1)-L(x,y-1))^2}$
Gaussian weight 함수를 이용하여 keypoint에 가까울수록 큰 값을, 멀어질수록 작은 값을 갖게함.

방향
$\theta(x,y)=tan^{-1}((L(x,y+1)-L(x,y-1))/(L(x+1,y)-L(x-1,y)))$
360도를 10도씩 36개로 분할하여 구분하고, patch 내의 모든 픽셀에 대해서 gradient 방향 계산.
히스토그램 내에서 가장 높은 방향과 80% 이상의 높이를 같는 방향이 keypoint의 방향.

5. Keypoint Descriptor

keypoint는 scale & rotation invariance 상태.
keypoint의 식별을 위한 작업 필요.

keypoint 픽셀 인근의 $16\times16$ patch를 16개의 $4\times4$ sub-patch로 구성.
16개의 각 sub-patch 별로 gradient의 크기와 방향을 구함.
이 때, 방향은 360도를 45도씩 8개로 분할.
즉, keypoint descriptor는 128 (= 16 $\times$ 8)개의 vector로 구분.

---

Reference
스케일 스페이스(scale space)란 무엇인가?
SIFT (Scale Invariant Feature Transform)의 원리