РАЗДЕЛ 2
ОБОСНОВАНИЕ СОВМЕСТИМОСТИ АРИФМЕТИЧЕСКОГО
КОДИРОВАНИЯ И ПРЕОБРАЗОВАНИЯ УОЛША В ТЕЛЕВИЗИОННЫХ СИСТЕМАХ
В разделе обосновано совместное использование преобразования Уолша и арифметического кодирования, которое позволяет снизить время на сжатие и восстановление изображений; сократить дополнительную статистическую избыточность. Показано, что ошибка аппроксимации слабокоррелированных изображений снижается в случае аппроксимации базисами Уолша. Проводится оценка устраняемой избыточности в трансформантах ортогональных преобразований на основе арифметического кодирования.
2.1 Обоснование выбора дискретного преобразования Уолша для аппроксимации изображений в системах сжатия
Использование в методах сжатия изображений двумерных ортогональных преобразований обусловлено:
1) снижением двумерной статистической зависимости между элементами обрабатываемых блоков изображений. В результате чего формируется трансформанта ортогональных преобразований, компоненты которой характеризуются неравномерностью распределения вероятностей их значений. В этом случае выполняется неравенство
, (2.1)
(2.2)
где и - соответственно количество информации на одну компоненту до и после учета закона распределения вероятностей появления величин ;
- значение компоненты, имеющей в трансформанте координаты ;
- динамический диапазон трансформанты ортогональных преобразований, равный
; (2.3)
; ; (2.4)
и - соответственно максимальное и минимальное значение компоненты в трансформанте ортогонального преобразования.
Причем, согласно свойствам энтропии информационных источников Бернулли, величина будет тем меньше, чем больше степень неравномерности распределения ;
2) тем, что величина ошибки аппроксимации элементов изображений на основе базисных функций ортогональных преобразований распределяется по всем элементам восстановленного блока изображения.
, (2.5)
где - значения -х элементов блока исходного изображения;
- значения -х элементов блока восстановленного изображения.
В этом случае повышается качество визуального восприятия видеоинформации.
В общем случае прямое и обратное ортогональные преобразования задаются соответственно выражениями [5, 36, 63, 79, 84, 98]:
; (2.6)
, (2.7)
где - трансформанта ортогонального преобразования размером ;
- массив размером , составленный из элементов исходного изображения;
- матрица дискретных значений базисных функций;
- транспонированная матрица дискретных значений базисных функций;
- коэффициент нормировки.
В системах сжатия размеры обрабатываемых блоков выбираются равными друг другу, т.е. . Значения элементов матрицы определяются видом базисных функций:
- для дискретного косинусного преобразования матрица равна :
; (2.8)
Для матрица примет вид:
= ;
- для преобразования Хаара матрица равна :
,
(2.9)
; .
Для матрица примет вид:
= ;
- для преобразования Уолша матрица равна :
; ; (2.10)
; .
Первые восемь дискретных функций, упорядоченных по Уолшу, имеют вид:
= .
Сравним различные виды ДОП по временным затратам на обработку. При этом учтем, что на прямое и обратное двумерное преобразование Уолша затрачивается операций сложения и вычитания , т.е.
. (2.11)
Оценка временных затрат на -е ортогональное преобразование одной цветовой плоскости осуществляется по формуле
, (2.12)
где , - соответственно количество операций сложения (вычитания) и умножения (деления), которое необходимо выполнить для -го вида ортогонального преобразования блока размерностью ;
, - количество операций соответственно сложения (вычитания) и умножения (деления), выполняемое вычислительной системой за 1 сек.;
- количество блоков размерностью в изображении размерностью .
Поскольку между скоростью выполнения операций сложения (вычитания) и операций умножения (деления) выполняется неравенство
то выразим величину через величину с использованием коэффициента :
или
, (2.13)
где - коэффициент, показывающий во сколько раз для вычислительных систем скорость выполнения операций сложения (вычитания) превышает скорость выполнения операций умножения (деления).
В этом случае соотношение (2.12) примет вид
. (2.14)
Согласно формуле (2.14), время для различных видов ортогональных преобразований равно
- для ДКП:
; (2.15)
- для преобразования Хаара
; (2.16)
- для преобразования Уолша
. (2.17)
Из сравнительного анализа выражений (2.15) - (2.17) следует, что:
- суммарное количество арифметических операций на быстрое преобразование Уолша меньше, чем количество операций, затрачиваемое на выполнение дискретного косинусного преобразования, т.е. выполняется неравенство . Причем
; (2.18)
- временные затраты на выполнение арифметических операций, соответствующих преобразованию Уолша, будут меньше временных затрат, необходимых для выполнения арифметических операций для преобразования Хаара , если выполняется неравенство
, (2.19)
где .
Между величинами выполняется следующее отношение:
. (2.20)
Причем, если выполняется неравенство (2.19), то
. (2.21)
Выражения (2.18) и (2.20) определяют нижнюю границу выигрыша по времени обработки для преобразования Уолша относительно преобразований ДКП и Хаара. Это объясняется тем, что операции сложения (вычитания), выполняемые для преобразований ДКП и Хаара, являются соответственно вещественными и частично вещественными, что приводит к дополнительному увеличению времени обработки относительно времени, требуемого на выполнение целочисленных операций сложения (вычитания) для преобразования Уолша. Оценка степени выигрыша по времени обработки для ДПУ относительно ДКП и ДПХ для разных типов микропроцессоров приведены в табл. 2.1 [12, 14, 25, 43]. Их анализ показывает, что минимальный выигрыш по времени обработки для ДПУ относительно ДКП и ДПХ равен 3,6 и 2,75 раза соответственно для