[CV] Scale Invariant Feature Transform (SIFT) : 영상의 스케일에 불변한 Feature

Keypoint ?

 

Keypoint(특징점)는 물체의 모양, 크기, 위치가 변해도 쉽게 식별이 가능한 위치이고 카메라의 시점, 조명이 이 변해도 이미지에서 쉽게 찾을 수 있는 위치를 뜻한다. 이러한 조건을 만족하는 위치는 대부분 corner point이고 대부분의 keypoint 추출 알고리즘들이 이러한 코너검출을 기반으로 설계되었다.

 

* 코너가 아닌 물체의 내부 또는 배경이면 그 주변과 특징이 비슷하기 때문에 keypoint의 조건을 만족할 수 없다.

 

때문에 영상에서 keypoint를 추출하면 서로 다른 시점의 영상을 매칭하거나 특정 물체를 추적하는데 사용할 수 있다.

 

 

Descriptor ?

 

Keypoint는 이미지에서의 특징이 되는 좌표를 의미하고 descriptor는 해당 keypoint에서 추출한 local 이미지 특징 정보이다. 대표적인 local invariant descriptor로는 SIFT, SURF, ORB 등이 있고 descriptor 계산을 위해서는 우선 keypoint를 추출해야 한다.

 

 

Harris Corner

Harris Corner는 코너 부분을 찾는 descriptor로 평행이동, 회전에 invariant 하고 affine 변화, 조명 변화에도 어느정도 robust 하지만 영상의 scale 변화에 영향을 받는다는 단점이 있다.

 

Scale Invariant Feature Transform (SIFT)

SIFT는 Harris corner의 scale 변화에 민감한 문제를 해결하기 위해 Difference of Gaussian(DoG)를 기반으로 scale 축으로도 코너성이 extrema인 점을 찾는 알고리즘이다. 즉 SIFT는 영상의 scale에도 invariant 한 알고리즘이다.

SIFT feature 추출 과정은 아래와 같다.

 

1. Scale space 생성
2. Difference of Gaussian (DoG) 연산
3. Keypoint 추출
4. Optimal keypoint 선택
5. Keypoint 방향 할당
6. SIFT 특징 추출

 

1. Scale-space 생성

• 우선, 다양한 scale의 특징을 추출하기위해 입력 이미지로 image pyramid를 생성
• 각 생성된 이미지들을 Octave1~4 로 표기

 

2. Difference of Gaussian (DoG) 연산

• Harris 와는 달리 Laplacian 함수를 이용하는데, 이는 이미지 픽셀값의 2차 미분값이다.
• 때문에 영상의 밝기 변화가 일정한 곳에서는 0에 가까운 값이 나오고 코너 부분과 같이 밝기 변화가 급격한 곳에서는 높은 값이 출력됨
• 실제 implementation에서는 속도 문제 때문에 laplacian을 직접 계산하지 않고 DoG를 이용하여 scale별 laplacian을 근사하여 사용
• DoG는 입력 이미지에 가우시안 필터를 점진적으로(시그마값이 점점 커지는) 적용하여 blur시킨 이미지 들에서 연속적인 이미지들간의 차(subtraction)이다.

 

3. Keypoint 추출

• DoG 이미지들에서 keypoint 들을 찾기 위해 DoG 이미지들에서 극대값, 극소값의 대략적인 위치를 찾는다
• 한 픽셀에서 극대/소값을 결정하기 위해서는 동일한 octave 내의 세장의 DoG 이미지에서 주변 26개의 픽셀값을 검사하여 체크하는 픽셀(중간)이 주변 픽셀값 중에 가장 작거나 클 경우에 keypoint로 선택
• 모든 octave에서 동일한 과정이 수행되고 각 octave 별 이미지 사이즈가 다르기 때문에 좌표계에도 차이가 발생

 

 

4. Optimal keypoint 선택

• keypoint들의 정확한 위치를 테일러 전개를 이용하여 찾음
• 활용가치가 떨어지는 (콘트라스트가 낮거나, 엣지 위에 존재하는) keypoint 들을 제거하는 후처리 과정 실행

 

 

5. Keypoint 방향 할당

• 앞 단계까지 진행된 keypoint 들은 scale invariance를 가진다
• keypoint 들에 orientation(방향)을 할당하여 rotation invariance를 만족시킴
• 각 keypoint 주변의 그레디언트 방향과 크기를 모아 가장 두드러지는 방향을 찾아서 keypoint의 방향으로 할당
• Keypoint 주변에 윈도우를 만들어 keypoint의 scale값으로 가우시안 블러링
• 위 식으로 magnitude와 orientation을 계산
• 그레디언트의 magnitude에는 가우시안 함수로 가중치를 부여하여 keypoint에 가까울수록 좀 더 큰 값을 가지도록
• Keypoint에 방향을 할당하기 위해 360도의 방향을 10도씩 잘라 36개의 bin을 가지는 히스토그램을 생성
• 윈도우 내의 모든 픽셀에서 그레디언트 방향 값을 bin에 채워서 히스토그램을 완성하고 가장 높은 bin의 방향이 keypoint의 방향으로 할당
• 가장 높은 bin의 80% 이상의 수치를 갖는 bin이 있으면 그 방향도 keypoint의 방향으로 선택
  
  

 

6. SIFT 특징 추출

 

• 이제 keypoint 들은 위치, 스케일, 방향 정보를 가지고 있고 스케일과 회전에 invariant
• 이러한 keypoint들을 식별하기 위해 keypoint 특징을 128개의 숫자로(128 dimension) 표현
• 이를 위해 keypoint 주변 16x16 사이즈의 윈도우를 적용하고 이 윈도우는 4x4의 sub-window로 구성
• 16개의 sub-window의 그레디언트 크기와 방향을 계산하고 앞선 방법과 유사하게 히스트그램화하는데 bin을 8개만 세팅
• 16개 sub-window는 각각 히스토그램을 가지게 되고 16*8 =128 개의 feature vector를 얻는데 이 feature vector는 물체가 회전하면 모든 그레디언트 방향이 바뀌게 되므로, keypoint의 방향을 16개의 윈도우 방향에서 뺀다
• 이러한 방법은 16개의 윈도우 방향을 keypoint 방향에 상대적이도록 만들어 회전 의존성을 해결해 줌
• 마지막으로 밝기 의존성을 해결하기 위해 정규화를 해주면 SIFT feature(descriptor)가 만들어진다.
• SIFT로 이미지 매칭을 하기 위해서는 두 이미지에서 keypoint 들을 찾고 feature의 차이가 가장 적은 곳을 매칭하면 된다