Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. Васту-шастра. Сад и деревья.
  2. Деревья
  3. Деревья и леса
  4. Деревья отказов (Fault Trees)
  5. Деревья событий (Event Trees)
  6. Тема 7.7 Деревья. Код Пруфера.

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

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

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

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

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

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

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

 

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

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



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

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

 

<== предыдущая лекция | следующая лекция ==>
| Квадротомические деревья

Дата добавления: 2014-01-04; Просмотров: 612; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2018) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление ip: 54.166.203.17
Генерация страницы за: 0.002 сек.