Квадротомические деревья

Общие положения

Квадротомическая модель данных

Определение 3.12. Квадротомическое представление данных или квадродерево – это модель представления пространственных объектов в виде иерархической древовидной структуры, основанный на декомпозиции пространства на квадратные участки или квадратные блоки (квадранты), каждый из которых делится рекурсивно на 4 вложенных до достижения некоторого уровня – числа Мортона, обеспечивающего требуемую детальность описания объектов, эквивалентную разрешению растра.

Квадротомическое представление данных еще называют «дерево квадратов», «Q-дерево» и «4-дерево».

Обычно модель используется как средство снижения времени доступа к данным в базе пространственных данных. Это средство повышения эффективности обработки и компактности хранения данных по сравнению с растровыми представлениями, является «интеллектуализированным» растром.

В случае 3D-систем используется октотомическое дерево. По сути использование такого дерева является трехмерным групповым кодированием пространственных данных.

Квадротомическая модель используется, в основном, для компактного представления растров, но иногда она применяется и для компактного представления векторных данных. Ниже рассмотрим идею квадротомических деревьев и один из алгоритмов перевода данных в растровом формате в квадротомическое дерево.

Квадротомическое дерево основано на рекурсивном разделении квадрата на квадранты и подквадранты до тех пор, пока все подквадранты не станут однородными по отношению к значению изображения, например, по цветам или пока не будет достигнут предопределенный заранее наименьший уровень разрешения. Если изображение состоит из 2ⁿ*2ⁿ пикселей, тогда оно полностью представлено на уровне n, а единичные пиксели тогда находятся на нулевом уровне. Квадрат уровня L (0<L<n) содержит 2^L*2^L пикселей, всего 4^L.

В ранних работах по квадротомическим деревьям связи между квадрантом и подквадрантом давались в виде дерева со степенью ветвления, равной 4. В такой структуре связи между родительским и дочерним уровнем определяются системой внешних указателей. Все узловые точки дерева, за исключением корневой, имеют одного родителя, в то же время все они, кроме так называемых листьев, связаны с четырьмя дочерними узловыми точками. Недавние исследования в этой области показали, что для описания больших квадротомических деревьев наиболее подходящей структурой является линейное квадродерево. В таком дереве каждый листовой узел представлен линейным числовым кодом, который базируется на упорядоченном списке узловых точек прародителей. Последующее преобразование дерева в код достигается использованием битового уровня или модулярной арифметики. В настоящее время разработаны несколько квадротомических алгоритмов, использующих свойство линейных квадротомических деревьев. Система линейных кодов, в свою очередь, обеспечивает эффективную связь между структурами пространственных данных и алгоритмами, используемыми в вычислительной геометрии для решения проблем восстановления прямоугольников и определения ближайшего соседа.

Исследования показали, что определенные формы линейных квадротомических деревьев могут быть быстро закодированы. Более того, если существует несколько последовательно закодированных листьев с одинаковым значением, то фиксировать надо код последнего из этих листьев.

Чаще всего используется схема пространственной нумерации (индексирования) элементов квадротомического дерева, известная как матрица Мортона, основанная на кривых Пиано и числах Пиано, или матрица Пиано-Гильберта. Мортоновские числовые последовательности позволяют создавать удобные коды для линейных квадротомических деревьев. Мортоновское число для пикселя получают путем пересчета в двоичной системе строковой и столбцовой координаты данного пикселя. Следует помнить, что чаще всего координаты нумеруются от нуля, а листу квадротомичекого дерева присваивается мортоновское число. Так как мортоновская последовательность фиксирует пиксели в двух измерениях одновременно, то такой подход назван двумерным групповым кодированием.

Дата добавления: 2014-01-04