OpenCV 특징점 검출과 매칭

크기 불변 특징(Scale invariant feature)

• 코너의 특징
  • 평탄한 영역, 에지 영역에 비해 변별력이 높음
  • 이동, 회전 변환에 강인
  • 크기 변환에 취약
• 크기 불변 특징점
  • 스케일 스페이스(scale-space) 또는 이미지 피라미드(image pyramid)를 구성하여 영상의 크기가 바뀌더라도 반복적으로 검출될 수 있는 특징점을 찾으면 매칭 등의 응용에서 사용할 수 있음
    • 스케일 스페이스: 블러와 이미지 크기를 줄여 만들어진 이미지 set들을 사용하는 방식
    • 이미지 피라미드: 이미지를 1, 1/2, 1/4, ... 크기로 줄인 후 이 이미지 set들을 사용하는 방식
  • 주요 크기 불변 특징점 알고리즘:
    • SIFT, SURF, KAZE, AKAZE, ORB 등
  • 특징점(feature point) $\approx$ 키포인트(keypoint) $\approx$ 관심점(interest point)
  • 기술자(descriptor) $\approx$ 특징 벡터(feature vector): 특징점을 벡터로 표현

$\\$
$\\$

SIFT

• Scale Invariant Feature Transform
• Scale & rotation invariant, local feature detector & descriptor
• 2020년 3월 알고리즘 특허 만료
• OpenCV 4.4 버전부터 메인 모듈로 통합됨

SIFT 계산 단계

• Detector: key point를 이미지에서 검출
  1. Scale-space extrema detection
  2. Keypoint localization
• Descriptor: key point 근방의 부분영상에서 특징 벡터를 추출
  3. Orientation assignment
  4. Keypoint description

Scale-space Extrema Detection

• 각 옥타브 별로 이미지를 Gaussian blur 처리 후(왼쪽), 연속된 gaussian blurring된 이미지들끼리 차 영상을 구함(오른쪽)
• DoG 영상에서 특징점의 위치를 찾게 됨

Keypoint Localization

• "The maxiam and minima of $\sigma^{2} \nabla^{2}G$ (=가우시안 함수를 두번 미분) produce the most stable image features..." (Scale-space theory)
• LOG(Laplacian Of Gaussian) 대신 DOG 영상의 모든 점에서 local maxima 또는 local minima를 선택
  • DOG는 LOG의 근사화 함수 ($\sigma=1.6$)

• 한 이미지 옥타브 기준, DOG로 만든 이미지가 준비되어 있을 때 현재 이미지 한 픽셀을 둘러싼 8픽셀, 전후 같은 위치의 9픽셀 각각을 모두 비교했을 때, 현재 픽셀이 다른 26개 픽셀보다 큰 지/작은 지 여부를 모두 만족할 경우 이 픽셀을 local Maxima/local Minima로 채택함
• 코너 위주의 특징점을 찾기 위해, 다음과 같은 필터링을 진행함
  • 서브 픽셀 정확도 높임
  • 낮은 대비(contrast) 극점 제거
  • 에지 성분 제거
    ==> 스케일, 회전 변화에도 다시 검출될 가능성이 높은 특징점만을 남김

Orientation Assignment

• 키포인트 근방의 부분 영상을 추출
• 부분 영상의 모든 픽셀에서 그래디언트 성분(크기&방향(을 계산
  • 방향 성분에 대한 히스토그램 생성 (360도에 대해 36개 빈)
• 히스토그램 최댓값 방향과 최댓값의 80% 이상 크기를 갖는 빈 방향을 키포인트 방향으로 설정
  • 하나의 좌표에서 여러 개의 키포인트 표현 가능

• 방향성분 최빈 히스토그램을 그림에 표현하면 화살표로 나타나는데, 긴 화살표는 이미지를 많이 축소시켰을 때 추출된 방향성분, 짧은 화살표는 원본 이미지에서 추출된 방향성분이라고 생각할 수 있음
• 각 키포인트에 대해 기준 방향 성분을 설정
  • 각 키포인트는 위치, 스케일, 기준 방향 정보를 가짐
  • 이를 이용하여 크기, 방향에 불변한 특징 벡터를 추출

Keypoint Description

• 각 키포인트 위치에서 스케일과 기준 방향을 고려하여 사각형 영역을 선택
• 사각형 영역을 4x4 구역으로 분할하고, 각 구역에서 8방향의 방향 성분 히스토그램을 구함
  --> 4 x 4 x 8 = 128 차원의 벡터(float 자료형)
  --> 128 x 4byte = 512byte
  --> keypoint 1000개면, 512KB

$\\$
$\\$

기타 특징점 알고리즘

SURF (Speed-Up Robust Features)

• SIFT를 기반으로 속도를 향상시킨 크기 불변 특징점 검출 방법
• DOG(Derivative of Gaussian) 함수를 단순한 이진 패턴으로 근사화
• 적분 영상(integral image)을 이용하여 속도 향상
• http://www.vision.ee.ethz.ch/~surf/

KAZE

• KAZE(바람): 비선형 스케일 스페이스에서 공기의 흐름
• 가우시안 함수 대신 비선형 확산 필터(nonlinear diffusion filter)를 이용하여 특징점을 추출
• SURF 보다는 느리지만 SIFT 보다 빠르고 동등한 성능
• http://www.robesafe.com/personal/pablo.alcantarilla/kaze.html

BRIEF (Binary Robust Independent Elementary Features)

• 이진 기술자를 이용한 빠른 키포인트 기술 방법(Not detector!)

• 키포인트 주변 픽셀 쌍을 미리 정하고, 픽셀 값의 크기를 비교하여 0 또는 1로 특징을 기술

• weak한 판별 기준을 많이 모아서 사용 (boosting)

  • 유사한 계산 방식으로, 매칭을 할 때 해밍 거리(Hamming distance)를 사용하기도 함.
    ex) 1011101 vs 1001001 의 경우, 서로 다른 비트 개수를 찾는 해밍거리는 2

• 특정 패치(p)에서 point pair (x,y)의 픽셀 값 크기 테스트:

  $\tau(p;x,y):=\begin{cases}1 & if p(x) < p(y)\\0 & otherwise\end{cases}$

• $n_{d}$차원 특징 벡터(기술자):

  $f_{n_{d}}:= \sum_{1\le i \le n_{d}} 2^{i-1}\tau(p;x,y)$

ORB(Oriented FAST and Rotated BRIEF)

• FAST 방법으로 키포인트를 찾고 Harris 코너 방식으로 순위를 매김
• 피라미드 영상에 적용하여 크기 불변성 확보
• 키포인트의 방향 성분을 이용하여 BRIEF 방법에서 픽셀 쌍의 좌표를 회전하여 특징 벡터를 추출 (이진 기술자)
• SIFT, SURF 보다 훨씬 빠르고 SURF보다 성능이 좋음

AKAZE(Accelerated KAZE)

• KAZE 알고리즘의 속도 향상 버전
• 비선형 공간에서 피라미드를 구축
• 이진 기술자를 사용
• https://www.youtube.com/watch?v=lI50PGr2TEU

$\\$
$\\$

References

• 자율주행 데브코스 황선규 강사님
• OpenCV documentation