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

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

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

Существует восемь стандартных вариантов DCT, из которых четыре являются распространенными.Наиболее распространенным вариантом дискретного косинусного преобразования является ДКП типа II, который часто называют просто ДКП . Это был первоначальный DCT, впервые предложенный Ахмедом. Его обратное, ДКП типа III, соответственно, часто называют просто обратным ДКП или IDCT . Двумя связанными преобразованиями являются дискретное синусоидальное преобразование (ДСТ), которое эквивалентно ДПФ действительных и нечетных функций , и модифицированное дискретное косинусное преобразование (МДКП), основанное на ДКП перекрывающихся данных. Многомерные DCT (MD DCT) разработаны для распространения концепции DCT на многомерные сигналы. Для снижения вычислительной сложности реализации DCT было разработано множество быстрых алгоритмов. Одним из них является целочисленное ДКП (IntDCT), целочисленное , приближение стандартного ДКП используется в нескольких ISO/IEC и ITU-T . международных стандартах

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

История

DCT был впервые разработан Насиром Ахмедом , Т. Натараджаном и К. Р. Рао во время работы в Университете штата Канзас . Концепция была предложена Национальному научному фонду в 1972 году. Изначально DCT предназначался для сжатия изображений . Ахмед разработал практический алгоритм DCT вместе со своими аспирантами Т. Раджем Натараджаном, Уиллсом Дитрихом и Джереми Фрайсом, а также своим другом доктором К. Р. Рао в Техасском университете в Арлингтоне в 1973 году. Они представили свои результаты в статье в январе 1974 года под названием «Дискретное косинусное преобразование» . В нем описывалось то, что сейчас называется DCT типа II (DCT-II), а также обратное ДКП типа III (IDCT).

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

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

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

Вариант DCT, модифицированное дискретное косинусное преобразование (MDCT), был разработан Джоном П. Принсеном, А.В. Джонсоном и Аланом Б. Брэдли в Университете Суррея в 1987 году. после более ранней работы Принсена и Брэдли в 1986 году. MDCT используется в большинстве современных форматов сжатия звука , таких как Dolby Digital (AC-3), MP3 (использующий гибридный алгоритм DCT- FFT ), Расширенное кодирование звука (AAC), и Ворбис ( Огг ).

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

Приложения

DCT — наиболее широко используемый метод преобразования при обработке сигналов . и, безусловно, наиболее широко используемое линейное преобразование при сжатии данных . Несжатые цифровые носители , а также сжатие без потерь предъявляют высокие требования к памяти и пропускной способности , что значительно снижается за счет метода сжатия с потерями DCT . возможность достижения степени сжатия данных от 8:1 до 14:1 для качества, близкого к студийному, до 100:1 для контента приемлемого качества. Стандарты сжатия DCT используются в цифровых медиа-технологиях, таких как цифровые изображения , цифровые фотографии , цифровое видео , потоковое мультимедиа , цифровое телевидение , потоковое телевидение , видео по запросу (VOD), цифровое кино , видео высокой четкости (HD-видео) и телевидение высокой четкости (HDTV).

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

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

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

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

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

• Обработка аудиосигнала — кодирование звука , сжатие аудиоданных (с потерями и без потерь), объемный звук , акустического эха и подавление обратной связи , распознавание фонем , подавление наложения временных интервалов (TDAC)
  • Цифровое аудио
  • Цифровое радио — цифровое аудиовещание (DAB+), HD-радио
  • Обработка речи — кодирование речи распознавание речи , обнаружение голосовой активности (VAD)
  • Цифровая телефония — передача голоса по IP (VoIP), мобильная телефония , видеотелефония , телеконференции , видеоконференции
• Биометрия — по отпечаткам пальцев ориентация , системы распознавания лиц , биометрические водяные знаки , биометрические водяные знаки на основе отпечатков пальцев, отпечатков ладоней . идентификация/распознавание
  • Обнаружение лиц — распознавание лиц
• Компьютеры и Интернет — Всемирная паутина , социальные сети , Интернет-видео
  • пропускной способности сети Снижение использования
• Бытовая электроника — мультимедийные системы, мультимедийные телекоммуникационные устройства, потребительские устройства
• Криптография — шифрование , стеганография , авторских прав. защита
• Сжатие данных — кодирование с преобразованием , сжатие с потерями , сжатие без потерь.
  • кодирования Операции — квантование , перцепционное взвешивание, энтропийное кодирование , кодирование с переменным битрейтом.
• Цифровые медиа — цифровая дистрибуция
  • Потоковое мультимедиа — потоковое аудио , потоковое видео , потоковое телевидение , видео по запросу (VOD)
• Обнаружение подделок
• Геофизическая переходная электромагнетика (переходная ЭМ)
• Изображения — художника , идентификация измерение фокуса и размытости , извлечение признаков
  • Форматирование цвета — форматирование яркости и различий в цвете, цветовые форматы (например, YUV444 и YUV411 ), операции декодирования , такие как обратная операция между форматами цвета дисплея ( YIQ , YUV , RGB ).
  • Цифровая обработка изображений — цифровые изображения , цифровые фотоаппараты , цифровая фотография , визуализация с высоким динамическим диапазоном (HDR-изображение)
  • Сжатие изображения — форматы файлов изображений , многоракурсное сжатие изображения, изображения прогрессивная передача
  • Обработка изображений — цифровая обработка изображений , анализ изображения , поиск изображения на основе содержимого , обнаружение углов , направленное блочное представление изображения , обнаружение краев , улучшение изображения , объединение изображений , сегментация изображения , интерполяция , шума изображения оценка уровня , зеркальное отображение, вращение, профиль едва заметного искажения (JND) , пространственно-временные маскирующие эффекты, фовеативная визуализация
  • Оценка качества изображения — показатель ухудшения качества на основе DCT (DCT QM).
  • Реконструкция изображения направленных текстур — автопроверка , восстановление изображения , закрашивание , визуальное восстановление.
• Медицинская техника
  • Электрокардиография (ЭКГ) — векторкардиография (ВКГ)
  • Медицинская визуализация — сжатие медицинских изображений, объединение изображений, водяные знаки, опухолей головного мозга . сжатия классификация
• Распознавание образов
• Извлечение области интереса (ROI)
• Обработка сигналов — цифровая обработка сигналов , цифровые сигнальные процессоры (DSP), программное обеспечение DSP , мультиплексирование , сигнализация , сигналы управления, аналого-цифровое преобразование (АЦП), компрессионная выборка пирамиды DCT , маскирование ошибок , понижающая дискретизация , повышающая дискретизация , оценка отношения сигнал/шум (SNR), трансмукс , фильтр Винера
  • Комплексный анализ функций кепстра
  • DCT- фильтрация
• Наблюдение
• автомобильных событий регистрации данных Камера
• Видео
  • Цифровое кино — цифровая кинематография , цифровые кинокамеры , видеомонтаж , монтаж фильмов , Dolby Digital Звук
  • Цифровое телевидение (ЦТВ) — цифровое телевещание , телевидение стандартной четкости (SDTV), телевидение высокой четкости (HDTV), HDTV Чипы кодера/декодера , ультра HDTV (UHDTV)
  • Цифровое видео — цифровой универсальный диск (DVD), видео высокой четкости (HD)
  • Видеокодирование — сжатие видео , стандарты видеокодирования , оценка движения , компенсация движения , межкадровое предсказание, векторы движения , Кодирование 3D-видео , модель вероятности обнаружения локальных искажений (LDDP), обнаружение движущихся объектов , многоракурсное видеокодирование (MVC)
  • Обработка видео — анализ движения , анализ движения 3D-DCT, анализ видеоконтента , извлечение данных , просмотр видео , профессиональная видеопродукция
• Водяные знаки — цифровые водяные знаки , водяные знаки изображений , водяные знаки видео, водяные знаки 3D-видео , обратимое сокрытие данных , обнаружение водяных знаков.
• Беспроводная технология
  • Мобильные устройства — мобильные телефоны , смартфоны , видеофоны
  • Радиочастотная (РЧ) технология — радиочастотная техника , апертурные решетки , формирование луча , цифровые арифметические схемы , направленное зондирование , космическая съемка
• Беспроводная сенсорная сеть (WSN) — беспроводные акустические сенсорные сети.

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

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

Целочисленное ДКП, целочисленное приближение ДКП, используется в расширенном кодировании видео (AVC), представленный в 2003 году, и высокоэффективное кодирование видео (HEVC), представлено в 2013 году. Целочисленное DCT также используется в формате высокоэффективного изображения (HEIF), который использует подмножество формата кодирования видео HEVC для кодирования неподвижных изображений. AVC использует блоки 4 x 4 и 8 x 8. HEVC и HEIF используют блоки разных размеров от 4 x 4 до 32 x 32 пикселей . По состоянию на 2019 год , AVC на сегодняшний день является наиболее часто используемым форматом для записи, сжатия и распространения видеоконтента, его используют 91% разработчиков видео, за ним следует HEVC, который используют 43% разработчиков.

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

Стандарт сжатия изображений	Год	Общие приложения
JPEG	1992	Наиболее широко используемый стандарт сжатия изображений. и формат цифрового изображения .
JPEG-XR	2009	Спецификация документа Open XML
ВебП	2010	Графический формат, поддерживающий сжатие цифровых изображений с потерями. Разработано Google .
Высокоэффективный формат изображения (HEIF)	2013	Формат файла изображения , основанный на сжатии HEVC. Он улучшает сжатие по сравнению с JPEG, и поддерживает анимацию с гораздо более эффективным сжатием, чем анимированный формат GIF .
ВВП	2014	На основе сжатия HEVC.
JPEG XL	2020	Бесплатный формат файлов растровой графики, поддерживающий сжатие как с потерями, так и без потерь.

Видео форматы

Стандарт кодирования видео	Год	Общие приложения
H.261	1988	Первый из семейства стандартов кодирования видео . Используется в основном в старых продуктах для видеоконференций и видеотелефонов .
Движущийся JPEG (MJPEG)	1992	QuickTime , монтаж видео , нелинейный монтаж , цифровые камеры
MPEG-1 Видео	1993	цифрового видео Распространение на компакт-диске или Интернет-видео.
Видео MPEG-2 ( H.262 )	1995	Хранение и обработка цифровых изображений в приложениях вещания, цифровом телевидении , HDTV , кабельном, спутниковом, высокоскоростном Интернете , распространении DVD- видео.
ДВ	1995	Видеокамеры , цифровые кассеты
H.263 ( MPEG-4, часть 2 )	1996	Видеотелефония по коммутируемой телефонной сети общего пользования (PSTN), H.320 , цифровая сеть с интеграцией услуг (ISDN)
Расширенное кодирование видео (AVC, H.264 , MPEG-4 )	2003	Популярный HD-видео формат записи, сжатия и распространения , интернет-видео , YouTube , диски Blu-ray , HDTV трансляции , веб-браузеры , потоковое телевидение , мобильные устройства , потребительские устройства, Netflix , видеотелефония , FaceTime
Теория	2004	Интернет-видео, веб-браузеры
ВК-1	2006	Windows Media, диски Blu-ray
Apple ProRes	2007	Профессиональная видеосъемка.
ВП9	2010	Видеокодек, разработанный Google , используемый в формате контейнера WebM с HTML5 .
Высокоэффективное кодирование видео (HEVC, H.265 )	2013	Преемник стандарта H.264 , имеющий существенно улучшенные возможности сжатия.
Daala	2013	Формат исследовательского видео от Xiph.org
АВ1	2018	Формат с открытым исходным кодом, основанный на VP10 ( , внутреннем преемнике VP9) Daala и Thor ; используется поставщиками контента, такими как YouTube и Нетфликс .

Аудиостандарты MDCT

Дополнительная информация: Модифицированное дискретное косинусное преобразование.

Общий звук

Стандарт сжатия звука	Год	Общие приложения
Долби Цифровой (AC-3)	1991	Кино , цифровое кино , DVD , Blu-ray , потоковое мультимедиа , видеоигры
Акустическое кодирование с адаптивным преобразованием (ATRAC)	1992	МиниДиск
MP3	1993	цифрового аудио Распространение , MP3-плееры , портативные медиаплееры , потоковое мультимедиа
Перцепционный аудиокодер (PAC)	1996	Служба цифрового аудиорадио (DARS)
Расширенное кодирование звука (аудио AAC/ MP4 )	1997	цифрового звука Распространение , портативные медиаплееры , потоковое мультимедиа , игровые консоли , мобильные устройства , iOS , iTunes , Android , BlackBerry
Высокоэффективное усовершенствованное кодирование звука (AAC+)	1997	Цифровое радио , цифровое аудиовещание (DAB+), Digital Radio Mondiale (DRM)
Кодек Кука	1998	RealAudio
Windows Media Аудио (WMA)	1999	Windows Медиа
Ворбис	2000	цифрового звука Распространение , радиостанции , потоковое мультимедиа , видеоигры , Spotify , Wikipedia
Кодирование высокой четкости (HDC)	2002	Цифровое радио, HD-радио
Адаптация динамического разрешения (DRA)	2008	Китайский национальный аудиостандарт, Китайское мультимедийное мобильное вещание , DVB-H
Опус	2012	VoIP, мобильная связь, WhatsApp , PlayStation 4
Долби AC-4	2015	ATSC 3.0 , телевидение сверхвысокой четкости (UHD TV)
MPEG-H 3D Audio

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

кодирования речи Стандарт	Год	Общие приложения
ААС-ЛД (LD-MDCT)	1999	Мобильная телефония , передача голоса по IP (VoIP), iOS , FaceTime
Сирена	1999	VoIP , широкополосное аудио , G.722.1
G.722.1	1999	VoIP, широкополосное аудио, G.722
G.729.1	2006	G.729 , VoIP, широкополосное аудио, мобильная телефония
ЕВРК-ВБ	2007	Широкополосный звук
Г.718	2008	VoIP, широкополосное аудио, мобильная телефония
Г.719	2008	Телеконференции , видеоконференции , голосовая почта
КЕЛЬТ	2011	VoIP, мобильная телефония
Расширенные голосовые услуги (EVS)	2014	Мобильная телефония, VoIP, широкополосное аудио

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

См. также: ЗПЭГ

Многомерные DCT (MD DCT) имеют несколько применений, в основном 3-D DCT, такие как 3-D DCT-II, который имеет несколько новых приложений, таких как системы кодирования гиперспектральных изображений, 3-D DCT-кодирование переменной временной длины, кодирования видео , алгоритмы адаптивное кодирование видео и 3-D сжатие. В связи с усовершенствованием аппаратного и программного обеспечения и внедрением нескольких быстрых алгоритмов необходимость использования MD DCT быстро возрастает. DCT-IV приобрел популярность благодаря своим приложениям для быстрого внедрения реальных банков многофазной фильтрации. перекрывающееся ортогональное преобразование и косинус-модулированные вейвлет-базы.

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

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

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

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

Дополнительная информация: Артефакт сжатия.

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

Блоки DCT часто используются в глитч-арте . Художница Роза Менкман использует артефакты сжатия на основе DCT в своих глитч-артах. особенно блоки DCT, присутствующие в большинстве цифровых медиаформатов , таких как цифровые изображения JPEG и MP3 цифровой звук . Другой пример — Jpegs немецкого фотографа Томаса Раффа , который намеренно использует артефакты JPEG в качестве основы стиля изображения.

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

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

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

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

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

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

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

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

Формальное определение

Формально дискретное косинусное преобразование представляет собой линейную обратимую функцию. $f:\mathbb {R} ^{N}\to \mathbb {R} ^{N}$ (где $\mathbb {R}$ обозначает набор действительных чисел ) или, что эквивалентно, обратимую N × N. матрицу размера квадратную Существует несколько вариантов DCT со слегка измененными определениями. N действительных чисел $~x_{0},\ \ldots \ x_{N-1}~$ преобразуются в N действительных чисел $X_{0},\,\ldots ,\,X_{N-1}$ по одной из формул:

ДКП-I

$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\,}}\,n\,k\,\right]\qquad {\text{ for }}~k=0,\ \ldots \ N-1~.$

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

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

Однако обратите внимание, что DCT-I не определен для $N$ менее 2, тогда как все остальные типы ДКП определены для любого положительного $N.$

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

ДКТ-II

$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».

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

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

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

ДКП-III

$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»).

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

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

ДКП-IV

$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).

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

ДКП V-VIII

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

Другими словами, ДКП типов I–IV эквивалентны вещественно-четному ДПФ четного порядка (независимо от того, является ли $N$ четно или нечетно), поскольку соответствующее ДПФ имеет длину $2(N-1)$ (для DCT-I) или $4N$ (для DCT-II и III) или $8N$ (для DCT-IV). Четыре дополнительных типа дискретного косинусного преобразования по существу соответствуют вещественно-четным ДПФ логически нечетного порядка, которые имеют коэффициенты $N\pm {1}/{2}$ в знаменателях косинусных аргументов.

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

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

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

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

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

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

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

МД ДКТ-II

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

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

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

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

$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 , и ее можно вычислить по формуле:

$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.$

Технически вычисление двух-, трех- (или многомерного) ДКП с помощью последовательностей одномерных ДКП вдоль каждого измерения известно как алгоритм строки-столбца . Однако, как и в случае с многомерными алгоритмами БПФ , существуют другие методы вычисления того же самого, выполняя вычисления в другом порядке (т.е. чередование/комбинирование алгоритмов для разных измерений). В связи с быстрым ростом приложений, основанных на 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 входные данные необходимо сформулировать и переупорядочить следующим образом. размер преобразования N × N × N Предполагается, что равен 2.

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

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

где $0\leq n_{1},n_{2},n_{3}\leq {\frac {N}{2}}-1$

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

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

$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})$

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

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

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

$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))$

где

${\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)$

$+(-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)$

$+(-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)$

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

$+(-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 требует $~[\log _{2}N]~$ этапы, и каждый этап включает в себя $~{\tfrac {1}{8}}\ N^{3}~$ бабочки. Весь 3-D DCT требует $~\left[{\tfrac {1}{8}}\ N^{3}\log _{2}N\right]~$ бабочки, подлежащие вычислению. Для каждой бабочки требуется семь действительных умножений (включая тривиальные умножения) и 24 действительных сложения (включая тривиальные сложения). Следовательно, общее количество действительных умножений, необходимых для этого этапа, равно $~\left[{\tfrac {7}{8}}\ N^{3}\ \log _{2}N\right]~,$ и общее количество реальных сложений, т.е. включая пост-сложения (рекурсивные сложения), которые могут быть рассчитаны непосредственно после этапа «бабочка» или после этапа реверса битов, определяются выражением $~\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, определяется выражением $~\left[{\frac {3}{2}}N^{3}\log _{2}N\right]~$ и $~\left[{\frac {9}{2}}N^{3}\log _{2}N-3N^{3}+3N^{2}\right]~,$ соответственно. Из таблицы 1 видно, что общее количество

ТАБЛИЦА 1Сравнение алгоритмов VR DIF и RCF для расчета 3D-DCT-II

Преобразовать размер	3D VR Mults	RCF мульты	3D VR добавляет	RCF добавляет
8 × 8 × 8	2.625	4.5	10.875	10.875
16 × 16 × 16	3.5	6	15.188	15.188
32 × 32 × 32	4.375	7.5	19.594	19.594
64 × 64 × 64	5.25	9	24.047	24.047

умножений, связанных с алгоритмом 3-D DCT VR, меньше, чем с использованием подхода RCF, более чем на 40%. Кроме того, подход RCF включает в себя транспонирование матрицы и большее количество индексации и обмена данными, чем новый алгоритм VR. Это делает алгоритм 3-D DCT VR более эффективным и лучше подходящим для 3-D приложений, в которых используется 3-D DCT-II, таких как сжатие видео и другие приложения обработки трехмерных изображений.

Основным соображением при выборе быстрого алгоритма является избежание вычислительных и структурных сложностей. По мере развития технологий компьютеров и DSP время выполнения арифметических операций (умножения и сложения) становится очень быстрым, и наиболее важным фактором становится регулярная вычислительная структура. Следовательно, хотя предложенный выше алгоритм 3D VR не достигает теоретической нижней границы количества умножений, он имеет более простую вычислительную структуру по сравнению с другими алгоритмами 3-D DCT. Его можно реализовать на месте с использованием одной бабочки, и он обладает свойствами алгоритма БПФ Кули – Тьюки в 3D. Следовательно, 3-D VR представляет собой хороший выбор для сокращения арифметических операций при расчете 3-D DCT-II, сохраняя при этом простую структуру, которая характеризует алгоритмы БПФ Кули-Тьюки типа «бабочка» .

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

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

МД-ДКП-IV

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

$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)~,$

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

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

Вычисление

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

В принципе, наиболее эффективными алгоритмами обычно являются те, которые специализируются непосредственно на ДКП, а не на использовании обычного БПФ плюс $~{\mathcal {O}}(N)~$ дополнительные операции (исключение см. ниже). Однако даже «специализированные» алгоритмы ДКП (включая все те, которые достигают наименьшего известного арифметического счета, по крайней мере, для размеров степени двойки ) обычно тесно связаны с алгоритмами БПФ, поскольку ДКП по сути представляют собой ДПФ вещественно-четных данных. можно разработать быстрый алгоритм ДКП, приняв БПФ и исключив избыточные операции из-за этой симметрии. Это можно сделать даже автоматически ( Frigo & Johnson 2005 ). Наиболее распространены алгоритмы, основанные на алгоритме БПФ Кули-Тьюки , но применим и любой другой алгоритм БПФ. Например, алгоритм БПФ Винограда приводит к алгоритмам минимального умножения для ДПФ, хотя обычно за счет большего количества сложений, и аналогичный алгоритм был предложен ( Фейг и Виноград 1992а ) для ДКП. Поскольку алгоритмы ДПФ, ДКП и подобных преобразований очень тесно связаны, любое улучшение алгоритмов одного преобразования теоретически приведет к немедленным улучшениям и для других преобразований ( Дюамель и Веттерли 1990 ).

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

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

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

Пример IDCT

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

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

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

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

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

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

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

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