CV 2. SIFT

Computer Vision [2]

1. SIFT(Scale-Invariant Feature Transformation)

앞 장에서, Harris Corner Detection은 Scale variation에 취약하며, Laplace of Gaussian (LoG)는 연산량이 많다고 언급하였다. 이를 해결하기 위해서 SIFT가 제안되었는데, SIFT는 두 부분으로 나뉜다.

1). Detector - Interesting point를 찾고 그 point를 filtering 한다.

2). Descriptor - Interesting point 주위의 방향을 바탕으로 dominant한 orientation과 주변 pixel들의 방향에 대한 정보를 끌어낸다.

이 두가지 방법으로 인해서 SIFT는 

1). Scale Variation (Difference of Gaussian 기반의 Scale Space에서 Maximum point를 찾아냄으로, Scale에 불변하는 Interesting point를 찾아낸다.)

2). Illumination Change (Gradient 값을 사용하기 때문에 Illumination change에 강인하다.)

3). Rotation and Viewpoint change (Interesting point의 orientation과 주변 pixel들의 orientation을 고려하므로 Rotation과 Viewpoint change에 강인하다.

1) Detector

LoG의 문제점은 연산량인데, 이를 해결하는 방법은 다음과 같다. 서로 다른 Sigma를 갖는 Gaussian Filter를 적용하고 적용된 Image의 차이를 계산함으로써, Normalized Laplace of Gaussian을 근사화한다. 다음 식을 보면 쉽게 이해할 수 있다. 

서로 다른 Sigma (or Scale)을 갖는 Gaussian Filter를 적용한 후, 이 차이를 계산하면 Normalized Laplace of Gaussian을 근사할 수 있는 것이다! Gaussian Filter는 n x 1 과 1 x n filter로 쪼갤 수 있어, n x n Gaussian Filter는 2 x n 의 parameter로 표현될 수 있다. 그리고 Gaussian Filter의 sigma는 Gaussian Filter를 convolution하는 연산을 통해서 늘릴 수 있다.

그러므로, 하나의 Gaussian Filter를 여러번 Convolution을 적용시키는 방법을 통해서 별도의 sigma를 갖는 Gaussian Filter를 재정의할 필요가 없는 것이다. 그리고 sigma가 original image의 sigma에 비해서 2배가 되는 경우 크기를 1/2배로 축소 (Width/2, Height/2)하여 다시 sigma를 적용한다. (이미지의 크기를 1/2배로 축소하는 이유는 연산량을 줄이기 위함 + sigma가 2배된 것은 image의 scale을 2배로 확대하는 것이므로 이미지의 크기를 1/2배로 축소하는 것과 동일한 효과를 볼 수 있다.)

이렇게 얻어진 Gaussian Smoothing Images로 부터 서로 인접한 Image를 빼줌으로써 Difference of Gaussian (DoG)를 얻을 수 있다. 서로 인접한 3개의 DoG로 부터 가장 값이 Max인 Point를 찾으면 이 point는 Interesting point의 후보가된다.

SIFT에서는 이 1. Interesting point의 위치를 다시 보정해주고, 2. Edge인 점을 제거해주기위해 추가적인 Filtering을 진행한다.

(1). Interesting point의 위치를 보정

Image의 x,y는 discrete하지 continuous하지 않으므로, discrete한 x,y 점이 Interesting point의 정확한 위치를 빗나갈 수 있다. 따라서, continuous한 상황으로 가정하여 미분 값이 0이 되는 부분을 찾아서 Interesting point의 위치를 수정한다. 그리고 이 point에서의 절대 값이 0.03보다 작은 경우 low contrast를 갖는 것으로 제거한다. 

(2). Edge인 점을 제거

1번 과정을 통과한 후에 Interesting point의 location에서 Hessian matrix를 계산한 후에 이 Hessian matrix가 다음 식을 만족하면 한쪽 방향의 edge response가 강한 것으로 가정하여 이 점을 제거한다.

밑의 그림은 scale-space extrema (즉, interesting point 후보)중 low constrast와 edge point를 제거한 결과를 보여주고 있다.

After scale space extrema are detected (their location being shown in the uppermost image) the SIFT algorithm discards low-contrast keypoints (remaining points are shown in the middle image) and then filters out those located on edges. Resulting set of keypoints is shown on last image. (출처: Wikipedia, Scale-Invariant feature transformation, https://en.wikipedia.org/wiki/Scale-invariant_feature_transform)

2) Descriptor

1) Detector 과정을 통해 얻은 Interesting point 주위로 pixel들의 방향을 다음 식으로 계산한다.

L은 Gaussian Filter (Noise에 강인)를 통과한 Image를 가리킨다. Interesting point 주위의 pixel들의 방향을 계산한 다음에, 가장 dominant한 방향을 histogram으로 찾아낸다. (bin의 개수는 hyper-parameter) Histogram 방법은 small variation에 강인한 특징을 갖는다.

그 다음, 주위의 pixel들의 방향들을 계산하여, 128 dimension (16 quadrant * 8 bin histogram)의 descriptor를 얻어낸다. 이때 중요한 것은 앞의 과정에서 찾은 dominant orientation에서 각 pixel의 방향을 찾아야한다는 것이다.

2. What is the next?

SIFT는 hand-crafted features로서, Image의 low-level만을 고려한 것이다. (즉, Gradient 값만 고려) 따라서, high-level의 semantic 정보를 얻을 수 없는데, 이를 가능하게 한 것이 바로 Deep Learning이다. low layer에서 추출된 low-level features들은 상위 layer로 이동하면서 결합이 되고 결합된 feature들은 low-level features보다 위 단의 high-level semantic 정보를 갖게 된다 (데이터로 이 feature를 학습한다.). (Edge and Blobs -> Textures -> Object's part) 

SIFT, Difference of Gaussian, Laplace of Gaussian, Orientation, Histogram, Hand-crafted Features