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

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

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

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

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

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

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

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

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

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

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

Существуют аналоги ${\displaystyle \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)

Эта страница в последний раз была отредактирована 19 марта 2022 в 23:24.