Un octree es una estructura de datos en forma de árbol en la que cada nodo interno tiene exactamente ocho hijos . Los octrees se utilizan con mayor frecuencia para particionar un espacio tridimensional subdividándolo recursivamente 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") + tree . Los octrees se utilizan a menudo en gráficos 3D y motores de juegos 3D .
Cada nodo de un octree subdivide el espacio que representa en ocho octantes . En un octree de región de puntos (PR), el nodo almacena un punto tridimensional explícito , que es el "centro" de la subdivisión de ese nodo; el punto define una de las esquinas de cada uno de los ocho hijos. En un octree 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 octree PR puede representar un espacio infinito; el nodo raíz de un octree MX debe representar un espacio limitado finito para que los centros implícitos estén bien definidos. Tenga en cuenta que los octrees no son lo mismo que los árboles k -d : los árboles k -d se dividen a lo largo de una dimensión y los octrees se dividen alrededor de un punto. Además, los árboles k -d siempre son binarios, lo que no es el caso de los octrees. Al utilizar una búsqueda en profundidad, se deben recorrer los nodos y solo se deben ver las superficies requeridas.
El uso de octrees para gráficos de computadora en 3D fue iniciado por Donald Meagher en el Instituto Politécnico Rensselaer , descrito en un informe de 1980 "Codificación de octree: una nueva técnica para la representación, manipulación y visualización de objetos 3D arbitrarios por computadora", [1] para el cual posee una patente de 1995 (con fecha de prioridad de 1984 ) "Generación de imágenes de alta velocidad de objetos sólidos complejos utilizando codificación de octree" [2]
El algoritmo de cuantificación de color octree, inventado por Gervautz y Purgathofer en 1988, codifica los datos de color de la imagen como un octree de hasta nueve niveles de profundidad. Los octrees se utilizan porque y hay tres componentes de color en el sistema RGB . El índice de nodo desde el que se ramifica en el nivel superior se determina mediante 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 la siguiente significación de bit, y así sucesivamente. A veces se ignoran los bits menos significativos para reducir el tamaño del árbol.
El algoritmo es muy eficiente en el uso de la memoria porque el tamaño del árbol puede ser limitado. El nivel inferior del octree consta de nodos de hoja que acumulan datos de color no representados en el árbol; estos nodos contienen inicialmente bits individuales. Si se ingresan en el octree muchos más colores de la paleta que el número deseado, 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, explorar todas las rutas en el árbol hasta los nodos de hoja, tomando nota de los bits a lo largo del camino, dará como resultado aproximadamente la cantidad requerida de colores.
El esquema de algoritmo recursivo de ejemplo que se muestra a continuación ( sintaxis de MATLAB ) descompone una matriz de puntos tridimensionales en contenedores de estilo octree. La implementación comienza con un solo contenedor que rodea todos los puntos dados, que luego se subdivide recursivamente en sus 8 regiones de octree. La recursión se detiene cuando se cumple una condición de salida determinada. Algunos ejemplos de tales condiciones de salida (que se muestran en el código a continuación) son:
función [binDepths, binParents, binCorners, pointBins] = OcTree ( puntos ) binDepths = [ 0 ] % Inicializa una matriz de profundidades de bin con este único bin de nivel base binParents = [ 0 ] % Este bin de nivel base no es un hijo de otros bins binCorners = [ min ( points ) max ( points )] % Rodea todos los puntos en el espacio XYZ pointBins (:) = 1 % Inicialmente, todos los puntos se asignan a este primer bin divide ( 1 ) % Comienza a dividir este primer bin función dividir ( binNo ) % Si este contenedor cumple alguna condición de salida, no lo divida más. binPointCount = nnz ( pointBins == binNo ) binEdgeLengths = binCorners ( binNo , 1 : 3 ) - binCorners ( binNo , 4 : 6 ) binDepth = binDepths ( binNo ) exitConditionsMet = binPointCount < valor || min ( binEdgeLengths ) < valor || binDepth > valor si exitConditionsMet return ; % Salir de la función recursiva fin % De lo contrario, divide este bin en 8 nuevos sub-bins con un nuevo punto de división newDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 para i = 1 : 8 newBinNo = length ( binDepths ) + 1 binDepths ( newBinNo ) = binDepths ( binNo ) + 1 binParents ( newBinNo ) = binNo binCorners ( newBinNo ) = [ uno de los 8 pares de newDiv con minCorner o maxCorner ] oldBinMask = pointBins == binNo % Calcula qué puntos en pointBins == binNo pertenecen ahora a newBinNo pointBins ( newBinMask ) = newBinNo % Divide recursivamente este bin recién creado divide ( newBinNo ) end Tomando la lista completa de colores de una imagen RGB de 24 bits como entrada puntual para la implementación de la descomposición de puntos de Octree descrita anteriormente, el siguiente ejemplo muestra los resultados de la cuantificación de color de Octree. La primera imagen es la original (532818 colores distintos), mientras que la segunda es la imagen cuantificada (184 colores distintos) utilizando la descomposición de Octree, con cada píxel asignado al color en el centro del contenedor de Octree en el que cae. Alternativamente, los colores finales podrían elegirse en el centroide de todos los colores en cada contenedor de Octree, sin embargo, este cálculo adicional tiene muy poco efecto en el resultado visual. [8]
% Leer la imagen RGB original Img = imread ( 'IMG_9980.CR2' ); % Extraer píxeles como tripletes de puntos RGB pts = reshape ( Img , [], 3 ); % Crear un objeto de descomposición OcTree utilizando una capacidad de bin de destino OT = OcTree ( pts , 'BinCapacity' , ceil (( size ( pts , 1 ) / 256 ) * 7 )); % Encontrar qué bins son "nodos de hoja" en el objeto octree leafs = find ( ~ ismember ( 1 : OT . BinCount , OT . BinParents ) & ... ismember ( 1 : OT . BinCount , OT . PointBins )); % Encuentra la ubicación RGB central de cada bin de hojas binCents = mean ( reshape ( OT . BinBoundaries ( leafs ,:), [], 3 , 2 ), 3 ); % Crea una nueva imagen "indexada" con un mapa de color 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 ; % Convierte colores de 8 bits a valores RGB de MATLAB % Muestra la imagen original de 532818 colores y la imagen resultante de 184 colores figure subplot ( 1 , 2 , 1 ), imshow ( Img ) title ( sprintf ( 'Imagen en color original de %d' , tamaño ( único ( pts , 'filas' ), 1 ))) subparcela ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) título ( sprintf ( 'Imagen en color %d cuantificada en octree' , tamaño ( ImgMap , 1 ))) 