[Computer Vision] 7. Matching & Geometrical alignment

Matching

물체를 비교해서 동일한지 비교하는 것을 매칭이라고 한다.

보통 두 오브젝트 사이의 유사도 거리를 비교한다.

 

만약 3개 이상의 매칭 페어가 발견되면, 그 물체의 위치와 방향을 결정할 수 있다.

 

일반적인 매칭 과정은 간단하다.

특징점들 (관심 포인트) 사이의 유사도를 계산한 뒤, 가장 큰 값을 갖는 것을 대응 쌍으로 결정한다.

또는 일치하는 관심 포인트 사이의 거리를 계산하여 가장 작은 거리를 갖는 것을 대응쌍으로 결정할 수도 있다.

 

하지만 매칭과정에서 현실적인 문제가 있다.

예를 들어 서로 다른 특징을 매칭쌍으로 결정하거나 (false-positive), 유사도 점수가 낮아 동일한 객체의 특징이 매칭되지 않을 수도 있다. (false-negative)

 

이 경우, 전형적인 해결책은 많은 매칭 쌍을 찾은 뒤, 신뢰도가 높은 쌍을 분류하는 방법을 취한다.

 

그 밖에도, 매칭의 계산속도에 대해서도 문제가 존재한다.

만약 두 영상의 특징이 각각 m, n 차원의 특징 벡터를 갖고, 그 벡터의 차원이 d라면, Θ(mnd) 의 시간복잡도를 갖는다.

 

Mahalanobis 거리

기본적인 매칭 방법은 이전 글의 방식으로 추출한 특징 벡터들 사이의 거리를 측정하는 것이다.

 

 

두 특징벡터를 위와 같이 나타낼 때, 이 둘 사이의 거리는 유클라디안 거리로 다음과 같이 표현할 수 있다.

 

유클라드 거리는 두 점이 얼마나 가까운지를 측정하는 기본적인 방법이지만, 두 점의 분포를 고려하면 다른 거리 측정 방법이 필요하다는 것을 알 수 있다.

 

 

위 그림 예시를 보자.

어떤 점의 분포로부터, c와 마이크로 사이 거리가, b-마이크로 사이 거리보다 멀다.

하지만 c가 마이크로가 속한 분포에 속해있다고 볼 수 있고, b는 마이크로가 속한 분포 밖에 있다고 볼 수 있기 때문에, 더 특징에 가깝게 일치하는 점은 c라고 할 수 있다.

 

그래서 Mahalanobis 라는 인도 통계학자는 다음과 같은 거리 계산법을 제안했다.

 

이때

 

만약 공분산 행렬의 합이 identity 행렬이라면, 유클라드 거리와 Mahalanobis 거리는 같다.

 

예시

 

다음과 같은 점의 분포가 있다.

각 점의 좌표는 (2,1), (1,3), (2,5), (3,3) 이다.

이 4개 점의 분포 평균내면, (2,3) 이 되는데, 이 점을 μ 라고 하자.

 

만약 유클라드 거리를 구한다면, μ-b 사이의 거리는 2, μ-c 사이의 거리는 3 이다.

 

이제, 각 점의 분포를 고려하여 거리를 구해보자.

우선 먼저 공분산 행렬의 역행렬 Σ^-1 을 구해야 한다.

이는 각 점와 좌표 (x1, x2) 에 대해, x1 들에 대한 분산, x2 들에 대한 분산을 구하고, 각각을 v1, v2 라고 할 때

 

(v1 0)

(0 v2)

 

와 같이 나타낼 수 있다.

 

위 예시에서 v1 = 0.5 이다.

 

v2 = 2 이다.

 

이를 이용하면 공분산 행렬을 다음과 같이 나타낼 수 있다.

 

이의 역행렬은, 그냥 두 분산위치를 바꿔주면 된다.

 

 

만약 이 4개 점에 대한 분포를 D 라고 표현한다면, (위 기본 수식의 Q에 해당)

다음과 같이 mahalanobis 거리를 구할 수 있다.

 

 

Dm(b, D) 와 Dm(c, D) 로부터, 점 c가 점 b 보다 더 분포에 가깝다는 것을 알 수 있다.

 

---

Matching & Performance Evaluation

이제 거리를 구하는 방법을 사용하여 매칭을 시켜보자.

 

두 이미지의 특징 벡터를 다음과 같이 나타낼 때, 가장 간단한 매칭 방법은 두 특징벡터 사이의 거리가 T 라는 임계값보다 작은지 보는 것이다.

 

 

이때 이 거리는 유클라드 거리, mahalanobis 거리, 어떤 것을 사용해도 괜찮다.

이 방법을 사용할 때는 T 값을 어떤 걸 사용할지 잘 결정해야 한다.

만약 T가 너무 작으면 정말 가까운 특징들만 검출되고 (특징인데, 부정해서 검출되지 않는 FN이 발생한다), 너무 T가 크면 거리가 먼 특징까지 모두 검출될 수도 있기 때문이다. (특징이 아닌데 긍정해서 검출되는 FP가 발생한다.)

 

 

이떄, FP, TP, FN, TN을 조합해서 위와 같은 값들을 구할 수 있다.

제일 좋은 것은 TPR이 클 수록 좋은 것이다.

(실제로 특징인 점 중에서 맞다고 긍정한 비율)

 

그리고 FPR은 낮을 수록 좋다.

(특징이 아닌 점 중에서 특징이라고 잘못 검출한 비율)

 

이 두 값을 축으로 하면 ROC(Receiver Operating Characteristic) 곡선을 구할 수 있다.

그림의 축이 반대로 바뀌었는데, c2로 갈 수록 좋은 것이다

.이 곡선은 T값을 증가시킬 때마다 FPR, TPR이 어떻게 변화는지를 점으로 찍어서 이은 그래프다.

 

만약 T가 작으면 FP가 감소하고, FN이 증가한다.

틀릴바에 그냥 검출하지 않게 된다.

 

만약 T가 증가하면 TP를 따라 FP가 증가한다.

 

이 곡선은 성능 분석을 위해 주로 사용된다.

c0 직선은 램덤으로 추측했을 때의 성능을 나타낸다.

 

c2로 갈 수록 좋다는 것은 바꿔말하면 곡선의 영역 (Area Under Curve, AUC) 이 넓을 수록 좋다고도 볼 수 있다.

이는 특정 숫자 하나로 더 좋다는 것을 판별할 때 사용한다.

 

 

이 매칭 방법의 대체 방법은, 가장 가까운 이웃을 찾는 것이다.

예를 들어 어떤 특징벡터 a와 매칭되는 특징 벡터를 찾을 때, 모든 벡터들 중 a에 제일 가까운 벡터 b를 찾는것이다.

이때 가장 가까운 이웃 벡터 b의 거리가 T 라는 임계값보다 작다면 매칭대상이 된다.

 

또 다른 방법은 가장 가까운 거리 비를 구하는 것이다.

이 방식은 a 에 제일 가까운 특징벡터 b를 구하고, 그 다음으로 가까운 특징벡터 b' 을 구한다.

이때 다음 식이 만족하면

 

(어떤게 특징벡터일까..... 강의록 내용이 여기에서 끊겼다....)

 

---

Fast Neareset Neighbor Search

가장 가까운 이웃을 찾는 나이브한 방법은, 두 이미지 a, b의 특징벡터 갯수 n, m 에 대해, n x m 번 반복문을 돌변서 모든 두 특징벡터 사이의 거리를 구하는 것이다.

 

이보다 더 빠르게 가장 가까운 이웃을 찾기 위해, kd tree 라는 것을 사용할 수 있다.

kd 트리는 BST의 변형 버전이다.

 

또는, 해시함수에 기반한 locality-sensitive hashing 기법을 사용해서 구할 수도 있다.

이 두 방식은 다차원 벡터들에 대해 자주 사용되는 방식이다.

 

kd tree

BST는 루트노드의 값보다 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 존재하는 재귀 조건을 만족하는 트리이다.

이를 통해 어떤 값을 찾는다면, O(log n) 시간에 찾을 수 있다.

이 BST를 특징 벡터를 매칭하는데 사용해보자.

 

특징벡터는 다차원이고, '같은 값을 갖는 노드' 가 아니라, '제일 가까운 값' 을 찾는 것이 목적이다.

그래서 BST를 그대로 적용하는 것은 불가능하다.

 

이를 조금 변형한 kd 트리는 아래와 같이 생성한다.

 

- n개의 특징 벡터가 주어져있을 때, 각각의 특징벡터는 d차원이다. (d개의 원소로 구성)

- kd tree 에서 노드 안에는 '특징 벡터'가 들어간다. 루트 노드에는 n개의 특징벡터를 구성하는 X 집합 값 중 중간값이 들어가고, 왼쪽, 오른쪾 서브트리에는 이 X가 반으로 쪼개진 벡터들이 들어간다.

 

1. 집합 X 를 쪼개기 위해, 우선 d차원 원소 중에 몇 번째 위치를 기준 축으로 할 지 결정한다.

이때, 분할의 효율을 높이기 위해, 각 축에 대해 분산을 구하고, 제일 큰 분산이 나오는 위치를 기준 축으로 정한다

 

2. 해당 축을 기준으로 특징벡터들을 정렬한 뒤, 중간 값을 현재 트리의 root 노드로 둔다.

그리고 해당 중간값을 갖는 벡터를 기준으로 왼쪽, 오른쪾을 나눠 서브트리에 넣어두고 각각의 서브트리에 대해 이를 반복한다.

 

Example

 

 

다음과 같은 특징벡터 집합으로 kd tree를 구축해보자.

각 벡터의 원소 개수가 2개이므로, 차원은 2이다.

 

1. 먼저 전체 x에 대해 x1 축에 대해 분산을 구하고, x2 축에 대해 분산을 구해보자.

대충 나열해보면 x1은 (3, 2, 6, 4, ..., 6), x2는 (1, 3, 2, ..., 11) 이 나오는데, 굳이 계산해보지 않아도 x2 축이 더 큰 분산을 갖는 축이라는 것을 알 수 있다.

따라서 축 k 는 2가 된다. (두번째 축의 분산이 크다)

 

이 축을 기준으로 x를 정렬하면, 가운데 값은 (3, 6) 이 되고, 이를 뺀 나머지들 집합에서 위 과정을 반복한다.

그러면 아래와 같은 트리가 그려진다.

 

 

그림에서 빨간색이 x2 축이고, 파란색이 x1 축이다.

 

그래프에 축을 표시하면 위와 같다.

 

이제, kd트리와 이 그림으로부터 제일 가까운 이웃을 찾아보자.

어떤 새로운 점 x (7, 5.5) 의 제일 가까운 이웃을 찾아보자.

이 x 는 다음 그림에 보이는 영역에 속해있다.

 

먼저 kd tree 의 루트와 비교해보면, 위 점은 두번째 원소를 축으로 했을 때 더 작은 영역에 속하므로, 그림의 회색 영역에 존재한다.

 

이 영역에서는 (4,4)가 기준점이 되므로 다시 이 점과 비교하면 오른쪽으로 가면서 (6,2)가 기준이 되는 영역으로 들어온다.

 

그렇게 영역을 자르고 자르면 위와 같이 회색 영역이 만들어지며, 이 영역에서 제일 가까운 점은 (8,5) 이다.

 

 

 

그 과정을 나타낸 그림이다.

 

그런데 과연 (8,5)를 가장 가까운 이웃이라고 단정지을 수 있을까?

위 그림에서 x를 주위로 원을 그렸을 때 회색 영역 밖에 있지만 (8,5)와 같은 거리에 있는 점이 하나 더 있다.

즉, 주어진 영역 밖에 사실 더 가까운 점이 있을 수 있다!

이를 위해, 지나온 노드들을 모두 스택에 저장하고, 백트래킹을 사용해서 다른 영역에서 이웃들도 찾아볼 수 잇다.

즉, 일단 거리가 제일 가까운 노트부터 보는 것이 더 효율적이라는 것을 알 수 있다.

이렇게 추상적인 가장 가까운 이웃을 찾는 방법을 best-bin-first search 라고도 한다.

추가적으로 이 알고리즘은 탐색 횟수 제한을 걸기 위해 try_allowed 를 사용하며, 그밖에도 다양한 변형 알고리즘이 있다.

만약 '제일 가까운 이웃'을 정말 찾고싶다면 추상적인 알고리즘보다, 가장 가까운 이웃을 찾는 알고리즘을 사용하는 것이 좋다.

만약 이웃을 찾는 속도가 중요하다면, GPU를 사용해 병렬연산하여 빠르게 구할 수도 있다.

 

 

---

Locality-Sensitive Hashing

해시는 메모리를 많이 쓰는 대신, 연산 속도를 증가시키는 장점을 갖는다.

만약 적절한 해시 함수와 충돌 해결 함수를 사용하면, Θ(1) 시간에 데이터 추가, 삭제, 탐색이 가능하다.

 

매칭 문제로 돌아와서, 컴퓨터 비전에서 사용하는 해시 key는 숫자가 아니라 여러 실수로 구성된 벡터이다.

해시 키로 들어온 벡터로부터, 다른 이미지에서 제일 가깝거나, 제일 가까운 것으로 추측되는 특징벡터를 value로 얻어낼 수 있어야 한다.

 

따라서 기존의 해시와 다르게 유일한 값이 아니기 때문에, 해시의 결과로 나온 벡터들이 넓게 퍼져있는 것이 아니라, 특정 점에 가까운 벡터들은 더 많이 해시 테이블에 저장되고, 멀리 떨어진 벡터는 해시 테이블에 적게 저장된다.

 

해시 기반의 매칭 알고리즘 중에 제일 유명한 것이 'Locality-Sensitive Hashing' 이다. (위치 의존 해싱)

기존 해시가 모든 데이터를 균등하게 넓게 퍼트리는 것이 목표였다면, 이 해싱은 가까운 벡터를 같은 해시 테이블 컨테이너에 저장하는 것을 목표로 한다.

 

위치 의존 해싱은 하나의 해시 함수만 사용하지 않고, 여러 해시 함수들을 사용하는데, 이 해시 함수들의 집합을 H라고 해보자.

어떤 특징벡터에 매칭되는 특징벡터를 찾는 해시 함수 h를 찾는 조건은 아래와 같다.

 

p() 는 확률을 의미하고, || a - b || 는 두 특징벡터 사이의 유클라드 거리를 의미한다.

둘 사이의 거리가 R 이하이면, p1 이라는 어떤 확률보다 높은 확률을 갖고,

둘 사이의 거리가 cR 이상이면, p2 라는 어떤 확률보다는 작은 확률을 갖는다.

 

식보다는 예시를 보면 이해가 쉽다.

위 그림에서 두 특징벡터 a, b1 또는 a, b2 사이의 거리가 R 이하 일 때, 특징벡터 a, b1, b2는 모두 같은 해시함수를 갖는다.

 반면 a, b4 는 서로 다른 해시함수를 갖는다. 둘 사이의 거리가 cR보다 멀기 때문이다.

 

이제, 위 식을 만족하는 해시함수 집합을 만드는 방법을 생각해보자.

 

위 식을 만족하는 여러 해시함수가 제안되었지만, 위 함수를 한번 생각해보자.

x는 입력으로 주어지는 특징 벡터이고, b는 (0, w) 사이에서 랜덤으로 선택된 실수이다.

이때, r은 d차원 벡터로, 이 벡터의 원소값들은 가우시안 분포에 따라 무작위로 선택된 값들이다.

 

Example 1

2차원 특징벡터 x를 생각하자.

 

w의 값은 2이고, 랜덤하게 생성된 r = (1, 2), b = 0.6 이라고 해보자.

그러면 이 결과로 만들어진 해시함수는 다음과 같다.

 

이제 x1, x2 값에 따라 h(x) 값이 어떻게 생성되는지를 그래프로 나타내면 다음과 같이 나타난다.

 

x1 = 1.4, x2 = 0을 대입해보면, h(x)의 값은 1이 된다.

x1 = 0, x2 = 0.7을 대입해보면, h(x)의 값은 1이된다.

이 둘을 연결한 선이 h(x)의 값이 1이되는 경계점이다. 이보다 작은 영역에 있으면 h(x)의 값이 항상 0이 나온다.

(즉, 그림에서 0, 1, 2, ...로 숫자를 매긴 것이, h(x)의 값이 그 값이 나오는 x1, x2 범위를 표시한 것이다.)

 

이제 이 상태에서, 그림에 보이는 것처럼, x1, x2, x3, x4 라는 특징점을 배치했다.

이 각각의 점에서의 해시값을 계산하면 (위 그림에 나타나있듯) 다음과 같이 나온다.

 

이때 3이라는 같은 해시값을 갖는 h(2.5, 2) 와 h(0.8, 3) 은 매칭될 것이고, 4라는 같은 값을 갖는 두 특징벡터는 매칭될 것이다.

 

Example 2

이번에는 해시함수를 2개 사용하는 예제를 보자.

첫 번째 해시함수 h1 은 위 예제에서 본 함수를 사용하고, 두 번째 해시함수 h2 는 r = (1.8, 0), b = 0 의 값을 갖는다.

이때 x1, x2, x3, x4 를 h1, h2 에 대입한 값으로 (h1(x), h2(x)) 좌표쌍을 만들면

 

다음과 같이 나온다.

[3, 1] 이라고 되어있는 부분은 h1 을 사용했을 땐 3 이라는 값이 나온 것이고, h2를 사용했을 땐 1 이라는 값이 나온 것이다.

이제 이렇게 2개 해시를 사용했을 때 매칭하려면, 모든 h 값들의 조합이 같으면 될 것이다.

위 그림에서 [4, 1] 이라는 같은 해시값 쌍을 갖는 두 특징벡터는 매칭될 것이다.

 

예제의 해시함수는 2차원 평면을 선으로 나누었지만, 3D 공간에서는 평면으로 공간을 나눈다.

이때 매개변수 w는 공간과 공간 사이 간격을 가리킨다.

만약 w가 작으면, 공간은 더 작은 공간으로 나뉘고, 만약 w가 커지면, 공간은 더 큰 공간으로 나뉘어진다.

 

가까운 특징벡터는 같은 해시 공간에 있을 가능성이 높지만, 만약 두 특징벡터가 해시 공간 경계 근처에 있다면 가까움에도 다른 해시 공간에 있다고 인식될 수 있다.

이 문제를 해결하는 간단한 방법은 해시 함수를 더 많이 사용하는 것이다.

그러면 두 특징벡터가 다른 해시 테이블에서는 같은 컨테이너에 포함될 확률이 올라간다.

 

Geometrical alignment

지금까지 살펴본 매칭 알고리즘은 두 개의 서로 다른 이미지에서 지역적으로 (위치적으로) 가까운 특징을 찾기 위해서만 사용되었다. 매칭되는 쌍이 여러 개 있을 때, 이 매칭 쌍들의 기하학적 변환은 거의 동일하게 유지되어야 하지만, local information 만을 사용하는 매칭 알고리즘은 기하학적 변환에서 오류가 발생하기 쉽다.

 

그래서 기하학적 변환이 그대로 유지되는 (noise, occlusion, clutters 에 영향을 잘 받지 않는), 기하학적으로 정렬된 알고리즘을 살펴보려고 한다.

 

즉, 특징점들을 잘 매칭했으니, 이제 그 매칭된 결과물을 보고, 어떤 변환행렬 (homography) 를 사용해야 그렇게 변환되는지 찾는 과정을 거친다.

 

Least Squares Method

최소제곱법은 컴퓨터 비전이 등장하기 훨씬 전부터 통계학자, 수학자들이 연구했던 방법이며, 지금도 다양한 응용 분야에 널리 사용된다. (수치해석에도 사용되는 듯하다..)

 

두 직선 l1, l2 중에, 어떤 직선이 x1, x2, x3, x4를 모두 잘 표현하고 있을까?

직관적으로 l1 이 잘 표현하고 있다.

x1, x2, x3, x4 4개 점에서 l1 으로 수선을 내렸을 때, 각각의 수선의 발을 y1, y2, y3, y4 라고 하자.

 

수학적으로 4개의 점을 잘 표현하는 직선은, || xi - yi || ^ 2 의 합이 최소가 되도록 하는 직선일 것이다.

그런 직선식 y = ax + b 의 a, b를 결정하는 것이 중요해진다.

 

이제 이 내용을 컴퓨터 비전에 응용해보자.

컴퓨터 비전에서 주어지는 데이터는 '점' 이 아니라, 매칭된 페어쌍이다.

이 페어쌍들의 집합을 X라고 하면 다음과 같이 나타난다.

 

 

이 경우, 어떤 직선 모델을 사용해야 할까?

만약 매칭된 벡터 페어쌍들이 같은 object 에서 발견된다면, 이 페어쌍들은 모두 동일한 H 라는 homography 결과로 변환되었을 것이다.

즉, b1 = H a1, b2 = H a2, .... 인 것이다.

 

이때 H를 다음과 같이 나타낼 수 있다. (affine transformation)

 

이 homography는 a라는 특징벡터를 b' 으로 변환시킬것이다.

이 변환결과는 실제 b 와 다를 수 있다.

이제 우리의 목표는 b' 과 b 사이의 오차를 최소화하는 homography를 찾는 것이다.

즉, 위 H 에서 6개 원소 값을 결정해야 한다.

 

 

다음과 같이 H homography를 사용함에 따른 bi, b'i 사이의 최소제곱법 결과를 E(H)라고 하자.

이때 이 함수를 H의 6개 원소 각각에 대해 부분적으로 E(H)를 미분하고, 그 각각의 값을 0으로 두면 아래와 같은 6개의 방정식을 얻는다.

 

 

그리고 이 등식을 정리하면 아래와 같은 행렬식을 얻을 수 있다.

 

 

이때 일치하는 쌍이 많을 수록, H를 더 정확하게 얻을 수 있다.

 

위치 오차가 가우시안 분포 범위에 있는 경우에는 최소제곱법으로 H를 잘 구할 수 있다.

그러나 그 분포를 벗어나는 매칭쌍이 존재하면, H가 왜곡될 수 있다.

 

위 그림처럼 x5 라는 동떨어진 점이 나오는 경우, l1 이라는 직선을 제대로 구하는데 방해가 될 것이다.

 

RANSAC

그래서 이 문제를 피하기 위해 RANSAC (RANdom SAmple Consensus) 방식을 사용하기도 한다.

이 알고리즘의 원리는 다음과 같다.

 

어떤 입력샘플 집합에서 임의로 2개의 점을 고른다.

(그림에서 (b)에 보이는 2개 빨간색 점이 임의로 선택된 2개 점이다.)

이 두 점으로부터 직선식을 하나 구하고, 나머지 특징벡터들이 이 직선식의 경향을 따르는지 확인한다.

만약, 이 테스트를 통과하면, 그 특징벡터들을 inliner 집합에 넣고, 전체 테스트가 끝났을 때, inliner 집합의 크기가 어떤 특정한 수자 d보다 크다면, 집합 내에 있는 점들에 대해 다시 직선식을 계산한다.

만약 이 직선식의 정확도가 특정 조건을 만족하면, 이 직선을 line group에 넣는다.

 

이 과정을 반복하고, 제일 정확도가 높은 직선을 선택한다.

 

그러면 이렇게 여러개의 직선들을 구할 수 있다.

 

ORB

SIFT 알고리즘이 발표된 이후, SIFT 기반의 새로운 알고리즘들이 여럿 제안됐다.

예를 들면 SURF 알고리즘은 DoG 피라미드를 이진 필터링된 이미지로 교체해서 속도를 개선한 알고리즘이다.

KAZE 알고리즘은 2012년에 제안되었으며, 가우시안 함수 대신 non-linear diffusion filter를 사용하여 nonlinear scale space를 생성하고, 이를 기반으로 특징점을 추출한다.

KAZE 알고리즘은 물체의 윤곽선을 잘 보존하고, 흐림, 노이즈, 크기변환, 회전된 이미지에 대해서도 잘 작동한다.

 

하지만 SIFT, SURF, KAZE 와 같은 알고리즘은 실시간 특징 추출을 사용하는데는 적합하지 않다.

scale-space를 만드는 것과 같이 복잡한 연산을 필요로 하기 때문이다.

 

이런 SIFT 기반의, 크기에 상관없이 일정한 특징 추출 알고리즘의 문제를 극복하기 위해, binary descriptor 를 사용한 새로운 알고리즘을 고안했다.

ORB는 그 중 하나이며, SIFT, SURF 와 같은 알고리즘을 충분히 대체할 만큼 좋은 성능을 보인다.

 

ORB는 FAST 특징점 추출 알고리즘을 사용한다.

하지만 FAST 알고리즘은 이미지의 크기 변화에 약하기 때문에 이미지 크기를 점점 줄이는 image pyramid를 만들고, 각 특징점에서의 지배적인 방향을 계산해 binary descriptor를 생성한다.

이때 BRIEF (Binary Robust Independent Elementary Features) 를 사용한다.

 

BRIEF 알고리즘은 입력 특징점 주변에 미리 정의된 픽셀 위치가 주어지는데, 이 픽셀의 강도 (밝기) 를 비교하여 특징을 찾는다.

 

두 픽셀 x, y 의 비교 테스트를 위해

 

다음과 같은 함수를 사용한다.

 

예를 들어, p 라는 특징점 주위에 a, b, c 라는 미리 정의된 픽셀이 있고,

이들에 대해 위 테스트 함수를 적용하면 110 이라는 이진수를 얻을 수 있다.

이 값은 a, b, c 사이의 연관된 밝기를 의미한다.

 

ORB는 FAST 알고리즘을 사용하여 특징점을 추출한다.

그리고, 픽셀의 밝기 분포를 고려하여 특징점의 방향 성분을 계산한다.

방향성분을 사용하여 BRIEF 에 대한 점의 위치를 조정하여, 회전에도 변하지 않는 불변 BRIEF discriptor를 계산한다.

ORB 알고리즘은 256-bit binary-discriptor를 만들기 위해, 256개의 비교쌍을 사용한다.

 

이때, 두 binary-discriptor 사이의 거리는 해밍 거리로 계산된다.

해밍 거리는 두 개의 binary-input discriptor에 대해 다른 비트를 반환한다.

 

(사실 ORB 내용은 무슨 말인지 모르겠다...)