[Yongggg's] SIFT (Scale Invariant Feature Transform)

안녕하세요! 오늘은 딥러닝의 붐이 일어나기 이전, 컴퓨터 비전 분야에서  매우 중요했던 개념인 SIFT (Scale Invariant Feature Transform)에 대해서 설명하겠습니다!

이 논문은 1999년에 나온 논문이지만, Image의 Feature을 extract하는데 정말 중요했다고 합니다. 컴퓨터 비전 분야의 Feature matching을 공부하면서 SIFT라는 논문이 얼만큼 중요했는지 알아보고 싶어서 정리하게 되었습니다!

이 설명은 고려대학교 김승룡 교수님의 강의와 bskyvision님의 블로그를 참고하여 정리하였습니다!

 

1. 목적

서로 다른 이미지 (같은 객체이지만 다른 각도에서 촬영한 두 사진, 한 사진을 바탕으로 회전을 한 사진 등)에서 같은 부분(유사한 Feature)을 갖는 Point를 matching 시키는 것은 어려운 Task이다. SIFT는 이미지의 크기와 회전에 강건한 특징을 추출하기 위한 알고리즘이다. 

2. 개념

서로 다른 두 이미지로부터 SIFT 알고리즘을 사용해 특징을 추출한 후, 서로 가장 비슷한 특징끼리 매칭해주는 개념이다. [그림 1]은 서로 다른 이미지에서 SIFT를 추출한 후, 비슷한 부분끼리 매칭을 한 결과이다. 크기와 영상의 각도가 다르지만 대부분의 matching Line이 알맞게 연결되어 있음을 확인할 수 있다. 이처럼 딥러닝이 나오기 전임에도 불구하고 SIFT 알고리즘은 매우 훌륭한 성능을 보였다.

[그림 1] SIFT를 사용하여 Image matching한 예제

3. 원리

SIFT 알고리즘은 다음과 같은 순서로 알고리즘이 동작한다.

1. Scale Space 만들기
2. Difference of Gaussian (DoG) 연산
3. KeyPoints 추출
4. Bad KeyPoints 제거
5. Keypoint Direction 할당
6. SIFT Feature 산출

위의 과정을 하나씩 살펴보도록 하겠다.

3.1.1 Scale Space 만들기

Scale Space에 대한 정의는 저의 블로그 Computer Vision 카테고리에 설명되어있습니다. https://yongggg.tistory.com/12?category=862525

위의 링크에서 확인 부탁드립니다.

[Yonggg's] Scale Space란?

 

 

SIFT에서 Scale Space를 만들 때에는 다음과 같은 과정을 따른다.

1. 원본 이미지를 두 배로 크게 만든 후, 점진적으로 블러되게 만든다.
2. 원본 이미지를 점진적으로 블러되게 만든다.
3. 원본 이미지를 반으로 축소시킨 후, 점진적으로 블러되게 만든다.
4. 원본 이미지를 $ 1 \over 4$로 축소시킨 후, 점진적으로 블러되게 만든다.

(1. 과정에서 원본이미지 사이즈를 두 배로 크게하는 이유는 DoG 이미지를 만들 때, 같은 옥타브 내의 인접한 2개의 블러 이미지를 활용하고 또, 이렇게 생성된 DoG 이미지들 중에서 인접한 세 개의 DoG 이미지를 활용하여 Keypoint를 찾기 때문이다.)

[그림 2]는 Scale Space를 만든 결과를 가져온 그림이다. (bskyvision님 블로그의 그림을 첨부했습니다.)

[그림 2] Scale Space 예시

이렇게 blurring 해주도록 하는 방법을 가우시안 blurring이라고 말하고, 이는 가우시안 연산자와 이미지를 컨볼루션 연삼함으로써 만들어줄 수 있다. 이는 [수식 1]처럼 표현할 수 있다. 

$$ L(x,y,\sigma) = G(x,y,\sigma) * I(x,y) \qquad [수식 1]$$

[수식 1]에서 $ L $은 블러된 이미지이고, $ G $는 Gaussian Filter, $ I $는 이미지를 뜻한다. $ x,y $는 이미지 픽셀의 좌표 값을 나타내고 $ \sigma $는 Scale 파라미터이다. $ \sigma $의 크기가 클 수록 더 흐려지게 된다.

가우시안 필터의 수식은 [수식 2]와 같이 나타낼 수 있다.

$$ G(x,y,\sigma) = {1 \over 2\pi\sigma^{2}}e^{-(x^{2}+y^{2})/2\sigma^{2}} \qquad [수식 2]$$

[그림 2]에서 점차적으로 blurring된 이미지를 얻기 위하여 [수식 2]의 $\sigma$ 값을 k배씩 높였다. 만약 처음에 $\sigma$ 값을 $ \sigma= {1 \over \sqrt{2}}$로, $k=\sqrt{2}$ 로 설정했고 두 배크기의 사이즈의 원본이미지가 처음에는 $ {1 \over \sqrt{2}}$의 값으로 blurring 되었다면, 그 다음에는 1, $\sqrt{2}$, 2의 값으로 blurring 되는 것이다. 이 $\sigma$ 값이 커지면서 점점 더 흐려진 결과를 볼 수 있다.

그리고 원본 이미지의 크기를 반으로 줄인 다음에는 $4\sigma$의 값으로 시작하여 k배씩 점차적으로 커지게하여 blurring 해준다. [그림 2]처럼 같은 사이즈를 갖지만 다른 blurring 정도를 갖는 이미지가 5장씩 존재하고, 총 4개의 옥타브(그룹)을 형성하게 된다.

이 과정은 우리가 물체를 볼 때, 선명하게 보이거나 흐릿하게 보이는 특징을 담기 때문에 SIFT는 이미지 크기에 Robust한 Feature를 matching할 수 있다는 것이다.

3.1.2 DoG 연산

3.1.1 과정에서 다양한 Scale을 사용해 Gaussian Blurring된 4개의 옥타브, 총 20장의 이미지를 도출했다. 이 이미지들을 Laplacian of Gaussian (LoG)를 사용하면, 이미지 내에서 특징이될 수 있는 Keypoint를 찾을 수 있다.

(LoG의 작동 원리는 다음과 같이 간략하게 설명할 수 있다. 먼저 이미지에 살짝 blurring 해준 후, 2차 미분을 해준다. 이는 [수식 3]처럼 나타낼 수 있다.)

$$ \nabla^{2}G \qquad [수식 3] $$

이 LoG 연산을 통해 이미지 내의 엣지들과 코너들이 두드러지게 된다. 이러한 엣지와 코너들은 Keypoint들을 찾는데 큰 도움이 된다. 하지만 LoG의 2차 미분 특성은 많은 연산이 요구되기 때문에, 비교적 간단하면서 비슷한 성능을 갖는 Difference of Gaussian (DoG)의 방법으로 대체할 수 있다. DoG도 LoG와 마찬가지로 엣지와 코너 정보를 도출할 때 널리 사용되는 방법이다. [그림 3]은 이 과정을 그림으로 나타낸 것이다.

[그림 3] DoG 연산

이 과정을 실제로 구현한 예제는 [그림 4]와 같다.

[그림 4] DoG 연산 예제

중간의 검은색 그림을 자세히 보면 얼룩말의 형상을 확인할 수 있다. 이를 더욱 자세히 보기위해 정규화한 DoG 이미지를 오른쪽에 나타냈다. 그림을 보면, 얼룩말의 줄무늬와 형상들이 보이는 것을 확인할 수 있다. 이미지의 엣지 정보들이 잘 도출되었다라고 할 수 있는 것이다. 이 과정은 모든 옥타브에서 동일하게 진행된다. 이 과정이 끝난다면 DoG 이미지들은 4개씩, 16장의 DoG의 이미지를 얻을 수 있을 것이다.

 

LoG를 DoG로 대체할 때, 가벼운 연산의 장점 이외의 것들을 살펴보고 넘어가겠다. LoG는 Scale의 불변성을 위해 $\sigma^{2}$으로 Laplacian 연산자를 정규화(Normalization)해줘야한다. 즉, LoG 연산자가 [수식 4]와 같이 scale-normalized LoG로 바뀐다.

$$ \sigma^{2}\nabla^{2}G \qquad [수식 4] $$

scale-normalized LoG의 극대값과 극소값은 매우 안정적으로 이미지의 특징을 나타낸다. 때문에 이 극대값과 극소값들은 Keypoint의 후보가 될 수 있다. 이러한 특징을 DoG도 가질 수 있을까? 이를 증명하기 위해 열 확산 방정식이 응용된다.

$$ {\partial G \over \partial \sigma} = \sigma \nabla^{2}G \qquad [수식 5] $$

열 확산 방정식에 의하여 [수식 5]과 같은 관계가 형성된다고 한다. Gaussian을 $\sigma$에 대해 미분한 것은 LoG에 $\sigma$를 곱한 것과 같다는 의미이다. 이것은 미분함수의 성질을 이용하면 [수식 6]과 같이 전개될 수 있다.

$$ \sigma \nabla^{2} G = {\partial G \over \partial \sigma} \approx {G(x,y,k\sigma) - G(x,y,\sigma) \over k\sigma - \sigma} \qquad [수식 6]$$

[수식 6]에서 양변에 우변의 분모를 각각 곱해주면, [수식 7]이 도출된다.

$$ G(x,y,k\sigma) -G(x,y,\sigma) \approx (k-1)\sigma^{2} \nabla ^{2}G \qquad [수식 7] $$

결국 다른 scale을 갖고 있는 Gaussian 이미지들끼리의 합, 즉 DoG는 scale-normalized LoG에 (k-1)을 곱한 것과 거의 같다. 그렇기 때문에 DoG는 scale 불변성을 보장하는 $\sigma^{2}$ scale 정규화 과정을 자연스럽게 포함하게 된다. 그리고 곱해진 (k-1)은 극대값, 극소값을 차즌데 아무런 영향을 주지 않기 때문에 무시가 가능하다. 이 특성은 LoG를 DoG로 대체할 수 있는 이유가 된다.

3.1.3  Keypoint 찾기

3.1.2의 최종과정에서 나온 4옥타브의 16장의 이미지를 갖고있다. 이를 이용해서 극대값과 극소값의 대략적인 위치를 찾는다. [그림 5]처럼 X표시의 pixel을 중심으로 DoG Image의 같은 크기의 인접 이미지의 26개의 pixel과 비교를 하는 원리이다. 

[그림 5] DoG 이미지에서 극대값과 극소값 찾기

자세히 설명하겠다. DoG 이미지와 scale이 한 단계씩 크고 작은 DoG 이미지를 사용하여 X 표시의 pixel이 극대값 혹은 극소값인지 확인한다. scale이 한 단계씩 다른 위 아래 두 DoG 이미지에서 X표시의 pixel과 가까운 9개의 pixel들을 검사한다. (지금 X 표시의 자기 자신 pixel은 제외한다. ; 총 26개가 나온다.) 

만약 지금 X 표시된 pixel이 26개의 pixel값 중에서 가장 작거나 가장 클 때, keypoint로 인정이 된다. (따라서 4장의 DoG 이미지들 중에서 가장 위에 있고 가장 아래에 있는 이미지들에서는 극대값, 극소값을 찾을 수 없다.)

이런 방식으로 DoG 이미지의 모든 픽셀에서 Keypoint들을 찾는다. 한 옥타브에 4장의 DoG 이미지가 존재하기 때문에 여기서 극대값 극소값을 찾으면 [그림 6]과 같이 두개의 극값 이미지가 나온다.

[그림 6] 극대값, 극소값을 구한 이미지

오른쪽의 두 장의 이미지를 확대해보면, 흰색 점들로 표현된 곳을 발견할 수 있다. 이 점들이 극대값, 극소값을 표현한 점이다. 이 점들이 일차적인 keypints라고 할 수 있다. 여기서 두 장의 극 값을 갖는 이미지를 얻기 위해 4장의 DoG이미지가 필요했다. 때문에 5장의 blurring이미지를 사용했던 것이다. (5장 blurring 이미지 -> 4장 DoG 이미지 -> 2장의 극값 이미지) 이로써, 네 그룹의 옥타브에서 모두 2장씩 극값 이미지가 나오기 때문에 8장의 극값 이미지를 얻게된다. 

하지만, 이렇게 얻은 극값들은 대략적이라고 할 수 있다. [그림 7]처럼 진짜 극대값과 극소값들은 픽셀들 사이의 공간에 위치할 확률이 높기 때문이다.

[그림 7] 진짜 극값의 위치 표시

하지만 이 극대값, 극소값들의 진짜 위치에 접근할 수 없기 때문에 subpixel의 위치를 수학적으로 찾아야한다. subpixel이란 픽셀들 사이에 위치한 것을 의미한다. 조금 더 정확한 극값들은 테일러 2차 전개를 사용하여 나타낼 수 있다. (테일러 전개는 한 함수 값을 함수의 점진적 미분 값을 무한대로 더했을 때, 원래의 함수값과 매우 근사한 값을 도출할 수 있다는 것이다.) 이는 [수식 8]처럼 나타낼 수 있다.

$$ D(x) = D + {\partial D^{T} \over \partial x} x + {1 \over 2} x^{T} {\partial^{2} D \over \partial x^{2}}x \qquad [수식 8] $$

여기서 D는 DoG 이미지이고, $x$는 $(x,y,\sigma)^{T}$이다. 이 것을 $x$로 미분하여 0이 되는 $x$의 값, 즉 $ \hat{x}$가 극값의 위치가 된다. 계산하면 [수식 9]와 같이 나타낼 수 있다.

$$ \hat{x} = - {\partial^{2} D^{-1} \over \partial x^{2}}{\partial D \over \partial x \qquad [수식 9]}

이 과정은 알고리즘이 조금 더 안정적인 성능을 낼 수 있도록 도와준다고 할 수 있다.

3.1.4 Bad Keypoints 제거

3.1.3 단계에서 극값들로 찾은 keypoints들 중에 Feature로서의 기능이 떨어지는 points들 제거해주어야 한다. 제거할 때에는 아래와 같이 두 가지의 기준으로 제거가된다.

1. 낮은 contrast의 keypoints를 제거
2. 엣지 위에 존재하는 keypoints를 제거

1.의 경우 DoG 이미지에서 keypoints들의 pixel값이 특정 값(threshold)보다 작으면 제거한다. 3.1.3과정에서 subpixel 위치에서 keypoints를 갖고 있기 때문에 이번에도 테일러 전개를 활용하여 subpixel 위치에서 픽셀 값을 구한다. 간단히 위에서 구한 $ \hat{x} $를 [수식 8]에 대입해주면 된다. 결과는 [수식 10]과 같다.

$$ D(\hat{x})=D+{1\over2}{\partial D^{T} \over \partial x}\hat{x} \qquad [수식 10]$$ 

[수식 10]의 절대값이 특정 값보다 작으면 그 위치를 keypoint에서 제거한다.

 

2.의 경우 DoG가 매우 민감하게 엣지를 찾아내기 때문에, 약간의 노이즈에도 반응할 수 있다. 즉, 노이즈를 엣지로 인식할 수 있다는 말이다. 때문에, 엣지 위에 있는 극값들은 keypoint로 사용하기에 위험성이 존재한다. 따라서 조금 더 확실하고 안전한 코너의 점들만 keypoint로 남겨주는 것이다. 이를 위해서 keypoint에서 수직, 수평 Gradient를 계산해준다. 이는 수평 방향으로는 픽셀값이 어떻게 변화하는지, 수직 방향으로는 픽셀 값이 어떻게 변화하는지에 대한 변화량을 계산하는 것이다. 만약 양 방향으로 변화가 거의 없다면 평탄한 지역(flat region)이라고 생각할 수 있다. 그런데, 수직 방향(또는 수평방향)으로 한 방향의 크기가 큰데, 나머지 방향으로는 변화가 적다면 엣지(가장자리)라고 판단할 수 있다. 또 수직, 수평 방향 모두 변화가 크다면 코너(모서리)라고 판단할 수 있다. 이는 [그림 8]과 같이 나타낼 수 있다.

[그림 8] flat, 엣지, 코너 그림

이 중에서 코너들이 좋은 keypoints이다. 따라서 코너의 keypoint들만 남기는 것이다. 또, Hessian Matrix를 활용하면 코너인지 아닌지 판별할 수 있다고 한다.

이 두 가지 제거 과정을 통해 [그림 9]와 같이 keypoint들의 개수를 확연하게 줄어들 수 있다.

[그림 9] Bad keypoints 제거 결과

3.1.5 Keypoint Direction 할당

3.1.4 과정에서 후보의 keypoints를 추려냈다. 이 keypoints는 scale invariance(스케일 불변성)을 만족한다. 이제 이 kepoints에 방향을 할당해서 rotation invariance(회전 불변성)을 갖게 할 것이다.

방법은 각 keypoint 주변의 그레디언트 방향과 크기를 모으는 것이다. 그 다음 가장 두드러지는 방향을 찾아 keypoint의 방향으로 할당한다. [그림 10] 처럼 하나의 keypoint 주변에 윈도우를 만들고, Gaussian blurring을 해준다. (이 keypoint의 scale값 ; 블러의 정도를 결정해주는 파라미터로 Gaussian blurring을 한다.

[그림 10] keypoint 주변의 윈도우 설정

이후, 그 안에 모든 픽셀들의 Gradient 방향과 크기를 [수식 11] 공식을 이용하여 구한다.

$$ m(x,y) = \sqrt{(L(x+1,y)-L(x-1,y))^{2}+(L(x,y+1)-L(x,y-1))^{2}} \\ \theta(x,y) =tan^{-1}((L(x,y+1)-L(x,y-1))/(L(x+1,y)-L(x-1,y))) \\  [수식 11] $$

결과는 [그림 11]과 같다.

[그림 11] 윈도우 내의 그레디언트 크기와 방향을 구한 결과

여기에서 Gradient 크기에는 Gaussian 가중 함수를 사용하여 keypoint에 가까울수록 더 큰 값을, 멀 수록 더 작은 값을 갖도록 한다. 이 과정은 [그림 12]와 같이 나타낼 수 있다.

[그림 12] Gradient 크기에 Gaussian 가중함수를 곱해준 결과

이제 각 keypoint에 방향을 할당해준다. 먼저 36개의 bin을 갖는 히스토그램을 만든다. 360도의 방향을 0-9도, 10-19도, 20-29도, $ \cdots$, 350, 359도로 10도씩 36개로 쪼갠것이다. 이 히스토그램은 [그림 12]의 윈도우의 모든 픽셀의 방향 값들을 bin에 채워준다. [그림 13]은 이 과정을 거친 후 타겟 픽셀이 갖는 Gradient 방향 히스토그램을 나타낸다.

[그림 13] 한 kepoint 주변의 그레디언트 방향의 히스토그램

여기서 bin이 가장 높은 bin을 갖는 방향으로 keypoint의 방향이 결정된다. 만약 [그림 13] 처럼 가장 높은 bin의 80% 이상의 높이를 갖는 bin이 있다면, 그 방향도 keypoint의 방향으로 인정된다. 한 keypoint가  개의 keypoint로 분리된다고 생각하면된다. (만약 3개의 bin이 가장 높은 bin의 80% 이상의 높이를 갖는다면, 총 4개의 keypoint로 분리된다.)

3.1.6 SIFT Feature 추출

3.1.5 까지 keypoint들을 추출하고 그에 대한 방향까지 산출했다. 이로써 keypoints의 위치와 스케일, 방향을 모두 알고있다.

이제 이 keypoint들을 식별하기 위해 fingerprint 같은 특별한 정보를 부여해준다. 각각의 keypoint의 특징을 128차원의 특징 벡터로 표현한다. 이렇게 표현하기 위하여 keypoint 주변의 모양, 방향등의 변화에 대한 경향을 파악한다. Keypoint 주변에 16 $ \times $ 16 윈도우를 세팅한다. 이 윈도우는 각각 4 $ \times $ 4 윈도우로 구성된다. [그림 14]는 이를 표현한 그림이다.

[그림 14] 하나의 keypoint의 특징을 나타내는 128개의 숫자를 얻는 과정

16개의 윈도우 속에 속한 픽셀들의 그레디언트 크기와 방향을 계산한다. 3.1.5 과정에서 했던 것처럼 히스토그램을 만들어 주는데, 이번에는 bin을 8개만으로 구성한다. (16 $\times$ 8 =128; 0-44, 45-89, $\cdots$ 320~359)

그 후, Gradient의 방향과 크기를 이용하여 bin을 채운다. 이렇게 하면, 결국 16개의 작은 윈도우들은 각각 자신만의 히스토그램을 갖게 된다. 이렇게 각 숫자를 구한다면, 128개로 구성된 feature vector를 구할 수 있게된다. 이 것이 바로 kepoint의 fingerprint가 된다.

하지만, 아직 회전 의존성과 밝기 의존성을 해결해야한다. 128개의 숫자로 구성된 feature vector는 이미지가 회전하면 모든 Gradient의 방향이 변한다. 회전 의존성 문제를 해결하기 위해, keypoint의 방향을 각각의 Gradient 방향에서 빼준다. 이렇게 한다면, 각각의 Gradient 방향은 keypoint의 방향에 상대적이게 된다. (Ex. keypoint의 방향을 구한 것이 20-29도라고 한다면, 이 값의 평균 방향 24.5도를 keypoint 주변 16개의 4 $\times$ 4 윈도우의 방향에서 빼준다. 이렇게 했을 때, 16개의 윈도우의 방향은 keypoint 방향에 상대적이게 된다.) 또, 밝기 의존성을 해결해주기 위해 정규화를 해준다. 이렇게 최종적으로 keypoints에게 fingerprint을 할당해줬다. 이를 바탕으로 유사도를 구해, 차이가 가장 작은 곳이 matching된다. 

4. 정리

이렇게 고전적인 Image matching 혹은 Image representation하는 방법을 정리해보았습니다. 요즘에는 딥러닝의 붐이 일어나면서 이러한 고전적인 방법보다 좋은 성능을 내는 모델이 많이 등장했다고 들었습니다. 하지만, 지금까지도 SIFT의 성능은 여러 딥러닝 기술과 견줄만 하고 좋다고 들었습니다. SIFT같은 고전적인 기술이지만 좋은 기술들을 딥러닝에 활용한다면 더욱 좋은 모델을 만들 수 있을 것이라고 생각합니다.

 

이렇게 SIFT에 대해 알아보는 시간이었습니다. 글의 오류나 문제가 되는 것들은 댓글로 남겨주시면 감사하겠습니다^^ !!