Кодирование последовательностей из нулей

Известен алгоритм кодирования повторяющихся последовательностей – RLE (Run Length Encoding), который заключается в следующем: повторяющиеся и неповторяющиеся символы заменяются на пары, состоящие из символа и счётчика повторений. Например, последовательность AAABCC будет заменена на A3B1C2. Из приведённого примера видно, что в результате RLE-кодирования количество символов может и увеличиться.

Будем применять RLE-кодирование только к нулям, а остальные символы оставлять без изменения. Здесь возможны два варианта кодирования. В первом варианте ноль используется в качестве признака начала последовательности, за которым следует счётчик повторений. При этом одиночные нули будут расширяться в пары символов, а кодирование будет целесообразно в случае достаточного количества более длинных последовательностей.

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

Может показаться, что уменьшение длины кодируемой последовательности всегда оправдывает применение RLE-кодирования. Это не так. Рассмотрим, к чему приводит замена k групп по m нулей в последовательности длиной N, содержащей n₀ нулей.

До замены количество информации в каждом нуле составляло

После замены длина кодируемой последовательности уменьшится на k*(m-1) бит.

Количество информации в символе, обозначающем группу, составит

а количество информации в оставшихся нулях возрастёт до

Таким образом, замена целесообразна, если справедливо неравенство

Решение неравенства даёт минимальную длину группы m, начиная с которой целесообразно применять RLE-кодирование. В неравенстве не учтено некоторое уменьшение количества информации в ненулевых символах, вследствие повышения их доли в общем потоке данных. Обычно это уменьшение незначительно и не сказывается на результатах энтропийного кодирования.

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

Рассмотрим два крайних случая. Первый, когда для каждой группы выделяется отдельный символ, т.е. возможные длины групп нулей представляют собой натуральный ряд. В этом случае сокращение длины кодируемой последовательности максимально, но и расширение алфавита также максимально. Второй, когда группы делятся на подгруппы, а длины подгрупп представляют собой показательный ряд степеней 2. В этом случае минимальны как расширение алфавита, так и сокращение длины последовательности. Компромиссным вариантом может стать ряд Фибоначчи, очередной член которого вычисляется как сумма двух предыдущих. Чтобы сделать выбор более богатым, предлагается использовать обобщённые ряды Фибоначчи [3], рассчитываемые по следующей рекуррентной формуле

a_i = a_i-1+ a _i-1-p-, где p – порядок ряда.

При p = 0 получаем, упомянутый ранее, показательный ряд; при p = 1 получится ряд Фибоначчи, а при больших p будем приближаться к натуральному ряду. В таблице 1 приведены примеры рядов различных порядков.

Выбор первого члена ряда выполняется на основании, приведённого выше неравенства, а порядок ряда – перебором, что нетрудно сделать, имея статистику по группам нулей.

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

Из таблицы 2 видно, что применение известного алгоритма RLE-кодирования может вредить последующему энтропийному кодированию, несмотря на уменьшение длины кодируемой последовательности. Предлагаемый алгоритм более взвешенно подходит к кодированию повторяющихся последовательностей – кодирует не все повторения, а только достаточно выгодные. В результате достигается некий компромисс между желанием большего сокращения длины последовательности и нанесением меньшего вреда энтропийному кодеру. Эксперименты показали, что эффективность предложенного алгоритма на 2 - 7 % выше известного RLE-кодирования.

Заключение

Предлагаемый алгоритм кодирования изображений формирует два потока дан-ных: основной и дополнительный. В терминах принятой в разделе 2 модели изображения, основной поток содержит информацию из множества значений отсчётов изображения Χ ⁿ, а в дополнительном потоке содержится информация о локальных свойствах изображения из множества ℜ ⁿ. В процессе кодирования алгоритм оценивает эффект от дополнительного описания множества ℜ ⁿ и находит наилучшее отношение количеств информации от множеств Χ ⁿ ℜ ⁿ, используя при этом проадаптацию к контексту изображения.

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

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

Список литературы

1. Ульянов В.Н. Алгоритм кодирования изображений без потерь со множеством пред-сказателей. – Труды V межд. научно-техн. конференции "Радиолокация, навигация, связь", Воронеж, 1999, т. 1, с. 408–412.

2. Ульянов В.Н. Кодирование изображений в технических приложениях. – Томск, 1995, – 21 с. – Томск. гос. академия систем упр. и радиоэлектроники. Деп. в ВИНИТИ 6.06.95 № 1662–В95.

3. Ульянов В.Н. Кодирование повторяющихся последовательностей. – Материалы 4-ой международной конференции "Распознавание-99", Курск, 1999, с. 36–38.