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

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

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

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

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