6.5. БИНАРНЫЕ ДЕРЕВЬЯ ИЗОБРАЖЕНИЙ

Бинарные деревья представляют собой полезную модификацию тетрарных деревьев и обладают рядом достоинств, которые рассматриваются ниже. Хотя этот вид деревьев введен недавно (см. разд. 6.11) и изучен не столь подробно, как тетрарные деревья, бинарные деревья могут в конечном счете оказаться наилучшей структурой данных. На рис. 6.6 представлена блочная организация бинарного дерева. Изменение формы блоков от уровня к уровню не вызывает серьезных затруднений: для ее определения необходимо лишь установить, является индекс уровня четным или нечетным.

Очевидным достоинством бинарных деревьев служит меньшая вариация четкости от уровня к уровню. Если в случае тетрарного дерева разрешающая способность при каждом переходе учетверяется, то в случае бинарного каждый переход приводит лишь к ее удваиванию. Поскольку в обоих случаях общий объем данных остается одним и тем же, бинарное дерево позволяет быстрее построить более точное изображение.

Другое важное преимущество бинарных деревьев — возможность использования соотношения между средним значением и отклонениями, что позволяет передавать не больше битов, чем содержится в исходном изображении. Так, в частности, значения определяются не по формулам (6.1), а с помощью некоторого дискретного приближения, как показано на рис. 6.7.

Последовательность изображений, полученная этим способом, представлена на рис. 6.8. Верхнее крайнее левое изображение

(кликните для просмотра скана)

характеризуется лишь средним значением яркости по всем пикселам. Первое изображение третьего ряда состоит из 4096 участков (блоков), и на его передачу затрачивается одна восьмая времени, необходимого для передачи последнего (четвертого) изображения, состоящего из 32 768 пикселов. Большая часть информации содержится уже в первом из этих изображений, поэтому можно быстро принять решение о целесообразности продолжения просмотра дерева.