Octree - Octree

Izquierda: subdivisión recursiva de un cubo en octantes . Derecha: El octárbol correspondiente.

Un octárbol es una estructura de datos de árbol en la que cada nodo interno tiene exactamente ocho hijos . Octrees son los más utilizados para dividir un espacio tridimensional por recursivamente subdividir en ocho octantes. Los octrees son el análogo tridimensional de los quadtrees . La palabra se deriva de oct (raíz griega que significa "ocho") + árbol . Los octrees se utilizan a menudo en gráficos 3D y motores de juegos 3D .

Para la representación espacial

Cada nodo de un octárbol subdivide el espacio que representa en ocho octantes . En un octárbol de región de puntos (PR), el nodo almacena un punto tridimensional explícito , que es el "centro" de la subdivisión para ese nodo; el punto define una de las esquinas para cada uno de los ocho niños. En un octárbol basado en matrices (MX), el punto de subdivisión es implícitamente el centro del espacio que representa el nodo. El nodo raíz de un octárbol PR puede representar un espacio infinito; el nodo raíz de un octárbol MX debe representar un espacio limitado finito para que los centros implícitos estén bien definidos. Tenga en cuenta que los octárboles no son lo mismo que los árboles k -d : los árboles k -d se dividen a lo largo de una dimensión y los octárboles se dividen alrededor de un punto. Además, los árboles k -d son siempre binarios, lo que no es el caso de los octárboles. Al utilizar una búsqueda en profundidad, se deben atravesar los nodos y solo se deben ver las superficies requeridas.

Historia

El uso de octárboles para gráficos por computadora en 3D fue iniciado por Donald Meagher en el Instituto Politécnico de Rensselaer , descrito en un informe de 1980 "Codificación de octárboles: una nueva técnica para la representación, manipulación y exhibición de objetos arbitrarios en 3D por computadora", para el cual él posee una patente de 1995 (con una fecha de prioridad de 1984 ) "Generación de imágenes de alta velocidad de objetos sólidos complejos usando codificación octree"

Usos comunes

Aplicación a la cuantificación del color

El algoritmo de cuantificación de color de octárbol , inventado por Gervautz y Purgathofer en 1988, codifica los datos de color de la imagen como un octárbol de hasta nueve niveles de profundidad. Los octárboles se utilizan porque hay tres componentes de color en el sistema RGB . El índice de nodo desde el que se ramifica en el nivel superior está determinado por una fórmula que utiliza los bits más significativos de los componentes de color rojo, verde y azul, por ejemplo, 4r + 2g + b. El siguiente nivel inferior utiliza el siguiente bit de significación, y así sucesivamente. A veces se ignoran los bits menos significativos para reducir el tamaño del árbol.

El algoritmo es muy eficiente en memoria porque el tamaño del árbol puede ser limitado. El nivel inferior del octárbol consta de nodos de hojas que acumulan datos de color no representados en el árbol; estos nodos contienen inicialmente bits únicos. Si se ingresa en el octárbol mucho más del número deseado de colores de paleta, su tamaño se puede reducir continuamente buscando un nodo de nivel inferior y promediando sus datos de bits en un nodo de hoja, podando parte del árbol. Una vez que se completa el muestreo, la exploración de todas las rutas en el árbol hasta los nodos de las hojas, tomando nota de los bits a lo largo del camino, producirá aproximadamente el número requerido de colores.

Implementación para descomposición puntual

El esquema de algoritmo recursivo de ejemplo a continuación ( sintaxis de MATLAB ) descompone una matriz de puntos tridimensionales en bins de estilo octárbol. La implementación comienza con un solo contenedor que rodea todos los puntos dados, que luego se subdivide de forma recursiva en sus 8 regiones de octárbol. La recursividad se detiene cuando se cumple una condición de salida determinada. Ejemplos de tales condiciones de salida (que se muestran en el código a continuación) son:

  • Cuando un contenedor contiene menos de un número determinado de puntos
  • Cuando un contenedor alcanza un tamaño o volumen mínimo en función de la longitud de sus bordes
  • Cuando la recursividad ha alcanzado un número máximo de subdivisiones
function [binDepths,binParents,binCorners,pointBins] = OcTree(points)
 
binDepths = [0]     % Initialize an array of bin depths with this single base-level bin
binParents = [0]    % This base level bin is not a child of other bins
binCorners = [min(points) max(points)] % It surrounds all points in XYZ space
pointBins(:) = 1    % Initially, all points are assigned to this first bin
divide(1)           % Begin dividing this first bin
 
function divide(binNo)
    
% If this bin meets any exit conditions, do not divide it any further.
binPointCount = nnz(pointBins==binNo)
binEdgeLengths = binCorners(binNo,1:3) - binCorners(binNo,4:6)
binDepth = binDepths(binNo)
exitConditionsMet = binPointCount<value || min(binEdgeLengths)<value || binDepth>value
if exitConditionsMet
    return; % Exit recursive function
end
 
% Otherwise, split this bin into 8 new sub-bins with a new division point
newDiv = (binCorners(binNo,1:3) + binCorners(binNo,4:6)) / 2
for i = 1:8
    newBinNo = length(binDepths) + 1
    binDepths(newBinNo) = binDepths(binNo) + 1
    binParents(newBinNo) = binNo
    binCorners(newBinNo) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]
    oldBinMask = pointBins==binNo
    % Calculate which points in pointBins==binNo now belong in newBinNo 
    pointBins(newBinMask) = newBinNo
    % Recursively divide this newly created bin
    divide(newBinNo)
end

Ejemplo de cuantificación de color

Tomando la lista completa de colores de una imagen RGB de 24 bits como entrada de punto para la implementación de descomposición de puntos de octárbol descrita anteriormente, el siguiente ejemplo muestra los resultados de la cuantificación de color de octárbol. La primera imagen es la original (532818 colores distintos), mientras que la segunda es la imagen cuantificada (184 colores distintos) usando descomposición de octárbol, con cada píxel asignado el color en el centro del bin de octárbol en el que cae. Alternativamente, los colores finales podrían elegirse en el centroide de todos los colores en cada contenedor de octárbol, sin embargo, este cálculo adicional tiene muy poco efecto en el resultado visual. 

% Read the original RGB image
Img = imread('IMG_9980.CR2');
% Extract pixels as RGB point triplets
pts = reshape(Img,[],3);
% Create OcTree decomposition object using a target bin capacity
OT = OcTree(pts,'BinCapacity',ceil((size(pts,1) / 256) *7));
% Find which bins are "leaf nodes" on the octree object
leafs = find(~ismember(1:OT.BinCount, OT.BinParents) & ...
    ismember(1:OT.BinCount,OT.PointBins));
% Find the central RGB location of each leaf bin
binCents = mean(reshape(OT.BinBoundaries(leafs,:),[],3,2),3);
 
% Make a new "indexed" image with a color map
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; % Convert 8-bit color to MATLAB rgb values
 
% Display the original 532818-color image and resulting 184-color image 
figure
subplot(1,2,1), imshow(Img)
title(sprintf('Original %d color image', size(unique(pts,'rows'),1)))
subplot(1,2,2), imshow(ImgIdx, ImgMap)
title(sprintf('Octree-quantized %d color image', size(ImgMap,1)))

Ver también

Referencias

enlaces externos