Теория скорости – искажения - Rate–distortion theory

Теория скорости и искажения является основным разделом теории информации, который обеспечивает теоретические основы для сжатия данных с потерями ; он решает проблему определения минимального количества битов на символ, измеряемого скоростью R , которое должно быть передано по каналу, так что источник (входной сигнал) может быть приблизительно восстановлен на приемнике (выходной сигнал) без превышения ожидаемое искажение D .

Вступление

Кодер искажения скорости и декодер. Кодировщик кодирует последовательность . Затем закодированная последовательность поступает в декодер, который выводит последовательность . Мы стараемся минимизировать искажение между исходной последовательностью и восстановленной последовательностью .

Теория «скорость – искажение» дает аналитическое выражение того, насколько компрессия может быть достигнута с использованием методов сжатия с потерями. Многие из существующих методов сжатия звука, речи, изображений и видео имеют процедуры преобразования, квантования и распределения битовой скорости, в которых используется общая форма функций скорость-искажение.

Теория искажения скорости была создана Клодом Шенноном в его фундаментальной работе по теории информации.

В теории искажений скорость обычно понимается как количество битов на выборку данных, которые должны быть сохранены или переданы. Понятие искажения является предметом постоянных дискуссий. В самом простом случае (который фактически используется в большинстве случаев) искажение определяется как ожидаемое значение квадрата разницы между входным и выходным сигналами (т. Е. Среднеквадратичная ошибка ). Однако, поскольку мы знаем, что большинство методов сжатия с потерями работают с данными, которые будут восприниматься людьми-потребителями (прослушивание музыки , просмотр изображений и видео), мера искажения предпочтительно должна быть смоделирована на человеческом восприятии и, возможно, на эстетике : очень похоже на использование вероятности при сжатии без потерь меры искажения можно в конечном итоге отождествить с функциями потерь, используемыми в байесовской теории оценки и принятия решений . При сжатии звука модели восприятия (и, следовательно, меры искажения восприятия) относительно хорошо разработаны и обычно используются в методах сжатия, таких как MP3 или Vorbis , но их часто нелегко включить в теорию искажения скорости. При сжатии изображений и видео модели человеческого восприятия менее развиты, и включение в них в основном ограничивается матрицей взвешивания ( квантования , нормализации ) JPEG и MPEG .

Функции искажения

Функции искажения измеряют стоимость представления символа приближенным символом . Типичными функциями искажения являются искажение Хэмминга и искажение квадратичной ошибки.

Искажение Хэмминга

Квадратная ошибка искажения

Функции скорости-искажения

Функции, связывающие скорость и искажение, находятся как решение следующей задачи минимизации:

Здесь , иногда называемая тестовым каналом, является функция условной плотности вероятности (PDF) выхода канала связи (сжатый сигнал) для данного входа (исходный сигнал) , а также взаимная информация между и определяется как

где и - энтропия выходного сигнала Y и условная энтропия выходного сигнала для входного сигнала, соответственно:

Проблема также может быть сформулирована как функция искажения-скорости, где мы находим нижнюю границу достижимых искажений для данного ограничения скорости. Соответствующее выражение:

Эти две формулировки приводят к функциям, обратным друг другу.

Взаимная информация может пониматься как мера «априорной» неопределенности получателя в отношении сигнала отправителя ( H ( Y )), уменьшенной за счет неопределенности, которая остается после получения информации о сигнале отправителя ( ). Конечно, уменьшение неопределенности связано с переданным объемом информации, который есть .

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

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

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

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

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

где h ( D ) - дифференциальная энтропия гауссовской случайной величины с дисперсией D. Эта нижняя граница может быть расширена для источников с памятью и другими мерами искажения. Одной из важных особенностей SLB является то, что он асимптотически плотный в режиме низких искажений для широкого класса источников и в некоторых случаях фактически совпадает с функцией скорость – искажение. Нижние границы Шеннона обычно могут быть найдены, если искажение между любыми двумя числами может быть выражено как функция разницы между значениями этих двух чисел.

Алгоритм Блейхута-Аримото , совместно изобретен Ричард Блейхута , элегантный итерационный метод численного получения скорости искажения функции произвольных конечных источников алфавита ввода / вывода и много работы было сделано , чтобы распространить его на более общие проблемные случаи.

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

куда

и

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

Гауссов источник без памяти (независимый) с квадратичным искажением ошибки

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

   

На следующем рисунке показано, как выглядит эта функция:

Оценить искажение function.png

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

Эта функция скорость – искажение верна только для гауссовых источников без памяти. Известно, что источник Гаусса является наиболее «сложным» для кодирования: для данной среднеквадратичной ошибки требуется наибольшее количество битов. Производительность практической системы сжатия, работающей, скажем, с изображениями, вполне может быть ниже указанной нижней границы.

Источник Бернулли без памяти (независимый) с искажением Хэмминга

Функция коэффициент искажения случайной величины Бернулли с искажением Хэмминга определяется выражением:

где обозначает двоичную функцию энтропии .

График функции скорость-искажение для :

Оцените функцию искажения Bernoulli.png

Связь теории скорости и искажения с пропускной способностью канала

Предположим , что мы хотим передать информацию об источнике для пользователя с искажением , не превышающей D . Теория скоростного искажения говорит нам, что по крайней мере бит / символ информации из источника должен доходить до пользователя. Мы также знаем из теоремы Шеннона о канальном кодировании, что если энтропия источника составляет H бит / символ, а пропускная способность канала равна C (где ), то биты / символ будут потеряны при передаче этой информации по данному каналу. Чтобы у пользователя была какая-либо надежда на реконструкцию с максимальным искажением D , мы должны наложить требование, чтобы информация, теряемая при передаче, не превышала максимально допустимую потерю бит / символ. Это означает, что емкость канала должна быть не меньше .

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

использованная литература

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