I love brew

2.Gaussian Smoothing Insight with Gaussian smoothing 가우시안 필터 빠르게 실행하기. Gaussian Filter g ( i , j ) = 1 2 π σ 2 × exp ⁡ − ( i 2 + j 2 ) 2 σ 2 g(i,j) = \frac{1}{2\pi\sigma^2}\times\exp^{-(i^2 + j^2)\over2\sigma^2} g ( i , j ) = 2 π σ 2 1 ​ × exp 2 σ 2 − ( i 2 + j 2 ) ​ 가우시안필터의 특징은 i, j = (0, 0)일 때 가장 큰 값을 갖고 원점에서 멀어질 수록 점점 함수값이 작아진다. Gaussian Smoothing 이를 사용해서 가우시안 필터를 이미지에 컨볼루션을 적용해주면 필터링이 가능해지는데 식은 다음과 같다. 1. 2. 식을 분리할 수 있다. 2차원 필터보다 빠른 1차원 필터 2차원 필터는 참으로 느리다. 1번 식에서 사용하는 필터는 2차원 필터로 한번 컨볼루션을 하는데 총 O(n x m)의 복잡도가 필요하다. 컨볼루션이 항상 그런것처럼 당연하다고 여길 수 있는데 재미있는 건 계산을 훨씬 더 줄일 수 있다는 것이다. 이미지의 사이즈가 PxQ 이고 필터의 사이즈가 m, n라고 해보자. 1번 과정은 약 PQmn의 시간이 필요할 거다. 1차원 수평 필터는 행에 따라서 값이 달라질 필요가 없다 는 사실을 기억하자. 2번 식을 살펴보면 exp ⁡ − n 2 2 σ 2 \exp^{-n^2\over{2\sigma^2}} exp 2 σ 2 − n 2 ​ 이고 이는 다음과 같은 1차원 필터이다. 이 1차원 수평 필터를 적용해서 계산한 후에 시그마로 합쳐주면 하나의 스칼라 값이 나온다. PQ의 이미지 사이즈에 1차원 가우시안 필터와 컨볼루션을 계산하는데 드는 시간은 PQn이 들 것이다. 1차원 수평 필터의 값은 행에 따라서 변하지 않기 때문에 우리는 재 계산할 필요없이 PxQ개의 값들...

Halting Problem Halting problem Halting problem 이란 홀팅 문제란 어떤 프로그램과 입력을 받았을 때, 그 프로그램을 실행했을 때 유한한 단계 후에 끝날지 혹은 영원히 끝나지 않을지를 판별할 수 있는 일반적인 방법이 있을까를 다루는 문제입니다. 왜 중요할까 결론을 먼저 말하자면 홀팅 문제를 푸는 알고리즘은 없습니다. 홀팅 문제는 최초로 풀지 못하는 문제로 증명되었다는 점에서 의미가 있습니다. 증명법 증명을 위해 홀팅 문제를 풀 수 있는 알고리즘 이 있다고 하나의 가정을 세우겠습니다. 해당 가정이 모순임을 밝히면 귀류법에 의해서 증명이 끝나겠죠. a : 사용될 임의의 프로그램 i : 사용될 임의의 입력 exit(a, i) : Boolean = if a(i) executed in finite time then true else false // a(i)의 exit 함수는 프로그램 a와 입력 i를 받아 a(i) 프로그램이 유한 시간에 종료되면 true를 프로그램이 영원히 돌면 false를 반환하는 함수라고 해보겠습니다. 즉 홀팅 문제를 판별하는 알고리즘 입니다. subroutine(s) : Boolean = if exit(s, s) == false then true else infinite loop s : 프로그램을 입력으로 받을 수 있는 프로그램. subroutine 함수는 s라는 프로그램을 입력으로 받습니다. 그리고 exit(s, s)을 실행해 결과가 거짓이면 참으로 프로그램을 끝내고, 참이면 무한 루프를 돕니다. 즉 exit(s, s)의 결과값을 거꾸로 내보낸다는 걸 알 수 있습니다. 프로그램을 입력으로 받는 프로그램 s 가 어떤 것이 있을까 싶을 수 있습니다. 주변의 함수를 생각해보면 함수를 입력으로 받는 함수도 있지만, 컴파일러를 떠올릴 수 있습니다. 컴파일러 프로그램은 다른 프로그램을 받아 오류가 있는지 확인해주죠. s(s) 라고 ...

컴퓨터는 단지 숫자다 :: 2. 부동 소수점 반올림과 Rounding 컴퓨터는 단지 숫자다 :: 근사와 Rounding 부동 소수점 표현법 이전 포스팅 보기 서론 프로그래밍 언어는 어떤 언어든지 완전하지 못하다. 이번 파트에서는 프로그램 언어가 가지는 태생적인 결함 중에서 근사에 대한 얘기를 해보려고 한다. 플라톤은 자신의 철학 사상을 얘기하면서 '이데아’를 주장하였다. 사람이 그린 어떤 삼각형도 모든 내각의 합이 결코 정확한 180도가 될 수 없지만 세상 밖에서는 모든 내각의 합이 정확히 180도인 삼각형의 원형이 존재한다는 사상이었다. 컴퓨터마저도 수를 표현함에 있어 '이데아’를 실현하지는 못한다. 예를 들어 0.1이라는 수를 컴퓨터는 정확히 표현할 수 없어 0.10000000000000000555111512... 이라는 값으로 저장한다. 정밀도에 따라 32비트 혹은 그 이상이 될 수 있겠지만 중요한 것은 컴퓨터도 때로는 정확한 값을 저장할 수 없다는 말이다. 이러한 오차는 별 것 아니라고 생각할 수 있겠지만 제대로 컨트롤 하지 못하는 수의 오차는 생각보다 심각한 문제를 일으키기도 한다. 1991년 2월 25일 1차 걸프 전쟁 기간중 사우디아라비아 Dharan에 위치한 미국 패트리엇 미사일 부대는 날아오는 이라크의 스커드 미사일을 격추하는 데 실패해 28명의 대원이 사망 했다. 미국 조사위는 이 실패에 관해 상세한 조사를수행한 결과 수치 계산의 부정확성이 주요 원인이라는 결론을 내렸다. 패트리엇 시스템은 내부적으로 0.1초마다 증가하는 카운터가 있었고 0.1초를 내부적으로 24비트에 저장해 근사값으로 더하고 있었다. 이 때 0.1초의 오차는 2 − 2 0 × 1 1 0 2^{-20}\times{1\over10} 2 − 2 0 × 1 0 1 ​ 이었고 약 100시간동안 패트리어트 시스템이 동작하고 있었고 스커드 미사일이 2000m/s로 날아오고 있었다. 그 결과 격추 시스템의 오차는 약 6...

Markov Process Markov Chain 마르코브 체인(MC)은 여러 개의 state들의 연결관계로 이루어진 그래프이다. MC의 state의 개수는 유한할 수도 있고 무한 할 수도 있다. State of chain Markov chain의 여러가지 상태의 정의에 대해서 알아보자. state란 다음 두 가지 의미 모두 쓰여 햇갈릴 수도 있다. Markov chain의 가장 작은 구성 요소이다. state i i i 는 그래프의 하나의 노드로 생각하면 된다. state와 chain의 상태를 다룬다. 다음에 배울 Communicate는 state i i i 와 j j j 간의 상태를 의미하기도 하며 chain의 상태를 의미하기도 한다. Accessible state i i i 는 state j j j 에 대해서 accessible : if 어떤 양수 n n n 에 대해서 P i , j n > 0 P_{i, j}^n > 0 P i , j n ​ > 0 을 만족한다 state i i i 가 state j j j 에 대해서 accessible하고 state j j j 가 state i i i 에 대해서 accessible하다면 communicate라고 한다. Communicate 두 state i , j i, j i , j 간에 이동할 수 있는 경로가 있다면 두 state가 commnicate하다고 말한다. communicate란 개념은 state들을 구분된 집합으로 나누게 되는데 집합 내의 모든 state간에 communicate하다면 그 Markov Chain을 communicate class라고 한다. 만약 A 클래스에서 B 클래스로 가는 경로가 있다면 A 클래스에서 B클래스로 이동하는 것은 가능하나 이 경우 다시 A클래스로는 돌아갈 수 없다. B클래스에서 A클래스로 갈 수 있다면 A와 B간에 communicate 성질을 만족하기 때문에 구분된 집합이 아니게 되기 때문...