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

Теория информации
Энтропия Дифференциальная энтропия Условная энтропия Совместная энтропия Взаимная информация Условная взаимная информация Относительная энтропия Скорость энтропии Предельная плотность дискретных точек
Асимптотическое свойство равнораспределения Теория скорости-искажения
Теорема кодирования источника Шеннона Емкость канала Теорема кодирования с шумом Теорема Шеннона – Хартли.

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Теория скоростей – искажений»  – Новости  · газеты  · книги  · ученый  · JSTOR (Март 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Вступление

Кодировщик искажений скорости и декодер. Кодировщик ${ displaystyle f_ {n}}$ кодирует последовательность ${ displaystyle X ^ {n}}$. Закодированная последовательность ${ displaystyle Y ^ {n}}$ затем передается в декодер ${ displaystyle g_ {n}}$ который выводит последовательность ${ displaystyle { hat {X}} ^ {n}}$. Мы стараемся минимизировать искажение исходной последовательности ${ displaystyle X ^ {n}}$ и восстановленная последовательность ${ Displaystyle { шляпа {X}} ^ {п}}$.

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

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

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

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

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

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

${ displaystyle d (x, { hat {x}}) = { begin {cases} 0 & { text {if}} x = { hat {x}} 1 & { text {if}} x neq { hat {x}} end {case}}}$

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

${ displaystyle d (x, { hat {x}}) = left (x - { hat {x}} right) ^ {2}}$

Скоростные-искажающие функции

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

${ displaystyle inf _ {Q_ {Y mid X} (y mid x)} I_ {Q} (Y; X) { text {при условии}} D_ {Q} leq D ^ {*}. }$

Здесь ${ Displaystyle Q_ {Y mid X} (y mid x)}$, иногда называемый тестовым каналом, является условный функция плотности вероятности (PDF) выхода канала связи (сжатый сигнал) ${ displaystyle Y}$ для данного входа (исходный сигнал) ${ displaystyle X}$, и ${ Displaystyle I_ {Q} (Y; X)}$ это взаимная информация между ${ displaystyle Y}$ и ${ displaystyle X}$ определяется как

${ Displaystyle I (Y; X) = H (Y) -H (Y mid X) ,}$

где ${ Displaystyle H (Y)}$ и ${ Displaystyle H (Y середина X)}$ энтропия выходного сигнала Y и условная энтропия выходного сигнала при входном сигнале соответственно:

${ Displaystyle H (Y) = - int _ {- infty} ^ { infty} P_ {Y} (y) log _ {2} (P_ {Y} (y)) , dy}$

${ Displaystyle H (Y mid X) = - int _ {- infty} ^ { infty} int _ {- infty} ^ { infty} Q_ {Y mid X} (y mid x ) P_ {X} (x) log _ {2} (Q_ {Y mid X} (y mid x)) , dx , dy.}$

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

${ displaystyle inf _ {Q_ {Y mid X} (y mid x)} E [D_ {Q} [X, Y]] { text {при условии}} I_ {Q} (Y; X) leq R.}$

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

Взаимную информацию можно понимать как меру `` априорной '' неопределенности получателя в отношении сигнала отправителя (ЧАС(Y)), уменьшенная неопределенностью, которая остается после получения информации о сигнале отправителя (${ Displaystyle H (Y середина X)}$). Конечно, уменьшение неопределенности связано с переданным объемом информации, который ${ Displaystyle I влево (Y; X вправо)}$.

Например, если есть нет общение вообще, тогда ${ Displaystyle H (Y середина X) = H (Y)}$ и ${ Displaystyle I (Y; X) = 0}$. В качестве альтернативы, если канал связи идеален и принятый сигнал ${ displaystyle Y}$ идентичен сигналу ${ displaystyle X}$ у отправителя, то ${ Displaystyle Н (Y середина X) = 0}$ и ${ Displaystyle I (Y; X) = H (X) = H (Y)}$.

В определении функции скорость – искажение ${ displaystyle D_ {Q}}$ и ${ displaystyle D ^ {*}}$ искажение между ${ displaystyle X}$ и ${ displaystyle Y}$ для данного ${ Displaystyle Q_ {Y mid X} (y mid x)}$ и предписанное максимальное искажение соответственно. Когда мы используем среднеквадратичная ошибка в качестве меры искажения имеем (для амплитуда -непрерывные сигналы ):

${ Displaystyle D_ {Q} = int _ {- infty} ^ { infty} int _ {- infty} ^ { infty} P_ {X, Y} (x, y) (xy) ^ { 2} , dx , dy = int _ {- infty} ^ { infty} int _ {- infty} ^ { infty} Q_ {Y mid X} (y mid x) P_ { X} (x) (xy) ^ {2} , dx , dy.}$

Как показывают приведенные выше уравнения, вычисление функции "скорость – искажение" требует стохастического описания входных данных. ${ displaystyle X}$ с точки зрения PDF ${ Displaystyle P_ {X} (х)}$, а затем стремится найти условную PDF ${ Displaystyle Q_ {Y mid X} (y mid x)}$ которые минимизируют скорость для данного искажения ${ displaystyle D ^ {*}}$. Эти определения могут быть сформулированы с точки зрения теории меры для учета дискретных и смешанных случайных величин.

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

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

${ Displaystyle R (D) geq h (X) -h (D) ,}$

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

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

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

${ Displaystyle R (D) = lim _ {n rightarrow infty} R_ {n} (D)}$

где

${ displaystyle R_ {n} (D) = { frac {1} {n}} inf _ {Q_ {Y ^ {n} mid X ^ {n}} in { mathcal {Q}}} I (Y ^ {n}, X ^ {n})}$

и

${ displaystyle { mathcal {Q}} = {Q_ {Y ^ {n} mid X ^ {n}} (Y ^ {n} mid X ^ {n}, X_ {0}): E [ d (X ^ {n}, Y ^ {n})] leq D }}$

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

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

Если предположить, что ${ displaystyle X}$ это Гауссовский случайная величина с отклонение ${ displaystyle sigma ^ {2}}$, и если предположить, что последовательные отсчеты сигнала ${ displaystyle X}$ находятся стохастически независимый (или, что то же самое, источник без памяти, или сигнал некоррелированный), находим следующее аналитическое выражение для функции скорость – искажение:

${ Displaystyle R (D) = { begin {case} { frac {1} {2}} log _ {2} ( sigma _ {x} ^ {2} / D), & { text { if}} 0 leq D leq sigma _ {x} ^ {2} 0, & { text {if}} D> sigma _ {x} ^ {2}. end {cases}} }$   ^[2]:310

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

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

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

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

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

${ Displaystyle R (D) = left {{ begin {matrix} H_ {b} (p) -H_ {b} (D), & 0 leq D leq min {(p, 1-p) } 0, & D> min {(p, 1-p)} end {matrix}} right.}$

где ${ displaystyle H_ {b}}$ обозначает бинарная функция энтропии.

График функции скорость-искажение для ${ displaystyle p = 0,5}$:

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

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

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

• Декорреляция
• Оптимизация скорости и искажений
• Исходное кодирование
• Сферы-упаковка
• Отбеливание
• Алгоритм Блахута-Аримото

Рекомендации

внешняя ссылка

• PyRated: Код Python для основных вычислений в теории искажений скорости.
• Инструмент для обучения сжатию изображений и видео VcDemo