살군의 보조기억 장치

Another memory device…

Scale-space theory 정리

leave a comment »

Scale-space theory 라는 것은 sift 알고리즘을 구성하는 핵심요소 중 하나로써, sift 의 scale-invariant 특성을 제공하는 것이다. 일단 scale-space theory 의 개념에 대해 살펴보자.

Scale-space theory 는 다양한 형태의 multi-scale representation 에 대한 연관관계를 정리해서 하나의 이론으로 정립한 것이다. 이러한 scale-space representation 이 나타난 이유는 실세계real-world에서 관측observation되는 데이터들data set이 서로 다른 스케일scale에서 다른 형태 혹은 구조structures를 보이는 특징을 보이기 때문이다. 이는 실세계의 물체는 이상적인 수학세계의 점points이나 선lines과 달리 관측하는 스케일에 따라 다르게 보인다는 것을 의미한다. 예를들어 “나무”를 관측하는데는 미터meter 단위의 관측이 적당하지만, 잎사귀나 분자를 관측하는데는 더욱더 정밀한 단위가 필요하다. 하지만 Computer vision 에서 어떤 scene 을 분석한다고 할 때에는, 주어진 이미지에서 관심을 가질 만한 구조를 찾기 위해 어떤 스케일이 적합할지를 알 수 있는 사전정보priori를 알 수 있는 방법이 전혀 없다. 그러므로 다양한 스케일에서 구조를 파악하는 것이 합리적인 접근방법이다. 즉, scale-space representation 은 가능한 모든 스케일을 고려하여 구조를 파악한다.

Multi-scale representation의 또 다른 쉬운 예로는, 지도를 생각해 볼 수 있다. 세계지도를 보면 우리나라의 형태나 수도를 찾을 수 있지만, 고속도로나 다른 도시들을 모두 표시하지는 않는다. 세계지도에서 우리나라만 확대하면 우리나라의 주요 도시들과 고속도로가 나타나지만 내가 살고 있는 지역을 표현할 만큼 상세하지는 않다. 이렇게 크기에 따라 나타낼 수 있는 구조 혹인 특징feature이 다르다. computer vision 에서 본다면 원본 이미지가 가장 상세하게 표현된 지도라고 볼 수 있다. 이를 점점 줌아웃 해가면서 멀리서 봤을 때의 구조나 특징을 뽑아내는 것이 multi-scale representation 의 기본이다. 여기에 몇가지 수학적인 방법을 동원하여 특수한 형태로 정의한 것이 scale-space theory 이다. 내가 보기엔 그렇다.

자… 그럼 실제 scale-space theory 내부를 한번 파헤쳐보자. 가장 단순한 1-D 의 scale-space representation은 다음과 같이 정의한다.

함수 f:\mathbb{R}\rightarrow\mathbb{R}가 있을 때 scale-space representation L은,

L:\mathbb{R}\times\mathbb{R}_+\rightarrow\mathbb{R}

로 정의되며, 이를 수식으로 표현하면,

L(x;t) = g(x;t)\ast f(x)

이 된다. 여기서 t\in\mathbb{R}_+는 scale parameter 이며, g는 gaussian 함수이다.

g(x;t) = \dfrac{1}{\sqrt{2\pi t}}e^{-\frac{x^2}{2t}}

위의 g는 일반적인 gaussian 과 약간 다르다. 일반적인 gaussian 은 아래와 같다.

\mathcal{N}(\mu,\sigma^2) = \dfrac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{\left(x -\mu\right)^2}{2\sigma^2}}

g\mathcal{N}과 다른점은 \mu=0 이고, t=\sigma^2로 치환한 것이다. 그리고 L의 초기값으로 “zero scale” 인 t=0 은 원본 이미지로 정의한다.

L(x;0) = f(x)

이는 직관적으로도 쉽게 이해할 수 있다. gaussian 에서 \sigma=0 이면 impulse response 가 되기 때문에 원래 신호가 그대로 나타나게 된다.

참고로 위의 식에서 나온 \mathbb{R}_+non-negative real number 이며, \mathbb{R}_+ \setminus\{0\}0 을 제외한 non-negative real number 이다. 처음에 논문을 살펴볼 때, 특별한 언급이 없어서 오타인가 했는데, 그게 아니였다. 아놔…;;;

이렇게 scale parameter t에 따라 원본 신호가 blur 되는 세트의 집합을 scale-space representation 이라 한다.

근데 “ g는 gaussian 인가?” 라는 의문이 생긴다. 다른 함수가 될 수도 있고 아니면 blur 해주는 다른 low-pass filter 도 있는데 반드시 gaussian 을 써야되는걸까? 이걸 답해주는 신의 한수가 바로 diffusion equation 이다. 이걸 발견한 Lindeberg 라는 분은 정말 천재다.

Scale-space 는 소스 시그널을 다룰 때, 새로운 extrema 를 생성하지 않아야 한다. 그리고 모든 스케일에서 동일한 방식으로 처리되어야 한다. 이부분이 좀 이해가 안된다. 자세한 내용은 원문을 참조하기 바란다. 원문에서 이와 관련된 부분만 발췌하면,

1.4.4. Uniqueness of the Gaussian
Later, when Koenderink (1984) extended the scale-space concept to two-dimensional signals, he introduced the notation of causality, which means that new level surfaces must not be created when the scale parameter is increased. Equivalently, it should always be possible to trace a grey-level value existing at a certain level of scale to a similar grey-level at any finer level of scale. By combining causality with the notions of homogeneity and isotropy, which essentially mean that all spatial points and all scale levels must be treated in a similar manner, he showed that the scale-space representation of a two-dimensional signal by necessity must satisfy the diffusion equation

diffusion eq.는 아래와 같다.

\dfrac{\partial u(x,t)}{\partial t} = D\nabla^2 u(x,t)

여기서 x는 거리이고 t는 경과시간이다. D는 확산계수diffusion coefficient로 매질마다 열을 전달하는 속도가 다른것을 표현한 상수라고 보면 된다.실제론 더 복잡하지만… 그리고 이 diffusion eq.의 솔루션은 다음과 같다.

u(x,t) = \dfrac{u_0}{2\sqrt{\pi D t}}e^{-\left(\frac{x^2}{4Dt}\right)}

어디서 많이 본 형태이지 않은가? 그렇다. 바로 gaussian 이다. 원문에서 언급한 것 처럼 scale-space representation 은 diffusion eq.를 만족해야 하므로 gaussian 이 unique 한 솔루션이 되는 것이다!

이것 역시 직관적으로 바라보는 것이 보다 쉽게 이해할 수 있다. 열역학 기준에서 본다면 시간이 흘러서 열평형(영상에서 본다면 bluring)이 이뤄진다고 볼 수 있지만, scale-space 기준에서 보면 gaussian 의 표준편차standard deviation에 따라 bluring 이 이뤄지는것이다. 즉 gaussian 의 \sigma값을 변경하는 것은 diffusion eq.의 시간t가 변하는 것과 동일한 효과를 준다. 다시말해, \sigma값을 변경함으로써 열역학의 시간흐름과 동일한 효과를 내는 것이다.

그리고 scale-space representation 에서의 scale parameter 는 t = \sigma^2 이다. 열역학의 diffusion eq.의 t는 시간을 의미한다. 그러나 신호의 관점에서 본다면 사실상 동일한 효과를 주는 coefficient 인 것이다.

이제 우리가 다루고자 하는 2-D 이미지 도메인에서의 정의를 살펴보자. fL이 2-D로 변하면 f:\mathbb{R}^2\rightarrow\mathbb{R} 이 되고, L:\mathbb{R}^2\times\mathbb{R}_+\rightarrow\mathbb{R} 이 된다. 수식으로 표현하면,

L(x,y;t) = g(x,y;t)\ast f(x,y)

diffusion eq.의 2-D는,

\dfrac{\partial u(x,y;t)}{\partial t} = D\nabla^2 u(x,y;t)

그리고 이 diffusion eq.의 솔루션인 gaussian 의 2-D는,

g(x,y;t) = \dfrac{1}{2\pi t}e^{-(x^2+y^2)/{2t}}

여기에는 1-D에서 보여준 것과는 약간 차이가 있다. 위 식은 Scale-space theory in computer vision 책에 있는 것을 그대로 옮겨온 것이다. 수학적인 증명은 위에서 언급한 Koenderink (1984) 을 참고하자. 사실 나도 안찾아봤다.

신호라는 관점에서 보면 영상이든 열이든 동일하게 취급하고 그리고 그 가운데서도 영상의 blur 되는 것을 열이 퍼져나가는diffusion것과 동일하게 해석될 수 있다는 것이 정말 대단하지 않은가! 나는 아마 죽었다 깨어나도 생각못할 것 같은 발상이다 ㅎㄷㄷ;;;

참고
Advertisements

Written by gomiski

2014/04/24 at 2:17 pm

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: