3.5.2.1. Особенности хранения информации; представленной в виде квадродерева

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

Максимальное число ранговых блоков на п-ом уровне квадродерева равно 4п.

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

2. Если на каком-то уровне имеется один ненулевой индекс, То должны присутствовать все 4 индекса (т.е. если в списке есть 111, то должны быть 112, 113 и 114).

3. «О» на некотором уровне означает, что все соответствующе индексы более высоких уровней - тоже нули.

Предлагается использовать двоичную структуру дерева с 4П битами на п-ом уровне. «1» показывает, что блок разбит на меньшие блоки. «О» показывает, что на данном уровне до. полнительного разбиения нет (и, следовательно, нет его и на всех более верхних уровнях). Заметим, что для того, чтобы максимальная глубина квадродерева была равна /V, дерево должно иметь только N-1 уровень, так как по определению на N-ом уровне разбиения нет. Так, например, 3-уровневое разбиение, показанное на Рис. 3.3.5, может быть представлено следующим 2-уровневым двоичным деревом:

Уровень 110 10

Уровень 2 Ю00 0000 0100 0000

Таким образом, вся информация о разбиении на Рис. 3.3.5 может быть записана в 20 битах. На самом деле, эту информацию можно записать меньшим количеством бит, если заметить, что второй и четвертый блоки на уровне 2 состоят из одних нулей и фактически являются избыточными, так как их значения определяются наличием нуля на предыдущем уровне. Такая схема требует более сложной логики декодирования. Программа, прилагаемая к книге, не исключает избыточные нули из хранимой информации.

Листинг 3.5.1 представляет относительно компактную программу, которая преобразует ранговый список индексов в состоящий из нулей и единиц «массив уровней» квадродерева, такой, как показан выше. Объяснять, что делает программа, дольше, чем написать саму эту программу. Переменная ievei_array - это массив указателей на структуру типа