ORB on efficient alternative to SIFT or SURF
[cite]10.1109/ICCV.2011.6126544[/cite]
1. Introduction
SIFT의 성능은 10년이 넘도록 그 성능이 증명된 알고리즘입니다. 하지만 많은 계산을 요구하기 때문에 실시간 처리가 필요한 시스템이나 핸드폰과 같이 계산 수행 능력이 떨어지는 장치에서는 사용하기 힘든 것이 사실입니다. 이는 SURF와 같은 상대적으로 낮은 계산력을 필요로하는 알고리즘이 나오게끔 하였습니다.
이 논문에서는 효율적인 계산으로 SIFT와 동등한 수준의 매칭 능력을 보이면서도 실시간으로 동작이 가능하고자 합니다. 여기서 보여줄 기술자(descriptor)는 파노라마나 패치 추적, 이미지 매칭 등이 작업에서 SIFT와 같은 수준의 성능을 보이면서도 2자리수 이상의 속도 향상을 보입니다.
이 알고리즘은 FAST keypoint detector와 BRIEF descriptor에 기반하여 만들어졌으며, ORB(Oriented FAST and Rotated BRIEF)라고 부르고자 합니다. 앞의 두 가지 방법들은 모두 적은 계산만으로도 좋은 성능을 낼 수 있는 방법이지만 SIFT에 비교하기에는 몇가지 한계점이 있었습니다. 특히 BRIEF에서의 회전 불변(rotational invariance) 성능이 중요한 단점입니다. 이 알고리즘의 장점은 다음과 같습니다.
- FAST보다 빠르고 정확한 방향성 추가
- Oriented BRIEF 특징의 효율적인 계산
- Oriented BRIEF 특징의 분산과 correlation 분석
- 방향 불변 하에서의 decorrelating BRIEF 특징을 위한 학습 방법
2. Related Work
Keypoints
FAST와 그 변종 알고리즘들은 실시간 시스템에서 키포인트를 찾고자 하는 알고리즘입니다. 하지만 SIFT나 SURF같은 알고리즘들과는 달리 FAST는 방향에 대한 계산이 들어가 있지 않습니다. Rosin은 자신의 연구에서 코너의 방향을 측정하기 위한 다양한 방법들을 분석하였습니다. 그 중 그의 중심점 테크닉(centroid technique)를 이용하고자 합니다. 한 키포인트에 여러 값들을 갖는 SIFT와는 다르게 중심점 테크닉은 하나의 값만을 가집니다.
Descriptor
BRIEF는 스무딩된 이미지 패치 내에서 픽셀간 값 테스트들를 통해 간단하게 기술자를 만들어내는 알고리즘입니다. 그 성능 또한 조명이나, 흐림이나 원근 왜곡을 포함하였을 때에도 SIFT와 동등한 수준이나 in-plane 회전에 대해 매우 민감합니다.
3. oFAST: FAST Keypoint Orientation
3.1 FAST Detector
FAST는 1개의 파라미터를 이용합니다. 중심 픽셀과의 그 주변의 원형으로 링 위치의 픽셀들과의 차이를 구분하기 위한 임계값입니다. 여기에서는 반지름으로 9를 사용하는 FAST-9를 사용하였습니다. FAST는 코너 부분을 찾아내지만은 않기 때문에 에지 부분에서도 큰 반응을 보입니다. 따라서 해리스 코너(Harris corner) 방법을 이용하여 FAST 키 포인트를 정렬하도록 하였습니다. 예를 들어 N개 키포인트를 구하고자 한다면, 낮은 임계값을 이용하여 N개 이상의 충분한 양의 키포인트를 구한 다음, 해리스 방법을 이용하여 정렬을 하고 상위 N개만을 이용하도록 하였습니다.
또한 FAST는 멀티 스케일(multi-scale) 기능 또한 없기 때문에 이미지의 스케일 피라미드를 생성하여 각각의 단계마다 FAST 특징을 생성하였습니다.
3.2 Orientation by Intensity Centroid
이 방법에서는 intensity centroid 방법을 이용하여 코너의 방향성을 판단하고자 합니다. Intensity centroid는 코너의 픽셀 값은 그 중심과 차이가 있고, 그 벡터는 방향성을 만드는데 사용된다는 것입니다. Rosin은 이미지 패치의 모멘트를 다음과 같이 정의하였습니다.
$$m_{pq} = \sum_{x,y} x^p y^q I(x, y)$$
그리고 중심점(centroid)을 찾는데 다음 모멘트가 사용됩니다.
$$C = \big( \frac{m_{10}}{m_{00}}, \frac{m_{01}}{m_{00}} \big)$$
여기서 코너의 중심 부분$O$과의 벡터 $\vec{OC}$를 계산합니다. 그렇다면 패치의 방향성은 다음과 같이 계산할 수 있습니다.
$$\theta = \text{atan2}(m_{01}, m_{10})$$
Rosin은 이러한 방법으로 어두운 코너이거나 밝은 코너인지를 고려하여야 한다고 언급하고 있으나 여기에서는 이것을 무시하기로 합니다. 코너 타입에 거의 무관하게 일정하게 각도가 만들어지기 때문입니다. 이를 더 발전시키기 위하여 모멘트 계산에 사용되는 픽셀들을 사각형이 아닌 반지름 $ r $의 원형 영역으로 사용하도록 하였습니다. $r$은 실험적으로 패치의 크기를 사용하도록 하였습니다. FAST 코너에서는 $|C|$가 0에 가까워짐에 따라 계산 결과가 매우 불안정하나 여기서는 매우 드물게 나타나는 케이스입니다.
이 중심점 방법을 2개의 그래디언트 기반 방법인 BIN과 MAX에 비교하였습니다. 양쪽 모두 X, Y 그래디언트는 스무딩된 이미지에서 계산되었습니다. MAX는 키포인트 패치에서 가장 큰 그래디언트를 선택하도록 하고 BIN은 10도 간격으로 히스토그램을 구성하여 가장 값이 큰 각도를 선택하도록 하였습니다. 노이즈와 in-plane 회전을 더한 데이터셋에 대하여 계산된 방향성의 분산을 살펴본 결과, 중심점 기반의 방법이 가장 일정한 결과를 보여주었습니다.
4. rBRIEF: Rotation-Aware Brief
4.1 Efficient Rotation of the BRIEF Operator
Brief overview of BRIEF
BREIF 기술자는 이미지 패치 내에서의 픽셀 값 비교를 통해 생성된 바이너리의 나열로 구성되어있습니다. 하나의 비교 테스트 $\tau$는 다음과 같이 이루어집니다.
$$\tau(p;x,y) := \begin{cases}
1 &\ p(x) \lt p(y) \\
0 &\ p(x) \geq p(y)
\end{cases}$$
$p(x)$는 위치 $x$에 대한 이미지 $p$의 픽셀 값입니다. 이것을 n개 비교 테스트에 대해서 반복하면 특징을 구할 수 있습니다.
$$f_n(p) := \sum_{1 \leq i \leq n} 2^{i-1} \tau(p;x_i,y_i)$$
패치 내에서 사용할 테스트 쌍에 대해 많은 연구가 이루어졌지만 여기서는 가장 좋은 결과를 나타내었던 패치의 중앙을 중심으로 하는 가우시안 분포에 따르도록 하였습니다. 또한 n은 256을 사용하였습니다.
비교 테스트를 하기 전에 스무딩을 하는 것 또한 중요한데 31 * 31 크기 패치에서 5 * 5 의 크기로 스무딩이 이루어졌습니다.
Steered BRIEF
이제 in-plane 회전에 대해 불변한 BRIEF를 소개하고자 합니다. 기존의 BRIEF는 몇도 정도면 회전하여도 그 매칭 성능이 급격하게 떨어졌습니다. 모든 각도와 원근 변화에 대해서 BRIEF를 만드는 논문도 있었지만 비효율적입니다. 더 효과적인 방법으로 키포인트의 각도에 대하여 BRIEF를 회전 시키는 방법을 생각할 수 있습니다. n개 테스트에 대한 위치를 $(x_i, y_i)$라고 하고 이로부터 이루어지는 행렬을 생각하여 봅시다.
$$S = ( x_1, \dots, x_n \\ y_1, \dots, y_n )$$
이제 이를 우리가 계산한 각도 $\theta$에 대하여 회전행렬을 적용하면 회전된 버전의 $S_\theta$를 구할 수 있습니다.
$$S_\theta = R_\theta S$$
이제 회전된 BRIEF는 다음과 같이 됩니다.
$$g_n(p, \theta) := f_n(p)|(x_i, y_i) \in S_\theta$$
여기서 각도는 12도 각도 간격으로 고정하고 이에 대하여 모든 BRIEF 패턴을 미리 다 계산해두어 계산 속도를 빠르게 하였습니다.
4.2 Variance and Correlation
우리는 특징을 좀더 명확하게 구분하기 위해서 우리가 입력에 대해 높은 분산 값을 갖기를 원합니다. 하지만 BRIEF는 0.5에 가까운 평균과 큰 분산 값을 가집니다. 반면, steered BRIEF를 만들기 위해 그 방향을 틀게 되면, 평균은 이동하여 좀더 넓게 퍼진 패턴을 가지게 됩니다. 즉 키포인트에 대해 방향성을 부여하게 되면 좀더 일관된 분산을 갖게 된다는 것입니다.
입력 외 비교 테스트의 결과 면에서 생각해 본다면, 비교 테스트가 비상관성을 가져야 한다는 것입니다. 이를 분석하기 위하여 PCA를 사용하여 BRIEF와 steered BRIEF를 비교하여보았습니다. 두 특징 모두 초반 10~15개의 콤포넌트에 대부분의 대부분이 특징이 모두 들어가게 되나, 각 상위 콤포넌트들을 비교하여보면 steered BRIEF가 BRIEF에 비해 낮은 분산을 가집니다. 따라서 각 콤포넌트의 상관성이 존재하여 서로 구분성이 떨어진다고 할 수 있습니다. 결과적으로 steered BRIEF는 올바른 매칭과 그렇지 않은 매칭의 분포가 좀더 0에 가까워져 있어 서로 많이 겹쳐 있어 분리성이 떨어져 있습니다.
4.3 Learning Good Binary Features
Steered BRIEF에서 분산이 떨어지는 것을 막고 비교 테스트의 상관성을 줄이기 위하여 비교 테스트의 좋은 패턴을 고르는 학습 방법을 소개합니다. 그 방법은 PCA나 다른 차원 축소 방법을 사용하여 많은 비교 테스트 셋을 계산하고 그들 중 큰 분산 값과 상관성이 떨어지는 256개의 새로운 특징을 골라내는 것입니다. 하지만 새로운 특징은 많은 수의 비교 테스트로 구성되므로 steered BRIEF보다 계산 효율이 떨어지게 됩니다. 따라서 그 대신, 모든 가능한 비교 테스트 중에서 높은 분산을 가지면서 상관성이 최대한 떨어지는 것들을 찾고자 합니다.
방법은 다음과 같습니다. 먼저 30만개의 키포인트를 생성합니다. 또한 31 * 31 패치에서 가능한 비교 테스트 쌍들을 순서대로 정렬해 놓습니다. 각 테스트는 패치 내에서의 5 * 5 크기의 서브 윈도끼리의 쌍으로 이루어집니다. 따라서 패치 크기를 $w_p$, 서브 윈도 크기를 $w_t$라고 한다면 가능한 모든 서브 윈도의 수는 $N = (w_p - w_t)^2 $가 되고, 만들 수 있는 쌍은 $(N \\ 2 ) $가 될 것입니다. 따라서 여기에서는 $M = 205590$의 비교 테스트가 가능해집니다. 알고리즘은 다음과 같습니다.
- 모든 트레이닝 패치에 대해서 테스트를 실행합니다.
- 각 테스트를 평균값인 0.5와의 거리에 따라서 순서대로 정렬하고 이를 벡터 T로 나타냅니다.
- Greedy한 탐색을 실행합니다.
a. T의 첫 테스트를 벡터 R에 넣고 T에서 제거합니다.
b. 다음 테스트를 T에서 빼내어 R의 모든 테스트와 비교합니다. 만약 연관성이 임계값보다 높다면 그것을 버리고 아니면 R에 추가합니다.
c. 이전 과정을 R에 256개의 테스트가 찰 때 까지 반복합니다. 256개가 다 채워지지 않는다면 임계값을 줄이고 다시 테스트합니다.
이러한 과정으로 만들어진 것을 rBRIEF라고 부르고자 합니다. rBRIEF는 steered가 가진 단점을 뛰어넘어 분산을 높이고 비상관성을 줄였습니다. 실험 결과에서도 PCA에서의 아이겐 밸류(eigenvalue)가 높아지고 콤포넌트가 진행되면서 급격하게 떨어지는 것을 볼 수 있었습니다.
4.4 Evaluation
oFAST와 rBRIEF, 여기서는 ORB라고 부르는 두개의 알고리즘을 비교하였습니다. 테스트는 in-plane 회전을 주고 가우시안 노이즈를 준 합성 이미지와 실제 환경에서 찍은 다른 시점에서의 이미지들을 사용하였습니다. 각 이미지들에서는 oFAST와 rBRIEF를 이미지당 500개씩 추출하였습니다.
합성 이미지의 실험 결과, 회전에 대해서는 ORB가 SIFT와 SURF를 넘어서 가장 좋은 결과를 보였습니다. 노이즈에 대해서는 SIFT에 비해 상대적으로 좋은 구간이 있었으나, SIFT에 비해 등락의 폭이 적었습니다.
실제 이미지에서 또한 ORB가 SIFT를 뛰어넘는 결과를 보였습니다.
5. Scalable Matching of Binary Features
SIFT/SURF에서 매칭 쌍을 찾기 위해서 nearest-neighbor를 사용하였습니다. 이미지 내의 많은 데이터 중에서 단순한 NN보다 더 효율적인 알고리즘을 소개합니다.
5.1 Locality Sensitive Hashing for rBRIEF
여기에서는 Locality Sensitive Hashing (LSH) 방법을 사용하였습니다. LSH는 각 점들을 여러 해시테이블에 저장하고, 여러 버켓에 해시시켜둡니다. 기술자가 주어지면 매칭된 버켓을 고른 다음 그 내부에 담긴 항목들을 일일이 모두 비교합니다. 바이너리 특징이기 때문에 해시 함수는 특징 비트들의 일부를 가져와서 사용하였습니다. 즉, 기술자의 특정 자리 비트를 공통으로 가지는 기술자들을 같은 버킷에 넣도록 합니다. 그리고 그 버킷간 거리는 해밍 거리를 사용하면 됩니다.
나아가서 multi-probe LSH를 사용할 수 있습니다. 버킷의 주변 버킷까지 탐색하도록 하여 기존의 LSH의 성능을 끌어올리도록 한 것입니다.
5.2 Correlation and Leveling
만약 rBRIEF가 가지는 비트들이 서로 관련성이 적다면 LSH는 버킷을 효율적으로 나눌 수 있게 되어 효율적이게 됩니다.
5.3 Evaluation
rBRIEF LSH와 kd트리를 사용하는 SIFT를 비교하였습니다.