Теория скорости и искажения является основным разделом теории информации, который обеспечивает теоретические основы для сжатия данных с потерями ; он решает проблему определения минимального количества битов на символ, измеряемого скоростью R , которое должно быть передано по каналу, так что источник (входной сигнал) может быть приблизительно восстановлен на приемнике (выходной сигнал) без превышения ожидаемое искажение D .
Вступление
Теория «скорость – искажение» дает аналитическое выражение того, насколько компрессия может быть достигнута с использованием методов сжатия с потерями. Многие из существующих методов сжатия звука, речи, изображения и видео имеют процедуры преобразования, квантования и распределения битовой скорости, которые основываются на общей форме функций скорость-искажение.
Теория искажения скорости была создана Клодом Шенноном в его фундаментальной работе по теории информации.
В теории искажений скорость обычно понимается как количество битов на выборку данных, которые должны быть сохранены или переданы. Понятие искажения является предметом постоянных дискуссий. [1] В самом простом случае (который фактически используется в большинстве случаев) искажение определяется как ожидаемое значение квадрата разницы между входным и выходным сигналами (т. Е. Среднеквадратичная ошибка ). Однако, поскольку мы знаем, что большинство методов сжатия с потерями работают с данными, которые будут восприниматься потребителями-людьми (прослушивание музыки , просмотр изображений и видео), мера искажения предпочтительно должна быть смоделирована на основе человеческого восприятия и, возможно, эстетики : во многом аналогично использованию вероятности при сжатии без потерь меры искажения можно в конечном итоге отождествить с функциями потерь, используемыми в байесовской теории оценки и принятия решений . При сжатии звука модели восприятия (и, следовательно, меры перцептивного искажения) относительно хорошо разработаны и обычно используются в таких методах сжатия, как MP3 или Vorbis , но их часто нелегко включить в теорию искажения скорости. При сжатии изображений и видео модели человеческого восприятия менее развиты, и включение в них в основном ограничивается матрицами взвешивания ( квантования , нормализации ) JPEG и MPEG .
Функции искажения
Функции искажения измеряют стоимость представления символа приближенным символом . Типичными функциями искажения являются искажение Хэмминга и искажение квадратичной ошибки.
Искажение Хэмминга
Квадратная ошибка искажения
Скоростно-искажающие функции
Функции, связывающие скорость и искажение, находятся как решение следующей задачи минимизации:
Здесь , иногда называемый тестовым каналом, представляет собой функцию условной плотности вероятности (PDF) выходного канала связи (сжатый сигнал) для данного входа (исходный сигнал) , а также это взаимная информация между а также определяется как
где а также - энтропия выходного сигнала Y и условная энтропия выходного сигнала для входного сигнала, соответственно:
Проблема также может быть сформулирована как функция искажения-скорости, где мы находим нижнюю границу достижимых искажений для данного ограничения скорости. Соответствующее выражение:
Эти две формулировки приводят к функциям, обратным друг другу.
Взаимная информация может пониматься как мера `` априорной '' неопределенности получателя в отношении сигнала отправителя ( H ( Y )), уменьшенной за счет неопределенности, которая остается после получения информации о сигнале отправителя (). Конечно, уменьшение неопределенности связано с переданным объемом информации, который.
Например, если связи нет вообще, то а также . В качестве альтернативы, если канал связи идеален и принятый сигнал идентичен сигналу у отправителя, то а также .
В определении функции скорость – искажение а также искажение между а также для данного и предписанное максимальное искажение соответственно. Когда мы используем среднюю квадратичную ошибку , как искажение меры, мы имеем (для амплитуды - непрерывных сигналов ):
Как показывают приведенные выше уравнения, вычисление функции "скорость – искажение" требует стохастического описания входных данных. с точки зрения PDF , а затем стремится найти условную PDF которые минимизируют скорость для данного искажения . Эти определения могут быть сформулированы с точки зрения теории меры для учета дискретных и смешанных случайных величин.
Аналитическое решение этой задачи минимизации часто трудно получить , за исключением некоторых случаев , для которых мы следующее предложение два из наиболее известных примеров. Известно, что функция скорость-искажение любого источника подчиняется нескольким фундаментальным свойствам, наиболее важными из которых является то, что это непрерывная , монотонно убывающая выпуклая (U) функция, и, таким образом, форма функции в примерах является типичной (даже измеренная скорость –Функции искажения в реальной жизни имеют очень похожие формы).
Хотя аналитических решений этой проблемы мало, существуют верхняя и нижняя границы этих функций, включая знаменитую нижнюю границу Шеннона (SLB), которая в случае квадрата ошибки и источников без памяти утверждает, что для произвольных источников с конечной дифференциальной энтропией
где h ( D ) - дифференциальная энтропия гауссовской случайной величины с дисперсией D. Эта нижняя граница может быть расширена для источников с памятью и другими мерами искажения. Одной из важных особенностей SLB является то, что он асимптотически плотный в режиме низких искажений для широкого класса источников и в некоторых случаях фактически совпадает с функцией скорость – искажение. Нижние границы Шеннона обычно могут быть найдены, если искажение между любыми двумя числами может быть выражено как функция разницы между значениями этих двух чисел.
Алгоритм Блейхута-Аримото , совместно изобретен Ричард Блейхута , элегантный итерационный метод численного получения скорости искажения функции произвольных конечных источников алфавита ввода / вывода и много работы было сделано , чтобы распространить его на более общие проблемные случаи.
При работе со стационарными источниками с памятью необходимо изменить определение функции искажения скорости, и ее следует понимать в смысле предела, принятого для последовательностей увеличивающейся длины.
где
а также
где верхний индекс обозначает полную последовательность до этого времени, а нижний индекс 0 указывает начальное состояние.
Гауссов источник без памяти (независимый) с квадратичным искажением ошибки
Если предположить, что - гауссовская случайная величина с дисперсией , и если предположить, что последовательные отсчеты сигнала являются стохастически независимы (или , что эквивалентно, источник без памяти , или сигнал коррелированы ), мы находим следующее аналитическое выражение для скорости как функции искажения:
- [2] : 310
На следующем рисунке показано, как выглядит эта функция:
Теория скоростей и искажений говорит нам, что «не существует системы сжатия, работающей за пределами серой зоны». Чем ближе практическая система сжатия к красной (нижней) границе, тем лучше она работает. Как правило, эта граница может быть достигнута только путем увеличения параметра длины блока кодирования. Тем не менее, даже при единичной длине блока часто можно найти хорошие (скалярные) квантователи, которые работают на расстояниях от функции скорость – искажение, которые имеют практическое значение. [2]
Эта функция скорость – искажение верна только для гауссовых источников без памяти. Известно, что гауссовский источник является наиболее «сложным» для кодирования: для данной среднеквадратичной ошибки требуется наибольшее количество битов. Производительность практической системы сжатия, работающей, скажем, с изображениями, вполне может быть ниже показана нижняя граница.
Источник Бернулли без памяти (независимый) с искажением Хэмминга
Функция коэффициента искажения случайной величины Бернулли с искажением Хэмминга определяется выражением:
где обозначает двоичную функцию энтропии .
График функции скорость-искажение для :
Связь теории скорости и искажения с пропускной способностью канала [3]
Предположим , что мы хотим передать информацию об источнике для пользователя с искажением , не превышающей D . Теория скоростного искажения говорит нам, что по крайней меребиты / символ информации из источника должны доходить до пользователя. Мы также знаем из теоремы Шеннона о канальном кодировании, что если энтропия источника равна H бит / символ, а пропускная способность канала равна C (где), тогда биты / символ будут потеряны при передаче этой информации по данному каналу. Чтобы у пользователя была какая-либо надежда на реконструкцию с максимальным искажением D , мы должны наложить требование, чтобы информация, теряемая при передаче, не превышала максимально допустимую потерюбит / символ. Это означает, что пропускная способность канала должна быть не менее.
Смотрите также
- Декорреляция
- Оптимизация скорости и искажений
- Исходное кодирование
- Сферы-упаковка
- Отбеливание
- Алгоритм Блахута-Аримото
Рекомендации
- ↑ Blau, Y. & Michaeli, T. «Переосмысление сжатия с потерями: компромисс между скоростью, искажением и восприятием» . Материалы Международной конференции по машинному обучению, 2019.
- ^ a b Томас М. Обложка, Джой А. Томас (2006). Элементы теории информации . John Wiley & Sons, Нью-Йорк.
- ^ Тоби Бергер (1971). Теория искажения скорости: математическая основа сжатия данных . Прентис Холл.
Внешние ссылки
- PyRated : код Python для основных вычислений в теории искажений скорости.
- Инструмент для обучения сжатию изображений и видео VcDemo