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

Метод, используемый при обработке сигналов и сжатии данных

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

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

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

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

История

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

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

Дискретное синусоидальное преобразование (DST) было получено из DCT путем замены условия Неймана при x=0 на условие Дирихле . ^{[2] : 35-36} DST было описано в статье 1974 года о DCT Ахмедом, Натараджаном и Рао. ^[5] DST типа I (DST-I) было позднее описано Анилом К. Джайном в 1976 году, а DST типа II (DST-II) было затем описано Х. Б. Кекрой и Дж. К. Соланкой в ​​1978 году. ^[13]

В 1975 году Джон А. Розе и Гунер С. Робинсон адаптировали DCT для межкадрового видеокодирования с компенсацией движения . Они экспериментировали с DCT и быстрым преобразованием Фурье (FFT), разрабатывая межкадровые гибридные кодеры для обоих, и обнаружили, что DCT является наиболее эффективным из-за своей уменьшенной сложности, способным сжимать данные изображения до 0,25 бит на пиксель для сцены видеотелефона с качеством изображения, сопоставимым с внутрикадровым кодером, требующим 2 бита на пиксель. ^{[14] [15]} В 1979 году Анил К. Джейн и Джасвант Р. Джейн дополнительно разработали сжатие видео DCT с компенсацией движения, ^{[16] [17]} также называемое блочной компенсацией движения. ^[17] Это привело к тому, что в 1981 году Чен разработал практический алгоритм сжатия видео, названный DCT с компенсацией движения или адаптивным кодированием сцены. ^[17] Позднее DCT с компенсацией движения стал стандартным методом кодирования для сжатия видео с конца 1980-х годов. ^{[18] [19]}

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

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

Приложения

DCT является наиболее широко используемым методом преобразования в обработке сигналов , ^[29] и, безусловно, наиболее широко используемым линейным преобразованием в сжатии данных . ^[30] Несжатые цифровые носители , а также сжатие без потерь имеют высокие требования к памяти и полосе пропускания , которые значительно снижаются с помощью метода сжатия с потерями DCT , ^{[7] [8]} способного достигать коэффициентов сжатия данных от 8:1 до 14:1 для почти студийного качества, ^[7] до 100:1 для приемлемого качества контента. ^[8] Стандарты сжатия DCT используются в цифровых медиатехнологиях, таких как цифровые изображения , цифровые фотографии , ^{[31] [32]} цифровое видео , ^{[18] [33]} потоковое мультимедиа , ^[34] цифровое телевидение , потоковое телевидение , видео по запросу (VOD), ^[8] цифровое кино , ^[22] видео высокой четкости (HD-видео) и телевидение высокой четкости (HDTV). ^{[7] [35]}

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

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

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

Общие приложения

DCT широко используется во многих приложениях, в том числе:

• Обработка аудиосигнала — аудиокодирование , сжатие аудиоданных (с потерями и без потерь), ^[36] объемный звук , ^[22] подавление акустического эха и обратной связи , распознавание фонем , подавление временного наложения спектров (TDAC) ^[37]
  • Цифровое аудио ^[1]
  • Цифровое радио — цифровое аудиовещание (DAB+), ^[38] HD Radio ^[39]
  • Обработка речи — кодирование речи ^{[40] [41]} распознавание речи , обнаружение голосовой активности (VAD) ^[37]
  • Цифровая телефония — передача голоса по IP (VoIP), ^[40] мобильная телефония , видеотелефония , ^[41] телеконференции , видеоконференции ^[1]
• Биометрия — ориентация по отпечаткам пальцев , системы распознавания лиц , биометрические водяные знаки , биометрические водяные знаки на основе отпечатков пальцев, идентификация/распознавание отпечатков ладоней ^[37]
  • Распознавание лиц — распознавание лиц ^[37]
• Компьютеры и Интернет — Всемирная паутина , социальные сети , ^{[31] [32]} Интернет-видео ^[42]
  • Сокращение использования полосы пропускания сети ^[1]
• Бытовая электроника ^[37] — мультимедийные системы, ^[1] мультимедийные телекоммуникационные устройства, ^[1] потребительские устройства ^[42]
• Криптография — шифрование , стеганография , защита авторских прав ^[37]
• Сжатие данных — кодирование с преобразованием , сжатие с потерями , сжатие без потерь ^[36]
  • Операции кодирования — квантование , перцептивное взвешивание, энтропийное кодирование , кодирование с переменным битрейтом ^[1]
• Цифровые медиа ^[34] — цифровая дистрибуция ^[43]
  • Потоковое мультимедиа ^[34] — потоковое аудио , потоковое видео , потоковое телевидение , видео по запросу (VOD) ^[8]
• Обнаружение подделки ^[37]
• Геофизические переходные электромагнитные явления (переходные ЭМ) ^[37]
• Изображения — идентификация художника , ^{[37] измерение} фокусировки и размытости , ^[37] извлечение признаков ^[37]
  • Форматирование цвета — форматирование яркости и цветовых различий, цветовых форматов (таких как YUV444 и YUV411 ), операций декодирования , таких как обратная операция между цветовыми форматами отображения ( YIQ , YUV , RGB ) ^[1]
  • Цифровое изображение — цифровые изображения , цифровые камеры , цифровая фотография , ^{[31] [32]} изображения с высоким динамическим диапазоном (изображения HDR) ^[44]
  • Сжатие изображения ^{[37] [45]} — форматы файлов изображений , ^{[46] сжатие} многоракурсных изображений , прогрессивная передача изображений ^[37]
  • Обработка изображений — цифровая обработка изображений , ^[1] анализ изображений , поиск изображений на основе содержимого , обнаружение углов , направленное блочное представление изображения , обнаружение краев , улучшение изображения , слияние изображений , сегментация изображений , интерполяция , оценка уровня шума изображения , зеркальное отображение, вращение, профиль едва заметного искажения (JND), эффекты пространственно-временного маскирования, фовеальная визуализация ^[37]
  • Оценка качества изображения — метрика ухудшения качества на основе DCT (DCT QM) ^[37]
  • Реконструкция изображения — автоматическая проверка направленных текстур , восстановление изображения, инрисовка , визуальное восстановление ^[37]
• Медицинские технологии
  • Электрокардиография (ЭКГ) — векторкардиография (ВКГ) ^[37]
  • Медицинская визуализация — сжатие медицинских изображений, слияние изображений, водяные знаки, классификация компрессии опухолей головного мозга ^[37]
• Распознавание образов ^[37]
• Извлечение области интереса (ROI) ^[37]
• Обработка сигналов — цифровая обработка сигналов , цифровые сигнальные процессоры (ЦСП), программное обеспечение ЦСП , мультиплексирование , сигнализация , управляющие сигналы, аналого-цифровое преобразование (АЦП), ^[1] сжатая выборка , маскировка ошибок пирамиды ДКП , понижение частоты дискретизации , повышение частоты дискретизации , оценка отношения сигнал/шум (SNR), трансмультиплексирование , фильтр Винера ^[37]
  • Анализ комплексных характеристик кепстра ^[37]
  • Фильтрация DCT ^[37]
• Наблюдение ^[37]
• Камера регистратора данных о транспортных событиях ^[37]
• Видео
  • Цифровое кино ^[45] — цифровая кинематография , цифровые кинокамеры , видеомонтаж , киномонтаж , ^{[47] [48]} Звук Dolby Digital ^{[1] [22]}
  • Цифровое телевидение (DTV) ^[7] — цифровое телевизионное вещание , ^[45] телевидение стандартной четкости (SDTV), телевидение высокой четкости (HDTV), ^{[7] [35]} микросхемы кодера/декодера HDTV , ультра HDTV (UHDTV) ^[1]
  • Цифровое видео ^{[18] [33]} — цифровой универсальный диск (DVD), ^{[45] видео} высокой четкости (HD) ^{[7] [35]}
  • Видеокодирование — сжатие видео , ^[1] стандарты видеокодирования , ^[37] оценка движения , компенсация движения , межкадровое предсказание, векторы движения , ^[1] 3D-видеокодирование , модель вероятности обнаружения локальных искажений (LDDP), обнаружение движущихся объектов , многовидовое видеокодирование (MVC) ^[37]
  • Обработка видео — анализ движения , анализ движения 3D-DCT, анализ видеоконтента , извлечение данных , ^[37] просмотр видео , ^[49] профессиональное видеопроизводство ^[50]
• Водяные знаки — цифровые водяные знаки , водяные знаки изображений , водяные знаки видео, водяные знаки 3D-видео , обратимое скрытие данных , обнаружение водяных знаков ^[37]
• Беспроводные технологии
  • Мобильные устройства ^[42] — мобильные телефоны , смартфоны , ^[41] видеофоны ^[1]
  • Радиочастотная (РЧ) технология — РЧ-техника , апертурные решетки , ^[37] формирование луча , цифровые арифметические схемы , направленное зондирование , космическая съемка ^[51]
• Беспроводная сенсорная сеть (WSN) — беспроводные акустические сенсорные сети ^[37]

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

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

Целочисленное DCT, целочисленное приближение DCT, ^{[2] [1]} используется в Advanced Video Coding (AVC), ^{[52] [1],} представленном в 2003 году, и High Efficiency Video Coding (HEVC), ^{[4] [1],} представленном в 2013 году. Целочисленное DCT также используется в High Efficiency Image Format (HEIF), который использует подмножество формата видеокодирования HEVC для кодирования неподвижных изображений. ^[4] AVC использует блоки 4 x 4 и 8 x 8. HEVC и HEIF используют различные размеры блоков от 4 x 4 до 32 x 32 пикселей . ^{[4] [1]} По состоянию на 2019 год ^{[обновлять]}AVC является наиболее часто используемым форматом для записи, сжатия и распространения видеоконтента, его используют 91% разработчиков видео, за ним следует HEVC, который используют 43% разработчиков. ^[43]

Форматы изображений

Форматы видео

Стандарты аудио MDCT

Общий звук

Кодирование речи

Многомерное ДКП

Многомерные DCT (MD DCT) имеют несколько приложений, в основном 3-D DCT, такие как 3-D DCT-II, который имеет несколько новых приложений, таких как системы кодирования гиперспектральных изображений, ^[85] 3-D DCT кодирование переменной временной длины, ^[86] алгоритмы видеокодирования , ^[87] адаптивное видеокодирование ^[88] и 3-D сжатие. ^[89] Благодаря усовершенствованию аппаратного обеспечения, программного обеспечения и внедрению нескольких быстрых алгоритмов необходимость использования MD DCT быстро растет. DCT-IV приобрел популярность благодаря своим приложениям в быстрой реализации банков полифазной фильтрации вещественных значений, ^[90] перекрывающегося ортогонального преобразования ^{[91] [92]} и косинусно-модулированных вейвлет-базисов. ^[93]

Цифровая обработка сигнала

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

Артефакты сжатия

Распространенной проблемой сжатия DCT в цифровых носителях являются артефакты блочного сжатия , ^[94] вызванные блоками DCT. ^[3] В алгоритме DCT изображение (или кадр в последовательности изображений) делится на квадратные блоки, которые обрабатываются независимо друг от друга, затем блоки DCT берутся внутри каждого блока, и полученные коэффициенты DCT квантуются . Этот процесс может вызывать артефакты блочного сжатия, в первую очередь при высоких коэффициентах сжатия данных . ^[94] Это также может вызывать эффект комариного шума , обычно встречающийся в цифровом видео . ^[95]

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

Неофициальный обзор

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

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

Иллюстрация неявных четных/нечетных расширений входных данных DCT для N =11 точек данных (красные точки) для четырех наиболее распространенных типов DCT (типы I-IV). Обратите внимание на тонкие различия в интерфейсах между данными и расширениями: в DCT-II и DCT-IV обе конечные точки реплицируются в расширениях, но не в DCT-I или DCT-III (и нулевая точка вставляется в расширение смены знака в DCT-III).

Однако, поскольку DCT работают с конечными дискретными последовательностями , возникают две проблемы, которые не применимы к непрерывному косинусному преобразованию. Во-первых, необходимо указать, является ли функция четной или нечетной как на левой, так и на правой границе области (т. е. на границах min- n и max- n в определениях ниже соответственно). Во-вторых, необходимо указать, около какой точки функция является четной или нечетной. В частности, рассмотрим последовательность abcd из четырех равноотстоящих точек данных и скажем, что мы указываем четную левую границу. Есть две разумные возможности: либо данные четны относительно образца a , в этом случае четное расширение равно 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. Существует несколько вариантов ДКП с немного измененными определениями. N действительных чисел преобразуются в N действительных чисел по одной из формул: ${\displaystyle f:\mathbb {R} ^{N}\to \mathbb {R} ^{N}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle ~x_{0},\ \ldots \ x_{N-1}~}$ ${\displaystyle X_{0},\,\ldots ,\,X_{N-1}}$

DCT-I

${\displaystyle X_{k}={\frac {1}{2}}(x_{0}+(-1)^{k}x_{N-1})+\sum _{n=1}^{N-2}x_{n}\cos \left[\,{\tfrac {\ \pi }{\,N-1\,}}\,n\,k\,\right]\qquad {\text{ for }}~k=0,\ \ldots \ N-1~.}$

Некоторые авторы дополнительно умножают члены и на и соответственно умножают члены и на , которые, если их дополнительно умножить на общий масштабный коэффициент , делают матрицу ДКП-I ортогональной , но нарушают прямое соответствие с действительно-четным ДПФ . ${\displaystyle x_{0}}$ ${\displaystyle x_{N-1}}$ ${\displaystyle {\sqrt {2\,}}\,,}$ ${\displaystyle X_{0}}$ ${\displaystyle X_{N-1}}$ ${\displaystyle 1/{\sqrt {2\,}}\,,}$ ${\displaystyle {\sqrt {{\tfrac {2}{N-1\,}}\,}},}$

DCT-I в точности эквивалентно (до общего масштабного коэффициента 2) DFT действительных чисел с четной симметрией. Например, DCT-I действительных чисел в точности эквивалентно DFT восьми действительных чисел (четная симметрия), разделенных на два. (В отличие от этого, типы DCT II-IV включают сдвиг на половину выборки в эквивалентном DFT.) ${\displaystyle 2(N-1)}$ ${\displaystyle N=5}$ ${\displaystyle a\ b\ c\ d\ e}$ ${\displaystyle a\ b\ c\ d\ e\ d\ c\ b}$

Однако следует отметить, что DCT-I не определен для значений менее 2, в то время как все другие типы DCT определены для любых положительных значений. ${\displaystyle N}$ ${\displaystyle N.}$

Таким образом, DCT-I соответствует граничным условиям: равномерен вокруг и равномерен вокруг ; аналогично для ${\displaystyle x_{n}}$ ${\displaystyle n=0}$ ${\displaystyle n=N-1}$ ${\displaystyle X_{k}.}$

DCT-II

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

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

Это преобразование в точности эквивалентно (до общего масштабного коэффициента 2) ДПФ действительных входов четной симметрии, где четные индексированные элементы равны нулю. То есть, это половина ДПФ входов , где для и для преобразования ДКП-II также возможно использование сигнала 2 N с последующим умножением на половину сдвига. Это демонстрирует Макхул . ${\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.}$

Некоторые авторы дополнительно умножают член на и умножают остальную часть матрицы на общий масштабный коэффициент (см. ниже соответствующее изменение в DCT-III). Это делает матрицу DCT-II ортогональной , но нарушает прямое соответствие с действительно-четным DFT полусмещенного ввода. Это нормализация, используемая Matlab , например, см. ^[99] Во многих приложениях, таких как JPEG , масштабирование произвольно, поскольку масштабные коэффициенты можно объединить с последующим вычислительным шагом (например, шагом квантования в JPEG ^[100] ), и можно выбрать масштабирование, которое позволяет вычислять DCT с меньшим количеством умножений. ^{[101] [102]} ${\displaystyle X_{0}}$ ${\displaystyle 1/{\sqrt {N\,}}\,}$ ${\textstyle {\sqrt {{2}/{N}}}}$

DCT-II подразумевает граничные условия: четно вокруг и четно вокруг четно вокруг и нечетно вокруг ${\displaystyle x_{n}}$ ${\displaystyle n=-1/2}$ ${\displaystyle n=N-1/2\,;}$ ${\displaystyle X_{k}}$ ${\displaystyle k=0}$ ${\displaystyle k=N.}$

DCT-III

${\displaystyle X_{k}={\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\left(k+{\tfrac {1}{2}}\right)n\,\right]\qquad {\text{ for }}~k=0,\ \ldots \ N-1~.}$

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

Некоторые авторы делят член на вместо на 2 (что приводит к общему члену) и умножают полученную матрицу на общий масштабный коэффициент (см. выше соответствующее изменение в DCT-II), так что DCT-II и DCT-III являются транспонированными друг друга. Это делает матрицу DCT-III ортогональной , но нарушает прямое соответствие с действительно-четным DFT полусдвинутого вывода. ${\displaystyle x_{0}}$ ${\displaystyle {\sqrt {2}}}$ ${\displaystyle x_{0}/{\sqrt {2}}}$ ${\textstyle {\sqrt {2/N}}}$

DCT-III подразумевает граничные условия: четно вокруг и нечетно вокруг четно вокруг и четно вокруг ${\displaystyle x_{n}}$ ${\displaystyle n=0}$ ${\displaystyle n=N;}$ ${\displaystyle X_{k}}$ ${\displaystyle k=-1/2}$ ${\displaystyle k=N-1/2.}$

DCT-IV

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[\,{\tfrac {\,\pi \,}{N}}\,\left(n+{\tfrac {1}{2}}\right)\left(k+{\tfrac {1}{2}}\right)\,\right]\qquad {\text{ for }}k=0,\ \ldots \ N-1~.}$

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

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

DCT-IV подразумевает граничные условия: четно вокруг и нечетно вокруг аналогично для ${\displaystyle x_{n}}$ ${\displaystyle n=-1/2}$ ${\displaystyle n=N-1/2;}$ ${\displaystyle X_{k}.}$

DCT V-VIII

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

Другими словами, типы DCT I–IV эквивалентны действительно-четным DFT четного порядка (независимо от того, четное оно или нечетное), поскольку соответствующее DFT имеет длину (для DCT-I) или (для DCT-II и III) или (для DCT-IV). Четыре дополнительных типа дискретного косинусного преобразования ^[104] по сути соответствуют действительно-четным DFT логически нечетного порядка, которые имеют множители в знаменателях косинусных аргументов. ${\displaystyle N}$ ${\displaystyle 2(N-1)}$ ${\displaystyle 4N}$ ${\displaystyle 8N}$ ${\displaystyle N\pm {1}/{2}}$

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

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

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

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

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

Многомерные DCT

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

MD DCT-II

Например, двумерное DCT-II изображения или матрицы — это просто одномерное DCT-II, сверху, выполненное вдоль строк, а затем вдоль столбцов (или наоборот). То есть, двумерное 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 DCT-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 вдоль каждого измерения известно как алгоритм строки-столбца . Однако, как и в случае с многомерными алгоритмами FFT , существуют и другие методы вычисления того же самого, выполняя вычисления в другом порядке (т. е. чередование/объединение алгоритмов для разных измерений). В связи с быстрым ростом приложений, основанных на 3-D DCT, разработано несколько быстрых алгоритмов для вычисления 3-D DCT-II. Векторно-радикальные алгоритмы применяются для вычисления MD DCT, чтобы уменьшить вычислительную сложность и увеличить скорость вычислений. Для эффективного вычисления 3-D DCT-II был разработан быстрый алгоритм, алгоритм векторно-радикального прореживания по частоте (VR DIF).

3-D DCT-II VR DIF

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

Четыре основных этапа вычисления 3-D DCT-II с использованием алгоритма VR DIF.

${\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. Первый этап - это 3-D переупорядочение с использованием индексного отображения, проиллюстрированного приведенными выше уравнениями. Второй этап - это вычисление бабочки. Каждая бабочка вычисляет восемь точек вместе, как показано на рисунке чуть ниже, где . ${\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.}$

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

Одиночный этап бабочки алгоритма VR DIF.

${\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.}$

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

Для всего вычисления 3-D DCT нужны этапы, и каждый этап включает в себя бабочек. Для всего вычисления 3-D DCT требуются бабочки. Для каждой бабочки требуется семь действительных умножений (включая тривиальные умножения) и 24 действительных сложения (включая тривиальные сложения). Таким образом, общее количество действительных умножений, необходимых для этого этапа, равно , а общее количество действительных сложений, т.е. включая пост-сложения (рекурсивные сложения), которые могут быть вычислены непосредственно после этапа бабочки или после этапа реверса битов, определяется как ^[106] ${\displaystyle ~[\log _{2}N]~}$ ${\displaystyle ~{\tfrac {1}{8}}\ N^{3}~}$ ${\displaystyle ~\left[{\tfrac {1}{8}}\ N^{3}\log _{2}N\right]~}$ ${\displaystyle ~\left[{\tfrac {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 заключается в использовании подхода Row-Column-Frame (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 время выполнения арифметических операций (умножений и сложений) становится очень быстрым, и регулярная вычислительная структура становится наиболее важным фактором. ^[107] Поэтому, хотя предложенный выше алгоритм 3-D VR не достигает теоретической нижней границы числа умножений, ^[108] он имеет более простую вычислительную структуру по сравнению с другими алгоритмами 3-D DCT. Он может быть реализован на месте с использованием одной бабочки и обладает свойствами алгоритма Кули-Тьюки FFT в 3-D. Следовательно, 3-D VR представляет собой хороший выбор для сокращения арифметических операций при вычислении 3-D DCT-II, сохраняя при этом простую структуру, характерную для алгоритмов Кули-Тьюки FFT в стиле бабочки .

Двумерные частоты DCT из JPEG DCT

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

MD-DCT-IV

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

${\displaystyle X_{k,\ell }=\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)(2\ell +1)\ \pi \,}{4M}}\ \right)~,}$

для и ${\displaystyle ~~k=0,\ 1,\ 2\ \ldots \ N-1~~}$ ${\displaystyle ~~\ell =0,\ 1,\ 2,\ \ldots \ M-1~.}$

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

Вычисление

Хотя прямое применение этих формул потребовало бы операций, можно вычислить то же самое с только сложностью, факторизуя вычисление аналогично быстрому преобразованию Фурье (БПФ). Можно также вычислять ДКП с помощью БПФ в сочетании с этапами предварительной и последующей обработки. В общем, методы вычисления ДКП известны как алгоритмы быстрого косинусного преобразования (БКП). ${\displaystyle ~{\mathcal {O}}(N^{2})~}$ ${\displaystyle ~{\mathcal {O}}(N\log N)~}$ ${\displaystyle ~{\mathcal {O}}(N)~}$ ${\displaystyle ~{\mathcal {O}}(N\log N)~}$

Наиболее эффективными алгоритмами, в принципе, обычно являются те, которые специализированы непосредственно для DCT, в отличие от использования обычного FFT плюс дополнительных операций (см. ниже исключение). Однако даже «специализированные» алгоритмы DCT (включая все те, которые достигают наименьших известных арифметических подсчетов, по крайней мере для размеров степени двойки ) обычно тесно связаны с алгоритмами FFT — поскольку DCT по сути являются DFT вещественно-четных данных, можно разработать быстрый алгоритм DCT, взяв FFT и исключив избыточные операции из-за этой симметрии. Это можно сделать даже автоматически (Frigo & Johnson 2005). Алгоритмы, основанные на алгоритме Cooley–Tukey FFT, наиболее распространены, но применим также любой другой алгоритм FFT. Например, алгоритм Winograd FFT приводит к алгоритмам минимального умножения для DFT, хотя, как правило, за счет большего количества сложений, и аналогичный алгоритм был предложен (Feig & Winograd 1992a) для DCT. Поскольку алгоритмы для DFT, DCT и подобных преобразований настолько тесно связаны, любое улучшение алгоритмов для одного преобразования теоретически приведет к немедленному улучшению и для других преобразований (Дюамель и Веттерли, 1990). ${\displaystyle ~{\mathcal {O}}(N)~}$

Хотя алгоритмы DCT, использующие немодифицированный FFT, часто имеют некоторые теоретические накладные расходы по сравнению с лучшими специализированными алгоритмами DCT, первые также имеют явное преимущество: высокооптимизированные программы FFT широко доступны. Таким образом, на практике часто проще получить высокую производительность для общих длин N с помощью алгоритмов на основе FFT. ^[a] Специализированные алгоритмы DCT, с другой стороны, широко используются для преобразований небольших фиксированных размеров, таких как 8 × 8 DCT-II, используемый в сжатии JPEG , или небольшие DCT (или MDCT), обычно используемые в сжатии звука. (Уменьшенный размер кода также может быть причиной использования специализированного DCT для приложений встроенных устройств.)

Фактически, даже алгоритмы DCT, использующие обычное БПФ, иногда эквивалентны отсечению избыточных операций из большего БПФ вещественно-симметричных данных, и они даже могут быть оптимальными с точки зрения арифметических подсчетов. Например, ДКП типа II эквивалентно ДПФ размера с вещественно-четной симметрией, четно-индексированные элементы которой равны нулю. Один из наиболее распространенных методов вычисления этого с помощью БПФ (например, метод, используемый в FFTPACK и FFTW ) был описан Нарасимхой и Петерсоном (1978) и Макхулом (1980), и этот метод в ретроспективе можно рассматривать как один шаг алгоритма Кули–Тьюки с прореживанием по основанию 4 во времени, применяемого к «логическому» вещественно-четному ДПФ, соответствующему ДКП-II. ^[b] Поскольку четно-индексированные элементы равны нулю, этот шаг по основанию 4 в точности совпадает с шагом разделения по основанию. Если последующее БПФ для действительных данных также выполняется с помощью алгоритма разделения оснований действительных данных (как в работе Соренсена и др. (1987)), то полученный алгоритм фактически соответствует тому, что долгое время было наименьшим опубликованным арифметическим подсчетом для степени двойки DCT-II ( действительные арифметические операции ^[c] ). ${\displaystyle ~4N~}$ ${\displaystyle ~N~}$ ${\displaystyle ~2N\log _{2}N-N+2~}$

Недавнее сокращение числа операций до также использует БПФ с реальными данными. ^[110] Таким образом, нет ничего изначально плохого в вычислении DCT с помощью БПФ с арифметической точки зрения — иногда это просто вопрос оптимальности соответствующего алгоритма БПФ. (С практической точки зрения накладные расходы на вызов функции при вызове отдельной процедуры БПФ могут быть значительными для small, но это вопрос реализации, а не алгоритма, поскольку его можно решить путем развертывания или встраивания.) ${\displaystyle ~{\tfrac {17}{9}}N\log _{2}N+{\mathcal {O}}(N)}$ ${\displaystyle ~N~,}$

Пример IDCT

Пример, демонстрирующий восемь различных фильтров, примененных к тестовому изображению (вверху слева) путем умножения его спектра DCT (вверху справа) на каждый фильтр.

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

Исходный размер, масштаб 10x (ближайший сосед), масштаб 10x (билинейный).

Базисные функции дискретного косинусного преобразования с соответствующими коэффициентами (специфичными для нашего изображения).
ДКП изображения = . ${\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}}}$

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

Слева — конечное изображение. Посередине — взвешенная функция (умноженная на коэффициент), которая добавляется к конечному изображению. Справа — текущая функция и соответствующий коэффициент. Изображения масштабируются (с использованием билинейной интерполяции) с коэффициентом 10×.

Смотрите также

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

Примечания

1. Алгоритмическая производительность на современном оборудовании обычно не определяется простыми арифметическими подсчетами, и оптимизация требует значительных инженерных усилий для наилучшего использования (в рамках ее внутренних ограничений) доступных встроенных возможностей аппаратной оптимизации.
2. Шаг radix-4 уменьшает размер DFT до четырех размеров DFT реальных данных, два из которых равны нулю, а два из которых равны друг другу по четной симметрии. Таким образом, давая единый размер FFT реальных данных плюс бабочки , как только тривиальные и/или дублирующие части устранены и/или объединены. ${\displaystyle ~4N~}$ ${\displaystyle ~N~}$ ${\displaystyle ~N~}$ ${\displaystyle ~{\mathcal {O}}(N)~}$
3. Точное количество действительных арифметических операций, и в частности количество действительных умножений, в некоторой степени зависит от масштабирования определения преобразования. Количество для определения DCT-II, показанного здесь; два умножения могут быть сохранены, если преобразование масштабируется общим множителем . Дополнительные умножения могут быть сохранены, если разрешить масштабировать выходные данные преобразования по отдельности, как было показано Араи, Агуи и Накадзимой (1988) для случая размера 8, используемого в JPEG. ${\displaystyle ~2N\log _{2}N-N+2~}$ ${\displaystyle {\sqrt {2}}}$

Ссылки

1. Станкович, Радомир С.; Астола, Яакко Т. (2012). "Воспоминания о ранней работе в области DCT: интервью с К. Р. Рао" (PDF) . Перепечатки с ранних дней информационных наук . 60 . Международный центр обработки сигналов в Тампере. ISBN 978-9521528187. ISSN  1456-2774. Архивировано (PDF) из оригинала 30 декабря 2021 г. . Получено 30 декабря 2021 г. – через ETHW .
2. Британак, Владимир; Йип, Патрик К.; Рао, КР (6 ноября 2006 г.). Дискретные косинусные и синусные преобразования: общие свойства, быстрые алгоритмы и целочисленные аппроксимации . Academic Press . ISBN 978-0123736246. LCCN  2006931102. OCLC  220853454. OL  18495589М. S2CID  118873224.
3. Алихани, Дарья (1 апреля 2015 г.). "За пределами разрешения: глитч-арт Розы Менкман". POSTmatter . Архивировано из оригинала 19 октября 2019 г. Получено 19 октября 2019 г.
4. Томсон, Гэвин; Шах, Атар (2017). "Введение в HEIF и HEVC" (PDF) . Apple Inc. Получено 5 августа 2019 г. .
5. Ахмед, Насир ; Натараджан, Т. Радж; Рао, КР (1 января 1974 г.). «Дискретное косинусное преобразование». Транзакции IEEE на компьютерах . С-23 (1). Компьютерное общество IEEE: 90–93. дои : 10.1109/TC.1974.223784. eISSN  1557-9956. ISSN  0018-9340. LCCN  75642478. OCLC  1799331. S2CID  206619973.
6. Рао, К. Рамамохан ; Йип, Патрик К. (11 сентября 1990 г.). Дискретное косинусное преобразование: алгоритмы, преимущества, приложения . Обработка сигналов, изображений и речи. Academic Press . arXiv : 1109.0337 . doi :10.1016/c2009-0-22279-3. ISBN 978-0125802031. LCCN  89029800. OCLC  1008648293. ОЛ  2207570М. S2CID  12270940.
7. Barbero, M.; Hofmann, H.; Wells, ND (14 ноября 1991 г.). «Исходное кодирование DCT и текущие реализации для HDTV». Технический обзор EBU (251). Европейский вещательный союз : 22–33 . Получено 4 ноября 2019 г. .
8. Lea, William (1994). "Видео по запросу: исследовательская работа 94/68". Библиотека Палаты общин . Получено 20 сентября 2019 г.
9. Ahmed, Nasir (январь 1991 г.). «Как я придумал дискретное косинусное преобразование» (PDF) . Цифровая обработка сигналов . 1 (1): 4–5. Bibcode : 1991DSP.....1....4A. doi : 10.1016/1051-2004(91)90086-Z.
10. "T.81 – Цифровое сжатие и кодирование неподвижных изображений с непрерывным тоном – Требования и рекомендации" (PDF) . CCITT . Сентябрь 1992 . Получено 12 июля 2019 .
11. Чен, Вэнь-Сюн; Смит, CH; Фралик, SC (сентябрь 1977 г.). «Быстрый вычислительный алгоритм для дискретного косинусного преобразования». Труды IEEE по коммуникациям . 25 (9): 1004–1009. doi :10.1109/TCOM.1977.1093941.
12. Смит, К.; Фралик, С. (1977). «Быстрый вычислительный алгоритм для дискретного косинусного преобразования». IEEE Transactions on Communications . 25 (9): 1004–1009. doi :10.1109/TCOM.1977.1093941. ISSN  0090-6778.
13. Дхамиджа, Свати; Джейн, Приянка (сентябрь 2011 г.). «Сравнительный анализ дискретного синусоидального преобразования как подходящего метода оценки шума». IJCSI International Journal of Computer Science . 8 (5, № 3): 162–164 (162) . Получено 4 ноября 2019 г.
14. Хуан, ТС (1981). Анализ последовательности изображений. Springer Science & Business Media . стр. 29. ISBN 9783642870378.
15. Roese, John A.; Robinson, Guner S. (30 октября 1975 г.). Tescher, Andrew G. (ред.). "Combined Spatial And Temporal Coding Of Digital Image Sequences". Эффективная передача изобразительной информации . 0066. Международное общество оптики и фотоники: 172–181. Bibcode : 1975SPIE...66..172R. doi : 10.1117/12.965361. S2CID  62725808.
16. Cianci, Philip J. (2014). Телевидение высокой четкости: создание, разработка и внедрение технологии HDTV. McFarland. стр. 63. ISBN 9780786487974.
17. "История сжатия видео". ITU-T . Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6). Июль 2002 г. стр. 11, 24–9, 33, 40–1, 53–6 . Получено 3 ноября 2019 г.
18. Ghanbari, Mohammed (2003). Стандартные кодеки: сжатие изображений для усовершенствованного кодирования видео. Институт инженерии и технологий . стр. 1–2. ISBN 9780852967102.
19. Ли, Цзянь Пин (2006). Труды Международной компьютерной конференции 2006 года по технологии вейвлет-активных медиа и обработке информации: Чунцин, Китай, 29-31 августа 2006 г. World Scientific . стр. 847. ISBN 9789812709998.
20. Princen, John P.; Johnson, AW; Bradley, Alan B. (1987). «Кодирование подполос/преобразований с использованием конструкций банка фильтров на основе отмены наложения спектров во временной области». ICASSP '87. Международная конференция IEEE по акустике, речи и обработке сигналов . Том 12. С. 2161–2164. doi :10.1109/ICASSP.1987.1169405. S2CID  58446992.
21. Принсен, Дж.; Брэдли, А. (1986). «Проект банка фильтров анализа/синтеза на основе отмены наложения спектров во временной области». Труды IEEE по акустике, речи и обработке сигналов . 34 (5): 1153–1161. doi :10.1109/TASSP.1986.1164954.
22. Luo, Fa-Long (2008). Стандарты мобильного мультимедийного вещания: технология и практика. Springer Science & Business Media . стр. 590. ISBN 9780387782638.
23. Britanak, V. (2011). «О свойствах, отношениях и упрощенной реализации банков фильтров в стандартах аудиокодирования Dolby Digital (Plus) AC-3». Труды IEEE по обработке звука, речи и языка . 19 (5): 1231–1241. doi :10.1109/TASL.2010.2087755. S2CID  897622.
24. Guckert, John (весна 2012 г.). «Использование FFT и MDCT в сжатии аудио MP3» (PDF) . University of Utah . Получено 14 июля 2019 г. .
25. Brandenburg, Karlheinz (1999). "MP3 и AAC Explained" (PDF) . Архивировано (PDF) из оригинала 2017-02-13.
26. Xiph.Org Foundation (2009-06-02). "Спецификация Vorbis I - 1.1.2 Классификация". Xiph.Org Foundation . Получено 2009-09-22 .
27. Mandyam, Giridhar D. ; Ahmed, Nasir; Magotra, Neeraj (17 апреля 1995 г.). Rodriguez, Arturo A.; Safranek, Robert J.; Delp, Edward J. (ред.). "Схема на основе DCT для сжатия изображений без потерь". Цифровое видеосжатие: алгоритмы и технологии 1995 . 2419 . Международное общество оптики и фотоники: 474–478. Bibcode :1995SPIE.2419..474M. doi :10.1117/12.206386. S2CID  13894279.
28. Комацу, К.; Сезаки, Каору (1998). «Обратимое дискретное косинусное преобразование». Труды Международной конференции IEEE 1998 года по акустике, речи и обработке сигналов, ICASSP '98 (Cat. No.98CH36181) . Том 3. С. 1769–1772, том 3. doi :10.1109/ICASSP.1998.681802. ISBN 0-7803-4428-6. S2CID  17045923.
29. Мучахари, Д.; Мондал, А. Дж.; Пармар, Р. С.; Борах, А. Д.; Маджумдер, А. (2015). «Упрощенный подход к проектированию для эффективного вычисления DCT». Пятая международная конференция по системам связи и сетевым технологиям 2015 г. стр. 483–487. doi :10.1109/CSNT.2015.134. ISBN 978-1-4799-1797-6. S2CID  16411333.
30. Чен, Вай Кай (2004). Справочник по электротехнике. Elsevier . стр. 906. ISBN 9780080477480.
31. "Что такое JPEG? Невидимый объект, который вы видите каждый день". The Atlantic . 24 сентября 2013 г. Получено 13 сентября 2019 г.
32. Pessina, Лора-Анн (12 декабря 2014 г.). «JPEG изменил наш мир». Новости ЭПФЛ . Федеральная политехническая школа Лозанны . Проверено 13 сентября 2019 г.
33. Lee, Ruby Bei-Loh; Beck, John P.; Lamb, Joel; Severson, Kenneth E. (апрель 1995 г.). "Программный декодер видео MPEG в реальном времени на процессорах PA 7100LC с расширенными возможностями мультимедиа" (PDF) . Hewlett-Packard Journal . 46 (2). ISSN  0018-1153.
34. Ли, Джек (2005). Масштабируемые системы непрерывной потоковой передачи мультимедиа: архитектура, проектирование, анализ и реализация. John Wiley & Sons . стр. 25. ISBN 9780470857649.
35. Shishikui, Yoshiaki; Nakanishi, Hiroshi; Imaizumi, Hiroyuki (26–28 октября 1993 г.). "Схема кодирования HDTV с использованием адаптивного DCT". Обработка сигналов HDTV . Elsevier . стр. 611–618. doi :10.1016/B978-0-444-81844-7.50072-3. ISBN 9781483298511.
36. Очоа-Домингес, Умберто; Рао, КР (2019). Дискретное косинусное преобразование, второе издание. CRC Press . стр. 1–3, 129. ISBN 9781351396486.
37. Очоа-Домингес, Умберто; Рао, КР (2019). Дискретное косинусное преобразование, второе издание. CRC Press . стр. 1–3. ISBN 9781351396486.
38. Британак, Владимир; Рао, КР (2017). Косинусно-/синусно-модулированные банки фильтров: общие свойства, быстрые алгоритмы и целочисленные приближения. Springer. стр. 478. ISBN 9783319610801.
39. Jones, Graham A.; Layer, David H.; Osenkowsky, Thomas G. (2013). Справочник по инжинирингу Национальной ассоциации вещателей: Справочник по инжинирингу NAB. Taylor & Francis . стр. 558–9. ISBN 978-1-136-03410-7.
40. Hersent, Olivier; Petit, Jean-Pierre; Gurle, David (2005). Beyond VoIP Protocols: Understanding Voice Technology and Networking Techniques for IP Telephony. John Wiley & Sons . стр. 55. ISBN 9780470023631.
41. Дэниел Эран Дилгер (8 июня 2010 г.). «Внутри iPhone 4: видеозвонки FaceTime». AppleInsider . Получено 9 июня 2010 г.
42. Netflix Technology Blog (19 апреля 2017 г.). «Более эффективные мобильные кодировки для загрузок Netflix». Medium.com . Netflix . Получено 20 октября 2019 г. .
43. "Video Developer Report 2019" (PDF) . Bitmovin . 2019 . Получено 5 ноября 2019 .
44. Очоа-Домингес, Умберто; Рао, КР (2019). Дискретное косинусное преобразование, второе издание. CRC Press. стр. 186. ISBN 9781351396486.
45. МакКернан, Брайан (2005). Цифровое кино: революция в кинематографии, постпроизводстве, дистрибуции. McGraw-Hill . стр. 58. ISBN 978-0-07-142963-4. DCT используется в большинстве систем сжатия, стандартизированных Moving Picture Experts Group (MPEG), является доминирующей технологией сжатия изображений. В частности, это основная технология MPEG-2, системы, используемой для DVD, цифрового телевизионного вещания, которая использовалась во многих испытаниях цифрового кино.
46. Baraniuk, Chris (15 октября 2015 г.). «Защита от копирования может появиться в JPeg». BBC News . BBC . Получено 13 сентября 2019 г. .
47. Эшер, Стивен; Пинкус, Эдвард (2012). Справочник кинорежиссера: всеобъемлющее руководство для цифровой эпохи: пятое издание. Penguin. С. 246–247. ISBN 978-1-101-61380-1.
48. Бертальмио, Марсело (2014). Обработка изображений для кино. ЦРК Пресс . п. 95. ИСБН 978-1-4398-9928-1.
49. Чжан, Хунцзян (1998). «Просмотр и извлечение видео на основе контента». В Furht, Borko (ред.). Справочник по Интернету и мультимедийным системам и приложениям. CRC Press . С. 83–108 (89). ISBN 9780849318580.
50. "Apple ProRes 422 Codec Family". Библиотека Конгресса . 17 ноября 2014 г. Получено 13 октября 2019 г.
51. Potluri, US; Madanayake, A.; Cintra, RJ; Bayer, FM; Rajapaksha, N. (17 октября 2012 г.). "Безмножительные приближения DCT для многолучевой цифровой апертурной решетки в пространстве и направленного зондирования". Measurement Science and Technology . 23 (11): 114003. doi :10.1088/0957-0233/23/11/114003. ISSN  0957-0233. S2CID  119888170.
52. Wang, Hanli; Kwong, S.; Kok, C. (2006). "Эффективный алгоритм прогнозирования целочисленных коэффициентов DCT для оптимизации H.264 / AVC". IEEE Transactions on Circuits and Systems for Video Technology . 16 (4): 547–552. doi :10.1109/TCSVT.2006.871390. S2CID  2060937.
53. Хадсон, Грэм; Леже, Ален; Нисс, Биргер; Себастьен, Иштван; Ваабен, Йорген (31 августа 2018 г.). «Стандарту JPEG-1 25 лет: причины успеха в прошлом, настоящем и будущем». Журнал электронных изображений . 27 (4): 1. doi : 10.1117/1.JEI.27.4.040901 .
54. "Объяснение формата изображения JPEG". BT.com . BT Group . 31 мая 2018 г. Получено 5 августа 2019 г.
55. "Сравнение HEIF - Высокоэффективный формат файла изображения". Nokia Technologies . Получено 5 августа 2019 г.
56. Alakuijala, Jyrki; Sneyers, Jon; Versari, Luca; Wassenberg, Jan (22 января 2021 г.). "JPEG XL White Paper" (PDF) . JPEG Org . Архивировано (PDF) из оригинала 2 мая 2021 г. . Получено 14 января 2022 г. . DCT переменного размера (квадратное или прямоугольное от 2x2 до 256x256) служит быстрой аппроксимацией оптимального декоррелирующего преобразования.
57. Wang, Yao (2006). "Стандарты кодирования видео: Часть I" (PDF) . Архивировано из оригинала (PDF) 2013-01-23.
58. Ван, Яо (2006). "Стандарты кодирования видео: Часть II" (PDF) . Архивировано из оригинала (PDF) 2013-01-23.
59. Хоффман, Рой (2012). Сжатие данных в цифровых системах. Springer Science & Business Media . стр. 255. ISBN 9781461560319.
60. Rao, KR ; Hwang, JJ (18 июля 1996 г.). Методы и стандарты кодирования изображений, видео и аудио . Prentice Hall. JPEG: Глава 8; H.261 : Глава 9; MPEG-1: Глава 10; MPEG-2: Глава 11. ISBN 978-0133099072. LCCN  96015550. OCLC  34617596. OL  978319M. S2CID  56983045.
61. Дэвис, Эндрю (13 июня 1997 г.). «Обзор рекомендаций H.320». EE Times . Получено 7 ноября 2019 г.
62. IEEE WESCANEX 97: коммуникации, электроэнергия и вычисления: материалы конференции. Университет Манитобы, Виннипег, Манитоба, Канада: Институт инженеров по электротехнике и электронике . 22–23 мая 1997 г. стр. 30. ISBN 9780780341470. H.263 похож на H.261 , но сложнее его . В настоящее время это наиболее широко используемый международный стандарт сжатия видео для видеотелефонии на телефонных линиях ISDN (цифровая сеть с интеграцией услуг).
63. Питер де Риваз; Джек Хотон (2018). "AV1 Bitstream & Decoding Process Specification" (PDF) . Alliance for Open Media . Получено 2022-01-14 .
64. Разработчики YouTube (15 сентября 2018 г.). «Плейлист запуска бета-версии AV1». YouTube . Получено 14 января 2022 г. Первые видео, получившие транскодирование AV1 YouTube.
65. Бринкманн, Мартин (13 сентября 2018 г.). «Как включить поддержку AV1 на YouTube» . Получено 14 января 2022 г.
66. Блог Netflix Technology (5 февраля 2020 г.). «Netflix Now Streaming AV1 on Android» . Получено 14 января 2022 г. .
67. Блог Netflix Technology (9 ноября 2021 г.). «Внедрение потоковой передачи AV1 на телевизоры участников Netflix» . Получено 14 января 2022 г.
68. Herre, J.; Dietz, M. (2008). "Высокоэффективное кодирование AAC MPEG-4 [Стандарты в двух словах]". Журнал обработки сигналов IEEE . 25 (3): 137–142. Bibcode : 2008ISPM...25..137H. doi : 10.1109/MSP.2008.918684.
69. Валин, Жан-Марк; Максвелл, Грегори; Терриберри, Тимоти Б.; Вос, Коэн (октябрь 2013 г.). Высококачественное кодирование музыки с малой задержкой в ​​кодеке Opus . 135-я конвенция AES. Общество звукорежиссеров . arXiv : 1602.04845 .
70. "Opus Codec". Opus (Домашняя страница). Фонд Xiph.org . Получено 31 июля 2012 г.
71. Лейден, Джон (27 октября 2015 г.). «WhatsApp разоблачен: исследованы внутренности приложения, высасывающего информацию». The Register . Получено 19 октября 2019 г.
72. Хазра, Судип; Матети, Прабхакер (13–16 сентября 2017 г.). «Проблемы криминалистики Android». В Тампи, Сабу М.; Перес, Грегорио Мартинес; Вестфалл, Карлос Беккер; Ху, Цзянькунь; Фан, Чун И.; Мармоль, Феликс Гомес (ред.). Безопасность в вычислительной технике и коммуникациях: 5-й международный симпозиум, SSCC 2017 . Спрингер. стр. 286–299 (290). дои : 10.1007/978-981-10-6898-0_24. ISBN 9789811068980.
73. Шривастава, Саурабх Ранджан; Дубе, Сачин; Шривастая, Гульшан; Шарма, Кавита (2019). «Проблемы безопасности, вызванные смартфоном — проблемы, примеры и профилактика». В Le, Dac-Nhuong; Kumar, Raghvendra; Mishra, Brojo Kishore; Chatterjee, Jyotir Moy; Khari, Manju (ред.). Кибербезопасность в параллельных и распределенных вычислениях: концепции, методы, приложения и примеры . John Wiley & Sons. стр. 187–206 (200). doi :10.1002/9781119488330.ch12. ISBN 9781119488057. S2CID  214034702.
74. "Программное обеспечение с открытым исходным кодом, используемое в PlayStation 4". Sony Interactive Entertainment Inc. Получено 11 декабря 2017 г.
75. "Dolby AC-4: Audio Delivery for Next-Generation Entertainment Services" (PDF) . Dolby Laboratories . Июнь 2015 г. Архивировано из оригинала (PDF) 30 мая 2019 г. Получено 11 ноября 2019 г.
76. Bleidt, RL; Sen, D.; Niedermeier, A.; Czelhan, B.; Füg, S.; et al. (2017). «Разработка аудиосистемы MPEG-H TV для ATSC 3.0» (PDF) . IEEE Transactions on Broadcasting . 63 (1): 202–236. doi :10.1109/TBC.2017.2661258. S2CID  30821673.
77. Шнелл, Маркус; Шмидт, Маркус; Яндер, Мануэль; Альберт, Тобиас; Гейгер, Ральф; Руоппила, Веса; Экстранд, Пер; Бернхард, Гриль (октябрь 2008 г.). MPEG-4 Enhanced Low Delay AAC — новый стандарт высококачественной связи (PDF) . 125-я конвенция AES. Fraunhofer IIS . Audio Engineering Society . Получено 20 октября 2019 г.
78. Луцки, Манфред; Шуллер, Джеральд; Гайер, Марк; Кремер, Ульрих; Вабник, Стефан (май 2004 г.). Руководство по задержке аудиокодека (PDF) . 116-я конференция AES. Fraunhofer IIS . Audio Engineering Society . Получено 24 октября 2019 г.
79. Nagireddi, Sivannarayana (2008). Обработка голосовых и факсимильных сигналов VoIP. John Wiley & Sons . стр. 69. ISBN 9780470377864.
80. «Рабочая программа МСЭ-Т». МСЭ .
81. Терриберри, Тимоти Б. Презентация кодека CELT. Событие происходит на 65-й минуте. Архивировано из оригинала 2011-08-07 . Получено 2019-10-19 ., а также «Слайды презентации кодека CELT» (PDF) .
82. "Ekiga 3.1.0 доступна". Архивировано из оригинала 2011-09-30 . Получено 2019-10-19 .
83. "☏ FreeSWITCH". SignalWire .
84. "Enhanced Voice Services (EVS) Codec" (PDF) . Fraunhofer IIS . Март 2017 . Получено 19 октября 2019 .
85. Abousleman, GP; Marcellin, MW; Hunt, BR (январь 1995), "Сжатие гиперспектральных изображений с использованием 3-D DCT и гибридного DPCM/DCT", IEEE Trans. Geosci. Remote Sens. , 33 (1): 26–34, Bibcode : 1995ITGRS..33...26A, doi : 10.1109/36.368225
86. Чан, И.; Сиу, В. (май 1997 г.), «Кодирование с 3-мерным дискретным косинусным преобразованием переменной временной длины» (PDF) , IEEE Trans. Image Process. , 6 (5): 758–763, Bibcode : 1997ITIP....6..758C, CiteSeerX 10.1.1.516.2824 , doi : 10.1109/83.568933, hdl : 10397/1928, PMID  18282969 
87. Song, J.; SXiong, Z.; Liu, X.; Liu, Y., «Алгоритм для многослойного кодирования и передачи видео», Proc. Четвертая международная конференция/выставка по высокопроизводительным вычислениям, Азиатско-Тихоокеанский регион , 2 : 700–703
88. Tai, S.-C; Gi, Y.; Lin, C.-W. (сентябрь 2000 г.), «Адаптивный 3-D дискретный косинусный преобразователь для сжатия медицинских изображений», IEEE Trans. Inf. Technol. Biomed. , 4 (3): 259–263, doi : 10.1109/4233.870036, PMID  11026596, S2CID  18016215
89. Йео, Б.; Лю, Б. (май 1995 г.), «Объемная визуализация сжатых трехмерных скалярных данных на основе DCT», IEEE Transactions on Visualization and Computer Graphics , 1 : 29–43, doi : 10.1109/2945.468390
90. Чан, С.К.; Лю, В.; Хо, КИ (2000). «Идеальная реконструкция модулированных банков фильтров с суммой коэффициентов степеней двойки». Международный симпозиум IEEE по схемам и системам 2000 г. Новые технологии для 21-го века. Труды (IEEE Cat No.00CH36353) . Том 2. стр. 73–76. doi :10.1109/ISCAS.2000.856261. hdl :10722/46174. ISBN 0-7803-5482-6. S2CID  1757438.
91. Queiroz, RL; Nguyen, TQ (1996). «Перекрывающиеся преобразования для эффективного преобразования/кодирования поддиапазонов». IEEE Trans. Signal Process . 44 (5): 497–507.
92. Малвар 1992.
93. Чан, С. К.; Луо, Л.; Хо, К. Л. (1998). «Базовые вейвлеты с компактной поддержкой биортогональных косинусно-модулированных M-каналов». IEEE Trans. Signal Process . 46 (2): 1142–1151. Bibcode : 1998ITSP...46.1142C. doi : 10.1109/78.668566. hdl : 10722/42775 .
94. Katsaggelos, Aggelos K.; Babacan, S. Derin; Chun-Jen, Tsai (2009). "Глава 15 - Итеративное восстановление изображений". The Essential Guide to Image Processing . Academic Press . С. 349–383. ISBN 9780123744579.
95. "Комариный шум". PC Magazine . Получено 19 октября 2019 г.
96. Менкман, Роза (октябрь 2011 г.). Момент сбоя (PDF) . Институт сетевых культур. ISBN 978-90-816021-6-7. Получено 19 октября 2019 г. .
97. Рафф, Томас (31 мая 2009 г.). "jpegs". Aperture . Aperture. стр. 132. ISBN 9781597110938.
98. Кольберг, Йорг (17 апреля 2009 г.). «Обзор: jpegs Томаса Раффа».
99. "Дискретное косинусное преобразование - MATLAB dct". www.mathworks.com . Получено 2019-07-11 .
100. Пеннебейкер, Уильям Б.; Митчелл, Джоан Л. (31 декабря 1992 г.). JPEG: Стандарт сжатия данных неподвижных изображений . Springer. ISBN 9780442012724.
101. Арай, Ю.; Аги, Т.; Накадзима, М. (1988). «Быстрая схема DCT-SQ для изображений». IEICE-транзакции . 71 (11): 1095–1097.
102. Шао, Сюаньчэн; Джонсон, Стивен Г. (2008). «Алгоритмы DCT/DST типа II/III с уменьшенным числом арифметических операций». Обработка сигналов . 88 (6): 1553–1564. arXiv : cs/0703150 . Bibcode : 2008SigPr..88.1553S. doi : 10.1016/j.sigpro.2008.01.004. S2CID  986733.
103. Малвар 1992
104. Мартуччи 1994
105. Чан, С. К.; Хо, К. Л. (1990). «Прямые методы вычисления дискретных синусоидальных преобразований». Труды IEE F — Радар и обработка сигналов . 137 (6): 433. doi :10.1049/ip-f-2.1990.0063.
106. Alshibami, O.; Boussakta, S. (июль 2001 г.). «Трехмерный алгоритм для 3-D DCT-III». Proc. Sixth Int. Symp. Commun., Theory Applications : 104–107.
107. Гоан Би; Ган Ли; Кай-Куанг Ма; Тан, TC (2000). «О вычислении двумерного DCT». Труды IEEE по обработке сигналов . 48 (4): 1171–1183. Bibcode : 2000ITSP...48.1171B. doi : 10.1109/78.827550.
108. Фейг, Э.; Виноград, С. (июль 1992a). «О мультипликативной сложности дискретных косинусных преобразований». Труды IEEE по теории информации . 38 (4): 1387–1391. doi :10.1109/18.144722.
109. Нуссбаумер, HJ (1981). Алгоритмы быстрого преобразования Фурье и свертки (1-е изд.). Нью-Йорк: Springer-Verlag.
110. Шао, Сюаньчэн; Джонсон, Стивен Г. (2008). «Алгоритмы DCT/DST типа II/III с уменьшенным числом арифметических операций». Обработка сигналов . 88 (6): 1553–1564. arXiv : cs/0703150 . Bibcode : 2008SigPr..88.1553S. doi : 10.1016/j.sigpro.2008.01.004. S2CID  986733.

Дальнейшее чтение

• Нарасимха, М.; Петерсон, А. (июнь 1978 г.). «О вычислении дискретного косинусного преобразования». Труды IEEE по коммуникациям . 26 (6): 934–936. doi :10.1109/TCOM.1978.1094144.
• Макхул, Дж. (февраль 1980 г.). «Быстрое косинусное преобразование в одном и двух измерениях». Труды IEEE по акустике, речи и обработке сигналов . 28 (1): 27–34. doi :10.1109/TASSP.1980.1163351.
• Sorensen, H.; Jones, D.; Heideman, M.; Burrus, C. (июнь 1987 г.). «Алгоритмы быстрого преобразования Фурье с действительными значениями». Труды IEEE по акустике, речи и обработке сигналов . 35 (6): 849–863. CiteSeerX  10.1.1.205.4523 . doi :10.1109/TASSP.1987.1165220.
• Plonka, G. ; Tasche, M. (январь 2005 г.). «Быстрые и численно устойчивые алгоритмы для дискретных косинусных преобразований». Линейная алгебра и ее приложения . 394 (1): 309–345. doi : 10.1016/j.laa.2004.07.015 .
• Duhamel, P.; Vetterli, M. (апрель 1990 г.). «Быстрые преобразования Фурье: обзор учебника и современное состояние». Обработка сигналов (Представленная рукопись). 19 (4): 259–299. Bibcode :1990SigPr..19..259D. doi :10.1016/0165-1684(90)90158-U.
• Ахмед, Н. (январь 1991 г.). «Как я придумал дискретное косинусное преобразование». Цифровая обработка сигналов . 1 (1): 4–9. Bibcode :1991DSP.....1....4A. doi :10.1016/1051-2004(91)90086-Z.
• Фейг, Э.; Виноград, С. (сентябрь 1992b). «Быстрые алгоритмы для дискретного косинусного преобразования». Труды IEEE по обработке сигналов . 40 (9): 2174–2193. Bibcode : 1992ITSP...40.2174F. doi : 10.1109/78.157218.
• Малвар, Энрике (1992), Обработка сигналов с помощью перекрывающихся преобразований , Бостон: Artech House, 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.; Johnson, SG (февраль 2005 г.). "Проектирование и реализация FFTW3" (PDF) . Труды IEEE . 93 (2): 216–231. Bibcode :2005IEEEP..93..216F. CiteSeerX  10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. S2CID  6644892.
• Boussakta, Said.; Alshibami, Hamoud O. (апрель 2004 г.). "Быстрый алгоритм для 3-D DCT-II" (PDF) . IEEE Transactions on Signal Processing . 52 (4): 992–1000. Bibcode :2004ITSP...52..992B. doi :10.1109/TSP.2004.823472. S2CID  3385296.
• Cheng, LZ; Zeng, YH (2003). "Новый быстрый алгоритм для многомерного DCT типа IV". IEEE Transactions on Signal Processing . 51 (1): 213–220. doi :10.1109/TSP.2002.806558.
• Вэнь-Сюн Чен; Смит, К.; Фралик, С. (сентябрь 1977 г.). «Быстрый вычислительный алгоритм для дискретного косинусного преобразования». Труды IEEE по коммуникациям . 25 (9): 1004–1009. doi :10.1109/TCOM.1977.1093941.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 12.4.2. Косинусное преобразование», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8, заархивировано из оригинала 2011-08-11 , извлечено 2011-08-13

Внешние ссылки

• Сайед Али Хайям: Дискретное косинусное преобразование (ДКП): теория и применение
• Реализация целочисленной аппроксимации MPEG 8x8 IDCT (ISO/IEC 23002-2)
• Маттео Фриго и Стивен Г. Джонсон : FFTW , домашняя страница FFTW. Бесплатная ( GPL ) библиотека C, которая может вычислять быстрые DCT (типы I-IV) в одном или нескольких измерениях произвольного размера.
• Такуя Оура: Пакет БПФ общего назначения, Пакет БПФ 1-мерный / 2-мерный. Бесплатные библиотеки C и FORTRAN для вычисления быстрых ДКП (типы II–III) в одном, двух или трех измерениях, размеры степени 2.
• Тим Кинцле: Быстрые алгоритмы для вычисления 8-точечного DCT и IDCT, Algorithm Alley.
• LTFAT — это бесплатный набор инструментов Matlab/Octave с интерфейсами для реализации FFTW DCT и DST типов I–IV.