CAM-Shift ( Computer Vision Face Tracking For Use in a Perceptual User Interface)

논문 제목 : Computer Vision Face Tracking For Use in a Perceptual User Interface

링크 : http://www.dis.uniroma1.it/~nardi/Didattica/SAI/matdid/tracking/camshift.pdf

예전에 CAM-Shift를 공부했었는데, 가물 가물해서 오랜만에 다시 보았습니다.

기억이 새록 새록...

나중을 위해서 정리를 해보자면,

Mean-shift와 매우 유사합니다.

논문에서는

"The mean shift algorithm is a non-parametric technique that climbs the gradient of a probability distribution to find the nearest dominant mode(peak)." 라고 표현하고 있습니다.

결국 시작점으로부터 가장 가까운 지역적 mode를 찾는 방법이라 설명합니다.

Mean Shift 와 CAM Shift의 차이를 다음과 같이 설명합니다.

Unlike the Mean Shift algorithm, which is designed for static distributions, CAMSHIFT is designed for dynamically changing distributions.

즉, Mean Shift는 정적인 분포를 사용하지만, CAM shift는 동적으로 변화하는 분포를 사용한다고 합니다.

추적을 수행할 경우, 실제 객체는 시간에 따라 확률 분포( 즉, 여기서는 색상)와 크기, 위치가 변화하기 때문에, CAM shift의 필요성을 설명합니다.

이제 간단하게 알고리즘을 정리하면,

먼저 추적하고자 하는 객체의 색상 히스토그램을 구해야 합니다. 사실 이것은, 하나의 응용 일 뿐, 굳이 색상 히스토그램이 아니여도 되겠죠.

논문에서는 다음과 같이 알고리즘을 설명합니다.

1. First, set the calculation region of the probability distribution to the whole image.

2. Choose the initial location of the 2D mean shift search window.

3. Calculate the color probability distribution in the 2D region centered at the search window location in an area slightly larger than the mean shift window size.

4. Mean shift to convergence or for a set number of iterations. Store the zeroth moment (area or size) and
mean location.

5. For the next video frame, center the search window at the mean location stored in Step 4 and set the window size to a function of the zeroth moment found there.Go to Step 3.

1. 먼저 추적 객체의 확률 분포를 생성하고,

2. 검색 윈도우의 초기 위치를 설정합니다.

3. Mean shift의 검색 윈도우 크기보다 좀 더 큰 영역에서 확률 분포를 계산합니다.

4. 반복적으로 수렴할때까지 Mean shift를 이용하여 평균 위치와 영역(0모멘트)을 구합니다.

5. 다음 프레임을 위해서, 4에서 저장된 평균로 검색 윈도우를 이동시키고,  0모멘트를 이용하여 윈도우 크기를 설정합니다.

 

====================================================================================================

s= 2*sqrt( M_00 / 256 )

이 식은 영역의 크기를 나타낸다고 볼 수 있습니다.

M_00는 확률값, 즉 확률 영상에서 화소값을 다 더한것이고, 256은 확률 영상에서 최대값입니다. 결국 만약 확률 영상에서

찾고자하는 객체가 10*10 크기로 어떤 임의의 위치에 있고, 정말 드라마틱하게도 확률값이 모두 256, 즉 100% 라고 보면,

영역의 M_00는 100 * 256 이 될 것입니다. 이것을 256으로 나누고, 다시 루트를 씌우면????

즉 영역을 스퀘어로 봣을 때, 한 면의 길이가 나오겠죠.

그런 의미로 사용한 것 같습니다. 앞에 2를 곱한건 윈도우를 좀 더 크게 사용하기 위함인 듯 하구요.

 

====================================================================================================

논문을 보고, 제대로 이해했는지 확인하기 위해 Opencv 소스 코드를 살펴보았습니다.

//아래 코드는 C:\OpenCV2.1\src\cv\cvcamshift.cpp 파일에 있는 cvCamShift 함수 내용입니다.

CV_IMPL int
cvCamShift( const void* imgProb, CvRect windowIn,
            CvTermCriteria criteria,
            CvConnectedComp* _comp,
            CvBox2D* box )
{
    const int TOLERANCE = 10;
    CvMoments moments;
    double m00 = 0, m10, m01, mu20, mu11, mu02, inv_m00;
    double a, b, c, xc, yc;
    double rotate_a, rotate_c;
    double theta = 0, square;
    double cs, sn;
    double length = 0, width = 0;
    int itersUsed = 0;
    CvConnectedComp comp;
    CvMat  cur_win, stub, *mat = (CvMat*)imgProb;

    comp.rect = windowIn;

    mat = cvGetMat( mat, &stub );

//영역 windowln을 기준으로 mean shift를 수행하여 결과값을 comp에 저장합니다.
    itersUsed = cvMeanShift( mat, windowIn, criteria, &comp );
    windowIn = comp.rect;

//검출된 윈도우를 10정도 키우네요...
    windowIn.x -= TOLERANCE;
    if( windowIn.x < 0 )
        windowIn.x = 0;

    windowIn.y -= TOLERANCE;
    if( windowIn.y < 0 )
        windowIn.y = 0;

    windowIn.width += 2 * TOLERANCE;
    if( windowIn.x + windowIn.width > mat->width )
        windowIn.width = mat->width - windowIn.x;

    windowIn.height += 2 * TOLERANCE;
    if( windowIn.y + windowIn.height > mat->height )
        windowIn.height = mat->height - windowIn.y;

    cvGetSubRect( mat, &cur_win, windowIn );

//모멘트를 계산합니다.
    /* Calculating moments in new center mass */
    cvMoments( &cur_win, &moments );

    m00 = moments.m00;
    m10 = moments.m10;
    m01 = moments.m01;
    mu11 = moments.mu11;
    mu20 = moments.mu20;
    mu02 = moments.mu02;

    if( fabs(m00) < DBL_EPSILON )
        return -1;

//======================================================.
//이부분이 약간 논문이랑 다릅니다. 검출된 영역에서 방향과, 크기를 구하는 것인데,
// 사실 이건 구현 방법에 따라 있겠죠. 당연히 방향을 구하는 방법은 여러가지이고,
// 헌데 대체 저 수식은 어떻게 나온건지... 레퍼런스라도 달아주지..ㅠㅠ
// http://en.wikipedia.org/wiki/Image_moment
// 이 곳에 가면, 아래와 매우 유사한? 수식이 나옵니다. 혹시 궁금하신 분들은 참고하세요.

    inv_m00 = 1. / m00;
    xc = cvRound( m10 * inv_m00 + windowIn.x );
    yc = cvRound( m01 * inv_m00 + windowIn.y );
    a = mu20 * inv_m00;
    b = mu11 * inv_m00;
    c = mu02 * inv_m00;

    /* Calculating width & height */
    square = sqrt( 4 * b * b + (a - c) * (a - c) );

    /* Calculating orientation */
    theta = atan2( 2 * b, a - c + square );

    /* Calculating width & length of figure */
    cs = cos( theta );
    sn = sin( theta );

    rotate_a = cs * cs * mu20 + 2 * cs * sn * mu11 + sn * sn * mu02;
    rotate_c = sn * sn * mu20 - 2 * cs * sn * mu11 + cs * cs * mu02;
    length = sqrt( rotate_a * inv_m00 ) * 4;
    width = sqrt( rotate_c * inv_m00 ) * 4;

//======================================================.
    /* In case, when tetta is 0 or 1.57... the Length & Width may be exchanged */
    if( length < width )
    {
        double t;
       
        CV_SWAP( length, width, t );
        CV_SWAP( cs, sn, t );
        theta = CV_PI*0.5 - theta;
    }

// 결과적으로 위에서 구한 결과값 ( 가로, 길이, 영역 )을 이용하여 다음 프레임을 위해 업데이트 작업을 수행합니다.
  /* Saving results */
    if( _comp || box )
    {
        int t0, t1;
        int _xc = cvRound( xc );
        int _yc = cvRound( yc );

        t0 = cvRound( fabs( length * cs ));
        t1 = cvRound( fabs( width * sn ));

        t0 = MAX( t0, t1 ) + 2;
        comp.rect.width = MIN( t0, (mat->width - _xc) * 2 );

        t0 = cvRound( fabs( length * sn ));
        t1 = cvRound( fabs( width * cs ));

        t0 = MAX( t0, t1 ) + 2;
        comp.rect.height = MIN( t0, (mat->height - _yc) * 2 );

        comp.rect.x = MAX( 0, _xc - comp.rect.width / 2 );
        comp.rect.y = MAX( 0, _yc - comp.rect.height / 2 );

        comp.rect.width = MIN( mat->width - comp.rect.x, comp.rect.width );
        comp.rect.height = MIN( mat->height - comp.rect.y, comp.rect.height );
        comp.area = (float) m00;
    }

    if( _comp )
        *_comp = comp;
   
    if( box )
    {
        box->size.height = (float)length;
        box->size.width = (float)width;
        box->angle = (float)(theta*180./CV_PI);
        box->center = cvPoint2D32f( comp.rect.x + comp.rect.width*0.5f,
                                    comp.rect.y + comp.rect.height*0.5f);
    }

    return itersUsed;
}

===============================================================================================

소스 코드를 어느정도 구현하실 줄 아신다면,

이 정도 설명만으로 충분히 직접 구현하실 수 있겠죠..

혹시 코드 상에, theta, length, width 구하는 식 어디서 나온건지 아시는 분 간단하게라고.. 댓글 부탁드립니다...^^