SIFT

Introduction to SIFT (Scale-Invariant Feature Transform)

• SIFT algorithm의 개념을 이해한다.
• 우리는 SIFT Keypoints 와 Descriptors를 찾는 법을 배울 것이다.

Theory

이전 몇챕터에서 우리는 corner detector인 Harris 등 몇가지를 살펴보았다. 그것들은 회전 불변 (rotation-invariant)입니다. 즉, 이미지가 회전 되어도 같은 모퉁이를 찾을 수 있습니다. 그러나 스케일링은? 이미지의 크기를 조정하면 코너가 코너가 아닐 수도 있습니다. 예를 들어 아래의 간단한 이미지를 확인해보세요. 동일한 크기의 창에서 바라보는 이미지를 확대 / 축소 할 때 코너가 상대적으로 평평합니다. 이러한 문제점으로 Harris corner는 스케일 불변 적이 아닙니다.

따라서 2004년에 ,D.Lowe, University of British Columbia에서 새로운 알고리즘을 고안해 냅니다. 그의 논문에서 SIFT (Scale Invariant Feature Transform)는 Keypoints를 추출하고 그 디스크립터를 계산하는 Scale-Invariant Keypoints의 Distinctive Image Features로 소개됩니다. (이 논문은 이해하기 쉽고 SIFT에서 입수 할 수있는 최상의 자료로 간주되므로 이 설명은이 논문의 간략한 요약입니다).

주로 SIFT 알고리즘에 관련된 네 가지 단계가 있습니다. 하나씩 살펴봅시다.

1. Scale-space Extrema Detection

위의 이미지에서 우리는 같은 크기의 창을 사용하여 다른 Scale의 Keypoint를 감지 할 수 없다는 것을 알 수 있습니다. 작은 그림에서는 충분히 코너를 찾아내는 크기이지만, 큰 그림에서는 더 큰 창이 필요합니다. 이를 위해 스케일 공간 필터링(Scale-Space filtering)이 사용됩니다. 그것에서, Laplacian of Gaussian은 다양한 sigma 값을 가진 이미지로 발견됩니다.

LoG(Laplacian of Gaussian) 는 얼룩(blob)을 감지하는 것처럼 작동하며, 얼룩을 감지할때 sigma 가 변화함에 따라서 다양한 사이즈를 변화시킵니다. 다시말하면 sigma 는 scaling parameter 로 작동하며, 예를 들어서 위에 이미지에서 낮은 sigma 를 가진 gaussian kernel은 작은 코너그림에 대해서도 높은 값을 줍니다. 반면, 높은 sigma 를 가진 gaussian kernel 은 큰 코너그림에 잘 맞습니다. 따라서, 우리는 Scale 과 Space 에 따른 local maxima 를 찾을 수 있습니다. 이는 우리에게 다음의 리스트를 줍니다.

이 리스트는 해당 (x,y) 와 sigma scale에 keypoint 의 potential 좌표가 있음을 나타냅니다.

그러나 이 LoG 는 꽤 costly 하여서, SIFT 알고리즘은 LoG 대신 Difference of Gaussians 을 사용한다. Difference of Gaussians 은 두 개의 다른 sigma 가있는 이미지의 Gaussian blurring의 차이로 얻어집니다.

이를 $\sigma$ 와 $k\sigma$라고 해보자,

이 과정은 Gaussian Pyramid 이미지의 다른 옥타브에 대해 수행됩니다. 그것은 아래 이미지에 표현되어 있습니다.

일단이 DoG(Difference of Gaussians)가 발견되면, 스케일 및 공간에 대해 로컬 극한을 검색합니다. 예를 들어, 이미지의 한 픽셀은 8 개의 이웃과 비교된 후, 다음 스케일의 9 픽셀과 이전 스케일의 9 픽셀 비교를 합니다. 만약, local extrema 인 경우 이는 잠재적 인 키포인트입니다. 이것은 기본적으로 키포인트가 그 스케일에서 가장 잘 표현된다는 것을 의미합니다. 아래 그림과 같습니다 :

다른 파라메터들에 대해서, 이 논문에서는 경험적으로 데이터에서 얻은 값을 요약하고 있는데, number of octaves = 4, number of scale levels = 5 을 초기값이 $\sigma = 1.6$ , $k = \sqrt{2}$ 과 같을때 Optimal 값으로 사용하였다고 합니다.

2. Keypoint Localization

잠재적인 키 포인트 위치가 발견되면 더 정확한 결과를 얻기위해 정밀하게 수정해야합니다. 저자는 극한의 더 정확한 위치를 얻기 위해 스케일 공간의 Taylor 시리즈 확장을 사용했으며 이 극한치의 강도가 임계 값 (용지 당 0.03)보다 작 으면 제외되도록 하였습니다.. 이 임계 값은 OpenCV에서 contrastThreshold라고합니다. DoG는 모서리에 대한 반응값이 높기 때문에 모서리도 제거해야합니다. 이를 위해 Harris 코너 검출기와 유사한 개념이 사용됩니다. 그들은 2x2 Hessian matrix (H)을 사용하여 값이 큰 곡률(Pricipal curvature)을 계산했습니다. 우리는 해리스 코너 검출기로부터 모서리의 경우 하나의 고유 값이 다른 것보다 크다는 것을 알고 있습니다. 그래서 여기에서는 간단한 함수를 사용했습니다. 이 비율이 OpenCV에서 edgeThreshold라고하는 임계 값보다 크면 해당 키포인트가 삭제됩니다. 이 값은 논문에서, 10으로 주어졌습니다. 따라서 저 contrast 키포인트 및 edge 키포인트를 제거하고 남아있는 것은 관심사 키포인트입니다.

3. Orientation Assignment

이제 각 키포인트에 오리엔테이션을 지정하여 이미지 회전에 대한 불변성을 얻는 과정입니다. scale에 따른 키포인트 주변 픽셀들을 취하고, 그래디언트 크기와 방향이 해당 영역에서 계산됩니다. 360도를 커버하는 36 개의 Bins 가있는 방향 histogram 이 작성됩니다. (그라디언트 크기로 가중치를 부여하고 가우시안 가중치를 circular window 에 줍니다 이때의 sigma 는 keypoint 의 scale 의 1.5 배입니다.)

히스토그램에서 가장 높은 피크가 얻어지고, 80 % 이상이 되는 피크들이 방향을 계산하기 위해서 고려됩니다. 이는 동일한 위치와 Scale이지만 방향이 다른 키포인트들을 만듭니다. 이는 또한 매칭의 안정성(stability)에 기여합니다.

4. Keypoint Descriptor

이제 keypoint descriptor 가 생성됩니다. 키포인트 주변의 16x16 이웃을 택합니다. 그것은 4x4 크기의 16 개 하위 블록으로 나누어 질 수 있습니다. 각 하위 블록에 대해 8 bin 으로 된 방향 histogram 이 작성됩니다. 따라서 총 128 개의 bin 값을 사용할 수 있습니다. keypoint descriptor를 형성하기 위한 벡터로 표현됩니다. 이 외에도 조명 변화, 회전 등에 대한 견고성(robustness)을 확보하기 위해 여러 가지 조치가 취해집니다.

5. Keypoint Matching

두 이미지 사이의 키포인트는 가장 가까운 이웃을 식별하여 match시키는 과정입니다. 그러나 경우에 따라 두 번째 가장 가까운 match은 첫 번째 match에 아주 가깝습니다. noise 또는 다른 이유로 인해 발생할 수 있습니다. 이 경우 가장 가까운 거리에서 두 번째로 가까운 거리의 비율을 취합니다. 0.8보다 크면 이는 제외되는데. 그것은 약 5 %의 true matches(correct matches)만을 버리고 false matches의 약 90 %를 제거합니다.

지금까지가 SIFT 알고리즘의 요약입니다. 자세한 내용과 이해를 위해 원본 논문을 읽는 것이 좋습니다. 한가지 기억하십시오,이 알고리즘은 특허입니다. 따라서 이 알고리즘은 OpenCV의 Non-free 모듈에 포함되어 있습니다.

SIFT in OpenCV

이제 OpenCV에서 사용할 수있는 SIFT 기능을 살펴 보겠습니다. 키포인트 탐지로 시작하여 이를 그려 봅시다. 먼저 SIFT 객체를 생성해야합니다. 선택적 매개 변수를 전달할 수 있으며 문서에 설명되어 있습니다.

import cv2
import numpy as np

img = cv2.imread('home.jpg')
gray= cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

sift = cv2.SIFT()
kp = sift.detect(gray,None)

img=cv2.drawKeypoints(gray,kp)

cv2.imwrite('sift_keypoints.jpg',img)

sift.detect () 함수는 이미지에서 키포인트를 찾습니다. 이미지의 일부만 검색하고 싶다면, 마스크를 사용하는 기법을 쓸 수 있습니다. 각 키포인트는 (x, y) 좌표, 의미있는 neighbourhood의 크기, 방향을 지정하는 각도, 키포인트의 강도에 대한 응답 등과 같은 많은 특성을 갖는 구조입니다.

OpenCV는 키포인트의 위치에 작은 원을 그려주는 cv2.drawKeyPoints () 함수도 제공합니다. 만약 플래그인 cv2.DRAW_MATCHES_FLAGS_FLAWS_DRAW_RICH_KEYPOINTS를 건네 주면, 키포인트의 사이즈로 원을 그려줄것이며, 방향을 나타도 나타내 줄것입니다. 아래 코드 예제를 참조하십시오.

img=cv2.drawKeypoints(gray,kp,flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
cv2.imwrite('sift_keypoints.jpg',img)

아래에 두가지 결과를 나타내었습니다.

이제 descriptors를 계산하기 위해 OpenCV는 두 가지 방법을 제공합니다.

1. 이미 키포인트를 발견 했으므로 sift.compute ()를 호출하여 우리가 찾은 키포인트로부터 디스크립터를 계산할 수 있습니다.

예 : kp, des = sift.compute (회색, kp)

2. 키포인트를 찾지 못한 경우 sift.detectAndCompute () 함수를 사용하여 키포인트와 설명자를 한 번에 직접 찾을 수 있습니다. 두 번째 방법은 다음과 같습니다.

sift = cv2.SIFT()
kp, des = sift.detectAndCompute(gray,None)

여기서 kp 는 keypoints 의 list 이며, des 는 아래와 같은 모양의 numpy array 입니다.

따라서 우리가 keypoints, 디스크립터를 가졌다면, 우리는 이 키포인트가 다른 이미지와 얼마나 잘 match 되는지에 대해서 알고 싶습니다. 이는 다음 챕터부터 다루어질 것입니다.

https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_sift_intro/py_sift_intro.html