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

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

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

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

Введение [ править ]

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

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

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

В теории искажений скорость обычно понимается как количество битов на выборку данных, которые необходимо сохранить или передать. Понятие искажения является предметом постоянных дискуссий. ^[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{cases}}}$

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

${\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{ subject to }}D_{Q}\leq D^{*}.}$

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

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

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

${\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{ subject to }}I_{Q}(Y;X)\leq R.}$

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

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

Например, если связи нет вообще, то и . В качестве альтернативы, если канал связи идеален и принятый сигнал идентичен сигналу отправителя, тогда и .${\displaystyle H(Y\mid X)=H(Y)}$${\displaystyle I(Y;X)=0}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle H(Y\mid 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)(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.}$

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

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

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

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

где h ( 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{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] : 310}

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

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

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

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

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

${\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 . Теория искажения скорости говорит нам, что по крайней мере бит / символ информации из источника должен достичь пользователя. Мы также знаем из теоремы Шеннона о канальном кодировании, что если энтропия источника равна H бит / символ, а пропускная способность канала равна C (где ), то биты / символ будут потеряны при передаче этой информации по данному каналу. Чтобы у пользователя была какая-либо надежда на реконструкцию с максимальным искажением D , мы должны наложить требование, чтобы информация, теряемая при передаче, не превышала максимально допустимую потерю${\displaystyle R(D)}$${\displaystyle C<H}$${\displaystyle H-C}$${\displaystyle H-R(D)}$бит / символ. Это означает, что емкость канала должна быть не меньше, чем .${\displaystyle R(D)}$

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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