Category: Graphics

Computer graphics theory

CG: dithering

팩스에서 처럼 이미지를 흑/백 으로만 표현할 수 있는 경우에도 어느 정도의 명암을 표현하기 위한 방법으로 아래와 같은 오리지널 이미지가 있을 때…

한 픽셀 값은 0~255 사이의 값을 가진다고 하고, 128 이상의 값은 하얀 색으로, 128 미만 값은 검은 색으로 표현하면 결과는 다음과 같다.

보다시피 디테일은 거의 사라져버리기 때문에 이런 것을 피하기 위해 디더링이란 기법을 사용하곤 한다. 수식으로 이를 표현해보자면 다음과 같고…

말로 설명하자면 랜덤 값을 더해준 뒤 128 을 기준으로 Thresholding 을 한다! 정도로 표현이 가능할 듯… 이론적으론 매우 간단하지만 효과는 확실하다. -16~16 의 랜덤 값을 이용하여 dithering 한 결과는 다음과 같다.

-32~32 사이의 랜덤 값을 이용할 경우는…

확실히 좀 디테일이 조금 생겨나는 것을 확인할 수가 있다. 장비들이 좋아지면서 이런 식의 트릭들에 대한 연구는 사라져가는 것 같다. -_ㅠ
위 테스트에 사용한 코드:

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 모두 구현했지만 이상하게 관련된 실험은 손에 잡히질 않고 있다. -_-; 아악;;

Math: line fitting

만약 서로 다른 2개의 (x,y) 쌍을 가지고 있다면 아래와 같은 직선의 방정식을 계산해낼 수 있습니다.

이를 아래와 같은 매트릭스 형태로 표현할 수도 있습니다.

그런데 (x,y) 값을 2 쌍보다 더 많이 알고 있다면, 해가 구해낼 수 없게됩니다. 이를 over constraint 라고 하며, over constraint 상태에서 가장 에러가 작은 직선의 방정식을 구해내는 것을 line fitting 이라고 부릅니다.

line fitting 을 하는 방법은 크게 2가지 방법이 있습니다. 첫번째는 에러를 최소화 하는 계수 a, b 를 찾기 위해 편미분을 이용하는 것이고, 두번째로는 pseudo inverse 를 이용하는 방법입니다.

line fitting with differencial equation

편미분을 통해 최적의 직선을 찾아내기 위해 우선 Error 를 아래와 같이 정의해 봅시다.

2차 곡선의 최소값은 기울기가 0이 되는 지점에 있으므로 a, b 각각에 대해 편미분을 한 뒤 기울기가 0 이 되는 지점을 찾습니다.

위 식을 정리하면 아래와 같은 매트릭스로 표현이 가능하며,

역함수를 양 변에 곱해주게 되면 간단히 계수 a, b 를 구할 수 있게 됩니다.

line fitting with pseudo inverse

지금까지 편미분을 이용한 line fitting 을 알아봤는데, 이 경우는 손으로 계산해야하는 것들이 많았지만 pseudo inverse 를 이용하면 계산을 모두 컴퓨터에게 맡길 수 있기 때문에 훨씬 쉽게 직선의 방정식을 구할 수 있습니다.

pseudo inverse 를 이용한 방법을 알아보기 앞서 위 매트릭스를 간단히 아래와 같이 표현하기로 하겠습니다.

X 에 대한 inverse 를 계산할 수 있다면 간단하게 계수 a, b 를 구할 수 있겠지만 불행히도 X 는 inverse 를 가지지 못하기 때문에 X 에 자신의 transpose 를 곱해준 뒤 역행렬을 구하는 방법을 사용하게 되며, 이런 식으로 역행렬을 구해내는 방법을 pseudo inverse 라고 합니다.

식을 정리하고 나니 아래와 같은 간단한(?) 행렬 연산을 통해 계수 a, b 를 계산해낼 수 있겠습니다.

Result

아래 그래프는 (1.1,0.7), (2.1,1.0), (4.3,3.2), (-1.2,-1.1), (-2.4,-2.1), (-3.5,-3.4) 이렇게 6개의 점에 대한 line fitting 결과를 gnuplot 을 이용해서 그래프로 만든 것이며, 6개의 점 사이를 지나는 직선이 구해진 것을 쉽게 확인할 수 있겠습니다.

p.s) 매트릭스 관련된 오퍼레이션들을 다 짜놨더니 이거이거 이런 간단한 것들 돌려보는건 일도 아니네요. 요 근래 뭔가 조급해하고 있었는데, 맘잡고 기초부터 탄탄히 해놓는게 나을 거 같다는 생각이 들어서. 욕심을 줄이고 있습니다. 후훗

코드: https://github.com/Tee0125/linear_regression/blob/master/numpy/numpy_linear_regression.py

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

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 변환을 빨리할 수 있지 않을까 하는 생각도 해봤지만 실제 결과는 참담…

처음 짜본 wavelet transform…

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


histogram 을 보면, 값들이 낮은 값들로 집중되어 있는걸 확인할 수 있습니다. 역시 이미지 압축을 위해 사용할만 하네요. 😉

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 레지스터 값을 백업하지 않고 저렇게 사용해도 되는지는 잘 모르겠지만 –;; 하여튼 저 코드에 한해서는 별 문제 없으니 패스~ 꺄홋!!