Tag: graphic

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

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