살군의 보조기억 장치

Another memory device…

Archive for May 2014

영상처리에서 미분과 convolution 의 관계

leave a comment »

보통 엣지edge를 찾거나 할 경우, 기본적으로 미분한 결과를 사용한다. 근데 왜 영상처리에서 미분이 convolution 이 되는 것일까? 갑자기 의문이 들었다. 물론 단순하게 “영상처리에서의 미분은 필터링filtering이고 필터링은 곧 convolution 이다”라고 생각하고 그냥 받아들이면 되지만 그냥 받아들이기엔 뭔가 찜찜하다. 이번 글에서는 왜 영상처리의 미분이 convolution 이 되었는지에 대해 수학적으로 한번 파고들어 보겠다.

편미분partial derivative 가능한 2차원 이미지 F(x,y)가 있을때, 이 함수의 편미분은 (1) 처럼 정리할 수 있다.

\dfrac{\partial F(x,y)}{\partial x} = \lim\limits_{\Delta x \rightarrow 0}^{} \dfrac{F(x + \Delta x, y) - F(x,y)}{\Delta x} (1)

물론 \Delta x는 미소변위이다. 디지털 영상처리의 영역에서 본다면 \Delta x = 1이 가능한 최소값이 된다. 이를 이용해서 (1) 을 좀 더 일반화 시키면,

\dfrac{\partial F(x,y)}{\partial x} \bigg\rvert_{x=i, y=j} \approx f(i+1, j) - f(i,j) (2)

(2) 를 코드로 바꿔보면 아래와 쓸 수 있다.

int g[2] = {1, -1};

for (i=istart; i<=iend; i++)
{
    h[i][j] = 0;
    for (a=0; a<=1; a++)
        h[i][j] += g[a]*f[i+a][j];
}

위 코드는 사소한 문제가 있다. 예를들어 f[iend +1][j] 같이 실제 이미지보다 더 큰 부분의 경우에 대한 프로그램적인 처리가 필요하지만, 이 부분은 이번 글에서의 요점이 아니기 때문에 생략하기로 한다. 이제 위의 코드를 좀 더 일반화 시켜서 g 가 임의의 필터가 되고 2차원 처리가 가능하도록 변경하면,

for (j=jstart; j<=jend; j++)
{
    for (i=istart; i<=iend; i++)
    {
        h[i][j] = 0;
        for (a=astart; a<=aend; a++)
            for (b=bstart; b<=bend; b++)
                h[i][j] = g[a][b]*f[i-a][j-b];
    }
}

위의 코드에서 +a 가 -a 로 바뀐 부분은 마스크mask인 g 와 이미지 f 와의 상관관계를 생각하면 쉽게 이해할 수 있다. 왜 이렇게 바꿨냐하면, 위의 코드를 다시 일반화된 수식으로 풀어쓰면 convolution 이 됨을 쉽게 확인할 수 있기 때문이다.

h(i,j) = \sum\limits_{a=a_{start}}^{a_{end}} \sum\limits_{b=b_{start}}^{b_{end}} g(a,b)f(i-a, j-b) (3)

자!!! 이렇게 해서 convolution 이 나왔다. 수식으로 풀면 (2) 에서 (3) 으로 바로 일반화 시킬 수도 있지만… 이러면 나도 이해가 안되기 때문에…;;;

정리하면, 미분과 convolution 의 문제가 아니라 2차원 영상처리에서 어떠한 필터를 적용하고자 한다면 2D convolution 을 하면 된다는 것을 수식으로 알 수 있다. 미분을 하고싶다면 필터 g 를 미분할 수 있는 coefficient 로 사용하면 되고 가우시안gaussian 필터링을 하고싶다면 g 에 가우시안 필터 계수를 넣으면 되는 것이다.

참고
Advertisements

Written by gomiski

2014/05/13 at 4:48 am

Harris Corner Detector

leave a comment »

Harris corner detector 를 이야기 하기전에 먼저 Moravec corner detector 에 대해 언급을 해야한다. Harris corner detector 는 H. Moravec (1980) 이 제안한 corner detector 를 개선한 것이기 때문에 배경을 알고 가면 더 쉽게 이해가 된다. 사실 나도 이 논문을 읽어보진 않았다.

Moravec corner detector 의 핵심은 조그만 사각형 윈도우를 모든 방향으로 45도 간격으로 이동하면서 얻은 값을 가지고 코너가 있는지 여부를 판단하는 것이다. 물론 여기에는 엣지edge도 포함이 된다. 왜 45도가 되는지는 금방 알 수 있다. 모든 방향으로 1픽셀씩 움직으면 결국 8방향 45도 간격으로 밖에 되지 않기 때문이다. 실제로는 4가지 변위만 측정

Flat

Flat

Edge

Edge

Corner

Corner

E(u,v) = \sum\limits_{x,y}^{} w(x,y)[I(x+u,y+v)-I(x,y)]^2 (1)
window function w(x,y)=binary window

위의 그림과 식 (1)이 Moravec corner detector 이다. I는 이미지이고, w는 윈도우 함수이다. E(u,v)를 이동해가면서 intensity 변화량을 검출한 결과이다. (u,v)를 (1,0), (1,1), (0,1), (-1,1) 로 바꿔가며 네가지 변위를 측정해서 \mathbf{min}(E)의 local maxima 를 탐색한다. 그러나 위의 그림에서 보듯이 Moravec 은 아래와 같은 몇가지 문제를 안고 있다.

  1. 노이즈에 취약하다 – binary window function
  2. 45도 각도의 엣지만을 고려할 수 있다 – (u,v)이동 변위의 고정된 4개 픽셀 값
  3. \mathbf{min}(E) 값만을 가지고 검출한다

이 문제를 해결한 것이 바로 Harris corner detector 다. Harris 는 위에서 언급한 Moravec 의 3가지 문제점에 대한 개선방안을 제시했다.

  1. 노이즈에 취약하다 – gaussian window function 사용
  2. w(x,y)=e^{-\frac{(x^2+y^2)}{2\sigma^2}} (2)
    window function w(x,y)=gaussian window

    즉, 가우시안을 윈도우 함수로 사용해서 노이즈에 대한 민감도를 낮췄다.

  3. 45도 각도의 엣지만을 고려할 수 있다 – 테일러 확장Taylor’s expansion으로 (u,v)의 미소변위에 대해 측정 가능

  4. 기존의 픽셀단위 이동으로는 엣지의 방향을 45도 간격으로 밖에 구할 수 없었다. 이를 해결하기 위해 Moravec 이 제안한 식 (1) 을 테일러 시리즈로 확장해서 엣지의 방향을 보다 정확하게 찾아낼 수 있도록 개선했다. 테일러 확장Taylor expansion한 결과는 식 (3) 과 같다. 2D 테일러 시리즈의 자세한 사항은 이전글을 참고하자.

    \begin{array}{rcl} E(u,v) & \approx & \sum\limits_{x,y}^{} w(x,y)[I(x,y) + uI_x + vI_y - I(x,y)]^2 \\ & \approx & \sum\limits_{x,y}^{} w(x,y)[u^2I_x^2 + 2uvI_xI_y + v^2I_y^2] \end{array} (3)

    (3) 을 다시한번 매트릭스 형태로 정렬하면,

    \begin{array}{rcl} E(u,v)  & \approx & [u,v] \left( \sum\limits_{x,y}^{} w(x,y) \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix} \right) \begin{bmatrix} u \\ v \end{bmatrix} \\ \\ & \approx & [u,v]M \begin{bmatrix} u \\ v \end{bmatrix} \end{array} (4)
    where, M = \sum\limits_{x,y}^{} w(x,y) \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix}

    (4) 에서 보는것 처럼 모든 (u,v)에 대한 이미지의 모든 점 (x,y)를 고려한다.

  5. \mathbf{min}(E) 값만을 가지고 검출한다

  6. 이 부분은 아직 잘 이해가 안된다. 개념적으로는 Local maxima of \mathbf{min}(E) 값만을 검출하더라도 코너라면 (1,0), (1,1), (0,1), (-1,1) 네 방향에서 모두 크게 나올 것이므로 가능하다. 그러나 나머지 유용한 정보들은 모두 버려지게 된다. 이를 개선한 것이 위의 (4) 이다. 테일러 시리즈로 확장하면서 max of min(E) 가 아니라 모든 점들의 정보를 다 사용하기 때문에 보다 정확한 코너의 방향을 추정할 수 있다.

이제 Harris corner detector 를 어떻게 해석하는지에 대해 살펴보자. (4) 에서 M은 symmetric 이므로 이를 decomposition 하면 아래와 같이 정리된다.

M = Q^{\mathsf{T}} \Lambda Q (5)
where, Q is rotation, \Lambda is Diagonal
\begin{array}{rcl} E(u,v)  & \approx & [u,v]  Q^{\mathsf{T}} \Lambda Q  \begin{bmatrix} u \\ v \end{bmatrix} \\ \\ & \approx & [u',v'] \Lambda \begin{bmatrix} u' \\ v' \end{bmatrix} \\ \\ & \approx & \Lambda_{1,1} (u')^2 + \Lambda_{2,2} (v')^2  \end{array} (6)

(6) 에서 보는바와 같이 E(u,v)\Lambda 다시말해 eigen-value 값에 의해 결정이 된다. 이를 수학적으로 판단하기 위한 수식이 바로 (7) 이다.

R = \mathbf{det} M + k (\mathbf{trace} M)^2 (7)
\mathbf{det} M = \lambda_1 \lambda_2
\mathbf{trace} M = \lambda_1 + \lambda_2
k = 0.04 ~ 0.06: empirical constant

\lambda_1\lambda_2는 diagonal matrix \Lambda의 eigen-value 이다. 이번에는 여기까지 🙂

참고

테일러 시리즈(Taylor series)

with one comment

x+x^2+x^3+\cdots은 유한한 수로 표현을 할 수 있을까? 좀 더 일반화 해서, 규칙을 가진 무한히 많은 수의 합이 유한한 수로 표현이 될 수 있을까? 이것은 아주 오래된 질문이다. 물론 우린 답을 알고 있다. 답은 “그렇다” 이다.

이 질문의 기원은 고대 그리스 시절로 거슬러 올라간다. 고대 그리스의 철학자 Zeno 는 무한한 수열의 합이 유한한 결과를 낼 수 있는가에 대해 생각을 했었다. 그러나 Zeno’s paradox 라고 알려진 결과를 통해 불가능하다고 했다. 이후 아리스토텔레스Aristotle는 Zeno’s paradox 에 대해 철학적인 수준에서 반박을 했으나 수학적인 증명을 하진 못했다. 수십년 뒤, 데모크리토스Democritus와 아키메데스Archimedes 대에 이르러서 수학적으로 가능하다는 것이 증명이 되었다.

테일러 시리즈Taylor series와 상관이 없어보이는 무한한 수에 대한 이야기를 먼저하는 이유는, 테일러 시리즈가 위에서 이야기 한 것과 반대로 유한한 값을 무한한 수의 합으로 표현(근사approximation)한 것이기 때문이다. 테일러 시리즈가 뭔지를 한번 보자.

f(x) = f(a)+\dfrac{f'(a)}{1!} (x-a)+ \dfrac{f''(a)}{2!} (x-a)^2+\dfrac{f^{(3)}(a)}{3!}(x-a)^3+ \cdots (1)

이것을 일반화 시키면,

f(x) = \sum\limits_{n=0}^{\infty} \dfrac {f^{(n)}(a)}{n!} \, (x-a)^{n} (2)

단, 이것은 모든 x에 대해서 성립하는 것이 아니라 x a 근처에서만 성립하고, a 의 범위는 f(x) 에 따라 달라진다. 이게 무슨뜻인지는 말로 설명하는 것 보다 그림을 보면 확실하게 이해할 수 있을 것이다.

The Taylor approximations for log(1+x) (black). For x > 1, any Taylor approximation is invalid. 출처: wikipedia

The Taylor approximations for log(1+x) (black). For x > 1, any Taylor approximation is invalid. 출처: wikipedia

위의 그림에서 보듯이 테일러 시리즈의 다항식 차수 N이 증가함에 따라 검은색 선으로 표시된 함수 f(x) = \log(1+x)에 점점 접근하는 것을 볼 수 있다. 그러나 |x|\geq 1일 경우에는 오차가 급격하게 증가한다. 다시말해 \log(1+x) 함수는 |a| < 1인 경우에만 테일러 시리즈를 적용할 수 있다. 또한 N의 차수가 낮더라도 xa 근처 있다면 보다 정확한 근사치를 얻을 수 있다.

테일러 시리즈는 당연히 미분가능한 영역에 대해서만 적용할 수 있다. 테일러 시리즈로 확장하는 것 자체가 미분가능한 구간이 아니면 불가능하니까. 그 외에 필요한 수학적인 조건은 패스.

테일러 시리즈가 주로 쓰이는 곳은,

  1. 정적분definite integral의 계산
  2. 부정적분indefinite integral을 계산하기 힘든 함수의 경우에 아래와 같이 테일러 시리즈를 활용하면 정적분의 계산값을 근사적으로 구할 수 있습니다.

    \displaystyle\int_0^1 \sin (x^2) \mathop{dx} = \displaystyle\int_0^1 \left(x^2 - \dfrac{x^6}{3!} + \dfrac{x^{10}}{5!} - \cdots \right) \mathop{dx}

    위 식에서 \sin (x^2)의 테일러 급수는 \sin (t)t = 0에서의 테일러 전개에 t = x^2을 대입하여 얻어진 식이며, 적분 구간이 [0, 1]이기 때문에 x = 0에서의(즉, a = 0) 테일러 급수를 사용해도 근사오차가 크지 않습니다.

  3. 함수의 점근asymptotic 특성 파악
  4. 테일러 급수를 활용하면 함수(특히 삼각함수, 지수함수, 로그함수와 같은 초월함수)의 점근적 특성을 손쉽게 파악할 수 있습니다. 예를 들어, 아래와 같이 x = 0 근처에서 \sin x \simeq x 임을 테일러 급수를 이용하면 쉽게 알 수 있습니다.

    \lim\limits_{x \rightarrow 0} \dfrac{\sin x}{x} = \lim\limits_{x \rightarrow 0} \dfrac{x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \cdots}{x} = 1

  5. 문제 또는 모델의 단순화
  6. 테일러 급수의 가장 일반적인 활용예로 볼 수 있습니다. 즉, 어떤 복잡한 또는 잘 모르는 함수가 있을 때, 이 함수를 저차의(1~3차) 다항함수로 근사하여 사용함으로써 문제 또는 모델을 단순화시키는데 테일러 급수가 활용될 수 있습니다. 구체적인 예를 들기는 어렵지만 테일러 급수는 논문 등에서 어떤 이론이나 주장에 대한 논리적 근거를 단순화하여 설명할 때 유용하게 사용되는 기법 중의 하나입니다. 한 활용예로 가우스-뉴턴(Gauss-Newton) 방법을 증명하는데 테일러 급수가 활용됩니다. 이에 대한 내용은 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton’s method)을 참조하기 바랍니다.

  7. 기타 활용예
  8. 테일러 급수는 미분방정식을 풀 때, 또는 초월함수의 함수값을 계산할 때도 활용될 수 있습니다. 예를 들어, 미분방정식 y' = y, y(0) = 1yy = a_0 + a_1x + a_2x^2 + \cdots 라 놓고 풀면 y(0) = 1에서 a_0 = 1, y' = y에서 a_1 + 2a_2x + 3a_3x^2 + \cdots = a_0 + a_1x + a_2x^2 + \cdots이 됩니다. 즉, a_1 = a_0 = 1, a_2 = a_1/2 = 1/2, \cdots 이런 식으로 y를 구할 수 있겠죠. 참고로, 이렇게 구한 ye^x를 테일러 전개한 식과 같습니다. 다른 예로, \sin x의 값을 컴퓨터로 계산한다고 했을 때, \sin x = x - \dfrac{x^3}{3!} + \dfrac{x^5}{5!} - \cdots 와 같이 테일러 급수를 이용하여 함수값을 계산하면 몇 번의 계산만으로도 매우 정밀한 결과값을 얻을 수 있습니다.

등이 있다.

이건 아주아주 예전부터 들어왔지만, 정확한 이해가 되지 않았는데… 이제서야 정리가 되었다.


update 2014.05.07
이제까지는 1D 테일러 시리즈를 보았다. 이를 2D 로 확장시키기 위해 식 (2) 를 약간 변형시켜 보겠다.

f(x_0 + \Delta x) = \sum\limits_{n=0}^{\infty} \dfrac {f^{(n)}(x_0)}{n!} \, {\Delta x}^{n} (3)

근본적으로 달라지는 것은 없다. xa 근처에서 성립하는 것만 인지하고 있다면 쉽게 이해할 수 있다. 꼭 찝에서 넣자면, x_0 =a 이고, \Delta x = (x - a)이다.

자 이제 테일러 시리즈를 2D 로 확장해보자. 기본적인 2D 형태의 함수는 식 (4) 와 같다. 이걸 이야기하기가 애매해서 식 (3)을 적은 것이다.

f(x_0 + \Delta x, y_0 + \Delta y) (4)

위 식에서 f는 2차원 함수이며, \Delta x\Delta y는 0 에 한없이 가까운 값이다. 이것을 테일러 시리즈로 확장하기 위해서 약간의 수학적인 트릭이 더해진다.

g(t) = f(x_0 + t \Delta x, y_0 + t \Delta y) (5)

x_0, y_0, \Delta x, \Delta y를 상수로 생각하면, g함수는 t변수만을 가진 1차원 함수로 쓸수가 있다. 여기에서 t_0 = 0으로 두고 \Delta t = 1로 두면, 1D 테일러 시리즈로 확장할 수 있는 형태가 된다. 이를 다시 정리하면,

g(t) = f(x(t), y(t)) (6)
where, x(t) = x_0 + t \Delta x, y(t) = y_0 + t \Delta y

식 (6) 은 1D 테일러 시리즈로 확장할 수 있는 형태가 되었다. 이제 필요한 것은 g(t)\big\rvert_{t=0}에서 미분가능한지 여부와 미분값을 확인하면 된다. \dfrac{\mathop{d}}{\mathop{dt}}x(t) = \Delta x 이고, \dfrac{\mathop{d}}{\mathop{dt}}y(t) = \Delta y 이므로,

\begin{array}{rcl} \dfrac{\mathop{d}}{\mathop{dt}}g(t) & = & \dfrac{\partial }{\partial x}f(x(t), y(t)) \dfrac{\mathop{d} }{\mathop{dt}}x(t) + \dfrac{\partial }{\partial y}f(x(t), y(t)) \dfrac{\mathop{d} }{\mathop{dt}}y(t) \\ \\ & = & f_x(x(t), y(t))\Delta x + f_y(x(t), y(t))\Delta y \\ \\ \dfrac{\mathop{d}^2}{\mathop{dt}^2}g(t) & = & f_{xx}(x(t), y(t))\Delta x^2 + 2f_{xy}(x(t), y(t))\Delta x\Delta y + f_{yy}(x(t), y(t))\Delta y^2 \end{array}

3차 이상의 미분항은… 거의 쓸일이 없으므로 생략한다. 자 이제 마지막으로 정리를 하면,

\begin{array}{rcl} f(x_0 + \Delta x, y_0 + \Delta y) & = & g(t_0 + \Delta t)\bigg\rvert_{t_0=0, \Delta t=1} \\ \\ & = & g(0) + g'(0) + \frac{1}{2}g''(0) + \cdots \end{array}

(7)

식 (7) 로 간단하게 정리가 되며, 이 결과로 얻어지는 2D 테일러 시리즈는 식 (8) 과 같다.

\begin{array}{rcl} f(x_0 + \Delta x, y_0 + \Delta y) & = & f(x_0, y_0) \\ \\ & + & f_x(x_0, y_0)\Delta x + f_y(x_0, y_0)\Delta y \\ \\ & + & \frac{1}{2}\left[f_{xx}(x_0, y_0)\Delta x^2 + 2f_{xy}(x_0, y_0)\Delta x\Delta y + f_{yy}(x_0, y_0)\Delta y^2 \right] \\ \\ & + &\cdots \end{array}

(8)
참고

Written by gomiski

2014/05/01 at 3:43 pm