Тетрарное дерево

Cтраница 2

Пример, характеризующий систему адресации пикселов изображения размерами 8X8, соответствующую конструкции некоторого тетрарного дерева. первый разряд обозначает вершину первого уровня, второй - вершину второго уровня и т. д. [16]

Следовательно, число вершин приблизительно на 33 % превышает число пикселов. Оказывается, что при решении многих прикладных задач для запоминания дерева достаточно использовать только 4П ячеек. Построение подобного тетрарного дерева будет рассмотрено ниже. [17]

Сжатие и выборочный просмотр изображений отражают всего лишь два из наиболее типичных способов использования тетрар-ных ( бинарных) деревьев. Алгоритмы расщепления - слияния представляют собой развитие этого подхода. Процесс начинается с изучения вершин ( квадратов) некоторого промежуточного уровня тетрарного дерева. Процесс может рекурсивно продолжаться до тех пор, пока не возникнет возможность осуществления новых расщеплений или слияний. Эта идея реализуется в алгоритме 6 6, и мы рассмотрим его после того, как определим метод описания вершин тетрарного дерева. [18]

Алгоритм 6.6 воспроизводит основную процедуру обхода изображения размерами 2пх2п в случае, когда просмотр изображения начинается с уровня q, содержащего 4Ч квадратов с размерами 2П - Чх2п - ч каждый. Таким образом, полное изображение соответствует нулевому уровню, а отдельные пикселы - n - му. Алгоритм строит не полное дерево, а лишь его необходимые части. Он работает со связным списком L, элементы которого соответствуют вершинам тетрарного дерева, упорядоченным таким образом, что четыре последовательно расположенные вершины имеют на дереве одного и того же предка. [19]

Работа алгоритма начинается с того, что изображение разбивается на фрагменты, соответствующие листьям тетрарного дерева. Вначале число таких граней очень велико, однако большая их часть удаляется, так как они расположены вне рассматриваемого фрагмента. Если при обработке некоторого фрагмента результатами являются только 0 и 2, то этот фрагмент также можно исключить из дальнейшего рассмотрения. Он полностью покрывается одной или несколькими гранями и его цвет совпадает, следовательно, с цветом ближайшей по отношению к наблюдателю грани. Очевидно, что всякая грань, отстоявшая на некоторое расстояние от исходного фрагмента, будет отстоять и от фрагментов, являющихся его непосредственными потомками на тетрарном дереве. Поскольку первое разбиение на более мелкие фрагменты происходит в случае, когда результатом выполнения процедуры LOC является 1, то понятно, что любые изменения содержания списков L к М связаны с отстоящими или покрытыми гранями. Следовательно, эти списки могут быть переданы непосредственным потомкам разбиваемого фрагмента на тетрарном дереве. [20]

Страницы: 1 2