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

Дискретного косинусного преобразования ( ДКП ) выражает конечную последовательность точек данных в терминах суммы косинус функций осциллирующих на разных частотах . DCT, впервые предложенный Насиром Ахмедом в 1972 году, представляет собой широко используемый метод преобразования при обработке сигналов и сжатии данных . Он используется в большинстве цифровых носителей , включая цифровые изображения (например, JPEG и HEIF , где небольшие высокочастотные компоненты могут быть отброшены), цифровое видео (например, MPEG и H.26x).), цифровое аудио (например, Dolby Digital , MP3 и AAC ), цифровое телевидение (например, SDTV , HDTV и VOD ), цифровое радио (например, AAC + и DAB + ) и кодирование речи (например, AAC-LD , Siren и Opus ). DCT также важны для множества других приложений в науке и технике , таких как цифровая обработка сигналов , телекоммуникационные устройства, уменьшение пропускной способности сети.использование и спектральные методы для численного решения уравнений в частных производных .

Использование косинусных функций, а не синусоидальных функций имеет решающее значение для сжатия, поскольку оказывается (как описано ниже), что требуется меньше косинусных функций для аппроксимации типичного сигнала , тогда как для дифференциальных уравнений косинусы выражают конкретный выбор граничных условий . В частности, DCT - это преобразование Фурье, подобное дискретному преобразованию Фурье (ДПФ), но с использованием только действительных чисел.. DCT обычно связаны с коэффициентами ряда Фурье периодически и симметрично расширенной последовательности, тогда как DFT связаны с коэффициентами ряда Фурье периодически расширенной последовательности. DCT эквивалентны DFT примерно в два раза большей длины, работающим с реальными данными с четной симметрией (поскольку преобразование Фурье действительной и четной функции является действительным и четным), тогда как в некоторых вариантах входные и / или выходные данные сдвигаются вдвое. образец. Существует восемь стандартных вариантов DCT, четыре из которых являются общими.

Наиболее распространенным вариантом дискретного косинусного преобразования является DCT типа II, который часто называют просто «DCT». Это был оригинальный DCT, впервые предложенный Ахмедом. Его обратный DCT типа III, соответственно, часто называют просто «обратным DCT» или «IDCT». Два связанных преобразования - это дискретное синусоидальное преобразование (DST), которое эквивалентно DFT действительных и нечетных функций, и модифицированное дискретное косинусное преобразование (MDCT), которое основано на DCT перекрытияданные. Многомерные DCT (MD DCT) разработаны для расширения концепции DCT для сигналов MD. Существует несколько алгоритмов вычисления MD DCT. Для уменьшения вычислительной сложности реализации DCT было разработано множество быстрых алгоритмов. Одним из них является целочисленный DCT ^[1] (IntDCT), целочисленное приближение стандарта DCT ^[2], используемого в нескольких международных стандартах ISO / IEC и ITU-T . ^{[2] [1]}

Сжатие DCT, также известное как сжатие блоков, сжимает данные в наборы дискретных блоков DCT. ^[3] Блоки DCT могут иметь несколько размеров, включая 8x8 пикселей для стандартного DCT и различные целочисленные размеры DCT от 4x4 до 32x32 пикселей. ^{[1] [4]} DCT обладает сильным свойством «сжатия энергии» ^{[5] [6],} позволяющим достичь высокого качества при высоких степенях сжатия данных . ^{[7] [8]} Однако блочные артефакты сжатия могут появиться при применении сильного сжатия DCT.

История [ править ]

Дискретное косинусное преобразование (DCT) было впервые задумано Насиром Ахмедом , когда он работал в Государственном университете Канзаса , и он предложил концепцию Национальному научному фонду в 1972 году. Первоначально он предназначал DCT для сжатия изображений . ^{[9] [1]} Ахмед разработал практический алгоритм ДКП со своим аспирантом Т. Natarajan и друга КР Рао в Университете штата Техас в Арлингтоне в 1973 году, и они обнаружили , что это был наиболее эффективный алгоритм для сжатия изображений. ^[9] Они представили свои результаты в статье под названием «Дискретное косинусное преобразование», опубликованной в январе 1974 года. ^{[5] [6] [10]}В нем описывается то, что сейчас называется DCT типа II (DCT-II), ^[11], а также обратное DCT типа III (IDCT). ^[5] Это была эталонная публикация, ^{[12] [13]} и с момента публикации она упоминалась как фундаментальное развитие в тысячах работ. ^[14] Основная исследовательская работа и события, которые привели к развитию DCT, были обобщены в более поздней публикации Ахмеда «Как я пришел к дискретному косинусному преобразованию». ^[9]

С момента его появления в 1974 году DCT проводились обширные исследования. ^[10] В 1977 году Вен-Сюн Чен опубликовал статью с К. Харрисоном Смитом и Стэнли К. Фраликом, в которой представил быстрый алгоритм DCT, ^{[15] [10]} и основал Compression Labs для коммерциализации технологии DCT. ^[1] Дальнейшие разработки включают статью 1978 года М.Дж. Нарасимхи и А.М. Петерсона и статью 1984 года Б.Г. Ли. ^[10] Эти исследовательские работы, наряду с оригинальной статьей Ахмеда 1974 года и статьей Чена 1977 года, были процитированы Joint Photographic Experts Group в качестве основы для алгоритма сжатия изображений JPEG с потерями в 1992 году. ^{[10] [16]}

В 1975 году Джон А. Роуз и Ганер С. Робинсон адаптировали DCT для межкадрового кодирования видео с компенсацией движения . Они экспериментировали с DCT и быстрым преобразованием Фурье (FFT), разрабатывая межкадровые гибридные кодеры для обоих, и обнаружили, что DCT является наиболее эффективным из-за его меньшей сложности, способного сжимать данные изображения до 0,25 бит на пиксель. для сцены видеотелефона с качеством изображения, сравнимым с внутрикадровым кодером, требующим 2 бита на пиксель. ^{[17] [18]} DCT был применен к кодированию видео Wen-Hsiung Chen, ^[1] который разработал быстрый алгоритм DCT с CH Smith и SC Fralick в 1977 году.^{[15] [10]} и основал Compression Labs для коммерциализации технологии DCT. ^[1] В 1979 году Анил К. Джайн и Джасвант Р. Джайн усовершенствовали сжатие видео DCT с компенсацией движения ^{[19] [20], которое} также называется компенсацией движения блоков. ^[20] Это привело к тому, что в 1981 году Чен разработал практический алгоритм сжатия видео, названный DCT с компенсацией движения или адаптивным кодированием сцены. ^[20] DCT с компенсацией движения позже стал стандартным методом кодирования для сжатия видео с конца 1980-х годов. ^{[21] [22]}

Целочисленный DCT используется в Advanced Video Coding (AVC), ^{[23] [1],} введенном в 2003 году, и High Efficiency Video Coding (HEVC), ^{[4] [1],} представленном в 2013 году. Целочисленный DCT также используется в Формат высокоэффективного изображения (HEIF), который использует подмножество формата кодирования видео HEVC для кодирования неподвижных изображений. ^[4]

ДКП вариант, модифицированного дискретного косинусного преобразования (МДКП), был разработан Джоном П. Princen, AW Джонсон и Алан Б. Брэдли в университете Суррей в 1987 году, ^[24] Ниже более ранней работы по Princen и Брэдли в 1986 году ^{[ 25]} MDCT используется в большинстве современных форматов сжатия звука , таких как Dolby Digital (AC-3), ^{[26] [27]} MP3 (в котором используется гибридный алгоритм DCT- FFT ), ^[28] Advanced Audio Coding (AAC). , ^[29] и Vorbis ( Ogg ). ^[30]

Дискретное преобразование синус (DST) , был получен из ДКПА, путем замены условию Неймана при х = 0 с условием Дирихля . ^[31] Летнее время было описано в документе DCT 1974 года Ахмедом, Натараджаном и Рао. ^[5] ТЛЧ I типа (ТЛЧ-I) было позже описано Анилом К. Джайном в 1976 году, а ТЛЧ II типа (ТЛЧ-II) было затем описано Х. Б. Кекрой и Дж. К. Соланка в 1978 г. ^[32]

Насир Ахмед также разработал алгоритм DCT без потерь с Гиридхаром Мандьямом и Нираджем Маготрой из Университета Нью-Мексико в 1995 году. Это позволяет использовать метод DCT для сжатия изображений без потерь . Это модификация исходного алгоритма DCT, включающая элементы обратной DCT и дельта-модуляции . Это более эффективный алгоритм сжатия без потерь, чем энтропийное кодирование . ^[33] DCT без потерь также известен как LDCT. ^[34]

Вейвлет- кодирование, использование вейвлет-преобразований при сжатии изображений, началось после разработки кодирования DCT. ^[35] Введение DCT привело к развитию вейвлет-кодирования, варианта DCT-кодирования, в котором вместо блочного алгоритма DCT используются вейвлеты. ^[35] дискретное вейвлет - преобразование (DWT) кодирование используется в формате JPEG 2000 стандарта, ^[36] разработан с 1997 по 2000, ^[37] и в BBC «ы Дирака формат сжатия видео выпущен в 2008. Вейвлетный кодирования является более processor- интенсивно, и он еще не получил широкого распространения в обращении к потребителю. ^[38]

Приложения [ править ]

ДКП является наиболее широко используемым методом преобразования в обработке сигналов , ^[39] , и, безусловно, наиболее широко используется линейное преобразование в сжатии данных . ^[40] Сжатие данных DCT было основополагающим для цифровой революции . ^{[8] [41] [42]} Несжатые цифровые носители, а также сжатие без потерь имели непрактично высокие требования к памяти и полосе пропускания , которые были значительно сокращены за счет высокоэффективного метода сжатия DCT с потерями ^{[7] [8],} способного обеспечитькоэффициенты сжатия данных от 8: 1 до 14: 1 для качества, близкого к студийному ^[7], до 100: 1 для контента приемлемого качества. ^[8] Широкое распространение стандартов сжатия DCT привело к появлению и распространению цифровых медиа-технологий, таких как цифровые изображения , цифровые фотографии , ^{[43] [44]} цифровое видео , ^{[21] [42]} потоковое мультимедиа , ^[45] цифровое телевидение , потоковое телевидение , видео по запросу (VOD), ^[8] цифровое кино , ^[26] видео высокой четкости (HD видео) ителевидение высокой четкости (HDTV). ^{[7] [46]}

DCT, и в частности DCT-II, часто используется при обработке сигналов и изображений, особенно для сжатия с потерями, поскольку он обладает сильным свойством «сжатия энергии»: ^{[5] [6]} в типичных приложениях большая часть сигнала информация имеет тенденцию концентрироваться в нескольких низкочастотных компонентах DCT. Для сильно коррелированных марковских процессов DCT может приблизиться к эффективности сжатия преобразования Карунена-Лоэва (что является оптимальным с точки зрения декорреляции). Как поясняется ниже, это происходит из граничных условий, неявных в функциях косинуса.

ДКП также широко используется при решении дифференциальных уравнений с помощью спектральных методов , где различные варианты соответствуют ДКП в несколько различных четных / нечетных граничных условий на двух концах массива.

DCT также тесно связаны с полиномами Чебышева , и быстрые алгоритмы DCT (см. Ниже) используются в приближении Чебышева произвольных функций сериями полиномов Чебышева, например, в квадратуре Кленшоу – Кертиса .

DCT - это стандарт кодирования мультимедийных телекоммуникационных устройств. Он широко используется для снижения скорости передачи данных и уменьшения использования полосы пропускания сети . ^[1] Сжатие DCT значительно уменьшает объем памяти и полосу пропускания, необходимые для цифровых сигналов . ^[8]

Общие приложения [ править ]

DCT широко используется во многих приложениях, включая следующие.

Стандарты визуальных медиа DCT [ править ]

DCT-II, также известный как DCT, является наиболее важным методом сжатия изображений . ^{[ необходима цитата ]} Он используется в стандартах сжатия изображений, таких как JPEG , и стандартах сжатия видео, таких как H.26x , MJPEG , MPEG , DV , Theora и Daala . Здесь вычисляется двумерный DCT-II блоков, а результаты квантуются и кодируются энтропийным кодом . В таком случае,${\ Displaystyle N \ раз N}$${\ displaystyle N}$обычно равно 8, и формула DCT-II применяется к каждой строке и столбцу блока. Результатом является массив коэффициентов преобразования 8 × 8, в котором элемент (вверху слева) представляет собой компонент DC (нулевой частоты), а записи с увеличивающимися значениями индекса по вертикали и горизонтали представляют более высокие пространственные частоты по вертикали и горизонтали.${\ displaystyle (0,0)}$

Advanced Video Coding (AVC) использует целочисленное DCT ^{[23] [1]} (IntDCT), целочисленное приближение DCT. ^{[2] [1]} Он использует целочисленные блоки DCT 4x4 и 8x8. Высокоэффективное кодирование видео (HEVC) и высокоэффективный формат изображения (HEIF) используют различные целочисленные размеры блоков DCT от 4x4 до 32x32 пикселей . ^{[4] [1]} По состоянию на 2019 год ^{[Обновить]}, AVC является наиболее часто используемым форматом для записи, сжатия и распространения видеоконтента, который используется 91% разработчиков видео, за ним следует HEVC, который используется 43% разработчиков. ^[54]

Форматы изображений [ править ]

Форматы видео [ править ]

Аудиостандарты MDCT [ править ]

Общий звук [ править ]

Кодирование речи [ править ]

MD DCT [ править ]

Многомерные DCT (MD DCT) имеют несколько приложений, в основном 3-D DCT, такие как 3-D DCT-II, у которого есть несколько новых приложений, таких как системы кодирования гиперспектральных изображений, ^[92] кодирование 3-D DCT с переменной временной длиной, ^{[93 ]} алгоритмы кодирования видео , ^[94] адаптивное кодирование видео ^[95] и трехмерное сжатие. ^[96] В связи с усовершенствованием аппаратного и программного обеспечения и внедрением нескольких быстрых алгоритмов необходимость использования MD DCT быстро возрастает. DCT-IV приобрел популярность благодаря своим приложениям в быстрой реализации многофазных фильтров с действительным знаком ^[97], ортогональных преобразований с перекрытием ^{[98] [99]}и косинус-модулированные базисы вейвлетов. ^[100]

Цифровая обработка сигналов [ править ]

DCT играет очень важную роль в цифровой обработке сигналов . Используя DCT, можно сжимать сигналы. DCT может использоваться в электрокардиографии для сжатия сигналов ЭКГ. DCT2 обеспечивает лучшую степень сжатия, чем DCT.

DCT широко применяется в процессорах цифровых сигналов (DSP), а также в программном обеспечении цифровой обработки сигналов. Многие компании разработали DSP на основе технологии DCT. DCT широко используются для таких приложений, как кодирование , декодирование, видео, аудио, мультиплексирование , управляющие сигналы, сигнализация и аналого-цифровое преобразование . DCT также обычно используются для микросхем кодера / декодера телевидения высокой четкости (HDTV) . ^[1]

Артефакты сжатия [ править ]

Общая проблема со сжатием DCT в цифровых носителях являются блочными артефактами сжатия , ^[101] , вызванные DCT блоков. ^[3] Алгоритм DCT может вызывать блочные артефакты при применении сильного сжатия. Поскольку DCT используется в большинстве стандартов кодирования цифровых изображений и видео (таких как форматы JPEG , H.26x и MPEG ), блочные артефакты сжатия на основе DCT широко распространены в цифровых носителях.. В алгоритме DCT изображение (или кадр в последовательности изображений) делится на квадратные блоки, которые обрабатываются независимо друг от друга, затем берется DCT этих блоков, и результирующие коэффициенты DCT квантуются . Этот процесс может вызвать артефакты блокировки, в первую очередь при высоких степенях сжатия данных . ^[101] Это также может вызвать эффект « москитного шума », обычно встречающийся в цифровом видео (например, в форматах MPEG). ^[102]

Блоки DCT часто используются в глитч-арте . ^[3] Художница Роза Менкман использует артефакты сжатия на основе DCT в своем глитч-арте ^[103], особенно блоки DCT, которые можно найти в большинстве цифровых медиаформатов, таких как цифровые изображения JPEG и цифровой звук MP3 . ^[3] Другой пример - Jpegs немецкого фотографа Томаса Руффа , который использует преднамеренные артефакты JPEG в качестве основы стиля изображения. ^{[104] [105]}

Неофициальный обзор [ править ]

Как и любое преобразование, связанное с Фурье, дискретные косинусные преобразования (DCT) выражают функцию или сигнал в виде суммы синусоид с разными частотами и амплитудами . Подобно дискретному преобразованию Фурье (ДПФ), ДКП работает с функцией в конечном числе дискретных точек данных. Очевидное различие между DCT и DFT состоит в том, что в первом используются только косинусные функции, а во втором - как косинусы, так и синусы (в форме комплексных экспонент ). Однако это видимое различие является просто следствием более глубокого различия: DCT подразумевает отличные от DFT или других связанных преобразований граничные условия .

Связанные с Фурье преобразования, которые работают с функцией в конечной области , такие как ДПФ, ДКП или ряд Фурье , можно рассматривать как неявно определяющие расширение этой функции за пределы области. То есть, как только вы напишете функцию как сумму синусоид, вы можете вычислить эту сумму в любом случае , даже если оригинал не был указан. ДПФ, как и ряд Фурье, подразумевает периодическое расширение исходной функции. DCT, как и косинусное преобразование , подразумевает четное расширение исходной функции.${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$

Однако, поскольку ДКП работают на конечных , дискретных последовательностей, две проблемы возникают , которые не применяются для непрерывного косинусного преобразования. Во-первых, необходимо указать, является ли функция четной или нечетной как на левой, так и на правой границах области (т. Е. На границах min- n и max- n в определениях ниже, соответственно). Во-вторых, нужно указать, в какой точке функция четная или нечетная. В частности, рассмотрим последовательность abcd из четырех равноотстоящих точек данных и скажем, что мы задаем четную левую границу. Есть два разумных варианта: либо данные даже о пробе а, и в этом случае четное расширение - это dcbabcd , или данные даже находятся примерно в точке на полпути между a и предыдущей точкой, и в этом случае четное расширение - dcbaabcd ( повторяется a ).

Этот выбор приводит ко всем стандартным вариациям DCT, а также к дискретным синусоидальным преобразованиям (DST). Каждая граница может быть четной или нечетной (2 варианта на границу) и может быть симметричной относительно точки данных или точки на полпути между двумя точками данных (2 варианта на границу), всего 2 × 2 × 2 × 2 = 16 возможности. Половина этих возможностей, с четной левой границей, соответствуют 8 типам DCT; другая половина - это 8 типов DST.

Эти различные граничные условия сильно влияют на приложения преобразования и приводят к уникальным полезным свойствам для различных типов DCT. Наиболее непосредственно, при использовании Фурье-преобразования , связанные решать дифференциальные уравнения в частных от спектральных методов , граничные условия непосредственно определены как часть решаемой задачи. Или, для MDCT (основанного на DCT типа IV), граничные условия тесно связаны с критическим свойством MDCT отмены наложения спектров во временной области. Более тонко, граничные условия отвечают за свойства «энергетической компактификации», которые делают DCT полезными для сжатия изображения и звука, потому что границы влияют на скорость сходимости любого ряда, подобного Фурье.

В частности, хорошо известно, что любые разрывы в функции снижают скорость сходимости ряда Фурье, так что требуется больше синусоид для представления функции с заданной точностью. Тот же принцип регулирует полезность ДПФ и других преобразований для сжатия сигнала; чем плавнее функция, тем меньше членов в ее ДПФ или ДКП требуется для ее точного представления и тем больше она может быть сжата. (Здесь мы думаем о ДПФ или ДКП как о приближении ряда Фурье или ряда косинусов.функции, соответственно, чтобы говорить о ее "гладкости".) Однако неявная периодичность ДПФ означает, что разрывы обычно возникают на границах: любой случайный сегмент сигнала вряд ли будет иметь одинаковое значение на обоих концах. левая и правая границы. (Аналогичная проблема возникает для DST, в котором нечетное левое граничное условие подразумевает разрыв для любой функции, которая не оказывается равной нулю на этой границе.) Напротив, DCT, где обе границы четные, всегда дает непрерывное расширение на границы (хотя наклонобычно прерывистый). Вот почему DCT и, в частности, DCT типов I, II, V и VI (типы, которые имеют две четные границы) обычно работают лучше для сжатия сигнала, чем DFT и DST. На практике DCT типа II обычно предпочтительнее для таких приложений, отчасти по причинам вычислительного удобства.

Формальное определение [ править ]

Формально дискретное косинус - преобразование является линейным , обратимо функция (где обозначает множество действительных чисел ), или , что эквивалентно обратимый N × N квадратная матрица . Есть несколько вариантов DCT с немного измененными определениями. В N действительных чисел х ₀ , ..., х _{N -1} преобразуются в N действительных чисел х ₀ , ..., Х _{Н -1} в соответствии с одной из формул:${\ displaystyle f: \ mathbb {R} ^ {N} \ to \ mathbb {R} ^ {N}}$${\ Displaystyle \ mathbb {R}}$

DCT-I [ править ]

${\ displaystyle X_ {k} = {\ frac {1} {2}} (x_ {0} + (- 1) ^ {k} x_ {N-1}) + \ sum _ {n = 1} ^ { N-2} x_ {n} \ cos \ left [{\ frac {\ pi} {N-1}} nk \ right] \ quad \ quad k = 0, \ dots, N-1.}$

Некоторые авторы дополнительно умножают члены x ₀ и x _{N −1} на √ 2 и соответственно умножают члены X ₀ и X _{N −1} на 1 / √ 2 . Это делает матрицу DCT-I ортогональной , если еще умножить ее на общий масштабный коэффициент , но нарушает прямое соответствие с реальным четным ДПФ.${\displaystyle {\sqrt {\tfrac {2}{N-1}}}}$

DCT-I в точности эквивалентен (с общим масштабным коэффициентом 2) ДПФ действительных чисел с четной симметрией. Например, DCT-I из N  = 5 действительных чисел abcde в точности эквивалентен ДПФ из восьми действительных чисел abcdedcb (даже симметрия), разделенных на два. (Напротив, DCT типов II-IV включают сдвиг на половину выборки в эквивалентном ДПФ.)${\displaystyle 2N-2}$

Однако обратите внимание, что DCT-I не определен для N меньше 2. (Все другие типы DCT определены для любого положительного N. )

Таким образом, DCT-I соответствует граничным условиям: x _n четно около n = 0 и даже около n = N −1; аналогично для X _k .

DCT-II [ править ]

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)k\right]\quad \quad k=0,\dots ,N-1.}$

DCT-II, вероятно, является наиболее часто используемой формой, и ее часто называют просто «DCT». ^{[5] [6]}

Это преобразование в точности эквивалентно (с общим масштабным коэффициентом 2) ДПФ реальных входных данных четной симметрии, где элементы с четным индексом равны нулю. То есть, это половина ДПФ входов , где , для , и для . Преобразование DCT II также возможно с использованием сигнала 2N с последующим умножением на половину сдвига. Это демонстрирует Махул .${\displaystyle 4N}$${\displaystyle 4N}$${\displaystyle y_{n}}$${\displaystyle y_{2n}=0}$${\displaystyle y_{2n+1}=x_{n}}$${\displaystyle 0\leq n<N}$${\displaystyle y_{2N}=0}$${\displaystyle y_{4N-n}=y_{n}}$${\displaystyle 0<n<2N}$

Некоторые авторы дополнительно умножают член X ₀ на 1 / √ 2 и умножают полученную матрицу на общий масштабный коэффициент (см. Ниже соответствующие изменения в DCT-III). Это делает матрицу DCT-II ортогональной , но нарушает прямое соответствие с реальным четным ДПФ полусмещенного ввода. Это нормализация, используемая , например, в Matlab . ^[106] Во многих приложениях, таких как JPEG , масштабирование является произвольным, поскольку масштабные коэффициенты могут быть объединены с последующим этапом вычислений (например, этапом квантования в JPEG ^[107]${\displaystyle {\sqrt {\tfrac {2}{N}}}}$), и можно выбрать масштаб, который позволяет вычислить DCT с меньшим количеством умножений. ^{[108] [109]}

DCT-II подразумевает граничные условия: x _n четно около n = −1/2 и даже около n = N  - 1/2; Х _к даже вокруг K = 0 и нечетное вокруг K = N .

DCT-III [ править ]

${\displaystyle X_{k}={\frac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \left[{\frac {\pi }{N}}n\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1.}$

Поскольку это обратный DCT-II (с точностью до масштабного коэффициента, см. Ниже), эту форму иногда называют просто «обратным DCT» («IDCT»). ^[6]

Некоторые авторы делят член x ₀ на √ 2 вместо 2 (в результате получается общий член x ₀ / √ 2 ) и умножают полученную матрицу на общий масштабный коэффициент (см. Выше соответствующее изменение в DCT-II), так что DCT-II и DCT-III являются транспозициями друг друга. Это делает матрицу DCT-III ортогональной , но нарушает прямое соответствие с реальным четным ДПФ с полусмещенным выходом.${\displaystyle {\sqrt {\tfrac {2}{N}}}}$

DCT-III подразумевает граничные условия: x _n четно около n = 0 и нечетно около n = N ; X _k четно около k = −1/2 и даже около k = N −1/2.

DCT-IV [ править ]

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1.}$

Матрица DCT-IV становится ортогональной (и, таким образом, будучи явно симметричной, своей собственной инверсией), если еще умножить на общий масштабный коэффициент .${\displaystyle {\sqrt {2/N}}}$

Вариант DCT-IV, в котором данные от различных преобразований перекрываются , называется модифицированным дискретным косинусным преобразованием (MDCT). ^[110]

DCT-IV подразумевает граничные условия: x _n четно около n = −1/2 и нечетно около n = N  - 1/2; аналогично для X _k .

DCT V-VIII [ править ]

DCT типов I-IV обрабатывают обе границы последовательно относительно точки симметрии: они четные / нечетные либо вокруг точки данных для обеих границ, либо на полпути между двумя точками данных для обеих границ. Напротив, DCT типов V-VIII подразумевают четные / нечетные границы вокруг точки данных для одной границы и на полпути между двумя точками данных для другой границы.

Другими словами, типы DCT I-IV эквивалентны вещественно-четным ДПФ четного порядка (независимо от того, является ли N четным или нечетным), поскольку соответствующее ДПФ имеет длину 2 ( N  - 1) (для DCT-I) или 4 Н (для DCT-II / III) или 8 Н (для DCT-IV). Четыре дополнительных типа дискретного косинусного преобразования ^{[111] по} существу соответствуют вещественно-четным ДПФ логически нечетного порядка, которые имеют множители N  ± & nbps; ½ в знаменателях аргументов косинуса.

Однако на практике эти варианты используются редко. Одна из причин, возможно, заключается в том, что алгоритмы БПФ для ДПФ нечетной длины обычно сложнее, чем алгоритмы БПФ для ДПФ четной длины (например, простейшие алгоритмы с основанием 2 предназначены только для четных длин), и эта повышенная сложность распространяется и на DCT. как описано ниже.

(Тривиальный вещественно-четный массив, ДПФ длиной один (нечетная длина) одного числа a , соответствует DCT-V длины N = 1.)

Обратные преобразования [ править ]

Используя приведенные выше соглашения о нормализации, обратное значение DCT-I представляет собой DCT-I, умноженное на 2 / ( N  - 1). Обратное ДКП-IV является ДКП-IV , умноженное на 2 / N . Обратным DCT-II является DCT-III, умноженный на 2 / N, и наоборот. ^[6]

Как и для ДПФ , коэффициент нормализации перед этими определениями преобразования является просто условием и различается в зависимости от обработки. Например, некоторые авторы умножают преобразования на, чтобы обратное преобразование не требовало дополнительного мультипликативного множителя. В сочетании с соответствующими множителями √ 2 (см. Выше) это можно использовать, чтобы сделать матрицу преобразования ортогональной .${\displaystyle {\sqrt {2/N}}}$

Многомерные DCT [ править ]

Многомерные варианты различных типов DCT прямо следуют из одномерных определений: они просто отделимый продукт (то есть композиция) DCT по каждому измерению.

MD DCT-II [ править ]

Например, двухмерный DCT-II изображения или матрицы - это просто одномерный DCT-II сверху, выполняемый вдоль строк, а затем вдоль столбцов (или наоборот). То есть 2D DCT-II задается формулой (без нормализации и других масштабных коэффициентов, как указано выше):

${\displaystyle {\begin{aligned}X_{k_{1},k_{2}}&=\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1},n_{2}}\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\right)\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\\&=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1},n_{2}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right].\end{aligned}}}$

Инверсия многомерного DCT - это просто разделимое произведение инверсий соответствующих одномерных DCT (см. Выше), например, одномерные инверсии, применяемые по одному измерению за раз в алгоритме строка-столбец.

3-D ДКП-II , является лишь продолжением 2-D DCT-II в трехмерном пространстве и математически можно вычислить по формуле

${\displaystyle X_{k_{1},k_{2},k_{3}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}\sum _{n_{3}=0}^{N_{3}-1}x_{n_{1},n_{2},n_{3}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\cos \left[{\frac {\pi }{N_{3}}}\left(n_{3}+{\frac {1}{2}}\right)k_{3}\right],\quad {\text{for }}k_{i}=0,1,2,\dots ,N_{i}-1.}$

Обратное к 3-D DCT-II является 3-D DCT-III и может быть вычислено по формуле, представленной

${\displaystyle x_{n_{1},n_{2},n_{3}}=\sum _{k_{1}=0}^{N_{1}-1}\sum _{k_{2}=0}^{N_{2}-1}\sum _{k_{3}=0}^{N_{3}-1}X_{k_{1},k_{2},k_{3}}\cos \left[{\frac {\pi }{N_{1}}}\left(n_{1}+{\frac {1}{2}}\right)k_{1}\right]\cos \left[{\frac {\pi }{N_{2}}}\left(n_{2}+{\frac {1}{2}}\right)k_{2}\right]\cos \left[{\frac {\pi }{N_{3}}}\left(n_{3}+{\frac {1}{2}}\right)k_{3}\right],\quad {\text{for }}n_{i}=0,1,2,\dots ,N_{i}-1.}$

Технически вычисление двух-, трехмерного (или многомерного) DCT с помощью последовательностей одномерных DCT по каждому измерению известно как алгоритм строки-столбца . Как и в случае с многомерными алгоритмами БПФоднако существуют другие методы для вычисления того же самого при выполнении вычислений в другом порядке (т. е. чередование / комбинирование алгоритмов для разных измерений). В связи с быстрым ростом приложений, основанных на 3-D DCT, разработано несколько быстрых алгоритмов для вычисления 3-D DCT-II. Алгоритмы Vector-Radix применяются для вычисления MD DCT, чтобы уменьшить вычислительную сложность и увеличить скорость вычислений. Для эффективного вычисления 3-D DCT-II был разработан быстрый алгоритм векторно-радикального прореживания по частоте (VR DIF).

3-D DCT-II VR DIF [ править ]

Чтобы применить алгоритм VR DIF, входные данные должны быть сформулированы и преобразованы следующим образом. ^{[112] [113]} Предполагается, что размер преобразования N × N × N равен 2.

${\displaystyle {\begin{array}{lcl}{\tilde {x}}(n_{1},n_{2},n_{3})=x(2n_{1},2n_{2},2n_{3})\\{\tilde {x}}(n_{1},n_{2},N-n_{3}-1)=x(2n_{1},2n_{2},2n_{3}+1)\\{\tilde {x}}(n_{1},N-n_{2}-1,n_{3})=x(2n_{1},2n_{2}+1,2n_{3})\\{\tilde {x}}(n_{1},N-n_{2}-1,N-n_{3}-1)=x(2n_{1},2n_{2}+1,2n_{3}+1)\\{\tilde {x}}(N-n_{1}-1,n_{2},n_{3})=x(2n_{1}+1,2n_{2},2n_{3})\\{\tilde {x}}(N-n_{1}-1,n_{2},N-n_{3}-1)=x(2n_{1}+1,2n_{2},2n_{3}+1)\\{\tilde {x}}(N-n_{1}-1,N-n_{2}-1,n_{3})=x(2n_{1}+1,2n_{2}+1,2n_{3})\\{\tilde {x}}(N-n_{1}-1,N-n_{2}-1,N-n_{3}-1)=x(2n_{1}+1,2n_{2}+1,2n_{3}+1)\\\end{array}}}$где ${\displaystyle 0\leq n_{1},n_{2},n_{3}\leq {\frac {N}{2}}-1}$

На рисунке рядом показаны четыре этапа, которые участвуют в вычислении 3-D DCT-II с использованием алгоритма VR DIF. Первый этап - это трехмерное переупорядочение с использованием отображения индекса, проиллюстрированного приведенными выше уравнениями. Второй этап - расчет бабочки. Каждая бабочка вместе вычисляет восемь точек, как показано на рисунке ниже, где .${\displaystyle c(\varphi _{i})=\cos(\varphi _{i})}$

Исходный 3-D DCT-II теперь можно записать как

${\displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}=1}^{N-1}\sum _{n_{2}=1}^{N-1}\sum _{n_{3}=1}^{N-1}{\tilde {x}}(n_{1},n_{2},n_{3})\cos(\varphi k_{1})\cos(\varphi k_{2})\cos(\varphi k_{3})}$

где ${\displaystyle \varphi _{i}={\frac {\pi }{2N}}(4N_{i}+1),{\text{ and }}i=1,2,3.}$

Если даже и нечетные части и и рассматриваются, общая формула для вычисления 3-D DCT-II может быть выражена как${\displaystyle k_{1},k_{2}}$${\displaystyle k_{3}}$

${\displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}=1}^{{\tfrac {N}{2}}-1}\sum _{n_{2}=1}^{{\tfrac {N}{2}}-1}\sum _{n_{1}=1}^{{\tfrac {N}{2}}-1}{\tilde {x}}_{ijl}(n_{1},n_{2},n_{3})\cos(\varphi (2k_{1}+i)\cos(\varphi (2k_{2}+j)\cos(\varphi (2k_{3}+l))}$

где

${\displaystyle {\tilde {x}}_{ijl}(n_{1},n_{2},n_{3})={\tilde {x}}(n_{1},n_{2},n_{3})+(-1)^{l}{\tilde {x}}\left(n_{1},n_{2},n_{3}+{\frac {n}{2}}\right)}$

${\displaystyle +(-1)^{j}{\tilde {x}}\left(n_{1},n_{2}+{\frac {n}{2}},n_{3}\right)+(-1)^{j+l}{\tilde {x}}\left(n_{1},n_{2}+{\frac {n}{2}},n_{3}+{\frac {n}{2}}\right)}$

${\displaystyle +(-1)^{i}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2},n_{3}\right)+(-1)^{i+j}{\tilde {x}}\left(n_{1}+{\frac {n}{2}}+{\frac {n}{2}},n_{2},n_{3}\right)}$

${\displaystyle +(-1)^{i+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2},n_{3}+{\frac {n}{3}}\right)}$

${\displaystyle +(-1)^{i+j+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{2}+{\frac {n}{2}},n_{3}+{\frac {n}{2}}\right){\text{ where }}i,j,l=0{\text{ or }}1.}$

Арифметическая сложность [ править ]

Для всего трехмерного расчета DCT нужны этапы, и каждый этап включает в себя бабочек. Для всего 3-D DCT необходимо вычислить бабочек. Каждая бабочка требует семи реальных умножений (включая тривиальное умножение) и 24 реальных сложений (включая тривиальные сложения). Таким образом, общее количество реальных умножений, необходимых для этого этапа, равно , а общее количество реальных сложений, то есть включая пост-сложения (рекурсивные добавления), которые могут быть вычислены непосредственно после этапа бабочки или после этапа обратного побитового преобразования, задается следующим образом: ^[113] .${\displaystyle [\log _{2}N]}$${\displaystyle N^{3}/8}$${\displaystyle \left[(N^{3}/8)\log _{2}N\right]}$${\displaystyle \left[(7/8)N^{3}\log _{2}N\right]}$ ${\displaystyle \underbrace {\left[{\frac {3}{2}}N^{3}\log _{2}N\right]} _{\text{Real}}+\underbrace {\left[{\frac {3}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]} _{\text{Recursive}}=\left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]}$

Традиционный метод расчета MD-DCT-II использует подход «строка-столбец-кадр» (RCF), который является сложным в вычислительном отношении и менее производительным на самых современных современных аппаратных платформах. Количество умножений, необходимых для вычисления алгоритма VR DIF по сравнению с алгоритмом RCF, довольно невелико. Количество умножений и сложений, задействованных в подходе RCF, обозначено и соответственно. Из таблицы 1 видно, что общее количество${\displaystyle \left[{\frac {3}{2}}N^{3}\log _{2}N\right]}$${\displaystyle \left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]}$

умножений, связанных с алгоритмом 3-D DCT VR, меньше, чем связанное с подходом RCF, более чем на 40%. Кроме того, подход RCF включает в себя транспонирование матрицы и большее количество операций индексации и обмена данными, чем новый алгоритм VR. Это делает алгоритм 3-D DCT VR более эффективным и лучше подходит для 3-D приложений, которые включают 3-D DCT-II, таких как сжатие видео и другие приложения для обработки 3-D изображений. Главное соображение при выборе быстрого алгоритма - избежать вычислительных и структурных сложностей. По мере развития технологий компьютеров и DSP время выполнения арифметических операций (умножения и сложения) становится очень быстрым, и регулярная вычислительная структура становится наиболее важным фактором. ^[114]Следовательно, хотя предложенный выше алгоритм 3-D VR не достигает теоретической нижней границы числа умножений, ^[115] он имеет более простую вычислительную структуру по сравнению с другими алгоритмами 3-D DCT. Он может быть реализован на месте с использованием единственной бабочки и обладает свойствами алгоритма БПФ Кули – Тьюки в трехмерном пространстве . Следовательно, 3-D VR представляет собой хороший выбор для сокращения арифметических операций при вычислении 3-D DCT-II при сохранении простой структуры, характерной для алгоритмов БПФ Кули – Тьюки в стиле бабочки .

Изображение справа показывает комбинацию горизонтальных и вертикальных частот для двумерного DCT 8 x 8 ( ). Каждый шаг слева направо и сверху вниз - это увеличение частоты на 1/2 цикла. Например, перемещение вправо от верхнего левого квадрата дает увеличение на полупериод горизонтальной частоты. Еще одно движение вправо дает два полупериода. Движение вниз дает два полупериода по горизонтали и полупериод по вертикали. Исходные данные (8x8) преобразуются в линейную комбинацию этих 64 квадратов частот.${\displaystyle N_{1}=N_{2}=8}$

MD-DCT-IV [ править ]

MD DCT-IV - это просто расширение 1-D DCT-IV на M размерную область. Двумерный DCT-IV матрицы или изображения задается формулой

${\displaystyle X_{k,l}=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x_{n,m}\cos \left({\frac {(2m+1)(2k+1)\pi }{4N}}\right)\cos \left({\frac {(2n+1)(2l+1)\pi }{4M}}\right){\text{. where }}k=0,1,2...,N-1{\text{ and }}l=0,1,2,\ldots ,M-1.}$

Мы можем вычислить MD DCT-IV, используя обычный метод строка-столбец, или мы можем использовать метод полиномиального преобразования ^[116] для быстрого и эффективного вычисления. Основная идея этого алгоритма заключается в использовании полиномиального преобразования для прямого преобразования многомерного DCT в серию одномерных DCT. MD DCT-IV также имеет несколько приложений в различных областях.

Вычисление [ править ]

Хотя прямое применение этих формул потребует O ( N ² ) операций, можно вычислить то же самое со сложностью только O ( N log N ) путем факторизации вычислений аналогично быстрому преобразованию Фурье (БПФ). Можно также вычислить DCT с помощью БПФ в сочетании с O ( N ) этапами предварительной и постобработки. В общем, методы O ( N log N ) для вычисления DCT известны как алгоритмы быстрого косинусного преобразования (FCT).

В принципе, наиболее эффективными алгоритмами обычно являются те, которые предназначены непосредственно для DCT, в отличие от использования обычного БПФ плюс O ( N ) дополнительных операций (см. Исключение ниже). Однако даже «специализированные» алгоритмы DCT (включая все те, которые достигают наименьшего известного арифметического счета, по крайней мере, для размеров степени двойки ), как правило, тесно связаны с алгоритмами БПФ, поскольку DCT по сути являются ДПФ реальных четных данных, можно разработать быстрый алгоритм DCT, взяв БПФ и исключив избыточные операции из-за этой симметрии. Это можно сделать даже автоматически (Frigo & Johnson, 2005). Алгоритмы, основанные на алгоритме БПФ Кули – Тьюки, являются наиболее распространенными, но применим и любой другой алгоритм БПФ. Например,Алгоритм Винограда БПФ приводит к алгоритмам минимального умножения для ДПФ, хотя, как правило, за счет дополнительных добавлений, и аналогичный алгоритм был предложен Фейгом и Виноградом (1992) для DCT. Поскольку алгоритмы для DFT, DCT и подобных преобразований очень тесно связаны, любое улучшение алгоритмов для одного преобразования теоретически приведет к немедленному улучшению и для других преобразований ( Duhamel & Vetterli, 1990 ).

Хотя алгоритмы DCT, которые используют немодифицированное БПФ, часто имеют некоторые теоретические издержки по сравнению с лучшими специализированными алгоритмами DCT, первые также имеют явное преимущество: широко доступны высокооптимизированные программы БПФ. Таким образом, на практике часто легче получить высокую производительность для общей длины N с помощью алгоритмов на основе БПФ. (Производительность на современном оборудовании обычно не зависит от простого арифметического подсчета, а оптимизация требует значительных инженерных усилий.) С другой стороны, специализированные алгоритмы DCT широко используются для преобразований небольших фиксированных размеров, таких как DCT-II, используемый в JPEG.${\displaystyle 8\times 8}$сжатие или небольшие DCT (или MDCT), обычно используемые при сжатии звука. (Уменьшение размера кода также может быть причиной использования специализированного DCT для приложений встроенных устройств.)

Фактически, даже алгоритмы DCT, использующие обычное БПФ, иногда эквивалентны сокращению избыточных операций из большего БПФ вещественно-симметричных данных, и они могут быть даже оптимальными с точки зрения арифметических подсчетов. Например, DCT типа II эквивалентен DFT размера с вещественно-четной симметрией, чьи четные индексированные элементы равны нулю. Один из наиболее распространенных методов вычисления этого с помощью БПФ (например, метод, используемый в FFTPACK и FFTW ) был описан Narasimha & Peterson (1978) и Makhoul (1980).${\displaystyle 4N}$, и этот метод в ретроспективе можно рассматривать как один из этапов алгоритма децимации во времени с основанием 4 счисления, применяемого к «логическому» ДПФ с вещественной четностью, соответствующему DCT II. (Шаг radix-4 уменьшает размер DFT до четырех размеров - DFT реальных данных, два из которых равны нулю, а два из которых равны друг другу по четной симметрии, что дает единый размер - FFT реальных данных плюс бабочки .) Поскольку элементы с четным индексом равны нулю, этот шаг по основанию счисления-4 в точности совпадает с шагом с разделением по основанию; если последующее БПФ с реальными данными размера также выполняется с помощью алгоритма с разделением на основе реальных данных (как у Соренсена и др., 1987 г.${\displaystyle 4N}$${\displaystyle N}$${\displaystyle N}$${\displaystyle O(N)}$ ${\displaystyle N}$), то полученный алгоритм фактически совпадает с самым низким из опубликованных арифметических подсчетов для DCT-II степени двойки ( действительные арифметические операции ^[a] ). Недавнее сокращение числа операций до также использует БПФ с реальными данными. ^[117] Итак, нет ничего плохого в вычислении DCT с помощью БПФ с арифметической точки зрения - иногда это просто вопрос, является ли соответствующий алгоритм БПФ оптимальным. (На практике накладные расходы на вызов функции при вызове отдельной процедуры БПФ могут быть значительными для small , но это вопрос реализации, а не алгоритмический, поскольку он может быть решен путем развертывания / встраивания.)${\displaystyle 2N\log _{2}N-N+2}$${\displaystyle {\frac {17}{9}}N\log _{2}N+O(N)}$${\displaystyle N}$

Пример IDCT [ править ]

Рассмотрим это изображение большой буквы A в оттенках серого 8x8.

Базисные функции дискретного косинусного преобразования с соответствующими коэффициентами (специфичными для нашего изображения).
DCT изображения = .${\displaystyle {\begin{bmatrix}6.1917&-0.3411&1.2418&0.1492&0.1583&0.2742&-0.0724&0.0561\\0.2205&0.0214&0.4503&0.3947&-0.7846&-0.4391&0.1001&-0.2554\\1.0423&0.2214&-1.0017&-0.2720&0.0789&-0.1952&0.2801&0.4713\\-0.2340&-0.0392&-0.2617&-0.2866&0.6351&0.3501&-0.1433&0.3550\\0.2750&0.0226&0.1229&0.2183&-0.2583&-0.0742&-0.2042&-0.5906\\0.0653&0.0428&-0.4721&-0.2905&0.4745&0.2875&-0.0284&-0.1311\\0.3169&0.0541&-0.1033&-0.0225&-0.0056&0.1017&-0.1650&-0.1500\\-0.2970&-0.0627&0.1960&0.0644&-0.1136&-0.1031&0.1887&0.1444\\\end{bmatrix}}}$

Каждая базовая функция умножается на свой коэффициент, а затем это произведение добавляется к окончательному изображению.

См. Также [ править ]

• Дискретное вейвлет-преобразование
• JPEG # Дискретное косинусное преобразование - содержит потенциально более простой для понимания пример преобразования DCT.
• Список преобразований, связанных с Фурье
• Модифицированное дискретное косинусное преобразование

Пояснительные примечания [ править ]

Цитаты [ править ]

Дальнейшее чтение [ править ]

• Нарасимха, М .; Петерсон, А. (июнь 1978 г.). «О вычислении дискретного косинусного преобразования». Транзакции IEEE по коммуникациям . 26 (6): 934–936. DOI : 10.1109 / TCOM.1978.1094144 .
• Махоул, Дж. (Февраль 1980 г.). «Быстрое косинусное преобразование в одном и двух измерениях». Транзакции IEEE по акустике, речи и обработке сигналов . 28 (1): 27–34. DOI : 10,1109 / TASSP.1980.1163351 .
• Соренсен, H .; Jones, D .; Heideman, M .; Буррус, К. (июнь 1987 г.). «Действительные алгоритмы быстрого преобразования Фурье». Транзакции IEEE по акустике, речи и обработке сигналов . 35 (6): 849–863. CiteSeerX  10.1.1.205.4523 . DOI : 10,1109 / TASSP.1987.1165220 .
• Arai, Y .; Агуи, Т .; Накадзима, М. (ноябрь 1988 г.). «Быстрая схема DCT-SQ для изображений» . Сделки IEICE . 71 (11): 1095–1097.
• Плонка, Г .; Таше, М. (январь 2005 г.). «Быстрые и численно устойчивые алгоритмы дискретных косинусных преобразований» . Линейная алгебра и ее приложения . 394 (1): 309–345. DOI : 10.1016 / j.laa.2004.07.015 .
• Duhamel, P .; Веттерли, М. (апрель 1990 г.). «Быстрые преобразования Фурье: обзор учебного пособия и современное состояние» . Обработка сигналов (Представленная рукопись). 19 (4): 259–299. DOI : 10.1016 / 0165-1684 (90) 90158-U .
• Ахмед, Н. (январь 1991 г.). «Как я придумал дискретное косинусное преобразование» . Цифровая обработка сигналов . 1 (1): 4–9. DOI : 10.1016 / 1051-2004 (91) 90086-Z .
• Feig, E .; Виноград, С. (сентябрь 1992 г.). «Быстрые алгоритмы дискретного косинусного преобразования». Транзакции IEEE по обработке сигналов . 40 (9): 2174–2193. Bibcode : 1992ITSP ... 40.2174F . DOI : 10.1109 / 78.157218 .
• Малвар, Энрике (1992), Обработка сигналов с перекрывающимися преобразованиями , Бостон: Дом Artech, ISBN 978-0-89006-467-2
• Мартуччи, С.А. (май 1994 г.). «Симметричная свертка и дискретные синусоидальные и косинусные преобразования». Транзакции IEEE по обработке сигналов . 42 (5): 1038–1051. Bibcode : 1994ITSP ... 42.1038M . DOI : 10.1109 / 78.295213 .
• Оппенгейм, Алан; Шафер, Рональд; Бак, Джон (1999), Обработка сигналов в дискретном времени (2-е изд.), Верхняя река Сэдл, Нью-Джерси: Prentice Hall, ISBN 978-0-13-754920-7
• Frigo, M .; Джонсон, С. Г. (февраль 2005 г.). «Дизайн и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. CiteSeerX  10.1.1.66.3097 . DOI : 10.1109 / JPROC.2004.840301 . S2CID  6644892 .
• Boussakta, Said .; Алшибами, Хамуд О. (апрель 2004 г.). «Быстрый алгоритм для 3-D DCT-II» (PDF) . Транзакции IEEE по обработке сигналов . 52 (4): 992–1000. Bibcode : 2004ITSP ... 52..992B . DOI : 10.1109 / TSP.2004.823472 . S2CID  3385296 .
• Cheng, LZ; Цзэн, YH (2003). «Новый быстрый алгоритм многомерного ДКП IV типа». Транзакции IEEE по обработке сигналов . 51 (1): 213–220. DOI : 10.1109 / TSP.2002.806558 .
• Вен-Сюн Чен; Smith, C .; Фралик, С. (сентябрь 1977 г.). «Быстрый вычислительный алгоритм для дискретного косинусного преобразования». Транзакции IEEE по коммуникациям . 25 (9): 1004–1009. DOI : 10.1109 / TCOM.1977.1093941 .
• Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), «Раздел 12.4.2. Косинусное преобразование» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN. 978-0-521-88068-8

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме дискретного косинусного преобразования .

• Сайед Али Хайям: Дискретное косинусное преобразование (DCT): теория и применение
• Реализация целочисленной аппроксимации MPEG 8x8 IDCT (ISO / IEC 23002-2)
• Маттео Фриго и Стивен Джонсон : FFTW , http://www.fftw.org/ . Бесплатная ( GPL ) библиотека C, которая может вычислять быстрые DCT (типы I-IV) в одном или нескольких измерениях произвольного размера.
• Такуя Оура: универсальный пакет FFT, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Бесплатные библиотеки C и FORTRAN для вычисления быстрых DCT (типы II – III) в одном, двух или трех измерениях, мощность двух размеров.
• Тим Кинцле: быстрые алгоритмы для вычисления 8-точечного DCT и IDCT, http://drdobbs.com/parallel/184410889 .
• LTFAT - это бесплатный набор инструментов Matlab / Octave с интерфейсами для реализации FFTW DCT и DST типа I-IV.