지역 특징 3 - 매칭

매칭은 컴퓨터 비전이 풀어야 하는 물체 인식, 물체 추적, 스테레오, 카메라 캘리브레이션 등의 다양한 문제에서 핵심 역할을 한다. 

---

 

 

 

1. 매칭 전략

매칭 문제는 가장 유사한 특징점을 찾아 쌍을 맺어주면 되니 얼핏 쉽다고 생각할 수 있다. 하지만 프로그램 5-2의 실행 결과에서 확인했듯이 특징점이 상당히 많고 잡음이 섞인 기술자가 적지 않아 꽤 까다로운 문제다. 방법을 고안하기 전에 문제를 정확히 이해하는 일이 먼저다.

 

문제의 이해

 

---

 

 

 

매칭 전략

 

---

 

 

 

 

2. 매칭 성능 측정

성능을 정량적으로 측정하는 일은 컴퓨터 비전에서 아주 중요하다. 정량적 성능은 알고리즘을 개선하거나 최선의 알고리즘을 선택하기 위한 기준이며 시스템을 현장에 투입할지 결정할 때 꼭 필요하다.

 

 

정밀도와 재현율

그림 5-14는 색깔로 정답을 표시하는데, 같은 색은 진짜 매칭 쌍이고 다른 색은 진짜 매칭 쌍이 아니다. 매칭 알고리즘의 예측에 따라 네 가지 경우가 있다.

 

 

 

식 (5.16)의 정확률은 옳게 예측한 비율이다. 특징점 매칭에서는 부정이 긍정보다 월등히 많아 정확률이 의미가 없는 상황이 많다. 예를 들어 물체 인식의 경우 물체만 있는 모델 영상에서 추출한 특징점은 대부분 긍정이지만 물체와 배경이 섞인 장면 영상에서 추출한 특징점 대부분은 부정이다. 이 경우 매칭 알고리즘이 매칭 쌍을 전혀 출력하지 않아도 정확률이 100% 가깝게 된다. 

---

 

 

 

ROC 곡선과 AUC

---

 

 

 

 

3. 빠른 매칭

앞 절에서 매칭이 얼마나 정확한지 측정하였는데 컴퓨터 비전에서는 속도라는 또 다른 중요한 성능 지표가 있다. 속도는 실시간 처리가 요구되는 상황에서 양보할 수 없는 강한 조건이다. 대용량 데이터를 빠르게 탐색하는 자료 구조가 많다. 그림 5-16이 예시하는 이진 탐색 트리와 해싱이 대표적이다.

 

---

 

 

 

kd 트리

그림 5-16 a에 있는 이진 탐색 트리의 루트 노드는 12를 가지는데 왼쪽 부분 트리에 있는 노드는 모두 로트보다 작고 오른쪽 부분 트리에 있는 노드는 모두 루트보다 크다. 두 부분 트리가 이 성질을 재귀적으로 만족한다. 질의어를 탐색하는 일은 루트에서 시작하여 루트보다 작으면 왼쪽, 크면 오른쪽으로 이동하는 일을 재귀적으로 반복하여 이루어진다.

이진 탐색 트리는 한 번 비교할 때마다 한 단계씩 내려가므로 최악의 경우에도 트리의 깊이 이하의 비교로 탐색을 마친다. 따라서 아주 빠른 탐색이 가능한 자료 구조다.

 

이진 탐색 트리를 특징점 매칭에 적용하면 빠른 속도를 달성할 수 있는데 특징점 매칭의 독특한 성질 때문에 그대로 적용할 수는 없다. 첫째, 이진 탐색 트리에서는 값 하나를 비교하는데, 특징점 매칭에서는 여러 값으로 구성된 기술자, 즉 특징 벡터를 비교해야 한다.

둘째, 이진 탐색 트리는 정확히 같은 값을 찾는 반면 특징점 매칭에서는 최근접 이웃을 찾아야 한다. 벤트리는 이진 탐색 트리를 특징점 매칭에 적합하게 개조한 kd 트리를 개발했다.

 

 

 

---

 

 

 

위치 의존 해싱

그림 5-16 b는 빠른 탐색을 위한 해싱을 보여준다. 해싱에서는 해시 함수 h가 키 값을 키가 저장될 칸의 번호로 매핑한다. 이 예는 나머지 연산을 해시 함수로 사용하는 아주 단순한 경우다. 예를 들어 키 x가 134라면 h(134) = 134 % 13 = 4이므로 x는 4번 칸에 저장한다.

해싱에서는 해시 함 수를 한 번만 계산하면 키가 들어있는 칸을 찾을 수 있어 매우 빠르게 탐색할 수 있다. 해싱에서는 서로 다른 키가 같은 주소로 매핑되어 충돌이 일어날 수 있다. 

 

해싱을 특징점 매칭에 할용하려면 이진 탐색 트리를 kd 트리로 개조했듯이 상당한 수정이 피요하다. 특징점 매칭에서는 키가 벡터이고 최근접 이웃을 찾아야 하기 때문이다. 또한 해싱에서는 충돌 확률을 최소화하는 전략을 사용하는데, 해싱을 특징점 매칭에 활용하려면 반대로 비슷한 특징 벡터가 같은 칸에 담길 확률을 최대한 높여야 한다. 이런 성질을 만족하는 대표적인 해싱 기법으로 위치 의존 해싱이 있다.

---

 

 

 

빠른 매칭을 보장하는 라이브러리 : FLANN과 FAISS

SIFT를 고안한 로우 교수와 제자인 무자는 앞에서 설명한 kd 트리의 다양한 변형을 소개하고 이들의 성능을 비교 분석한 논문을 발표했다. 또한 이들을 구현한 FLANN 라이브러리를 공개했다. FLANN은 C++로 개발했는데 C, C++, Ruby, 파이썬 인터페이스를 제공한다.

FLANN의 소스 코드는 깃 허브에 있다.

 

FLANN 라이브러리

GitHub - flann-lib/flann: Fast Library for Approximate Nearest Neighbors

 

 

최근 페이스북은 최근접 이웃을 아주 빠르게 찾는 FAISS 라이브러리를 공개했다. C++로 작성하였으며 파이썬 인터페이스를 제공한다. 사용법은 아래를 참고하라.

 

FAISS 라이브러리 사용법

Welcome to Faiss Documentation — Faiss documentation

 

---

 

 

 

 

4. FLANN을 이용한 특징점 매칭

프로그램은 5-3은 프로그램 5-2와 비슷한 과정을 거친다. 단지 MOT 동영상의 70번째 영상과 83번째 영상을 읽어 들이며 70번째 영상의 버스 부분을 오려내 물체의 모델 영상으로 사용하는 점이 다르다. 

 

FLANN 라이브러리를 이용한 SIFT 매칭

 

 

 

 

 

 

실행 결과를 보면 잘못된 매칭, 즉 거짓 긍정도 보이지만 대부분 옳은 매칭, 즉 참 긍정이 많다는 사실을 확인할 수 있아. 출력을 보면 21행 모델 영상에서 231개, 장면 영상에서 4096개의 특징점이 검출되었다. 43행의 출력을 보면 둘을 매칭하는데 불과 0.031초 걸렸다. kd 트리 알고리즘을 구형한 FLANN의 바른 속도를 확인하였다.

 

---

 

 

 

학습을 마치고

이제 한 단원만 더 공부하면 5장의 개념 학습을 마치게 된다. 조금만 더 힘을 내서 새벽 공부를 잘 마무리해볼 것이다. 이번에도 어려운 내용은 책 내용을 스캔해 보았다.

버스를 매칭한 결과를 보니 신기하다.