Geometry & Recognition

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

$N$개의 꼭짓점을 갖는 두 개의 형상 $S=\{(x_1, y_1), (x_2, y_2),..., (x_N, y_N) \}$, $S'=\{(x'_1, y'_1), (x'_2, y'_2),..., (x'_N, y'_N) \}$이 affine 변환에 의해서 연결이 되는 경우에 각 꼭짓점 사이의 관계는

\begin{align} x'_i &= a x_i  + b y_i + t_x \\ y'_i &= c x_i + d y_i + t_y, \quad (i=1,2,..., N);\end{align}

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

꼭짓점 위치는 실제로 다양한 영상처리 과정에 의해서 얻어지므로 필연적으로 노이즈를 포함하게 되어서 일종의 랜덤 변수로 생각해야 한다. 주어진 랜덤 변수에서 최적으로 매개변수를 추출하기 위해 최소자승법을 이용한다. Affine 변환된 좌표와 실제 측정된 좌표 사이의 거리 차이를 최소화하는 매개변수를 찾도록 하자:

$$L=\sum_i \big| x'_i - a x_i - b y_i - t_x \Big|^2 + \big| y'_i - c x_i -d y_i - t_y\big|^2 $$

Affine변환을 규정하는 매개변수를 구하기 위해서는 L을 각 매개변수에 대해서 미분해서 극값을 가질 조건을 구하면 된다:

        ∂L/∂a = -2 * ∑ (x'_i - a * x_i - b * y_i - t_x) * x_i ;
        ∂L/∂b = -2 * ∑ (x'_i - a * x_i - b * y_i - t_x) * y_i ;
        ∂L/∂c = -2 * ∑ (y'_i - c * x_i - d * y_i - t_y) * x_i ;
        ∂L/∂d = -2 * ∑ (y'_i - c * x_i - d * y_i - t_y) * y_i ; 
        ∂L/∂t_x = -2 * ∑ (x'_i - a * x_i - b * y_i - t_x) ;
        ∂L/∂t_y = -2 * ∑ (y'_i - c * x_i - d * y_i - t_y); 

각 식을 0으로 놓아서 얻어지는 연립방정식을 행렬식으로 다시 정리하면,

$$\left[\begin{array}{ccc} S_{xx} & S_{xy} & S_x \\ S_{xy} & S_{yy} & S_y \\ S_x & S_y & N \end{array}\right]\left[ \begin{array}{ll} a & c \\ b & d\\ t_x & t_y \end{array} \right] = \left[\begin{array}{cc} S_{xx'} & S_{x y'} \\ S_{y x'} & S_{yy'} \\ S_{x'} & S_{y'}\end{array} \right]$$

여기서,
\begin{align} & S_{xx}= ∑ x^2, ~S_{yy} = ∑ y^2, ~S_{xy} = ∑ xy, \\ &S_x = ∑ x, ~S_y = ∑ y, ~S_{x'} = ∑ x', ~S_{y'} = ∑ y' \\ & S_{xx'} = ∑ xx', ~S_{xy'} = ∑ xy', ~S_{yx'} =∑ yx' \end{align} 이다.

// dst = (A,T)src;
//  [u]  = [ A0 A1 ][x] + A4
//  [v]  = [ A2 A3 ][y] + A5
//
BOOL GetAffineParameter(const std::vector<CPoint> &srcPts, 
                        const std::vector<CPoint> &dstPts, 
                        double AT[6]) 
{
    double Sx, Sy, Sxx, Sxy, Syy;
    double Su, Sv, Sxu, Sxv, Syu, Syv ;
    double A[9], invA[9];
    Sx = Sy = Sxx = Sxy = Syy = 0;
    Su = Sv = Sxu = Sxv = Syu = Syv = 0;
    for (int i = srcPts.size(); i-->0;) {
        double x = srcPts[i].x, y = srcPts[i].y ;
        double u = dstPts[i].x, 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] = srcPts.size() ;
    double 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을 만들 수 있다. 물론 추가된 녹색점이 신뢰할 수 있는 것인가에 대한 판단을 하기 위해서는 추가적인 정보가 더 요구된다.

영상에서 전경 물체가 어떤 방향으로 정렬이 되어있는가를 찾는 문제는 다양한 영상 인식 알고리즘에서 나타난다. 예를 들면, 영상에서 사람의 머리가 어떤 자세를 취하고 있는가를 묻는 것에 대한 답이나, 손바닥 인식에서 손이 가리키는 방향에 대한 정보를 제공한다.

물체의 정렬 방향(orientation)의 의미는 영상에서 물체 영역의 픽셀에서 정렬 방향을 정의하는 직선까지 거리의 합이 최소인 직선의 방향(기울기)을 의미한다. 이 직선은 물체 영역의 질량중심 $(x_c, y_c)$을 지나야 한다.

물체 영역의 중심을 지나고 각도가 $\theta$ 만큼 기울어진 직선이 있을 때, 픽셀 $(i, j)$에서 직선까지 거리는

$$ \text{distance} =\left| -(i-x_c) \sin \theta + (j-y_c) \cos \theta\right|$$

로 주어진다. (직선에 수직한 단위 벡터 $(-\sin\theta, \cos\theta)$에 대한 $(i-x_c, j-y_c)$의 정사영임을 생각하면 쉽게 이해할 수 있다) 

따라서, 최소자승법의 의미에서 orientation은 전경 픽셀에 대해 직선까지 거리 제곱을 다 더한 양을 최소화시키는 $\theta$를 구하는 걸로 귀결된다.

$$S(\theta) =  \sum _{  (i,j)~\in \\ \text{object}} \big| -(i-x_c)\sin \theta + (j-y_c) \cos \theta \big|^2 $$

$$ \longrightarrow \quad \theta^{*}  = \text{argmin} \big[ S(\theta) \big].$$

$ S( \theta)$를 $\theta$에 대해서 미분을 한 후에 정리하면,

\begin{align}\sum_{ij} \left[ (i-x_c)^2  - (j-y_c)^2 \right] \sin\theta \cos \theta -\sum _{ij} (i-x_c) (j-y_c) (\cos ^2 \theta - \sin^2 \theta ) = 0\end{align}

$$\therefore~\tan 2\theta^{*} =  \frac{2 \mu_{11} }{ \mu_{20} - \mu_{02}} $$

로 주어짐을 알 수 있다. $\mu_{pq}$ 는 영상의 $p+q$ 차원 central moment에 해당한다. $\tan \theta^*$을 구해보면

$$ \tan \theta^*  = \frac{(\mu_{20}-\mu_{02}) \pm \sqrt{(\mu_{20}-\mu_{02})^2 + 4 \mu_{11}^2 }}{2\mu_{11}}$$로 구해지는데 $S''(\theta^*)= \pm \sqrt{ (\mu_{20}- \mu_{02})^2 + 4 \mu_{11}^2}$이므로 최소조건($S''(\theta^* )\ge0$)을 만족하려면 윗쪽 부호를 선택해야 한다.  따라서 $\mu_{11}>0$이면 $0\le \theta^* \le \pi/2$이고, $\mu_{11}<0$이면 $\pi/2 < \theta^{*} < \pi$의 범위를 가진다.

물론, 이들 central moment을 이용해서 만든 공분산 행렬(covariance matrix) 

$$ \Sigma  = \left( \begin{array}{cc}  \mu_{20} &  \mu_{11} \\ \mu_{11} & \mu_{02} \end{array} \right) $$의 두 eigenvalue 중 큰 값에 해당하는 eigenvector가 물체의 정렬 방향을 알려준다.