Similarity Transformation

2차원 이미지의 기하학적인 변형 중에서 평행이동, 회전 및 전체적인 크기의 변화를 주는 변환이 similarity transformation이다. 이 변환은 두 직선이 이루는 각을 보존하고 길이 비를 유지한다. 따라서 similarity 변환 후 물체의 모양은 변환 전과 같은 형태를 가진다. 이 변환보다도 더 일반적인 2차원의 기하학적인 변환은 affine transformation이다. Affine 변환은 한쪽 방향으로의 밀림(sheer)도 허용한다. 평행한 두 직선은 affine 변환 후에도 여전히 평행하다.

Hierarchy of 2d transformation

 

Similarity transformation은 전체적인 크기를 바꾸는 scale parameter($s$) 1개와 회전각($\theta$) 1개, 그리고 $x,y$축으로의 평행이동을 나타내는 parameter ($t_x$, $t_y$) 2 개를 합해서 총 4개가 있어야 한다. 이 parameter에 의해서 원본 이미지의 픽셀 $(x,y)$가 변환된 이미지의 픽셀 $(u,v)$에 대응한다고 하면, 이들 간의 관계는 다음식으로 주어진다.

$$u=s\cos (\theta )x-s\sin (\theta )y+t_x$$

$$v=s\sin (\theta )y+s\cos (\theta )y+t_y$$

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

$$(x_1,y_1)\to (u_1,v_1)$$

$$(x_2,y_2)\to (u_2,v_2)$$

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

$$\begin{array}{rl}L=\sum _i& [{|u_i-(s\cos (\theta )x_i-s\sin (\theta )y_i+t_x)|}^2\\ & +{|v_i-(s\sin (\theta )x_i+s\cos (\theta )y_i+t_y)|}^2]\end{array}$$

$$(s,\theta ,t_x,t_y)=\text{argmin}(L)$$

이 식을 최소화시키는 파라미터는 $(a=s\cos (\theta ),b=s\sin (\theta )$로 놓으면) $a,b,t_x,t_y$에 대해서 극값을 가질 조건에서 얻을 수 있다. $$\frac{\partial L}{\partial a}=0:\sum _i(u_i-(a{x}_i-b{y}_i+t_x))(-x_i)+(v_i-(b{x}_i+a{y}_i+t_y))(-y_i)=0$$

$$\frac{\partial L}{\partial b}=0:\sum _i(u_i-(a{x}_i-b{y}_i+t_x))(y_i)+(v_i-(b{x}_i+a{y}_i+t_y))(-x_i)=0$$

$$\frac{\partial L}{\partial t_x}=0:\sum _i(u_i-(a{x}_i-b{y}_i+t_x))=0$$

$$\frac{\partial L}{\partial t_y}=0:\sum _i(vi-(b{x}_i+a{y}_i+t_y))=0.$$

따라서, $S_u=\sum _i{u}_i$, $S_v=\sum _i{v}_i$, $S_{ux}=\sum _i{u}_i{x}_i$, $S_{uy}=\sum _i{u}_i{y}_i$, $S_{vx}=\sum _i{v}_i{x}_i$, $S_{vy}=\sum _i{v}_i{y}_i$, $S_x=\sum x_i$, $S_y=\sum _i{y}_i$, $S_{xx}=\sum _i{x}_i^2$, $S_{xy}=\sum _i{x}_i{y}_i$, $S_{yy}=\sum _i{y}_i^2$ 라고 하면,

$$-S_{ux}+a{S}_{xx}+t_x{S}_x-S_{vy}+a{S}_{yy}+t_y{S}_y=0$$

$$S_{uy}+b{S}_{yy}-t_x{S}_y-S_{vx}+b{S}_{xx}+t_y{S}_x=0$$

$$S_u-a{S}_x+b{S}_y-t_{x}N=0$$

$$S_v-b{S}_x-a{S}_y-t_{y}N=0$$

의 4개의 식을 얻으므로 $(a,b,t_x,t_y)$에 대한 1차 연립방정식을 풀면 된다.

$$\left[\begin{array}{cccc}{S}_x& -S_y& N& 0\\ S_y& S_x& 0& N\\ S_{xx}+S_{yy}& 0& S_x& S_y\\ 0& S_{xx}+S_{yy}& -S_y& S_x\end{array}\right]\left[\begin{array}{c}a\\ b\\ t_x\\ t_y\end{array}\right]=\left[\begin{array}{c}{S}_u\\ S_v\\ S_{ux}+S_{vy}\\ S_{vx}-S_{uy}\end{array}\right]$$

$$\text{or}\mathbf{A}\cdot \mathbf{x}=\mathbf{b}$$

$4\times 4$ 행렬 $\mathbf{A}$의 역행렬은 다음과 같이 쉽게 구해진다. 

$${\mathbf{A}}^{-1}=\frac{1}{S_x^2+S_y^2-N(S_{xx}+S_{yy})}\left[\begin{array}{cccc}{S}_x& S_y& -N& 0\\ -S_y& S_x& 0& -N\\ -(S_{xx}+S_{yy})& 0& S_x& -S_y\\ 0& -(S_{xx}+S_{yy})& S_y& S_x\end{array}\right]$$

아래의 코드는 이것을 구현한 것이다. 물론, $N=2$개인 경우에는 파라미터는 유일하게 정해지고 이보다도 더 간단한 식으로 주어진다.

// dst = (S|T)(src)
BOOL SimilarTransParams(std::vector<CPoint>& src, std::vector<CPoint>& dst, double ST[4]) {
    double Sx = 0, Sy = 0, Sxx = 0, Syy = 0;
    double Su = 0, Sv = 0, Sxu = 0, Sxv = 0, Syu = 0, Syv = 0;
    for (int i = srcPts.size(); i-->0;) {
        double x = src[i].x, y = src[i].y;
        double u = dst[i].x, v = dst[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 denorm = Sx * Sx + Sy * Sy - src.size() * Z;
    // det = (denorm)^2;
    if (denorm == 0) return FALSE;
    invA[16] = { Sx, Sy, -src.size(),           0,
                -Sy, Sx,           0, -src.size(),
                -Z,   0,          Sx,         -Sy,
                 0,  -Z,          Sy,          Sx};
    for (int i = 0; i < 16; i++) invA[i] /= denorm;
    //
    double b[4] = {Su, Sv, Sxu + Syv, Sxv - Syu};
    for (int i = 0; i < 4; i++) {
    	double s = 0;
        for (int j = 0; j < 4; j++) 
            s += invA[i * 4 + j] * b[j];
        ST[i] = s;
    }
    return TRUE ;
};

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

similarity_trans.nb

0.01MB

BOOL InvertMatrix4x4_d(double* srcMatr, double* dstMatr) {
    double di = srcMatr[0];
    double d = 1.0 / di;

    dstMatr[0] = d;
    dstMatr[4] = srcMatr[4] * -d;
    dstMatr[8] = srcMatr[8] * -d;
    dstMatr[12] = srcMatr[12] * -d;
    dstMatr[1] = srcMatr[1] * d;
    dstMatr[2] = srcMatr[2] * d;
    dstMatr[3] = srcMatr[3] * d;
    dstMatr[5] = srcMatr[5] + dstMatr[4] * dstMatr[1] * di;
    dstMatr[6] = srcMatr[6] + dstMatr[4] * dstMatr[2] * di;
    dstMatr[7] = srcMatr[7] + dstMatr[4] * dstMatr[3] * di;
    dstMatr[9] = srcMatr[9] + dstMatr[8] * dstMatr[1] * di;
    dstMatr[10] = srcMatr[10] + dstMatr[8] * dstMatr[2] * di;
    dstMatr[11] = srcMatr[11] + dstMatr[8] * dstMatr[3] * di;
    dstMatr[13] = srcMatr[13] + dstMatr[12] * dstMatr[1] * di;
    dstMatr[14] = srcMatr[14] + dstMatr[12] * dstMatr[2] * di;
    dstMatr[15] = srcMatr[15] + dstMatr[12] * dstMatr[3] * di;
    di = dstMatr[5];
    dstMatr[5] = d = 1.0 / di;
    dstMatr[1] *= -d;
    dstMatr[9] *= -d;
    dstMatr[13] *= -d;
    dstMatr[4] *= d;
    dstMatr[6] *= d;
    dstMatr[7] *= d;
    dstMatr[0] += dstMatr[1] * dstMatr[4] * di;
    dstMatr[2] += dstMatr[1] * dstMatr[6] * di;
    dstMatr[3] += dstMatr[1] * dstMatr[7] * di;
    dstMatr[8] += dstMatr[9] * dstMatr[4] * di;
    dstMatr[10] += dstMatr[9] * dstMatr[6] * di;
    dstMatr[11] += dstMatr[9] * dstMatr[7] * di;
    dstMatr[12] += dstMatr[13] * dstMatr[4] * di;
    dstMatr[14] += dstMatr[13] * dstMatr[6] * di;
    dstMatr[15] += dstMatr[13] * dstMatr[7] * di;
    di = dstMatr[10];
    dstMatr[10] = d = 1.0 / di;
    dstMatr[2] *= -d;
    dstMatr[6] *= -d;
    dstMatr[14] *= -d;
    dstMatr[8] *= d;
    dstMatr[9] *= d;
    dstMatr[11] *= d;
    dstMatr[0] += dstMatr[2] * dstMatr[8] * di;
    dstMatr[1] += dstMatr[2] * dstMatr[9] * di;
    dstMatr[3] += dstMatr[2] * dstMatr[11] * di;
    dstMatr[4] += dstMatr[6] * dstMatr[8] * di;
    dstMatr[5] += dstMatr[6] * dstMatr[9] * di;
    dstMatr[7] += dstMatr[6] * dstMatr[11] * di;
    dstMatr[12] += dstMatr[14] * dstMatr[8] * di;
    dstMatr[13] += dstMatr[14] * dstMatr[9] * di;
    dstMatr[15] += dstMatr[14] * dstMatr[11] * di;
    di = dstMatr[15];
    dstMatr[15] = d = 1.0 / di;
    dstMatr[3] *= -d;
    dstMatr[7] *= -d;
    dstMatr[11] *= -d;
    dstMatr[12] *= d;
    dstMatr[13] *= d;
    dstMatr[14] *= d;
    dstMatr[0] += dstMatr[3] * dstMatr[12] * di;
    dstMatr[1] += dstMatr[3] * dstMatr[13] * di;
    dstMatr[2] += dstMatr[3] * dstMatr[14] * di;
    dstMatr[4] += dstMatr[7] * dstMatr[12] * di;
    dstMatr[5] += dstMatr[7] * dstMatr[13] * di;
    dstMatr[6] += dstMatr[7] * dstMatr[14] * di;
    dstMatr[8] += dstMatr[11] * dstMatr[12] * di;
    dstMatr[9] += dstMatr[11] * dstMatr[13] * di;
    dstMatr[10] += dstMatr[11] * dstMatr[14] * di;
    return TRUE;
}

2개의 대응점만 주어진 경우 $(x_1,y_1),(x_2,y_2)\to (u_1,v_1),(u_2,v_2)$;

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, y21 = y2 - y1;
    double u21 = u2 - u1, 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의 역할만 바꾸면 쉽게 구할 수 있다.

원본 얼굴 이미지

변환된 영상