살군의 보조기억 장치

Another memory device…

Archive for April 2014

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

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것과 동일하게 해석될 수 있다는 것이 정말 대단하지 않은가! 나는 아마 죽었다 깨어나도 생각못할 것 같은 발상이다 ㅎㄷㄷ;;;

참고

Written by gomiski

2014/04/24 at 2:17 pm

잘 만든 소스코드란?

leave a comment »

흔히들 말하는 “잘 만든 소스코드란 무엇인가?” 에 대한 스크랩이다. 이 글을 본 지는 엄청 오래됐는데, 한번 봐야지 하면서 계속 미루고 미루다 결국 메일함의 한쪽구석에서 계속 방치되고 있어서 이리로 옮겼다. 둠3 소스코드 공개는 꽤 오래전에 있었던 이벤트였는데… 존 카막 이 냥반이 지금은 오큘러스 리프트의 CTO 로 옮겨가서 오큘러스에 대한 기대감이 급 상승되고있다. 그걸 반영하듯 얼마전에 오큘러스를 페북에서 낼름 사버리는 빅뉴스가 발표되었고. 제품이 시장에 나오면 게임내의 사용자 인터페이스가 엄청나게 바뀌게 될 가능성이 아주높아 보인다.
그치만 실제로 이걸 착용하고 하프라이프2 를 돌려보니 무진장 어지럽더라. 내가 기기에 적응을 해야되는건가?…;;; 여튼, 오늘은 The Exceptional Beauty of Doom 3’s Source Code 꼭 읽어봐야지.

Written by gomiski

2014/04/16 at 6:18 am

맥 원격접속 단축키

leave a comment »

여기를 참고했다.
Finder 창에 포커스를 두고, command + K
주소를 치면 접속 끝.

보안을 위해 원격접속의 환경설정에서 “항상 보안연결” 을 하면 좀 더 보안이 강화된 원격접속이 가능하다.

Written by gomiski

2014/04/10 at 1:18 am

Posted in Life, Memories

Tagged with , ,

첫번째 커밋 closed

with one comment

처음으로 한 커밋이 closed 됐다. 아쉽지만 merged 되진 않았고, 내가 닫았다. 내가 한 커밋을 할당받은 담당자가 그대로 놔두자라고 한 것이 제일 크고, 그 이유가 binary compatibility 때문이였다. binary compatibility이진 호환성 문제는 아무래도 major 버전 변환이 일어나기 전에 이제 정리되는 버전에서 중요하지도 않은 기능 때문에 호환성을 깨면서까지 바꾸기엔 의미가 없었던 듯 하다. 내가 봐도 맞는 이야기이고. 일단 전체 프로세스를 한번 거쳤다는 것에 의의를 둬야 되겠다.

그리고 나도 잘 몰랐던 binary compatibility 란 것에 대하 찾아봤다. 깊게 들어가면 플랫폼이나 os 에 따라 요구사항도 다르고 내가 지금 이걸 확인할 사항은 아니므로, 이 정도면 대충 감을 잡겠다 싶은 정도까지만 알아보자. 우선 정의를 보면,

Definition

A library is binary compatible, if a program linked dynamically to a former version of the library continues running with newer versions of the library without the need to recompile.
If a program needs to be recompiled to run with a new version of library but doesn’t require any further modifications, the library is source compatible.

Binary compatibility saves a lot of trouble. It makes it much easier to distribute software for a certain platform. Without ensuring binary compatibility between releases, people will be forced to provide statically linked binaries. Static binaries are bad because they

  • waste resources (especially memory)
  • don’t allow the program to benefit from bugfixes or extensions in the libraries

In the KDE project, we will provide binary compatibility within the life-span of a major release for the core libraries (kdelibs, kdepimlibs).

새로 컴파일 안하고 그대로 라이브러리를 그대로 교체해서 사용할 수 있는것이다. 조건이 대략 까다롭다. 외부 인터페이스는 전혀 건드리지 말아야 된다는 소리다. 인터페이스와 관련해서 binary compatibility 를 이야기할 때 빠지지 않는 ABI, API, interface 에 대한 내용을 살펴보면,

  • ABI – Application Binary Interface. The binary interface between systems. If a binary interface changes, both sides of the interface (the user and the implementation) must be recompiled.
  • API – Application Program Interface. The source interface between systems. If a source interface changes, code that uses that interface must be modified. API changes usually imply ABI changes.
  • Interface – A class where every method is pure virtual, and thus has no inherent implementation. An interface is merely a protocol for communication between objects.
  • Factory – Something that creates objects. In this article, we’ll use a single global function as our factory.
  • DLL Boundary – The line between code instantiated in a DLL and code in a calling process is called the DLL boundary. In some cases, code can be on both sides of the boundary: Consider an inline function in a header file that gets used in the DLL and the executable. The function is actually instantiated on both sides of the boundary. Therefore, if the inline function has a static variable, two variables will be created, one in the executable and one in the DLL, and which is used depends on whether the code in the DLL or the executable is calling the function.

물론 처음에 인용한 내용은 전반적인 binary compatibility 에 관한 이야기이고, 아래 인용한 내용은 이 가운데 windows 기반에서 binary compatibility 를 지키기 위해 고려해야 될 사항들을 정리한 것이다. 처음에 언급한 것 처럼, binary compatibility 는 플랫폼, os 등등에 따라 달라진다는 것만 생각한다면 쉽게 이해가 된다.

이 문제 때문에, 이번 커밋은 반영되지 못하고 그냥 닫혔다. 하나 배웠으니까… 다음에는 더 잘하겠지. 🙂

참고

Written by gomiski

2014/04/08 at 5:53 am

클래스 생성자 사용시 warning 문제

leave a comment »

아래글에서 언급한 것 처럼, 처음 커밋하고 build bot 에서 에러가 났을 때, 조금 당황했다. opencv 가 멀티플랫폼에서 돌아가기 때문에 linux 나 mac, android 까지 빌드를 하는데 에러가 난 부분이 linux 와 android 컴파일에서 났기 때문이다. 이거 linux 랑 android 설치를 해야되나… 잠깐 고민을 했다. 다행히 빌드로그가 잘 나와있고 문제점을 구글링 해서 처리할 수 있었다.

두 가지 문제가 있었는데, 그 가운데 하나가 바로 클래스 생성자 사용시 생길 수 있는 문제이다. 이게 왜 문제가 되는지는 아직 모르겠지만, 혹시 이러한 문제를 만나더라도 심각하게 고민하지는 않아도 된다. 단순한 룰만 지켜주면 쉽게 해결할 수 있기 때문이다.

class A
{
    int i, j, k;
    A(int a, int b, int c) : i(a), k(c), j(b) {}
}

위의 line:4 에서 warning 이 발생한다. 이유인즉,

주의할 것은 초기화 순서는 초기화 리스트의 순서가 아니라 멤버 선언 순서로 되는데, 경우에 따라 이들 차이로 인해 미묘한 문제가 발생할 수 있기 때문에 경고를 주는 것입니다.
멤버 선언 순서와 초기화 리스트의 순서를 일치시키는 것이 바람직한 스타일입니다.

라는 것이다. 따라서 생성자를 아래와 같이 바꿔주면 해결할 수 있다.

    A(int a, int b, int c) : i(a), j(b), k(c) {}

평소에는 신경도 안쓰던 것들이 멀티플랫폼의 대규모 프로젝트에서는 민감하게 처리되는 듯 하다.

참고

Written by gomiski

2014/04/03 at 10:36 am

Posted in C++, General, Lecture, opencv, study

Tagged with , , ,

첫번째 커밋. 그리고 fail…

with one comment

드디여 opencv community 에 처음으로 커밋을 했다.
나름 고민고민해서 올렸는데…

두둥!!!
build bot 에서 fail 이 떳다.
뭐가 문제인지 찾아볼려고 하니… 잉? 로그를 못찾겠네. 제일 좋은건 github 에서 commit 한 번호 옆에 떠 있는 마커를 클릭하면 빌드봇의 현재 상태를 알 수 있다. 아니면 여기에서 볼 수 있다.

일단은 fail 먹었으니… 로그보고 고쳐야지.

update
두번의 추가 커밋으로 build bot 에서 발생하는 에러는 다 잡았다. 이제는 under review 상태! 크흐흐.

Written by gomiski

2014/04/03 at 7:35 am

Posted in Life, Memories, opencv, study

Tagged with , , , ,