[cite]10.1109/CVPR.2001.990517[/cite]

1. Introduction

이 논문은 속도가 빠르면서 강인한 물체 인식을 위한 프레임워크를 제안합니다. 논문에서는 이를 흑백 영상에서의 얼굴 인식에 적용하여 높은 프레임레이트로 동작하는 것을 확인하였습니다.

이 프레임워크는 3가지 특징이 있습니다. 첫번째는 integral image라는 새로운 이미지 표현을 사용하였다는 점입니다. 이를 통해 매우 빠른 피쳐의 계산이 가능하게 되었습니다. 이것은 Papageorgious의 연구에서 착안하였는데, 그의 연구에서와 같이 Haar Basis function을 연상시키는 피쳐를 사용하였습니다.

두번째로 AdaBoost를 사용하여 적은 수의 중요한 피쳐들만을 선택하고 이를 이용하여 분류기를 생성한 방법입니다. 빠른 분류를 하기 위해서 모든 피쳐가 아닌 중요한 피쳐들에만 집중하였습니다. 이는 Tieu, Viola의 연구에 착안하여 AdaBoost 과정을 조금 수정하여 피쳐를 선택하였습니다. 각 개별 피쳐는 약 분류기(weak classifier)에 해당됩니다. Boosting 과정의 각 단계의 결과로 새로운 약분류기를 선택하는데, 이는 피쳐 선택 과정으로 볼 수 잇습니다.

세번째는 복잡한 분류기들을 통합하기 위해 단계적인 구조를 사용한 것입니다. 이를 통해 속도는 비약적으로 빨라질 수 있었습니다.

2. Features

여기서 다룰 인식기는 이미지에서의 간단한 피쳐를 이용합니다. 픽셀 값을 직접 사용하지 않고 피쳐를 사용하는 이유는 여러가지가 있는데, 가장 큰 이유로 피쳐는 한정된 수의 트레이닝 데이터로부터는 얻기가 힘든 도메인 정보를 얻어내기 위해서 입니다. 또 다른 이유로는, 픽셀 기반의 시스템보다 속도가 빠르다는 장점이 있습니다.

앞에서 이야기한 것과 같이 단순한 피쳐로 Haar basis function과 비슷한 피쳐가 사용되었습니다. 이 피쳐는 3가지 종류가 있는데, 각각 2, 3, 4개의 사각형 영역을 갖는 것이 차이입니다. 2개의 경우, 각 영역에 존재하는 픽셀 값의 합을 계산한 다음 둘 간의 차이를 계산합니다. 3개 영역의 경우, 양쪽 영역의 합을 더한 다음 가운데 영역을 빼서 계산을 하고, 4개의 경우에는 대각선 방향의 영역끼리의 차이를 계산하게 됩니다.

만약 크기가 24 * 24 이미지에서 이러한 피쳐를 완전히 뽑는다면 이것은 180,000개가 넘습니다.

2.1 Integral Image

이러한 사각형 피쳐들은 integral image를 통하여 빠르게 계산할 수 있습니다. integrla image의 x, y 위치는 왼쪽 위로부터 x, y 위치까지의 합을 저장하고 있습니다.

$$ii(x, y) = \sum_{x' \leq x, y' \leq y} i(x', y')$$

여기서 ii는 integral image를, i는 원래 이미지를 나타냅니다.

다음을 참고하여, 이미지를 한번 훑는 것으로 integral image를 생성할 수 있습니다.

$$s(x, y) = s(x, y-1) + i(x, y)$$

$$ii(x, y) = ii(x-1, y) + s(x, y)$$

Integral image를 이용하면 사각 영역의 합을 단 4번의 참조로 구할 수 있습니다. 나아가 두 영역으로 이루어진 피쳐는 중간의 2부분을 공유하기 때문에 6번이면 계산이 끝납니다. 마찬가지로 3영역 피쳐는 8번, 4영역 피쳐는 9번이면 됩니다.

2.2 Feature Discussion

사각형 모양의 피쳐는 steerable filters와 같은 다른 피쳐들에 비해 단순해 보일 수 있습니다. 하지만 가로, 세로, 대각선만을 다루는 사각형 피쳐들로 효과적으로 학습하기에 충분한 이미지 표현이 가능합니다. Integral image와의 조합을 통해서 사각 피쳐들은 그 자체의 제한을 뛰어넘을 수 있습니다.

3. Learning Classification Functions

다른 여타 기계 학습 알고리즘과 마찬가지로 positive와 negative 트레이닝 셋이 주어지면 이를 통해서 분류기를 학습시키게 됩니다. 이 시스템에서는 AdaBoost를 변형시켜서 사용할 피쳐들의 선택하는 작업과 분류기를 훈련시키는 작업을 같이 하고자 합니다.

각 이미지에서 28 * 28 크기의 서브 윈도우에서 사각 피쳐들을 생각해보면, 이는 오히려 픽셀의 수보다 더 많은 피쳐들을 갖게 됩니다. 아무리 integral image로 빠르게 계산이 가능하더라도 이것은 부담되는 계산량일 것입니다. 하지만 그들 중 아주 적은 피쳐들만을 가지고도 성능이 좋은 분류기를 만들 수 있습니다. 중요한 것은 어떻게 그러한 피쳐를 찾느냐 입니다.

약(weak) 학습 알고리즘을 하나의 사각형 피쳐를 골라가는 작업이라고 정의합니다. 이 사각형 피쳐는 이미지가 positive인지 negative인지 분류를 가장 잘 하는 피쳐가 되어야 합니다. 또한 약 학습기(learner)는 각 피쳐에 대해서 오분류가 가장 덜 되도록 하는 임계값을 결정하는 역할을 합니다.

따라서 약 분류기(classifier) $ h_j(x) $는 따라서 피쳐 $ f_j$와 임계값 $ \theta_j $, 부등호의 방향을 조절해주는 parity $p_j$의 조합으로 나타내어집니다.

$$h_j(x) = 1 \text{, if } p_j f_j(x) \lt p_j \theta_j \\0, \text{otherwise}$$

여기선 x는 24 * 24 크기의 서브 윈도우를 나타냅니다.

Boosting 알고리즘을 정리하면 아래와 같습니다.

1. 이미지와 positive, negative 쌍이 주어집니다. $(x_1, y_1), \dots, (x_n, y_n) $
2. 가중치를 초기화합니다. $ w_{1,i} = 1/2m \text{ or } 1/2l \text{ for } y_i = 0, 1 $ m과 l은 postivei, negative 샘플의 수입니다.
3. $ t= 1, \dots, T$에 대하여 4-7을 반복합니다.
4. 가중치를 normalize 합니다. $ w_{t, i} = \frac{w_{t, i}}{\sum_{j=1}^n w_{t, j}} $
5. 각 피쳐 j에 대하여 분류기 $h_j$를 학습시킵니다. 에러는 가중치를 고려하여 $\epsilon_j = \sum_i w_i |h_j(x_i) - y_i | $로 계산합니다.
6. 가장 낮은 에러를 보이는 분류기 $h_t$를 선택합니다.
7. 가중치를 업데이트합니다. $ w_{t+1, i} = w_{t, i} \beta_t^{1-e_i} $ 여기서 $x_i$가 잘 분류되었다면 $ e_i = 0$ 이고 그렇지 않다면 1입니다. 또한 $\beta_t = \frac{\epsilon_t}{1- \epsilon_t} $ 입니다.
8. 최종적으로 완성된 강 분류기는 다음과 같습니다.
   $ h(x) = 1 \text{, if } \sum_{t=1}^T \alpha_t h_t(x) \geq 0.5 \sum_{t=1}^T \alpha_t $, otherwise 0
   $ \alpha_t = \log 1 / \beta_t $

실제로는 하나만으로 낮은 에러를 보이는 피쳐는 없기에 초반에 선택되는 피쳐는 0.1 ~ 0.3 사이의 에러를, 후에 선택되는 피쳐는 0.4 ~ 0.5 정도의 에러를 갖게 됩니다.

3.1 Learning Discussion

많은 피쳐 선택 알고리즘이 있지만 이 알고리즘은 대다수의 피쳐들을 과감히 버리도록 하고 있습니다.

3.2 Learning Results

초기 실험의 경우 200개의 피쳐들을 선택하여 95%의 인식률을 보였으며, 오탐지는 14084개 중 1개뿐이었습니다. 하지만 속도는 384 * 288 크기 이미지에서 0.7초가 걸렸습니다. 당연하게도 성능을 늘리려고 피쳐를 더 추가하면 속도는 더 느려질 것입니다.

한편, 얼굴 인식에 대한 관점에서 보면 AdaBoost에서 첫번째 선택된 피쳐는 다음과 같이 해석할 수 있습니다. 주로 눈 부분은 검고 그 아래 코와 턱 부분은 밝은 픽셀을 갖기에 이를 이용하는 것처럼 보입니다. 이 피쳐는 상대적으로 크기 때문에 그 위치나 크기에 대하여 민감하게 작용하지는 않습니다. 두번째 피쳐 또한 두 눈과 코 사이의 영역을 이용하는 것처럼 보입니다.

4. The Attentional Cascade

이제 속도를 올리기 위하여 분류기를 단계적으로 구성한 방법을 알아봅시다. 강화된 분류기는 positive 영역을 검출하는 동안 많은 negative 서브 윈도우들을 맞닥드리게 됩니다. 따라서 하위의 복잡한 분류기로 내려가기 전에 단순한 분류기에서 미리 negative 대상을 걸러내는 식으로 속도를 향상 시킬 수 있습니다. 단 이 단순한 분류기는 false positive rate를 적게 유지시키는 한도 내에서 동작하여야 합니다.

전체 검출 과정은 결정 트리 형태로 구성됩니다. 첫번째 분류기에서 positive가 나온다면, 더 높은 검출률을 보이는 두번째 분류기로 내려가 검사를 하고 같은 동작을 계속 반복하는 식으로 동작하게 됩니다. Negative 결과가 나온다면 즉시 그 과정을 중단합니다.

단계적인 구조를 만들기 위해 AdaBoost 과정에서 false negatives를 최소화하도록 임계값을 정하는 것으로 수정을 하였습니다. 참고로 일반적으로 AdaBoost가 사용하는 낮은 오류율을 기준으로 한다면 높은 검출률과 높은 false positive율을 보이게 됩니다.

이 방법을 사용하여 단 두개의 피쳐로 이루어진 분류기를 만들었을 때, 임계값은 100%의 인식률과 40%의 false positive율을 보였습니다. 그리고 그 과정에서 걸리는 시간은 단 60개의 프로세서 명령만이 필요할 뿐입니다. 이러한 단계적 분류기는 이미지를 서브 윈도우로 스캔하는 과정에서 얼굴이 아닌 부분을 조기에 탐지하여 더 계산을 진행하지 않고 다음 영역으로 빨리 넘어가도록 하여줍니다.

다른 결정 트리와 마찬가지로, 하위 분류기는 상위 분류기를 통과한 샘플들만을 이용해서 훈련됩니다. 그 결과 하위 분류기는 상위보다 더 어려운 분리를 해내야 하기 때문에 하위로 갈 수록 높은 false positive 율을 가지게 됩니다.

4.1 Training a Cascade of Classifiers

다른 분류기와 마찬가지로 사용되는 역시 분류기의 수에 대하여 성능과 계산 시간 간의 트레이드 오프가 있습니다. 자세히 살펴보면 1. 분류 단계의 수, 각 단계에서 사용되는 분류기의 수, 3. 각 단계에서의 입계값에 따라 계산할 피쳐의 수가 결정이 되어 트레이드 오프를 발생시키는 요인입니다. 이러한 것들을 결정하는 최적 값은 존재하지 않으나, 실제 구현에서는 간단한 방법을 사용합니다. 사용자는 최소한 false positive율이 얼마나 줄어들어야 할지와, 최대로 허용할 인식률을 설정하고, 각 단계가 이 조건을 만족할 때 까지 피쳐를 추가합니다. 또한 같은 방법으로 전체 인식기가 조건을 만족할 때까지 단계를 추가합니다.

4.2 Detector Cascade Discussion

최종적으로 만들어진 분류기는 6000개의 피쳐와 32 단계로 이루어져있습니다. 507개의 얼굴과 75개의 서브 윈도우로 이루어진 데이터셋에서 서브 윈도우당 평균 10번의 계산을 통해 얼굴을 검출할 수 있었습니다.

5. Results

38개의 단계로 이루어진 분류기는 정면 얼굴을 통해서 학습되었습니다. 학습을 위해서 4916 개의 수작업으로 크기와 위치를 24 * 24로 맞춘 이미지를 사용하였습니다. 얼굴이 아닌 이미지는 9544개의 이미지로 얼굴이 아닌 부분을 잘라내서 사용하였습니다. 처음 5개의 단계에서는 이텍터가 1, 10, 25, 25, 50 피쳐를 사용하였고, 남은 단계에서는 더욱 많이 증가하도록 하여 총 6061개의 피쳐가 사용되었습니다.

데이터셋이 모두 다른 광원에서 찍혔기 때문에 normalization 과정이 거쳐야 했습니다. $ \sigma^2 = m^2 - \frac{1}{N} \sum x^2 $로 계산되는 분산 값은 추가적으로 픽셀 제곱의 integral image를 생성하는 것으로 쉽게 구할 수 있었습니다.

서브 윈도우를 얼마나 좁은 간격으로 움직이느냐도 속도에 영향을 끼쳤습니다.

---