1 Это метод анализа структуры дерева, при котором каждый уровень полностью подвергается анализу до перехода к следующему уровню. - Примеч. перев.
12.5. Квантование цвета Затем файл читается еще раз, и каждый встречающийся цвет снова включается в дерево, где быстро находит «свое место»: либо на нижнем уровне дерева, где расположено его точное представление, либо на некотором промежуточном узле, где хранится его наилучший цвет-представитель. Индекс этого узла затем возвращается, сообщая, какой цвет является текущим.
Таблица 12.1. Пример пути от корня дерева до листа цвета
~к~^ 1 О 1 О 1 С) О 1
й= 0 110 10 0 1
В= 110 0 1110
Потомок 5360711 6
Посмотрим, как структура октодерева используется для увеличения эффективности процесса без особых затрат памяти. На рис. 12.22 показан фрагмент октодерева: в каждом его узле содержится некоторая информация относительно добавленных к октодереву цветов. Кроме того, каждый узел содержит восемь указателей на своих потомков. Когда к дереву добавляется какой-либо цвет, его появление фиксируется с помощью «увеличения» пути вниз вплоть до восьмого уровня. В табл. 12.1 приведен характерный пример, в котором в двоичной системе изображены байты цветов r, g, в. Рассмотрим отдельные биты тройки (r, g, в), начиная со старшего бита каждого из байтов r, g, в, - здесь они составляют 101. Это является двоичным представлением числа пять, поэтому путь ведет к потомку под номером 5. Если этот потомок до сих пор пуст, то создается и прикрепляется новый узел. Затем этот процесс повторяется со следующей по старшинству битовой тройкой (011), вследствие чего путь ведет к потомку под номером 3. После следующих пяти итераций исследуется тройка самых младших бит (110) цвета и путь ведет к потомку номер 6. Если здесь имеется концевая вершина (leaf node - лист), то есть этот цвет уже встречался в файле ранее, то число цветов (а это одно из полей узла) увеличивается на единицу. В противном случае создается лист со счетчиком цвета, равным 1. Отметим, что глубина октодерева никогда не превышает восьми, а добавление цвета осуществляется быстро, поскольку требует не более восьми вычислений индекса потомка.