며칠 전 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 같은 라이브러리를 설계하신 분들은 상상하기 힘들 정도로 똑똑한 것 같아요.

소스:
http://trac.unfix.net/browser/snippet/rotation_3d

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 로 표현하면 다음과 같이 표현할 수 있겠네요.

for( y = 0 ; y < height ; y++ ){ for( x = 0 ; x < width ; x++ ){ x' = (ax+by+c) / (gx+hy+1); y' = (dx+ey+f) / (gx+hy+1);   dst[y'][x'] = src[y][x]; } }

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

backward mapping

위에서 얘기한 hole 을 방지하기 위한 방법 중 하나로 backward warping 이란 것이 있습니다. forward warping 에서 src 의 좌표를 기준으로 dst 의 좌표를 계산했다면, backward warping 에서는 dst 의 좌표를 기준으로 src 의 좌표를 계산하게 됩니다.

간단하게 pseudo code 로 표현하면 아래와 같이 되겠습니다.

for( y' = 0 ; y' < height ; y'++ ){ for( x' = 0 ; x' < width ; x'++ ){ x = (ax'+by'+c) / (gx'+hy'+1); y = (dx'+ey'+f) / (gx'+hy'+1);   dst[y'][x'] = src[y][x]; } }

간단히 코드만 봐도 예상할 수 있겠지만 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 도 없고, 보기에 상당히 괜찮아진 것을 확인할 수 있습니다.

소스코드:
http://trac.unfix.net/browser/snippet/image_projection/

참고자료:
http://en.wikipedia.org/wiki/Perspective_%28graphical%29
http://en.wikipedia.org/wiki/Gaussian_elimination

p.s) 부동 소숫점 연산에서 x - x/x*x = 0 이라는 것이 보장되질 않더군요. 코드 한 줄 줄일려다가 디버깅을 30분동안 해야했습니다. -_ㅜ

어제 술을 꽤 많이 마신데다가 아침에 일이 있어서 잠을 좀 못잤더니 머리가 아프다.

데스크탑은 여전히 화면이 나오질 않고, A/S 를 받기 위해선 메인보드를 들어내야 할 것 같은데 너무나도 귀찮다. 내가 왜 이런 짓을 해야하는 생각이 들었고, 데스크탑 관련된 것들을 전부 팔아버리고 15인치급 x86 노트북을 사서 쓸까 하는 생각까지 들고 있다. 연구실 형 한 명이 맥북 프로를 사신 관계로 요새 간간히 맥북 프로를 구경해보고 있는데 역시나 매력적이다.

문제는 그걸 지를만한 여유자금이 있지는 않다는 거…

동기들 중에 벌써 컨퍼런스에 낼 논문을 쓰고 있는 사람들이 나오기 시작했다. 난 아직 실험도 채 다 못했는데… 정확하겐 아이디어 검증조차 –;;

왠지 뒤쳐지고 있는 것 같아서 조급해진다.

HCI 수업에서 벌써 과제가 하나 나왔다. 이미지를 읽어서 특정 각도만큼 돌리는 프로그램을 작성하는 것등 3D rotation 과 관련된 것들인데, 오랫만에 코드를 짜보니 재밌다. 물론 짜야했던 코드 양이 많지 않았고 (7줄 남짓; ) 에러 없이 한 번에 구현을 성공해서 더 재밌었는지도 모르겠다. 한동안 프로그래밍과 멀어져 있었는데 아직 녹슬지는 않은 거 같아서 다행이다.

임베디드 소프트웨어 수업과 내장형 시스템 수업에서는 ARM 의 conditional execution[1] 과 관련된 내용을 들었는데, 참 흥미롭다. Computer Architecture 상에서 Conditional branch 가 일어나게 되면 pipeline hazard 가 발생하게 되고, 실제 성능에 큰 악영향을 끼치게 되는데 conditional execution 을 통해 분기를 줄이는 동시에 더 적은 양의 코드로 똑같은 동작을 수행할 수 있도록 만드는 기법이 참 재밌어 보인다.

그 외에도 Havard Architecure 와 폰노이만 아키텍쳐의 차이 등 어설프게 알고 있던 내용들이 좀 정리되는 것 같어서 나름 재밌다. 컴퓨터 아키텍쳐에 관한 내 짧은 지식을 가지고 상상해봤던 내용들이 실제 구현되어 있는 것들과 나름 비슷하다는 사실이 너무나도 신기하다. 이 쪽으로 전공을 했어도 재밌었을 거 같다는 생각이 들기 시작한다.

그나저나 내장형 시스템이랑 임베디드 소프트웨어 이 두 과목이 모두 ARM 수업이다 보니 내용이 많이 겹친다. 월요일에 듣고 수요일에 리뷰 받는 기분이랄까 -_-; 뭐 엄한 시간표를 짠 대신 약간의 보상이라고 생각해야겠다.

그냥 심심해서 잡담겸 포스트… 오늘의 수다 끝!!!

[1] Conditional execution 의 예를 들어보면 아래와 같음.
pseudo code:
if( R0 == 0 ) R1 = 1; else R2 = 2;   Re=3;

Without conditional execution
cmp r0, 0 jnz IDX_ELSE mov r1, #1 jmp IDX_END IDX_ELSE: mov r2, #2 IDX_END: mov r3, #3

With conditional execution
cmp r0,0 movz r1, #1 movnz r2, #2 mov r3, #3

분명히 파워북에 LCD 를 연결하면 잘 나오는데 반해 데스크탑에 연결하기만 하면 화면이 안나오는 걸로 보아 그래픽 카드 고장일 거라고 단정지었고, 그래픽 카드만 뽑아서 A/S 를 보냈었다.

그런데 A/S 가 제대로 안된건지… 아님 메인보드의 PCI-E 슬롯에 문제가 있는건지 여전히 화면은 안나온다. 해야할 것들이 많은데 데스크탑이 말썽을 부리니 너무 피곤하다.

저 그래픽카드를 그대로 학교로 가져간 뒤 학교에 있는 컴퓨터에 꼽아서 화면이 나오면 그래픽카드는 멀쩡한 거라고 생각하면 될 듯 싶고, 학교에 있는 컴퓨터에 꼽아도 화면이 안나오면 A/S 를 제대로 처리 안해준 거라고 보면 될 듯…

문제는 만약 학교에 있는 컴터에 그래픽카드를 꼽아서 화면이 잘 나올 때 -_-;; 학교서 쓰던 지포스를 가져와서 집에있는 컴퓨터에 꼽아봐야 하는 수고가 추가로 필요할 것 같다.

온게임넷 시청이 불가능해진 지 2주일째… 매우 까칠해지고 있다.

요새 h.264 로 scalable coding 된 hd 급 영상을 다루는 프로젝트를 하고 있는데, 신입생에게 지급된 펜티엄4 2.8Ghz 따위로는 매우 버거움을 느끼고 있었습니다. 하지만 다행히도 제 컴퓨터를 새로 구입해도 된다는 허락을 받아서 70만원 한도내에서 신나게 견적을 내고, 프로젝트 카드를 이용 어제 새 컴퓨터를 확 질러버렸습니다.

ssse3 명령어인 phaddd 등을 이용하면 좀 더 빠르게 구현할 수 있는 것들도 있고 예산도 충분히 책정되고 해서, core2 duo E6400 에 2GB Ram 을 꼽아줬더니 이거 컴퓨터가 날라다니는군요. 이제는 리붓도 v3도 두렵지 않습니다. (그렇지만 safenet + v3 조합은 여전히 깔기가 싫기에 프록시는 계속해서 사용하고 있습니다. 캬캬캬!)

그나저나 열혈 어셈질을 해봐도 겨우 10% 정도밖에 성능 향상을 보이지 않았던데 반해, 70만원으로 디코딩 시간이 1/4 로 줄어버렸습니다. 목표치에 도달하는 가장 좋은 방법은 펠티어 소자를 이용한 슈퍼 쿨러 + 극한 오버가 아닐까하는 생각이 드네요. -_-;

뭐 하튼! 저 컴터 업글했어요!!! 이거이거 연구실에서 발이 안떨어지는군요. -_ㅜ

p.s) cpuid 를 확인해보니 sse4 가 지원된다고 나와있던데, sse4 에는 또 어떤 명령어가 추가되었을지 흥미진진하군요.

하드 날린 사건을 시작으로 계속 컴퓨터 주변기기들이 반항을 하고 있다. 4 년간의 데이타를 날리고 실의에 빠져 영화나 다운받자는 생각으로 eMule 을 깔고 한 3일동안 풀타임 p2p 세상을 만끽했더니, 가만히 있어도 모레시계가 돌아가고 별로 한것도 없는데 스왑은 640MB 씩 사용… 내 데스크탑이 바보가 되버렸다!! 떠있는 프로그램이 5개가 채 안되는데 리소스가 모잘라서 파이어폭스를 실행 못시키겠다면 나보고 어쩌란거냐!

하튼 우울한 마음을 안고 포멧을 했는데 이제는 s-ata 가 문제!! 윈도우를 설치할 때 oem 디스크를 넣고 3rd party 드라이버로 s-ata 를 잡는데까지는 문제가 없었는데, 파티션을 정리해주고 인스톨 시작하니 s-ata 드라이버를 복사할 수 없다는 에러 발생!! 예전엔 잘 됐었는데 왜 그런지 모르겠다. 다른 이미지를 구워서 재시도를 해봤으나 여전히 에러;; 비굴하게 누나방 컴퓨터에 꼽아줬던 40기가 IDE 하드를 다시 뺐어와야만 했다. 그냥 시스템 하드로 40G 짜리 시게이트 IDE 하드를 쓰고 120G 짜리는 자료 정리용으로 쓰면서 250G 짜리 하나를 추가해서 백업용으로 써야겠다. 하드랙도 이쁘장 하게 하나 더 사다 껴놨으니 이제 디스크만 사면 될 듯 -_-!!

하튼 어찌어찌 윈도우를 다 깔고 프로그램을 대강 세팅한 담에 외장 하드를 다시 맥에 연결해봤더니 -_-;; 마운트가 되지 않는다. 에러메시지를 추적해보니 예전에 하다만 트랜잭션을 마무리 하고 싶은데 타임아웃이라신다 -_-;; 시스템 하드를 제외한 하드에 남아있던 데이타들을 모두 한쪽에 몰아주고, 깔끔하게 zero-fill 을 해줘야만 했다 -_-;; 역시 하드 관련된 문제는 low level format 이 최고다 -_-;;

여기서 끝났음 그나마 괜찮았을 텐데, powerbook 에서 갑자기 bluetooth 모듈을 못찾겠다고, bluetooth 를 사용할 수 없다신다. 뭐 찾아보니 나말고도 비슷한 문제를 겪은 사람들이 꽤 있었던 듯! 설치 디스크등으로 부팅하는 방법이나 PRAM 소거로 효과를 보는 경우도 있다는데, 나는 효과가 없었다;; 흑흑… CD 쌓아놓은 걸 뒤적거리다 처음 파워북을 살 때 받았던 하드웨어 진단용 시디 발견!! 지푸라기라도 씹어먹는 기분으로 고 녀석으로 부팅해봤는데 도대체 어떻게 쓰는건지 모르겠다. 리눅스를 하나도 모르는 사람에게 리눅스 콘솔을 던져준 상황과 비슷한 상황 -_-!! 에 모르겠다 싶어 그냥 냅다 리붓을 했는데 갑자기 살아난 블루투쓰;;

뭔가 오랫만에 한 영양가 없는 삽질이 아닌가 싶다. 원인도 모르고 해결책도 모르고 그냥 데스크탑이랑 외장하드 / 파워북 에게 농락당한 기분이다. 진짜 컴퓨터들이 밉다 -_-;;

p.s) 윈도우 깔아놓고 쾌적하게 쓸라면 슬슬 업그레이드가 필요할 거 같다 -_-; 요새 메모리 512M 로는 어디 뭐 작업할 엄두도 못낼 듯 -_-;; 우선 휴학했으니까 대강 버텨보고 복학할 때를 노려봐야지;;