살군의 보조기억 장치

Another memory device…

Laplacian of Gaussian (LoG) approximation in SIFT

leave a comment »

자… 지난 포스트에 이어서 이번에는 scale space 를 왜 했는지를 확인해볼 차례다. scale-space 자체로만 봐도 개념적으로는 합당한 이야기다. 특히자 scale 에 대한 priori 가 없는 경우에는 당연히 합리적인 접근방법이라고 생각한다. 하지만 이번에는 좀 더 실질적인 부분에서 찾아보자.

제일 대표적으로 이용되는 부분이 아마 SIFT 알고리즘의 extrema 검출부분일 것이다. Lowe (2004) 의 논문을 살펴보면 scale-space 를 이용해서 feature 를 찾는 방법이 나온다.

\dfrac{\partial G}{\partial\sigma} = \sigma\nabla^2 G

얼핏 보기에는 문제가 없어 보인다. scale-space theory 에서 정의한 heat diffusion equation 을 그대로 가져와서 적용하되 diffusion coefficient 를 \sigma로 둔 것이다.

여기서 궁금증이 생긴다. 왜! diffusion coefficient 는 \sigma인 것일까? Lowe (2004) 의 논문에서도 true scale-invariance 를 위해서는 \sigma^2를 diffusion coefficient 로 해야한다고 적어놨다. 근데 어떻게 \sigma를 쓸 수 있는 것인지가 궁금해졌다. 이를 확인하기 위해 우선 Laplacian of Gaussian(LoG) 의 수식과 gaussian 의 미분형태를 보면,

LoG(x,y) = \nabla^2 G = \dfrac{1}{\pi\sigma^4}\left(\dfrac{x^2 + y^2}{2\sigma^2} -1\right)e^{-\frac{x^2 + y^2}{2\sigma^2}}

\dfrac{\partial G(x,y)}{\partial x} = \dfrac{1}{2\pi\sigma^2}\left(-\dfrac{x}{\sigma^2}\right)e^{-\frac{x^2 + y^2}{2\sigma^2}}

이게 다르다는 거다. 근데 어떻게 위에 있는 첫번째 수식이 성립할 수 있단 말인가?!

이것을 이해하기 전에 알아야 될 사항이, scale-invariance 란 무엇인가? 하는 것이다. 위키피디아는 scale invariance 를 아래와 같이 설명하고 있다.

In physics, mathematics, statistics, and economics, scale invariance is a feature of objects or laws that does not change if scales of length, energy, or other variables, are multiplied by a common factor.

요약하면, 특징feature이 (일반적인 요소의) 곱에 의해 변하지 않는다는 것이다. 난해하다…;; 다시 위의 식을 돌아보면, scale invariance 관점에서는 절대적인 값의 비교가 아닌 feature 가 불변한다는 점에서 식을 봐야한다는 것이다.

게다가 diffusion equation 역시 diffusion coefficient 는 물체의 매질에 열 전도율을 정의한 상수값이 되므로 영상처리에서는 사실상 어떤 상수가 와도 상관이 없다. 즉, SIFT 논문에서는 scale-space 에서부터 extrema 를 찾아내는detection 것이 목적이므로 그냥 등호(=)를 사용해버린 것이다. 이게 내가 이해한 방법이다. 절대적인 수치로는 도저히 등호를 그냥 붙일 수가 없다. 실제로 LoG 를 Difference of Gaussian(DoG) 로 approximation 할 경우, 값의 정확성 여부는 DoG 의 \Delta\sigma가 작을수록 정확해지는 것일 뿐이지 특정한 \sigma값이 더 정확해 지는 것은 아니다.

LoG approximation by DoG

LoG approximation by DoG

위 그림에서 보듯이 \Delta\sigma가 작을수록 LoG 에 근접한다. SIFT 에서 LoG approximation 역시도 절대적인 수치의 동일함으로 보는 것이 아니라 LoG 특성을 어떻게 이용할 것인가에 대한 것이다. 그 가운데서도 scale-space representation 을 얼마나 효율적으로 만들어내느냐 하는 문제, 다시말해 어느수준에서 trade-off 할 것인가에 대한 문제인 것이다. 그럼 Lowe (2004) 에서 LoG approximation 을 어떻게 이용했는지를 보자.

\sigma\nabla^2 G = \dfrac{\partial G}{\partial\sigma} \approx \dfrac{G(x,y,k\sigma) - G(x,y,\sigma)}{k\sigma - \sigma}

G(x,y,k\sigma) - G(x,y,\sigma) \approx (k-1)\sigma^2\nabla^2 G

위의 수식에서 LoG approximation 은 k가 1에 가까울 수록 정확해진다. 그러나 실제로는 k=\sqrt{2} 정도의 값에서도 extrema 는 안정적으로 검출된다고 Lowe (2004) 에서는 언급하고 있다.

그렇다면 이 k값을 어떻게 정해야 하는 것이냐. 이 부분이 바로 trade-off 문제가 된다. 이와 관련된 쉬운 설명을 아래에 인용했다. 요약하면, k값은 어느것으로 해도 상관이 없으나 1에 가까이 갈 수록 정확한 approximation 이 가능하다. 그러나 k가 작으면 작을 수록 충분한 octave layer 구성을 위해 더 많은 계산을 해야한다.

So the value of k is usually chosen so that you can calculate a series of gaussian filtered images with sigmas s, s*k, s*k^2, s*k^3…, and then calculate the differences between adjacent gaussians. So if you choose a smaller k, you’d have to calculate more “layers” of gaussians for the same sigma-range. k=1.6 is a trade-off between wanting a close approximation and not wanting to calculate too many different gaussians.

여기까지가 SIFT 에서 LoG approximation 을 어떻게 하는지에 대한 내용이다. 덤으로 실제 SIFT 에서는 어떤 방식으로 LoG 를 효율적으로 구현하였는지에 대한 내용을 살펴보자. 아래 내용은 Lowe (2004)의 일부 내용을 발췌한 것이다.

The initial image is incrementally convolved with Gaussians to produce images factor k in scale space, shown stacked in the left column. We choose to divide each octave of scale space (i.e., doubling of \sigma) into an integer number, s, of intervals, so k = 2^{1/s}. We must produce s+3 images in the stack of blurred images for each octave, so that final extrema detection covers a complete octave. Adjacent image scales are subtracted to produce the difference-of-Gaussian images shown on the right. Once a complete octave has been processed, we resample the Gaussian image that has twice the initial value of \sigma (it will be 2 images from the top of the stack) by taking every second pixel in each row and column. The accuracy of sampling relative to \sigma is no different than for the start of the previous octave, while computation is greatly reduced.

s는 각 octave 의 scale 크기를 지정하는 값이다. s=2로 두면 1st octave는 원본 이미지 그대로 사용하고 2nd octave는 가로세로가 1/2 로 줄어들고 3rd octave는 1/4로 줄어드는 식으로 octave 가 구성이 된다. 아래 표는 s=2, k=\sqrt{2} 일때, octave 에 따른 gaussian 과 DoG 의 \sigma값이다.

1st octave
Gaussian \sigma \sqrt{2}\sigma 2\sigma 2\sqrt{2}\sigma 4\sigma
DoG \sigma \sqrt{2}\sigma 2\sigma 2\sqrt{2}\sigma
2nd octave
Gaussian 2\sigma 2\sqrt{2}\sigma 4\sigma 4\sqrt{2}\sigma 8\sigma
DoG 2\sigma 2\sqrt{2}\sigma 4\sigma 4\sqrt{2}\sigma

표에서 보듯이 Gaussian 사이의 간격은 k값과 동일하고 DoG 간격 역시 k이다. SIFT 에서 실제 사용하는 DoG 결과물은 회색 음영처리를 한 것이다. 그리고 위의 논문발췌부분에서 언급한 연산량을 줄이기 위한 트릭은 octave 간의 \sigma값의 차이를 보면 쉽게 알 수 있다.

정말 마지막으로, gaussian kernel, 즉 이미지 필터의 크기는 gaussian 함수와 \sigma의 연관관계를 생각하면 쉽게 예상할 수 있다. 아래 그림에서 보듯이 gaussian 함수는 [-3\sigma, 3\sigma]구간이 전체 신호의 약 99.7% 의 정보를 담고 있다. 그러므로 6\sigma+1의 필터크기를 선정하면 된다.
gaussian bell-curve

아… 길었다 😉

참고
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: