Month: May 2014

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

보통 엣지_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 에 가우시안 필터 계수를 넣으면 되는 것이다.

참고

Harris Corner Detector

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

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

$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)=$

위의 그림과 식 (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 은 아래와 같은 몇가지 문제를 안고 있다.

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

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

노이즈에 취약하다 – gaussian window function 사용

$w(x,y)=e^{-\frac{(x^2+y^2)}{2\sigma^2}}$	(2)
window function $w(x,y)=$

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

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

기존의 픽셀단위 이동으로는 엣지의 방향을 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)$ 를 고려한다.

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

~~이 부분은 아직 잘 이해가 안된다.~~ 개념적으로는 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)

$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

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

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

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

정적분_{definite integral}의 계산

부정적분_{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) 테일러 급수를 사용해도 근사오차가 크지 않습니다.

함수의 점근_asymptotic 특성 파악

테일러 급수를 활용하면 함수(특히 삼각함수, 지수함수, 로그함수와 같은 초월함수)의 점근적 특성을 손쉽게 파악할 수 있습니다. 예를 들어, 아래와 같이 $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$

문제 또는 모델의 단순화

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

기타 활용예

테일러 급수는 미분방정식을 풀 때, 또는 초월함수의 함수값을 계산할 때도 활용될 수 있습니다. 예를 들어, 미분방정식 $y' = y$ , $y(0) = 1$ 은 $y$ 를 $y = 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$ 를 구할 수 있겠죠. 참고로, 이렇게 구한 $y$ 는 $e^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)

근본적으로 달라지는 것은 없다. $x$ 가 $a$ 근처에서 성립하는 것만 인지하고 있다면 쉽게 이해할 수 있다. 꼭 찝에서 넣자면, $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)

참고