РАЗДЕЛ 2
ОБОСНОВАНИЕ ВОЗМОЖНОСТИ КОМПАКТНОГО ПРЕДСТАВЛЕНИЯ МАССИВОВ ДЛИН СЕРИЙ ПОЛИАДИЧЕСКИМИ КОДАМИ
Приводится обоснование возможности компактного представления массивов длин серий полиадическими кодами на основе исследования их физических особенностей. Излагается вероятностно - статистическая модель компактного представления серий одинаковых элементов изображений полиадическими кодами. Дано теоретическое обоснование совместимости массивов длин серий и полиадических кодов.
2.1. Обоснование совместимости полиадических кодов и массивов длин
серий на основе их физических особенностях
Для снижения времени доведения видеоинформации необходимо, чтобы полиадические коды и длины серий соответствовали по следующим показателям:
1. Достигалась требуемая степень сжатия изображений, которая зависит от цифрового объема массива длин серий и массивов цветовых координат .
2. Общее количество операций на кодирование и декодирование не должно превышать порядка [2, 24, 35].
3. Обеспечивалось бы сохранение нужного качества восстановления изображения (не менее 40 дБ [6, 21, 73, 74, 105 - 107]).
С целью обоснования такого соответствия рассмотрим физические особенности полиадического кодирования длин серий.
В общем случае полиадическое кодирование задается выражением [10, 11, 67, 71, 108]:
, (2.1)
где - числовое значение i-й серии в последовательности (блок, столбец, строка) длин серий
;
- количество длин серий в ;
- максимальное значение, увеличенное на 1 (основание полиадического числа) для i+1 элемента (при ) последовательности
;
- значение полиадического кода для последовательности .
Если значение находится для каждой последовательности , то каждый полиадический код будет иметь свою систему оснований. Это приведет к снижению коэффициента сжатия. Поэтому основания вычисляются для нескольких последовательностей , , где - количество последовательностей , для которых формируется общая система оснований. Другими словами полиадическое кодирование осуществляется для массивов L длин серий. Тогда величины находятся для строк массива L по формуле
, (2.2)
где - строка массива L;
- значение длины серии на пересечении -й строки и j -го столбца.
Из анализа выражений (2.1) и (2.2) следует, что значение полиадического кода не будет превышать величину произведения оснований по всем строкам массива L [11]:
. (2.3)
В связи с этим логарифм от правой части неравенства (2.3) является значением максимального количества разрядов , затрачиваемых на один полиадический код
.
В свою очередь произведение оснований ограничено сверху величиной произведения предельных (с технической стороны) значений длин серий по m строкам
. (2.4)
Причем логарифм от правой части неравенства (2.4) является значением объема цифрового представления элементов последовательности до полиадического кодирования
.
Знак равенства в выражении (2.4) будет только в том случае, когда максимальное значение в каждой строке равно предельно возможному значению длин серий :
.
В этом случае количество разрядов на представление полиадического кода последовательности и количество разрядов на представление этой последовательности до полиадического кодирования будут равны
= .
В противном случае, если не все максимальные значения равны :
,
то на основании неравенства (2.4) длина полиадического кода будет меньше исходного кодового представления последовательности длин серий
< .
Отсюда следует, что сжатие массивов длин серий в результате полиадического кодирования произойдет в том случае, если не все максимальные значения в строках равны . Другими словами полиадические коды позволят компактно представить массивы длин серий, если максимальные значения имеют неравномерное распределение или ограниченные значения ()
.
При этом произведение равно количеству перестановок длин серий в последовательности с учетом ограничений на максимальные значения (выражение (2.2)). Величина в общем случае равна количеству перестановок с повторениями (без учета ограничений). Тогда, если выполняется неравенство (2.4), то последовательность длин серий будет иметь комбинаторную избыточность. Значит сжатие массивов длин серий за счет полиадического кодирования будет достигнуто в том случае, если они имеют комбинаторную избыточность, обусловленную ограничениями на максимальные значения . Кроме того, из анализа выражения (2.4) следует, что чем меньше максимальные значения , тем больше степень сжатия массивов длин серий. Поэтому для длин серий, имеющих большие численные значения должна существовать возможность понижения динамического диапазона.
Таким образом, для повышения степени сжатия изображений массивы длин серий должны удовлетворять следующим требованиям полиадических кодов:
1. Должны иметь комбинаторную избыточность, вызванную неравномерным распределением максимальных значений или ограниченными значениями , т.е. .
2. Должна существовать возможность сокращения динамического диапазона длин серий. Это позволит снизить значения .
На основе выражения (2.2) значение характеристики вычисляется для элементов -й строки, а, следовательно, является векторной характеристикой. Поэтому в случае полиадического кодирования наибольший интерес представляют свойства не отдельных длин серий, а их совокупностей (последовательностей). Причем поскольку являются максимумами в строках, то они характеризует динамический диапазон значений длин серий. Значит для обоснования возможности сжатия массивов д