[논문 리뷰] SIFT (Scale Invariant Feature Transform)

예전에 시험 기간에 노션에 정리해놓은것을 그대로 가져왔다.

몇 가지 내용이 빠졌다. 시험기간이라 바빠서 전체 논문을 읽지는 못했거든...

노션에 그대로 놔두고 읽던가하지 왜 이렇게 귀찮게 한번 더 올리는 이유는 지식 공유 차원 겸 블로그 관리 차원 겸....

요즘 너무 이 블로그를 내 일기장처럼 쓰는 감이 없지 않아 있어서.

 

 

 

Distinctive Image Features from Scale-Invariant Keypoints (2004)

• SIFT 논문은 28페이지이다.
• SIFT를 알기 위해 필요한 scale-space theroy의 논문은 50페이지이다.

미친 개많아…

그래도 힘내서 정리해보자.

전체 요약 (초록)

• 이미지로부터 distinctive invariants features를 추출하는 것이 목표.
• 추출된 feature은 different view나 scene의 reliable한 matching에 이용됨 → visual correspondence!!
• 이 feature는 scale, rotation, affine distortion, 3D viewpoint 변화, noise 추가, illumination 변화에 강건함(robust)

SIFT 과정 요약

1. Scale-space extrema detection
   • 모든 scale과 image location 탐색
   • DoG (difference-of-gaussian) 이용
   • potential interest points 추출
   • 추출된 points들은 scale과 orientation에 invariant
2. Keypoint localization
   • location과 scale을 정하기 위해 뭐지 이건 더 자세히 보고 정리해야
3. Orientation assignment
4. Keypoint descriptor

그럼 각 과정을 자세히 들어가 보자.

1. Detection of scale-space extrema

• efficient한 알고리즘을 이용한 “cascade filtering” 사용
• scale change에 invariant한 location을 detect하기 위해서는, 모든 가능한 scale에서 feature를 탐색할 수 밖에 없음 → Scale Space (오늘날의 FPN과 유사)

Scale-Space Theory?

• scale-space란?
  • scale 축을 따라서 생성되는 공간(?)
  • 즉 scale-space representation이라 하면
  • scale parameter t에 따라 원본 신호가 blur 되는 세트의 집합을 뜻한다.

• 이 때 scale이 커질수록, 사물을 넓은 시야에서 볼 수 있다.
• → 더 coarse한 특징들만이 잡힘
• 즉 다음과 같을 때 scale이 커진다고 한다.
  • image size가 작아질 때 (down-sampling)
  • image가 더 강하게 blurring될 때 ( $\sigma$가 커질 때)

•  
• Scale-space theory: A basic tool for analysing structures at dierent scales (1994)

논문 전문 읽기는 포기하고 abstract + 일부 + 이 페이지 + 페이지2에 설명된 걸 요약함

한 줄 요약이 가능한데, 결국 여러 유도 과정을 통해…

• Scale-space theory: A basic tool for analysing structures at dierent scales (1994) 에서는 이러한 문장으로 요약했고
• 💡 Under rather general conditions on the type of computations that are to performed at the first stages of visual processing, in what can be termed the visual front end, **it can be shown that the Gaussian kernel and its derivatives are singled out as the only possible smoothing kernels.**

이걸 SIFT 논문에서는 “the only possible scale-space kernel is the Gaussian function”이라고 요약했다. → scale을 조정할 때 사용할 수 있는 (blur) kernel은 오직 Gaussian밖에 없다!!

• 식으로 나타내보자.

왜 scale이 필요한가?

• 이미지의 scale 달라지면 뽑히는 feature의 종류도 달라진다.
• 주어진 이미지에서 우리가 관심을 가질 만한 정보를 뽑기 위해서는 어느 scale이 적절한지 모른다. → 그러므로 모든 scale을 고려한다. (SIFT가 여기서 영감을 받은 듯)
• ⇒ multi-scale representation
• 여기서 t는 Gaussian func.의 표준편차와 동치. t의 값이 커질수록 blur의 정도가 커짐
• ⇒ multi-scale 집합에서 추출된 feature는 scale-invariant한 특성을 지니게 된다.
• 그러면 어떻게 scaling 하는가?
  • 보통 blurring → sub-sampling (down-sampling)의 과정을 거치는 듯 하다.
    • 연산의 효율성을 위해, 등등의 이유가 있어 보이는데 정확한 이유는 모르겠음
• 그림으로 나타내면 다음과 같음

• SIFT에서는 scaling * s, downsampling의 단계로 진행한다. 이건 추후 설명

 

 

특이점을 뽑자 (이 파트는 좀 내 뇌피셜이 있음)

reference: 전적대 컴퓨터비전 자료

• 특이점(e.g. edge)는 1차 미분(혹은 2차 미분)을 통해 얻어짐
  • 왜? pixel값이 급격하게 바뀌니까!

• 이 때 이미지 pixel의 2nd derivative를 구하기 위해 사용되는 filter가 Laplace of Gaussian(LoG)이다.
• LoG filter를 image에 적용시켜 값을 구한 후, 0이 되는 지점 (zero-crossing)을 찾는다 → 그 값이 특이점이 된다.

• 그럼 LoG가 뭔데?
  • Laplacian of Gaussian. 즉 gaussian 함수를 2차 미분 시킨 것임.

• LoG를 다음과 같은 값으로 필터화(?)할 수 있다.
• 김승룡 교수님께선 그냥 이런 필터가 있어요~ 라고 언급만 하시고 넘어가셨던 것 같음

• scale parameter에 따라 filter의 형태가 달라진다.

• 왜 2차 미분의 특이점을 구할 때 LoG filter가 쓰이는데?
  • Differentiation is convolution, and convolution is associative
    • ppt에 있는 문장 그대로 가져왔는데 사실 뭔 말인지 잘..^^..
    • 여튼 아래의 식이 성립한다고 하네여.

• 그러면 f와 g(filter)를 conv해서 미분하는 것보다 미리 g를 미분한 필터를 만들어두고, 이 filter와 f를 conv하는 게 훨씬 연산량을 절약할 수 있겠죠!?
• 2차 미분도 비슷. 그러므로 conv → 2차미분 ㄴㄴ, 2차미분 filter 만들어서 conv ㅇㅇ

 

• 위의 Scale-space theory에 의해, image를 scaling하려면 Gaussian filter가 무조건 필요
• 그러므로 2차 미분을 통해 특이점을 찾으려면 Gaussian filter를 2차 미분한 필터, 즉 LoG filter가 필요하다.
• SIFT 논문에서도 이전 연구 결과를 통해 LoG가 가장 sable한 image feature를 생성한다고 밝혀졌다고 언급.

그러나, LoG를 사용하지는 않는다

• LoG 필터를 구하려면 scale parameter(t or sigma)별로 필터 값을 다 구해야 함..
• 연산의 효율성을 위해, SIFT저자는 LoG 대신 DoG (Difference of Gaussian) 함수를 제시

• DoG는 LoG를 근사한 함수가 된다.
  • (SIFT논문에도 증명이 있는데 수식이 이해가 안 가서 생략한다.^^)

• 어차피 모든 scale에서의(=모든 parameter k$\sigma$에서의) L을 봐야 하기 때문에 L은 무조건 scale별로 계산이 되어야 함. DoG를 구하려면, 여러 scale의 L 사이에서 단순한 뺄셈 연산만 하면 되겠죠?

그러면 DoG를 이용해 scale extrema를 추출해보자

• SIFT의 경우 다음의 단계로 DoG 연산이 진행됨
  1. image를 constant factor k를 가진 Guassian kernal을 적용해 blurring (scaling)한다.
  2. 즉, 각 processed image = $L(x, y, k\sigma)$
  3. 이를 “octave”라는 이름으로 묶는다.
  4. 이 때 한 octave 안의 interval (= blurred images 개수 - 1)을 s라고 하자.$k = 2^{\frac{1}{s}}$가 되어야 한다. 위의 예시에서는 s=4니까 k = 2^(1/4)가 되어야 함→ 다음 과정에서 DoG 결과의 local maxima와 minima를 판별할 때, 최상층과 최하층은 비교군이 없어서 2개를 추가로 더 만들어준다고 함.
  5. 그런데 논문에서는 한 octave당 blurred images 개수가 s+3개라네??? 왜지???
  6. octave의 마지막 blurred image는 $L(x, y, 2\sigma)$를 만족해야 한다. 그러므로
  7. 인접한 두 image scale들을 빼서 DoG image를 만든다. → 총 s+2개의 DoG image
  8. 한 Octave가 끝이 나면, octave의 첫 이미지=$L(x, y, \sigma)$ 마지막 이미지=$L(x,y,2\sigma)$가 됨
  9. we resample the Gaussian image that has twice the initial value of $\sigma$ (it will be 2 images from the top of the stack) by taking every second pixel in each row and column→ 크기가 작아지니 연산량이 줄어든다. 이 때 scale params sigma는 동일한듯?
  10. → 왜 이미지가 두장이 필요하다고 하는걸까?? 쨌든 이미지 크기를 가로세로 1/2씩 downsampling 해 준다.
• DoG 연산 후, 결과물 D(x, y, sigma)를 가지고 local extrema detection 진행
  • local maxima와 minima를 detect한다.

• 각 D(x, y, sigma)마다, 위 아래 scale로는 각각 9개의 neighborhood가 있고 (총 18개)
• 현재 scale 에서는 8개의 neighborhood가 있음
• 모든 neighborhood보다 작거나 큰 경우에만 해당 D를 select한다.
• image와 scale domain상에서 sampling frequency(?)를 정하는 것이 중요하다고 하는데 뭔소리임
• 3.3 3.4 frequency? domain? 이 부분은 신시를 들어야 이해할 수 있을 것 같다 현재로선 pass
•  

2. Accurate keypoint localization

• 1.에서 keypoint 후보군을 최종적으로 뽑았으면, 그 후보군을 정교하게 조정하고 걸러내는 과정이 2이다.

Interpolated location

• 동 저자의 1999년 연구에서는 keypoint를 단순히 동일한 위치 (central sample point)로 지정했다면, 타 2002년 연구에서는 3D quadratic function을 이용해 maximum의 interpolated location을 결정 → matching improvement & stability
  • 즉 위에서 구한 keypoint가 정확하지 않을 수도 있으니 interpolation을 한번 더 해보자는 것임
  • ⇒ SIFT 저자도 해당 방법을 채택
• quadratic function으로
  • D(x, y, sigma) (scale-space func.)에 대한 Taylor expansion을 사용 

• D와 그 미분값들은 sample point (keypoint ?)에서 연산
• $\mathbf{x} = (x, y, \sigma)^{T}$ : offset from the sample point (keypoint)
• 즉, 이 식의 원점은 sample point이고 위 식은 그 sample point로부터 x만큼 떨어진 점의 값을 나타냄

• extremum $\hat{\mathbf{x}}$을 구하기 위해 위 식을 x에 대해 미분후 0이라 두면, $\hat{\mathbf{x}}$은 다음과 같이 나옴

• D의 Hessian과 derivative는 이웃 sample point들과의 차이로 approximate 가능
• offset $\hat{\mathbf{x}}$ > 0.5
  • extremum이 현재 sample point보다는 다른 sample point와 더 가까움
  • → sample point를 interpolation된 point로 변경

Rejecting unstable extema with low contrast

• 위의 과정을 통해 구해진 식들로 $D(\hat{\mathbf{x}})$를 도출할 수 있음. 식은 다음과 같음

• $|D(\hat{\mathbf{x}})|$<0.03
  • pixel value가 [0,1]안에 있다고 가정
  • low contrast, 버림

Eliminating edge responses

• DoG 함수는 edge에 강한 response
  • 주변의 위치가 poorly determined되더라도 (keypoint가 되기에 부족해도) 무조건 edge라면 강한 반응을 보이는 것 같다.
  • ⇒ 작은 noise에도 unstable
  • “edge”보다는 “corner”를 검출하는 데 집중
• corner? edge?
  • (예전에 배웠던 건데 이것도 자세히 정리하기엔 시간이 없어서 그냥 시간 나면 자세히 정리하기로)

• Hessian matrix를 H라 하자. (2x2) (이는 아래에 추후 설명0
• corner: 모든 방향에서 변화가 큰 값. H의 두 eigenvalue가 모두 큼
• edge: edge 방향에서는 변화 작음. H의 두 eigenvalue 중 하나만 큼
• flat : 모든 방향에서 변화 작음. 모든 eigenvalue가 작음

• DoG로 검출된 poorly defined peak는
  • edge와 동일한 방향에선 큰 주곡률 (principal curvature) 값 가짐
  • 그러나 수직 방향에서는 작은 값 가짐
• edge와 horizental, vertical한 방향의 주곡률은 D의 Hessian matrix의 eigenvalue에 비례

이러한 원리 + 효율성을 고려해 저자들이 제안한 방법은 다음과 같다.

1. D의 Hessian matrix를 구한다.
2. 직접 두 eigenvalues를 구하기보다는 (연산량 이슈) 두 값 사이의 ratio만 고려
   • $\alpha$를 큰 eigenvalue, $\beta$를 작은 eigenvalue라 하자.
   • 그러면 두 값들의 합과 곱은 H의 trace와 determinant로 나타내어짐

• alpha와 beta가 다를 경우 (=det < 0 일 경우) extremum이 아닌 것으로 판별, 버린다

3. r을 alpha와 beta사이 비라고 하자. 즉, $\alpha = r\beta$. 그러면 다음 식을 만족:

• (r+1)^2/r는 두 eigenvalue가 동일해질 때 최소가 된다.
• → edge가 아니라 corner라는 의미. (flat은 애초에 걸러졌으니까)
• ⇒ Tr/Det이 작은 값만 고르자.

4. r을 threshold 값으로 두고 Tr/Det만 계산해 아래 식에 대입하자.

5. r = 10으로 둠. 즉, r ≤ 10만 남긴다.

(b) 1.의 과정만 끝냄 (c) ~rejecting .. low contrast 까지만 끝냄 (d) eliminating edge response까지 다 끝냄

 

3. Orientation assignment

• rotationally invariant measure를 바탕으로 한 (orientation 정보를 제거한) 1997의 다른 연구와 반대
• orientation 정보도 포함해서 keypoint descriptor의 representation을 만듦

그럼 Orientation 정보는 어떻게 넣는가?

1. keypoint의 scale (sigma)와 가장 가까운 Gaussian smoothed image L을 가져옴
2. keypoint의 주변 영역에서 gradient magnitude $m(x, y)$와 orientation $\theta(x, y)$를 계산

(이 때 x, y는 주변 영역의 좌표이지만 계산된 값은 keypoint의 historgram에 할당이 된다.)

• pixel difference를 이용해 미리 계산해둔다.

3. 처리된 gradient magnitude 값을 Gaussian-weighted circular window ($\sigma$=key point scale * 1.5)를 이용해 보정

• why?
  • keypoint pixel과의 거리에 따라 가중치를 주기 위해

4. 360도 방향의 orientation를 10도씩 쪼개서 36 bins로 만듦 → histogram 만듦

- 이 때 gradient magnitude에 비례해 (weighted) histogram에 반영됨

 

5. historgram의 가장 높은 peak가 해당 keypoint의 orientation이 됨

6. highest peak의 80%에 필적하는 값을 가진 다른 peak가 있을 경우 같이 detected

 

4. The local image descriptor

• 위에서 추출한 orientation 정보를 바탕으로 representation vector(descriptor)를 만드는 과정
• 무슨 visual cortex하면서 shift over a small receptive field 어쩌구…. 하는데
• 4.가 3.과 비슷하지만 차이가 있는 게 patch를 만들어 그 patch단위로 값을 추출하는 건데 이게 더 좋은 방법이다 라는 걸 뒷받침하는 근거였던 것 같다.
• 그럼 어떻게 descriptor를 만드는가?

1. keypoint를 중심으로 16x16 sample window 생성 (위 그림에선 8x8이지만 실제론 이렇다)
2. 3에서 했던 것처럼 gradient magnitude과 orientation을 구한다.
3. 역시 3에서 했던 것처럼 이 값을 Gaussian window로 보정
4. 4x4 patch로 묶어 orientation histogram을 만든다. 즉, 총 4x4=16개의 histogram이 만들어짐
5. (위 그림에서는 2x2)
6. 이 때 3에서 했던 대로 orientations를 45도씩 쪼개서 8 bins을 만든다.
   • 왜 8인가? → 실험적으로 입증됨(이 때 한 histogram에서 다른 histogram으로 넘어갈 때 혹은 한 orientation에서 다른 orientation으로 넘어갈 때 값의 변화가 급격하면 trilinear interpolation을 적용해줬다고 함)
7. 최종적으로, 추출된 모든 histogram의 값들을 한 vector에 넣는다.
   • 즉 patch 개수 = 4x4, bins 개수 = 8이므로 vector의 차원은 4x4x8 = 128이 됨⇒ 정리하면, 한 keypoint당 R^128의 차원을 가진 descriptor vector가 나오게 된다.
8. 이 vector를 기반으로 distance를 구하거나 clustring을 하여 image matching을 수행.

 

 

 

 

 

 

이거 리뷰할 때 까지만 해도 난 비전을 제일 좋아했었는데....