[cite]10.1.1.175.2122[/cite]

1 Introduction

컴퓨터비전에서의 특징 기술자(feature descriptor)는 많은 영역에서 핵심적인 역할을 합니다. 많은 데이터를 제한적인 자원에서도 처리하기를 위해서는 이러한 기술자의 계산과 매칭 작업을 빠르게 계산하여야 하고 메모리 또한 효율적으로 사용해야 합니다. 이를 위한 방법으로 PCA나 LDA 등을 활용한 차원 축소를 하는 방법이 있습니다. 또한 실수 값들을 적은 수의 비트를 갖도록 양자화(quantization)하는 방법도 있습니다. 하지만 기존의 방법들은 먼저 전체 기술자를 계산하고 후에 처리하는 방식을 이용하기 때문에 비효율적입니다. 이 논문은 그것을 개선하여 이미지 패치에서 곧바로 이진 기술자(binary string)을 생성 BRIEF를 소개하고자 합니다.

이것은 256개 혹은 128개의 비트만 사용해도 좋은 결과를 얻을 수 있었으며, 매칭 과정에서 비교는 XOR 연산을 통한 해밍 거리(Hamming distance)를 사용할 수 있어 SSE 등의 확장 명령어에서 더욱 빠른 성능을 보입니다.

2 Related Work

SIFT는 128이라는 높은 차원의 벡터를 가지고 잇어 그 계산과 매칭 작업이 느립니다. 이것은 많은 수의 기술자를 다루는 SLAM과 같은 환경에서는 특히 단점으로 작용합니다. 이를 개선하기 위해 SURF 같은 개선된기술자들이 생겨났으나 SURF는 여전히 64개의 float 변수를 가져 256바이트의 큰 용량을 차지하는 단점이 남아있습니다. 이를 해결하기 위한 방법으로는 Principal Component Analysis (PCA)나 Linear Discriminant Embedding (LDE)같은 차원 축소 방법을 생각할 수 있고, 다른 방법으로는 기술자 자체를 더 작은 비트를 차지하도록 양자화하는 방법을 생각해볼 수 잇습니다. 좀더 극단적인 방법으로 기술자 자체를 이진화(binarize)해버리는 방법도 있습니다. 이진화된 벡터는 메모리 공간을 적게 차지할 뿐만 아니라 매칭단계에서도 XOR 연산을 이용하여 빠르게 해밍 거리를 계산할 수 있다는 장점이 있습니다. Loncality Sensitive Hashing (LSH)나 GIST 기술자 등의 방법들이 이에 해당되고 둘다 좋은 성능을 보여주지만 여전히 기술자를 먼저 계산한 다음에 이진화를 거치는 과정을 이용하고 있기 때문에 비효율적입니다. 따라서 여기에서는 곧바로 이진 기술자를 계산함으로써 이러한 단점을 해결하고자 합니다.

3 Method

이 방법은 기본적으로 이미지 패치를 설정하고 그 내부에서 가능한 픽셀 쌍 중, 일부 적은 수의 쌍의 픽셀 값 비교하는 것만으로도 패치를 분류할 수 있다는 가정에서 출발합니다. 이 가정은 randomized classification tress나 Naive Bayesian classifier등을 이용한 기존의 연구가 있으므로, 검증은 건너뛰도록 하고 어떻게 기술자를 만들 것인지에만 집중하고자 합니다.

먼저 기술자에서 패치 $p$내의 두 픽셀을 비교하는 테스트 함수는 아래와 같습니다.

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

여기서 $p(x)$는 패치 내 $x=(u, v)^T$ 위치의 픽셀 값을 의미합니다. 여기서 패치는 이미지를 스무딩한(smoothed) 이미지입니다. 패치는 $S \times S$를 갖습니다. 패치 내의 두 위치 $(x, y)$쌍을 겹치지 않도록 $n_d$개를 골라서 다음과 같이 구성하면 $n_d$의 비트 길이를 갖는 BRIEF 기술자를 계산할 수 있습니다.

$$f_{n_d}(p) := \sum_{1 \leq i \leq n_d} 2^{i-1} \tau(p;x_i,y_i)$$

사용되는 비트 수로 $n_d = 128, 256, 512$를 비교해보았으나 좋은 성능을 보여주었습니다. 사용된 비트 수에 따라 $k=n_d / 8 $로 계산하여 각 버전을 BRIEF-k 로 표시하도록 합니다.

이제 기술자를 만들 때에 고려해야할 것은 두가지로 스무딩에 사용될 커널과 $(x, y)$ 쌍을 어떻게 나열할 것인지를 결정하여야 합니다.

3.1 Smoothing Kernels

위에서 살펴본 테스트 식을 보면 픽셀 단위로 계산이 진행되기 때문에 노이즈에 매우 민감할 수밖에 없습니다. 따라서 사전에 패치를 스무딩하는 것으로 안정성(stability)와 반복성(repeatability)를 강화시키고자 합니다. 가우시안 커널의 분산을 0 ~ 3 까지 변화시켜보았지만 크게 성능 차이가 없었기에 실험에서는 2로 사용하였고, 커널의 크기는 9 * 9를 사용하였습니다.

3.2 Spatial Arrangement of the Binary Tests

S * S 크기의 패치 내에서 $(x,y)$쌍을 어떻게 선택하느냐에 따라 $n_d$개의 비트 벡터가 달라집니다. 여기서는 5개의 방식으로 실험을 해보았습니다.

1. $(X, Y) \sim \text{i.i.d. Uniform}(-\frac{S}{2}, \frac{S}{2}) $
2. $(X, Y) \sim \text{i.i.d. Gaussian}(0, \frac{S^2}{25}) $
3. $X \sim \text{i.i.d. Gaussian}(0, \frac{S^2}{25}), Y \sim \text{i.i.d. Gaussian}(x, \frac{S^2}{100}) $
4. $(x_i, y_i)$ 극 좌표계(polar grid)에서 랜덤 샘플링되어 x-y 좌표계로 양자화된 좌표
5. $x_i= (0, 0)^T$이고 $y_i$는 극좌표계에서 가능한 모든 좌표

실험 결과 5번 방법에 제일 좋지 않았고, 2번째 방법이 나머지 3개 중에 근소하게 좋은 결과를 보였기 떄문에 이를 사용하도록 하였습니다.

3.3 Distance Dsitributions

여기서는 두 기술자의 해밍 거리에 대한 분포를 살펴보고자 합니다. 이를 위해 5개의 이미지 쌍에서 4000개의 매칭 포인트를 추출하엿습니다. 그리고 이들 매칭 쌍 중에서 서로 관련있는 쌍과 관련이 없는 쌍을 구분하여 히스토그램으로 나타내었습니다. 256 비트를 사용하였기 때문에 해밍 거리가 가질 수 있는 최대 값은 256일 것입니다. 서로 관련 없는 쌍의 경우 128을 중심으로 하는 가우시안 형태의 분포를 가졌습니다. 또한 서로 관련 있는 쌍의 경우에는 그보다 더 작은 값을 중심으로 분포되어있었습니다. 따라서 해밍 거리를 이용한 분류기를 만든다면 이 두 분포가 서로 가장 멀리 떨어진 것을 선택하여야 할 것입니다.

4 Results

결과는 OpenCV에서 구현된 SURF 기술자를 속도의 기준의 삼았습니다. SURF64를 사용하였으며, BRIEF는 회전에 영향을 받기 때문에 회전 불변 성질을 뺀 U-SURF를 사용하였습니다. 성능은 4가지 측면을 고려하였습니다.

• 시점 변화
• 압축에 대한 아티팩트
• 조명 변화
• 이미지 블러

이들 측면으로부터 평가는 CPU시간과 인식률에 대하여 평가하였습니다.

5 Conclusion

이미지 패치내의 일부 픽셀 쌍의 값 비교만으로 생성되는 BRIEF는 이진 값을 가져 속도가 빠를 뿐 아니라, 회전이 존재하지 않는한 성능 또한 높았습니다. 이것은 제한된 계산 성능을 가진 환경에서 중요한 부분일 것입니다.