Keypoint Detector : SIFT & SURF Algorithm 비교

이번 포스팅에서는 computer vision 분야 중 keypoint detection task에서 전통적으로 사용되어온 대표적인 SIFT와 SURF 알고리즘을 비교하여 정리해 볼까 합니다.

이 글은 각각의 영상 feature의 세부 구현이나 특징을 열거하기보다는 전체적인 관점에서 두 알고리즘의 동작원리 및 특성을 파악하는 것이 목적이라 글은 최대한 간결하게 쓰고자 하며 BRIEF, ORB 등 기타 invariant local feature들에 대해서도 향후 별도 포스팅하여 다뤄볼 예정입니다.

1. SIFT detector

• SIFT detector는 다음과 같은 순서로 동작
  1. 가우시안 blurring을 통한 Scale space construction 수행
  
  -> 이미지의 각 픽셀별로 가우시안 필터를 적용시켜 이미지의 사이즈를 점차 줄여나가는 형태의 가우시안 피라미드를 통해 Scale Space를 생성
  2. Local Extrema Detection(26개 neighbors 끼리의 DoG 비교)
  
  - 픽셀 주변의 8개 픽셀과, 같은 octave 내 scale이 하나씩 다른 두 DoG 이미지에서의 체크하려고 하는 픽셀과 동일 위치의 픽셀 9개씩, 총 26개의 neighbor끼리의 DoG를 비교. 이때, 픽셀값이 26개 neighbor 픽셀 중 가장 크거나 가장 작은 값을 갖는 픽셀을 keypoints candidate로 선정.
  3. Descriptor construction(128 bin histogram)
  - Descriptor 생성목적? 추출한 keypoints들을 식별하기 위해 사람의 지문과 같은 구분되는 정보를 부여해주기 위함.
  
  - 16x16 사이즈의 큰 윈도우를 기준으로, 4x4 사이즈의 작은 윈도우 16개로 구성되는 descriptor를 가정하였을때 16개의 작은 윈도우에 속한 픽셀들의 gradient 크기와 방향을 계산해준다. 이때 bin을 8개로 하여 360도를 8방향으로 나누고 gradient 크기와 방향을 이용하여 각각의 bin을 채워준다. 16개의 작은 윈도우들은 모두 자신만의 히스토그램을 가지게되며 16개의 작은 윈도우마다 8개의 bin이 있으므로 16*8=128개의 숫자 vector를 가지게됨. 이것이 바로 각각의 keypoint들을 구별해주는 원리이다.
  - 회전 의존성 문제를 해결하기 위해 : 각각의 keypoint들의 방향을 gradient 방향에서 빼줌.
  - 밝기 의존성 문제를 해결하기 위해 : 정규화 진행
  4. Image Matching
  - 앞서 구한 Descriptor를 이용하여 이미지와 keypoint들 간의 L2 distance 값을 계산하여 가장 가까운 keypoints들이 많은 이미지가 similar한 이미지라고 판단 가능함.

• SIFT detector는 Harris detector와 다르게 이미지의 scale과 rotate 변화에 robustness하다는 장점이 있다.**

2. SURF detector

• SURF detector는 다음과 같은 순서로 동작
• SURF에서는 가우시안 필터 형태를 단순화한 box filter를 사용하여 필터의 스케일을 키우면서 극점을 찾는 방식임. 이미지의 사이즈를 직접 줄이며 극점을 찾는 SIFT보다 필터의 스케일을 늘리는 방식으로, SURF가 SIFT보다 훨씬 빠른 속도를 보임.
  1. Computation of Integral Image
  
  - 왼쪽 위 끝 픽셀값에서부터 현재 좌표까지의 pixel 합을 구해서 intergral image 만들어놓음으로써 연산을 보다 빨리 수행가능. 이는 Hessian Matrix determinant 구할 때 사용됨.
  2. Computation of Hessian Matrix Determinant
  
  - 가우시안 필터를 단순화한 box filter에서 hessian matrix를 구하고 det를 계산.
  3. hessian matrix determinant 결과값을 normalize
  4. SIFT와 유사하게, 26 neighbors 픽셀값들을 비교하여 hessian matrix determinant 결과값이 threshold보다 큰지 판별하여 keypoints 후보를 선정.
  5. wavelet response를 바탕으로, keypoints 후보들에 대해 orientation과 descriptor를 계산하고 계산결과를 바탕으로 이미지와 keypoint 매칭한다.
  

• 이러한 방식은 scale과 rotation에 robustness한 특성이 있으며 이미지간 scale/사이즈가 다르더라도 매칭이 가능하다는 특징이 있음.
• SURF에서는 가우시안 필터 형태를 단순화한 box filter를 사용하여 필터의 스케일을 키우면서 극점을 찾는 방식임. 이미지의 사이즈를 직접 줄이며 극점을 찾는 SIFT보다 필터의 스케일을 늘리는 방식으로, SURF가 SIFT보다 훨씬 빠른 속도를 보임.
• SURF의 이러한 방식이 가능한 이유는 이미지 처리 관점에서 이미지가 blur 처리되는 행위는, 이미지가 original size보다 작아지며 Scale은 커지게 되는 현상과 동일한(매칭되는) 행위이기 때문임.