Geometry & Recognition

표준형 타원

$$ \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$$

의 두 주축에 대한 central moment (moment of inertia)는 각각

$$ \mu_{20} = \frac{\pi}{4} a^3 b, \quad \mu_{02} = \frac{\pi}{4} ab^3$$

으로 주어짐은 쉽게 계산할 수 있다. 그런데 타원의 면적인 0차 central moment가 $\mu_{00}= \pi ab$이므로 normalized central moment (위치의 분산을 의미한다)는 각각

$$\tilde\mu_{20} = \frac{\mu_{20}}{\mu_{00}} = \frac{1}{4}a^2, \quad  \tilde\mu_{02} = \frac{\mu_{02}}{\mu_{00}} = \frac{1}{4}b^2$$

따라서 장축과 단축의 반지름은 주축에 대한 2차 normalized central moment을 구하면 얻을 수 있다.

기울어진 타원의 경우는 $\tilde\mu_{pq}$가 픽셀의 분포를 알려주므로 이를 이용한 covariance 행렬의 고유값을 구하면 장축과 단축의 반지름을 알 수 있고, 기울어진 정도도 알 수 있다. 공변행렬

$$ \Sigma = \left( \begin{array}{cc} \tilde\mu_{20} & \tilde\mu_{11} \\ \tilde\mu_{11} & \tilde\mu_{02} \end{array} \right)$$

의 두 고윳값은

$$ \lambda_1 = \frac{1}{2}\left( \tilde\mu_{20}+ \tilde\mu_{02} + \sqrt{ (\tilde\mu_{20} - \tilde\mu_{02})^2 + 4 \tilde\mu_{11}^2} \right),$$

$$ \lambda_2 = \frac{1}{2}\left( \tilde\mu_{20}+ \tilde\mu_{02} - \sqrt{ (\tilde\mu_{20} - \tilde\mu_{02})^2 + 4 \tilde\mu_{11}^2} \right).$$

따라서 기울어진 타원의 장축과 단축의 반지름, 그리고 회전각은

$$ a = 2\sqrt{ \lambda_1}, \quad b = 2\sqrt{ \lambda_2}, \quad \tan(2\theta)=\frac{2 \tilde\mu_{11}}{ \tilde\mu_{20}-\tilde\mu_{02}   }$$

로 주어지므로 회전된 좌표계 $(u, v)$에서 타원의 방정식은

$$ \frac{ u^2 }{4 \lambda_1} + \frac{v^2 }{4\lambda_2} = 1$$

로 쓰인다. 

다시 원 좌표계 $(x, y)$로 돌아가기 위해서 (물론 질량중심이 원점인 좌표계이다)

$$ u =  \cos \theta x+  \sin \theta y, \quad v = -\sin \theta x + \cos \theta y$$

를 대입하면 타원을 2차식 형태

$$ A x^2 + 2B xy + C y^2 = 1$$

로 쓸 수 있는데, 그 계수는

$$ A= \frac{1}{8}\left( \frac{1}{\lambda_1} + \frac{1}{\lambda_2} +\Big( \frac{1}{\lambda_1} - \frac{1}{\lambda_2} \Big) \cos (2\theta) \right)=\frac{\tilde\mu_{02}}{ 4(\tilde\mu_{20}\tilde\mu_{02}-\tilde\mu_{11}^2 )} $$

$$ C= \frac{1}{8}\left( \frac{1}{\lambda_1} + \frac{1}{\lambda_2} -\Big( \frac{1}{\lambda_1} - \frac{1}{\lambda_2} \Big) \cos (2\theta) \right)=\frac{\tilde\mu_{20}}{ 4(\tilde\mu_{20}\tilde\mu_{02}-\tilde\mu_{11}^2 )} $$

$$ B= \frac{1}{8}\left( \frac{1}{\lambda_1} - \frac{1}{\lambda_2} \right)\sin (2\theta)=\frac{-\tilde\mu_{11}}{ 4(\tilde\mu_{20}\tilde\mu_{02}-\tilde\mu_{11}^2 )} $$

로 주어진다. 주어진 object의 normalized central moment를 구하면 타원 fitting에 대한 정보를 구할 수 있음을 보였다.

영상에 담고 있는 object을 간단히 근사를 할 때 타원으로 많이 기술한다(e.g: head tracking). 타원으로 기술하면 장축의 방향으로 object의 기울어진 방향을, 장축과 단축의 길이로 object의 크기를 가늠할 수 있다. object의 픽셀 분포에서 형상에 대한 정보는 2차 moment를 계산해서 얻을 수 있다. 이는 타원이 2차 곡선이기 때문에 가능하다. 그리고 질량중심을 원점으로 잡으면 2차 central moment를 계산해야 한다. 그런데 통계적인 의미를 부여하기 위해서는 central moment를 object의 픽셀로 나눈 normalized central moment로 구성한 covariance matrix를 사용하면 된다.

$$\Sigma = \left(\begin{array}{cc} \tilde\mu_{20} &  \tilde\mu_{11} \\ \tilde\mu_{11} & \tilde\mu_{02} \end{array} \right), \quad\quad\tilde\mu_{pq} \equiv \frac{\mu_{pq}}{\mu_{00}},  \quad (p+q=2)$$ 

(Note: $\mu_{00}$로 정규화를 하지 않더라도 문제는 없다).

$\Sigma$는 영상에서 object pixel의 $x$ 뱡향 분산($\mu_{20}$: $x$축에 대한 회전관성), $y$ 방향 분산($\mu_{02}$: $y$축에 대한 회전관성), $x$-$y$의 correlation을 나타낸다. $\Sigma$가 대칭행렬이므로 두 개의 음이 아닌 고윳값을 가진다. 

\begin{gather} \lambda_1 = \frac{\tilde\mu_{20} + \tilde\mu_{02}}{2} + \frac{ \sqrt{(\tilde\mu_{20} - \tilde\mu_{02})^2 + 4\tilde\mu_{11}^2 } }{2}, \\  \lambda_2 = \frac{\tilde\mu_{20} + \tilde\mu_{02}}{2} - \frac{ \sqrt{(\tilde\mu_{20} - \tilde\mu_{02})^2 + 4\tilde\mu_{11}^2 } }{2}\end{gather}

큰 고유값에 해당하는 고유벡터의 방향이 타원의 장축 방향에 해당하고 (픽셀 변동이 심하므로) , 작은 고윳값의 고유벡터 방향은 단축 방향이다. 그리고 고윳값은 각각 장축과 단축의 반지름의 제곱에 비례한다($\tilde\mu_{pq}$는 단위가 거리 제곱이다). object의 orientation인 타원의 장축 방향은 

$$ \theta = \frac{1}{2} \tan^{-1} \Big( \frac{   2\tilde\mu_{11} }{\tilde\mu_{20} - \tilde\mu_{02}}\Big)= \frac{1}{2} \tan^{-1} \Big( \frac{   2\mu_{11} }{\mu_{20} - \mu_{02}}\Big) $$

로 계산된다. (https://kipl.tistory.com/58)

타원의 orientation 각도를 구했으므로 두 주축을 나타내는 단위벡터는

$$\text{major axis: }(\cos \theta, \sin \theta), \quad \text{minor axis: }(-\sin\theta, \cos \theta)$$

로 쓸 수 있다. 그리고 이 두 축에 대한 object의 회전관성은 정의에 의해서 다음 식으로 구할 수 있다: $(\bar{x}, \bar{y})=\text{center of mass}$

\begin{align}\text{major axis:} ~I_\text{min} &= \sum_{(x, y )\in \text{object}} | - (x-\bar{x})\sin \theta + (y - \bar{y})\cos \theta |^2 \\ &=\frac{\mu_{20}+\mu_{02}}{2} -\frac{\mu_{20} - \mu_{02}}{2} \cos (2\theta)-  \mu_{11} \sin(2\theta)\end{align}

\begin{align}\text{minor axis:} ~I_\text{max} &= \sum_{(x, y)\in \text{object}} | (x-\bar{x}) \cos \theta + (y - \bar{y}) \sin \theta|^2 \\&= \frac{\mu_{20}+\mu_{02}}{2}+\frac{\mu_{20}-\mu_{02}}{2}\cos (2\theta)+ \mu_{11}\sin(2\theta)\end{align}

(note: object의 orientation 각은 $I_\text{min}$을 최소화시키는 값이다)

표준 타원의 장축 반지름이 $a$고 단축 반지름이 $b$일 때 ($x^2/a^2 + y^2/b^2 =1$) 2차 central moment(회전관성)는 간단한 계산에 의해서

$$\mu_{20}^\text{(e)} = \frac{\pi}{4} a^3 b, \quad \mu_{02}^\text{(e)} = \frac{\pi}{4} ab^3,\quad \mu_{11}^\text{(e)}= 0$$

으로 구해짐을 알 수 있다.

주어진 타원이 object을 잘 피팅하려면 타원의 두 축에 대한 회전관성이 각각 object의 주축에 대한  회전관성과 같은 값을 가져야 할 것이다:

$$ I_\text{min} = \mu_{20}^\text{(e)}, \quad I_\text{max} =\mu_{02}^\text{(e)}$$

이 두 식을 풀면 타원의 장축과 단축의 반지름을 구할 수 있다. 

$$a = \Big( \frac{4}{\pi}\Big)^{1/4} \Big( \frac{I_\text{max}^3}{I_\text{min}}\Big)^{1/8}, \quad b = \Big( \frac{4}{\pi}\Big)^{1/4} \Big( \frac{I_\text{min}^3}{I_\text{max}}\Big)^{1/8}$$

보통 object을 타원 피팅할 때 윤곽선 정보를 이용하는데, 이 방법은 윤곽선을 추출할 필요가 없어서 편리하다. 단 내부에 빈 곳이 있는 object의 경우 회전관성을 감소시키므로 좋은 결과를 기대할 수 없다. 영상이 다수의 object를 담고 있을 때는 connected component labeling을 한 후 각각의 component에 대해서 fitting을 수행하면 된다.

void getEllipse(CRaster& raster) {
    const double four_pi = 1.0 / atan(1.0);
    CSize sz = raster.GetSize();
    double xsum = 0, ysum = 0;
    double x2sum = 0, y2sum = 0, xysum = 0;
    int count = 0;
    for (int y = 0; y < sz.cy; y++) {
        BYTE *p = (BYTE *)raster.GetLinePtr(y);
        for (int x = 0; x < sz.cx; x++) {
            if (*p++) {
                count++;
                xsum += x;      ysum += y;
                x2sum += x * x; y2sum += y * y; 
                xysum += x * y;
            }
        }
    }
    if (!count) return;
    double xm = xsum / count;
    double ym = ysum / count;
    double m20 = x2sum - xm * xm * count;
    double m02 = y2sum - ym * ym * count;
    double m11 = xysum - xm * ym * count;
    double theta2 = atan2(2 * m11, m20 - m02);
    double ct = cos(theta2), st = sin(theta2);
    double Imin = 0.5 * (m20 + m02) - 0.5 * (m20 - m02) * ct - m11 * st;
    double Imax = 0.5 * (m20 + m02) + 0.5 * (m20 - m02) * ct + m11 * st;
    double major = pow(four_pi, 0.25) * pow(Imax * Imax * Imax / Imin, 0.125);
    double minor = pow(four_pi, 0.25) * pow(Imin * Imin * Imin / Imax, 0.125);
    drawEllipse(raster, mx, my, major, minor, theta2 / 2);
}

영상처리에서 영상에서 분리된 객체의 형상을 기술할 때 moment를 많이 사용한다. 영상은 각 픽셀 위치에서 컬러 값이 할당된 일종의 2 변수 함수로 생각할 수 있다. 영상의 모멘트는 픽셀 위치(의 단항식)를 컬러값으로 가중치를 주어서 낸 평균이라고 간단하게 기술할 수 있다.  이미지가 $I(x, y)$로 주어진 경우 $p+q$-차 moment는

$$m_{pq} = \iint x^p y^q I(x, y) dxdy, \quad p, q=0,1,2,3...$$

로 정의한다. 그러나 이 정의는 똑같은 형상이라도 원점에서 얼마나 떨어진 위치에 있는가에 따라 결과가 달라지므로 (원점의 선택에 의존되는 정의다. 객체를 구성하는 픽셀 개수를 알려주는 $m_{00}$는 불변이다.) 형상 기술에 적합한 형태가 아니다. 이 문제는 객체의 질량중심에 대한 상대 위치에 대한 weighed mean인 central moment를 feature 값으로 이용하면 된다:

$$ \mu_{pq} = \iint (x - \overline{x})^p ( y - \overline{y})^q I(x, y) dx dy$$

여기서 

$$\overline{x} = m_{10}/m_{00}, \quad \overline{y} = m_{01}/m_{00}$$

로 객체의 질량중심(center of mass)의 위치다. 0차 central moment는 원래의  moment와 같고, 1차 central moment는 질량중심이 원점이므로 0으로 주어진다: $\mu_{10}=\mu_{01}=0$. 이 central moment는 이미지에서 객체가 이동하더라도 동일한 값을 가진다.

그런데 같은 객체를 담은 이미지라도 확대하거나 축소하면 central moment의 값은 변하게 되므로 영상의 scale이 달라지는 경우는 central moment를 feature로 한 형상 판별하는 작업에는 적당하지 않을 수 있다. 이미지를 전체적으로 축소하거나 확대하더라도 같은 값을 주는 scale invariant인 moment 정의가 필요한데, 이는 central moment를 정규화시켜 사용하면 된다.

우선 이미지를 $\lambda$ 만큼 확대하거나 축소하면 변환된 이미지는 $I'(x', y') = I(x'/\lambda, y'/\lambda)$로 표현된다. 이 이미지에서 central moment를 계산하면

\begin{align} \mu'_{pq} &= \iint (x'- \overline{x'})^p ( y' - \overline{y'})^q I(x'/\lambda , y'/\lambda ) dx'dy'\\ &= \lambda^{p+q+2} \iint (x- \overline{x} )^p(y -\overline{y})^q I(x, y) dx dy \\ &= \lambda^{p+q+2} \mu_{pq} \end{align}

즉, 이미지를 scaling 하면 $\mu_{pq}$는 scaling factor $\lambda$의 ${p+q+2}$ 지수승만큼 변하게 된다. 이 변화를 없애기 위해서 양변을 제일 단순한 central moment인 $\mu_{00}^\gamma$로 나누어서 전체적인 scale factor가 사라지게 만들자. 그런데 $$\mu'_{00} = \lambda ^2 \mu_{00}$$

이므로

$$ \frac{ \mu'_{pq} }{ (\mu'_{00})^\gamma} = \lambda^{p+q+2-2\gamma} \frac{\mu_{pq}}{ (\mu_{00})^\gamma } $$

$\gamma$를

$$ \gamma = \frac{p+q}{2}+1$$

로 선택하면 다음의 normalized central moment는 scaling에 대해서 불변인 성질을 가진다.

$$ \eta_{pq} = \frac{\mu_{pq}}{\mu_{00}^\gamma}$$

이진 이미지에서 지름 $2a$인 원과 한 변이 $2a$인 정사각형에 대해서 2차 central moment을 구해보면

$$\text{circle: }~  \mu_{20}= \mu_{02}=\frac{\pi}{4} a^4 = 0.7854 a^4 ,~~\mu_{11}=0,$$

$$\text{rectangle: }~\mu_{20}=\mu_{02}=\frac{4}{3} a^4 = 1.3333 a^4, ~~\mu_{11}=0.$$

그리고 $\mu_{00}= \pi a^2~(\text{circle})$, $\mu_{00}= 4 a^2 ~(\text{rectangle})$이므로 2차 normalized central moment는

$$\text{circle: }~ \eta_{20}=\eta_{02} = \frac{1}{4\pi} = 0.07956,\quad \eta_{11}=0, $$

$$\text{rectangle:}~\eta_{20}=\eta_{02}=\frac{1}{12}=0.08333,\quad \eta_{11} = 0.$$

normalized central moment는 크기에 의존하지는 않지만 원과 사각형에서 분명한 차이를 보이므로 이미지에서 분리된 객체를 구별하는 기준으로 삼을 수 있을 것이다.

물론 normalzed central moment는 객체를 회전시키면 그 값이 다시 변하게 된다. 하지만 이들을 잘 조합하면 회전 불변인 성질까지 추가되는 invariant moment를 구성할 수 있다. 이차 central moment의 경우 질량중심에 대한 회전변환을 고려할 때 서로 다르게 변환하는 부분이 섞여 있는데 이를 분리하면

\begin{gather} \mu_{20}= \iint \left[ \frac{1}{2}(x^2-y^2) + \frac{1}{2}(x^2+y^2) \right] f(x, y) dxdy =T_{11} +\delta_{11} S ,\\ \mu_{11}= \iint xy I(x, y) dxdy = T_{12}+\delta_{12}S, \\ \mu_{02} = \iint \left[ -\frac{1}{2}(x^2 - y^2) +\frac{1}{2}(x^2+y^2) \right] dx dy= T_{22} + \delta_{22} S ,\\ T_{ij} = \iint \left[x_i x_j -\frac{1}{2}(x^2+y^2) \delta_{ij} \right] I(x, y) dxdy=\frac{1}{2} \left(\begin{array}{cc}\mu_{20} - \mu_{02} & 2\mu_{11} \\ 2\mu_{11}& -(\mu_{20}-\mu_{02}) \\\end{array} \right),\\ S= \iint (x^2 + y^2) I(x, y)dx dy =\mu_{20}+\mu_{02}   \end{gather}

로 쓸 수 있는데, $T_{ij}$는 회전 변환에 대해서 rank가 2인 tensor의 성분을 구성하고, $S$는 $rank=0$인 scalar가 된다.  traceless인 $rank=2$인 텐서를 가지고 만들 수 있는 회전에 대해 invariant 한 양은 tensor의 determinant ($\det(T)$)인데, 이를 normalized central moment로 표현하면 (scaling까지 고려하기 위해서)

$$ \text{det}(T) \propto (\eta_{20} - \eta_{02})^2 + 4 \eta_{11}^2 \quad (\text{up to a numerical factor})$$

로 쓸 수 있고, $rank = 0$ 인 부분($S$)은 그 자체로 회전에 불변이다. (물리적으로는 질량중심축에 대한 rotational inertial에 대응하는 양이다). 

$$ \eta_{20} + \eta_{02}= \frac{1}{\mu_{00}^2} \iint (x^2 + y^2 ) I(x, y) dxdy$$

다른 회전 invariant 한 양은 order가 3 이상인 central moment를 이용해서 만든 rank=3 이상인 tensor의 invariant을 이용해서 얻을 수 있다.