[Computer Vision / Image Precessing] SIFT (Scale Invariant Feature Transform)

SIFT는 Scale-Invariant Feature Transform의 약자로, 데이비드 로우(David G. Lowe)가 2004년에 처음 소개하였습니다. SIFT는 스케일과 회전에 불변하며, 특허를 받은 알고리즘이므로 OpenCV의 Non-free 모듈에 포함되어 있습니다.

 

 

SIFT의 장점은 다음과 같습니다.

• 지역성 : 지역 특징이기 때문에, 가림과 복잡한 배경에 강합니다(robust).
• 특수성 : 각각의 특징을 큰 규모의 객체 데이터베이스와 매칭시킬 수 있습니다.
• 수량 : 작은 객체에서도 많은 특징들을 검출할 수 있습니다.
• 효율성 : 실시간 성능에 가깝습니다.
• 확장성 : 다양한 특징의 종류들로 쉽게 확장할 수 있으며, 각 특징들을 더욱 견고하게 검출할 수 있습니다.

 

 

알고리즘

SIFT는 상당히 까다로운 알고리즘입니다. 알고리즘은 4단계로 구성됩니다.

• 스케일 공간(scale-space)과 극점(peak) 선택 : 특징을 찾기위한 후보 위치입니다.
• 특징점 지역화(localization) : 특징점의 위치를 정확하게 검출합니다.
• 방향(orientation) 할당 : 특징점의 방향을 할당합니다.
• 특징점 기술자 : 특징점을 고차원 벡터로 기술합니다.
• 특징점 매칭

 

 

스케일 공간 극점(Peak) 선택

스케일 공간 (Scale-space)

현실의 객체들은 오직 특정 크기(Scale)를 가져야만 의미가 있습니다. 여러분은 부엌에서 식탁 위에 놓인 각설탕을 완벽하게 식별할 수 있습니다. 하지만 지구 밖에서는 그 각설탕을 찾지 못할 것입니다. 다중 스케일(multi-scale)은 평소에도 아주 흔하게 느낄 수 있는 특성입니다. 이러한 스케일 공간의 특성을 디지털 영상에 적용하게 됩니다.

 

 

영상의 스케일 공간은 원본 영상의 서로 다른 스케일에서 가우시안 커널(블러링)의 컨볼루션 연산을 통해 생성되는 함수 L(x, y, σ)입니다. 스케일 공간은 옥타브(octaves)로 구분되며 원본 영상의 크기에 따라 옥타브와 스케일의 수가 달라집니다.

 

블러링 (Blurring)

한 옥타브 내에서 영상은 가우시안 블러 연산자를 통해 점점 흐려집니다. 수학적으로 블러링은 가우스 연산자와 영상의 합성곱으로 언급됩니다. 가우시안 블러는 각 픽셀에 적용되는 특정 표현식 혹은 연산자를 가지고 있습니다. 연산의 결과는 흐린 이미지입니다.

 

 

DoG (Difference of Gaussian kernel)

블러링 된 영상들을 사용하여 다른 이미지 셋인 Difference of Gaussian(DoG)을 생성합니다. DoG 영상은 특징점을 찾기 좋습니다. DoG는 다른 σ(블러 강도)가 적용된 두 영상의 차이로 구합니다. 이 과정은 가우시안 피라미드의 같은 옥타브 내 인접한 두 영상에 대해 이루어집니다.

 

 

특징점 찾기

지금까지 스케일 공간을 생성하고 이를 사용하여 DoG를 계산했습니다. DoG는 스케일에 대해 불변인 Laplacian of Gaussian(LoG)를 근사하는데 사용됩니다.

 

 

대상이 되는 영상의 한 픽셀을 중심으로 같은 스케일에서는 해당 픽셀을 둘러싼 8개의 이웃 픽셀과 차이를 비교하고, 다음 단계 스케일과 이전 단계 스케일에서는 중심 픽셀의 위치를 포함한 9개의 픽셀과 차이를 비교합니다. 이렇게 총 26번의 비교(check)가 이루어집니다. 만약 해당 픽셀이 지역 극점인 경우, 특징점 후보가 됩니다. 이는 특징점이 해당 스케일영상을 가장 잘 표현함을 의미합니다.

 

 

특징점 지역화

이전 단계에서 생성된 특징점 후보들은 많은 특징점을 제공합니다. 이 중 일부는 엣지(edge)를 따라 존재하거나, 충분한 대비(contrast)를 보이지 않습니다. 이 두 경우에는, 특징점으로써 유용하지 못합니다. 따라서 해당 특징점 후보들은 제외합니다. 이러한 접근방식은 Harris Corner Detector에서 엣지 특징들을 제거하는데 사용한 방식과 유사합니다. 낮은 대비의 특징점들은 그 강도(intensities)만 확인하면 됩니다.

 

더 정확한 극점의 지역을 찾기 위해 스케일 공간에 대해 테일러 급수 확장을 사용했고, 만약 극점의 강도가 임계값(논문에서는 0.03)보다 낮으면 특징점 후보에서 제외됩니다. DoG는 엣지에 대한 반응이 크기 때문에, 엣지 또한 제거해야 합니다. 때문에 주곡률(principal curvature)을 계산하기 위한 2 x 2 헤시안 행렬(Hessian matrix)을 사용합니다.

 

 

 

방향 할당 (Orientation Assignment)

이제 적절한 특징점들을 찾았습니다. 위 과정을 통해 검증된 안정적인 특징점들입니다. 우리는 이미 특징점이 감지된 스케일을 알고 있습니다. 따라서 스케일에 불변합니다. 다음은 각 특징점에 방향을 할당해 회전 불변으로 만드는 작업입니다.

 

 

스케일에 따라 특징점 위치 주변(neighborhood)을 취하여, 해당 지역에서 기울기(gradient)의 크기(magnitude)와 방향(direction)이 계산됩니다. 360도를 커버하는 36개의 빈(bin)으로 이루어진 방향 히스토그램이 생성됩니다. 특정 지점에서의 기울기 방향이 18.759도라고 가정한다면, 10-19도 빈 영역에 해당합니다. 빈에 추가되는 값의 "양(amount)"은 해당 지점의 기울기 크기에 비례합니다. 특징점 주변의 모든 픽셀에 대해 이 작업을 적용하면 어느 시점에서 히스토그램은 극점(peak)을 가지게 됩니다.

 

 

그 중 히스토그램에서 가장 높은 극점과 극점의 80%를 초과하는 극점도 방향을 계산하는 데 사용됩니다. 이는 같은 위치와 스케일은 같지만 방향은 다른 특징점을 만듭니다. 이 작업은 매칭의 안정성을 부여합니다.

 

 

특징점 기술자 (Keypoint descriptor)

이 시점에서 각 특징점들은 위치와 스케일, 방향 성분을 가지고 있습니다. 다음은 시점과 조도의 변화와 같은 변동에 대해 가능한 한 잘 구분되고 불변하는 특징점의 지역 영상 영역을 위한 기술자(descriptor)를 계산하는 작업입니다.

계산을 위해 특징점 주변에 16 x 16 윈도우를 취합니다. 이는 4 x 4로 구성된 16개의 서브 블록들로 구성됩니다.

 

 

각 서브 블록에서 방향을 8개의 빈으로 표현한 히스토그램이 생성됩니다.

 

 

16 x 16 샘플 배열에 거쳐 4 x 4의 기술자가 사용되었습니다. 4 x 4 x 8 방향은 128개의 빈 값들을 표현할 수 있습니다. 이는 특징점 기술자를 형성하기 위한 특징 벡터로 나타냅니다. 특징 벡터는 몇 가지 복잡한 점들을 수반합니다. "지문"을 완성하기 전에 이러한 점들을 제거해야 합니다.

1. 회전 종속성 : 특징 벡터는 기울기 방향 성분들을 사용합니다. 만약 영상을 회전시키면, 모든 성분이 변형됩니다. 당연히 모든 기울기 방향 성분들도 변형될 것입니다. 회전 독립성을 얻기 위해(회전 종속성을 제거하기 위해) 각 방향에서 특징점의 회전 성분을 빼줍니다. 이러한 연산을 통해 각 기울기 방향 성분들은 특징점의 방향에 대해 상대적으로 표현됩니다.
2. 조도 종속성 : 만약 큰 기울기 값에 대해 임계점을 둔다면, 조도에 대한 독립성을 얻을 수 있습니다. 128개의 기울기 값 중 0.2보다 큰 값들은 모두 0.2로 변경됩니다.(0.2는 논문에서 실험을 통해 결정된 값입니다.) 결과적으로, 특징 벡터는 다시 정규화됩니다. 또한 조도에 독립적인 특징 벡터를 얻게 되었습니다.

 

 

특징점 매칭 (Keypoint Matching)

두 영상 사이의 특징점들은 가장 근접한 주변(neighbors)을 식별하여 매칭시킵니다. 하지만 어떠한 경우에는 두 번째로 가까운 매칭이 첫 번째 매칭보다 더 유사할 수 있습니다. 이는 노이즈나 다른 이유들로 발생할 수 있는 현상입니다. 이러한 경우, 가장 가까운 매칭의 거리에 대한 두 번째로 가까운 매칭 거리의 비율을 이용합니다. 논문에서는 0.8보다 크면 해당 매칭은 제외합니다. 논문에 따르면 이는 잘못된 매칭(false matches)의 약 90%를 제외시키고, 올바른 매칭(correct matches)의 5%만 제외시킵니다.

 

 

(원 저작자에게 이용 허락을 받고 옮긴 글입니다.)

https://medium.com/data-breach/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40

Introduction to SIFT( Scale Invariant Feature Transform)