살군의 보조기억 장치

Another memory device…

Archive for the ‘study’ Category

매번 햇갈리는 UML 정의

leave a comment »

매번 햇갈리는 UML 정의가 있다. 바로 Aggregation과 Composition의 차이 이다.

  • Aggregation: 전체와 부분의 연관 관계를 맺지만, 그러나 동일한 생명 주기를 갖지는 않는다.
  • Composition: 전체와 부분이 강력한 연관 관계를 맺으며, 전체와 부분이 같은 생명 주기를 갖는다.

Aggregation 의 예로는, Person-Address 관계가 있을 수 있다. 역사과목-학생의 관계 또한 aggregation 이라고 볼 수 있다. Composition 의 예로는 Car-Engine 관계가 있다. House-Room 도 가능하다. 이젠 햇갈리지 말자

참고
Advertisements

Written by gomiski

2014/11/05 at 6:14 am

Posted in General, Lecture, Life, study

Tagged with , ,

Trac 설치 방법

leave a comment »

예전에 Trac 을 설치해서 사용했던 적이 있었는데, 한동안 안쓰다가 다시 쓰려니 하나하나 다시 찾아봐야 되서 정리를 하기로 마음먹었다. Trac 은 파이썬 기반이므로 일단 파이썬을 설치해야 한다.

  1. 파이썬 ≥ 2.5 and < 3.0 설치
  2. 파이썬 홈페이지에 가서 설치를 하면 되는데, 주의할 점은 파이썬은 3.x 버전부터 문법이 달라져서 2.x 대 버전과 호환성이 없어져버렸다. 근데 Trac 은 2.x 기반으로 만들어졌으므로 3.x 버전을 설치하면 안된다. 파이썬 홈페이지에 가도 2.x 와 3.x 를 따로 다운 받을 수 있도록 해놨으니, 2.x 버전의 최신판으로 다운 받아서 설치하면 된다.

  3. setup_tools ≥ 0.6 설치
  4. 좀 전까지 설치한게 이건데… 애매하지만 간단하게 설명하면, setup_tools 다운로드 페이지에 가서 아래로 내리면 “Windows (simplified)” 항목에서 시키는 대로 “ez_setup.py” 파일을 다운 받아서 파이썬으로 실행시키면 된다. 파이썬으로 파일을 실행하는 방법은,

    python ez_setup.py

    라고 하면 된다. 그럼 알아서 다운 받고 설치도 된다.

  5. Genshi ≥ 0.6 설치
  6. 나머지 Mendetory 패키지인 Genshi 는 setup_tools 에서 지원하는 easy_install 을 이용해서 쉽게 설치할 수 있다. 위의 2.를 제대로 설치했다면, 파이썬 디렉토리 안에 Scripts 라는 디렉토리가 생겼을 것이다. 여기 들어가면 easy_install.exe 파일이 보인다. 이걸로 아래와 같이 실행하면 끝.

    easy_install Genshi

  7. 파이썬 DB 바인딩 설치
  8. 홈페이지에서 권고하는데로 PySqlite 를 다운 받을려고 보니, 파이썬 2.5 버전 이상에서는 PySqlite 2가 sqlite3 모듈로 기본 DB 바인딩으로 들어가 있다고 한다. 굳이 다운 안받아도 되겠다.

  9. Trac 설치
  10. 자! 이제 준비가 다 되었으니 Trac 을 설치해보자. 설치 방법은 간단하다. easy_install 이 있는 파이썬 디렉토리 내의 Scripts 디렉토리에 들어가서,

    easy_install Trac==1.0

    을 실행하면 된다. 그러면 Scripts 디렉토리 내부에 trac 과 관련된 파일이 생성된 것을 볼 수 있다.

  11. 프로젝트 생성
  12. 나는 아파치 서버를 따로 안 쓸 예정이므로, 그냥 trac 에 내장된 tracd 를 돌려서 사용한다. 일단 여기까지 하면 trac 이 실행되는 환경까지 왔다. 처음 설치한 파이썬의 하위에 있는 Scripts 디렉토리에 보면 trac 과 관련된 파일들이 생성되어 있을 것이다. 이제 프로젝트를 한번 등록해보자. Scripts 디렉토리에서

    trac-admin /path/to/myproject initenv

    을 실행하면, /path/to/myproject 라는 디렉토리가 생성되고 trac 이 초기화 되었다. 이제 tracd 를 이용해서 실제 trac 을 돌려보자.

    tracd –port 8000 /path/to/myproject

    이제 웹브라우저에서 http://localhost:8080 으로 접속하면 trac 페이지가 보이고 프로젝트로 갈 수 있을 것이다.

  13. 관리자 계정 등록
  14. 첨에 들어가면 아무것도 할 수 없다. 그냥 trac 이 잘 돌아간다는 것만 확인할 수 있다. 이제 관리자 계정을 부여받자. 일단 tracd 를 멈추고 난 후,

    trac-admin /path/to/myproject permission add admin TRAC_ADMIN

    명령어를 입력하고 난 후, 다시 tracd 를 실행해서 웹브라우저로 들어가보면 우측 상단에 “Admin” 혹은 한글로 “관리” 라는 탭이 생겼을 것이다. 이제 관리자 계정으로 접속이 가능하다. 로긴도 없이 말이지…ㅋ

  15. 계정관리 플러그인 설치
  16. 이것저것 복잡하게 계정관리하는 뭔가가 나오는데… 복잡하다. 그렇다고 계정관리를 안할 수는 없으니, 편하게 관리해주는 툴을 찾아보자. 바로 Account Manager Plugin 이다. svn 이 설치되어 있다면 easy_install 로 간단하게 설치가 가능하다.

    easy_install https://trac-hacks.org/svn/accountmanagerplugin/tags/acct_mgr-0.4.4

    그러나 나는 아직 svn 이 설치되어 있지 않으니 일단 소스를 다운 받아서 압축을 푼 다음 acct_mgr-0.4.4 디렉토리에 들어가서 (들어가면 setup.py 파일이 보일거다),

    python setup.py bdist_egg
    cd dist
    easy_install TracAccountManager-0.4.4-py2.7.egg

    를 실행하면 된다. 단, 이때 tracd 를 종료한 상태에서 실행해야 한다. 당연한 이야기다.이제 다시 tracd 를 실행해서 “Admin” 탭에 Plugins 에 들어가보면 trac account manager 가 설치되어 있을 것이다. 이걸 열어서 모두 enable 채크! 그럼 왼쪽에 Account 관리기능이 생긴다. 대단히 대단하다!

끝으로… trac 을 설치하고 프로젝트를 생성하고 나면 안에 여러 디렉토리가 있다. 이 가운데,

    site/ – htdocs/ 의 복사본. 고로 메시지 로그상에 site/ 에 파일이 없다고 나온다면 htdocs/ 에 넣어주면 된다.
    common/ – trac 에서 관리하는 static resource
    <plugin>/ – 플러그인 별로 하나씩 생기는 디렉토리로 플러그인 환경설정에서 관리하는 디렉토리 들이다.

2014-10-21 추가

  1. mscgen 플러그인 설치
  2. mscgen 은 sequence diagram 을 그려주는 것이다. websequencediagram 플러그인을 써 보려고 했는데 Genshi 에서 UnicodeError 라면서 안되길래 그냥 포기하고 예전에 써봤던 경험이 있는 mscgen 으로 바꿨다. 설치방법은 다른 것들과 동일하다. 파이썬으로 빌드해서 egg 파일을 trac/plugin 디렉토리에 집어넣으면 trac 에서 자동으로 인식한다. 다만… 빌드할 때, 주의할 사항으로 mscgen 의 위치와 mscgen 으로 생성되는 이미지 캐시들이 저장될 위치를 하드코딩해넣어야 한다. 소스의 mscgen.py 파일을 살펴보면,

    	def __init__(self):
    		self.cache_dir = "%s\mscgen_cache" % (self.env.path)
    		self.proc_path = "D:\PATH_TO_MSCGEN\mscgen.exe"
    		self.proc_opts = ""
    		self.log.info('version: %s - id: %s' % (__version__, str(__id__)))
    

    하일라이트 된 줄을 내 환경설정에 맞게 하드코딩 해 넣어야 한다. 여기서 %s 는 현재 trac 이 설치된 디렉토리를 말한다. 나는 윈도우 기반으로 간단하게 설치한 것이라 mscgen.exe 파일을 사용하는 것을 볼 수 있다. 42번 라인인 캐시 디렉토리의 경우, 상대경로로 지정이 가능한데, mscgen 실행파일이 저장된 디렉토리는 절대경로로 지정해야 한다. 나는 D 드라이브에 실행파일이 있으므로 D:\PATH_TO_MSCGEN\mscgen.exe 로 지정했다. 완료되면 trac 안에서 아름다운 sequence diagram 을 쉽게 만들고 편집할 수 있다 🙂

2014-11-04 추가

  1. PlantUML 플러그인 설치
  2. PlantUML 은 UML 제작툴이다. 위에 있는 mscgen 은 sequence diagram 만 제작해주는데, 이걸로는 다양한 표현이 어려워서 새로운 플러그인을 찾아보니 좋은게 있어서 설치했다. 의외로 잘 동작한다. 설명페이지에는 linux 기반의 설명밖에 없지만, PlantUML 이 java 기반으로 만들어져있어 윈도우 환경에서도 잘 동작한다. 자… 일단 메뉴얼에서 시키는데로 dependency 들을 설치한다. 여기서 주의할 점은 ​Graphviz의 환경변수를 등록하고 path를 지정하는 것이다. 일단 테스트를 위해서 윈도우 커맨드 창에서,

    set GRAPHVIZ_DOT=C:\path\to\dot.exe

    이렇게 등록을 하면 일단 테스트는 가능할 것이다. 그러나 매번 새로 부팅할 때마다 다시 설정해줘야하니 환경변수 설정에서 등록을 해놓으면 간단하게 해결할 수 있다. 그리고 끝으로 trac.ini 파일에서

    [plantuml]
    plantuml_jar = /path/to/plantuml.jar
    java_bin = /path/to/java_bin (optional, if Java binary is not on the search path)

    위의 설정을 추가해주면 된다. 완료되면 trac 안에서 mscgen 보다 더 아름다운 sequence diagram 을 쉽게 만들고 편집할 수 있다 🙂

참고

Written by gomiski

2014/10/07 at 7:27 am

영상처리에서 미분과 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 에 가우시안 필터 계수를 넣으면 되는 것이다.

참고

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

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

아… 길었다 😉

참고

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