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을 이용해서 얻을 수 있다.

평면에서 주어진 벡터장의 orientation을 찾는 문제는 영상처리 알고리즘에서 자주 접하게 된다. 벡터의 방향은 두 성분의 부호와 상대적인 크기에 따라 달라지지만, 기준선에 대해 상대적으로 기울어진 정도를 나타내는 orientation은 정반대 방향의 두 벡터 $(v_x, v_y)$와 $(-v_x, -v_y)$에 같은 값이 부여되고, 그 값은 벡터의 $x$ 성분과 $y$ 성분의 비의 arctangent 값

$$\theta=\tan^{-1} \left( \frac {v_y}{ v_x }\right)$$

로 계산할 수 있다. 

영상처리에서는 영상에 내재하는 잡음에 의한 영향을 줄이기 위해 한 지점에서 orientation을 추정할 때 보통 그 지점 주변의 벡터 성분의 평균을 이용한다. 주변에서 정반대 방향의 두 벡터가 있는 경우 이 두 벡터는 기하학적으로 같은 orientation을 주지만 더하는 경우 서로 상쇄되어 평균에는 기여가 없으므로 위 식을 사용하면 잘못된 예측을 줄 수 있다. 따라서 잡음을 고려한 상황에서 좀 더 robust 하게 orientation을 추정할 수 있는 방법이 있어야 한다. 벡터 성분의 상대적인 부호만 고려하는 식으로 바꾸기 위해서 $\tan \theta$ 대신에 $\tan (2\theta)$를 고려하자.

\[ \tan (2\theta) = \frac {2\tan(\theta)}{1-\tan^2(\theta)}=\frac {2v_x v_y}{v_x^2 - v_y^2}. \]

분모에서는 각 성분의 제곱, 분자는 두 성분의 곱으로 표현되므로 성분 사이의 상대부호가 같은 경우에는 우측식은 같은 값을 주므로 분모, 분자를 주변 평균값 $v_x v_y ~\longrightarrow ~<v_x v_y>$, $v_x^2 - v_y^2 ~\longrightarrow ~<v_x^2> - < v_y^2>$으로 대체하여도 올바른 orientation을 주게 된다. orientation 각도는

\[ \theta = \frac {1}{2} \tan^{-1}\left( \frac {2 <v_x v_y>}{ <v_x^2> - <v_y^2>}  \right)  \]

으로 주어진다. 실제 계산은 인자가 singular해지는 경우를 피하기 위해서 $\text {atan2}()$ 함수를 사용한다.

https://kipl.tistory.com/293

https://kipl.tistory.com/111

https://kipl.tistory.com/58

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

물체의 정렬 방향(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}} | -(i-x_c)\sin \theta + (j-y_c) \cos \theta |^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가 물체의 정렬 방향을 알려준다.