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

Рис. 3.3.4.

Фрактальное кодирование изображений в градациях серого

85

3.3.2.1. Схема слежения за разбиением методом квалродерева

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

1Д0

2,0,0 3,0,0 4,0,0

Этот список соответствует начальному разбиению, или первому уровню квадродерева, показанному на Рис. 3.3.3 слева. Принято считать, что список из четырех исходных векторов сопоставляется четырем ранговым блокам, расположенным по часовой стрелке, начиная с левого верхнего. Когда алгоритм осуществляет деление рангового блока, входной вектор, соответствующий этому ранговому блоку, заменяется на четыре новых входных вектора. Компоненты векторов, индексы которых меньше номера данного уровня квадродерева, остаются неизменными, а компоненты, соответствующие данному уровню, получают значения 1, 4. Так, например, список, соответствующий второму уровню разбиения, показанному на Рис. 3.3.3 в центре, будет таким:

1,1,0

1,2,0 1,3,0 1,4,0 2,0,0 3,0,0 4,0,0

86

_Фракталы и вейвлеты для сжатия изображений в Дейс^