2D Disjunctive Normal Form (DNF)

기계학습 알고리즘을 물체 추적에 적용해 본다.

물체 추적 문제는 보통 비디오의 첫번째 프레임에서 추적할 대상 물체를 사용자가 사각형 box(ROI, 즉 Region Of Interest라고도 부른다)를 그려 지정해 준다.  이렇게 물체 영역을 지정하면, box 내부의 영역은 학습을 위한 positive 영역, 물체 주위의 배경 영역은 negative 영역으로 간주된다.  이 정보를 이용하여 물체 추적을 위한 분류기를 학습할 수 있다.

먼저, 물체를 포함하는 영역과 배경(물체 영역을 중시으로 물체 영역의 2배 정도) 영역에서 랜덤하게 복수 개의 positive patch$^{주1}$와 negative patch를 추출한다. 이러한 patch들은 분류기(classifier)를 학습할 수 있는 샘플(training samples)이 된다.


1st frame
추적할 대상을 지정해 주는 프레임이다.
사용자의 ROI 지정 $\rightarrow$ ROI 내의 랜덤한 위치에서 정해진 갯수의 patch를 추출한다.   각각의 patch들이 training sample이 된다.

학습
분류기의 학습과 갱신은 adaptive boosting알고리즘을 이용한다.
(임의로 선택된) 두 특징 함수 $h_i$와 $h_j$(특징 함수는 Harr-like feature, LBP, HOG 등이 될 수 있다)에 patch를 입력하면 특징 값 $v_i, v_j$가 계산된다.  모든 샘플에 대해 얻어진 $v$의 가능한 값의 범위를 여러 bin(일정한 간격을 가진 여러 값의 범위)으로 나눈다.  이때, 어떤 하나의 샘플이 주는 $h_i$와 $h_j$ 값은 2차원 공간 상의 하나의 bin(특징 값이 2개이므로 2차원이다)을 가리킨다. 또 각각의 sample은 부류정보(positive or negative)를 가지고 있으므로 이 부류 정보에 따라 bin에 Positive나 Negative로 보팅한다$^{주2}$.


모든 sample에 대한 voting후 각 bin에서 positive로 보팅한 수가 negative로 보팅한 수보다 $r$만큼 더 많다면 이 bin 영역의 위치는 저장된다. $r$은 미리 지정된 상수이다.

특징은 일반적으로 여러 개이고 특징 들의 쌍(pair)은 아주 많이 구성할 수 있다.
가능한 여러 pair중에서 정, 부의 모든 샘플을 고려했을 때 가장 작은 오류를 주는 특징 pair를 선정한다.  이것이 하나의 weak DNF classifier이다.

이러한 과정을 $M$번 반복한다. 모두 $M$개의 weak 2d DNF classifier를 선정하면 학습이 완료되고, 선정된 weak classifier를 선형 결합하여 strong classifier를 만든다.


2nd frame
물체의 2배 확대 영역 내 모든 patch에 대해 strong classifier를 적용하고 confidence map를 작성한다.  confidence map의 measure는 strong classifier의 값으로 한다.
계산 방법은 각 patch를 2d DNF weak classifier에 입력하고 계산된 값이 학습 시에 저장된 bin에 포함된다면 이 patch는 positive가 된다.

confidence값을 integral image로 합하고 최대의 confidence값을 가진 영역이 추적 위치가 된다.
아래는 c.m(confidence measure)값을 평가하여 현재 프레임에서 물체가 발견되었는지(FOUND) 또는 잃어버렸는지(LOST)에 대한 모드 평가를 보여준다.

c.m < $th_1$ $\rightarrow$ LOST $\rightarrow$ initial state (전 영역 검색)
c.m > $th_2$ & LOST state $\rightarrow$ FOUND state로 초기화
c.m > $th_2$ & FOUND state $\rightarrow$ Update classifier

실제 구현 시의 strong classifier는 2D DNF만 사용하는 것이 아니라 1차원 weak classifier와 2d DNF classifier의 조합으로 구성된다.


(주1) patch는 8x8 pixels과 같은 특징을 계산할 수 있는 작은 크기의 window이다

(주2) Harr-like 특징을 예를 들어 생각해보면, patch 내 어떤 위치에, 어떤 크기로 두 특징 값 $h_i$와 $h_j$가 정의된다고 가정하자. 하나의 샘플이 선정되고 두 특징에 적용되면 2개의 값이 얻어지고 이것은 두 특징이 정의하는 2차원 평면 상의 좌표 값을 가리키게 된다.  이 좌표 평면은 균등한 간격으로 가로 세로로 나누어진 많은 작은 영역(bin)들이 정의되어 있다면 이 값은 이 영역들 중의 하나로 떨어지게 된다.  voting이란 두 특징 값이 가리키는 영역의 counter(초기에는 0) 값을 하나 증가시키는 것이 된다.  counter는 샘플의 부류에 따라 positive, negative의 두 개가 존재한다.



참고 논문
[1] Disjunctive Normal Form of Weak Classifiers for Online Learning based Object Tracking, ZhuTeng et. al., VISAPP'2013.