Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Слева: Рекурсивное разбиение куба на октанты . Справа: соответствующее октодерево.

Октодерева представляет собой структуру данных , дерево , в котором каждый внутренний узел имеет ровно восемь детей . Октодеревья чаще всего используются для разделения трехмерного пространства путем рекурсивного деления его на восемь октантов. Октодеревья являются трехмерным аналогом квадродеревьев . Имя образовано от oct + tree , но учтите, что обычно оно пишется " octree " только с одним "t". Октодеревья часто используются в 3D-графике и в 3D- игровых движках .

Для пространственного представления [ править ]

Каждый узел в октодереве подразделяет пространство, которое он представляет, на восемь октантов . В октодереве точечной области (PR) узел хранит явную трехмерную точку , которая является «центром» подразделения для этого узла; точка определяет один из углов для каждого из восьми детей. В октодереве на основе матрицы (MX) точка подразделения неявно является центром пространства, которое представляет узел. Корневой узел октодерева PR может представлять бесконечное пространство; корневой узел октодерева MX должен представлять конечное ограниченное пространство, чтобы неявные центры были четко определены. Обратите внимание, что октодеревья - это не то же самое, что деревья k -d : деревья k -d разделяются по измерению, а октодеревья разбиваются вокруг точки. Также k-d деревья всегда бинарны, чего нельзя сказать о октодеревьях. Используя поиск в глубину, необходимо проходить узлы и просматривать только требуемые поверхности.

История [ править ]

Использование октодерева для трехмерной компьютерной графики было впервые предложено Дональдом Мигером из Политехнического института Ренсселера , описанным в отчете 1980 г. «Кодирование октодерева: новая техника для представления, манипулирования и отображения произвольных трехмерных объектов с помощью компьютера», [1] на который он имеет патент 1995 г. (с датой приоритета 1984 г. ) «Высокоскоростное создание изображений сложных твердых объектов с использованием кодирования октодерева» [2]

Обычное использование [ править ]

Приложение для квантования цвета [ править ]

Алгоритм квантования цвета октодерева , изобретенный Герваутцем и Пургатхофером в 1988 году, кодирует данные цвета изображения как октодерево глубиной до девяти уровней. Октодеревья используются потому, что в системе RGB есть три цветовых компонента . Индекс узла, от которого следует разветвляться на верхнем уровне, определяется формулой, в которой используются наиболее значимые биты компонентов красного, зеленого и синего цветов, например 4r + 2g + b. Следующий более низкий уровень использует значение следующего бита и так далее. Менее значимые биты иногда игнорируются, чтобы уменьшить размер дерева.

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

Реализация точечной декомпозиции [ править ]

Контур Примера рекурсивного алгоритма ниже ( MATLAB синтаксиса) разлагается массив 3-мерных точек в октодереве бункеров стиля. Реализация начинается с одного бина, окружающего все заданные точки, который затем рекурсивно разделяется на 8 областей октодерева. Рекурсия останавливается, когда выполняется заданное условие выхода. Примеры таких условий выхода (показаны в коде ниже):

  • Когда в корзине меньше заданного количества точек
  • Когда бункер достигает минимального размера или объема в зависимости от длины его краев
  • Когда рекурсия достигла максимального количества подразделений
функция  [binDepths, binParents, binCorners, pointBins] = OcTree ( точки )  binDepths  =  [ 0 ]  % Инициализирует массив глубин бинов  с помощью этого единственного бункера базового уровня binParents =  [ 0 ]  % Этот бункер базового уровня не является дочерним по отношению к другим бункерам binCorners  =  [ min ( points )  max ( points )]  % It окружает все точки в пространстве XYZ pointBins (:)  =  1  % Изначально все точки назначаются этому первому делению бина ( 1 )  % Начните деление этого первого деления функции бина ( binNo )   % Если этот лоток удовлетворяет каким-либо условиям выхода, не разделяйте его дальше. binPointCount  =  nnz ( pointBins == binNo ) binEdgeLengths  =  binCorners ( binNo , 1 : 3 )  -  binCorners ( binNo , 4 : 6 ) binDepth  =  binDepths ( binNo ) exitConditionsMet  =  binPointCount < значение  ||  мин ( binEdgeLengths ) < значение ||  binDepth > значение, если  exitConditionsMet  return ;  % Выход из рекурсивной функции end % В противном случае разделите этот лоток на 8 новых суб-ячеек с новой точкой разделения newDiv  =  ( binCorners ( binNo , 1 : 3 )  +  binCorners ( binNo , 4 : 6 ))  /  2 для  i  =  1 : 8  newBinNo  =  length ( binDepths )  +  1  binDepths ( newBinNo )  =  binDepths ( binNo )  +  1  binParents( NewBinNo )  =  binNo  binCorners ( newBinNo )  =  [ один  из  самых  8  пар  из  в  newDiv  с  minCorner  или  maxCorner ]  oldBinMask  =  pointBins == binNo  % Вычислить , какие точки в pointBins == binNo Теперь принадлежат newBinNo  pointBins ( newBinMask )  =  newBinNo  % Рекурсивно разделить этот вновь созданный  разделитель бинов ( newBinNo ) end

Пример цветового квантования [ править ]

Принимая полный список цветов 24-битного изображения RGB в качестве входной точки для реализации декомпозиции точек октодерева, описанной выше, следующий пример показывает результаты квантования цвета октодерева. Первое изображение является исходным (532818 различных цветов), а второе - квантованным изображением (184 различных цвета) с использованием декомпозиции октодерева, при этом каждому пикселю назначается цвет в центре окна октодерева, в которое он попадает. В качестве альтернативы, конечные цвета могут быть выбраны в центроиде всех цветов в каждом бункере октодерева, однако это добавленное вычисление очень мало влияет на визуальный результат. [8]

% Прочитать исходное изображение RGB Img  =  imread ( 'IMG_9980.CR2' ); % Извлечь пиксели как триплеты точек RGB pts  =  reshape ( Img , [], 3 ); % Создать объект декомпозиции OcTree с использованием целевой емкости бункера OT  =  OcTree ( pts , 'BinCapacity' , ceil (( size ( pts , 1 )  /  256 )  * 7 )); % Найти которые бункеры «листовые узлы» на объект октодерева Лифс  =  находке( ~ ismember ( 1 : OT . BinCount ,  OT . BinParents )  &  ...  ismember ( 1 : OT . BinCount , OT . PointBins )); % Найти центральное RGB расположение каждого листа бен binCents  =  средняя ( Reshape ( OT . BinBoundaries ( листья ,:), [], 3 , 2 ), 3 ); % Создайте новое "проиндексированное" изображение с цветовой картой ImgIdx  =  нули ( размер ( Img , 1 ),  размер ( Img , 2 )); для  я  =  1 : длина ( листья )  pxNos  =  найти ( OT . PointBins == листья ( я ));  ImgIdx ( pxNos )  =  i ; конец ImgMap  =  binCents  /  255 ; % Преобразование 8-битного цвета в значения MATLAB rgb % Отображение исходного 532818-цветное изображение и в результате 184-цветного изображения фигуры подзаговора (1,2,1),  imshow (Img) Название ( Sprintf ( 'Оригинал% d цветного изображения' ,  размера ( уникальный ( PTS , 'строк' ) , 1 ))) subplot ( 1 , 2 , 2 ),  imshow ( ImgIdx ,  ImgMap ) title ( sprintf ( 'Цветное изображение% d, квантованное по октодереву' ,  size ( ImgMap , 1)))

См. Также [ править ]

  • Разделение двоичного пространства
  • Иерархия ограничивающих интервалов
  • Cube 2: Sauerbraten , трехмерный игровой движок, в котором геометрия почти полностью основана на октодеревьях.
  • id Tech 6 - это трехмерный игровой движок, использующий воксели, хранящиеся в октодеревьях.
  • Irrlicht Engine , поддерживает узлы сцены октодерева
  • Клее проблема меры
  • Линейное октодерево
  • OGRE , имеет реализацию менеджера сцены октодерева
  • Подмощение
  • Воксель
  • Quadtree

Ссылки [ править ]

  1. ^ Мигэр, Дональд (октябрь 1980). «Кодирование октодерева: новый метод представления, манипулирования и отображения произвольных трехмерных объектов с помощью компьютера». Политехнический институт Ренсселера (Технический отчет IPL-TR-80-111).
  2. ^ Мигер, Дональд. «Быстрая генерация изображений сложных твердых объектов с использованием кодирования октодерева» . УСПО . Проверено 20 сентября 2012 года .
  3. ^ Дэвид П. Luebke (2003). Уровень детализации 3D-графики . Морган Кауфманн. ISBN 978-1-55860-838-2.
  4. ^ Эльзеберг, Ян и др. « Сравнение стратегий поиска ближайшего соседа и реализаций для эффективной регистрации формы ». Журнал программной инженерии для робототехники 3.1 (2012): 2-12.
  5. ^ Akenine-Mo ller, Tomas; Хейнс, Эрик; Хоффман, Нэти (2018-08-06). Рендеринг в реальном времени, четвертое издание . CRC Press. ISBN 978-1-351-81615-1.
  6. ^ Хеннинг Эберхард, Веса Клумпп, Уве Д. Ханебек, Деревья плотности для эффективного нелинейного оценивания состояния , Труды 13-й Международной конференции по слиянию информации, Эдинбург, Соединенное Королевство, июль 2010 г.
  7. ^ В. Древелле, Л. Джаулин и Б. Зерр, Гарантированная характеристика исследуемого пространства мобильного робота с помощью субмарин , NOLCOS 2013.
  8. ^ Блумберг, Дэн С. «Цветовое квантование с использованием октодеревьев». , 4 сентября 2008 г. Проверено 12 декабря 2014 г.

Внешние ссылки [ править ]

  • Квантование октодерева в Microsoft Systems Journal
  • Квантование цвета с использованием октодеревьев доктора Добба
  • Квантование цвета с использованием октодеревьев в исходном коде доктора Добба [ постоянная мертвая ссылка ]
  • Обзор квантования цвета октодерева
  • Параллельная реализация алгоритма генерации октодерева, П. Соджан Лал, А. Унникришнан, К. Пулозе Якоб, ICIP 1997, IEEE Digital Library
  • Генерация октодерева из растрового сканирования с уменьшенной потерей информации, П. Соджан Лал, А. Унникришнан, К. Пулозе Джейкоб, Международная конференция IASTED VIIP 2001 [1] [ постоянная мертвая ссылка ]
  • Параллельные октодеревья для приложений с конечными элементами
  • Видео: Использование октодерева в оценке состояния