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분동안 해야했습니다. -_ㅜ

소스 공개: yuvplayer

예전 포스트에서 얘기한 적이 있던 제 yuvplayer 를 svn repository 에 추가했습니다. 관심이 있으신 분은 아래 링크를 따라가보시면 되겠네요.
http://trac.unfix.net/browser/yuvplayer
사실 한 달쯤 전에 올려뒀는데, 제 svn repository 는 저조차 잘 가보질 않기 때문에 아무도 몰랐을거라 생각합니다;; 흐흣~ Mac 용 버젼도 있는데, 이건 아직 넣고 싶은 기능들 중 구현을 안한 것들이 많아서 추가해두지 않았습니다.
visual studio 2005 기반으로 작업하다보니 프로젝트 파일등이 모두 vs2005 용이네요. 하여튼 uyuv, yuv444, yuv422, yuv420 등으로 된 파일을 플레이할 수 있고, 마우스 오른쪽 버튼을 누른 후 현재 프레임을 다른 포멧으로 저장하는 것도 가능합니다.
관련 포스트:
mac 버젼 – http://b.mytears.org/2007/06/541
windows 버젼 – http://b.mytears.org/2007/06/544

이쁜 아이콘 배포 사이트~

  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 아이콘을 인터페이스 리프트에서 구한 아이콘으로 대체해버렸는데 굉장히 만족스럽다. 히힛

YUVplayer for MS Windows

지난 이틀간 작업한 내 YUVPlayer for windows~! MFC + OpenGL 기반으로 작성되었고, 정말 아무 문제 없이 사용할 수 있을만큼 완성도 높게 작업해보기는 처음이 아닐까 싶다. (CUI 기반으로는 공개를 하고 있지는 않았지만 혼자 유용하게 쓰는게 몇 가지 있는데… GUI 기반으로는 정말 처음인 것 같다.)
단축키를 통해 모든 액션을 취할 수 있고, 드래그앤 드롭을 통한 파일 오픈 또한 가능하다. 게다가 _lseeki64 같이 64bit offset 을 사용하는 시스템 콜을 사용하고 있기 때문에 2GB 를 넘어가는 파일들도 문제 없이 플레이가 가능하다. (31GB 짜리 파일도 문제 없이 플레이가 가능한 것을 확인했음.)

위 스크린 샷은 기본적인 플레이 화면! CBitmapButton 을 통해 이쁜 플레이어 버튼을 만들었고, 여러가지 편법을 통해 –;; 사이즈가 조절되더라도 저 레이아웃이 그대로 유지되도록 만들었다.
Continue reading YUVplayer for MS Windows

OpenGL: texture vs glDrawPixels

openGL 을 사용해서 2D 이미지 데이타를 화면에 뿌려주는 방법은 대강 다음과 같이 세가지로 분류할 수 있는 것 같다.

  1. glBegin(GL_POINTS); glColor3i(…);glVertex3d(x0,y0,0); …반복; glEnd();
  2. texture 로 올려주고, 해당 texture 가 입혀진 quad 을 그려줌
  3. glDrawPixels 를 이용

첫번째 방법이야 그냥 저렇게도 가능하다는거지 실제 저렇게 사용할 일은 없다고 생각되고, 실제 빠르게 화면에 2D 이미지를 그려주기 위해서는 2번째 방법이나 3번째 방법을 사용해야할텐데, 저 중에 어떤 걸 사용하는게 더 좋은 방법인지 확신이 들질 않는다.
우선 화면이 확대되었을 때 texture 를 사용할 경우 GL_LINEAR 등의 기본으로 제공되는 interpolation method 들이 있기 때문에 (약간 Blur 된 결과일지는 모르지만) 더 좋은 품질의 이미지를 얻을 수 있겠고, 화면이 다시 그려질 일이 있을 때 texture 데이타가 다시 전송될 필요가 없다는 장점이 있는 듯 싶지만, (texture 로 등록할 때 이미지 데이타는 비디오 메모리로 옮겨진다.) width 나 height 가 2^x 형태로 표현되어야 한다는 제약이 있다. 이게 만약 이미지가 크지 않다면 큰 문제가 되지 않겠지만 만약 HD Sequence 라면? 1920×1080 을 표현하기 위해 2048×2048 = 4MB 를 사용해야 하므로 반 정도의 공간이 낭비될 수밖에 없다.
glDrawPixels 는 다시 화면을 그려줘야할 때마다 이미지 데이타를 메인메모리->비디오메모리 로 복사해줘야 하는 문제가 있지만 만약 동영상 플레이어등을 만들 때 처럼 빠르게 화면이 전환되는 경우라면 이는 큰 문제가 되지 않을 듯 싶기는 하다. 물론 화면이 멈춰있는 상태라면 얘기가 다를 지 모르겠다. 또 이미지를 실제 크기보다 더 크게 표현할 경우 glPixelZoom 을 이용해 간단히 구현할 수 있지만 실제로는 픽셀 크기만 커지는 효과이지 interpolation 은 일어나지 않으므로 화질은 texture 를 사용할 때에 비해 떨어진다고 할 수 있을 듯…
뭐 하튼 뭘 사용하는게 더 좋은건지 인터넷을 열심히 찾아봤지만 뭐가 더 좋은지에 대한 정확한 답은 찾을 수가 없다. -_-!
p.s) yuv2rgb 변환 같은 것은 cg 를 이용해서 처리할 수 있는 것 같은데… 이 경우 texture 를 사용해야지만 가능 한 듯…
openGL 에 이미 4×4 matrix multiplication 은 구현되어 있으므로 color_matrix 를 사용해서 yuv2rgb 변환을 빨리할 수 있지 않을까 하는 생각도 해봤지만 실제 결과는 참담…

내 첫 cocoa application: yuv player

저번 주에 개인적으로 de-interlacing 관련된 발표를 준비하느라 논문에 있는 de-interlacing 기법들을 구현해서 실험을 했었는데, 맥에서 돌아가는 yuv player 를 못찾는 바람에 결과는 윈도우로 옮겨서 확인해야하는 불편이 있었다.
랩에 이미 충분히 쓸만한 yuvplayer 가 있기는 하지만 윈도우 전용이고, 내가 예전 신입생 과제를 하면서 만들었던 플레이어 역시 윈도우용;; 뭐 하튼 플레이어를 구현하는데 필요한 기반 테크닉은 다 갖추고 있었기 때문에 MFC + OpenGL 로 구현해봤던 것을 똑같이 Cocoa+OpenGL 로 구현해봤다.

메뉴를 이용해서 size 와 color format, frame rate 등을 준비할 수 있도록 만들었는데, size 와 frame rate 를 사용자가 직접 입력하는 것은 귀찮은 관계로 나중에 -_-;;
뭐 하튼 Zoom 하고 Drag And Drop 과 관련된 코드만 추가하고 나면 내가 구현하고 싶었던 모든 기능이 다 들어가는 거 같다. (Zoom 이야 glPixelZoom 을 사용하면 한방에 오케이니 흐흣)
XCode + Interface Builder 를 이용한 첫 결과물인데, 굉장히 오래전에 이미 나와있던 프로그래밍 인터페이스인데도 불구하고 굉장히 편리하게 프로그래밍이 가능해서 감탄을 해버렸다. 물론 MS 진영도 Visual Studio 2005 로 오면서 편리한 기능들이 꽤 많이 추가되긴 했지만, GUI Application 을 만들기 위한 IDE 로는 XCode + 인터페이스 빌더 쪽이 한 수 위인 듯…
MFC 나 Cocoa 나 진입 장벽이 꽤 높지만… 기본적인 테크닉을 익히고 나면 굉장히 강력하게 사용이 가능한 것 같다. 그리고 C 에 능숙하다면 다른 언어를 접하는 데도 그리 큰 어려움을 느끼지 않는 것 같다. 학부 시절 C++, Java 등에 눈길을 뺐기지 않고 주력 언어로 C 를 선택했던 게 탁월한 선택이었던 듯…
p.s) 코드를 좀 정리하고 sourceforge 등에 자리를 틀어볼까 싶네요. 🙂

처음 짜본 wavelet transform…

화상처리기초 수업 과제 때문에 처음으로 wavelet transform 을 구현해보았습니다. 아래 이미지는 wavelet 으로 변환된 512×512 사이즈의 lena

histogram 을 보면, 값들이 낮은 값들로 집중되어 있는걸 확인할 수 있습니다. 역시 이미지 압축을 위해 사용할만 하네요. 😉
소스코드: https://github.com/Tee0125/snippet/tree/master/wavelet

matrix multiply with mmx #2


대강 생각을 해보니 정말 mmx 를 이용해서 빠르게 연산을 하려면 위와 같이 하는게 가장 빠르겠군요. 다만 레지스터를 많이 쓰고 완전히 asm 코딩을 해야한다는 게 조금 귀찮겠군요. 😉
위의 다이아그램에 있는 과정을 통해 4×4 matrix * 4×4 matrix 의 한 row 씩을 계산해낼 수 있습니다. 대강 계산했을 때 3배 이상의 속도 향상이 있을거라고 예상되던데 과연~

코드로 옮기니 위와 같군요. 중간에 실수로 바이트오더를 헷갈려서 연산 결과가 뒤집혔었습니다. 정상적인 결과는 250 260 270 280 이 나와야 하는데 280 270 260 250 이 나와버리더군요. 아아 이거 다시 하고 싶은 작업이 아니네요;
흐흣 그래도 오랫만에 어셈블리 관련된 것들을 생각하고 있는데, 이것도 가끔 하니까 재밌네요. 근데 길어지면 할만하지 않다는거 -_-!
p.s) 전체 연산 코드를 보고 싶으시면 http://mytears.org/resources/mysrc/c/mmx.c 를 보시길 😉

matrix multiply with mmx #1

몇 일 전에 썼던 글에서 테스트를 해본 내용을 바탕으로 4×4 matrix multiply 연산을 mmx 를 이용해서 구현해봤습니다.

위와 같은 c version 의 코드를 작성한 후 아래와 같은 asm version 으로 컨버팅을 해봤는데, 100000 번 반복해서 연산을 하도록 해본 결과 mmx 버젼이 c 버젼보다 3배 정도 빠르게 연산을 하는 것을 확인할 수 있었습니다. (-O0 옵션과 함께 컴파일 했을 경우)
하지만 -O3 옵션과 함께 컴파일하게 되면 asm 버젼은 무한룹에 빠진 듯한 모습을 보여줬고, c 버젼의 수행속도가 -O0 로 컴파일한 asm 버젼보다 빠른 현상이 발생했습니다. 이유는 알 수 없음 -_-;

8×8 matrix 는 뭔가 좀 더 생각해야할 것 같으니 나중에 정말 필요한 일 있을 때 구현을 해봐야겠습니다. -_-;
inline asm 작업을 하면서 eax 레지스터 값을 백업하지 않고 저렇게 사용해도 되는지는 잘 모르겠지만 –;; 하여튼 저 코드에 한해서는 별 문제 없으니 패스~ 꺄홋!!