Дискретное косинусное преобразование

Дискретное косинусное преобразование (англ. Discrete Cosine Transform, DCT) — одно из ортогональных преобразований. Вариант косинусного преобразования для вектора действительных чисел. Применяется в алгоритмах сжатия информации с потерями, например, MPEG и JPEG. Это преобразование тесно связано с дискретным преобразованием Фурье и является гомоморфизмом его векторного пространства.

Данное преобразование является линейным, поэтому его результат можно вычислить при помощи умножения матрицы преобразования и вектора. Матрица ДКП является ортогональной (обратная матрица равна транспонированной), поэтому обратное преобразование вычисляется с помощью умножения транспонированной матрицы ДКП на вектор. На практике используется вариант ДКП с матрицей, пропорциональной ортогональной (получающейся из ортогональной умножением на константу).

Различные периодические продолжения сигнала ведут к различным типам ДКП. Ниже приводятся матрицы для первых четырёх типов ДКП:

$\mathrm {DCT} {\text{-}}1_{n}=\left[\cos(kl{\tfrac {\pi }{n-1}})\right]_{0\leq k,l<n}$

$\mathrm {DCT} {\text{-}}2_{n}=\left[\cos(k(l+{\tfrac {1}{2}}){\tfrac {\pi }{n}})\right]_{0\leq k,l<n}$

$\mathrm {DCT} {\text{-}}3_{n}=\left[\cos((k+{\tfrac {1}{2}})l{\tfrac {\pi }{n}})\right]_{0\leq k,l<n}$

$\mathrm {DCT} {\text{-}}4_{n}=\left[\cos((k+{\tfrac {1}{2}})(l+{\tfrac {1}{2}}){\tfrac {\pi }{n}})\right]_{0\leq k,l<n}$

Именно $\mathrm {DCT} {\text{-}}2$ чаще всего встречается в практических приложениях благодаря свойству «уплотнения энергии».

$\mathrm {DCT}$ для вектора из 8 чисел часто называют $\mathrm {DCT} {\text{-}}2_{8}$. Наиболее распространён двумерный вариант преобразования для матриц 8x8, состоящий из последовательности $\mathrm {DCT} {\text{-}}2_{8}$ сначала для каждой строки, а затем для каждого столбца матрицы.

Существуют алгоритмы быстрого $\mathrm {DCT}$-преобразования, похожие на алгоритм быстрого преобразования Фурье. Для $\mathrm {DCT} {\text{-}}2_{8}$ и других вариантов $\mathrm {DCT}$ с фиксированной размерностью вектора существуют также алгоритмы, позволяющие свести количество операций умножения к минимуму.

Существуют аналоги $\mathrm {DCT}$, приближающие косинус числами, легко получающимися путём небольшого количества операций сдвига и сложения, что позволяет избежать операций умножения и тем самым повысить скорость вычислений.

Литература

• C. Loeffler, A. Ligtenberg and G. Moschytz. Practical Fast 1-D DCT Algorithms with 11 Multiplications // Proc. Int’l. Conf. on Acoustics, Speech, and Signal Processing 1989 (ICASSP '89), pp. 988—991.

Ссылки

• Список статей по ДКП и альтернативным преобразованиям
• About JPEG: Discrete Cosine Transform
• The Discrete Cosine Transform (DCT)