'Similarity Transformation'에 해당되는 글 2건

  1. 2010.01.11 Isometric Transformation
  2. 2009.12.14 Similarity Transformation (1)
기준 좌표계에 대해서 원점이 이동하고 회전한 경우에 이 새로운 좌표계에서 점들의 좌표는 바뀐다. 원래의 좌표와 바뀐 좌표값 사이의 관계를 주는 변환이 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