작지도,크지도, 같지도 않다. -1.#IND

공부 2010.12.29 09:05
수치 계산을 하다보면 컴퓨터의 부동소수점 계산 오차때문에

a<b여야 하는것이 b<a 가 된다거나, 혹은 a==b가 되는 경우가 발생한다.


그런데 컴퓨터의 두 실수(float) a,b가
1. a<b
2. b<a
3. a==b

중에 어느것에도 속하지 않을 수 있을까?

정답은 yes 이다.



아래의 C++코드를 보자.
float  a=1.0, b=sqrt(-1.0);
if(a<b || a==b || b<a ) printf("OK.");
else printf("what happen? (%g)\n",b);


문제는 b=sqrt(-1.0)에서 발생한다.

b=sqrt(-1.0) 을 할경우, 음의 루트값이기 때문에 허수값이 나오고 float형인 b에는 담을 수 없다.

그래서 b에는 -1.#IND 값이 들어가게 된다.

IND는 indeterminate의 약자로 정해지지 않았다는 말이다.


양수, 음수를 0.0으로 나누었을때 보게되는 +-1.#INF (infinite,양/음 의 무한대)와는 다르게 -1.#IND은 크기가 없다.

문제되는것은 크기가 없기 때문에 <,>,==의 모든 비교에 대해서 false를 내놓는다는 것이다.

그래서 위의 코드를 실행하면 놀랍게도 if문을 통과해서 "what happend? (-1.#IND)" 을 보게된다.


(위 코드의 실행결과)


일반적으로는 위의 예제처럼 일부러 sqrt안에 음수를 넣을일은 없겠지만,

복잡한 수치계산을 하다보면, 이론상으로는 0이 될 수 없는 수식도 수치오차때문에 -0.0001 이 될 수도 있고,

그 수식이 루트(sqrt)안에 있다면 바로 -1.#IND이 뜨면서 이후의 루틴에서 많은것을 망쳐놓으므로 조심해야한다.


하다못해 수식의 결과를 소팅 하더라도, 원소중에 하나라도 -1.#IND가 섞여있다면

혼자만 문제가 생기는게 아니라, 소팅 전체 결과가 엉망이 되어버린다.
저작자표시

'공부' 카테고리의 다른 글

작지도,크지도, 같지도 않다. -1.#IND  (0) 2010.12.29
언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
Posted by youknow04
트랙백 9개, 댓글 0개가 달렸습니다

언어의 모호성

공부 2010.11.16 17:25
컴파일러 같이 굉장히 제한적인 포멧(소스코드)를 파싱할때에도 종종 모호성이 발생하곤 하는데,

최근에 MSRA에서 온톨로지 연구하시던분이 와서 세미나하는것을 듣다보니

역시나 온톨로지와 같이 일반언어(프로그래밍 언어가 아닌)를 연구하는 사람들은

언어의 엄청난 모호성 때문에 정말 힘들어 하는것 같다.


일상에서 언어를 정말 대화의 목적으로 사용할때는 언어가 얼마나 모호한지 잘 느끼기 힘들지만,

좀 더 공부를 하다보면 얼마나 모호한지를 잘 알게 된다.

아래 문장을 보자.

I shoot a buck.


대화중에 forest라거나 hunting에 대해서 언급하다가 이 문장을 들으면

"I shoot a buck(나는 사슴을 쐈다)" 가 되지만,

gamble이라거나 casino에 대해서 언급하다가 들으면

"I shoot a buck (나는 1달러를 베팅했다)"

가 된다.


위의 예는 이번 세미나때 들은것이 아니라 예전에 인지과학 스터디를 할때

사람이 언어를 인지하는 방식에 대해 나온 예였는데,

이번 세미나때에는 저거보다 더 심각한 예도 들었다.


아래 문장을 보자.

A rather than B such as C

1. PET rather than DOG such as CAT

2. LIZARD rather than ANIMAL such as REPTILE


위의 문장에서 1번과 2번의 관계를 그림으로 나타내보면


이렇게 된다.

위에서의 I shoot a buck의 경우에는 문맥에 따라서 단어자체가 가지는 뜻의 모호성이 있었을뿐

A가 B를 C했다 같은 '구조'자체에는 변화가 없었는데

여기서는 단어들간의 구조가 바뀌었다.

심지어 전후 문맥같은것도 없이 문장의 나머지 구성요소(rather than, such as)들은 완전히 똑같았는데

거꾸로 단어에대한 배경지식이 문장에서 자기들간의 구조에 영향을 미친거다.


이런거 처리하려면 참 힘들것 같다.
저작자표시

'공부' 카테고리의 다른 글

작지도,크지도, 같지도 않다. -1.#IND  (0) 2010.12.29
언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
Posted by youknow04
TAG 모호성, 온톨로지
트랙백 25개, 댓글 0개가 달렸습니다

가변인수(va_arg)를 이용한 계산오차 줄이기

공부 2010.08.02 19:28
기하관련 코딩을 하다보면 컴퓨터에서의 수치오차 때문에 골치아플 때가 있다.

일반적인 어플리케이션에서는 값이 1000.000 이건 1000.001 이건간에 큰 차이가 없을 수도 있지만,

기하 알고리즘에서는 그 차이 때문에 두 도형이 만나는지/안만나는지 가 갈릴 수도 있기 때문이다.

기하 알고리즘이 아니더라도 시뮬레이션 같은이 계산결과가 누적되는 곳에서는 오차가 누적되서 커질 수 있기 때문에 역시 문제가 되곤 한다.

한 예로, 걸프전 당시 미군에서 사용하던 패트리어트 미사일은, 뉴스에서 요란하게 떠들던것과는 다르게 실제로 명중률이 굉장히 낮았다.

실수 계산을 할때 수치오차를 제대로 고려하지 않아서 엉뚱한 결과가 나왔기 때문이다.

(왼쪽이 정상적으로 계산되어야할 미사일 궤도. 오른쪽이 y축의 float오차때문에 깍여서 실제 계산된 궤도)


이러한 수치오차가 발생하는 이유는 컴퓨터가 실수를 저장할때

유효숫자의 n승 형태로 저장하기 때문이다.

그래서 더하기나 빼기를 할때 특히나 문제가 되는데 (왜 곱하기가 아니라 더하기 인지는 유효숫자*n승 표현으로 직접 계산해보면 알듯...)


이런 수치오차를 해결하는 한가지 방법은 float이 아니라 좀 더 많은 유효숫자를 가지는 double을 사용하는거다.

하지만 double로 해서도 문제가 생길 경우에는 숫자들을 더할때 약간 더 조심함으로서 계산오차를 줄일 수 있는 방법들이 있다.


그중 한가지 방법이 작은수부터 더하는건데, 이때 얼마나 많은 수를 더할지 모르기 때문에,

가변인수를 사용하면 코딩을 좀 더 쉽게 할 수 있다.

최근 코딩을 하면서 가변인수로 만들어둔 함수가 있어서 붙여본다.

#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdarg.h>
#include <algorithm>

using namespace std;

bool lessABS(const double& lhs, const double& rhs)
{
return fabs(lhs) < fabs(rhs);
}

double numeric_addition(int num,...){
     double sum=0.0;
     vector<double> v;
     int i;
     va_list ap;
     double arg;

     v.assign(num,0);
     va_start(ap,num);
     for (i=0;i<num;i++) {
          arg=(double)va_arg(ap,double);
          v[i] = arg;
     }
     va_end(ap);

     sort(v.begin(),v.end(),lessABS);
     for(i=0;i<(int)v.size();i++){
         sum+=v[i];
     }
     return sum;
}

int main(int argc, char **argv){
double a = 10000000000000000;
double b = 1;
double c = 1;
printf("%lf\n",numeric_addition(3,a, b, c));
printf("%lf\n",a+b+c);

return 0;
}




10000000000000000(경)에다가 1을 두번 더해보면, 일반적으로 1000000000000+1+1을 하면 1경이 그대로 나오지만,

위의 numeric_addition함수를 이용해서 더하면 올바른 값이 나옴을 알 수 있다.


위 numeric_addition함수의 첫번째 숫자는 argument의 수를 말한다. (여기서는 3개의 숫자를 더했으므로 3)

저작자표시

'공부' 카테고리의 다른 글

작지도,크지도, 같지도 않다. -1.#IND  (0) 2010.12.29
언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
Posted by youknow04
TAG va_arg, va_end, va_list, 가변인수, 수치오차
트랙백 7개, 댓글 3개가 달렸습니다

계산기하 - 원 포함 알고리즘 코딩

공부 2010.06.03 22:25
요즘에는 모처럼 계산기하 관련 코딩을 하고있다.

평면위에 원들이 있을때 각각의 원들을 일부라도 포함하는 가장 작은 원을 찾는 문제다.

(까만원들이 이렇게 문제로 주어졌을때,
모든 까만원의 일부라도 포함하거나 터치하는 원들 중 가장 작은 저 빨간 원을 찾으면 된다.)


재밌는건 원의 갯수를 n개라고 했을때,

이 문제는 n개의 원을 x축을 따라서 정렬하는것보다 빠르게 풀 수 있다는거다.(시간복잡도가 expected O(n))


재미없는건...

사실 논문으로 쓸때에는 99%의 지면을 할당하는 주요 알고리즘이 코드에서는 10%가량밖에 안되고

it's trivial 이라고 논문에 적은 1%에 해당하는 부분이 저 코드의 90%에 해당한다는거다.


예를들면 단순히 3개의 원을 터치하는 가장 작은 원을 찾는 trivial한 문제조차도

실제 구현하려면 비선형 연립 방정식을 풀어야한다.

논문에서는 매우 직관적이고 우아한 알고리즘이지만

구현은 지옥임.

근데 사실 굳이 이 문제만이 아니라 계산기하쪽 알고리즘들이 대부분 그런듯...


아무튼 이제 거의 구현해서 코드 돌리고 xml로 결과 뽑아서 ipe에서 열어봤더니 위에 그럼처럼 이쁘게 나온다.

이걸 열심히 구현한 공로(?)로 논문에 공저자로도 들어갈것 같으니 조만간 그간 노력한 보람이 있을듯하다.
저작자표시

'공부' 카테고리의 다른 글

언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Posted by youknow04
TAG 계산기하
트랙백 1개, 댓글 0개가 달렸습니다

NP, NP-COMPLETE, NP-HARD

공부 2010.05.05 05:11
P,NP 문제는 워낙에 유명한 난제라서 그런지 검색은 많이 되는데,
그렇게 나온 검색 결과는 보통
너무 엄격하게 써놔서 어려워서 뭔말인지 모르겠다거나
아예 틀린경우도 종종 보인다.

NP문제를 쉽게 설명하자면 yes/no로 답할 수 있는 문제중에,
yes라는 답에 해당하는 구체적인 예를 줬을때, 그것이 yes가 맞다는것을 빠른(polynomial)시간안에 알 수 있으면 NP문제이다.

알기쉽게 예를들면,

"평면위에 점이 n개가 있는데 그 점중에 하나에서 시작해서 모든 점을 한번씩만 방문하고 다시 제자리로 돌아오는 길중에서, 그 경로의 길이가 k이하인게  있을까?"

라는 문제는 NP문제이다.

yes/no로 대답할 수 있고,
(검은점 n=10개, 발로그려서 빨간선의 길이가 제멋대로긴 하지만 숫자만큼의 길이를 가진다고 하면, 한번씩 거치는 위의 빨간 길의 총 길이는 29. 문제에서 k가 30이었다면 답은 yes)

위의 그림에서처럼 yes에 해당하는 답을 줬을때 쉽게 답이 맞음을 알 수 있기 때문이다.


그러면 P문제는 뭘까?
NP문제 중에서 답조차도 빠른시간안에 찾는 방법이 알려져 있으면 그건 P문제다.

위에서 예를든 문제 같은 경우에는 NP문제이지만 P문제는 아니다.

저 경우에는 경로의 길이인 k가 30이라서 대충해도 쉽게 찾을 수 있었지만 k가 20정도라면 그 답을 쉽게 찾을 수 없기 때문이다. 실제로 위의 문제에 대해서 알려진 가장 빠른 알고리즘도 exponential한 시간복잡도를 요구한다.
물론 이경우에도 누가 k=20일때의 답을 알려준다면 우리는 손쉽게 그 답이 yes임을 알 수 있다. P문제도 NP문제에 속하기 때문이다.


NP-COMPLETE문제는 모든 NP문제들이 빠른시간안에 변환(reduction)될 수 있는 문제를 말한다. 모든 NP문제들이 빠른시간안에 NP-COMPLETE문제로 변환될 수 있기 때문에, NP-COMPLETE문제만 풀면 모든 NP문제를 빠르게 풀 수 있다.


NP-HARD문제는 정말 어려운 문제로, NP문제가 아니다.
유명한 TSP같은 문제가 NP-HARD인 문제인데,
TSP가 뭐냐하면 아까 위에서 예를 들었던문제의 일반적인 버전의 문제이다.
총 길이가 k이하인 길이 있느냐가 아니라, 가장 최적인 길이 뭐냐라는 문제같은거다.

이 문제의 경우에는 최단경로에 해당하는 답을 줘도 우리가 그 길이 진짜 최단경로인지 빠른시간안에 알 수 있는 알려진 방법이 없다.



그럼 이제 그 유명한 수학적 난제인 P=NP? 문제에 대한건데,
P문제가 NP문제와 같으냐 다르냐를 증명하는 문제이다.
NP가 P와 같다면 NP문제에 해당하는 모든 문제를 빠른시간안에 푸는것이 가능하다는 거니까.

그런 엄청난 파급력 때문인지 이 문제는 유독 이상한 사람들이 많이 꼬이는것 같다.

예를들어 입시철 즈음 되면 모 지방대학에서 P=NP를 증명했다고 '주장'하며 언론플레이를 하는 교수님이라거나...

사실 P는 NP와 다른것임이 거의 확실해 보인다.
다만 증명이 안되있을뿐이지.

그리고 사실 P,NP문제에 대해서 배우는 이유는 위에처럼 둘이 같거나 다르다는것을 증명하는 극단적인 응용 보다도
어떤 문제를 풀 수 없음을 미리 알수 있다는데 있는것 같다.
내가(혹은 누구라도) 이 문제를 빠르게 풀 수 없음을 미리 파악하고, 우회해서 갈 수 있다는건 정말 엄청난 이득이지.

'공부' 카테고리의 다른 글

가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Google Summer of Code2010 & CGAL  (0) 2010.03.30
Posted by youknow04
TAG NP, NP-Complete, NP-Hard
트랙백 8개, 댓글 7개가 달렸습니다

for문에서 j

공부 2010.04.26 02:11
많은 사람들이 for문을 돌릴때 변수로 i를 사용한다.

i는 iteration, 혹은 index를 나타내기도 하고
한글자라 간결하기도 하고
널리 사용된다는 점에서도 for문에서 i를 사용하는건 바람직한 일인것 같다.

그런데 j는 어떨까?
사람들이 j를 사용하는 이유는 아마도 널리 사용하는 "i"다음의 알파벳이 "j"여서 그런것 같다.

문제는 j는 i와 매우 비슷하게 생겼다는 거다.

for i:
 for j:
   arr[i*j+i][j*i-i] .....

2중루프에서만 사용되도 헷갈린다.

단지 헷갈릴 뿐만이 아니라, 실수로 i와j를 바꿔썼을 경우에는 디버깅이 재앙이 된다.

나는 학부생때 이미 저런 상황을 몸으로 겪은 다음에 i,k,m 순으로 변수를 할당하거나,
아니면 아예 알파벳 하나가 아닌 단어를 변수로 사용하는  습관을 가지게 되었는데,
오늘 내 주위에서 j를 사용하는 습관때문에 하루를 꼬다박은 안타까운 케이스를 또 보게됐다.

이런걸 굳이 다들 몸으로 체험하지 않아도 되게
CS101에서 아예 비슷한 알파벳은 인덱스로 섞어쓰지 말라고 가르치면 좋지 않을까 하는 생각을 해봤다.

전부 다 몸으로 때우지 않고도 깨닫게 하려고 있는게 교육이잖아?

'공부' 카테고리의 다른 글

계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Google Summer of Code2010 & CGAL  (0) 2010.03.30
O/R mapping  (0) 2010.02.26
Posted by youknow04
TAG FOR, i j, 변수
트랙백 2개, 댓글 3개가 달렸습니다

SQL injection on python+SQLite3

공부 2010.04.02 03:29
모처럼 약간 여유가 생겨서 웹코딩이나 좀 하고있는데

파이썬의 SQLite3 기본 라이브러리가 쿼리문의 테이블 이름에 있어서는

SQL injection 공격에 대한 방어를 안해주는것 같다.


예를들면 코드에 SQL문을 사용할때 포맷스트링을 사용하면 엄청난 문제가 발생할 수 있는데
cursor.execute("INSERT INTO tablename  VALUES (%s,%s)"%(value1,value2) )
이경우에 value1과 value2가 사용자에게 웹에서 받은 정보라고 해보면

value2가
"2); DROP TABLE tablename; 아무거나~~"
이라고 하면 임의로 데이터를 다 날려버릴 수도 있는거잖아?

그래서 정석대로 안전하게 하면
cursor.execute("INSERT INTO tablename  VALUES (?,?)",(value1,value2) )
이렇게 하면 SQLite에서 안전하게 물음표를 value로 치환해주는데


cursor.execute("INSERT INTO? VALUES (?,?)",(value1,value2) )
이렇게 tablename에 해당하는 부분도 ?로 치환하면 에러가 나더라.

'공부' 카테고리의 다른 글

NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Google Summer of Code2010 & CGAL  (0) 2010.03.30
O/R mapping  (0) 2010.02.26
Laplacian Pyramid on GPU  (1) 2010.01.13
Posted by youknow04
TAG Python, SQL Injection, SQLite3
트랙백 6개, 댓글 0개가 달렸습니다

Google Summer of Code2010 & CGAL

공부 2010.03.30 23:42
구글에서 매년 오픈소스를 발전시키고자 학생들을 동원하는 프로그램이 있다.

이름하여 Google Summer of Code (아래부터는 GSoC로 줄임..)

학생들에게 구글에서 돈을 주고 학생은 열심히 프로그래밍을 해서 오픈소스를 발전시키는 매우 바람직한 프로그램이라 할 수 있겠다.
(정말 바람직하지 아니한가?)

이번 년도에는 특히나, 내 전공인 계산기하(Computational Geometry)쪽 오픈소스 라이브러리인 CGAL이 GSoC프로그램에 선정되어서
CGAL을 발전시키는데 나의 여름을 불사르고자, 프로포잘도 준비하고
거의 풀타임으로 이쪽 일을 해도 좋다고 교수님한테 허락까지 받았는데...

메일한번 보내면 한달씩 감감 무소식이던 모 기업에서 느닷없이 예전에 그 공동 프로젝트를 하자고 해서 취소될 위기에 처했다.... ㅠㅠ

아무튼 오픈소스에 관심이 있다면 괜찮은 프로그램인것 같다.
우리나라 돈으로 500만원이 넘는 돈도 돈이지만..
나중이 이력으로도 괜찮을것 같고,
글로벌 프로그램인 외국 유명 대학이나 연구소의 쟁쟁한 분들이 멘터를 맡아주시는 경우가 많다.

그리고 CGAL외에도 GSoC에 선정된 다른 유명한 오픈소스들(boost라거나...)이 대단히 많이 있으니 입맛대로~


'공부' 카테고리의 다른 글

for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Google Summer of Code2010 & CGAL  (0) 2010.03.30
O/R mapping  (0) 2010.02.26
Laplacian Pyramid on GPU  (1) 2010.01.13
Block-based Web Search  (0) 2009.12.06
Posted by youknow04
TAG CGAL, Google Summer of Code, GSoC, 오픈소스
트랙백 4개, 댓글 0개가 달렸습니다

O/R mapping

공부 2010.02.26 16:14
최근에 앨리스 개발에 다시 손대면서 Django(파이썬기반의 웹프레임웍)에서 DB위에 씌운 레이어의 편리성에 다시한번 감탄하게 됐다.

일반적으로 데이터베이스에 엑세스를 할때에는 SQL을 사용하는데,
사실 웹코딩을 하다보면 이런 SQL형식으로 DB쿼리를 날리는게 여간 귀찮은 일이 아닐 수 없다.

하지만 Django에서는 SQL쿼리를 직접 날리는게 아니라
아래와 같이 그냥 일반적인 object에 엑세스 하는것처럼 DB를 관리할 수 있다.

SQL:
INSERT INTO  Blog (id, name, url) VALUES (12, 'youknow', 'http://youknow04.textcube.com')

Django:
b = Blog()
b.id = 12
b.name = 'youknow'
b.url = 'http://youknow04.textcube.com'

b.save() #실제로 DB에 저장하기 위한 함수. model에서 상속받으면 기본으로 있음.


이처럼 DB상의 한 데이터를 객체지향(Object-Oriented)언어의 한 객체로 변환하는것을 O/R mapping(Object-relational mapping) 이라고 한다.
특히 파이썬 같은 스크립트 언어의 객체로 변환을 하면, 파이썬 특유의 막강한 내장함수들을 활용하거나 유연한 코딩을 할 수 있기 때문에 월등한 생산성을 얻을 수 있다.
그냥 직관적으로 생각해봐도 DB안에 박혀있는 데이터를 다루는것과, 언어 자체의 객체를 다루는것에는 편리성 측면에서 엄청난 차이가 있으니까.

그래서 O/R mapping은 Ruby on Rails같은 다른 웹프레임웍들에서도 많이들 지원한다더라.


'공부' 카테고리의 다른 글

SQL injection on python+SQLite3  (0) 2010.04.02
Google Summer of Code2010 & CGAL  (0) 2010.03.30
O/R mapping  (0) 2010.02.26
Laplacian Pyramid on GPU  (1) 2010.01.13
Block-based Web Search  (0) 2009.12.06
오토 레포트  (3) 2009.11.04
Posted by youknow04
TAG Django, O/R mapping, orm, Python, 웹코딩
트랙백 3개, 댓글 0개가 달렸습니다

Laplacian Pyramid on GPU

공부 2010.01.13 23:17
이번 GPU수업을 들으면서 했던 숙제 중에 하나가 Laplacian pyramid와 Gaussian pyramid를 구현하고, 그것을 이용해서 이미지 모자이크를 만드는 것이었다.

(그림출처: http://fourier.eng.hmc.edu/e161/lectures/canny/node3.html)

라플라시안 피라미드의 기본적인 원리는 이미지를 확장했을때 원본과의 차이를 저장해놓는 것이다.
예를들어 위의 그림 라플라스 피라미드의 제일 아래의 이미지를 가로세로 각각 2배로 확장을 하더라도 가우시안 피라미드의 2번째 그림과 같은 깔끔한 결과를 '바로' 얻을 수는 없다.(일반적으로 이미지 리사이즈를 해서 크기를 키웠을때 결과가 깔끔하지 않은것을 생각해보면 된다)
하지만 라플라스 피라미드 2번째에 저장되어있는 차이를 이용해서 보정을 하면 똑같은 깔끔한 결과를 얻을 수 있고, 이것을 반복하면 가우시안 피라미드 제일 위쪽에 있는것과 같은 깔끔한 원본그림을 얻을 수 있는것이다.


그리고 이 과정에서 mask를 지정해서 두 이미지를 합성하면, 아래와 같이 부드럽게 합성이 된다.
합성할 이미지1. 내손.



합성할 이미지 2. 왼쪽눈을 손바닥 위치에 맞추기 위해서 대강 잘라서 위치를 수정했다.

mask. 흰색은 1번이미지, 검은색은 2번이미지가 차지할 영역이다.



결과물. mask의 경계선이 부드럽게 처리되면서 두 1,2번 이미지가 결합된다.


사실 이 방법은 이미 내가 태어나기도 전에 나왔던 논문에 실린 방법이라 요즘의 계산사진학의 결과물에 비할바는 아닌데다가, 굳이 GPU까지 써가면서 가속할 필요도 없어보이는 작업이다.
사실 애초에 mask를 부드럽게 하는것만으로도 비슷한 결과를 얻을 수 있어 보이기도 한다.
하지만 image pyramid는 SIMD계열의 parallel머신에서 계산을 할때 종종 마주하게되는 난감한 문제인 data packing이라거나 expansion같은 기본적인 문제의 해결과도 관련이 있기 때문에 한번쯤 연습해보는것도 괜찮은것 같다.


포스팅 하는김에 내가 CUDA로 작성한 코드도 올린다.

CUDA의 기본프로젝트에 있는 recursiveGaussian에서 내가 필요한 부분만 수정했다.
나도 저때 CUDA를 막 배우기 시작한터라 깔끔한 코드는 아니지만, 처음 CUDA를 시작하는 사람에게는STL과 CUDA를 같이 사용해서 GPU메모리를 관리하는 좋은 예제가 될 수 있을듯?
(*vs2005에서 구현하고 돌려봤다. 근데 Linux용 CUDA컴파일러에서는 버그가 있어서 STL을 사용할경우 문제가 생길 수도 있으니 주의!)

Ref : PETER J. BURT, EDWARD H. ADELSON, A Multiresolution Spline With Application to Image Mosaics(1983)

'공부' 카테고리의 다른 글

Google Summer of Code2010 & CGAL  (0) 2010.03.30
O/R mapping  (0) 2010.02.26
Laplacian Pyramid on GPU  (1) 2010.01.13
Block-based Web Search  (0) 2009.12.06
오토 레포트  (3) 2009.11.04
Constructive Logic  (3) 2009.09.22
Posted by youknow04
TAG CUDA, GPU, Laplacian pyramid, stl
트랙백 3개, 댓글 1개가 달렸습니다