OpenCV Adaboost 분석

cvhaartraining.cpp 파일을 분석하였다.

1. 포지티브, 네거티브 데이터 열기

2. 가중치 초기화

3. 모든 haar 특징을 모든 샘플에 대해서 계산

4. 학습 //스테이지 학습 루틴

4.1 cvCreateCARTClassifier

    - 내부적으로 stump를 만들어가면서 가장 좋은 특징을 찾고, 가장 좋은 stump를 받아서 사용자
      가 원하는 갯수로 분할하는 CART 트리를 생성한다.

4.2 선택된 분류기로 학습 데이터를 평가한다.

4.3 cvBoostNextWeakClassifier
    - 부스트 타입에 따라서 호출되는 함수가 다른데, 단순히 샘플에 대한 가중치를 업데이트 하고, 선택된 특징의 신뢰도를 리턴하는 것 같다.

4.4 선택된 분류기에다가 신뢰도를 곱해준다
  - 이것은, 4,1에서 선택된 분류기는 트리 형태이다. 단순히 1번 분할한 경우에는 왼쪽과 오른쪽 노드가 있고, 결국 왼쪽과 오른쪽 노드의 val 값에 신뢰도를 곱해주는 듯 하다. 여기서 한가지 중요한것은 val에는 4.1에서 선택된 stump의 left와 right 값이 들어있다.

4.5 선택된 분류기를 스테이지에 추가한다.

4.6 포지티브 샘플만으로 분류기 테스트를 해서 강분류기의 임계값을 정한다.

4.6 임계값이 정해지면, 네거티브 샘플에 대해서 False alarm ( False Positive 수 / 전체 네거티브 수)를 구한다.

4.7 모든 샘플에 대해서 평가를 수행한다.
   - 이것은 매 반복마다 성능을 보기 위해서 하는 듯하다. 한가지 특이한건 잠재적인 에러 가능성을 체크 한다.

                 if( ( sum_stage >= 0.0F ) != (data->cls.data.fl[idx] == 1.0F) )
                {
                    v_experr += 1.0F;
                }

 - 위의 코드는 잠재적인 에러를 구하는 식이다. 강분류기의 값이 양수인 경우 실제 데이터가 네거티브라면 위험한 것이 아닐까?

 

//cvhaartraining.cpp 일부분

//어떤 방법으로든 젤 좋은 약분류기를 뽑는 거겠지.
alpha = cvBoostNextWeakClassifier( &eval, &data->cls, weakTrainVals,
                                           &data->weights, trainer );

cvEvalCARTClassifier : 이 함수로 샘플들을 평가하여 값을 넣는다.
    - 샘플 값이 작다면 left, 크거나 같다면 right 
    - 인덱스 값이 - 가 나올때까지 트리를 search하여 val 값을 얻는다.

그렇다면 트리는 어떻게 만들어지며, val값으로 무엇이 들어가는가?

cvCreateCARTClassifier: 이 함수를 통해서 통해서 트리가 생성된다. 이 함수는 사용자가 몇번 분리(split)를 수행할 것인지 정해진 값에 따라서 트리의 노드의 수가 결정된다. 일단 처음에는 루트 노드 생성 후 stump로 값을 구한다. 좌측과 우측의 값이 0이 아니면 좌측과 우측을 각각 분리해본다. 분리를 시도한 좌측과 우측의 에러값을 검사하여 높은 에러값을 갖는 것을 새로운 노드로 추가한다.

그렇다면 stump의 에러값은 어떻게 구해지나?

cvCreateMTStumpClassifier : 이 함수에서 stump를 계산한다. 이것은 병열처리 코드라 분석이 힘들어 이 함수의 순차 프로그래밍 방법의 함수를 분석하였다. 그 함수는 cvCreateStumpClassifier 이다. 이 함수에서는 모든 특징들의 최적 임계값을 찾고, 에러율을 구한다. 하지만 임계값 찾는 방법과, 에러율을 구하는 방법은 상당히 다양한 종류를 사용한다.

icvFindStumpThreshold : 최적 임계값을 찾는 함수, 아마 정렬된 데이터가 넘어갈 것으로 생각된다. stump의 left와 right에는 positive일 확률이 들어가는 것 같다. 즉, 현재 임계값을 기준으로 좌측의 가중치의 합으로 좌측의 Positive 가중치의 합을 나눠 curleft로 저장한다. 다음에 error를 구하는데, error구하는 방법은 4가지 방법을 사용하는 듯하다.

1. misclassification error

2. gini error

3. entropy error

4. least sum of squares error

 

icvBoostStartTraining : 이함수는 cvBoostStartTraining에 의해 콜되는데, DAB, RAB, GAB의 경우 학습데이터의 클래스는 0, 1인데, 이를 -1, 1로 변경시켜 배열에 저장하여 실제 Stump로 분할 할 때, -1, 1을 이용하여 임계값을 결정한다.

cvBoostNextWeakClassifier : 평가한 값을 기준으로 가중치를 갱신한다.

//약분류기의 신뢰도를 더한다?
sumalpha += alpha;
       
        for( i = 0; i <= classifier->count; i++ )
        {
            if( boosttype == CV_RABCLASS )
            {
                classifier->val[i] = cvLogRatio( classifier->val[i] );
            }
            classifier->val[i] *= alpha;
        }

        cvSeqPush( seq, (void*) &classifier );

        //이부분이 중요해보인다. 강분류기의 임계값을 구하는 방법
        // 먼저 모든 Positive 샘플에 대해서 지금까지 선택된 약분류기로 분류를 수행하여 결과값을 
        //저장한다. 그러면 eval.data.fl 안에는 Positive 샘플 각각의 현재까지 선택된 분류기를 통과시켰을때의
        //결과값이 들어있다. 이를 정렬하고, minhitrate 즉,예를들어 0.99이고, Positive 샘플이 100개라면, 
        // 0.01 * 100 = 1 이므로 eval.data.fl[1] 에 있는 값을 임계값으로 선택하겠다는 의미임.
        numpos = 0;
        for( i = 0; i < numsamples; i++ )
        {
            idx = icvGetIdxAt( sampleIdx, i );

            if( data->cls.data.fl[idx] == 1.0F )
            {
                eval.data.fl[numpos] = 0.0F;
                //지금까지 선택된 약분류기로 테스트 해본다.
                for( j = 0; j < seq->total; j++ )
                {
                    classifier = *((CvCARTHaarClassifier**) cvGetSeqElem( seq, j ));
                    eval.data.fl[numpos] += classifier->eval(
                        (CvIntHaarClassifier*) classifier,
                        (sum_type*) (data->sum.data.ptr + idx * data->sum.step),
                        (sum_type*) (data->tilted.data.ptr + idx * data->tilted.step),
                        data->normfactor.data.fl[idx] );
                }
                /* eval.data.fl[numpos] = 2.0F * eval.data.fl[numpos] - seq->total; */
                numpos++;
            }
        }
        icvSort_32f( eval.data.fl, numpos, 0 );
        threshold = eval.data.fl[(int) ((1.0F - minhitrate) * numpos)];

 

//Haar-like 특징으로 판단하는 과정
//중요한 것은 기존 논문에는 네거티브라고 인지한 경우에는 어떤 가중치도 주지 않았지만,
//네거티브라고 인지한 경우에도 어느정도의 가중치를 준다.
//이 가중치가 어떻게 만들어져있는지 분석할 필요가 있다.
float icvEvalCARTHaarClassifier( CvIntHaarClassifier* classifier,
                                 sum_type* sum, sum_type* tilted, float normfactor )
{
    int idx = 0;

    do
    {
        if( cvEvalFastHaarFeature(
                ((CvCARTHaarClassifier*) classifier)->fastfeature + idx, sum, tilted )
              < (((CvCARTHaarClassifier*) classifier)->threshold[idx] * normfactor) )
        {
            idx = ((CvCARTHaarClassifier*) classifier)->left[idx];
        }
        else
        {
            idx = ((CvCARTHaarClassifier*) classifier)->right[idx];
        }
    } while( idx > 0 );

    return ((CvCARTHaarClassifier*) classifier)->val[-idx];
}

 #define ICV_DEF_FIND_STUMP_THRESHOLD( suffix, type, error )                              \
CV_BOOST_IMPL int icvFindStumpThreshold_##suffix(                                              \
        uchar* data, size_t datastep,                                                    \
        uchar* wdata, size_t wstep,                                                      \
        uchar* ydata, size_t ystep,                                                      \
        uchar* idxdata, size_t idxstep, int num,                                         \
        float* lerror,                                                                   \
        float* rerror,                                                                   \
        float* threshold, float* left, float* right,                                     \
        float* sumw, float* sumwy, float* sumwyy )                                       \
{
//임계값 구하고 에러율 평가하는 것            

sumw = 샘플들의 가중치 합

sumwy = 가중치 * 라벨 의 합

sumwyy = 가중치  * 라벨 * 라벨의 합

wl = 임계값으로 분류하였을 경우 왼쪽에 있는 샘플들의 가중치의 합

wr = 임계값으로 분류하였을 경우 오른쪽에 있는 샘플들의 가중치의 합

curleft =  wyl / wl

curright = wyr / wr;            

}

 

- cvTrimWeights : 이 함수는 샘플들의 가중치를 정렬하여 일정 퍼센트만 남기고 웨이트 작은 몇 개의 샘플은 사용하지 않기 위한 작업을 하는 듯하다. 결국 학습 샘플 중에 가중치가 작은 순으로 조금 씩 줄여서 다음 단계를 학습 시키겠다는 전략인듯하다.

ㅇ OpenCV의 약분류기

Opencv의 Boosting 의 경우에는 각 단계에 트리를 생성할 수 있다.

즉 약분류기가 하나의 트리가 되는 것이다. 트리를 만드는 방법은 자세히는 코드를 분석하지 않아 정확히 알 수

없으나, 먼저 가장 좋은 분류 성능을 갖는 특징을 선택하고, 그걸로 분류한 뒤 왼쪽과 오른쪽의 확률을 구하고,

샘플을 다시 왼쪽으로 분류된 샘플, 오른쪽으로 분류된 샘플끼리 묶어서 다시 그걸 각각 분류를 수행한다.

이는 사용자가 몇 번 분할 할 것인가에 따라서 노드의 수가 결정 되는 듯하다.

노드는 어떻게 생성되는가?

- 이부분이 좀 중요하다. 사용자가 예를들어 2번 분할을 원할 경우, 먼저 가장 좋은 분류기로 노드를 하나 생성한다. 그러면 그 노드로 샘플들을 분류할 수 있을 것이다. 분류를 수행할 경우, 왼쪽과 오른쪽으로 분류가 될 것이며, 각각 왼쪽과 오른쪽에는 오류률이 있을 것이다.
2번째 노드를 고르는 과정은 일단 1번째 노드에서 분류된 왼쪽과 오른쪽을 모두, 같은 방법으로 좋은 특징으로 노드를 생성한다. 그러면 그 2번째 왼쪽 노드도 다시 왼쪽과 오른쪽으로 분류할 것이고 각각에 오류률이 생긴다.
오른쪽도 마찬가지이다. 그렇다면, 그 둘 중에 어떤 것을 2번째 노드로 할 지 정하게 된다.

현재 노드의 오류 감소율? = intnode[i-1].stump->rerror - (list[listcount].stump->lerror + list[listcount].stump->rerror

현재 노드의 오류 감소율이라 표현했는데, 그것은 자신의 부모 노드의 에러값에서 자신이 분리햇을 경우, 왼쪽과 오른쪽 두 오류율의 합을 뺀 값,  다시 말하면, 부모 노드로부터 분리되어 온 샘플들 중에 20%가 잘못 분리되어 왔는데, 내가 분리했더니, 왼쪽에 5%, 오른쪽에 5%가 잘못된 경우를 계산하면, 20 - (5+5) = 10. 즉 나는 부모가 걸러내지 못한 10%를 걸러낸 것이다. 따라서 2번째 노드를 선택할 때는 오류감소율이 높은 것을 선택하게 된다.

ㅇHaar-like Normalizaion

Opencv에서는 유사 하르 특징을 정규화를 수행한다. 정규화에 대한 이야기는

"Rapid object detection using a boosted cascade of simple features" 의 5. Result의 Image Processing 부분에서 언급한다.

다음 코드는 영역에 대한 정규화 factor를 구하는 함수이다.

/*
 * icvGetAuxImages
 *
 * Get sum, tilted, sqsum images and calculate normalization factor
 * All images must be allocated.
 */
static
void icvGetAuxImages( CvMat* img, CvMat* sum, CvMat* tilted,
                      CvMat* sqsum, float* normfactor )
{
    CvRect normrect;
    int p0, p1, p2, p3;
    sum_type   valsum   = 0;
    sqsum_type valsqsum = 0;
    double area = 0.0;
   
    cvIntegralImage( img, sum, sqsum, tilted );
    normrect = cvRect( 1, 1, img->cols - 2, img->rows - 2 );
    CV_SUM_OFFSETS( p0, p1, p2, p3, normrect, img->cols + 1 )
   
    area = normrect.width * normrect.height;
    valsum = ((sum_type*) (sum->data.ptr))[p0] - ((sum_type*) (sum->data.ptr))[p1]
           - ((sum_type*) (sum->data.ptr))[p2] + ((sum_type*) (sum->data.ptr))[p3];
    valsqsum = ((sqsum_type*) (sqsum->data.ptr))[p0]
             - ((sqsum_type*) (sqsum->data.ptr))[p1]
             - ((sqsum_type*) (sqsum->data.ptr))[p2]
             + ((sqsum_type*) (sqsum->data.ptr))[p3];

    /* sqrt( valsqsum / area - ( valsum / are )^2 ) * area */
    (*normfactor) = (float) sqrt( (double) (area * valsqsum - (double)valsum * valsum) );
}

위에 정규확 factor 구하는 수식이 멀 의미하는지 몰라서 한참을 연구한 결과, 결국 풀었다.ㅋㅋ

 

위의 수식 전개는 분산을 좀 더 구하기 쉽게 정리한 수식이다. 누구나 보면 쉽게 이해가 갈 것이다.

 

이것은 위에서 구한 분산 정리 식을 이용해서 Opencv에서 factor를 구하는 수식으로 정리하기 위해 수식 전개 결과이다. 결국 Opencv에서 정규화 하는 값은 영역의 표준편차*픽셀 수 이다.

이 정규화 과정이 실제 학습 과정에 어떤 영향을 미칠지는 아직까지는 정확하게 분석을 못하겠다. 하지만, 결론적으로 표준편차가 작다면, 영역 내부의 화소들이 평준화 되어있다는 의미이고, 고로 유사하르 특징의 결과에 큰 신뢰도를 주겠다는 의미이지 않을까 싶다. 반대로 만약 영역 내의 분산이 크다면, 하르의 결과 값이 먼가 찝찝함? 따라서, 결과 값을 상당히 낮게 해주는 역할을 할 것이라 생각된다.

그리고 정규화 factor는 학습 영상의 전체 영역, 즉 인식하고자 하는 영역 전체, 또는 학습 하고자 하는 영상 전체를 대상으로 구하는 것으로 생각되는데, 이것은 좀 더 확실하게 분석해봐야할 듯 하다.