'Affine Transformation'에 해당되는 글 3건

  1. 2010.01.20 Affine Transformation
  2. 2010.01.11 Isometric Transformation
  3. 2009.12.14 Similarity Transformation (1)

물체의 형상은 폴리곤이나 폴리곤의 집합으로 근사적으로 표현을 할 수 있다. 예를 들면 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
기준 좌표계에 대해서 원점이 이동하고 회전한 경우에 이 새로운 좌표계에서 점들의 좌표는 바뀐다. 원래의 좌표와 바뀐 좌표값 사이의 관계를 주는 변환이 Isometric transformation (isometry)이다. 평면상에서 이변환은 평행이동 2개 회전각도 1개에 의해서 결정이 된다. 다수의 점과 그 대응점들이 주어진 경우에 두 둘간의 isometry 파라미터는 일반적으로 최소자승법에 의해서 결정될 수 있다.
회전각도가 θ이고, 평행이동이 (tx, ty)인 isometry에 의해서 두 점 (x,y)가 (u,v)로 연결이 되는 경우에, 아래의 식으로 표현이 된다:

u = cosθ * x - sinθ * y + tx ;
v = sinθ * y + cosθ * x + ty ;

최소자승법을 사용하기 위해서는 회전각도 θ보다는 a = cosθ, b = sinθ로 정의된 새로운 파라미터로 식을 표현하는 것이 더 편리하다. 그러나 이 경우에 파라미터 a, b는 서로 독립적이 아니고  a^2 + b^2 = 1의 제한조건을 만족시켜야 한다.  
평행이동 파라미터는 질량중심의 isometry 관계로 해결이 되므로, 이  전체계산을 각각의 질량중심을 기준으로 하는 좌표로 옮겨서 하면 더 이상 평행이동을 고려할 필요가 없고 회전만 생각하면 된다. 

최소자승법의 원리에 따라서 아래의 라그랑지안을 최소화시키는 파라미터 a, b, λ를 찾으면 된다

L = ∑ ( a * xi - b * yi - ui)^2 + ( b * xi + a * yi - vi)^2 + λ*(a^2 + b^2 - 1) ;

여기서 λ는 제한조건 a^2 + b^2 = 1를 넣기 위한 Lagrange multiplier이다. 라그랑지안 L를 각각 a, b, λ에 대해서 미분하여서 다음의 조건을 얻는다:

∑ ( a * xi - b * yi - ui)*xi + ( b * xi + a * yi - vi)*yi + λ*a = 0
∑ ( a * xi - b * yi - ui)*(-yi) + ( b * xi + a * yi - vi)*xi + λ*b = 0
a^2 + b^2 = 1;

이 식들을  a, b, λ에 대해서 풀면 다음의 관계식을 얻든다:

a = (∑ xi*ui + yi*vi) / (∑ xi^2 + yi^2 + λ) ;
b = (∑ xi*vi - yi*ui) / (∑ xi^2 + yi^2 + λ) ;

또한, 라그랑지 멀티플라이어 λ는

A  = (∑ xi*ui + yi*vi);   B =  (∑ xi*vi - yi*ui);

로 놓으면, a^2 + b^2 = 1 조건에서 

∑ xi^2 + yi^2 + λ = sqrt(a^2 + b^2) 

임을 쓰면 된다. 따라서 우리가 구하는 회전각도는

a = A / sqrt(A*A + B*B);
b = B / sqrt(A*A + B*B);

로 주어진다.

질량중심을 빼기전의 좌표 (x,y)의 질량중심과 (u,v)의 질량중심은 서로 isometry에 의해서 연결이 되므로, 이것에서  평행이동 파라미터(tx, ty) 는 결정이 된다;
(xc, yc) --->(uc, vc) ;
uc = a * xc - b * yc + tx ;
vc = b * yc + a * yc + ty ;

참고:

** affine transformation = similarity transformation + shear;
** similarity transformation = isometry transformation + overall scaling;


/* struct CfPt { double x, y;};
*      u = T[0] * x + T[1] * y +T[4] ;
*      v = T[2] * x + T[3] * y + T[5] ; 
*/
BOOL IsometryTransform(CfPt A[], CfPt U[], int n, double T[6]) {
    double cx = 0, cy = 0;
    double ux = 0, uy = 0;
    for(int i = 0; i < n ; i++) {
        cx += A[i].x ;  cy += A[i].y ;
        ux += U[i].x ;  uy += U[i].y ;
    };
    //center of mass ;
    cx /= n; cy /= n;
    ux /= n; uy /= n;

    //centering 된 좌표계에서 계산;
    double dot = 0 , cross = 0;
    for(i = 0; i < n; i++) {
        double x = A[i].x - cx ;
        double y = A[i].y - cy ;
        double u = U[i].x - ux ;
        double v = U[i].y - uy ;
        dot += (x * u + y * v) ;
        cross += ( x * v - y * u) ;
    };
    double norm = sqrt(dot * dot + cross * cross) ;
    double a = dot / norm ;
    double b = cross / norm ;

    T[0] = a ; T[1] = -b ; T[2] = b; T[3] = a; 
    T[4] = ux - (a * cx - b * cy) ;
    T[5] = uy - (b * cx + b * cy) ;
    return 1;
} ;
저작자 표시 비영리 변경 금지
신고

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

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
Eigenface (2)  (0) 2009.12.28
Active Shape Model :: Face  (1) 2009.12.27
Posted by helloktk

2차원 이미지의 기하학적인 변형중에서 일정하게 이동을 시키고, 일정각도 회전 및 전체적인 크기의 변화를 주는 변환이 similarity transformation이다. 이 변화은 두 직선이 이루는 각도를 보존하고 길이비를 변경시키지 않는다. 이 변환보다도 더 일반적인 2차원의 기하학적인 변환은 affine transformation이다. 이것은 한쪽 방향으로의 밀림(sheer)도 허용한다. 그러다 두 직선의 각도는 변환후에도 변하지 않는다.
similarity transformation은 전체적인 크기를 바꾸는 스케일 파리미터(s) 1개와 회전각도(θ) 1개 그리고 x, y축으로의 이동을 나타내는 파라미터 2 (tx, ty)개를 합해서 총 4개의 파라미터가 필요하다. 이 파라미터에 의해서 원본 이미지의 (x,y)점이 변환된 이미지의 (u,v)에 대응한다고 하면, 이들간의 관계는 아래의 식으로 주어진다.

    u =  s*cos(θ)*x - s*sin(θ)*y + tx ;
    v =  s*sin(θ)*y + s*cos(θ)*y + ty;

 이 따라서 원본영상의 2 점에 대응하는 정보만 주어지면 파라미터(s, θ, tx, ty)를 유일하게 결정할 수 있다. 

    (x1, y1) -----> (u1, v1)
    (x2, y2) -----> (u2, v2)

그러나 많은 경우에는 기준점을 잡는데 에러등을 고려하여서 일반적으로 원본 영상의 N(>=2)개의 점에 대응하는 정보를 주게되는데, 이 경우에 변환관계식은 overdetermined되어서 해를 구할 수 없는 경우도 있다. 이 경우에는 최소자승법을 써서 변환점과 변환식에 의해서 의해서 주어지는 값의 차이를 최소화시키는 파라미터를 구해서 쓰면 된다.

L =  ∑ |ui - (s*cos(θ)*xi - s*sin(θ)*yi + tx)|^2 + |vi - (s*sin(θ)*xi + s*cos(θ)*yi + ty)|^2,           (i=1,...,N)

                        (s, θ, tx, ty) = arg min (L)

이 식을 최소화사키는 파라미터는  (a= s*cos(θ), b=s*sin(θ)로 놓으면)  a, b, tx, ty에 대해서 미분하여서 0인 조건을 만족시키면 된다.

a에 대한 미분 :   ∑ (ui - (a*xi - b*yi + tx))*(-xi) + (vi - (b*xi + a*yi + ty))*(-yi) = 0,   
b에 대한 미분 :   ∑ (ui - (a*xi - b*yi + tx))*(yi) + (vi - (b*xi + a*yi + ty))*(-xi) = 0,   
tx에 대한 미분 :  ∑ (ui - (a*xi - b*yi + tx)) = 0.
ty에 대한 미분 :  ∑ (vi - (b*xi + a*yi + ty)) = 0

따라서, Su = ∑ ui, Sv = ∑ vi, Sux = ∑ ui*xi, Suy = ∑ ui*yi, Svx = ∑ vi*xi, Svy = ∑ vi*yi , Sx = ∑ xi, Sy=∑ yi, Sxx = ∑ xi*xi, Sxy = ∑ xi*yi, Syy=∑ yi*yi 라고 하면,

-Sux  + a * Sxx - b * Sxy + tx * Sx - Svy + b*Sxy + a*Syy + ty *Sy = 0; 
  Suy - a * Sxy + b * Syy - tx * Sy -Svx + b*Sxx + a*Sxy + ty*Sx = 0;
  Su - a* Sx + b*Sy - tx * N = 0;
  Sv - b* Sx - a*Sy - ty * N = 0;

의 4개의 식을 얻으므로 4원(a,b,tx,ty) 1차 연립방정식을 풀면 된다. 이식의 답은 쉽게 구할 수 있고, 아래의 코드는 이것을 구현한 것이다. 물론, 점이 2개인 경우에는 파라미터는 유일하게 정해지고, 이보다도 더 간단한 식으로 주어진다.

//dstPt = (ST)(srcPt)
BOOL SimilarTransParams(POINT *srcPts, POINT *dstPts, int n, double ST[4]) {
    double Sx, Sy, Sxx, Syy;
    double Su, Sv, Sxu, Sxv, Syu, Syv ;
    Sx = Sy = Sxx = 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) ;
        Syy += (y*y) ;
        Su += u ;
        Sv += v ;
        Sxu += (x*u) ;
        Syv += (y*v) ;
    }
    double Z = Sxx + Syy ;
    double C1 = Sxu + Syv ;
    double C2 = Sxv - Syu ;
    double A[16] , invA[16] ;
    A[0]  = Sx; A[1]  = -Sy;  A[2]  =   n; A[3] = 0.;
    A[4]  = Sy; A[5]  =  Sx;  A[6]  =  0.; A[7] = n ;
    A[8]  = Z ; A[9]  =  0.;  A[10] =  Sx; A[11] = Sy;
    A[12] = 0.; A[13] =  Z;   A[14] = -Sy; A[15] = Sx;
    InvertMatrix4x4_d(A, invA) ;
    double R[4] ;
    R[0] = Su ; R[1] = Sv; R[2] = C1; R[3] = C2 ;
    // ax = scale * cos(angle) ;
    double ax = invA[0]*R[0]  + invA[1]*R[1]  + invA[2]*R[2]  + invA[3]*R[3];
    // ay = scale * sin(angle) ;
    double ay = invA[4]*R[0]  + invA[5]*R[1]  + invA[6]*R[2]  + invA[7]*R[3];
    // x-translation ;
    double tx = invA[8]*R[0]  + invA[9]*R[1]  + invA[10]*R[2] + invA[11]*R[3];
    // y-translation ;
    double ty = invA[12]*R[0] + invA[13]*R[1] + invA[14]*R[2] + invA[15]*R[3];
    ST[0] = ax ;
    ST[1] = ay ;
    ST[2] = tx ;
    ST[3] = ty ;

    return TRUE ;
}
InvertMatrix4x4()는 4x4행렬의 역행렬을 구한다(OpenCV에서)

더보기

2개의 대응점만 주어진 경우 (x1,y1), (x2, y2)-->(u1,v1), (u2,v2);
bool SimilarTransParams(double x1, double y1, double x2, double y2,
                                     double u1, double v1, double u2, double v2,
                                     double ST[4])
{
    double x21=x2-x1;
    double y21=y2-y1;
    double u21=u2-u1;
    double v21=v2-v1;
    double det=x21*x21 + y21*y21;
    if(det==0.) return false;
    double a=( x21*u21 + y21 * v21)/det ;
    double b=( x21*v21 - y21 * u21)/det ;
    double tx = u1 - a*x1 + b*y1;
    double ty = v1 - b*x1 - a*y1;
    ST[0]=a; ST[1]=b; ST[2]=tx; ST[3]=ty;
    return true;
};
얼굴인식용 training data set을 만들기위해서 얼굴을 정렬시키는데 사용한 예:
- 양 눈의 위치 변환: (70,93), (114, 84) --> (30,45), (100,45)로 변환( linear interpolation사용)
- 실제로 사용되는 변환은 정해진 dst영역으로 매핑하는 src영역을 찾아야 하므로, 역변환이 필요하다.
- 필요한 역변환은 src와 dst의 역할만 바꾸면 쉽게 구할 수 있다.

신고

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

Active Shape Model :: Face  (1) 2009.12.27
Active Shape Model (ASM)  (2) 2009.12.25
Similarity Transformation  (1) 2009.12.14
Eigenface  (0) 2009.12.12
Retinex 알고리즘 관련 자료.  (1) 2009.04.29
Spline Based Snake  (0) 2008.08.15
Posted by helloktk