이산 코사인 변환

파일:Phalaenopsis fft dct.png

2차원 DCT와 DFT의 비교

이산 코사인 변환, DCT(discrete cosine transform)는 이산 푸리에 변환(DFT)과 유사한 변환이다. 이산여현변환(離散餘弦變換)이라고 하기도 한다. 수식적으로는 길이가 두 배이고 실수값을 가지는 짝함수에 DFT 연산을 수행하는 것과 동일하다. 실수값을 가지는 짝함수의 푸리에 변환도 실수값을 가지는 짝함수이기 때문이다. 입력/출력 데이터를 반 샘플 정도 이동시키는 등 8가지의 변형이 있는데 그중에서 4가지가 널리 사용된다.

가장 널리 쓰이는 변형 DCT 알고리즘은 type-II DCT인데, 이것을 그냥 "DCT"라고 부르는 경우가 많다. 이것의 역변환이 type-III DCT인데 마찬가지로 단순히 "역DCT"혹은 "IDCT"라고 부른다.

DCT와 연관된 변환은 두 가지가 있다. 이산 사인 변환 (DST)은 실수 값을 가지는 홀함수의 DFT와 동일하며, 변형 이산 코사인 변환 (MDCT)은 다른 하나는 겹치는 데이터를 사용한다.

응용

실수 신호에 대하여, 변환 결과물이 복소수로 나오는 DFT와는 달리 실수로만 결과물이 나오기 때문에, 처리하기가 간편하여 신호처리 및 영상처리에 널리 사용한다. 특히 신호의 에너지 성분 대부분이 저주파 성분 일부에 집중되는 '에너지 집중 현상'을 가지고 있기 때문에, 손실 압축에 널리 사용한다. 예를 들어, JPEG 영상 압축, MJPEG, MPEG, DV 동영상 압축등에서 DCT를 사용한다. N × N 블록에 2차원 DCT-II을 적용하고, 결과값을 양자화하고 엔트로피 부호화한다. 이때, N값은 보통 8이며 이 블록의 행과 열에 DCT-II 공식을 적용한다. 결과값은 8 × 8 변환 계수 행렬이며, (0,0) 원소는 (주파수가 0인) 직류 성분이고 나머지 성분은 점점 주파수가 커지는 순서로 배열된다.

파일:Example dft dct.svg

2차원 DCT와 DFT의 비교

변형 이산 코사인 변환 (modified discrete cosine transform, 줄여서 MDCT)는 AAC, Vorbis, MP3 등의 오디오 압축에 사용한다. DCT는 편미분 방정식을 푸는데도 사용할 수 있다.

엄밀한 정의

이산 코사인 변환은 역함수가 존재하는 선형함수 F : R^N → R^N이다. (R은 실수의 집합이다.) 또는 N × N 정사각행렬로 나타낼 수도 있다. DCT의 정의는 약간씩 다를 수 있다. 아래 공식 중 하나를 이용하여 N개의 실수 x₀, ..., x_N-1가 N개의 실수 f₀, ..., f_N-1로 변형한다.

역변환

DCT-I의 역변환은 DCT-I에 2/(N-1)을 곱한 것이다. DCT-IV의 역변환은 DCT-IV에 2/N을 곱한 것이다. DCT-II의 역변환은 DCT-III에 2/N을 곱한 것이며, DCT-III의 역변환은 DCT-II에 2/N을 곱한 것이다.

DFT과 마찬가지로, 관습적으로 변환 공식 앞에 일정한 수를 곱해서 정규화하는 경우가 있는데 이를 따르지 않는 경우도 많다. 예를 들어, 어떤 사람들은 역변환 공식 앞에 곱하는 수를 없애기 위해서 변환 공식 자체에 $\sqrt{2/N}$를 곱하기도 한다.

계산

공식을 그대로 적용하면 O(N²)의 연산이 필요하지만, 고속 푸리에 변환(FFT)과 마찬가지로 계산 과정을 분해하여 O(N log N)만큼의 연산으로 계산할 수도 있다. O(N)만큼의 전처리 및 후처리 과정을 통해 DCT를 FFT로 변환하여 계산할 수도 있다.

같이 보기

• 이산 웨이블릿 변환
• JPEG
• 푸리에 관련 변환의 목록
• 수정 이산 코사인 변환

외부 링크

• 소스 코드