Октодерево — это древовидная структура данных , в которой каждый внутренний узел имеет ровно восемь дочерних элементов . Октодеревья чаще всего используются для разбиения трехмерного пространства путем рекурсивного деления его на восемь октантов . Октодеревья — это трехмерный аналог квадродеревьев . Слово происходит от oct (греческий корень, означающий «восемь») + tree . Октодеревья часто используются в трехмерной графике и трехмерных игровых движках .
Каждый узел в октодереве подразделяет пространство, которое он представляет, на восемь октантов . В октодереве точечной области (PR) узел хранит явную трехмерную точку , которая является «центром» подразделения для этого узла; точка определяет один из углов для каждого из восьми дочерних элементов. В октодереве на основе матрицы (MX) точка подразделения неявно является центром пространства, которое представляет узел. Корневой узел октодерева PR может представлять бесконечное пространство; корневой узел октодерева MX должен представлять конечное ограниченное пространство, чтобы неявные центры были четко определены. Обратите внимание, что октодеревья не то же самое, что k -d деревья : k -d деревья разделяются вдоль измерения, а октодеревья разделяются вокруг точки. Кроме того, k -d деревья всегда являются бинарными, что не относится к октодеревьям. При использовании поиска в глубину узлы должны быть пройдены, и должны быть просмотрены только требуемые поверхности.
Использование октодеревьев для трехмерной компьютерной графики было впервые предложено Дональдом Мигером в Политехническом институте Ренсселера и описано в отчете 1980 года «Кодирование октодеревьев: новая технология представления, обработки и отображения произвольных трехмерных объектов с помощью компьютера» [1] , на который он получил патент 1995 года (с приоритетной датой 1984 года ) «Высокоскоростная генерация изображений сложных сплошных объектов с использованием кодирования октодеревьев» [2].
Алгоритм квантования цвета октодерева , изобретенный Гервотцем и Пургатхофером в 1988 году, кодирует данные о цвете изображения как октодерево глубиной до девяти уровней. Октодеревья используются, потому что в системе RGB есть три цветовых компонента . Индекс узла для ответвления на верхнем уровне определяется формулой, которая использует самые значимые биты красного, зеленого и синего цветовых компонентов, например, 4r + 2g + b. Следующий более низкий уровень использует следующую значимость бита и т. д. Менее значимые биты иногда игнорируются, чтобы уменьшить размер дерева.
Алгоритм очень эффективен в плане памяти, поскольку размер дерева может быть ограничен. Нижний уровень октодерева состоит из листовых узлов, которые накапливают цветовые данные, не представленные в дереве; эти узлы изначально содержат отдельные биты. Если в октодерево вводится гораздо больше желаемого количества цветов палитры, его размер можно постоянно уменьшать, находя узел нижнего уровня и усредняя его битовые данные в листовой узел, отсекая часть дерева. После завершения выборки исследование всех маршрутов в дереве вплоть до листовых узлов, принимая во внимание биты по пути, даст приблизительно необходимое количество цветов.
Пример рекурсивного алгоритма, представленный ниже ( синтаксис MATLAB ), разлагает массив трехмерных точек на ячейки в стиле октодерева. Реализация начинается с одной ячейки, окружающей все заданные точки, которая затем рекурсивно подразделяется на 8 областей октодерева. Рекурсия останавливается, когда выполняется заданное условие выхода. Примеры таких условий выхода (показаны в коде ниже):
функция [binDepths, binParents, binCorners, pointBins] = OcTree ( точки ) binDepths = [ 0 ] % Инициализируем массив глубин ячеек с помощью этой единственной ячейки базового уровня binParents = [ 0 ] % Эта ячейка базового уровня не является дочерней для других ячеек binCorners = [ min ( points ) max ( points )] % Она окружает все точки в пространстве XYZ pointBins (:) = 1 % Изначально все точки назначаются этой первой ячейке divide ( 1 ) % Начинаем деление этой первой ячейки функция деления ( binNo ) % Если этот бин удовлетворяет каким-либо условиям выхода, не делить его дальше. binPointCount = nnz ( pointBins == binNo ) binEdgeLengths = binCorners ( binNo , 1 : 3 ) - binCorners ( binNo , 4 : 6 ) binDepth = binDepths ( binNo ) exitConditionsMet = binPointCount < значение || min ( binEdgeLengths ) < значение || binDepth > значение if 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 % Рекурсивно разделите этот вновь созданный контейнер divided ( newBinNo ) конец Принимая полный список цветов 24-битного изображения RGB в качестве входных точек для реализации точечного разложения Octree, описанной выше, следующий пример показывает результаты квантования цвета Octree. Первое изображение является оригиналом (532818 отдельных цветов), в то время как второе является квантованным изображением (184 отдельных цвета) с использованием разложения Octree, где каждому пикселю назначается цвет в центре ячейки Octree, в которую он попадает. В качестве альтернативы, окончательные цвета могут быть выбраны в центроиде всех цветов в каждой ячейке Octree, однако это дополнительное вычисление оказывает очень малое влияние на визуальный результат. [8]
% Прочитать исходное изображение RGB Img = imread ( 'IMG_9980.CR2' ); % Извлечь пиксели как триплеты точек RGB pts = reshape ( Img , [], 3 ); % Создать объект разложения OcTree, используя целевую емкость бинов OT = OcTree ( pts , 'BinCapacity' , ceil ( ( size ( pts , 1 ) / 256 ) * 7 )); % Найти , какие бины являются "листовыми узлами " объекта octree leafs = find ( ~ ismember ( 1 : OT.BinCount , OT.BinParents ) & ... ismember ( 1 : OT.BinCount , OT.PointBins ) ) ; % Найти центральное положение RGB каждого листового контейнера binCents = mean ( reshape ( OT.BinBoundaries ( leafs ,:), [], 3 , 2 ), 3 ); % Создать новое "индексированное" изображение с цветовой картой ImgIdx = zeros ( size ( Img , 1 ), size ( Img , 2 )) ; for i = 1 : length ( leafs ) pxNos = find ( OT.PointBins == leafs ( i ) ) ; ImgIdx ( pxNos ) = i ; end ImgMap = binCents / 255 ; % Преобразовать 8-битный цвет в значения MATLAB rgb % Отобразить исходное изображение с 532818 цветами и полученное изображение с 184 цветами figure subplot ( 1 , 2 , 1 ), imshow ( Img ) title ( sprintf ( 'Исходное изображение с %d цветом' , size ( unique ( pts , 'rows' ), 1 ))) subplot ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) title ( sprintf ( 'Квантованное октадеревом %d-цветное изображение' , size ( ImgMap , 1 ))) 