[Photogrammetry] 8-1. Visual Features Part2: Descriptors (SIFT, BRIEF, ORB)

dusruddl2·2022년 3월 18일

Photogrammetry (Cyrill Stachniss)

목록 보기

1/10

Binary features - 5 minutes with Cyrill

앞서 배운 SIFT는 성능이 검증된 알고리즘이지만, 128차원이라는 높은 차원의 벡터를 가졌기 때문에 연산량이 많다는 단점이 있었다.

따라서 이에 대한 대안책으로 제시된 것이 바로 binary descriptor을 이용하는 BRIEF 알고리즘이다. SIFT의 아쉬움을 보완한 것이므로, desciptor을 계산할 때 더 빠르고 쉬운 장점이 있다.

Binary descriptor

: 이진 테스트(Binary test)을 이용하여 부분 영상의 특징을 기술
: 이진 기술자를 사용하는 알고리즘 ex. AKAZE, ORB, BRIEF
: 이진 기술자는 해밍거리(Hamming distance)를 사용하여 유사도를 판단

BRIEF 알고리즘

Binary
Robust
Independent
Elementary
Features
: 각각의 bit는 1:1 comparison에 의하여 계산된다.
: 이 알고리즘은 keypoint을 검출하는 알고리즘이 아니라, 검출된 keypoint에 대한 descriptor 생성하는데 사용한다.
: keypont 주변 영역의 픽셀을 다른 픽셀과 비교해 어느 부분이 더 밝은지 찾아 이진 형식으로 저장한다고 할 수 있다.

간단한 예시

우리는 다음과 같은 예에서 descriptor을 만들어보겠다.
위에서 정의한 식에 따르면 I(5) = 255, I(1) = 90이고, I(5) > I(1)이기 때문에 b = 0이 된다.
이러한 과정을 계속 반복하게 되면,
다음과 같은 결과를 얻을 수 있다.

ORB(Oriented FAST Rotated BRIEF) 알고리즘

: BRIEF의 확장버전
: image의 rotation에 강한 성질을 갖고 있다.
: patch의 main orienatation을 측정함

`START!`

Motivation

우리는 이전 강의에서 다음 두 사진을 matching하기 위하여 keypoint를 찾는 방법을 공부했었다. 이번 강의에서는 이러한 keypoint에 대한 정보를 담고 있는 descriptor에 대하여 알아볼 예정이다.

Visual Features: Keypoints and Descriptors

앞서 배운 내용을 다시 한번 정리하겠다.

Keypoint란 이미지에서 locally distinct location을 의미한다.

feature descriptor이란 keypoint 주변에서 local structure을 요약해주는 역할을 한다.

이렇게 keypoint에 대하여 vector로 표현한 형태가 descriptor이다.

Today's Topics

그렇다. 오늘은 descriptor에 대해 배우고 descriptor을 만드는 다양한 알고리즘에 대하여 알아볼 것이다.

DoG(Difference of Gaussians)

저번 시간에 배운 내용 짧게 복습하겠다.
우리는 다양한 image pyramid level을 이용하여

1.(STEP1) Gaussian smoothing : 원본 이미지를 여러 크기로 만든 다음에 점진적으로 blur처리를 하였는데, 이때 blur처리를 할 때 gausisan연산이 사용된다.

2.(STEP2) Difference-of-Gaussians and find extrema
: 전 단계에서 얻은 같은 Octative 내에 인접한 두 개의 blur 이미지를 빼준다. 그리고 DoG이미지 내에서 극댓값, 극솟값의 대략적인 위치를 찾는다.
: 한 픽셀에서의 극댓값, 극솟값을 결정할 때는 동일한 octave 내에서의 3장의 DoG이미지가 필요하다. 체크할 DoG이미지와 scale이 한단계씩 다른 위아래 DoG이미지에서 체크하려고 하는 픽셀과 가까운 9개 총 26개 검사하고, 지금 체크하는 픽셀의 값이 26개의 이웃 픽셀값 중에 가장 작거나 가장 클 때 keypoint로 인정되는 것이다.

3.(STEP3) maxima suppression for edges
: 다음 사진은 Harris Corner Criterion을 첨부하였다. 여기서는 앞선 단계에서 찾은 keypoint 중에서 활용가치가 떨어지는 keypoint들은 제거해준다고 생각하는 것이 좋다. Eigenvalue test를 통해서 edge는 제거하고 corner만 남게 하는 것이 이 단계의 목적이다.

Popular Features Descriptors

다음 사진과 같이 descriptor을 찾는 알고리즘은 정말정말로 많은데.. 우리는 이 중에서 SIFT, BRIEF, ORB에만 집중하겠다.

SIFT Descriptor

SIFT(Scale Invariant Feature Transform)

image는 다음과 같은 transform에 invariant하다.
- image translation
- rotation
- scale
: 예를 들어, 이미지를 옆으로 조금 옮겨도 descriptor은 그대로라는 것이다.

그리고 다음과 같은 transform에 대해서는 partially invariant하다.
- illumination changes
- affline transformation, 3D projections
: affline transformation이란 선형변환 중 하나로 점, 직선, 평면을 보존한다.

visual landmarks를 찾는데에 적합하다.

다양한 angels와 distances에 대하여

다양한 illumination에 대하여

SIFT Features

SIFT Considers the Distribution of Gradients Around Keypoints

현재 우리가 하고 있는 과정을 사진으로 보면 한눈에 이해할 수 있다.

SIFT Descriptor in Sum

우리는 이제 keypoint들의 위치 & 스케일 & 방향을 알고 있는 상태이다. 이제 이 keypoint들을 식별하기 위해 지문(fingerprint)과 같은 특별한 정보를 각각 부여해줘야 한다. 각각의 keypoint의 특징을 128개의 숫자(keypoint descriptor)로 표현을 한다.

8 orientations x 4 x 4 histogram array = 128 dimensions (yields best results)

이를 위해 keypoint 주변의 모양변화에 대한 경향을 파악한다.
keypoint 주변에 16x16 윈도우를 세팅하는데, 이 윈도우는 작은 16개의 4x4 윈도우로 구성된다.

SIFT Illustration

이제 예시를 통하여 이해를 해보겠다.
다음 사진에서는 given keypoint가 있다. keypoint 주변의 지역을 orientation과 scale에 맞게 warp(왜곡)한 후에 그 지역을 16x16 pixel로 resize한다.
각각 픽셀에 대하여 gradients를 계산하고, 픽셀을 16개(4x4 pixels squares)로 나눈다.
각각의 square은, 8개의 directions에 대하여 gradient direction histogram을 계산한다.
histogram들을 연결하여 128(16x8)차원의 feature vector을 얻는다.

SIFT Descriptor Illustration

다시 한번 정리를 하자면,

(STEP1) keypoint주변의 지역을 추출하여 16x16 pixel로 resize한다.
(STEP2) 각각의 픽셀에 대하여 gradient를 계산하고, 픽셀을 16개(4x4 pixels squares)로 나눈다.
(STEP3) 각 square은, 8개의 방향에 대하여 gradient direction histogram을 계산한다.
(STEP4) square은 총 16개가 있으므로, hisogram을 연결하면 16x8 크기의 feature vector을 얻는다.

SIFT Approach Done!

이제 SIFT에 대한 설명이 끝났다.

keypoint는 DoG 연산을 통해 결정되었고,
descriptor은 gradient histogram에 의해서 결정되었다.

How to Match?

Based on Descriptor Difference

어렵지 않다. 왼쪽 사진의 keypoint에 대하여 오른쪽 사진에서의 모든 keypoint와 값을 비교해본 다음에 가장 비슷한 keypoint를 찾아주면 그것이 바로 matching되는 것이다.
초록색 라인과 같이 정확히 matching되는 곳도 있지만, 빨간색 라인과 같이 그렇지 않은 곳도 있다.