본문 바로가기

OpenCV

SIFT 알고리즘

320x100
320x100

 

 

Scale Invariant Feature Transform (SIFT)

 

 개발하기 급급해서 OpenCV 함수로만 사용해왔는데 논문을 쓰는 입장이 되어보니 원리에 대해 공부해야할 필요성이 생겨버렸다. 그래서 내가 할 수 있는 최대로 구글링해서 공부했고 그 내용들을 정리해두려고 한다. 시간이 지나면 일부분은 까먹게 될테니깐..!

 

 

SIFT Algorithm

 이미지의 Scale (크기) 및 Rotation (회전)에 Robust한 (= 영향을 받지 않는) 특징점을 추출하는 알고리즘이다. 이미지 유사도 평가나 이미지 정합에 활용할 수 있는 좋은 알고리즘이다. 논문에서는 4단계로 구성되어 있다고 밝히고 있다.

  1. Scale-space extrema detection
  2. Keypoint localication
  3. Orientation assignment
  4. Keypoint descriptor 

 

이제 각 단계에서 어떤 연산들이 수행되는지 알아보자.

 

 

1. Scale-space extrema detection

 먼저 Scale-space를 만들어서 extrema (극점 = 극대점과 극소점)을 검출한다. 세부 단계는 아래와 같다.

 

(1) 먼저 Scale-space (= 크기 공간)를 생성을 위해 원본 이미지를 다양한 크기로 resize해서 image pyramid를 만든다.

 

[ Image Pyramid 예시 ]

 

 

(2) 다음으로 image pyramid의 각 층 이미지(octave image)를 점점 더 커지는 σ(= gaussian blur scale factor)로 gaussian blurring를 적용한 이미지들을 얻는다. Scale-space는 이 이미지들을 가리키는 용어다. 더 자세한 설명을 원한다면 이곳1 과 이곳2 에 들어가보자. 읽으면 제대로 감이 잡힐 거다.

[ scale-space 예시 ]

 

 

(3) Difference of Gaussian(DoG) 이미지를 구한다. DoG 이미지는 아래 그림처럼 같은 octave 내 서로 다른 두 개 gaussian blurred image로 빼기 연산을 수행하여 생성한다.

 

 

(4) 마지막으로, 만들어진 DoG를 이용해 extrema detection을 수행한다. 해당 좌표가 극소점이거나 극대점이라 판단되면 이를 keypoint 후보군으로 분류한다. Extrema detection의 자세한 과정은 다음과 같다.

 위 그림과 같이 DoG_(target)에서 target pixel (빨간점) 값을 총 26개의 주변 pixel 값과 비교해 극점인지 판단한다. 주변 pixel에는 다음이 해당된다.

  • DoG_(target)에서 target pixel 주변의 8개 pixel
  • DoG_(target-1)와 DoG_(target+1)에서 각 9개 pixel

 


※ 추가 1

 나처럼 헷갈려하거나 궁금해하는 사람이 또 있을 것 같아서 추가로 정리한다. Octave1의 image size와 Octave2의 image size는 다르다. 이 말은 각 Octave에서 찾은 keypoint candidate들의 좌표계에도 차이가 있다는 말과 같다.

예를 들어,

Octave1에서 찾은 keypoint candidate는 [ 2*W × 2*H ] 좌표계를 기준으로 좌표값이 정해지지만, 

Octave2에서 찾은 keypoint candidate는 [ W × H ] 좌표계를 기준으로 좌표값이 정해져서

각 Octave에서 뽑힌 keypoint candidate는 완전히 다른 좌표계를 사용하게 된다.

그래서 각 Octave에서 뽑은 keypoint candidate ( = extrema)를 Origianl Image에 표현하고 싶은 경우, 좌표계를 Original Image 좌표계로 변환해줘야 제대로 표현해줄 수 있다.

 

※ 추가 2

 Keypoint candidate는 속성으로 X 좌표, Y 좌표 뿐만 아니라 Scale Factor와 Octave도 같이 갖고 있다. Scale Factor는 추후 Original Image에서 keypoint를 표시할 때 keypoint의 크기를 결정하는 인자로 활용되고, Octave 정보는 위에서 말한 것처럼 좌표계를 맞추는 데에 활용된다.

 

 

! 광고 시간 !

728x90

 


 

2. Keypoint localization

 이렇게 뽑은 keypoint 후보군들 중에는 정확한 좌표계에 위치하지도 않고 활용가치가 떨어지는 것들도 있어서 most stable keypoint만을 선택하는 과정이 필요하다고 한다. 논문에서 이런거 저런거 소개하긴 하는데... 이 부분은 

 

'아~ 후처리로 keypoint selection 진행하나보네~'

 

하고 넘어간 터라 따로 정리할 내용이 없다. 아무튼 이 단계까지 끝나면 keypoint는 scale-invariance를 갖게 된다.

 

 

 

3. Orientation assignment

 지금까지 찾은 keypoint의 방향을 결정하는 단계다. 여기서 찾은 orientation을 이후에 keypoint descriptor에서 빼주면 rotation-invariance 성질을 갖게 된다. 

 

(1) 먼저 keypoint를 중심으로 추출한 16x16 patch를 사용해서 Gradient magnitude와 Gradient orientation을 구한다 [Ref]. Gradient magnitude와 Gradient orientation을 구하는 식은 다음과 같다.

 

[출처] SIFT 논문

 

 이때 patch 추출에 사용되는 이미지는 해당 keypoint가 뽑힌 gaussian blurred image이다.

특정 Keypoint가 Octave2에서 k값(=scale factor)으로 gaussian blurring된 image에서 뽑힌 거라면,

Gradient magnitude와 Gradient orientation 계산에도 Octave2에서 k값으로 gaussian blurring된 image의 pixel 값을 사용한다는 말이다.

 

(2) Keypoint에 방향 속성을 추가하기 위해 1 bin 당 10 degree을 담당하는 36개의 bin을 갖는 orientation histogram을 생성한다. 그런 다음 16x16 patch에서 구한 Gradient orientation 값들을 Gradient orientation이 해당되는 bin에 더하는데, 이때 Gradient magnitude에 gaussian-weighted circular window를 곱한 값을 bin에 더한다. 가중치를 부여하기 위함이다.

 

[출처] bskyvision

 

 

 bin들이 다 채워진 orientation histogram 상에서 가장 높은 값을 갖는 bin을 해당 keypoint의 방향으로 할당한다. 또한 가장 높은 bin의 80% 이상의 값을 갖는 bin이 추가로 존재한다면 그 방향을 갖는 keypoint를 새로 만든다.

 

 만약 한 Keypoint의 [ X 좌표, Y 좌표, Scale Facor, Octave ] = [ 10, 20, 2, 3 ] 이고, orientation histogram 생성 결과 90~99 bin에서 가장 높은 값을 갖고, 20~29 bin이 80% 이상의 값을 갖는 상황이라 하면, [ X 좌표,  Y 좌표, Scale Factor, Octave ]는 같되 방향은 다른 두 개의 Keypoint를 생성한다.

Keypoint1 : [ X 좌표,  Y 좌표, Scale factor, Octave, Orientation ] = [ 10, 20, 2.0, 3, 95 ]

Keypoint2 : [ X 좌표,  Y 좌표, Scale factor, Octave, Orientation ] = [ 10, 20, 2.0, 3, 25 ]

 

 

4. Keypoint descriptor

 마지막으로 Keypoint를 표현하기 위해 Descriptor를 생성해줘야 한다. 과정의 대부분은 Orientation assignment랑 비슷하고 약간의 차이가 있다. 

  1. KeypointA에는 [ X 좌표,  Y 좌표, Scale factor, Octave, Orientation ]의 정보가 담겨있다.
  2. Scale factor와 Octave 정보를 이용해 Scale-space에서 해당되는 gaussian blurred image를 가져오다.
  3. 이 image에서 KeypointA의 X 좌표, Y 좌표를 중심으로 16x16 patch를 추출한다.
  4. 이 patch를 16개의 4x4 sub-patch로 다시 분할한다.
  5. 한 개의 sub-patch에서는 8-bin orientation histogram을 생성해 한 sub-patch 당 8방향 정보를 담게 만든다.

 

결과적으로 한 개의 16x16 patch에서는 8방향 정보가 16개 생성되어 총 128개의 값을 얻게 되는데 이를 keypoint descriptor라 부른다. 끝으로 후처리로 descriptor에서 keypoint orientation 값을 빼 rotation-invariance 성질을 부여하고 nomalization을 통해 밝기 의존성을 해결한다. 

 

[출처] Boosting of factorial correspondence analysis for image retrieval

 

 

 

[ 참고 사이트 ]

https://link.springer.com/content/pdf/10.1023/B:VISI.0000029664.99615.94.pdf

https://bskyvision.com/144

https://bskyvision.com/21

https://takehoon.tistory.com/entry/Comvision-Chap6-Feature-Detection-FAST-SURF-BRIEF-ORB

https://slideplayer.com/slide/6276090/

https://medium.com/@james.chain1990/sift-scale-invariant-feature-transform-25d1a934997b

https://salkuma.files.wordpress.com/2014/04/sifteca095eba6ac.pdf

https://towardsdatascience.com/sift-scale-invariant-feature-transform-c7233dc60f37

https://github.com/rmislam/PythonSIFT/blob/master/siftdetector.py

https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf

https://ngost.tistory.com/60

http://166.104.231.121/ysmoon/mip2017/lecture_note/%EC%A0%9C6%EC%9E%A5-%EC%B6%94%EA%B0%80.pdf