Un octree es una estructura de datos de árbol en la que cada nodo interno tiene exactamente ocho hijos . Los octárboles se utilizan con mayor frecuencia para dividir un espacio tridimensional subdividié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") + árbol . Los octrees se utilizan a menudo en gráficos 3D y motores de juegos 3D .
Cada nodo de un ocárbol subdivide el espacio que representa en ocho octantes . En un ocárbol 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 para cada uno de los ocho niños. 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 acotado finito para que los centros implícitos estén bien definidos. Tenga en cuenta que los octrees no son lo mismo que los k -d árboles : los k -d árboles se dividen a lo largo de una dimensión y los octrees se dividen alrededor de un punto. Además, los árboles k -d son siempre binarios, lo que no es el caso de los octrees. Al utilizar una búsqueda en profundidad, se deben atravesar los nodos y solo se deben ver las superficies requeridas.
El uso de octrees para gráficos por 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 3-D arbitrarios por computadora", [1] para la 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 octree" [2]
El algoritmo de cuantificación de color de ocárbol , inventado por Gervautz y Purgathofer en 1988, codifica los datos de color de la imagen como un ocárbol de hasta nueve niveles de profundidad. Los octrees se utilizan porque hay tres componentes de color en el sistema RGB . El índice de nodo desde el que se ramificará 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 el siguiente 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 memoria porque el tamaño del árbol puede ser limitado. El nivel inferior del octree consta de nodos de hojas que acumulan datos de color no representados en el árbol; Estos nodos contienen inicialmente bits individuales. Si se ingresa en el octree una cantidad de colores de paleta mucho mayor que la deseada, 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 las hojas, tomando nota de los bits a lo largo del camino, producirá aproximadamente la cantidad requerida de colores.
El siguiente esquema de algoritmo recursivo de ejemplo ( sintaxis de MATLAB ) descompone una matriz de puntos tridimensionales en contenedores de estilo octree. La implementación comienza con un único 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. Ejemplos de tales condiciones de salida (que se muestran en el código siguiente) son:
función [binDepths, binParents, binCorners, pointBins] = OcTree ( puntos ) binDepths = [ 0 ] % Inicializa una matriz de profundidades de contenedores con este único contenedor de nivel base binParents = [ 0 ] % Este contenedor de nivel base no es hijo de otros contenedores binCorners = [ min ( puntos ) máximo ( puntos )] % It 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 con 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 regresa ; % Salir del final de la función recursiva % De lo contrario, divida este contenedor en 8 nuevos subcontenedores con un nuevo punto de división newDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 para i = 1 : 8 newBinNo = longitud ( 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 ahora pertenece a newBinNo pointBins ( newBinMask ) = newBinNo % Divide recursivamente este bin recién creado divide ( newBinNo ) fin Tomando la lista completa de colores de una imagen RGB de 24 bits como entrada de puntos para la implementación de descomposición de puntos de Octree descrita anteriormente, el siguiente ejemplo muestra los resultados de la cuantificación de colores de octree. La primera imagen es la original (532818 colores distintos), mientras que la segunda es la imagen cuantificada (184 colores distintos) mediante descomposición de octree, donde a cada píxel se le asigna el 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' ); % Extrae píxeles como tripletes de puntos RGB pts = remodelar ( Img , [], 3 ); % Crear un objeto de descomposición OcTree utilizando una capacidad de contenedor objetivo OT = OcTree ( pts , 'BinCapacity' , ceil (( size ( pts , 1 ) / 256 ) * 7 )); % Encuentre qué contenedores son "nodos de hoja" en el objeto octree leafs = find ( ~ ismember ( 1 : OT . BinCount , OT . BinParents ) & ... ismember ( 1 : OT . BinCount , OT . PointBins )); % Encuentre la ubicación RGB central de cada contenedor de hojas binCents = mean ( reshape ( OT . BinBoundaries ( hojas ,:), [], 3 , 2 , 3 ); % Crea una nueva imagen "indexada" con un mapa de colores ImgIdx = ceros ( tamaño ( Img , 1 ), tamaño ( Img , 2 )); para i = 1 : longitud ( hojas ) pxNos = buscar ( OT . PointBins == hojas ( i )); ImgIdx ( pxNos ) = i ; finalizar ImgMap = binCents / 255 ; % Convertir color de 8 bits a valores rgb de MATLAB % Mostrar la imagen original de 532818 colores y la subtrama de la figura de la imagen de 184 colores resultante ( 1 , 2 , 1 ), imshow ( Img ) título ( sprintf ( 'Imagen original %d color' , tamaño ( único ( pts , 'filas' ), 1 ))) subtrama ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) título ( sprintf ( 'Imagen en color %d cuantificada en octree' , tamaño ( ImgMap , 1 ) )) 