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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

\inf _{Q_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{ subject to }}D_{Q}\leq D^{*}.

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

I(Y;X)=H(Y)-H(Y\mid X)\,

где $H(Y)$ и $H(Y\mid X)$ – энтропия выходного сигнала Y и условная энтропия выходного сигнала с учетом входного сигнала соответственно:

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

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.

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

\inf _{Q_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y]]{\text{ subject to }}I_{Q}(Y;X)\leq R.

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

Взаимную информацию можно понимать как меру «априорной» неопределенности, которую получатель имеет относительно сигнала отправителя ( H ( Y )), уменьшенную на неопределенность, оставшуюся после получения информации о сигнале отправителя ( $H(Y\mid X)$ ). Конечно, уменьшение неопределенности происходит за счет сообщаемого количества информации, которая $I\left(Y;X\right)$ .

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

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

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

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

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

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

R(D)\geq h(X)-h(D)\,

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

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

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

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

где

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

и

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

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

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

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

R(D)={\begin{cases}{\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]

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

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

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

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

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

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.

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

График функции искажения скорости для $p=0.5$ :

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

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

См. также

Алгоритм Блахута – Аримото - Класс алгоритмов в теории информации.
Сжатие данных – компактное кодирование цифровых данных.
Декорреляция - процесс уменьшения корреляции внутри одного или нескольких сигналов.
Оптимизация скорости и искажений — алгоритм принятия решений, используемый при сжатии видео.
Упаковка сфер – геометрическая структура
Белый шум – тип сигнала при обработке сигнала

Ссылки

^ Блау, Ю.; Михаэли, Т. (2019). «Переосмысление сжатия с потерями: компромисс между скоростью, искажением и восприятием» (PDF) . Материалы международной конференции по машинному обучению . ПМЛР. стр. 675–685. arXiv : 1901.07821 .
^ Обложка и Томас 2012 , с. 310
^ Обложка, Томас М.; Томас, Джой А. (2012) [2006]. «10. Теория искажения скорости» . Элементы теории информации (2-е изд.). Уайли. ISBN 978-1-118-58577-1 .
^ Бергер, Тоби (1971). Теория искажения скорости: математическая основа сжатия данных . Прентис Холл. ISBN 978-0-13-753103-5 . LCCN 75-148254 . ОСЛК 156968 .

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

Марзен, Сара; ДеДео, Саймон. «PyRated: пакет Python для теории искажения скорости» . PyRated — это очень простой пакет Python для выполнения самых основных вычислений в теории искажений скорости: определения «кодовой книги» и скорости передачи R с учетом функции полезности (матрицы искажений) и бета -множителя Лагранжа .
Инструмент обучения сжатию изображений и видео VcDemo

[1] Блау, Ю.; Михаэли, Т. (2019). «Переосмысление сжатия с потерями: компромисс между скоростью, искажением и восприятием» (PDF) . Материалы международной конференции по машинному обучению . ПМЛР. стр. 675–685. arXiv : 1901.07821 .

[2] Обложка и Томас 2012 , с. 310

[3] Обложка, Томас М.; Томас, Джой А. (2012) [2006]. «10. Теория искажения скорости» . Элементы теории информации (2-е изд.). Уайли. ISBN 978-1-118-58577-1 .

[BergerRateDistortion-4] Бергер, Тоби (1971). Теория искажения скорости: математическая основа сжатия данных . Прентис Холл. ISBN 978-0-13-753103-5 . LCCN 75-148254 . ОСЛК 156968 .

[1]

[2]

[3]

[4]