[Object Detection] Class-Specific Hough Forests for Object Detection (1)

논문 정보

Gall J. and Lempitsky V., Class-Specific Hough Forests for Object Detection (PDF, Images/Videos/Code), IEEE Conference on Computer Vision and Pattern Recognition (CVPR'09), 2009. ©IEEE

---

주요 Keyword

Hough Forest (Hough Voting Codebook)

Random Forest (미리 걔념을 알아야할듯)

Object Detection

Codebook

Voting

앙상블

---

Abstract

- 타켓된 One 클래스를 감지하는 알고리즘.( 이후, 멀티클래스 관련논문이 존재하는듯~)

- 이미지내에 특정 오브젝트의 위치까지 판단.

- 전체적인 개념으로 볼때, Viola jones의 객체 인식 알고리즘과 하는 일이 거의 유사하다고 판단.

---

Random Forest[1]

한국어 refer를 찾아보니 다음과 같이 정의하고 있다.

1. bagging과 같은 bootstrap sample을 traning data로 사용하되 split을 하는 변수를 random하게 선택하는 하여 각 split 시, 변수선택 과정을 생략하고 random하게 선택된 변수에서 best split의 위치를 찾는 방법을 택함(링크)

2. Breiman에 의해 2004년 제안된 랜덤 포레스트는 다수의 결정이진 (binary) 트리를 앙상블 형태로 결합한 것으로, 각 이진트리에서는 랜덤한 방법으로 트리들을 성장 시킨다. 학습과정에서 Random Forest는 랜덤한 수의 노드를 생성시키고 각 트리의 노드마다 information gain에 최적의 판별식과 임계값을 결정한다. 이렇게 생성된 N개의 이진 결정트리들은 앙상블로 결합되어 패턴 분류의 일반화(generalization) 율을 높이는 역할을 한다. 테스트시에는 입력 벡터가 각 트리에 적용이 되고 각 트리에서 생성된 클래스별 확률값은 분류 클래스의 수만큼의 bin을 갖는 히스토그램에 누적되어 누적 확률 히스토그램을 생성한다. 최종적으로 각 빈의 최대 확률값을 추정하고 가장 높은 빈에 해당하는 클래스로 입력벡터를 분류한다. Random Forest는 이진 결정 트리를 기본으로 함으로 학습데이터의 수나 차원에 상관없이 빠른 학습 속도를 가짐으로 많은 양의 데이터를 실행시키는데 탁월하며 Support vector machine이나 Adaboost등에 비해 향상된 정확성을 가지는 분류기 이다. 또한, 기본적으로 이진 분류이지만 단계별 노드의 수를 조절하여 멀티클래스로 쉽게 확장될 수 있는 장점을 지니고 있다.(링크)

3. 우리는 사용자들이 single classification trees에 대해서 알고있다고 가정한다. input vector로 부터 새로운 object를 classify하기 위해서, forest의 각 tree에 input vector를 넣는다. 각각의 tree는 classification을 하고, 우리는 이것을 해당 class에 대한 vote라고 말한다. forest는 가장 많은 vote를 얻은 classification을 택한다. (링크)

4. Random Forest는 앙상블(Ensemble) 모델 중 하나이다. 데이터의 일부를 추출하여 의사 결정 나무를 만드는 작업을 반복하고, 이렇게 만들어진 다수의 의사 결정 나무들의 투표(voting)로 최종 결과를 출력한다. 또 각 가지를 나누는 변수를 선택할 때 전체 변수를 매번 모두 고려하는대신 변수의 일부를 임의로 선택하는 특징을 갖는다.(링크)

5. Random Forest는 Leo Breiman과 Adele Cutler에 의해 개발된, decision tree들이 여러 개 모여서 만들어진 ensemble classifier이다. 새로운 object에 대한 input vector를 이용하여 분류하기 위해서는, forest내 각 tree에 input vector을 넣는다. 각 tree는 classification 결과를 주게 되는데, 이를 그 class에 대한 "votes"라 한다. forest는 가장 많은 vote를 가진 class를 선택하게 된다. (링크) 

각 tree는 다음과 같이 grow된다:

     5.1. 만약 training set의 case(class) 개수가 N 이라면, 랜덤하게 N개의 case를 샘플링한다. 

   - 그러나 replacement를 가지고 original data로부터 샘플링한다. 그 샘플은 트리를 growing시키기 위한 training set 이 된다.

   5.2. 만약 M개의 input variable가 존재하고, m<<M이 node를 best split 하는 데 사용되는 M개 중에 랜덤하게 선택된 variable라 하면, m 값은 forest growing 동안에 constant 하다. 

   5.3. 각 tree는 가능한한 가장 크게 확장되며, pruning(가지치기)은 없다. 

※ prunning이란? 일종의 Over-fitting을 막기위한 방법인듯?

※ replacement ? 모름

정리하자면, 

- 앙상블이란 용어는 tree를 구성하는데 있어서 한개의 트리가 아니라 여러개의 트리로 구성된다는 점. 이는 숲(forest)의 모양으로 구성된다는 의미와 같음.

:  Forest is ensemble of several decision trees.

※앙상블은 bagging & boosting 방법이 있다.

- 이 트리구성은 주어진 training set으로 부터 램덤 샘플링한다. (이게 좀 애매함)

- 여러개의 트리의 결과를 취합해서 이를 확률적으로 특정 Class가 높으면 선택한다는 개념.

그외) 

Random Forest는 Binary Decision Tree의 단점을 해결하는데 부터 출발하는듯, 

Binary Decision  Tree는 subset이 하나의 클래스만 포함할 때까지  Binary tree로 Split. fast하고 큰 스케일의 데이터를 hadling할 수 있다는 장점. 반면, Overfitting 특성을 내재. --> 이를 해결!! ?

의문)

각 트리 모델은 램덤 샘플링 횟수에 의해 그 모델 수가 결정된는가?(500개이하라고 나와있던데?)

Decision Tree

double[] ClassifyDT(node, v)
  if node.IsSplitNode then

      if node.f(v) >= node.t then    

          return ClassifyDT(node.right, v)

      else

          return ClassifyDT(node.left, v)

      end

  else

      return node.P

  end

end

Random Forest

Refer Link

---

Building Hough Forests

- 기본적으로 Random Forest 알고리즘과 유사 또는 파생 알고리즘

- 입력값 정보

SET {Pi = (Ii, ci, di)}

P : Patch

I  : Patch's appearances, intensity 정도가 아닐까 생각.

※ Intensity가 아님 ㅠㅠ, 

16x16 Patch

Derivative filter response

즉, 32개의 Channel로 Convert : (RGB 3 Channels 처럼)

// 7+9 = 16 channels

 L, a, b, |I_x|, |I_y|, |I_xx|, |I_yy|, HOG (9개) 

// 최종, 이 16개 채널을 이용하여

//     16개 minfilter 5x5 neighborhood

//   + 16개 maxfilter 5x5 neighborhood 

//   -------------------------------------

//   = 32 개 Channels

--> Why 32 Channels ? (헉, 다시 미궁속으로 들어간 느낌)

왜 이렇게 적용했는지, 논문에 대한 언급은 없으나, 이중 하나의 Channel이 Split Test할 때, Random하게 선택된다.

di : patch의 offset, center와 거리, training sample 이미지의 중심(positive 일때)

ci : class

- Random Forest의 Split 기준

Refer Link

-- pixel based test

-- 16 by 16 Patch

-- 위의 빨간색 원안에 있는 threshold (r) - real handicap value(?)

※ 그냥 분리하기 위하 threshold라고 하면 되지, 논문에서는  real handicap value 이게 모냐 ㅠㅠ

- Hough Forest' Tree Construction

-- 보다 복잡한듯, 일단 위의 방법으로 Tree 구성은 Random Forest 방법을 적용한다고 나와 있음.(3장 Tree Construction)

-- 재귀

-- Node Max depth = 15   ?

-- Patch number Min = 20 ?

-- 트리 구성중에 depth 가 max 값이고 patch 수가 작다면 그 구성노드는 Leaf!! 선언, 이는 Vote information(CL, DL)과 관련(accumulate and save)

  그렇지 않으면, 계속 non-leaf node 생성 그리고 Test!!

※ Leaf ->분리된 맨 마지막 노드중의 하나, cf) split node, non-leaf node

※ 여기서 Test의 의미는 split function을 이용한 일종의 binary 분리 과정인듯.

-- 위에서 언급했듯이, Split 조건은 Random forest 방법을 그대로 적용한다. 그러나, 실제 최적의 Threshold(r)를 찾기위한 방법은 이제부터 이야기한다.

※ 논문자체에서는 이해하기 어려움 ㅠㅠ 소스 분석에서 알았음.

-- 즉, 이 Hough Forest vs Random Forest의 차이는 이 Split Function에서의 Optimal한 threshold를 찾는 알고리즘에 있다.

-- 이를위해, 다음 두가지 값을 최소화한다.

-- 두가지 불확실성(Uncertainty)이 존재 

--- Class Label(0, 1) & Vector Offset

※  Vector Offset =  Green color

즉, 중심과의 패치들과의 거리들의 Set

-- Class Label 의 불확실성 측정

A는 모든 이미지 패치의 Set, Ci는 클래스 레이블

--- 실제적으로 구하는 값의 의미는 

for( i < Split Left Data Size){

p(i) = (분리된 각 클래스의 size)/(Split Left Data Size)

left_sum += (p(i)*log(p(i)):

}

for( i < Split Right Data Size){

p(i) = (분리된 각 클래스의 size)/(Split Right Data Size)

right_sum += (p(i)*log(p(i)):

}

entropy = left_sum+right_sum;

-- Vector Offset의 불확실성

dA는 모든 오프셋 벡터의 평균 

즉, 각 Left Right의 나뉜 각각의 데이터들의 중심값들에 대한 값을 구한후 각각 차이를 위의 공식대로 구한후, Left+Right 함.

반복을 통하여(iteration=10) 이 값들이 최소화되는 값이면 그때 선택

이것이 randomness라는 의미가 Split Test에서 나오는듯하다.

(요약) Split Node에서 Binary로 분할하는 과정

1. 랜덤하게 image patch의 appearance' channel의 하나가 선택.

2. 랜덤하게 patch의 두 점을 선택.

3. random forest의 split function을 적용하여 값을 구한다.

4. iteration = 10 (소스 참고)

(binary tree 구조를 형성하기 위해,) 최적의 Split 하기 위한 Threshold값을 구한다. 이를 위해, 

4.1 random하게 threshold를 선택한다.

threshold는 3에서 구한 distance의 min~max사이의 값이다.

4.2 이 threshold값이 optimal한지를 검사하는데 위에서 소개한 두개의 불확실성 값보다 작다면(min), 바꾼다.

주의할점은 불확실성 값을 저장하는게 아니다. 이것은 선택하기위한 조건일뿐 실제 threshold은 4.1에서 구한 random 값이다.

4.3 이과정을 반복

5. 이 과정에서 Split node에서, 결과값에서 최적의 threshold를 찾았으니, 이 기준에서 나뉘진 두개의 Data Set이 나온다.

단점)

Detail한 Object의 위치를 잡기 어렵다.

part .training  end

Next : object detection

---

Reference

[1] http://stat-www.berkeley.edu/users/breiman/RandomForests/cc_home.htm