이산 코사인 변환

편집 역사 토론
수치해석 소프트웨어 마지막 수정: 2026-08-31 04:13:27

1. 개요[편집]

이산 코사인 변환
Discrete Cosine Transform
약칭DCT
제안Ahmed · Natarajan · Rao (1974)
실무의 주인공DCT-II(순변환) / DCT-III(역변환)
기저$\cos\bigl[\tfrac{\pi}{N}(n+\tfrac12)k\bigr]$ — 실수 직교
비용$O(N\log N)$, 8점은 곱셈 11회
쓰는 곳JPEG · MPEG · H.264 · HEVC · AAC(MDCT) · 고속 푸아송 솔버

푸리에가 신호를 원통에 감아 놓고 이음매를 못 본 척한다면, 코사인은 아예 거울을 대서 이음매를 없앤다.

이산 코사인 변환(discrete cosine transform, DCT)은 유한 길이 실수 신호를 코사인 함수만으로 이루어진 직교 기저로 전개하는 변환이다. 경계 조건을 어떻게 대칭 확장하느냐에 따라 DCT-I부터 DCT-VIII까지 여덟 종류가 정의되지만, 실무에서 “DCT”라고 하면 사실상 DCT-II 하나를 가리키며 그 역변환이 DCT-III다.

Xk  =  ∑n=0N−1xncos⁡ ⁣[πN(n+12)k],k=0,1,…,N−1X_k \;=\; \sum_{n=0}^{N-1} x_n \cos\!\left[\frac{\pi}{N}\left(n+\frac{1}{2}\right)k\right], \qquad k = 0,1,\dots,N-1

직교정규화한 형태로 쓰면 행렬 CC 의 성분이 Ckn=αkcos⁡[πN(n+12)k]C_{kn} = \alpha_k\cos\bigl[\tfrac{\pi}{N}(n+\tfrac12)k\bigr], α0=1/N\alpha_0=\sqrt{1/N}, αk≥1=2/N\alpha_{k\ge1}=\sqrt{2/N} 이고 C−1=CTC^{-1}=C^{\mathsf T} 가 된다. 즉 역변환이 전치이고, 그 전치가 곧 DCT-III다. 아메드·나타라잔·라오가 1974년에 이 변환을 제안하며 붙인 목표가 “카루넨-루베 변환(KLT)을 근사하되 데이터에 의존하지 않는 고정 기저”였는데, 그 목표가 얼마나 잘 달성됐는지는 오늘날 세상에 굴러다니는 이미지 압축 파일의 압도적 다수가 DCT-II 위에 얹혀 있다는 사실이 말해 준다.1

2. 왜 코사인인가 — 경계의 문제[편집]

이산 푸리에 변환(DFT)은 유한 신호를 주기 확장해서 본다. 길이 NN 신호를 그대로 반복시키면 xN−1x_{N-1} 다음에 x0x_0 이 붙으므로, 두 값이 다른 한 이음매마다 계단 불연속이 생긴다. 불연속이 있는 함수의 푸리에 계수는 O(1/k)O(1/k) 로만 감쇠하고, 몇 개를 잘라 되돌리면 이음매에서 깁스 진동이 튄다. 신호 자체는 멀쩡히 매끄러운데 “유한하게 잘랐다”는 사정 하나 때문에 스펙트럼이 지저분해지는 것이다.

DCT는 확장 방법을 바꿔서 이 문제를 없앤다. DCT-II가 암묵적으로 쓰는 것은 반표본 지점에 대한 짝수(거울) 확장이다 — n=−12n=-\tfrac12 과 n=N−12n=N-\tfrac12 을 축으로 신호를 접어 길이 2N2N 짜리 대칭 신호를 만든 뒤 그것을 주기 확장한다. 접힌 자리에서 값이 자기 자신과 만나므로 계단 불연속이 사라진다. 남는 것은 기울기의 꺾임(1차 미분 불연속)뿐이고, 그래서 계수 감쇠가 O(1/k)O(1/k) 에서 O(1/k2)O(1/k^2) 로 한 계단 빨라진다. 대칭 신호의 DFT는 허수부가 소거되어 실수만 남고, 그 실수부가 바로 코사인 합이다.

여덟 가지 변형은 결국 양 끝을 어디서 접을 것인가의 조합이다.

형좌·우 대칭축성격
DCT-I표본점 n=0n=0, n=N−1n=N-1끝점을 공유, 길이 NN 에 2(N−1)2(N-1) 주기
DCT-II반표본 −12-\tfrac12, N−12N-\tfrac12압축의 표준. 에너지 집중 최고
DCT-IIIDCT-II의 전치DCT-II의 역변환
DCT-IV반표본 좌·우 모두, 반주기 어긋남MDCT의 뼈대, 겹침 변환

여기서 정직하게 짚을 것 하나. 이 대칭 확장이 없애는 것은 인위적인 경계 불연속이지, 신호 안에 원래 있던 진짜 에지가 만드는 링잉이 아니다. 8×8 블록 안에 선명한 경계가 지나가면 DCT도 깁스 진동을 낸다. 그게 JPEG 글자 주변에 끼는 모기 잡음(mosquito noise)의 정체다.

3. 에너지 집중과 KLT[편집]

변환부호화가 이득을 보는 원리는 하나다. 에너지를 소수의 계수에 몰아넣고 나머지를 버린다. 어떤 변환이 가장 잘 몰아넣는가에 대한 답은 이론적으로 이미 나와 있다 — 신호의 공분산행렬 RR 의 고유벡터, 즉 KLT(주성분 분석과 같은 물건)다. 문제는 KLT가 데이터에 의존한다는 것이다. 기저를 매번 계산해야 하고, 복호기에 기저를 통째로 보내야 하고, 고속 알고리즘도 없다.

자연 영상의 인접 화소는 강하게 상관되어 있고, 이를 가장 단순하게 모형화한 것이 1차 마르코프(AR(1)) 과정이다.

Rij=σ2ρ ∣i−j∣,ρ≈0.9–0.98R_{ij} = \sigma^2\rho^{\,|i-j|}, \qquad \rho \approx 0.9\text{--}0.98

이 행렬의 역행렬은 삼중대각이며, 경계 성분 두 개만 살짝 손보면 그 삼중대각 행렬의 고유벡터가 정확히 DCT-II 기저가 된다. 일반적인 경계에서도 N→∞N\to\infty 또는 ρ→1\rho\to1 극한에서 DCT-II는 KLT에 점근한다.2 그래서 DCT는 “공짜 KLT” 라고 불린다 — 고정 기저이고, 실수이고, 고속 알고리즘이 있고, 그런데도 성능은 데이터 최적 기저와 소수점 이하에서만 갈린다.

정량적으로는 부호화 이득으로 잰다. 계수 분산 σi2\sigma_i^2 들에 대해

GTC  =  1N∑iσi2(∏iσi2)1/NG_{\text{TC}} \;=\; \frac{\frac{1}{N}\sum_{i} \sigma_i^2}{\bigl(\prod_{i}\sigma_i^2\bigr)^{1/N}}

즉 산술평균 대 기하평균의 비다. 분산이 고를수록(= 변환이 탈상관에 실패할수록) 1에 가까워지고, 몇 개 계수에 몰릴수록 커진다. N=8N=8, ρ=0.95\rho=0.95 에서 DCT-II의 이득은 KLT와 소수점 첫째 자리에서도 잘 갈리지 않는다. 이 값이 곧 율-왜곡 이론의 역주수(reverse water-filling) 논의에서 “수위 아래로 내려가는 계수가 몇 개인가”를 결정한다.

128×128 합성 영상을 8×8 블록으로 잘라 직교 DCT-II 를 걸고, 각 블록에서 지그재그 순서 상위 K 개 계수만 남긴 뒤 되돌린다. 64개 중 4개(6.3 %)만 남겨도 PSNR 32.5 dB 이고, 더 버리면 오차가 블록 경계로 몰려 격자가 뜬다 — 블록 경계와 내부의 기울기오차 RMS 비가 K=4 에서 1.29배, DC 하나만 남기면 2.29배다.

여기서 자주 오해되는 지점 하나. DCT 자체는 압축이 아니다. NN 개 실수를 넣으면 NN 개 실수가 나오는 가역 직교변환일 뿐이고, 비트를 줄이는 것은 그 뒤에 오는 양자화와 엔트로피 부호화다. DCT가 하는 일은 “버려도 덜 아픈 성분”을 한군데로 모아 주는 것, 즉 버리기 좋은 좌표계를 마련하는 것뿐이다.

4. 2차원과 고속 알고리즘[편집]

2차원 DCT는 분리형(separable)이다. 행 방향과 열 방향으로 1차원 DCT를 차례로 걸면 되고, 행렬로는 한 줄이다.

X  =  C x CT\mathbf{X} \;=\; C\,\mathbf{x}\,C^{\mathsf T}

8×8 블록이면 1차원 8점 DCT를 16번(행 8 + 열 8) 돌리는 것으로 끝난다. 분리 없이 곧이곧대로 하면 계수 하나당 64회 곱셈 × 64계수 = 4096회지만, 분리하면 2×8×64=10242\times 8\times 64 = 1024 회로 떨어진다. 이 분리성이 없었다면 블록 크기를 8보다 키우는 것은 꿈도 못 꿨을 것이다.

고속 알고리즘의 출발점은 DCT-II가 2N2N 점 DFT의 실수부로 표현된다는 사실이다. 그대로 고속 푸리에 변환에 태우면 O(Nlog⁡N)O(N\log N) 이 나오고, 대칭성을 이용해 N/2N/2 점 복소 FFT + 전후 회전으로 줄이는 것이 표준 구현이다. 다만 압축 코덱이 실제로 쓰는 것은 작은 NN 에 특화된 손계산 버터플라이다.

  • Loeffler-Ligtenberg-Moschytz(1989) — 8점 DCT-II를 곱셈 11회, 덧셈 29회로 계산한다. 8점 DCT의 곱셈 하한이 11이라는 것이 증명되어 있으므로 곱셈 수로는 최적이다.
  • AAN(Arai-Agui-Nakajima, 1988) — 출력이 상수배 스케일된 값이어도 상관없다는 점을 이용해 곱셈을 5회까지 줄인다. 그 스케일 인자를 양자화표에 미리 곱해 두면 공짜가 되기 때문에 JPEG 인코더의 단골이다.
  • 정수 변환 — H.264의 4×4 코어 변환은 DCT-II를 정수로 근사해 덧셈과 시프트만으로 계산하며, 인코더와 디코더가 비트 단위로 같은 결과를 낸다. 초기 MPEG·JPEG 시절 부동소수 IDCT 구현이 제각각이라 예측 루프에서 오차가 누적되는(drift) 사고가 있었고, IEEE 1180 정확도 규격까지 만들어졌던 흑역사에 대한 반성이다. HEVC는 4~32점 정수 DCT-II에 더해 4×4 인트라 휘도에 DST-VII를 따로 쓴다 — 인트라 예측 잔차가 예측원에서 멀어질수록 커지는 비대칭 구조라, 대칭 코사인보다 사인 기저가 더 잘 맞기 때문이다.

5. JPEG의 8×8 파이프라인[편집]

DCT가 세상에서 가장 많이 실행되는 형태는 JPEG의 8×8 블록이다. 순서만 짚으면 이렇다.

  1. 레벨 시프트. 0~255 화소값에서 128을 빼 대략 0 평균으로 만든다.
  2. 8×8 DCT-II. 좌상단 X00X_{00} 이 DC 계수(블록 평균의 8배), 오른쪽·아래로 갈수록 고주파.
  3. 양자화. X^uv=round⁡(Xuv/Quv)\hat{X}_{uv} = \operatorname{round}(X_{uv}/Q_{uv}). 여기서만 정보가 버려진다. 표준 부속서의 휘도 양자화표는 좌상단이 16, 우하단이 99 근처로, 고주파일수록 눈금이 굵다. 품질 계수는 이 표에 스케일을 곱하는 방식으로 구현된다.
  4. 지그재그 스캔. 2차원 계수를 u+vu+v 가 커지는 방향, 즉 대략 주파수 오름차순으로 지그재그로 훑어 1차원 열로 편다. 고주파가 뒤로 몰리므로 끝이 0으로 길게 이어지고, 그 꼬리를 EOB(end-of-block) 기호 하나로 끝낸다.
  5. 엔트로피 부호화. DC는 이전 블록과의 차분(DPCM), AC는 (0의 런 길이, 값의 비트 수) 쌍을 허프만 부호화한다.

왜 하필 8인가? 4는 블록이 너무 잘아 탈상관 이득이 부족하고, 16 이상은 상관거리를 넘어서 이득이 포화되는 데다 연산량과 국소성 손실만 커진다. 1980년대 하드웨어 사정까지 얹으면 8이 스위트 스폿이었다. 현대 코덱은 이 결정을 고정하지 않고 쿼드트리로 블록을 4×4에서 64×64까지 적응적으로 쪼갠다 — 평탄한 하늘은 크게, 나뭇잎은 잘게.

6. MDCT — 겹쳐서 이음매를 지운다[편집]

블록 단위 DCT의 고질병은 블록 경계다. 이웃한 두 블록이 서로 다른 양자화 오차를 갖고 복원되면, 경계에서 값이 어긋나 격자 무늬가 보인다. 영상에서는 이것이 “JPEG 블록 깨짐”이고, 오디오에서는 프레임 경계마다 딸깍거리는 소리가 된다.

오디오 쪽 해법이 MDCT(modified DCT)다. 프레임을 50% 겹쳐서 자르되, 입력 2N2N 표본에서 출력을 NN 개만 낸다.

Xk=∑n=02N−1xncos⁡ ⁣[πN(n+12+N2)(k+12)],k=0,…,N−1X_k = \sum_{n=0}^{2N-1} x_n \cos\!\left[\frac{\pi}{N}\left(n+\frac{1}{2}+\frac{N}{2}\right)\left(k+\frac{1}{2}\right)\right], \qquad k=0,\dots,N-1

2N→N2N \to N 이니 프레임 하나만 보면 당연히 정보가 모자라고, 역변환하면 시간 영역 알리아싱이 낀다. 그런데 이웃 프레임의 알리아싱이 정확히 반대 부호로 생겨서, 겹치는 구간을 더하면 서로 상쇄된다. 프린슨과 브래들리가 정리한 TDAC(time-domain alias cancellation)이고, 창함수가

wn2+wn+N2=1w_n^2 + w_{n+N}^2 = 1

를 만족하기만 하면 완전 복원이 보장된다(사인 창, KBD 창이 표준). 결과적으로 표본 수는 늘지 않으면서 이음매는 매끄럽게 이어지는 임계표본 겹침 변환이 된다. 알맹이는 DCT-IV이며, MP3·AAC·Vorbis·Opus·AC-3가 전부 이 위에 서 있다. 과도음(트랜지언트)에서 양자화 잡음이 신호보다 먼저 들리는 프리에코를 막으려고 프레임 길이를 짧게 전환하는 블록 스위칭이 붙는 것까지가 세트다.

영상 쪽에서 블록 아티팩트를 다루는 방식은 조금 다르다. 겹침 변환(LOT) 계열도 연구됐지만, 실전에서 이긴 것은 인루프 디블로킹 필터다 — 복원 후 블록 경계에서 화소 기울기를 보고 진짜 에지인지 인공 계단인지 판정해 선택적으로 평활한다. 이 필터가 참조 프레임에도 적용되기 때문에 “인루프”이고, H.264 이후 모든 표준의 필수 부품이 됐다. 아예 블록을 안 쓰는 길도 있는데, 그쪽이 웨이블릿 변환 기반의 JPEG2000이다.

7. 압축 바깥의 DCT — 고속 푸아송 솔버[편집]

수치해석 하는 사람에게 DCT는 압축 도구이기 전에 경계조건에 맞는 대각화 도구다. 균일 격자 위의 이산 라플라시안은 삼중대각 토플리츠 행렬 구조를 갖는데, 이 행렬을 정확히 대각화하는 변환이 경계조건에 따라 정해진다.

경계조건대각화하는 변환고유값
주기DFT2cos⁡(2πk/N)−22\cos(2\pi k/N)-2
디리클레DST2cos⁡(πk/(N+1))−22\cos(\pi k/(N+1))-2
노이만DCT2cos⁡(πk/N)−22\cos(\pi k/N)-2

덕분에 N×NN\times N 격자의 푸아송 방정식을 O(N2log⁡N)O(N^2\log N) 에 직접 풀 수 있다. 비압축성 전산유체역학의 압력 사영 단계, 즉 매 시간 스텝마다 나오는 압력 푸아송 방정식을 벽에서 노이만 조건으로 놓고 DCT로 푸는 구현이 흔한 이유다. 반복법인 다중격자법이 복잡 형상까지 감당하는 범용 해법이라면, DCT 기반 직접 솔버는 균일 직사각 격자에 한해 반복 없이 기계 정밀도로 끝낸다. 격자가 직사각형이 아니면 못 쓴다는 것이 유일하고도 치명적인 제약.

체비쇼프 다항식과의 인연도 깊다. 체비쇼프-가우스-로바토 점에서의 체비쇼프 계수 계산이 정확히 DCT-I이며, 스펙트럴 방법의 미분·보간 연산이 FFT 대신 DCT로 구현되는 근거가 여기 있다.3

8. 관련 문서[편집]

9. Footnotes[편집]

  1. Ahmed, N., Natarajan, T., Rao, K. R. (1974). “Discrete Cosine Transform.” IEEE Trans. Computers. 훗날 아메드 본인이 회고하기를, 처음 NSF에 낸 제안서는 “이미 있는 변환들의 조합일 뿐”이라며 반려당했다고 한다. 그 반려당한 아이디어가 지금 인류가 저장한 사진·영상 파일의 대부분을 떠받치고 있다. 심사위원 인생 최대의 오심 후보. ↩

  2. 정확한 진술은 Strang, G. (1999). “The Discrete Cosine Transform.” SIAM Review 41(1)에 정리되어 있다. 요점은 AR(1) 공분산의 역행렬이 삼중대각이고, 그 삼중대각족 안에서 DCT-II·DCT-III 등이 각각 정확한 고유벡터가 되는 경계항이 존재한다는 것. “DCT는 KLT의 근사”라는 흔한 문장은 좀 억울한 축약이고, 실은 경계조건만 맞으면 정확히 KLT다. ↩

  3. 그래서 FFTW 문서에는 DCT가 REDFT10(DCT-II), REDFT01(DCT-III) 같은 정겨운 이름으로 등장한다. 처음 보면 암호 같지만 R=real, E=even, DFT에 좌우 대칭 종류를 붙인 것뿐이다. 이걸 해독하고 나면 왜 DCT-II의 역이 DCT-III인지가 이름만 봐도 보인다. ↩