Теория скоростей – искажений

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

• 1 Введение
• 2 Функции искажения
  • 2.1 Искажение Хэмминга
  • 2.2 Искажение в квадрате ошибки
• 3 Функции коэффициента искажения
  • 3.1 Без памяти (независимые) Источник Гаусса с искажением в квадрате ошибки
  • 3.2 Источник Бернулли без памяти (независимый) с искажением Хэмминга
• 4 Связь теории искажения скорости с пропускной способностью канала
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

Кодер и декодер искажения скорости. Кодировщик $f\; n\; \{\backslash \; displaystyle\; f\_\; \{n\}\}$кодирует последовательность $X\; n\; \{\backslash \; displaystyle\; X\; ^\; \{n\}\}$. Закодированная последовательность $Y\; n\; \{\backslash \; displaystyle\; Y\; ^\; \{n\}\}$затем подается в декодер $gn\; \{\backslash \; displaystyle\; g\_\; \{n\}\}$, который выводит последовательность $X\; ^\; n\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{X\}\}\; ^\; \{n\}\}$. Мы пытаемся минимизировать искажение между исходной последовательностью $X\; n\; \{\backslash \; displaystyle\; X\; ^\; \{n\}\}$и восстановленной последовательностью $X\; ^\; n\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{X\}\}\; ^\; \{n\}\}$.

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

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

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

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

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

$d\; (x,\; x\; ^)\; =\; \{0,\; если\; x\; =\; x\; ^\; 1,\; если\; x\; \ne \; x\; ^\; \{\backslash \; displaystyle\; d\; (x,\; \{\backslash \; hat\; \{x\}\})\; =\; \{\backslash \; begin\; \{case\}\; 0\; \{\backslash \; text\; \{if\}\}\; x\; =\; \{\backslash \; hat\; \{x\}\}\; \backslash \backslash \; 1\; \{\backslash \; text\; \{if\}\}\; x\; \backslash \; neq\; \{\backslash \; hat\; \{x\}\}\; \backslash \; end\; \{cases\}\}\}$

Искажение квадратичной ошибки

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

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

$inf\; QY\; \mid \; X\; (y\; \mid \; x)\; IQ\; (Y;\; X)\; при\; условии\; DQ\; \le \; D\; \ast .\; \{\backslash \; displaystyle\; \backslash \; inf\; \_\; \{Q\_\; \{Y\; \backslash \; mid\; X\}\; (y\; \backslash \; mid\; x)\}\; I\_\; \{Q\}\; (Y;\; X)\; \{\backslash \; text\; \{при\; условии\}\}\; D\_\; \{Q\}\; \backslash \; leq\; D\; ^\; \{*\}.\; \}$

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

$I\; (Y\; ;\; Икс)\; знак\; равно\; ЧАС\; (Y)\; -\; ЧАС\; (Y\; \mid \; Икс)\; \{\backslash \; Displaystyle\; I\; (Y;\; X)\; =\; H\; (Y)\; -H\; (Y\; \backslash \; mid\; X)\; \backslash ,\}$

где $H\; (Y)\; \{\backslash \; displaystyle\; H\; (Y)\}$и $H\; (Y\; \mid \; X)\; \{\backslash \; displaystyle\; H\; (Y\; \backslash \; mid\; X)\}$- энтропия выходного сигнала Y и условная энтропия выходного сигнала для входного сигнала, соответственно:

$H\; (Y)\; =\; -\; \int \; -\; \infty \; \infty \; PY\; (Y)\; журнал\; 2\; \; (PY\; (y))\; dy\; \{\backslash \; displaystyle\; H\; (Y)\; =\; -\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; P\_\; \{Y\}\; (y)\; \backslash \; log\; \_\; \{2\}\; (P\_\; \{Y\}\; (y))\; \backslash ,\; dy\}$

$H\; (Y\; \mid \; X)\; =\; -\; \int \; -\; \infty \; \infty \; \int \; -\; \infty \; \infty \; QY\; \mid \; X\; (y\; \mid \; x)\; PX\; (x)\; log\; 2\; \; (QY\; \mid \; X\; (\; у\; \mid \; х))\; dxdy.\; \{\backslash \; Displaystyle\; H\; (Y\; \backslash \; mid\; X)\; =\; -\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; Q\_\; \{Y\; \backslash \; mid\; X\}\; (y\; \backslash \; mid\; x)\; P\_\; \{X\}\; (x)\; \backslash \; log\; \_\; \{2\}\; (Q\_\; \{Y\; \backslash \; mid\; X\}\; (y\; \backslash \; mid\; x))\; \backslash ,\; dx\; \backslash ,\; dy.\}$

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

$inf\; Q\; Y\; \mid \; X\; (y\; \mid \; x)\; E\; [D\; Q\; [X,\; Y]]\; при\; условии\; I\; Q\; (Y;\; X)\; \le \; R.\; \{\backslash \; displaystyle\; \backslash \; inf\; \_\; \{Q\_\; \{Y\; \backslash \; mid\; X\}\; (y\; \backslash \; mid\; x)\}\; E\; [D\_\; \{Q\}\; [X,\; Y]]\; \{\backslash \; text\; \{при\; условии\}\}\; I\_\; \{Q\}\; (Y;\; X)\; \backslash \; leq\; R.\}$

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

Взаимная информация может пониматься как мера «предшествующей» неопределенности получателя в отношении сигнала отправителя (H (Y)), уменьшенной за счет неопределенности, которая остается после получения информации о сигнале отправителя ($ЧАС\; (Y\; \mid \; Икс)\; \{\backslash \; Displaystyle\; H\; (Y\; \backslash \; mid\; X)\}$). Конечно, уменьшение неопределенности происходит из-за переданного количества информации, а именно: $I\; (Y;\; X)\; \{\backslash \; displaystyle\; I\; \backslash \; left\; (Y;\; X\; \backslash \; right)\}$.

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

В определении функции "скорость – искажение" $DQ\; \{\backslash \; displaystyle\; D\_\; \{Q\}\}$и $D\; \ast \; \{\backslash \; displaystyle\; D\; ^\; \{*\}\}$- это искажение между $X\; \{\backslash \; displaystyle\; X\}$и $Y\; \{\backslash \; displaystyle\; Y\}$для данного $QY\; \mid \; X\; (y\; \mid \; x)\; \{\backslash \; displaystyle\; Q\_\; \{Y\; \backslash \; mid\; X\}\; (y\; \backslash \; mid\; x)\}$и предписанного максимума искажения соответственно. Когда мы используем среднеквадратичную ошибку в качестве меры искажения, мы имеем (для амплитуды - непрерывных сигналов ):

$DQ\; =\; \int \; -\; \infty \; \infty \; \int \; -\; \infty \; \infty \; PX,\; Y\; (x,\; y)\; (x\; -\; y)\; 2\; dxdy\; =\; \int \; -\; \infty \; \infty \; \int \; -\; \infty \; \infty \; QY\; \mid \; X\; (y\; \mid \; x)\; PX\; (x)\; (x\; -\; y)\; 2\; dxdy.\; \{\backslash \; Displaystyle\; D\_\; \{Q\}\; =\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; P\_\; \{X,\; Y\}\; (x,\; y)\; (xy)\; ^\; \{\; 2\}\; \backslash ,\; dx\; \backslash ,\; dy\; =\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; \backslash \; int\; \_\; \{-\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; Q\_\; \{Y\; \backslash \; mid\; X\}\; (y\; \backslash \; mid\; x)\; P\_\; \{\; X\}\; (x)\; (xy)\; ^\; \{2\}\; \backslash ,\; dx\; \backslash ,\; dy.\}$

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

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

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

$R\; (D)\; \ge \; h\; (X)\; -\; h\; (D)\; \{\backslash \; displaystyle\; R\; (D)\; \backslash \; geq\; h\; (X)\; -h\; (D)\; \backslash ,\}$

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

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

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

$R\; (D)\; =\; lim\; n\; \to \; \infty \; R\; n\; (D)\; \{\backslash \; displaystyle\; R\; (D)\; =\; \backslash \; lim\; \_\; \{n\; \backslash \; rightarrow\; \backslash \; infty\}\; R\_\; \{n\}\; (D)\}$

где

$Р\; N\; (D)\; знак\; равно\; 1\; N\; Inf\; QY\; N\; \mid \; Икс\; N\; \in \; QI\; (Y\; N,\; X\; n)\; \{\backslash \; Displaystyle\; R\_\; \{n\}\; (D)\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; inf\; \_\; \{Q\_\; \{\; Y\; ^\; \{n\}\; \backslash \; mid\; X\; ^\; \{n\}\}\; \backslash \; in\; \{\backslash \; mathcal\; \{Q\}\}\}\; I\; (Y\; ^\; \{n\},\; X\; ^\; \{n\})\}$

и

$Q\; =\; \{QY\; n\; \mid \; Икс\; N\; (Y\; N\; \mid \; Икс\; N,\; Икс\; 0):\; E\; [d\; (X\; n,\; Y\; n)]\; \le \; D\}\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{Q\}\}\; =\; \backslash \; \{Q\_\; \{Y\; ^\; \{n\}\; \backslash \; mid\; X\; ^\; \{n\}\}\; (Y\; ^\; \{n\}\; \backslash \; mid\; X\; ^\; \{n\},\; X\_\; \{0\}):\; E\; [d\; (X\; ^\; \{n\},\; Y\; ^\; \{n\})]\; \backslash \; leq\; D\; \backslash \}\}$

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

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

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

$R\; (D)\; =\; \{1\; 2\; log\; 2\; \; (\sigma \; x\; 2\; /\; D),\; если\; 0\; \le \; D\; \le \; \sigma \; x\; 2\; 0,\; если\; D>\sigma \; x\; 2.\; \{\backslash \; Displaystyle\; R\; (D)\; =\; \{\backslash \; begin\; \{case\}\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; log\; \_\; \{2\}\; (\backslash \; sigma\; \_\; \{x\}\; ^\; \{2\}\; /\; D),\; \{\backslash \; text\; \{\; if\}\}\; 0\; \backslash \; leq\; D\; \backslash \; leq\; \backslash \; sigma\; \_\; \{x\}\; ^\; \{2\}\; \backslash \backslash \; 0,\; \{\backslash \; text\; \{if\}\}\; D>\backslash \; sigma\; \_\; \{x\}\; ^\; \{2\}.\; \backslash \; end\; \{cases\}\}\; \}$

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

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

Эта функция скорость-искажение верна только для гауссовых источников без памяти. Известно, что t Источник Гаусса является наиболее "трудным" для кодирования: для данной среднеквадратичной ошибки требуется наибольшее количество битов. Производительность практической системы сжатия, работающей, скажем, с изображениями, вполне может быть ниже показанной нижней границы $R\; (D)\; \{\backslash \; displaystyle\; R\; \backslash \; left\; (D\; \backslash \; right)\}$.

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

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

$R\; (D)\; Знак\; равно\; \{ЧАС\; б\; (п)\; -\; ЧАС\; б\; (D),\; 0\; \le \; D\; \le \; мин\; (п,\; 1\; -\; р)\; 0,\; D>мин\; (р,\; 1\; -\; р)\; \{\backslash \; Displaystyle\; R\; (D)\; =\; \backslash \; влево\; \backslash \; \{\{\backslash \; begin\; \{matrix\}\; H\_\; \{b\}\; (p)\; -H\_\; \{b\}\; (D),\; 0\; \backslash \; leq\; D\; \backslash \; leq\; \backslash \; min\; \{(p,\; 1-p)\}\; \backslash \backslash \; 0,\; D>\backslash \; min\; \{(\; p,\; 1-p)\}\; \backslash \; end\; \{matrix\}\}\; \backslash \; right.\}$

где $H\; b\; \{\backslash \; displaystyle\; H\_\; \}\}$обозначает двоичную энтропийную функцию.

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

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

• Декорреляция
• Оптимизация скорости – искажения
• Кодирование источника
• Упаковка сфер
• Отбеливание
• Алгоритм Блахута-Аримото

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