이산 코사인 변환(Discrete cosine transform)

푸리에 급수⁠(Fourier series)⁠가 주기 함수⁠(periodic function)⁠를 사인파⁠(sinusoid)⁠들의 합으로 쓰듯, 이산 코사인 변환은 값 N개 $x_0, \ldots, x_{N-1}$을 코사인 N개에 계수를 곱해 더한 것으로 씁니다. k번째 코사인(k = 0, 1, …, N − 1)은 N칸 동안 반 바퀴를 k번, 곧 k/2바퀴 돕니다. 이 N개의 코사인 벡터⁠(vector)⁠는 서로 내적⁠(dot product)⁠이 0입니다. 서로 수직이고 0이 아닌 벡터 N개는 N차원 공간의 기저가 되므로, N개 값으로 된 어떤 데이터든 이것들에 계수를 곱해 더하는 방법이 꼭 하나 있습니다. 게다가 서로 수직이라서 계수 $X_k$는 데이터와 k번째 코사인의 내적 하나로 바로 구해지고(위 식), 거꾸로 되돌리기도 쉽습니다. 크기를 맞추면 변환 행렬⁠(matrix)⁠은 직교 행렬⁠(orthogonal matrix)⁠, 곧 길이와 각을 바꾸지 않는 변환(N차원 공간의 회전⁠(rotation)⁠이나 뒤집기)이라서 벡터의 길이(에너지)도 그대로입니다. 1974년 미국에서 연구하던 공학자 나시르 아메드, T. 나타라잔, K. R. 라오가 발표했습니다.

점을 위아래로 끌어 16개 값을 바꿔 보세요. 보기: . 변환: . 가장 낮은 진동수부터 개의 계수만 남기고 나머지를 0으로 버린 뒤 되돌린 것이 노란 곡선입니다.

계수 16개 가운데 개만으로 에너지의 를 담고, 값 하나당 평균⁠(mean)⁠ 오차(RMS: 오차를 제곱해 평균한 뒤 제곱근을 씌운 값)는 입니다.

매끈한 데이터에서는 이웃한 값이 비슷하니 빠르게 출렁이는 성분이 작고, 에너지가 낮은 진동수 몇 개에 몰립니다. 그래서 몇 개만 남겨도 거의 그대로 되살아납니다. 이웃한 값의 상관이 1에 가까운 단순한 모형(한 칸 떨어진 값끼리만 직접 닮는 1차 마르코프 모형)에서는, 데이터에 맞춰 구한 주성분 분석⁠(principal component analysis)⁠의 축이 DCT의 기저에 다가간다는 것이 알려져 있습니다. 차이는 DCT가 데이터를 보지 않고 미리 정해 둔 축이라 계산이 빠르고 축을 따로 보낼 필요가 없다는 점입니다. '잡음'을 고르면 에너지가 모든 진동수에 흩어져 있어 거의 줄일 수 없습니다.

왜 사인과 코사인⁠(sine and cosine)⁠을 다 쓰는 이산 푸리에 변환(DFT)이 아니라 코사인일까요? DFT는 16개 값이 끝없이 되풀이된다고 봅니다. 그래서 '경사'처럼 끝과 처음의 값이 다르면 경계에 큰 계단이 생기고, 그 계단을 흉내 내느라 높은 진동수가 많이 필요하며, 몇 개만 남기면 깁스 현상⁠(Gibbs phenomenon)⁠처럼 끝이 출렁입니다. DCT는 데이터를 거울에 비춰 이어 붙인 것을 변환하는 셈이라 경계에서 값이 끊기지 않습니다. '경사'를 고른 채 변환을 DFT로 바꿔 보세요. 같은 개수의 계수로도 노란 곡선의 양 끝이 크게 출렁이고, 그림 아래 문장에 적힌 오차가 커집니다.

JPEG은 그림을 8×8 화소 덩어리로 나눠 가로세로로 DCT를 하고(64개 무늬), 계수를 표에 적힌 수로 나눠 반올림하는 양자화⁠(quantization)⁠를 합니다. 높은 진동수일수록 크게 나눠 거칠게 남기는데, 눈은 좁은 영역의 빠른 밝기 변화에 둔하기 때문입니다. 그러면 0이 된 계수가 많아지고, 이것을 지그재그로 읽어 0의 길이와 나머지 값을 허프만 부호⁠(Huffman coding)⁠로 적습니다. 너무 세게 줄이면 덩어리 경계가 보이는 격자 무늬가 생깁니다. MP3와 AAC는 소리를 조금씩 겹치는 짧은 토막(창)으로 잘라 토막마다 변형된 DCT(MDCT)를 하고, 동영상 부호화도 비슷한 정수⁠(integer)⁠ 변환을 씁니다. 이런 변환들은 1965년 제임스 쿨리와 존 튜키가 널리 알린 고속 푸리에 변환(FFT)처럼, 문제를 절반 크기 둘로 쪼개 푸는 분할 정복⁠(divide and conquer)⁠으로 $N^2$번 대신 $O(N \log N)$번의 계산으로 끝낼 수 있습니다.

이어지는 곳. 양 끝이 막힌(열이 새지 않는) 막대의 열방정식⁠(heat equation)⁠을 풀면 온도가 바로 이 코사인 무늬들의 합으로 나타나고, 높은 진동수일수록 빨리 사라집니다. 열이 퍼지면 온도 분포가 매끄러워지는 것은 높은 진동수 성분부터 사라지기 때문이고, 높은 진동수를 버리면 매끄러워지는 것도 같은 원리입니다. 각 기저는 진폭⁠(amplitude)⁠과 진동수를 가진 사인파를 표본⁠(sample)⁠으로 뽑은 것이고, 변환 전체는 하나의 선형변환⁠(linear transformation)⁠입니다. 소리나 그림을 애초에 표본으로 뽑아도 되는 까닭은 표본화 정리⁠(sampling theorem)⁠가 말해 주고, 계수마다 몇 비트를 줄지, 곧 얼마나 거칠게 양자화할지의 이론적 한계는 율–왜곡 이론⁠(rate–distortion theory)⁠이 정합니다.