Кодирование бинарных последовательностей, кодирование длин серий (КДС)

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

Простой пример:

На входе: AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

На выходе: 3A2B4C1D6E38A

L=2^b*- количество объединенных символов КДС

Дифференциальное кодирование (ДИКМ): общее описание метода

Разностное кодирование=кодирование с предсказанием=дифференциальная импульсная кодовая модуляция.

26. Квантование при дифференциальном кодировании (ДИКМ), шкала Макса.

Что же такое квантование вообще?

Под квантованием произвольного сигнала f будем понимать следующий процесс:

Пусть область значений f разбита на L интервалов квантования с границами

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

Все это вместе – шкала квантования:

Квантование заключается в замене квантуемого значения параметра f на квантованный уровень f_i

того интервала квантования                       в который попадает это квантуемое значение.

Равномерная шкала

Это наиболее распространенная шкала. В ней все интервалы квантования одинаковой длины, а квантующие значения – это середины этих интервалов. Эта шкала наиболее проста и удобна, но для ДИКМ не подходит. Почему?

Потому что в ДИКМ квантованию подвергается разностный сигнал f(n,m), при этом квантованный сигнал , кодируется малым количеством разрядов b (для достижения эффекта сжатия), т.е. шкала квантования содержит малое число интервалов квантования L=2^b.  

А равномерную шкалу строят обычно таким образом, чтобы она согласовывалась с дисперсией, например по правилу «трех сигма» (размах шкалы d_L-d₀ равен 6σ²_f ). В таком случае шкала получается слишком «растянутой», расстояние между уровнями слишком велико и величина ошибки квантования становится недопустимой:  

Шкала Макса

Выходом из ситуации является использование неравномерных шкал, в которых уровни квантования выбираются тем уже, чем больше вероятность попадания в такой интервал. Наиболее известная шкала – шкала Макса.

Она строится из условия минимизации квадратичной погрешности квантования:

при заданном количестве уровней квантования, т.е. является решением задачи:

Отсюда можно получить следующие выражения для квантованных уровней и границ интервалов квантования:

Построение шкалы Макса основано на том, что f_i и d_i зависят друг от друга. В общем случае алгоритм следующий:

1. Берем равномерную шкалу (в качестве начального приближения)

2. По формуле (1) пересчитываем все f_i

3. По формуле (2) пересчитываем все d_i

4. Если при последнем пересчете погрешность изменились меньше, чем на заданную величину, или квантованные уровни подвинулись меньше, чем на заданную величину, то КОНЕЦ, ИНАЧЕ вернуться к шагу 2.

В некоторых частных случаях шкалу Макса удается построить более простым способом.

Для любознательных

27. Линейные и нелинейные предсказатели при дифференциальном кодировании (ДИКМ)

Эффективность метода ДИКМ в значительной степени определяется точностью алгоритма предсказания: чем точнее предсказание, тем меньше дисперсия разностного сигнала и, следовательно, тем лучше он сжимается. Следовательно, основными требованиями к предсказателю являются как можно большая точность при минимальной вычислительной сложности.

Линейное предсказание

Устройство предсказателя обычно строится как линейная система с постоянными параметрами:

где g( k, l) – импульсная характеристика предсказателя, а D – область ее ненулевых значений, которая должна быть задана таким образом, чтобы обеспечить физическую реализуемость системы при заданном виде развертки. Например, при построчной развертке на область D налагается следующее ограничение:

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