[Computer Vision/OpenCV] 21. Feature Descriptor(2) - SIFT

https://he-kate1130.tistory.com/150

[Computer Vision/OpenCV] 20. Feature Descriptor(1)

 

이전 글에서는 Feature Descriptor가 무엇인지 알아보았다.

오늘은 대표적은 Descriptor인 SIFT에 대해서 알아보자.

0. 문제점: Harris Corner Detector

이미지에서 지역적인 특징을 잘 추출해내는 것은 대다수의 비전 테스크에서 매우 중요한 역할을 한다.

우리가 기존에 배웠던 특징점 검줄 방식 중 하나는 코너를 키포인트로 검출하는 Harris Corner Detector가 있다.

Harris Corner Detector 알고리즘은 아래 포스팅에 작성되어있다.

https://he-kate1130.tistory.com/149

[Computer Vision/OpenCV] 19. Corner Detection - Harris Corner Detection

 

 

Harris Corner Detector의 베이직 아이디어

Harris Corner Detector는 윈도우를 적은 위치에서 움직였을 때 타겟 픽셀 주변의 변화량을 측정하여 코너를 검출하는 것이 기본 아이디어이다.

이 방식의 장점은 픽셀 주변의 local information을 관찰하고, 윈도우를 여러뱡향으로 이동하며 관찰하므로 rotation과 translation, intensity change에 Robust하다는 것이다.

 

그러나 이미지의 크기가 바뀔 때는 코너를 제대로 검출하지 못한다는 문제가 있다.

위의 이미지를 보자.

기존 코너로 검출되었던 부분은 이미지 사이즈를 스케일업했을 때 Edge 로 검출되게된다. 코너검출에 사용했던 윈도우의 크기가 커지지 않았기 때문이다.

원본 이미지에서는 특정 영역이 코너로 잘 검출되었더라도,
같은 구조를 가진 이미지라도 크기(스케일)를 키우면 해당 영역이 더 이상 코너로 인식되지 않는 문제가 발생한다.

 

이는 Harris Detector에서 사용하는 윈도우의 크기는 고정되어 있기 때문이다.
즉, 이미지가 커졌는데도 불구하고 동일한 크기의 필터를 사용하니, 상대적으로 더 넓은 영역을 한 번에 바라보게 되어
이전에는 ‘급격한 변화’였던 패턴이 이제는 완만한 변화로 느껴지는 것이다.

 

따라서 코너로 검출되던 부분이 스케일 업 후에도 코너로 검출되도록 하기 위해서는 커널의 사이즈 또한 그에 맞추어 커져야 할 것이다.

 

Scale Controllable Kernel

스케일 불변의 검출기를 만들기 위해서는, 커널이 이미지 구조의 크기에 맞게 적절히 조절되어야 한다.

이렇게 스케일에 따라서 커널의 크기를 조절할 수 있게 하는 구조를 Scale-Controllable Kernel이라고 한다.

 

그럼 또 다른 문제... O<-<

어떻게 Scale을 변경할까? 이미지의 스케일 변화를 예측해서 변경해야 한다.

 

이 때 사용하는 것이 바로 Blob Detection 기법이다.

 

1. 블롭 검출: Laplacian of Gaussian

Edge Detection 파트에서 본 적이 있는 LoG에 대해서 다시 살펴보자.
LoG연산은 Gaussian filtering과 Laplacian Filtering을 순차로 수행한 것과 같다.

 

왼쪽은 edgelike signal, 오른쪽은 corner like signal

Signal을 통해서 LoG가 적용되면 어떻게 시그널이 변하는지 살펴보자.

LoG를 엣지에 적용하면 양극성이 없는 Ripple 형태의 응답이 만들어진다. (왼쪽 plot들)

코너에 적용하게 되면 Ripple이 합쳐져 Blob 형태의 extremum이 생긴다.

즉, 시그마가 pulse의 width와 매치되는 순간 blob이 형성된다.

 

이 특성 때문에 Blob이 형성될 때의 시그마 값을 관찰하면 이미지의 스케일 정보를 추정할 수 있게 된다.

 

Scale Normalized Laplacian

다만 LoG의 시그마 값이 커지면 응답의 결과를 구분하기 어려워지므로 정규화를 수행하여 사용하도록 한다.

 

Difference of Gaussian

LoG를 사용하기에는 연산량이 많으므로 DoG의 근사를 이용해 계산한다. 

계산 방법은 간단하다.

아래 수식처럼 기준이 되는 가우시안에 시그마 값을 k배 하여 또 다른 가우시안을 구하고, 그 둘을 subset하면 된다.

 

가우시안을 미분할 필요 없이 두개의 가우시안 필터를 사용하면 된다는 (엄청난)장점이 있다

.

 

2. SIFT (Scale-Invariant Feature Transform)

https://www.researchgate.net/figure/Diagram-of-SIFT-keypoint-detection-algorithm-showing-one-octave-with-6-Gaussian-image_fig1_256546531

SIFT알고리즘은 위에서 알아본 Scale Space extrema 를 찾아 이미지의 scale에 맞는 키포인트를 찾아내고 이를 바탕으로 Dscriptor를 만든다.

 

STEP 1) Scale - Space Extrema Detection

Interst point들의 후보들을 찾아내는 단계이다.

첫 번째 단계에서는 입력 이미지를 다양한 해상도로 다운샘플링하여 다양한 크기의 이미지를 얻고,

각 이미지에서 Blob이 형성되는 부분을 찾아 Interest Point의 후보로 한다.

 

다음과 같은 단계로 진행된다.

 

1. 입력 이미지를 여러 해상도로 다운샘플링하여, 크기 차이가 큰 객체도 탐지 가능하도록 한다.
이렇게 다중 해상도로 이미지를 생성하는 것을 옥타브라고 부르며, 각 옥타브는 특정 해상도를 대표한다.

예를 들어, 첫 옥타브는 원본 이미지, 두 번째 옥타브는 1/2 크기로 축소된 이미지, 세 번째 옥타브는 1/4 크기 이미지가 된다.

 

2. 각 옥타브 이미지에 대해서는 다시 다양한 수준의 가우시안 커널을 적용한다.

이는 Gaussian 커널을 여러 스케일의 시그마로 변화시키며 필터링하는 작업으로, 이렇게 생성된 일련의 이미지들을 가우시안 피라미드라고 부른다.

한 옥타브 내에서는 원본 이미지 크기를 유지하면서 점차 Gaussian 블러 정도를 높인 이미지들이 생성된다.

 

 

3. 각 옥타브 내 인접한 Gaussian 이미지들 간 차이를 계산한다. 

즉, DoG를 계산하여 Blob을 찾을 수 있게 한다.

 

4. 이제 DoG 피라미드에서 Local Extema를 찾아낸다.

여기서 3차원 Non-Maximum Suppression를 적용해, 형성되는 Blob의 local extrema point를 찾는다.

이 지점들이 Interest Point의 후보들이 된다.

 

 

STEP 2) KeyPoint Localization 

앞선 단계에서 DoG 피라미드 상의 지역 극값을 기반으로 특징점 후보들이 추출되었다.

그런데 이들 중 일부는 노이즈 거나 엣지 위에 존재할 수 있고, 일부는 contrast가 크기 않은 약한 키포인트일 수 있다.

 

따라서 두번째 단계에서는 이러한 불필요하거나 신뢰도가 낮은 키포인트를 제거하고

나머지 키포인트들의 위치를 보다 정밀하게 추정하는 작업을 수행한다.

 

1. Sub pixel localization

우리는 앞선 스텝에서 키포인트의 locationd르 얻어왔는데, 정확한 위치정보로 선택되지 안았다.

이제는 더 정확한 위치를 알아낼 차례다.

D를 알고 있으므로 테일러 전개를 통해서 X를 알아낼 수 있다.

2. 이 위치에서 Contrast 가 낮은 경우(D가 임계값보다 작은 경우)를 제외한다.

논문에서는 0.03으로 th를 두었다.

 

3. Edge Like Feature를 제거한다.

DoG는 엣지 구조에 대해 높은 응답을 보이는 특성이 있다.

그러나 엣지에서 검출된 키포인트는 방향성이 불안정하고 반복성이 낮기 때문에 제거되어야 한다.

 

SIFT는 Harris 코너 검출기에서와 비슷하게, 헤시안 기반의 principal curvature분석을 수행한다.

 

이렇게해서 DoG를 이용해 후보 키포인트들을 뽑아내고, edge-like&low contrast 키포인트를 후보에서 제외하는것으로 키포인트 추출을 완료한다.

 

STEP 3) Orientation Assignment  

정제된 키포인트가 추출된 후, SIFT는 이미지의 회전 변화에 대해 불변성을 확보하기 위해 각 키포인트에 주 방향(primary orientation)을 부여한다.

이 과정은 각 특징점 주변의 local gradient분포를 분석함으로써 이루어진다.

 

1. 키포인트를 기준으로 16X16 크기의 윈도우를 관찰한다.

 

2. 이 윈도우 내에서 각각 2X2 블록을 보고 edge의 방향과 magnitude를 계산한다. (edge orientation계산)

 

 

3. gradient의 magnitude가 threshold보다 작은 지점은 weak edge부분으로 간주하고 throw out한다.

 

4. 8개의 discrete 한 방향으로 angle의 amgnitude 히스토그램을 만든다.

이때 magnitude에 가우시안 필터링을 적용하여 거리에 가중치를 부여한다.

히스토그램 내에서 가장 큰 피크를 이루는 방향은 해당 키포인트의 주 방향으로 설정된다.

그러나 하나 이상의 방향이 최고 피크의 80% 이상에 해당하는 경우, 각각의 방향에 대해 별도의 키포인트를 생성한다.

이로 인해 하나의 위치에서 위치와 스케일은 동일하지만 방향이 다른 복수의 키포인트가 생성될 수 있다.

 

여기까지 해서 키포인트는 다음처럼 나타내어진다. 

Keypoint1 : [ X 좌표,  Y 좌표, Scale factor, Octave, Orientation ] = [ 10, 20, 2.0, 3, 95 ]
Keypoint2 : [ X 좌표,  Y 좌표, Scale factor, Octave, Orientation ] = [ 10, 20, 2.0, 3, 25]

angle histogram 예씨

STEP 4) Key Point Descriptor Construction

각 키포인트에 대해 방향이 할당되면, SIFT는 그 주변의 지역적 이미지 구조를 정량화하여 Feature Descriptor를 생성한다.

하나의 키포인트는 4×4×8=128 차원의 고정 길이 벡터로 표현된다.

 

이렇게 Feature Descriptor형태로 만들기 위해서 다음과 같은 과정을 거친다.

1. 먼저 우리에게 키포인트의 위치, Scale, Octave 정보와 orientation 정보가 존재한다.

 

2. 이제 키포인트를 기준으로 16X16 윈도우를 설정한다.

 

3. 여기를 다시 4X4의 sub block으로 나누어 gradient histogram을 만든다.

이때 중심을 기준으로 gaussian 가중치를 적용한다.

 

이렇게 되면 각각 서브 블록마다 8개의 방향 히스토그램 정보가 생기고, 이것이 총 4X4개 존재하므로

하나의 키포인트에 대한 Descriptor는  8X4X4 =128 개의 정보로 표현할 수 있다.

즉, 128 차원의 벡터로 표현이 된다.

 

후처리로,

만들어진 벡터는 L2 Normalize를 수행하여서 조명의 밝기에 대한 영향을 줄인다.

이후에는 keypoint orientation값을 빼서 회전에 영향을 받지 않는, local 영역에 상대적인 벡터를 형성하게 한다. 

 

 

참고:

https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf

https://www.researchgate.net/publication/4351572_Boosting_of_factorial_correspondence_analysis_for_image_retrieval

https://docs.opencv.org/4.x/da/df5/tutorial_py_sift_intro.html

https://ballentain.tistory.com/47