[ 2차원 DCT ]
이제 여러분은 1차원 배열에 DCT를 적용하는 법을 알아보았다. 이미지에도 DCT를 적용할 것이라고 했는데, 한 가지 문제점에 봉착한다. 이미지는 2차원 배열이기 때문이다. 2차원 배열에 DCT를 적용하려면 어떻게 해야 할까?
1차원에서 정의된 함수를 f(x)라고 나타냈다. 이번엔 2차원이니까 f(x, y)라고 하면 된다. f(x)를 나타내기 위해서는 아래와 같은 함수들을 이용했다.
|
1 |
cos x |
cos 2x |
cos 3x |
… |
2차원 함수 f(x, y)를 위해선 아래와 같이 확장하면 된다.
|
1 |
cos x |
cos 2x |
cos 3x |
… |
|
cos y |
cos x cos y |
cos 2x cos y |
cos 3x cos y |
… |
|
cos 2y |
cos x cos 2y |
cos 2x cos 2y |
cos 3x cos 2y |
… |
|
cos 3y |
cos x cos 3y |
cos 2x cos 3y |
cos 3x cos 3y |
… |
|
… |
… |
… |
… |
… |
y에 대한 코사인함수를 세로줄에 적어넣고 구구단 표 완성하듯이 나머지 부분을 채운 것 뿐이다. 2차원 DCT의 식은 아래와 같다. x방향으로 N개, y방향으로 M개의 점들이 있다고 하면,
< 2차원 DCT >
복잡하기 서울역에 그지없다. 게다가 모든 C의 값을 구하려면 NM개의 C에 대해 NM번의 연산을 해야 된다. 입력 데이터의 4승에 해당하는 시간, 가뜩이나 계산이 느린 파이썬이라면 허덕댈 만도 하다. 어떻게 개선할 방법이 없을까? 식을 보아 하니, Σ기호도 2개, cos도 비슷하게 생긴 녀석이 2개. 어떻게 간단해 질 것 같기도 하다.
다음과 같이, f에 x방향에 대해서만 DCT를 적용한 결과를 
이 녀석에 y방향으로 DCT를 적용해 보자.
↓ 
원래 2차원 DCT의 정의와 완전히 똑같아진 것이 보인다. x좌표에 대한 변환을 한 뒤 y좌표에 대한 변환을 하면 2차원 DCT가 완성되는 것이다. 우리는 이미 1차원 DCT를 위한 함수를 확보했으므로, 2차원 DCT는 문제없다.
|
|
x방향 DCT → |
|
y방향 DCT → |
|
변환을 되돌려주는 IDCT도 마찬가지이다. 각 좌표마다 1차원 IDCT를 적용하면 되는 것이다. Σ의 순서는 바뀌어도 상관없으므로, x방향과 y방향을 적용하는 순서는 상관이 없다.
|
|
y방향 IDCT → |
|
x방향 IDCT → |
|
1차원에서의 DCT만 알고 있으면 2차원, 나아가 n차원의 DCT는 거저 먹는 셈이다.
[ Numpy를 이용하여 2차원 DCT 적용하기 ]
이미지 프로세싱 컨텐츠의 앞부분에서 회선 기법을 적용하는 코드를 실행해 본 학생이라면 파이썬의 느리디 느린 숫자 계산에 넌덜머리가 났을 것이다. 고급 언어인 파이썬의 계산은 느릴 수 밖에 없고, 그래서 Numpy라는 라이브러리가 흔히 사용된다. 이 모듈은 파이썬만으로 실행하면 자칫 느려질 수 있는 수치 계산을 빠르게 하기 위한 여러 모듈을 제공하는데, 우리는 여기서 DCT를 위한 함수를 사용할 것이다.
1차원 DCT을 공식 그대로 계산할 경우, N개의 자료 각각에 대해 N번의 연산을 수행해야 하므로 N2에 비례하는 시간이 소요된다. 하지만 Numpy라이브러리에서 제공하는 알고리즘을 이용하면 N log N에 비례하는 시간 만에 DCT를 수행할 수 있다. 이것을 빠른 코사인 변환(FCT, Fast Cosine Transform)이라고 부른다.
사실 Numpy에서 제공하는 함수는 FCT랑 조금 달라서, 다음처럼 FCT를 위한 함수를 정의했다. Numpy에서 제공하는 FFT함수는 복소수를 이용하기 때문에 다소 복잡하다. 여러분은 이 소스를 이해할 필요 없이 그냥 사용하면 된다.
|
def FCT(array): def IFCT(array): |
이 함수를 이용해서 FCT를 적용해 보자.
|
>>> FCT( [ 1, 2, 3, 4, 5 ] ) |
FCT와 IFCT가 제대로 동작하는 것이 보인다. 지금까지는 많아야 10개의 데이터를 사용했지만, 이미지프로세싱에서는 수만 개의 픽셀들을 처리해야 하고, 파이썬으로 직접 만들었던 DCT함수와 FCT함수의 속도차는 엄청나게 커진다.
DCT의 결과가 조금 다른 것도 보이는데, 이 FCT함수가 DCT-1이기 때문이다. 흔히 말하는 DCT가 DCT-2이고 IDCT가 DCT-3이라고 했던 것을 기억할 것이다. 결과는 조금 다르지만, 데이터의 각 주파수 성분을 얻어온다는 개념은 똑같다. DCT-1은 [0, π] 구간을 N-1개로 분할해서 생기는 N개의 경계에 점을 찍었을 때를 가정한다.
PIL의 PixelAccess 객체pix가 있다고 할 때, 다음의 두 단계로 2차원 DCT를 완료할 수 있다.
|
mid=[FCT([pix[n,m] for n in range(N)]) for m in range(M)] |
코드가 이렇게 간단할 수 있는 건 파이썬의 "리스트 조건제시법(List Comprehension)" 문법 덕분이다. 자세한 내용은 http://www.network-theory.co.uk/docs/pytut/ListComprehensions.html 에 있는 예제들을 참조하자.
첫 줄에서, [pix[n,m] for n in range(N)]은 PixelAccess 객체에서 m번째 열을 뽑아서 리스트로 만든 것이다. 여기에다가 FCT를 적용한 것을 range(M)에 있는 m에 대해 리스트로 만들면 중간 단계의 결과가 완성된다. 같은 방법으로 각 열을 뽑아서 FCT를 적용시키면 2차원 DCT완성!
이제 result에 적절한 수정을 가한 뒤 다시 IDCT를 적용하면, 앞서 말했던 주파수 영역에서의 이미지프로세싱을 할 수 있다. 2차원 IDCT도 똑 같은 방식으로 구현하면 된다.
|
mid=[IFCT([result[n][m] for n in range(N)]) for m in range(M)] |
이제 여러분은 이미지를 주파수 영역에서 갖고 놀 준비가 완료되었다.
It's showtime!
[ 연습문제 4 ]
result로 주어진 DCT결과를 화면에 보여줄 수도 있다. result에 있는 숫자들을 각 픽셀값으로 가지는 이미지를 만드는 것이다. 이 때 result의 숫자들은 0~255에 속해 있지 않으므로, 적절히 바꿔주는 절차도 필요하다. result의 0을 회색(128)으로 나타내고, 음수를 더 어둡게, 양수를 더 밝게 나타내도록 해 보자. 고양이 사진의 DCT결과를 이런 식으로 그림으로 나타내면 아래처럼 된다. 이것을 주파수 스펙트럼(Frequency Spectrum)이라고 한다.
< 고양이 사진의 DCT >
그림의 왼쪽 위가 낮은 주파수 영역의 정보이고, 거기서 멀어질수록 높은 주파수 영역의 정보이다. 코사인 급수에서 주파수가 커질수록, 각 계수들이 부호가 반복되며 점점 작아졌던 것을 기억하자. 여기서도 왼쪽 위에서 멀어질수록 회색에 가까워지므로, 더 숫자들이 작아진다는 것을 확인할 수 있다.
첨부한 DCT.pyw 파일을 이용하면 이미지를 열어서 그것에 DCT와 IDCT를 마음대로 적용할 수 있다. 다만 계산의 편리를 위해 이미지를 흑백으로 바꾸어서 계산한다. 주석을 많이 달아 두었으므로, 프로그램의 소스 코드를 잘 읽고 이해하길 바란다.
invalid-file(문제 1)
고양이 사진을 열고 DCT를 적용하자. 프로그램에서DCT의 결과는 클래스 변수 Result에 저장된다. Result[0][0]의 값을 0으로 만들고 다시 IDCT를 적용해 보자. 어떤 결과를 얻었는가? 다시Result[0][0]값을 300, 500, 700 등으로 바꿔 보면서 결과를 확인해 보자. 이미지가 Result[0][0]의 값에 어떤 영향을 갖는 것으로 추측되는가?
(문제 2)
고양이 사진을 열어서 DCT를 적용한 다음 다시 한 번 DCT를 적용해 보자. IDCT와 DCT가 서로 매우 비슷하기 때문에 DCT만 두 번 적용해도 처음과 비슷한 결과를 얻게 된다. 하지만 처음 고양이 이미지랑은 다소 차이가 있다. 이렇게 되는 이유를 문제 1의 답과 관련해서 추측해 보자. (힌트 : 왼쪽 위에 가까운 영역에서는 DCT의 결과가 흰색, 검정색 등으로 나타났다.)
[목차] 이미지프로세싱 - 시작
[이전] 주파수 영역에서의 처리 - (4) 삼각함수의 합으로 나타내기 2
[다음] 주파수 영역에서의 처리 - (6) 주파수 영역에서 이미지 주무르기
