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

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

История

Идея использования косинусных функций для представления сигналов восходит к работам французского математика Жана-Батиста Жозефа Фурье, который в начале XIX века показал, что произвольную периодическую функцию можно разложить в ряд синусов и косинусов. Однако дискретная форма, пригодная для цифровой обработки, была разработана значительно позже.

В 1974 году инженеры Насир Ахмед, Т. Натараджан и К. Р. Рао из Техасского университета (США) опубликовали статью «Discrete Cosine Transform», в которой впервые формально описали ДКП и его свойства. Они показали, что ДКП является дискретным аналогом преобразования Фурье для вещественных сигналов и обладает высокой степенью декорреляции данных, что критически важно для сжатия. В 1977 году Чен, Смит и Фрейкс предложили алгоритм быстрого вычисления ДКП, аналогичный быстрому преобразованию Фурье (БПФ), что сделало ДКП практичным для реальных применений.

Широкое распространение ДКП получило в конце 1980-х — начале 1990-х годов, когда Международная организация по стандартизации (ISO) и Международная электротехническая комиссия (IEC) приняли его в качестве основы для стандарта сжатия изображений JPEG (Joint Photographic Experts Group) и стандарта сжатия видео MPEG (Moving Picture Experts Group). С тех пор ДКП остаётся одним из наиболее часто используемых преобразований в цифровой обработке сигналов.

Математическое описание

Дискретное косинусное преобразование представляет собой линейное преобразование, которое отображает последовательность из N вещественных чисел x[0], x[1], ..., x[N-1] в последовательность из N коэффициентов X[0], X[1], ..., X[N-1]. Существует несколько вариантов ДКП, отличающихся граничными условиями и симметрией базисных функций. Наиболее распространённым является ДКП-II (DCT-II), используемое в JPEG и MPEG.

Формула прямого ДКП-II для последовательности x[n] (n = 0, 1, ..., N-1) имеет вид:

X[k] = c[k] Σ_{n=0}^{N-1} x[n] cos( (π k (2n + 1)) / (2N) ),

где:

• k = 0, 1, ..., N-1 — индекс коэффициента,
• c[0] = 1/√N,
• c[k] = √(2/N) для k > 0.

Обратное преобразование (ДКП-III) восстанавливает исходную последовательность:

x[n] = Σ_{k=0}^{N-1} c[k] X[k] cos( (π k (2n + 1)) / (2N) ).

Коэффициент X[0] называется постоянной составляющей (DC-коэффициент) и представляет собой среднее значение исходного сигнала, умноженное на √N. Остальные коэффициенты (X[1]...X[N-1]) называются переменными составляющими (AC-коэффициенты) и соответствуют различным частотам косинусоид.

Свойства

• Энергетическая компактность: ДКП концентрирует энергию сигнала в небольшом числе низкочастотных коэффициентов. Для типичных изображений и аудиосигналов более 90% энергии может содержаться в первых 5-10% коэффициентов.
• Декорреляция: ДКП снижает корреляцию между отсчётами сигнала, что позволяет эффективно применять последующее квантование и кодирование.
• Ортогональность: Базисные функции ДКП ортогональны, что обеспечивает обратимость преобразования без потерь (при условии использования вещественных чисел с достаточной точностью).
• Разделимость: Для двумерных сигналов (например, изображений) ДКП может быть выполнено последовательно по строкам и столбцам, что упрощает вычисления.

Классификация

Существует 8 стандартных типов дискретного косинусного преобразования (DCT-I — DCT-VIII), которые различаются граничными условиями и симметрией. На практике чаще всего используются:

• DCT-II (стандартное ДКП): применяется в сжатии изображений и видео (JPEG, MPEG, H.264, H.265).
• DCT-III (обратное ДКП): используется для восстановления сигнала из коэффициентов.
• DCT-IV: применяется в некоторых аудиокодеках (например, AAC) и в модифицированном дискретном косинусном преобразовании (MDCT).
• MDCT (Modified Discrete Cosine Transform): вариант ДКП-IV с перекрытием блоков, используется в современных аудиокодеках (MP3, AAC, Ogg Vorbis) для уменьшения артефактов на границах блоков.

Применение

Сжатие изображений (JPEG)

В стандарте JPEG (Joint Photographic Experts Group, принят в 1992 году) ДКП является основным этапом сжатия. Процесс включает:

1. Разбиение изображения на блоки размером 8×8 пикселей.
2. Преобразование цветового пространства из RGB в YCbCr (яркость и цветность).
3. Выполнение двумерного ДКП для каждого блока.
4. Квантование коэффициентов с использованием таблиц квантования, которые уменьшают точность высокочастотных компонент.
5. Кодирование полученных коэффициентов с помощью кодирования длин серий (RLE) и кодирования Хаффмана или арифметического кодирования.

ДКП обеспечивает высокую степень сжатия (до 10-20 раз) с минимальными визуальными потерями. При сильном сжатии проявляются характерные артефакты — «блочность» (видимые границы между блоками 8×8).

Сжатие видео (MPEG, H.264, H.265)

В стандартах сжатия видео (MPEG-1, MPEG-2, MPEG-4, H.264/AVC, H.265/HEVC) ДКП применяется к остаточным сигналам после компенсации движения. Размер блоков может варьироваться от 4×4 до 32×32 (в H.265). ДКП позволяет эффективно удалять пространственную избыточность в видеокадрах.

Сжатие аудио (MP3, AAC, Ogg Vorbis)

В аудиокодеках используется модифицированное дискретное косинусное преобразование (MDCT) с перекрытием блоков. MDCT применяется к окнам сигнала длительностью 20-50 мс, что позволяет снизить артефакты на границах блоков. После MDCT выполняется квантование и кодирование с использованием психоакустической модели, которая учитывает особенности восприятия звука человеком.

Обработка сигналов и спектральный анализ

ДКП используется в задачах фильтрации, сглаживания, интерполяции и спектрального анализа, где требуется компактное представление сигнала. Например, в системах распознавания речи ДКП применяется для извлечения мел-частотных кепстральных коэффициентов (MFCC).

Криптография и стеганография

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

Примеры

Одномерное ДКП для последовательности

Пусть дана последовательность из 4 чисел: x = [1, 2, 3, 4]. Вычислим коэффициенты ДКП-II (N=4):

• c[0] = 1/√4 = 0.5
• c[k] = √(2/4) = √0.5 ≈ 0.7071 для k > 0

X[0] = 0.5 (1 + 2 + 3 + 4) = 0.5 10 = 5.0 X[1] = 0.7071 [1cos(π/8) + 2cos(3π/8) + 3cos(5π/8) + 4cos(7π/8)] ≈ 0.7071 (0.9239 + 0.3827 - 0.3827 - 0.9239) = 0 X[2] = 0.7071 [1cos(π/4) + 2cos(3π/4) + 3cos(5π/4) + 4cos(7π/4)] = 0.7071 (0.7071 - 0.7071 - 0.7071 + 0.7071) = 0 X[3] = 0.7071 [1cos(3π/8) + 2cos(9π/8) + 3cos(15π/8) + 4cos(21π/8)] ≈ 0.7071 (0.3827 - 0.9239 - 0.9239 + 0.3827) = 0.7071 * (-1.0824) ≈ -0.765

Результат: X = [5.0, 0, 0, -0.765]. Большая часть энергии сосредоточена в DC-коэффициенте (5.0), что демонстрирует энергетическую компактность.

Двумерное ДКП для блока изображения

Для блока 8×8 пикселей (например, в JPEG) двумерное ДКП вычисляется как:

X[k1][k2] = c[k1] c[k2] Σ_{n1=0}^{7} Σ_{n2=0}^{7} x[n1][n2] cos( (π k1 (2n1 + 1)) / 16 ) cos( (π k2 (2n2 + 1)) / 16 )

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

Интересные факты

• ДКП является вещественным аналогом дискретного преобразования Фурье (ДПФ). Если ДПФ использует комплексные экспоненты (синусы и косинусы), то ДКП — только косинусы, что даёт вдвое меньше коэффициентов для вещественного сигнала.
• В стандарте JPEG используется ДКП-II, а обратное преобразование — ДКП-III. В некоторых реализациях для ускорения вычислений применяются алгоритмы быстрого ДКП, основанные на БПФ.
• ДКП лежит в основе формата изображений JPEG, который является одним из самых распространённых в мире. По оценкам, ежедневно создаётся миллиарды JPEG-файлов.
• В 2019 году группа исследователей из Массачусетского технологического института (MIT) предложила альтернативу ДКП — нейросетевое преобразование, которое может адаптироваться к конкретным данным и обеспечивать более высокую степень сжатия. Однако ДКП остаётся стандартом де-факто благодаря своей простоте и эффективности.

Критика и ограничения

• Блочные артефакты: При сильном сжатии изображений (JPEG) на границах блоков 8×8 возникают видимые ступеньки и искажения, особенно заметные на однородных участках (например, небо, стена). Для борьбы с этим используются постфильтры и методы сглаживания.
• Неоптимальность для некоторых типов данных: ДКП хорошо работает для естественных изображений и аудиосигналов, но может быть менее эффективным для искусственных (текст, графика) или сильно зашумлённых данных.
• Зависимость от размера блока: Выбор размера блока (8×8, 16×16, 32×32) влияет на качество сжатия и вычислительную сложность. Слишком маленькие блоки увеличивают количество артефактов, слишком большие — снижают локальную адаптивность.
• Альтернативы: В современных стандартах сжатия (например, JPEG XL, AVIF) всё чаще используются вейвлет-преобразования или нейросетевые методы, которые могут превосходить ДКП по качеству при одинаковой степени сжатия.

Источники

• Ahmed, N., Natarajan, T., & Rao, K. R. (1974). Discrete Cosine Transform. IEEE Transactions on Computers, C-23(1), 90–93.
• Rao, K. R., & Yip, P. (1990). Discrete Cosine Transform: Algorithms, Advantages, Applications. Academic Press.
• Wallace, G. K. (1992). The JPEG Still Picture Compression Standard. IEEE Transactions on Consumer Electronics, 38(1), xviii–xxxiv.
• ISO/IEC 10918-1:1994 — Information technology — Digital compression and coding of continuous-tone still images: Requirements and guidelines.
• ITU-T Recommendation H.264 (2021) — Advanced video coding for generic audiovisual services.
• Britanak, V., Yip, P., & Rao, K. R. (2007). Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations. Academic Press.