Ferns를 이용한 영상 Object Detection

영상처리 2013.08.08 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 다크 프로그래머


  • 이전 댓글 더보기
  • 감사합니다 2013.08.17 19:45 신고 ADDR 수정/삭제 답글

    추출한 keypoint로 부터 확률값 히스토그램을 만드는 부분에서 질문드립니다.

    예를들면 keypoint를 추출한뒤 fern사이즈를 30으로 설정하고, fern크기 12개로 설정했을시
    keypoint를 중심으로 -15~15크기의 픽셀값을 기준으로 fern 확률값 히스토그램을 추출하는것이
    맞는건가요?(제가 이해한 부분입니다)- 1번질문입니다.

    fern크기를 12개로 설정했을시 총 12번의 binary feature을 추출해 히스토그램에 누적하는것이구요.
    - 2번 질문입니다.

    이러한 작업을 class 400개, 어파인변환 10000번해서 총 40000번의 누적히스토그램을 구하는 것이구요(3번질문입니다.)

    혹시 코드를 보셧다면, 논문저자분께서 작성하신 코드를 보게 되면 fern 누적히스토그램을 구할때 keypoint주위서 추출한 랜덤 값이 아닌 한줄씩 비교해 크면 1증가시키더군요. 혹시 제가 이해한 부분이 맞는지 궁금합니다(4번질문입니다).

    값진 정보 감사드립니다.

    • BlogIcon 다크pgmr 2013.08.19 07:07 신고 수정/삭제

      fern에 대해 관심들이 많으시네요... 답변을 드리면,
      1. 네. 다만, 패치 크기라는 표현이 정확하겠네요.
      2. fern의 크기가 12라는 의미는 하나의 fern이 12개의 binary feature 조합으로 구성된다는 표현이 좀더 적절하겠습니다.
      3. 클래스(로컬패치)마다 fern의 개수만큼 히스토그램을 생성하므로 총 히스토그램 총 개수는 400 x fern개수 개이고, 각각의 히스토그램은 10000개의 어파인변환 샘플들로부터 구해집니다 (이 숫자들은 파라미터들이므로 조절가능합니다)
      4. 히스토그램을 구할 때 랜덤하게 binary feature를 뽑아서 값을 누적하는 것이 아니라, 미리 랜덤하게 feature들을 뽑아서 fern들을 구성한 후, 히스토그램을 구할 때는 미리 뽑혀진 좌표값 쌍에 대입하여 차이를 구합니다. ferns.cc 생성자를 보면 램덤하게 feature들이 뽑힘을 확인할 수 있습니다.

  • EiGeN 2013.08.20 16:53 신고 ADDR 수정/삭제 답글

    한가지 의문이 들어서 질문 남깁니다.

    예를들어 class A와 유사한(형태학적 유사) local path를 확률값이 높은 순서로 여러개 찾는 문제라고 가정했을때, ferns로 적용이 가능할까요?
    학습할 때 affine-deformation된 것과 더불어 유사한 local patch도 같이 학습시키던지 해서, DB에 등록을 하고 input으로 들어오는 image에 대해 유사한 patch를 어느 수준이상 찾게 할수는 있을까요?

    아니면 다른 알고리즘을 적용을 해야 하는것인지...

    • BlogIcon 다크pgmr 2013.08.20 23:17 신고 수정/삭제

      image retrieval 쪽인가 보네요.
      글쎄요.. 학습이야 얼마든지 시킬 수 있겠지만 성능이 어떻게 나올지는 저도 잘 모르겠습니다. 문제는 두 이미지가 형태상으로 유사할 때 local patch들도 유사할 것인가가 관건이겠네요. 만일 그렇다면 ferns를 사용하는 것도 좋은 방법이 될 것 같습니다. 다만, 이 경우 ferns feature만을 사용하고 detection 방법 혹은 evaluation 방법은 별도로 개발해야 할 것으로 보입니다.

  • 감사합니다 2013.08.22 01:12 신고 ADDR 수정/삭제 답글

    질문이 길어서 메일 보냈습니다ㅜ

    • BlogIcon 다크pgmr 2013.08.22 07:17 신고 수정/삭제

      아무래도 포인터 연산에 대한 이해의 문제로 보이네요.
      if (*(C + *D_ptr) < *(C + D_ptr[1])) index++;
      에서 C는 이미지 픽셀에 대한 메모리 주소, D는 binary feature 좌표가 기준점으로부터 (메모리 주소 상으로) 몇 byte 떨어졌는지를 나타내는 값입니다.

    • 감사합니다 2013.08.22 16:49 신고 수정/삭제

      아!!!@ 이해갔습니다. 감사드립니다^^

  • Soon 2013.08.23 15:15 신고 ADDR 수정/삭제 답글

    보행자 인식 관련 자료를 찾다가 오게되었는데, 정말 대단합니다!
    많은 자료 보고 갑니다. ^^ 감사합니다!

  • BlogIcon Fox's_Diary 2013.10.16 19:54 신고 ADDR 수정/삭제 답글

    크기 s인 펀의 결과값은 0~ (2^s)-1 이 아닐까요??

    • BlogIcon 다크pgmr 2013.10.16 23:55 신고 수정/삭제

      아 네 그렇네요 ^^; 수정하였습니다. 감사합니다.

  • MJ 2013.11.01 15:04 신고 ADDR 수정/삭제 답글

    안녕하세요. 블로그에서 좋은자료 많이 받고 있습니다. 감사합니다.
    자료실(개발한 것들)에 올려주신 Ferns detector를 실행시켜보았는데, 혹시 Window resizing 등의 Scaling 기능은 없는 것인가요? 처음 training시킨 이미지 크기와 달라질 경우 못찾는 것 같아서요. 어떤 다른 설정이 필요한건지 궁금합니다.

    • BlogIcon 다크pgmr 2013.11.03 08:55 신고 수정/삭제

      안녕하세요. 물체를 training시킬 때, 내부적으로 물체를 일정 범위로 resize하면서 학습을 시킵니다. 지금 정확히 기억은 나지 않지만 아마도 원래 크기의 0.5배 ~ 1.5배 사이의 크기만 검출되도록 파라미터를 설정해 놓았던 것으로 기억합니다. 보다 넓은 범위로 크기 변화를 커버하도록 파라미터를 변경할 수는 있지만 컴파일시 고정해 놓은 것이라 이를 동적으로 조절하지는 못합니다.

  • Geometry 2014.01.16 19:54 신고 ADDR 수정/삭제 답글

    정말 재미있게 잘 보고 있습니다.

    내용 상으로 봤을 때, Fern의 갯수와 크기는 히스토그램의 총 수가 정해져있다고 가정했을 때,
    서로 trade-off관계에 있는 것이 맞겠지요?
    즉, 위 예에서 3의 크기를 갖는 3개의 Ferns는 9개의 크기를 갖는 한개의 Fern과 같은 결과를 낼 수 있다고 볼 수 있나요? (대신 bin의 수가 많이 늘어나 invarient한 결과에 상대적으로 좋지 못한 상태를 낳을 수 있나요?

    p.s.: 아 글을 끝까지 읽으니 확률 얘기가 나오네요. 결국 M과 S는 semi-naive bayesian에 사용되는군요?

    • BlogIcon 다크pgmr 2014.01.17 18:37 신고 수정/삭제

      말씀하신 것처럼 fern의 크기는 semi-naive bayesian과 밀접한 관계가 있습니다. 말씀하신 예에서 크기 9인 fern 하나를 사용하는 것은 pure bayesian, 크기 3인 fern 3개를 사용하는 것은 semi-naive, 크기 1인 fern 9개를 사용하는 것은 naive bayesian에 해당합니다. A, B, C, D, E, F, G, H, I 9개의 feature값이 0, 0, 1, 0, 0, 1, 0, 1, 1일 확률을 구할 때, A, B, ..., I 각각에 대해 확률분포(히스토그램)를 구해서 p(A=0)*p(B=0)*...*p(I=1)로 계산하는 것과 A,B,...,I가 가질 수 있는 2^9 = 512가지 경우에 대해 한꺼번에 확률분포(히스토그램)를 구해서 p(A=0&B=0&...&I=1)로 계산하는 것의 차이인데, 전자(naive)는 각 feature들의 확률이 서로 아무런 상관관계가 없이 독립적으로 변한다는 가정하의 확률이고, 후자는 9 feature의 가능한 모든 값의 조합에 대해 직접 확률분포를 계산하여 값을 구하는 방식이기에 후자가 훨씬 정확한 확률값을 낸다고 볼 수 있습니다. 하지만 feature의 개수가 증가(>100)하면 조합의 가짓수가 기하급수적으로 증가하여 계산상으로 다루기 힘들기 때문에 그 절충점인 semi-naive bayesian을 사용한 것입니다. 결론적으로 컴퓨터 용량이 허용한다면 fern의 크기를 키우는 것이 성능상으로는 좋을 것이며 다만 그만큼 계산된 확률분포(히스토그램)가 sparse해지기 때문에 의미있는 확률분포 도출을 위해 훨씬 많은 샘플이 필요할 것입니다 (성능과 컴퓨터용량&샘플수&학습시간 과의 trade-off). http://darkpgmr.tistory.com/119 글도 같이 참조하면 좋을듯 싶습니다.

    • Geometry 2014.01.20 16:22 신고 수정/삭제

      좋은말씀 감사드립니다.

  • lksman0419 2014.01.21 19:31 신고 ADDR 수정/삭제 답글

    먼저 좋은 글 잘 읽었습니다. 궁금한 사항이 있는데요. Fern을 조합할 때 한 패치 내에서 fern의 개수와 크기를 정해놓고 랜덤으로 조합한다고 되어있는데, 여기서 패치는 이미지를 의미하는게 맞는지요? 그리고 feature를 랜덤으로 뽑는다면 불필요한 점도 많이 생길것 같은데.. 이 부분은 사용자의 필요성에 따라 수동으로 뽑는게 더 효과적이지 않을까 하는 생각이 드는데 어떻게 생각하시는지요? 감사합니다. ^^

    • BlogIcon 다크pgmr 2014.01.22 09:17 신고 수정/삭제

      패치란 이미지 일부분을 작게 잘라낸 영역을 말합니다. Ferns에서는 먼저 특징점들을 뽑고 각각의 특징점을 중심으로 한 33 x 33 픽셀크기의 패치들에 대해 Ferns 특징을 계산하게 됩니다. Ferns 특징을 계산할 point 쌍들을 수동으로 직접 지정해줘도 큰 관계는 없습니다만 굳이 그럴 필요는 없다고 생각합니다. 왜냐하면 이러한 point 쌍은 하나의 패치에만 적용되는 것이 아니라 모든 패치들에 대해 동일하게 적용되기 때문입니다. 예를 들어 포인트 쌍 (5,5)-(10,10) 을 하나의 feature로 사용한다면 모든 특징점 패치들에 대해 (5,5)에서의 밝기값과 (10,10)에서의 밝기값을 차를 계산합니다. 그러면 패치마다 서로 다른 결과값이 나올 것인데 그 차이를 이용하여 패치들을 서로 구분하는 원리입니다.

    • 2014.01.23 16:11 수정/삭제

      비밀댓글입니다

    • BlogIcon 다크pgmr 2014.01.23 17:44 신고 수정/삭제

      접근방법을 제가 잘 이해했는지 모르겠네요. 추측컨데 특징점 추출 과정없이 관심영역 전체를 하나의 패치로 생각하여 ferns 특징을 추출한 후 추출된 ferns 특징의 시간에 따른 변화를 관찰하여 대상을 식별코자 하는 것으로 이해했습니다. 만일 그렇다면 포인트 쌍에 대한 binary feature를 사용한다는 점만 유사할 뿐 나머지 과정은 원래의 ferns와는 무관한 것으로 생각됩니다. 사실 저는 시간축에 따른 ferns 변화를 어떻게 특징으로 활용할지 잘 감이 떠오르진 않습니다. 그냥 생각나는 방법은 시간축으로 샘플링한 ferns 값들을 쭉 연결한(concatenate) 값을 SVM 등에 넣고 학습시키는 방법 정도일것 같은데 시간축에 대한 샘플링 간격을 어떻게 할지가 문제일것 같습니다. 그리고 기존의 틀을 이용하는 것이 아니기 때문에 나름의 방법을 잘 찾으셔야 할 것 같습니다.

    • lksman0419 2014.02.04 20:07 신고 수정/삭제

      네 좋은정보 감사합니다. 다크님 덕분에 많은 도움이 되었습니다. ^^
      random fern에 대해서는 이해를 했습니다. 공부하면서 random forest라는 새로운 개념에 대해서 알게되었는데.. 다크님처럼 이해하기 쉽게 설명한 자료가 없네요. 아직 확실히 이해는 못했습니다만, 혹시 이 부분도 아시는지요?혹시 아신다면 fern 에서 확장된 개념으로 이해했는데...random fern은 하나의 결과값이 나온다면.. random fern에서는 다수의 결과값을 뽑아서 majority voting rule을 사용해서 최종 결과를 낸다고 이해했는데.. 이게 맞는지 모르겠네요 ^^;

    • BlogIcon 다크pgmr 2014.02.05 07:28 신고 수정/삭제

      random forest는 어떤 classification 문제에 대해 다수의 decision tree들을 독립적(랜덤)으로 학습시킨 후 새로운 입력에 대해 각각의 tree마다 클래스 decision을 내린 후, 말씀하신 것처럼 majority voting rule을 적용하여 최종 클래스를 결정하는 방법입니다. random ferns에 대한 확장된 개념이라기 보다는 그냥 둘이 서로 다른 부류의 기계학습(machine learning) 방법이라고 생각하시는게 좋습니다. random ferns는 semi-naive Bayesian 틀(framework)에 따라서 클래스를 결정하는 방법으로서 다수의 독립적인 class probability density (fern이라 불리며 random forest의 decision tree에 대응)들을 학습시킨 후, 새로운 입력에 대해서는 각 fern에서 계산된 class probability들을 서로 곱하여 최종 class 확률을 계산하는 방식입니다. 즉, 다수의 classifier들을 랜덤하게 학습시킨다는 점은 유사하지만, 각 classifier들을 어떻게 학습시키는지(forest는 class decision tree, ferns는 class probability density를 추정)와 각 classifier들의 output을 어떻게 결합시키는지(forest는 majority voting, ferns는 확률을 곱함)에 있어서 서로 차이가 있으며 일반적으로 random ferns가 random forest보다 성능이 좋다고 알려져 있습니다.

  • sunny 2014.02.05 20:50 신고 ADDR 수정/삭제 답글

    정리 감사합니다. 내용 중에 궁금한 사항이 있습니다.
    1. 논문에서는 1 class에 대해서 10000개로 확장했다고 했는데 이게 하나의 패치에 대해서 affine 변환을 10000번 했다는 의미인가요?
    2. affine 변환을 할 경우 패치사이즈는(이미지 사이즈) 그대로 두고 할텐데,아님 사이즈가 변할 수 있는건가요? 만약 회전(scale, 이동 등)을 할 경우 빈공간이 생기게 되는데 이 부분은 intensity 값을 0으로 그대로 두고 fern 특징값을 구하는지요?

    • BlogIcon 다크pgmr 2014.02.06 07:58 신고 수정/삭제

      1. 입력 영상 전체를 랜덤하게 변환시킨 후 각 패치(class)들에 대해 fern을 계산하는 방식입니다. 그 변환이 모든 패치에 동일하게 적용될 뿐, 결과적으로는 패치마다 10000번 변환이 일어납니다.
      2. 패치의 크기도 변합니다.. 빈공간에 대해서는 상수값을 사용하거나 아니면 랜덤 노이즈를 사용할 수 있는데, 구현 코드를 보면 랜덤 노이즈를 사용하고 있습니다.
      * 세부 구현에 대해서는 ferns 구현 소스코드를 참조하시기 바랍니다 (http://cvlab.epfl.ch/software/ferns/index.php)

  • hope 2014.04.18 00:51 신고 ADDR 수정/삭제 답글

    안녕하세요 글 정말 잘 읽었습니다. 오픈 소스를 windows 운영체제에서 돌려보는데 궁금한 게 있습니다. 코드를 컴파일 했는데 기존에 있는 model.bmp 이미지를 통해 training이 되었습니다.
    이렇게 training이 되고 model.bmp.detector_data 가 생성이 되었습니다. 여기서 코드 어디부분을 수정해야 detection 할 수 있을까요? 그리고 이미지 하나로 training을 하는건 아닐텐데 이 코드가 어떻게 작동하는지 모르겠습니다.

    • BlogIcon 다크pgmr 2014.04.18 07:22 신고 수정/삭제

      안녕하세요. ferns는 이미지 한장으로 training을 합니다. 그래서 이미지를 다양하게 변형시키기 때문에 training 시간이 오래 걸립니다.
      공개된 코드를 컴파일한 후 실행시키면 처음에는 이미지를 불러와서 training을 시킨 후(training 결과는 하드디스크에 파일로 저장됨) 같이 들어있는 동영상 파일에서 detection 및 tracking을 자동으로 시작합니다. 그리고 이후부터는 ferns를 실행할 때마다 training을 하지 않고 하드에 저장된 training 결과 파일을 자동으로 읽어와서 detection을 시작합니다. 따라서, training이 정상적으로 성공했다면 detection을 위해 따로 코드를 수정할 필요가 없습니다. 아마도 어디선가 컴파일이 잘못되지 않았나 싶습니다.

  • hope 2014.04.18 02:07 신고 ADDR 수정/삭제 답글

    제가 추가적으로 해본 결과 detection이 안되는 이유는
    if (cvInvert(HHt, HHt_inv, CV_SVD_SYM) == 0) {
    cerr << "> In template_matching_based_tracker::compute_As_matrices :" << endl;
    cerr << " Can't compute HHt matrix inverse!" << endl;
    cerr << " damn!" << endl;
    exit(-1);
    }

    이부분으로 들어가면서 training 중간에 끝나버리는 것 같습니다. 어떤 문제가 있어서 일까요?

    • BlogIcon 다크pgmr 2014.04.18 07:34 신고 수정/삭제

      저의 경우에는 그런 문제가 발생하지 않았었는데요.. windows 버전으로 바꾼 후 돌렸을 때 training 및 detection까지 잘 동작했습니다. 아마도 리눅스 버전을 윈도우즈 버전으로 바꾸는 과정에서 문제가 발생한 게 아닌가 추측해 봅니다.

  • asd 2015.01.12 21:02 신고 ADDR 수정/삭제 답글

    코드를 실행하면서 문제된점 몇가지 올려봅니다.

    초기화 과정으로 인한 메모리 에러가 발생하여 혹시나 비슷한분이 있으실까봐 댓글을 남깁니다.

    homography_estimator::homography_estimator(void)
    {
    ...... 이상 같음 ....
    scores = NULL;
    sorted_ids = NULL;
    }

    비주얼 12기준으로 위 와같이 두 변수를 초기화를 해주어야만 됩니다.

    그리고 2.49버젼은 왠지 안되서 2.44버젼으로 돌렸습니다.

    2.44버젼은 무리없이 잘돌아가는것을 확인 했습니다~

    • yq 2015.01.29 20:11 신고 수정/삭제

      헐 그렇네요..
      저 변수 두개를 초기화 해야되는걸 어떻게 발견하셨는지..
      덕분에 실행 오류 해결했습니다^^
      아 근데 전 2.4.9 버젼에서 잘돌아가네요..
      그리고 다크프로그래머 님께 무척감사드립니다!
      Ferns.. 좋은 알고리즘 제대로 배워가네요~!

  • 감사합니다 2015.01.20 20:04 신고 ADDR 수정/삭제 답글

    궁금한점이 있는데요 모델의 binary feature의 x,y좌표와 입력영상의 binary feature의 x,y좌표가 동일한가요? 아니면 랜덤하게 선정을 하는건가요

  • yQ 2015.01.29 20:38 신고 ADDR 수정/삭제 답글

    글 너무 잘읽었습니다,..
    논문 구현 동영상에서 보이는 수 많은 원들은 무엇을 의미하나요??
    패치는 33x33 크기라고 하셨으니 아닐거같고.. 패치가 크기기반 아핀 변환된 모습들인지..

    • BlogIcon 다크pgmr 2015.01.30 12:04 신고 수정/삭제

      원의 크기는 패치의 이미지 피라미드(image pyramid) 상에서의 스케일(scale) 정보를 나타냅니다. 본 블로그의 http://darkpgmr.tistory.com/137 글을 참조하시기 바랍니다.

  • 학생 2015.04.10 18:56 신고 ADDR 수정/삭제 답글

    디버깅하는데 LINK : fatal error LNK1181: 'opencv_core244.lib' 입력 파일을 열 수 없습니다.라고 뜹니다. 이부분을 249로 수정하고 싶은데 어떻게 하는지 혹시 알 수 있을까요?

    • BlogIcon 다크pgmr 2015.04.11 05:03 신고 수정/삭제

      그건.. visual studio의 프로젝트 설정에서 바꿔야 하는데요, 위치가 프로젝트 설정의 링크(link)-입력(input) 입니다.

  • 라르크윽 2015.07.22 17:59 신고 ADDR 수정/삭제 답글

    글 매우 잘봤습니다. ferns라는 알고리즘 이해에 도움을 주셔서 감사합니다.
    한가지 의문점이 있는데, 사실 fern의 개수와 크기의 관계가 명확하지 않습니다.
    설명하신 내용 그림3의 경우 위의 설명에는 fern의 개수3, 크기3이라고 하셨는데
    막상 그림3의 내용은 fern의 개수1, 크기9의 예가 아닌가요? 하나의 fern에 9가지 경우의 binary fearture를 구성하니깐요. 제가 올려주신 소스도 분석중인데 소스의 ferns.cc의 pick_random_tests()를 보면
    for(int i = 0; i < number_of_ferns; i++)
    for(int j = 0; j < number_of_tests_per_fern; j++) {
    int k = i * number_of_tests_per_fern + j;
    DX1[k] = dx_min + rand() % (dx_max - dx_min + 1);
    DY1[k] = dy_min + rand() % (dy_max - dy_min + 1);
    DX2[k] = dx_min + rand() % (dx_max - dx_min + 1);
    DY2[k] = dy_min + rand() % (dy_max - dy_min + 1);
    DS1[k] = DS2[k] = 0;
    }
    이렇게 되어 있는데 여기서 fern의 개수를 의미하는 number_of_ferns가 30이고 fern의 크기를 의미하는 number_of_tests_per_fern가 12이므로 binary feature의 위치에 해당하는 (DX1,DY1),(DX2,DY2)를 360가지 경우로 저장합니다. 즉, 하나의 fern에 360가지의 경우로 binary feature를 구성합니다.
    저는 fern의 개수라는 것을 affine된 같은 위치의 patch로 이해하였었는데, 제가 잘못이해하고 있는지 궁금합니다. 소스를 살펴보면 fern의 개수라는 개념은 같은 위치의 affine된 다른 patch가 아니라, 동일한 30개의 patch를 의미하며, 각 개수마다 다른 크기(12)의 feature를 추출하여 2^12=4096확률로 저장되는 그룹 개념인것 같은데, 맞는지 궁금합니다.

    • BlogIcon 다크pgmr 2015.07.22 22:30 신고 수정/삭제

      네.. 그림 3은 fern의 개수 3개, 크기 3이 맞습니다. 그리고 number_of_ferns가 30이고 number_of_tests_per_fern가 12라는 것은 크기가 12인 fern 30개를 사용하여 class를 구분한다는 의미입니다. 이렇게 굳이 그룹을 짓는 것은 수학적 이유가 있는데, ferns는 수학적으로 semi-naive Bayesian에 해당합니다. 이에 대한 내용은 http://darkpgmr.tistory.com/119 글을 참조하시기 바랍니다.

    • 라르크윽 2015.07.23 13:39 신고 수정/삭제

      그렇군요~ 이해가 잘 되었습니다.
      예전글임에도 불구하고 답변 달아주셔서 감사합니다~^^

  • 영상처리공학도 2016.01.29 17:25 신고 ADDR 수정/삭제 답글

    안녕하세요. 페이스 디텍션으로 공부하고 있는 대학생입니다.
    너무 친절하게 써주셔서 도움이 많이 되었습니당 ㅎㅎ
    궁금한점이 있는데 리눅스프로그램을 윈도우로 포팅한다는 말이 윈도우에 돌아갈수 있게끔 한다는 말인가요???
    OS가 다른데 어떻게 포팅을 하는건지 궁금하네용. 음 함수를 고치거나 하는단계인건지 아니면 다른 어떤 과정이 있는지.... 리눅스 프로그램을 윈도우에 쓸수 있도록 쉽게 고칠 수 있나요??
    리눅스를 다뤄본적이 없어서 이부분에서 오픈소스를 쓰려구 하다가도 막히네요... 다크님께서는 어떻게 하시는지 궁금합니다.

    • BlogIcon 다크pgmr 2016.01.31 12:29 신고 수정/삭제

      네, 윈도우 개발환경에서 컴파일되도록 만드는 과정입니다. 핵심 코드는 차이가 없기 때문에 일단 컴파일해 보고 오류가 나면 하나씩 수정하면 됩니다. 일부 시스템 함수들을 바꿔주는 정도이고 대부분은 동일합니다. 다만 프로그램에서 리눅스용 외부 라이브러리를 사용했을 경우에는 해당 라이브러리의 윈도우즈 버전을 설치해서 대체해 주는 과정이 필요할 수 있습니다.

  • 입원중 2016.08.30 18:02 신고 ADDR 수정/삭제 답글

    안녕하세요 간혹 공부하러 오는 학생입니다.
    질문이 있는데요, binary feature를 선택할 때 랜덤하게 뽑는다고 하셨는데, 몇몇 자료에서는 random sampling의 단점이 있어 Conditional Mutual Information Maximization(CMIM), binary tree, FAST CORRELATION-BASED FILTER, ada boost 라는 것을 사용한다고 하였는데요, 혹시 간략하게나마 어떤 내용인지 알 수 있을까요?

    • BlogIcon 다크pgmr 2016.09.03 18:46 신고 수정/삭제

      네, binary feature를 뽑을 때 말씀하신 방법들을 충분히 적용할 수 있고 성능도 더 좋으리라 생각합니다. 그리고 말씀하신 방법들은 다 조금씩 다른 방법/개념들인데 하나씩 공부해 나가야 할 내용이 아닌가 싶습니다. wikipedia 등을 참조하면서 공부해 보시면 좋을 것 같습니다.

  • 궁금함 2016.10.14 11:56 신고 ADDR 수정/삭제 답글

    안녕하세요~ 기본 샘플코드를 돌려보는데 처음에는 잘실행이되다가 어느순간
    warning:pyr_yape06 not optimized for 88*68 image
    you may want add this size to the pyr_yape06::compute_laplacian member function for more efficiency.
    라는 오류와 함께 실행이되지않습니다 ㅠㅠ.. 코드변경한거 없고 있는그대로 사용하는건데 갑자기 이러는 증상이 무엇을까요...

    • BlogIcon 다크pgmr 2016.10.15 00:20 신고 수정/삭제

      예전에 그런 메시지를 봤던것 같은데 오랜전 일이라 기억이 안나네요. 소스코드에서 해당 메시지를 찾아보면 어떨까요?

  • 박준철 2017.03.09 17:42 신고 ADDR 수정/삭제 답글

    그림 3에서 첫번째 그림에서 랜덤한 좌측부터 첫번째와 두번째는 변환되서 서로 다른 패치인가요 아니면 변환되지 않은 패치에서 랜덤한 점을 다르게 뽑는건가요

    • BlogIcon 다크pgmr 2017.03.11 16:14 신고 수정/삭제

      질문을 잘 이해(파악)하지 못하겠네요. 패치는 특징점이고 특징점은 영상에서 특징이 되는 점을 뽑은 것입니나. 하나의 패치와 그 패치를 다양하게 워핑시킨 패치들이 하나의 클래스를 형성합니다. 클래스마다 히스토그램을 학습(생성)시키고 그림 3은 히스토그램 생성 과정을 보여줍니다.