spam filtering with transport/router of exim

I used to classify spam mail with procmail, but procmail is excuted only for local users. So when you use the .forward file, spam mail is also forwarded to the other email addresses.
It’s not so quite import but I don’t like this behavior. so I change the exim configuration to run bogofilter with the transport/router of exim.
first let’s configure transport like this.
bogofilter:
driver = pipe
command = /usr/sbin/exim -oMr bogodone -bS
use_bsmtp = true
transport_filter = /usr/bin/bogofilter -d /etc/bogofilter/ -e -p
log_output = true
return_path_add = false
temp_errors = *
home_directory = "/tmp"
current_directory = "/tmp"
message_prefix = ""
message_suffix = ""

after that you need to declare the router which uses this transport. Order is important in router. I put it right after the system_alias router.
bogofilter:
domains = +local_domains
no_verify
condition = ${if !eq {$received_protocol}{bogodone} {1}{0}}
driver = accept
transport = bogofilter

With this configuration, bogofilter will be excuted but it put only an additional header like “X-bogofilter: …” so we need another transport/router to classify the spam mails.
Here’s the transport to do that.
spam_delivery:
driver = appendfile
directory = /home/$local_part/.maildir/.Spam
maildir_format
delivery_date_add
envelope_to_add
return_path_add

With this transport, we can put the spam mails to the .Spam folder within $HOME/.maildir. If you use the IMAP protocol, then you can simply check the spam mails by accessing Spam folder. But with POP3 protocol there’s no way to check it. So if you use POP3 then use the header filtering rules of client software instead.
And we also need to add a router which uses this transport. The order is important in here too. I put it below the bogofilter router.
removingspam:
driver = accept
check_local_user
condition = ${if match {$h_X-Bogosity:} {Spam, tests=bogofilter} {1}{0}}
transport = spam_delivery

Spam mail has the header, X-Bogosity: Spam, test=bogofilter …, so we can classify the spam mail easily.
To confirm it working, check the mail log. I checked /var/log/mail/current because I use metalog but in almosts linux distributions syslogd is included so check the /var/log/messages file.

$ # tail -f /var/log/mail/current |grep R=
Feb 26 16:48:31 [exim] 2008-02-26 16:48:31 1JRkT5-0001pz-Nx => mailaddr R=procmail T=procmail
Feb 26 16:48:35 [exim] 2008-02-26 16:48:35 1JTuY0-00081q-7u => mailaddr R=removingspam T=spam_delivery
Feb 26 16:48:44 [exim] 2008-02-26 16:48:44 1JQWAs-0002po-CR => mailaddr R=bogofilter T=bogofilter
Feb 26 16:48:45 [exim] 2008-02-26 16:48:45 1JTuY5-000826-EK => mailaddr R=removingspam T=spam_delivery

The name of router/transport is located after R= and T= . The name of router appears after R=, and the name of transport appears after T=. According to this log, we can say that removespam or procmail router is used after the bogofilter excuted.

exim 의 transport, router 를 이용한 스팸 필터링

익숙한 걸 사용하려다보니 procmail 을 이용해서 bogofilter 를 수행하는 방법을 사용해 왔지만, procmail 은 로컬 유져에 한해서 실행되게 되므로, alias 나 .forward 를 사용하게 되는 경우 스팸 필터링을 하지 않게 된다.
하여튼 이게 좀 신경쓰여서 transport 와 router 를 이용해서 bogofilter 를 수행하도록 설정해봤다.
우선 transport 를 다음과 같이 설정해보자.
bogofilter:
driver = pipe
command = /usr/sbin/exim -oMr bogodone -bS
use_bsmtp = true
transport_filter = /usr/bin/bogofilter -d /etc/bogofilter/ -e -p
log_output = true
return_path_add = false
temp_errors = *
home_directory = "/tmp"
current_directory = "/tmp"
message_prefix = ""
message_suffix = ""

그리고 이 transport 를 이용하는 router 를 만든다. 참고로 router 는 순서에 민감하므로 삽입할 위치를 잘 조절해야 한다. 나같은 경우는 system_alias 다음에 선언해두었다. (alias 를 사용하는 주소들중 로컬 유져에게 전달되지 않는 건 mailman 과 관련된 것들 밖에 없는데 이거야 뭐 어짜피 인증된 사용자가 보낸 메일만 받으니 상관 없겠다는 마음으로…-_-;; )
bogofilter:
domains = +local_domains
no_verify
condition = ${if !eq {$received_protocol}{bogodone} {1}{0}}
driver = accept
transport = bogofilter

여기까지만 하게 되면 bogofilter 를 수행하기는 하지만 이를 이용해서 메일을 옮긴다거나 하는 동작은 하지 않게 된다. 그러므로 이런 동작을 시키기 위한 transport 와 router 를 또 추가해주자.
역시나 transport 먼저…
spam_delivery:
driver = appendfile
directory = /home/$local_part/.maildir/.Spam
maildir_format
delivery_date_add
envelope_to_add
return_path_add

이렇게 하면 자신의 홈 디렉토리의 .maildir 아래 .Spam 이란 디렉토리를 만들고, 그 디렉토리에 스팸 메일을 저장하게 된다. IMAP 으로 접속하면 Spam 메일들을 확인할 수 있기 때문에 이렇게 했는데, POP3 만 사용하는 거라면 그냥 제목에 [Spam] prefix 를 붙이게 하는 것도 나쁘지 않을 듯…
그 다음엔 이 transport 를 이용하는 router! 역시나 어디다 위치시킬지 잘 생각해야 한다. 나같은 경우엔 bogofilter router 바로 아래에 이걸 위치시켜놓았다.
removingspam:
driver = accept
check_local_user
condition = ${if match {$h_X-Bogosity:} {Spam, tests=bogofilter} {1}{0}}
transport = spam_delivery

스팸 메일은 bogofilter 에 의해 X-Bogosity: Spam, test=bogofilter … 식의 헤더가 추가되기 때문에 이렇게 할 경우 스팸을 쉽게 분류해낼 수 있다.
잘 됐는지 확인은 메일로그를 이용해서 확인하면 된다. 나같은 경우는 metalog 를 사용하니 /var/log/mail/current 를 이용해서 확인해야 했는데 대부분의 경우 syslogd 를 사용할테니 /var/log/message 를 확인하면 될 것 같다.

$ # tail -f /var/log/mail/current |grep R=
Feb 26 16:48:31 [exim] 2008-02-26 16:48:31 1JRkT5-0001pz-Nx => 메일주소 R=procmail T=procmail
Feb 26 16:48:35 [exim] 2008-02-26 16:48:35 1JTuY0-00081q-7u => 메일주소 R=removingspam T=spam_delivery
Feb 26 16:48:44 [exim] 2008-02-26 16:48:44 1JQWAs-0002po-CR => 메일주소 R=bogofilter T=bogofilter
Feb 26 16:48:45 [exim] 2008-02-26 16:48:45 1JTuY5-000826-EK => 메일주소 R=removingspam T=spam_delivery

유심해서 봐야할건 R=, T= 다음에 나오는 것들이다. R= 다음에 나오는 것은 사용된 router 를 의미하고, T= 다음에 나오는건 transport 를 의미한다. 위의 로그를 보면 bogofilter 를 수행한 뒤 removingspam router 를 이용해서 spam_delivery trasport 가 수행되기도 하고 혹은 이를 통과해서 procmail transport 가 수행되기도 하는 걸 확인할 수 있다.
기본으로는 procmail transport 가 없으니 원랜 local_delivery 가 나올 수도 있겠고 뭐 하여튼 router 나 transport 이름은 사용자가 맘대로 지으면 되는거라 상황에 따라 다 다를 듯…
스팸 없는 세상이 올 때까지 ㅠ.ㅠ 오늘도 삽질…

CentOS 삽질 후기: 잘못된 정보여 안녕!

얼마 전에 아는 형 부탁으로 또 하나의 서버를 살펴봐주게 되었다. 장기적으로 할건 아니고 단발성으로 잠깐 봐주게 될 일이었는데…
여기 설치되어 있던 리눅스는 Fedora core2! 아는 사람은 다 알다시피 Fedora core2 는 업데이트 지원이 끊긴지 이미 오래된 배포판이다. 하여튼 알려진 버그들로 무장된 상태를 유지하는건 알바로써의 자세가 아니기 때문에 최신 버젼으로의 업데이트를 시도해봤지만 core2->8 으로의 업데이트는 실패!! (core8 의 redhat-release를 설치한 뒤 yum upgrade 를 시도해봤지만 패키지 의존성이 해결되질 않는다. 7, 6, 5 도 마찬가지)
차례로 순서를 밟아가야 겠다는 생각이 들어서 3, 4, 5 순서로 시도를 해봤는데 8 까지 제대로 업데이트가 되지도 않았을 뿐더러 reboot 이 제대로 되지 않아 버렸다. 하하하하하하 (사고 쳤단 얘기) apache, mysql 등이 /usr/local/apache, /usr/local/mysql 등의 prefix 에 설치되어 있었고, init script 조차 제대로 없는 그런 암울한 상황이었는데 마침 잘됐다는 생각으로 CD 와 함께 IDC 에 방문했다. fedora 는 업데이트 주기가 너무 짧고, 내가 관리해야할 서버가 아닌 마당에 젠투를 깔아주는건 옳지 못하단 생각이 들었으며, 우분투 등을 깔아주기엔 내가 너무 무지했다. 결국 선택한건 CentOS 5.1!
불행히도 DVD rom 이 없었기 때문에 가져갔던 CentOS 5.1 dvd 는 사용할 수가 없었고, 혹시 몰라 구워갔던 CentOS 5.1 net install cd 를 사용해야 했다. 설치야 예전 레드햇 계열들과 별로 다르지 않으니 어렵지 않게 끝~
하지만 이게 왠 일! /home 계정 밑에 있는 파일들을 아파치에서 읽질 못한다! 혹시나 해서 apache 유져의 쉘을 /bin/bash 로 바꿔주고 apache 유져로 스위치한 뒤 파일들을 읽어보니 잘 읽어온다. -_-; 헉; 이젠 리눅스마저 날 농락하려 드는건가 싶은 마음이… ㅠ.ㅠ 정확히 뭐가 문젠지도 몰라서 검색어조차 찾을 수 없던 이 시점! selinux 라는 요상 야릇한 단어가 눈에 들어왔다. 하여튼! 검색을 통해 찾아낸 아래와 같은 명령어를 통해 이 문제를 해결할 수 있다.

acl 을 사용하는건지 아님 뭔가 다른 방법을 사용해서 저런 secure context 를 저장하는 건지 까지는 모르겠지만 하여튼 강화된 보안 정책 덕에 초보 리눅서만 고생했다. ㅠ.ㅠ 그나저나 하고 싶었던 얘기는 내가 천재라 저런 문제를 해결했다는게 아니고, 웹에 잘못된 문서가 너무 많다는 것!
저 문제를 해결하기 위해 CentOS apache home 403 등으로 검색했을 경우 상위 랭크로 나오는 페이지들은 대부분 아파치 소스를 가져다 빌드해서 저 에러를 피해가는 요상한 방법이다. 그나마 거기에 설명된 설치 법에는 CFLAGS 등을 설정하지도 않고, 무슨 의미인지도 모르는 옵션들로 가득차 있으며 그나마 효율적이지도 않다.
linux 는 배포판 별로 파일 레이아웃에 대한 정책이 있다. 약간씩은 다르지만

/usr – 실행파일, 라이브러리, man 페이지, 문서 등이 놓여짐
/etc – 설정파일이 놓여짐
/var – 런타임에 생성되는 데이타가 놓여짐 (로그, 데이타베이스 파일, 메일 파일 등등)
/tmp – 임시파일 저장장소

대강 위와 같은 정책을 사용하며 약간 부연하자면 /usr 과 / 에 대해 아래와 같은 디렉토리 구조가 더 사용된다.

/bin 실행파일
/sbin 관리자한테만 필요한 실행파일
/lib 프로그램이 실행될 때 사용하는 쉐어드 라이브러리등이 존재

이런 얘기를 왜 하냐면 배포판에서 제공하는 패키지를 사용할 경우 위의 정책대로 파일들이 놓여지며 설정파일을 찾기 위해선 /etc 밑을 뒤지면 되고, 실행은 /usr/local/apache/bin/apachectl start 와 같이 해야 하는게 아니라 apachectl start 와 같이 하면 된다.
그냥 소스를 가져다가 ./configure –prefix=/usr/local/apache 와 같이 설치할 경우 PATH 가 걸려있지 않아서 실행 파일의 full path 를 적어줘야 하는 불편함 외에도 man page 가 놓여있는 경로가 MANPATH 에 등록되질 않기 때문에 명령어 들의 man 페이지를 확인해볼 수도 없다. (사실 저렇게 설치하는 유져가 man 페이지를 참고할 거란 생각은 별로 들지 않지만) 거기다가 init 스크립트를 제공하지 않는 프로그램들도 많아서 프로그램의 실행 종료를 수동으로 해야하는 불편도 생긴다.
간단한 예로 mysql 을 패키지로 설치한 것과 소스로 /usr/local/mysql 에 설치한 것을 비교해보자.

소스 패키지
실행 /usr/local/mysql/bin/mysql mysql
man page 사용불가능 사용가능
데몬 시작 /usr/local/mysql/bin/mysqld_safe & /etc/init.d/mysqld start
데몬 종료 ps ax|grep mysql 후 kill 해당pid /etc/init.d/mysqld stop
자동 실행 /etc/rc.local 에 /usr/local/mysql/mysqld_safe & 추가 ntsysv 에서 mysql 체크
파일 변조 확인 불가능 rpm -Va mysql
제거 rm -rf /usr/local/mysql rpm -e mysql
업데이트 체크 수동 yum check-update mysql
파일 리스트 find /usr/local/mysql rpm -ql mysql

이걸로 끝이 아니다. 만약 openssl 이 업데이트 되면서 소스로 가져다 설치한 mysql 이 실행되는데 필요한 libcrypto.so.4 란 파일이 제거되었다고 해보자. rpm 등을 사용하면 dependency check 과정이 있으므로 이런 황당 무계한 일이 벌어지지 않는다. 하지만 소스로 설치했다면 저 라이브러리를 찾을 수 없다는 에러를 만날 수밖에 없다.
그리고 실행파일 경로(PATH)나 man page 경로(MANPATH) 같은 건 ~/.bash_profile 이나 /etc/bashrc /etc/profile.d 등을 수정해주면 쉽게 등록해 줄 수 있다. 하지만 이런 것까지 설명하고 있는 문서는 본 적이 별로 없는 것 같다. (물론 이렇게 설치하는 유져가 man 페이지를 확인할 거란 생각은 하지 않는다.)
우선 패키지 관리자를 사용하면 업데이트가 나왔는지를 확인하는 작업과 업데이트를 수행하는 일이 아주 간단해진다. 또한 프로그램의 설치/제거 가 같은 인터페이스를 통해 이뤄지고, 데몬의 실행/종료도 비슷한 인터페이스를 통해 이뤄진다.
대부분의 데몬들은 /etc/init.d/데몬이름 start|stop 와 같이 시작/종료를 할 수 있으므로 뭔가를 새로 설치했을 때 어떤 식으로 실행해야할지, 어떤 식으로 종료시켜야할지 고민할 필요가 없다. 게다가 ntsysv 를 통해 gui 로 시동 스크립트들을 관리할 수도 있게 되고…
뭐 하튼 예전부터 주장하고 있는 바지만 괜히 a.p.m 을 구축하기 위해 이미 다 설치되어 있는 apache, php, mysql 등을 제거하고 libjpeg, libungif, libgd 등을 줏어다가 하나하나 빌드하는 방법을 설명한 문서는 다 사라졌음 좋겠다.
jpeg 헤더가 필요하면 yum install libjpeg-devel 을 설치하면 된다. gif 헤더는? yum install libungif-devel, gd 는 yum install gd-devel …
다들 삽질로 부터 해방되는 그 날까지! 꺄아악
p.s) 졸려서 날림 마무리

요 며칠 삽질기 -_-! with Exim

어째 요새 관리해야할 서버가 늘어버렸네요. (전 언픽스 하나로 족한데 ㅠ.ㅠ) 하여튼!! 요 며칠 사이 gentoo + exim + procmail + spf + srs + clamav + bogofilter + dovecot 를 시도해봤습니다.

사실 계속 제가 맡아서 할 게 아니라 길어야 일 년 정도 만져줄 서버기 때문에 젠투가 아닌 다른 배포판을 생각했었는데, spf 와 srs 를 지원할 수 있도록 하면서 기본으로 제공되는 패키지를 이용할 수 있는 조합이 몇 가지 되질 않더군요. exim 에서 spf 와 srs 는 experimental 로 되어 있기 때문에 바이너리 배포판에선 기본으로 적용이 되어 있질 않고, postfix + milter 조합에서는 srs 를 제공할 수 없기 때문에 남은 선택은 sendmail + milter 조합 밖에 없는데 sendmail 을 사용하기는 싫었거든요.

하여튼! exim 에 procmail 을 붙이는 방법은 아래와 같습니다.

Continue reading 요 며칠 삽질기 -_-! with Exim

exim 에 spf, srs 적용하기

unfix 서버를 구축할 땐 postfix 를 사용했지만 postfix 에선 srs 를 사용할 수가 없었기 때문에 새로 설치하게 된 서버들에선 exim 을 시도 중이다.
그런데 exim 을 사용하려고 하니 문제가 하나 있는데, 구글에서 검색을 해도 원하는 결과가 잘 나오질 않는다는 점이 바로 그것! exim 에는 spf 와 srs 등을 사용하기 위해서는 따로 패치가 필요 없이 그저 EXPERIMENTAL_SPF=yes EXPERIMENTAL_SRS=yes 이 두 가지 환경변수를 세팅한 채로 빌드를 진행하면 된다.
그 이후 어떻게 해야하는 지에 대한 설명이 없어서 한참 헤맸는데 exim 과 함께 설치되는 문서를 확인해야하는 것이었다. -_-; 보면 domain key 등도 위에서와 같이 환경변수만 세팅해주면 사용이 가능해진다.
doc/exim-4.68/experimental-spec.txt.bz2
문서를 확인해보니 이제 해야할 일은 spf 와 srs 설정을 추가해주는 것 뿐 후훗!
SPF 는 global 섹션에서 acl_smtp_rcpt 로 등록되어 있는 것에 다음과 같은 설정을 넣어주면 된다.
# Query the SPF information for the sender address domain, if any,
# to see if the sending host is authorized to deliver its mail.
# If not, reject the mail.
#
deny
message = [SPF] $sender_host_address is not allowed to send mail \
from $sender_address_domain
log_message = SPF check failed.
spf = fail
 
# Add a SPF-Received: header to the message
warn
message = $spf_received

젠투에선 acl_smtp_rcpt = acl_check_rcpt 와 같이 되어 있기 떄문에 acl_check_rcpt 에 위와같은 설정을 추가해줬다. 만약 아래 warn message = $spf_received 를 넣어주지 않으면 spf 결과를 헤더에 추가해주지 않게된다. 생색을 내기 위해선 뭔가 출력될 필요가 있으므로 -_-! 난 헤더를 추가하도록 설정해줬다.
하지만 위에 대로만 할 경우 내가 메일을 보낼 경우에도 SPF-Received 헤더가 붙는 문제가 생긴다. smtp auth 를 설정해놓은 상황에서 이 서버를 통해 메일을 보낼려면 인증이 되어있어야 할테니 아래와 같이 수정해서 이런 문제를 피해주자.

# Add a SPF-Received: header to the message
warn
message = $spf_received
!authenticated = *

그리고 그 담은 SRS 복잡하게 하려면 복잡하겠지만 다 귀찮아서 hash 용 secretkey 하나만 넣어서 설정해버렸다. 아래 설정은 global 섹션에 들어가면 된다. (domainlist 같은게 들어가는 곳) 실제로 somesecretkey 를 적어주는건아니고 그냥 원하는 단어 하나를 적어주면 된다.
srs_config = somesecretkey
그 다음엔 userforward 트랜스포트에 srs 를 적용하도록 해주자 srs = forward 만이 내가 추가해준 부분;;
userforward:
driver = redirect
srs = forward
check_local_user
# local_part_suffix = +* : -*
# local_part_suffix_optional
file = $home/.forward
# allow_filter
no_verify
no_expn
check_ancestor
file_transport = address_file
pipe_transport = address_pipe
reply_transport = address_reply

이제 끝!!!
얼마 받지도 못하는 웍스테이션 조굔지 뭔지 때문에 지난 며칠간 고생한걸 생각하면 흑흑 ㅠ.ㅠ
p.s) exim 에 spf 적용하기와 관련해서 따라하기 편한 문서가 있는데 페이지 랭크가 낮은거 같아서 링크
http://slett.net/spam-filtering-for-mx/exim-spf.html

Sender Rewrite Scheme

spf 는 예전에 써놨던 글에서 충분히 설명해놨듯이 메일의 도메인값과 발송지 값을 이용해 스팸을 필터링해내기 위한 기술입니다. 예를 들어 From address 에 nospam@mytears.org 가 있을 경우 mytears.org 도메인의 txt 정보를 읽어오고, 거기에 적혀있는 61.109.245.78 에서 온 메일만을 정상적인 메일로 판단하게 되는데, 이렇게 spf 가 적용되어 있는 경우 .forward 나 alias 등을 이용해서 메일을 포워딩 시킬 경우 문제가 있을 수 있습니다.
.forwards 를 통해 nospam@mytears.org 를 nospam@gmail.com 으로 리다이렉션을 시킨 경우를 생각해봅시다.

  1. sender@somedomain 에서 nospam@mytears.org 로 메일을 보냄
  2. mytears 메일 서버에서 nospam@mytears.org 사용자에 대한 .forward 파일을 읽어서 거기 적혀있는 nospam@gmail.com 으로 메일을 포워딩 시킴
  3. gmail 메일 서버에서 from address 인 somedomain 의 txt 에서 spf 정보를 읽어옴
  4. spf 로 지정된 아이피와 메일을 포워딩시킨 서버의 아이피가 동일하지 않으므로 spf 정보가 맞지 않다고 판단함
  5. spf 정책에 따라 다르겠지만 대부분 스팸이라고 판단하게 됨
  6. 결국 제대로 메일이 전해지지 않음

이걸 해결하기 위한 방법으로 srs 라는 게 있습니다. 이걸 적극적으로 적용한 예로는 구글이 있습니다.
exim 의 경우 기본적으로 spf, srs 를 지원하기 때문에 빌드할 때 옵션을 잘 조절해주면 쉽게 적용할 수 있습니다. sendmail 의 경우 milter 를 이용하면 srs 를 적용할 수 있구요. 하지만 postfix 에서는 이를 사용할 수 없는 방법이 없습니다. (구버젼의 postfix 라면 패치를 통해 사용할 수 있지만 이 패치가 계속 유지되질 않고 있습니다.)
참고
spf: http://www.openspf.org/
srs: http://www.openspf.org/SRS
p.s) 그나저나 spf 가 나온지 꽤 오랜 시간이 흘렀음에도 대학 메일 서버들 중에 spf 를 지원하는 곳은 별로 없군요.

CG: gaussian blur

gaussian blur 는 간단하게 아래와 같은 gaussian function 을 이미지에 convolution 해주는 것을 통해 쉽게 구현할 수 있다.

시그마값을 0, 2, 4 로 변경시켜가며 가우시안 블러를 적용해보면 아래와 같은 결과를 얻을 수 있음.

코드:
https://github.com/Tee0125/snippet/tree/master/perspective_projection

p.s) 이걸 이용해서 구현해보려는 게 있는데, 막상 gaussian blur 와 difference of gaussian 모두 구현했지만 이상하게 관련된 실험은 손에 잡히질 않고 있다. -_-; 아악;;

CG: 3D Image Rotation

며칠 전 Perspective Projection 을 정리해놓은 김에 3D Image Rotation 도 정리를 해볼까 싶습니다.

Rotation Matrix

3D 이미지 회전은 아래와 같은 행렬을 통해 새로운 좌표를 계산할 수 있습니다. 또한 이 행렬들은 모두 unitary matrix 이기 때문에 Transpose 를 취해줌으로 역행렬을 쉽게 구할 수 있습니다.

z축 기준: (xy 평면에서의 회전)

y축 기준: (zx 평면에서의 회전)

x축 기준: (yz 평면에서의 회전)

Implementation of Image Rotation

처음에는 3차원 공간을 3차원 배열을 사용하여 모델링한 뒤 실제 3차원 좌표를 모두 뒤지며 forward/backward mapping 하는 방법을 통해 3D image rotation 을 구현해보았습니다. 3차원 배열을 이용 512×512 사이즈의 lena image 를 회전시키려면 (512*1.414)^3 만큼의 공간이 필요하게 되고, 저 공간을 모두 뒤지려면 계산 복잡도가 엄청나더군요.

실제 이 방법을 통해 이미지를 회전 시키는 데 ‘분’ 단위 시간이 필요했던 것으로 기억합니다. 게다가 변환을 반복할 수록 이미지의 디그라데이션이 심해졌기 때문에 이건 아니라는 생각이 들더군요. 이런 경우 이미 잘 설계되어 있는 그래픽 라이브러리를 참고하는 것이 좋기 때문에 OpenGL 의 인터페이스를 살펴보며 어떤 식으로 구현하면 좋을 지 생각하기 시작했습니다.

뭐 어짜피 화면이나 이미지로 보여주기 위해선 2D 평면에 projection 하는 것이 필요하므로 매 번 이미지 자체를 돌리기 보다 축을 회전시키고, 마지막에 그 축을 이용해서 원래 이미지를 새로운 좌표 공간으로 매핑시켜주면 되겠다는 결론을 얻었습니다.
우선 x, y, z 좌표를 identity matrix 로 표현한 뒤 R^T * AXIS 를 통해 새로운 축 AXIS’ 를 구할 수 있고, 회전을 시키고 싶은 만큼 위 연산을 반복해준 뒤 forward mapping 을 해주는 것으로 빠르고 훌륭한 품질을 보여주도록 구현하는걸 성공했습니다.

위 이미지는 512×512 사이즈의 lena 이미지를 z축을 기준으로 45도만큼 회전시킨 결과입니다. 왼 쪽은 단순히 forward mapping 을 해준 것이고 오른쪽은 weighted sum 을 이용해서 forward mapping 을 개선해준 것입니다.

결과적으로 Photoshop 등을 이용한 만큼 훌륭한 이미지를 얻어낼 수 있는 것을 확인할 수 있습니다.

Other Results

아래 이미지는 x 축, y축, z축을 기준으로 순서대로 30도씩 회전시킨 이미지입니다. 이런 식으로 계산을 하려면 순서를 뒤집어서 z축, y축, x 축 기준으로 30도씩 회전을 시켜주면 됩니다.

다음은 x축으로 30도, y축으로 60도 만큼 돌린 결과

실제 구현 코드에 관심이 있으신 분들은 아래 링크를 방문하시면 되겠습니다. 이런 걸 하나하나 구현해볼 때마다 느끼는 거지만 openGL 같은 라이브러리를 설계하신 분들은 상상하기 힘들 정도로 똑똑한 것 같아요.

소스:
https://github.com/Tee0125/snippet/tree/master/rotation3d

CG: Perspective Projection

HCI 과제 덕에 심심찮게 프로그래밍을 하게 되네요. 첫 과제 였던 3D rotation 관련을 구현하는 것도 상당히 흥미로웠지만, 두번째 과제인 Perspective Projection 를 구현하는 것은 정말 멋진 경험이었다고 생각합니다.

지난 며칠간 꽤나 재밌게 프로그래밍을 했던 관계로 블로그에도 살짝 정리해보는게 어떨까 하는 생각이 들었는데, 막상 쓸려니 내용이 잘 전해질지 의문이네요.

What is the Perspective Projection?

Perspective Projection 이란 아래의 왼쪽 이미지를 오른쪽 이미지 처럼 변화시키는 것을 얘기합니다. 꼭 저렇게 비뚜러진 이미지를 바로잡는것은 아니고, 이미지가 투영되는 면을 변화시키는 것이라고 생각하시면 됩니다.

이해를 돕기 위해 wikipedia 에서 이미지를 하나 가져왔습니다. 아래 이미지의 연보라색 면이 상이 맺히는 곳이라고 할 때, perspective transform 은 그 보라색 면을 이동시킨 것 같은 효과를 주기 위해 사용합니다.

How to get a projection matrix.

기본 적으로 Perspective Transform 을 위한 식은 다음과 같습니다.

homogenious coordinate 를 사용하고 있으니 x’ 와 y’ 에 관한 식은 아래와 같이 바꿔쓸 수 있습니다.

이를 정리하면 다음과 같은 꼴로 만들 수 있고,

우리가 값을 알고 싶은 변수들은 a, b, c, d, e, f, g, h 이렇게 8 개이므로, (x, y) 와 그에 대응되는 (x’, y’) 쌍을 4개만 알고 있으면 projection matrix 를 구할 수 있습니다. 이를 구하기 위한 매트릭스는 아래와 같습니다.

남은 건 8×8 matrix 의 inverse matrix 를 구한 뒤 뒤 쪽의 매트릭스에 곱해주는 것 뿐이군요.

Implementation of Perspective projection

이제까지 Perspective Transform 을 위한 매트릭스에 대해 알아봤습니다. 이제는 실제 구현을 해보는 것만 남았네요. 위에서 알아봤듯이 Perspective matrix 를 구하려면 matrix multiplication 과 inverse 를 위한 인터페이스가 필요합니다.

matrix multiplication 의 경우 서로 곱할 수 있는 형식인지를 체크한 뒤 단순한 계산을 하면 되고, inverse 는 gauss elimination 을 이용 reduced row echelon form 으로 만들어주는 것을 통해 쉽게(?) 구해낼 수 있습니다.

위의 두 가지까지 구현했다면, 이제 warping 만을 구현하면 되겠습니다. 이 warping 은 크게 두가지 방법을 통해 구현할 수 있습니다.

forward mapping

forward mapping 은 말 그대로 src 의 x, y 좌표에 대하 dst 의 x’, y’ 를 계산 한 뒤 값을 채워주는 방식입니다. 간단히 pseudo code 로 표현하면 다음과 같이 표현할 수 있겠네요.

근데 막상 구현을 해놓고 보면 pixel 이 정수단위이기 때문에 아래와 같이 hole 이 발생하는 것을 확인할 수 있습니다.

backward mapping

위에서 얘기한 hole 을 방지하기 위한 방법 중 하나로 backward warping 이란 것이 있습니다. forward warping 에서 src 의 좌표를 기준으로 dst 의 좌표를 계산했다면, backward warping 에서는 dst 의 좌표를 기준으로 src 의 좌표를 계산하게 됩니다.
간단하게 pseudo code 로 표현하면 아래와 같이 되겠습니다.

간단히 코드만 봐도 예상할 수 있겠지만 backward_warping 을 해주게 되면 hole 은 확실하게 없앨 수 있습니다. 결과 이미지는 아래와 같은데, 아주 깔끔한 결과가 나오지는 않았습니다.

forward (or backward) warping with interpolation

forward warping 을 하게 되면 hole 이 생기게 되고, 단순한 backward warping 을 하게 되면 이미지의 화질 저하가 발생하게 되는데, interpolation 을 사용하게 되면 이를 조금 더 개선할 수 있습니다.

전 linear-interpolation 을 사용해보았는데, 설명하기는 복잡하니 관심있으신 분은 저 아래 첨부할 소스를 참고해보시면 좋겠습니다. 결과는 아래와 같이 나옵니다.

우선 interpolation 을 이용한 forward warping 입니다. 복잡하게 하기는 귀찮고 해서 대강 구현했더니, hole 이 줄기는 했지만 여전히 존재하고 있습니다.

다음은 backward warping 에 linear interpolation 을 적용한 결과입니다. hole 도 없고, 보기에 상당히 괜찮아진 것을 확인할 수 있습니다.

소스코드:
https://github.com/Tee0125/snippet/tree/master/perspective_projection
참고자료:
http://en.wikipedia.org/wiki/Perspective_%28graphical%29
http://en.wikipedia.org/wiki/Gaussian_elimination
p.s) 부동 소숫점 연산에서 x – x/x*x = 0 이라는 것이 보장되질 않더군요. 코드 한 줄 줄일려다가 디버깅을 30분동안 해야했습니다. -_ㅜ

이쁜 아이콘 배포 사이트~

  1. Silk Icons: http://www.famfamfam.com/lab/icons/silk/
  2. Intefrace Lift: http://interfacelift.com/

Silk IconCreative Commons Attribution 2.5 License 로 배포되고 있는 16×16 아이콘으로 애플리케이션의 툴바라거나 웹페이지 버튼으로 쓰기 적당한 아이콘들 이다. 사용료는 $0.0 지만 굉장히 높은 퀄리티를 가지고 있기 때문에 활용도는 상당히 높을 것 같다.
그리고 Interface Lift 는 Mac OS X 와 MS Windows 용 고품질 아이콘들을 구할 수 있는 곳! Mac 용 VLC 아이콘이나 Mplayer 아이콘을 인터페이스 리프트에서 구한 아이콘으로 대체해버렸는데 굉장히 만족스럽다. 히힛