Ferns를 이용한 영상 Object Detection

영상처리 2013. 8. 8. 12:19

영상 매칭에 사용될 수 있는 local feature 중에 Ferns라는게 있습니다.


Ferns라는 용어는 영어 ferns(고사리)에서 따온 말로 Ferns의 구조가 고사리와 유사하기에 지은 이름입니다.


Ferns는 흔히 알고 있는 SIFT, SURF 등에 비해 훨씬 속도가 빠르면서도 (VGA기준 50 Hz) 매칭 성능 또한 뛰어납니다.


또한 Ferns는 속도와 성능 사이의 trade off를 파라미터로 조절할 수 있으며 object detection 및 tracking에도 사용할 수 있습니다. Tracking에 사용된 대표적인 예는 TLD tracker입니다 ([영상추적#2] TLD - 추적하면서 학습한다 글 참조)


Ferns detector는 오프라인 학습뿐만 아니라 온라인 학습도 가능합니다. 즉, 점진적인(incremental) 학습이 가능합니다. TLD tracker는 ferns를 점진적인 학습 방법으로 활용한 예입니다.


Ferns의 한 가지 단점은 사전에 학습을 위한 시간이 (5분 내외) 많이 걸린다는 점인데, 검출 성능만 좋다면 큰 문제가 아닙니다. 다만 object tracking 등에 활용하기 위해서는 시간을 최소화해야 하기 때문에 초기 성능을 희생하거나 (TLD처럼 이후 tracking 동안 점진적으로 학습을 통해 성능을 향상) 또는 물체의 변화폭을 제한하여 학습 시간을 줄이는 등의 방법을 사용해야 합니다.



1. Ferns 논문 및 링크


- CVPR 2007 논문: M. Ozuysal, P. Fua, V. Lepetit, "Fast Keypoint Recognition in Ten Lines of Code"

- PAMI 2010 논문: M. Ozuysal, M. Calonder, V. Lepetit, P. Fua, "Fast Keypoint Recognition using Random Ferns"

- 웹사이트 (소스코드 다운로드): http://cvlab.epfl.ch/software/ferns/index.php


Ferns는 EPFL Computer Vision Lab.의 Mustafa Ozuysal이 개발한 알고리즘으로 CVPR 2007 학회에서 처음 발표되었으며 이후 PAMI 2010 저널에 실렸습니다.


위 웹사이트에 가면 Ferns의 소스코드를 다운로드 받을 수 있습니다 (GPL 라이센스). 단, Linux C++ 버전이기 때문에 윈도우즈에서 사용하기 위해서는 약간의 포팅 작업이 필요합니다.


아래 동영상은 다운받은 ferns 프로그램을 직접 돌려서 얻은 결과 동영상입니다.




2. Ferns 설명


Ferns는 논문만 봐서는 핵심 내용을 파악하기가 쉽지 않습니다. 원래는 주 개발자(저자)인 M. Ozuysal의 홈페이지에 ferns에 대한 설명이 잘 나와 있었는데, 얼마 전부터 무슨 이유인지 EPFL에서 M. Ozuysal의 홈페이지가 사라지고 없습니다. 


다행히 당시 M. Ozuysal의 홈페이지에 있던 그림들을 백업해 둔게 있어서 그 그림들을 활용하여 설명토록 하겠습니다. 설명은 논문의 수식을 이해하는 것보다는 핵심 내용을 직관적으로 이해하는 방향으로 진행하되 용어는 가급적 원 논문의 용어를 사용하겠습니다.


Ferns 설명에 앞서, 먼저 일반적인 local feature matching 과정을 살펴보면,

  1. 식별이 용이한 특징점(keypoint)들을 선택한다 (ex. Harris corner)
  2. 선택된 특징점 주변의 local patch에서 특징량(feature vector, descriptor)을 추출한다 (ex. SIFT, SURF, BRIEF, ORB)
  3. 물체모델에서 뽑은 특징벡터(feature vector)들과 입력 이미지에서 뽑은 특징벡터들 사이의 매칭을 시도한다. 매칭은 feature vector 사이의 유사도(보통은 유클리디언 거리)를 이용한다.
  4. 매칭된 쌍들 사이의 기하학적 변환 관계를 RANSAC 등을 이용하여 추정하여, 유효한 변환관계가 발견되면 물체를 발견한 것이고 그렇지 않으면 물체를 검출하지 못한 것으로 판단한다.

입니다.


Ferns에서는 위와 같은 local feature matching 문제를 일종의 classification 문제로 간주합니다. 특징점(keypoint)을 뽑는 것 까지는 위와 동일한데 이후 특징량 추출 및 feature matching과정에서 차이가 납니다. Ferns에서는 특징점(keypoint) 하나 하나를 class로 간주하고 , 매칭단계에서 classification을 수행합니다.


예를 들어, 물체모델에서 400개의 특징점(keypoint)들을 뽑았습니다 (특징점 뽑는 방법은 어떤 방법을 사용해도 무방함). 그러면 특징점 각각을 class로 간주하여 C1, C2, ..., C400 까지 총 400개의 class가 존재합니다. 이제 입력 영상이 들어오면 입력 영상에서 특징점들을 뽑습니다. 가령 1000개의 특징점을 뽑았다고 하겠습니다. 그러면 이제 매칭을 위해 1000개의 특징점 각각이 어떤 class에 속하는지 classification을 수행합니다. 이와 같이 1000개의 입력 특징점에 대한 classification이 완료되면 동일 클래스(class)에 속하는 입력 특징점들 중에서 모델 특징점과 가장 유사한 특징점을 하나씩만 선택합니다. 그러면 매칭이 완료되고 이후의 RANSAC 과정은 동일합니다.


<그림 1>


위 그림 1과 같이 뽑인 모델 특징점 하나 하나 마다 local patch를 class로 저장하고 새로운 patch가 들어왔을 때 어떤 class에 속하는 것인지를 판단하는 것입니다. 클래스를 생성할 때에는 local patch를 다양한 방식으로 변형(affine deformation)하여 다수의 학습 데이터를 생성한 후 이들을 이용하여 class를 학습시킵니다.


문제는 각 모델 특징점마다 어떻게 class를 학습시키고 또 입력 특징점에 대해서 어떻게 classification을 수행하느냐입니다.


Ferns에서는 매우 단순한 binary feature만을 이용하여 class를 학습시키고 또 식별합니다. patch 내에 임의의 두 점을 잡고 두 점의 픽셀 밝기차가 +인지 -인지를 feature로 사용합니다. 즉, 하나의 feature는 두 점의 좌표로 구성되며 결과값은 부호에 따라 0 또는 1의 값을 갖습니다.


이러한 binary feature들을 patch 내에 무수히 많이 잡을 수 있는데, 이들을 몇개씩 일정한 크기로 그룹핑(grouping)한게 fern입니다. F를 fern, f를 binary feature라 할 때, Fj = {fj1, fj2, ..., fjS}, j = 1, ..., M와 같은 식입니다. 그런데, 사실은 binary feature들을 먼저 뽑은 후에 이들을 그룹핑하는 것이 아니라, 사전에 fern의 개수 M과 fern의 크기 S를 정해 놓고 이 개수에 맞추어 binary feature들을 patch 내에서 무작위로 랜덤하게 뽑는 것입니다.


<그림 2>


위 그림 2의 첫번째 경우와 같이 하나의 binary feature에 대한 결과는 0 또는 1 즉, 두 가지 결과값이 가능합니다. 그러나, 두번째 경우와 같이 3개의 binary feature로 구성된 하나의 fern에 대한 결과는 000, 001, 010, 011, ..., 111까지 총 8가지 결과값이 가능합니다. 이를 이진수로 생각하면 0부터 7 사이의 값이 가능한 셈입니다. 이를 일반적으로 표현하면 크기 S인 fern의 결과값은 0 ~ 2S-1 사이의 값을 가집니다.


그림 2의 세번째 경우는 class 학습과정을 설명하기 위한 것입니다. 앞서 설명한 바와 같이 하나의 모델 패치에 대해 (이미지에서 물체가 변할 수 있는 다양한 변화를 고려하기 위해) 모델패치를 affine 변환으로 확장하여 이들을 모두 같은 class로 간주합니다. 이와같이 다수의 패치로 구성되는 한 class에 대한 fern의 결과값은 하나의 값으로는 표현이 안되기 때문에 그림과 같이 히스토그램으로 표현합니다.


이 히스토그램의 bin의 개수는 2S개입니다. 한 class에 속하는 각각의 패치마다 한 fern에 대해 0 ~ 2S-1 사이의 결과값을 내는데 이 값들에 대한 히스토그램을 구하는 것입니다. 만일 fern이 여러개인 경우에는 각 class마다 fern의 개수만큼 히스토그램을 구하게 됩니다. 그리고 이렇게 구한 히스토그램들이 나중에 이 class에 속하는 패치를 식별하기 위한 classifier 역할을 수행하게 됩니다.


논문에서는 특징점(keypoint) 개수는 400개, fern의 개수는 30개, fern의 크기는 (즉, 각 fern을 구성하는 binary feature의 개수는) 10개, 하나의 클래스를 학습시키기 위한 (확장시킨) 패치의 개수는 10,000개 정도를 사용하고 있습니다.


아래 그림은 class의 개수가 5개, fern의 개수가 3개, fern의 크기가 3인 경우의 classifier 학습 과정을 예로 든 것입니다. 그림 3에서 맨 윗 그림은 class 1에 대한 학습 데이터가 들어온 경우이고, 중간 그림은 class 4에 대한 학습 데이터가 들어온 경우, 그리고 맨 아래쪽은 최종 학습된 결과 히스토그램들입니다.


<그림 3>



이와 같은 학습 과정이 모두 완료되면, 이후 들어오는 입력 이미지에 대해서는 다음과 같은 과정을 통해 매칭을 수행합니다.


먼저, 입력 영상에서 keypoint를 추출하고, 추출한 각 keypoint들에 대해 local patch를 잡습니다. 이들 각각의 local patch가 어느 class에 속하는지를 판단하기 위해 각 fern에 대한 결과값을 계산합니다. 그리고 이 결과값에 대응하는 히스토그램의 bin 값이 얼마나 큰지를 가지고 class를 식별하는 것입니다. 히스토그램의 bin 값은 일종의 확률값이 되는 것이고, fern이 여러 개일 경우 각 fern의 확률값을 곱하여 최종적으로 가장 큰 확률값을 갖는 class를 선택합니다.


예를 들어, 아래 그림을 보면


<그림 4>


식별하고자 하는 어느 한 입력 패치에 대해, 첫번째 fern F0에 대한 출력 1102 = 6에 대한 히스토그램 bin 값, F1의 출력 0에 대한 히스토그램 bin값, F2에 대한 bin 값을 구해서 이 세 값을 모두 곱했을 때 그 값이 최대인 클래스를 구해보면 C2이기 때문에 이 패치는 C2라고 식별하는 방식입니다.



3. 이론적인 부분 (2013.8.13 추가)


Ferns에 대한 이론적인 설명 부분입니다. 댓글로 문의가 있어서 답변을 겸해서 내용을 추가합니다.


먼저, 수식 표현을 위해 용어 및 기호를 정리하면 다음과 같습니다.

fi: binary feature

N: binary feature의 총 개수 (N = M*S)

Fj: fern (binary feature들의 집합)

M: fern의 개수

S: fern의 크기 (fern을 구성하는 binary feature 개수)

Ck: class


어떤 입력 패치에 대한 각 binary feature에 대한 출력이 f1, f2, ..., fN라 했을 때, 이 패치의 class는 ML(Maximum Likelihood) 원리에 의해 다음과 같이 구할 수 있습니다.


 --- (1)


이 확률을 계산하는 방법은 크게 3가지 형태가 있습니다.



식 (1)을 일반적으로 계산하기 위해서 원래는 (a)와 같이 2N개의 모든 가능한 binary feature 결과값에 대한 확률을 모두 구해야 하지만 N이 400 ~ 500 이기 때문이 이는 현실적으로 불가능합니다.


현실적인 방법으로 (b)와 같이 binary feature들 사이의 상관관계가 전혀 없다고 가정하고 단순히 각 feature 하나 하나가 나올 확률을 전부 곱해서 식 (1)의 확률을 근사하는 방법을 사용할 수도 있습니다. 이러한 방식을 Naive formulation이라고 하는데, 이는 너무 단순화가 심하기 때문에 성능이 그다지 좋지 않습니다.


따라서 절충적인 방식으로 (c)와 같이 feature들을 소그룹으로 묶고 각 소그룹 사이에는 상관관계가 업다고 가정하는 Semi-Naive formulation을 Ferns에서는 사용하고 있습니다. 즉, S개씩 binary feature들을 묶어서 fern을 만들고 각 fern의 확률값을 구해 곱함으로써 식 (1)의 확률값을 계산하는 방식입니다.


Ferns에서는 각 fern에 대한 확률 P(Fj|Ck)를 구하기 위해 모델 패치를 다양한 랜덤 affine 변환으로 수천번 이상 변형시킨 후 각각의 변환된 패치에서의 Fj의 출력값을 구하고, 이 출력값들의 히스토그램을 확률로서 사용합니다 (이와 같이 확률을 근사하는 방식을 Monte Carlo 방식이라고 합니다).


☞ 결국 ferns는 Semi-Naive Bayesian이라는 새로운 기계학습(machine learning) 방법을 물체인식에 적용한 것으로 볼 수 있습니다. 베이지언(Bayesian) 확률에 대한 보다 자세한 내용은 [기계학습] - 베이지언 확률(Bayesian Probability) 글을 참고하시기 바랍니다.



4. Ferns-demo 소스코드 윈도우즈 버전


http://cvlab.epfl.ch/software/ferns/index.php에 공개된 리눅스 코드를 win7(32bit) 환경에서 visual c++ 2008 (with service pack 1)로 포팅해 보았습니다. 참고용으로 포팅한 코드를 올립니다.


ferns_demo_win.zip


프로젝트 설정에서 opencv 경로를 자신의 opencv에 맞게 설정한 후 컴파일하면 됩니다. 만일 error가 날 경우 zlib를 자신의 opencv 버전 및 visual studio 버전에 맞는 것으로 대체해 주면 됩니다(opencv/build/x86/vcX/staticlib/에 있는 zlib 복사)


※ windows 포팅 버전 파일에는 원본 linux 버전 파일에 포함되어 있는 샘플 동영상 파일(mousepad.mp4)이 포함되어 있지 않습니다. 해당 동영상 파일이 없으면 에러가 발생하므로 원본 linux 버전 파일에서 동영상 파일을 복사한 후 실행하시기 바랍니다.



5. 테스트 프로그램


Ferns를 기반으로 구현한 object detector 프로그램입니다. [개발한 것들] - Ferns Detector 글을 참고해 주세요.



☞ 이상으로 Ferns에 대한 소개글을 마칩니다. 세부적인 이론이나 수식적인 부분은 논문을 참조하기 바랍니다. 개인적으로 봤을 때 평면 물체를 검출하는데는 꽤 쓸만한것 같습니다.


by 다크 프로그래머