논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

Evaluation of Local Detectors and Descriptors for Fast Feature Matching

10월 29th, 2015 Posted by 룬룬

[cite]10.1.1.301.6783[/cite]

1 Introduction

컴퓨터 비전 분야에서 영향력이 큰 것을 꼽자면 그중 하나는 아마도 SIFT일 것입니다. 이는 많은 분야에서 활용되고 있지만 아무래도 큰 계산 복잡도로 인하여 SLAM과 같은 시간적인 제약이 있는 분야에서는 사용하기가 적합하지 않습니다. 때문에 SIFT를 대체하고자 하는 많은 연구가 있었으나, 이들의 정량적인 비교의 연구는 없었습니다. 여기에서는 동일한 데이터에 대한 평가 방법을 제시하고, 속도 및 매칭 정확도를 기준으로 그 결과를 알아보고자 합니다.

Detectors and descriptors

아래 디스크립터들에 대하여 테스트를 하였습니다.

  • SIFT
  • SURF
  • MSER
  • FAST
  • ORB
  • FAST
  • BRISK
  • MRRID
  • MROGH
  • LIOP
  • BRIEF

Efficient data structures

많은 연구들이 매칭의 효율성을 위하여 nearest neighbour (NN)을 사용하였습니다. 널리 사용된 알고리즘은 kd-trees와 hashing method입니다. 또한 높은 차원에서의 NN 탐색을 위한 e-approximate nearest neighbour (e-ANN) 탐색도 있습니다.

2 Evaluation framework

[12]의 연구와 마찬가지로 이미지가 주어지고 그것의 올바른 매칭과 잘못된 매칭 수를 토대로 평가하였습니다. 하지만 매칭 성능을 평가하기 위하여 다른 이미지로부터 생성된 피쳐들을 같이 섞어서 사용하였습니다.

Repeatability score

올바르게 대응 점을 찾는지 평가하였습니다. Repeatability score는 $ S_A = A^+ / A^* $로 계산하였습니다. $A^+$는 대응쌍의 수, $A^*$는 검출된 모든 피처의 수입니다. $A^+$는 호모그래피에 의해 프로젝션된 피쳐가 50% 이상 겹쳐졌을 경우만을 사용하였습니다.

Precision-recall

$ S_B = B^* / B $로 계산하였습니다 이는 곧, 올바른 매칭 $B^*$와 데이터베이스에서 찾은 NN피쳐 $B$로 계산됩니다. $B$는 쿼리한 피쳐 $F_q$와 거리가 NN이내인 데이터베이스의 피쳐 $F_d$입니다.

Recall $S_{BA} = B^* / A^+ $로 계산합니다.

Speed-up

속도 향상은 $S_T = T_S / T_E $로 계산합니다. $ T_S$는 순서대로 탐색했을 경우, $T_E$는 다른 효과적인 방법을 사용했을 때의 시간으로 둘간의 비를 사용합니다.

Dataset

실험은 [12]에서 사용된 8장의 이미지로 구성된 Graffiti sequences를 사용하였습니다. 이것은 다른 위치에서, 회전, 크기 변화, 시점 변화, 이미지 블러, 압축, 조명 변화 등을 포함합니다. 각 이미지들은 6개의 이미지와 ground truth 호모그래피로 이루어져 있습니다. 또한 매칭에 관계없는 피쳐들을 만들기 위해서 Pscal VOC의 1000개 이미지에서 피쳐를 추출하였습니다.

Implementation details

BRISK, LIOP, MROGH, MRRID를 제외한 나머지는 OpenCV를 사용하엿습니다. 제외던 것들은 최근 나온 디스크립터들로 저자의 바이너리를 사용하였습니다. kd-tree는 ANN과 FLANN을 사용하였습니다.

3. Experimental results

3.1 Feature extraction comparison

키포인트의 추출 시간과 그 양을 평가할 것입니다. 모든 결과는 Graffiti와 Pascal VOC데이터셋의 100개 이미지 들에서 처리된 것입니다.

가장 많은 키포인트가 추출된 것은 multiscale FAST 디텍터고 가장 적은 것은 MSER입니다. 가장 효율적인 추출기는 FAST로 SURF보다 88배, DoG보다 169배 빨랐습니다. 평균 이미지당 2ms가 걸린 셈입니다.

가장 빠른 디스크립터는 BRIEF, 다음으로 ORB, BRISK가 뒤를 이었습니다. 단순 테스트에서 SURF, SIFT대비 31배ㅣ 118배의 수준입니다.

정확도는 FAST가 제일 좋았습니다.

3.2 Efficient mathcing

매칭의 질과 속도 향상을 평가할 차례입니다. 실수 피쳐의 빠른 매칭을 위해서는 보통 multiple randomized kd-tree를 사용합니다. 키포인트는 SURF를 이용해서 추출하였고, N개의 디스크립터를 랜덤 샘플링하여 kd-tree를 생성하였습니다. 매칭은 모든 트리에 대해서 동시에 이루어졌습니다. kd-tree의 주된 약점은 NN approximation에 사용되는 파라미터 e와 속도 사이의 트레이드 오프가 있다는 것입니다.

결과적으로 순위가 역전되거나 하는 일은 없었습니다. 정확도는 순차 탐색에 비해서 2.5% 정도 떨어졌습니다. recall의 경우는 N=160에서 손실이 4% 정도, 하지만 속도는 14890배 빨랐습니다. N=20에서는 ㅗㄴ실이 5%, 속도는 1719배 빨랐습니다.

3.3 Comparison of descriptors

디스크립터의 성능을 비교해보고자 합니다. 실수 피쳐는 multiple randomized kd-tree 환경에서, 바이너리 디스크립터는 Hamming distance기반에서 수행하였습니다. 모든 결과는 40개의 트리에서 e =3 환경에서 수행되었습니다.

가장 빠른 매칭은 BRIEF와 ORB였습니다. 바이너리 디스크립터의 매칭은 kd-tree를 이용한 SURF만큼 빨랐으며 SIFT에는 5.6배 빨랐습니다. e에 따라 오히려 SIFT가 빨라진다는 이야기를 할 수도 있겠으나 그런 경우 오히려 정확도가 떨어지기 때문에 고려하지 않았습니다. 높은 차원의 디스크립터의 경우 kd-tree를 생성하는데 많은 비용이 들 것입니다.

매칭 성능은, SURF와 SIFT보다 모두 성능이 좋았으며 LIOP, MROGH, MRRID가 더 나은 결과를 보여주었습니다. LIOP는 MROGH보다 4.4배 빨랐고 MRRID보다 2.1배 빨랐습니다. ORB는 BRIEF보다 성능이 좋았으나 in-plane rotation만 고려하기 때문에 그렇다고 할 수 있습니다. repeatability score는 FAST가 높았습니다.

Add a Comment Trackback