TTA аудиокодек без потерь - Теория компрессии

Алгоритм работы беспотерьного аудио компрессора True Audio (TTA). Основные принципы компрессии аудио данных без потерь.

Общеизвестно, что нет алгоритма, способного сжать без потерь входные данные любого типа. Высокая степень компрессии аудио данных может быть достигнута только с помощью алгоритма, учитывающего их характерные особенности. TTA аудио компрессор предназначен для беспотерьной компрессии мультиканальных 8-,16- и 24-битных аудио данных, предварительно сохраненных в виде файлов, в популярном формате WAV.

Сжатие данных без потерь - не является новой технологией. Этот принцип используется известными утилитами сжатия типа PkZip, Compress или Gzip для компрессии текста и двоичных файлов. Это сжатие без потерь, потому что файлы после декомпрессии остаются идентичны оригиналам. К сожалению, указанные выше программы, обычно использующие варианты алгоритмов Лемпела-Зива, не показывают хороших результатов в сжатии мультимедиа данных. В то время как большинство текстовых файлов может быть сжато с коэффициентами большее чем 2:1, размер мультимедиа файлов практически не меняется.

Утилиты сжатия, основанные на алгоритме Лемпела-Зива заменяют группу символов указателем на тот фрагмент текста, где они встречаются ранее. На примере мультимедиа файлов символам соответствуют выборки сигнала. К сожалению, последовательности повторений тех же самых выборок сигнала очень редки, так что коэффициент сжатия получается очень низким. Кроме того, эти утилиты сжатия не используют важную особенность мультимедиа файлов - сильную зависимость между соседними выборками данных и между соседними каналами в случае многоканальных данных. Именно по этому все современные алгоритмы сжатия мультимедиа информации включают стадию декорреляции данных, в целях снижения этой статистической зависимости. В современных компрессорах обычно присутствует как минимум две стадии декорреляции: межканальная декорреляция и прогнозирующее моделирование.

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

Обычно, современные многоканальные компрессоры мультимедиа данных без потерь строятся по общей схеме, включающей в себя четыре основных этапа:

Разбиение сигнала на блоки;
Межканальная декорреляция;
Моделирование сигнала (прогнозирование);
Кодирование остатка.

Архитектура беспотерьного компрессора TTA включают все описанные выше стадии. Разбитые на блоки данные подвергаются межканальной декорреляции и передаются далее на стадию прогнозирования. На этой стадии моделирование входного сигнала осуществляется с помощью 2-х ступенчатого адаптивного фильтра. На кодировщик энтропии передается разница между оригинальным сигналом и спрогнозированным. Остаточный сигнал сжимается с использованием кодов Райса. Рассмотрим архитектуру TTA аудио компрессора подробнее.

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

Поступающие на вход TTA компрессора мультиканальные данные подвергаются межканальной декорреляции. На примере двухканальных данных – два исходных канала преобразуются к среднему и разностному по формулам: средний = (первый + второй)/2, разностный = первый - второй. В целях исключения потери данных описанная формула приводится к виду: разностный = первый – второй, средний = первый – разностный/2. Для многоканальных данных с хорошей корреляцией соседних каналов это обычно приводит к значительному увеличению степени сжатия.

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

Аппроксимация сигнала с помощью множества постоянных предикторов;
Моделирование сигнала методом линейного предсказания (LPC);
Моделирование сигнала с помощью адаптивных фильтров.

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

В этом методе используется IIR (Infinite Impulse Response model) фильтры, параметры которых изменяются адаптивно в процессе работы. Базовым элементом системы является p-мерный нерекурсивный фильтр, в общем случае описываемый следующими выражениями:

x'[n] = \sum_{k=1}^p v[n,k] \cdot x[n-r-k]

(1)

где x'[n] - предсказанное значение новой выборки x[n]; v[n,k] - очередное значение весового коэффициента фильтра; r - задержка сигнала. Весовые коэффициенты фильтра определяются по формуле:

v[n + 1,k] = v[n,k] + m \cdot sign[e[n]] \cdot x[n-r-k]

(2)

где m - коэффициент, определяющий скорость адаптации; e[n] - очередной отсчет выходного сигнала (сигнала ошибки); sgn - знак сигнала [.];

Минимизация остатка $e[n] = x[n] - x'[n]$ может быть реализована с помощью различных алгоритмов, таких как: алгоритм минимума среднего квадрата ошибки Уидроу-Хоффа (LMS), основанного на статистическом подходе или же, рекурсивным алгоритмом наименьших квадратов (RLS). Второй, хоть и имеет более высокую скорость сходимости, но отнимает значительно больше ресурсов процессора. Поэтому, в компрессоре TTA был использован LMS алгоритм. Сходимость алгоритма TTA осуществляется по методу наискорейшего спуска, причем, для упрощения вычислений используется стохастическая аппроксимация градиента по Уидроу-Хопфу. Для ускорения сходимости в качестве критерия оптимальности используется минимум модуля ошибки фильтра. Независимо от начального значения матрицы коэффициентов фильтра v, которое может быть произвольным, алгоритм сходится в среднем и остается устойчивым до тех пор, пока параметр m удовлетворяет условию 1/λ_max > m > 0, где λ_max - максимум собственного значения автокорреляционной матрицы входных сигналов. Выходной остаточный сигнал фильтра, определяется как разность между реальным сигналом и его предсказанным значением, которое вычисляется как свертка реального сигнала с весовыми коэффициентами трансверсального фильтра в соответствии с (1). Импульсная характеристика этого фильтра (или вектор весовых коэффициентов размерностью p) обновляется на каждом дискретном моменте времени n в соответствии с (2).

Алгоритм работы беспотерьного TTA компрессора незначительно отличается от описанного выше. Входной сигнал проходит 2-х ступенчатую фильтрацию. На первой стадии в качестве фильтра выступает предиктор нулевого порядка. Т.е. сигнал ошибки определяется следующей формулой:

e[n] = x[n] - kx[n-1]

, где k достаточно близко к 1.

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

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

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

Литература

А.В.Джурик, П.Г.Жилин. Сибирский Солнечный Радиотелескоп: Формат PCA компрессора данных ССРТ.. Вычислительные методы и программирование, (Научно-исследовательский вычислительный центр МГУ им. М. В. Ломоносова), 4 (2003), 278-282.
M.Hans, R.Schafer. Lossless Audio Coding. Technical Report. CSIP TR-97-07. Atlanta, 1997.
T.Robinson. SHORTEN: Simple lossless and near-lossless waveform compression. Technical report, Cambridge University Engineerig Department. Cambridge, December 1994.
P.C.Craven, M.J.Law, and J.R.Stuart. Lossless Compression using IIR Prediction Filters. 102nd AES Convention. Munich, March 1997.
R.F.Rice, Some practical universal noiseless coding techniques. Technical Report. JPL-79-22, Jet Propulsion Laboratory. Pasadena, 1979.