6.4.1. ПОСТРОЕНИЕ ТЕТРАРНОГО ДЕРЕВА

Допустим, что мы работаем с изображением, выборка значений которого может осуществляться построчно. Такая ситуация имеет место, когда это изображение хранится на ленте или диске, а также когда его дискретизация производится с помощью какого-либо барабанного сканирующего устройства или устройства, выполненного на основе телевизионной камеры (см. разд. 1.3). Для построения соответствующего дерева во внутреннюю память вводятся две строки изображения, после чего начинается просмотр четверок пикселов в последовательности, представленной на рис. 6.5, а Пусть — соответствующие уровни серого тона для каждой группы, состоящей из четырех пикселов с индексами Теперь можно определить четыре новых уровня:

Отметим, что при переходе от уровней серого тона к уровням никакой потери информации не происходит, поскольку значения восстанавливаются по значениям при помощи следующих формул:

Единственное затруднение связано с тем, что для представления уровней может потребоваться больше битов, чем для представления уровней Мы еще вернемся к этому вопросу.

Рис. 6.5. Иллюстрации к построению тетрарного дерева: а — порядок выборки пикселов из массива при построении тетрарного дерева; метки записаны в восьмеричной системе для изображения размерами — верхняя строка получена из двух строк исходного изображения, в нижней записан массив, содержащий разности уровней серого тона; в — элементы, составляющие две первые строки нового изображения

Для того чтобы сформировать следующий уровень нашего дерева, построим некоторое новое изображение, элементами строки которого служат значения Одновременно в специальный массив помещаются значения разностей Таким образом мы приходим к конструкции, представленной на рис. 6.5,б. При вводе следующих двух строк индекс первого элемента возрастает , где — длина строки, и возникает конструкция, приведенная на . В результате получим новое изображение размерами и массив состоящий из значений разностей. Отметим, что, если исходить из номеров пикселов, общий размер памяти тем не менее равен Эта процедура может повторяться до тех пор, пока не будет получено изображение, состоящее из единственного пиксела. При этом почти вся информация будет содержаться в массиве Рассмотренный процесс построения можно описать с помощью алгоритма 6.4, в котором используется процедура, представленная в виде алгоритма 6.4 а.

Алгоритм 6.4а. Построение уровня тетрарного дерева

(см. скан)