Русская Википедия:Дискретное косинусное преобразование
Дискретное косинусное преобразование (Шаблон:Lang-en) — одно из ортогональных преобразований. Вариант косинусного преобразования для вектора действительных чисел. Применяется в алгоритмах сжатия информации с потерями, например, MPEG и JPEG. Это преобразование тесно связано с дискретным преобразованием Фурье и является гомоморфизмом его векторного пространства.
Данное преобразование является линейным, поэтому его результат можно вычислить при помощи умножения матрицы преобразования и вектора. Матрица ДКП является ортогональной (обратная матрица равна транспонированной), поэтому обратное преобразование вычисляется с помощью умножения транспонированной матрицы ДКП на вектор. На практике используется вариант ДКП с матрицей, пропорциональной ортогональной (получающейся из ортогональной умножением на константу).
Различные периодические продолжения сигнала ведут к различным типам ДКП. Ниже приводятся матрицы для первых четырёх типов ДКП:
- <math>\mathrm{DCT}\text{-}1_n= \left[\cos (kl\tfrac{\pi}{n-1})\right]_{0\leq k,l<n} </math>
- <math>\mathrm{DCT}\text{-}2_n= \left[\cos (k(l+\tfrac{1}{2})\tfrac{\pi}{n})\right]_{0\leq k,l<n} </math>
- <math>\mathrm{DCT}\text{-}3_n= \left[\cos ((k+\tfrac{1}{2})l\tfrac{\pi}{n})\right]_{0\leq k,l<n} </math>
- <math>\mathrm{DCT}\text{-}4_n= \left[\cos ((k+\tfrac{1}{2})(l+\tfrac{1}{2})\tfrac{\pi}{n})\right]_{0\leq k,l<n} </math>
Именно <math>\mathrm{DCT}\text{-}2</math> чаще всего встречается в практических приложениях благодаря свойству «уплотнения энергии».
<math>\mathrm{DCT}</math> для вектора из 8 чисел часто называют <math>\mathrm{DCT}\text{-}2_8</math>. Наиболее распространён двумерный вариант преобразования для матриц 8x8, состоящий из последовательности <math>\mathrm{DCT}\text{-}2_8</math> сначала для каждой строки, а затем для каждого столбца матрицы.
Существуют алгоритмы быстрого <math>\mathrm{DCT}</math>-преобразования, похожие на алгоритм быстрого преобразования Фурье. Для <math>\mathrm{DCT}\text{-}2_8</math> и других вариантов <math>\mathrm{DCT}</math> с фиксированной размерностью вектора существуют также алгоритмы, позволяющие свести количество операций умножения к минимуму.
Существуют аналоги <math>\mathrm{DCT}</math>, приближающие косинус числами, легко получающимися путём небольшого количества операций сдвига и сложения, что позволяет избежать операций умножения и тем самым повысить скорость вычислений.
Литература
- 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)
Шаблон:Compu-stub
Шаблон:Math-stub
Шаблон:Computer-sci-stub
