WikiSort.ru - Не сортированное

Дискретное косинусное преобразование (англ. 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)

Это заготовка статьи о компьютерах. Вы можете помочь проекту, дополнив её. Это примечание по возможности следует заменить более точным.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её.