본문 바로가기
영상처리/Feature Detector

SIFT(Scale Invariant Feature Transform)

by 목가 2010. 2. 26.
반응형

SIFT란???
간단하게 소개하자면 크기와 회전에 불변하는 특징을 추출하는 것이다.
이 특징을 뽑아서 뭐하자고??? 물체인식이나 파노라마영상을 만드는 등의 작업을 할 때 특징을 찾을 필요가 있다.

SIFT는 크기가 변하든 회전을 하든 상관이 없이 항상 그 위치에서 뽑히는 특징을 찾아내준다.
SIFT가 나온 후에 많은 유사 논문들이 쏟아져 나왔지만 여전히 SIFT만큼 성능이 좋은 것은 없다고들 말한다. 

SIFT는 David Lowe's라는 사람이 2004년에 논문을 제출하면서 알려지게 되었다.

지금부터 어떻게 SIFT가 크기에 불변하고 회전에도 불변한 특징을 뽑아내는지 천천히 정리해보자.

1.Sacle-Space extrema detection
  Scale(크기)과 Orientation에 불변할 거라 추측되는 Interest point들을 검출하는 과정이라고 보면된다.
 여기서는 DoG(Difference of Gaussian)을 사용하였고, DoG가 LoG와 비슷한 결과가 나오는데 속도가 더 빠르기 때문에 사용했다 고 한다. (피라미드 영상을 구성할 때 가우시안 컨벌루션을 계산해 놓은 것이 있기 때문이다. 피마리드 영상의 차연산을 계산하면(DoG) 2차 미분한 LoG와 유사한 효과를 얻을 수 있으므로 계산량이 많이 절약된다.)

DoG는 가우시안 컨벌루션된 영상에 대한 2차 미분, 즉 LoG의 근사이다.
Scale에 불변하기 위해서 각 octave에 sigma값을 다르게 영상에 적용한다.  
따라서 아래 그림과 같이 피라미드를 구성하여 각 octave를 위한 블러된 영상을 s+3만큼 생성해야 한다. 그리고 DoG 영상들을 생성하기 위하여 인접한 scale의 영상들을 차연산 한다.
DoG영상에서 Local extrema를 검출하기 위해서 인접한(위, 아래) scale의 9개의 이웃들과 현재 scale의 8개의 이웃들을 비교하여 만약 이웃들의 전부보다 크거나 작으면 후보 keypoint로 선택된다.  



간단히 줄이면 위의 그림처럼 영상에대해 scale을 다르게한 가우시안 이미지들에대해 DoG를 뽑고 DoG영상에서 Extrema 점을 찾는다.
3x3x3공간에서 중심에 있는 값이 가장 크거나 가장 작을 때 keypoint후보가 된다.


2.Keypoint localization
 - keypoint의 후보로 만들어진 점들 중 매칭을 함에 있어 안정적이지 못한 점들을 제거하고, keypoint를 integer domain이 아닌 연속공간에 정확히 위치시킨다. 이를 위하여 테일러(Taylor)급수를 사용한다.

- Taylor 급수로 DoG영상을 전계하게 되면 이진 영상이 연속영상에 근사된다.

- 근사된 영상은 이진영상과 D값에서 다른 극점을 가지게 되므로, 이의 차이를 가지고 조정해 줄 수 있다. 이 차이가 어느 방향으로든 0.5(한 픽셀 간격의 50%)이상이 차이 나게 된다면, keypoint는 현재의 위치가 아닌 다른 점에 가까우므로 이동하여 다시 Taylor 급수를 전계하여야 한다.

- 이와 같은 근사 과정은 scale x, y좌표 뿐 아니라 scale에도 적용된다.

- 0.5보다 작다면 세밀하게 계산된 D함수의 극점의 좌표를 계산하여 keypoint의 위치를 조정한다. 이 과정에서 keypoint의 , , 그리고 scale이 정해진다.

- 또한 D값이 특정한 값(실험결과 0.03)보다 작다면 low contrast이므로 keypoint에서 제외시킨다.

- Edge Elimination : Harris corner detection에서 사용했던 Hessian Matrix사용법과 유사하게 threshold값을 주어 edge임을 확인하고 edge에 가까운 경우 keypoint에서 제외시킨다.

3.Orientation assignment
 - 각 keypoint의 direction, magnitude 즉, orientation을 구하는 단계.

- keypoint주변의 pixel의 orientation을 다음 두 개의 식을 이용하여 계산한다.

- Orientation histogram을 만든다.


가장 값이 큰 것을 해당 keypoint의 orientation으로 결정하며, 만약 해당 orientation의 값의 80%에 해당하는 다른 orientation이 있다면 또 다른 keypoint를 만들어 준다. 즉, 동일한 지점에서 여러 개의 keypoint가 존재 할 수 있다.

4.Keypoint descriptor

- keypoint를 중심으로 주변에 있는 gradient값들의 orientation을 구한다.

- 주변의 gradient값들은 Gaussian window를 사용하여 weighting하는데 그 크기는 해당 keypoint의 scale값의 1.5배에 해당하는 값을 사용한다. 즉, 마스크의 크기가 원래의 image에 적용되었던 크기의 1.5배가 됨을 뜻한다.

- Gaussian window의 목적은 window의 위치내에서 갑작스런 변화들을 피하고 descriptor의 중앙으로부터 먼 gradient들은
덜 강조하기 위함이다.


- Orientation Invariant를 위하여 Gradient값을 구할 때 사용하는 좌표는 반드시 keypoint의 방향으로 회전시켜주어 sampling한다.

- Illumination Invariant를 위하여 모든 orientation값을 normalization 해준다.

5.Matching

- template이미지와 환경이미지를 matching할 때, 먼저 두 영상의 keypoint database를 구성한 후 template이미지의 모든 keypoint를 환경이미지의 keypoint들과 비교한다. keypoint는 이미 스케일이 계산 되어 있고, normalization, orientation에 rotate되어 있기 때문에 단순히 배열을 비교하는 것으로 matching을 수행할 수 있다.

- 물체 인식에서 좀 더 좋은 결과물을 위하여, 하나의 keypoint에서 가장 가까운 matching된 keypoint와 두 번째로 가까운 matching된 keypoint사이의 거리가 일정 비율(0.8, 실험결과)이상인 경우 이를 matching에서 제외시킨다.

- BBF (Best-Bin-First) : KD tree의 구조를 가지며, 가장 유사한 Bin을 찾아나가는 방식으로 계산해 나가는 Matching을 수행한다. 빠른 속도를 보이기는 하지만, SIFT의 계산 과정이 워낙 느리므로, 전체적인 Matching은 할 수 없이 느리다.

- Hough transform을 사용하여 matching된 keypoint들을 clustering한다. 이는 하나의 물체를 이미지 내에서 추출해 낼 수 있도록 해준다. 또한 clustering된 물체의 affine 변환을 알아내기 위하여 프로젝션매트릭스 공식을 사용할 수 있다.

6.Conclusion

‧ keypoint는 rotation, illumination, scale, affine변환에 크게 영향을 받지 않게 정의되었다.

‧ 또한 Noise영상에도 크게 영향을 받지 않는다.

‧ 논문에서는 빠른 속도를 보여주고 있다고는 하지만, real time matching에 이용될 경우 굉장히 느린 속도를 보일 것이라 생각한다.

반응형

'영상처리 > Feature Detector' 카테고리의 다른 글

SIFT mind map  (3) 2012.03.21
Feature  (0) 2012.03.21
SURF(Speeded-Up Robust Features)  (7) 2010.05.19

댓글