Skip to content

Scale-invariant feature transform

The scale-invariant feature transform (SIFT) is a feature detection algorithm in computer vision to detect and describe local features in images. It was patented in Canada by the University of British Columbia and published by David Lowe in 1999. Applications include object recognition, robotic mapping and navigation, image stitching, 3D modeling, gesture recognition, video tracking, individual identification of wildlife and match moving.

About

Harris Corner Detector 에서는 Scale변화에 따라 특징점이 검출 될 수도/안될 수도 있다. Scale이 변화되어도 특징점을 검출해낼 수 있는 SIFT알고리즘 이다.

  1. Detect Scale-Space Extrema: Scale-Space를 만들어서 찾아낼 수 있는 모든 Key Candidate를 찾는다.
  2. Accurate Key Point: 위에서 넘어온 Key Candidate중에는 Edge, Corner, Blob 등이 포함되는데 그 중에 중요도가 높은 Edge나 Corner,blob등을 고르는 것이다.
    • Low Contrast 제거
    • Edge Thresholding
  3. Assign Orientation: Key를 중심으로 16x16패치를 잡은 뒤 Gradient Magnitude / Orientation을 정해준다. 그 후 Histogram을 그리게 되는데 각 방향으로 Magnitude를 그대로 사용하는것이 아니라 Gaussian weighted Function을 곱해서 Histogram에 사용한다. 즉, Key중심에 조금 더 큰 가중치를 두고 Histogram을 그린다는 소리다.
    • 이 때 Histogram상 Peak인 방향을 Key Orientation으로 잡게 되는데 Key orientation의 80%이상의 Peak가 또 있다면 그것또한 Key Orientation이 된다.
  4. Key Point Descriptor: 앞에서 Key Orientation을 찾아냈다. 여기서 회전 불변의 방법이 나온다. 찾아낸 Key Orientation을 0도로 역회전 시켜서 Descriptor를 만들어 낸다. 즉,Key Orientation이 60도면 역으로 60도만큼 돌려서 Key Orientation을 0도 기준으로 잡는것이다. 이 상태에서 16x16 픽셀을 4x4Cell로 합쳐서 8방향 Histogram을 그리고 4x4x8의 Descriptor를 만드는 것이다.(주로 128Demension사용)
  5. Key Matching: 입력영상과 Descriptor간의 매칭. 각 Key와 Descriptor간의 유클리디언 거리를 계산하여 가장 작은(가까운) 값을 갖는 Key를 찾는다. 이때 제일 가까운 Key와 두번째로 가까운 Key 간의 비교를 해서 차이가 얼마 없으면 Key matching에 사용하지 않게 된다.

See also

Favorite site

References

  1. Bskyvision_-_Scale_Invariant_Feature_Transform.pdf ↩