물체의 형상은 폴리곤이나 폴리곤의 집합으로 근사적으로 표현을 할 수 있다. 예를 들면 snake나 active shape model(ASM) 등에서 손모양이나 얼굴의 윤곽, 또는 의료영상등에서 장기의 모양등을 표현할 때 사용이 된다. 이러한 응용에서 주어진 형상을 기준으로 주어진 형상에 정렬을 시켜야 필요가 생긴다. 일반적인 카메라에서 얻은 영상에서 추출한 정보의 경우에는 서로 사영변환의 관계가 주어질것이다. 그러나 많은 경우에는 in-plane 변형만을 고려하면 충분할 때가 많다. 이 경우에 가장 일반적인 형상의 변형은 affine변환의 관계를 가지게 된다. 회전, 평행이동, 크기변환, 및 층밀림(shear)를 허용하는 변환이다. 물론, 간단한 경우로는 shear를 제외할 수 도 있고(similarity transformation), 더 간단하게는 크기변환을 제외할 수 도 있다(isometric transformation).

N개의 꼭지점을 갖는 두개의 형상 S={(x1,y1),...(xN,yN)}, S'={(x'1,y'1),...,(x'N,y'N)}이 affine 변환에 의해서 연결이 되는 경우에 각각의 꼭지점들 간에는

          x'i = a * xi + b * yi + tx ;
          y'i = c * xi + d * yi + ty ;         i=1,...,N; 

의 6개의 매개변수(a,b,c,d, tx, ty)에 의해서 기술이 된다(평행이동:2, 회전:1, shear:1, 스케일: 2). Affine변환은 변환전에 평행인 두직선은 변환후에도 평행인 관계를 유지한다.

꼭지점의 위치는 실제로 다양한 영상처리 방법에 의해서 주어지므로 필연적으로 노이즈를 포함하게 되어서 일종의 램덤변수로 생각해야 한다. 따라서 주어진 랜덤변수에서 최적으로 매개변수를 추출하기 위해서 최소자승방법을 이용한다. 즉, affine변환된 좌표값과 실제값의 차이를 최소화하는 매개변수를 찾는 것이다. 

         L = ∑ ( |x'i - a * xi - b * yi - tx |2 + |y'i - c * xi - d * yi - ty|2 ),

affine변환을 규정하는 매개변수들을 구하기 위해서는 L을 각각의 매개변수들에 대해서 미분을 하여 그 극값을 구하면 된다.

        ∂L/∂a = -2 * ∑ (x'i - a * xi - b * yi - tx) * xi ;
        ∂L/∂b = -2 * ∑ (x'i - a * xi - b * yi - tx) * yi ;
        ∂L/∂c = -2 * ∑ (y'i - c * xi - d * yi - ty) * xi ;
        ∂L/∂d = -2 * ∑ (y'i - c * xi - d * yi - ty) * yi ; 
        ∂L/∂tx = -2 * ∑ (x'i - a * xi - b * yi - tx) ;
        ∂L/∂ty = -2 * ∑ (y'i - c * xi - d * yi - ty); 

각각의 식들을 0으로 놓아서 얻어지는 연립방정식을 행렬의 형태로 다시 정리하여서 쓰면 그 해는 쉽게 구할 수 형태로 된다.

             [ Sxx   Sxy   Sx ][ a  c ]     [  Sxx'   Sxy' ]
             [ Sxy   Syy   Sy ][ b  d ]  =  [  Syx'   Syy' ]
             [ Sx     Sy    N   ][tx, ty ]     [  Sx'     Sy'  ]
 

여기서,
Sxx = ∑ x*x, Syy = ∑ y*y, Sxy = ∑ x*y,
Sx = ∑ x, Sy = ∑ y,
Sxx' = ∑ x*x', Sxy' = ∑
x*y', Syx' = ∑ y*x',
Sx' = ∑ x', Sy' = ∑ y'

이다.

// dst = (A,T)src;

//  [u]  = [ A0 A1 ][x] + A4
//  [v]  = [ A2 A3 ][y] + A5
//
BOOL GetAffineParameter(POINT *srcPts, POINT *dstPts, int n, double AT[6]) {
    double Sx, Sy, Sxx, Sxy, Syy;
    double Su, Sv, Sxu, Sxv, Syu, Syv ;
    double A[9], invA[9] ;
    double det ;
    Sx = Sy = Sxx = Sxy = Syy = 0;
    Su = Sv = Sxu = Sxv = Syu = Syv = 0;
    for (int i = 0; i < n; i++) {
        double x = srcPts[i].x ;
        double y = srcPts[i].y ;
        double u = dstPts[i].x ;
        double v = dstPts[i].y ;
        Sx += x ;
        Sy += y ;
        Sxx += (x*x) ;
        Sxy += (x*y) ;
        Syy += (y*y) ;
        Su += u ;
        Sv += v ;
        Sxu += (x*u) ;
        Sxv += (x*v) ;
        Syu += (y*u) ;
        Syv += (y*v) ;
    }
    A[0] = Sxx ; A[1] = Sxy ; A[2] = Sx ;
    A[3] = Sxy ; A[4] = Syy ; A[5] = Sy ;
    A[6] = Sx  ; A[7] = Sy  ; A[8] = n  ;
    det = (A[0]*(A[4]*A[8]-A[5]*A[7])-A[1]*(A[3]*A[8]-A[5]*A[6])+A[2]*(A[3]*A[7]-A[4]*A[6])) ;
    if (det != 0.) {
        det = 1./det; 
        invA[0] = (A[4]*A[8] - A[5]*A[7]) * det;
        invA[1] = (A[2]*A[7] - A[1]*A[8]) * det;
        invA[2] = (A[1]*A[5] - A[2]*A[4]) * det;
        invA[3] = (A[5]*A[6] - A[3]*A[8]) * det;
        invA[4] = (A[0]*A[8] - A[2]*A[6]) * det;
        invA[5] = (A[2]*A[3] - A[0]*A[5]) * det;
        invA[6] = (A[3]*A[7] - A[4]*A[6]) * det;
        invA[7] = (A[1]*A[6] - A[0]*A[7]) * det;
        invA[8] = (A[0]*A[4] - A[1]*A[3]) * det;
    }
    else return FALSE;

   
AT[0] = invA[0]*Sxu + invA[1]*Syu + invA[2]*Su ;
    AT[1] = invA[3]*Sxu + invA[4]*Syu + invA[5]*Su ;
    AT[4] = invA[6]*Sxu + invA[7]*Syu + invA[8]*Su ;
   
AT[2] = invA[0]*Sxv + invA[1]*Syv + invA[2]*Sv ;
    AT[3] = invA[3]*Sxv + invA[4]*Syv + invA[5]*Sv ;
    AT[5] = invA[6]*Sxv + invA[7]*Syv + invA[8]*Sv ;
    return TRUE ;
};

아래의 그림은 지문에서 얻은 특징점을 가지고 변환을 한 것이다. 밑에 그림이 기준 template (붉은점들)이고 윗그림은 이 기준  template와 입력된 지문의 특징점(노란점+ 녹색점)사이에 서로 메칭이 되는 특징점(노란색)들을 찾고, 그것을 기준으로 두 지문영상간의 affine 파라미터를 찾아서 기준 template을 변환시킨것이다. 이렇게 하면 기준 template에 없는 새로운 특징점(녹색점)을  기준 template에 추가하여서 넓은 범위를 커버할 수 있는 template을 만들 수 있다. 물론 녹색점이 신뢰할 수 있는 것인가에 대한 것은 다른 확률적인 추정을 할 수 있는 정보들이 더 필요하다.

'Image Recognition' 카테고리의 다른 글

Image Morphing  (0) 2010.01.24
Fant's Algorithm  (0) 2010.01.22
Affine Transformation  (0) 2010.01.20
Color Counting  (0) 2010.01.18
Isometric Transformation  (0) 2010.01.11
Active Shape Model (3)  (0) 2009.12.30
Posted by helloktk

댓글을 달아 주세요