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

Дискретное косинусное преобразование (англ. Discrete Cosine Transform, DCT) — одно из ортогональных преобразований. Вариант косинусного преобразования для вектора действительных чисел. Применяется в алгоритмах сжатия информации с потерями, например, 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.

Ссылки

• [compression.ru/download/video_dct.html Список статей по ДКП и альтернативным преобразованиям]
• [www.pcs-ip.eu/index.php/main/edu/5 About JPEG: Discrete Cosine Transform]
• [www.cs.cf.ac.uk/Dave/Multimedia/node231.html The Discrete Cosine Transform (DCT)]

Отрывок, характеризующий Дискретное косинусное преобразование

Когда Ростов вошел в комнату, княжна опустила на мгновенье голову, как бы предоставляя время гостю поздороваться с теткой, и потом, в самое то время, как Николай обратился к ней, она подняла голову и блестящими глазами встретила его взгляд. Полным достоинства и грации движением она с радостной улыбкой приподнялась, протянула ему свою тонкую, нежную руку и заговорила голосом, в котором в первый раз звучали новые, женские грудные звуки. M lle Bourienne, бывшая в гостиной, с недоумевающим удивлением смотрела на княжну Марью. Самая искусная кокетка, она сама не могла бы лучше маневрировать при встрече с человеком, которому надо было понравиться.
«Или ей черное так к лицу, или действительно она так похорошела, и я не заметила. И главное – этот такт и грация!» – думала m lle Bourienne.
Ежели бы княжна Марья в состоянии была думать в эту минуту, она еще более, чем m lle Bourienne, удивилась бы перемене, происшедшей в ней. С той минуты как она увидала это милое, любимое лицо, какая то новая сила жизни овладела ею и заставляла ее, помимо ее воли, говорить и действовать. Лицо ее, с того времени как вошел Ростов, вдруг преобразилось. Как вдруг с неожиданной поражающей красотой выступает на стенках расписного и резного фонаря та сложная искусная художественная работа, казавшаяся прежде грубою, темною и бессмысленною, когда зажигается свет внутри: так вдруг преобразилось лицо княжны Марьи. В первый раз вся та чистая духовная внутренняя работа, которою она жила до сих пор, выступила наружу. Вся ее внутренняя, недовольная собой работа, ее страдания, стремление к добру, покорность, любовь, самопожертвование – все это светилось теперь в этих лучистых глазах, в тонкой улыбке, в каждой черте ее нежного лица.
Ростов увидал все это так же ясно, как будто он знал всю ее жизнь. Он чувствовал, что существо, бывшее перед ним, было совсем другое, лучшее, чем все те, которые он встречал до сих пор, и лучшее, главное, чем он сам.
Разговор был самый простой и незначительный. Они говорили о войне, невольно, как и все, преувеличивая свою печаль об этом событии, говорили о последней встрече, причем Николай старался отклонять разговор на другой предмет, говорили о доброй губернаторше, о родных Николая и княжны Марьи.
Княжна Марья не говорила о брате, отвлекая разговор на другой предмет, как только тетка ее заговаривала об Андрее. Видно было, что о несчастиях России она могла говорить притворно, но брат ее был предмет, слишком близкий ее сердцу, и она не хотела и не могла слегка говорить о нем. Николай заметил это, как он вообще с несвойственной ему проницательной наблюдательностью замечал все оттенки характера княжны Марьи, которые все только подтверждали его убеждение, что она была совсем особенное и необыкновенное существо. Николай, точно так же, как и княжна Марья, краснел и смущался, когда ему говорили про княжну и даже когда он думал о ней, но в ее присутствии чувствовал себя совершенно свободным и говорил совсем не то, что он приготавливал, а то, что мгновенно и всегда кстати приходило ему в голову.