Тетрарное дерево
Cтраница 1
Тетрарное дерево - одна из наиболее часто рассматриваемых в современной литературе структур данных. Тетрарные деревья являются сейчас популярным объектом исследований, и их свойства изучены достаточно досконально; в докладе [6.11] дан обзор полученных результатов. [1]
Выбирается начальный уровень тетрарного дерева и для каж дого квадратного фрагмента, соответствующего вершине, за водится список L, в который помещаются все грани воспро изводимых трехмерных объектов. Список М для всех фраг ментов - пустой. [2]
Q - квадратный фрагмент, соответствующий листу тетрарного дерева. L - список, содержащий все грани, которые могут иметь пересечение с фрагментом Q. Флагу F присваивается 1 для всех квадратных фрагментов, для которых задача разделения видимых и невидимых элементов еще не решена. [3]
Этот алгоритм обрабатывает фрагменты изображения, соответствующие вершинам тетрарного дерева ( см. разд. [5]
Из утверждения 6.1 следует, что при использовании тетрарного дерева каждый уровень требует добавления двух битов, и их накопление, естественно, может превзойти допустимые пределы. С другой стороны, существует определенный баланс между числом битов, затрачиваемых на q, r и af-q. Если значения чисел af очень близки, то для представления г и ai-q требуется очень немного битов, однако для хранения q может потребоваться до Q бит. Если различия между значениями чисел щ велики, то значение q будет малым и для его хранения потребуется меньшее число битов. Это обстоятельство можно использовать для получения представлений, не требующих дополнительных затрат памяти; они рассматриваются в следующем разделе. Здесь мы обсудим, каким образом утверждение 6.1 можно использовать для увеличения эффективности сжатия. [6]
Описанный в этой главе алгоритм, основанный на использовании тетрарного дерева, является модификацией алгоритма, предложенного Уорноком ( точную ссылку на его работу можно найти в монографии [1.4] или статье [17.13]); отметим, что это первое упоминание в научной печати о применении такой структуры данных в обработке изображений. Ряд методов, предложенных в более поздние годы, описан в статье [17.10], в том числе решение задачи разделения видимых и невидимых элементов сцены для нелинейных конечных участков поверхности. В статье [17.14] рассмотрена комбинированная задача, включающая разделение видимых и невидимых элементов сцены и штриховку, в том числе для случая многократного отражения света. В диссертации [13.1] проведено тщательное исследование растрового алгоритма построчного разделения видимых и невидимых элементов сцены для случая, когда объекты описываются с помощью конечных участков поверхности. В ней также подробно рассмотрены методы получения текстурообразных изображений и наши разд. В статье [17.3] описывается один из методов рандомизации, который был успешно использован для получения изображений участков земной поверхности. [7]
Дерево такого вида обычно называют деревом четвертой степени или тетрарным деревом. [8]
Алгоритм 6.5 описывает процесс построения первоначально грубоинформативного отображения с помощью тетрарного дерева. В этом алгоритме для воспроизведения изображения используется процедура FILL ( ЗАПОЛНЕНИЕ), причем предполагается, что изображение может быть получено также с помощью эхо-контроля. [9]
Изображение, получаемое в результате применения алгоритма расщепления - слияния, использующего тетрарное дерево, нуждается в дальнейшей обработке: необходимо слияние областей, не являющихся в данном дереве сибсами. Для осуществления этой процедуры необходимо применять другую структуру данных, которая будет рассмотрена в разд. [10]
Работа алгоритма начинается с того, что изображение разбивается на фрагменты, соответствующие листьям тетрарного дерева. Вначале число таких граней очень велико, однако большая их часть удаляется, так как они расположены вне рассматриваемого фрагмента. Если при обработке некоторого фрагмента результатами являются только 0 и 2, то этот фрагмент также можно исключить из дальнейшего рассмотрения. Он полностью покрывается одной или несколькими гранями и его цвет совпадает, следовательно, с цветом ближайшей по отношению к наблюдателю грани. Очевидно, что всякая грань, отстоявшая на некоторое расстояние от исходного фрагмента, будет отстоять и от фрагментов, являющихся его непосредственными потомками на тетрарном дереве. Поскольку первое разбиение на более мелкие фрагменты происходит в случае, когда результатом выполнения процедуры LOC является 1, то понятно, что любые изменения содержания списков L к М связаны с отстоящими или покрытыми гранями. Следовательно, эти списки могут быть переданы непосредственным потомкам разбиваемого фрагмента на тетрарном дереве. [11]
При использовании алгоритмов, предусматривающих копирование, а не совместное использование списков, следует проявлять осторожность, поскольку после копирования списки каждого из непосредственных потомков вершин на тетрарном дереве могут изменяться по-разному. [12]
Очевидным достоинством бинарных деревьев служит меньшая вариация четкости от уровня к уровню. Если в случае тетрарного дерева разрешающая способность при каждом переходе учетверяется, то в случае бинарного каждый переход приводит лишь к ее удваиванию. Поскольку в обоих случаях общий объем данных остается одним и тем же, бинарное дерево позволяет быстрее построить более точное изображение. [13]
Связный список L содержит координаты левого верхнего угла и размеры квадратов, а также указатели на предшествующий и следующий элементы. Входными данными служит набор квадратов, соответствующих некоторому уровню q тетрарного дерева. Выходными данными служит другой набор квадратов, соответствующих другим уровням дерева. Условия while на шагах 4 и 11 и условия if на шагах 8 и 13 предусматривают вызов какой-либо процедуры проверки однородности области. [14]
И наконец, ГСО является основной структурой данных, используемой при сегментации изображения с помощью выделения областей путем наращивания, в том числе на основе алгоритмов расщепления - слияния. Один из недостатков алгоритма 6.6 состоит в том, что в конечном счете области, обладающие аналогичными признаками, могут не подвергнуться слиянию, если они не имеют в тетрарном дереве общего предка. Использование ГСО на этом последнем этапе позволяет объединять подобные области. [15]
Страницы: 1 2