Octree


Octree
Izquierda: Subdivisión recursiva de un cubo en octantes. Derecha: La grilla octree correspondiente.

Una grilla octree es una estructura "árbol (informática)" de datos en la cual cada nodo interno tiene exactamente 8 "hijos". Las grillas octree se usan mayormente para particionar un espacio tridimensional, dividiéndolo recursivamente en ocho octantes. Las grillas octree son las análogas tridimensionales de las grillas quadtree. El nombre está formado a partir de oct (octante) + tree (árbol), y normalmente se escribe como "octree" en vez de "octtree".

Contenido

Grillas octree para la representación espacial

En una grilla octree, cada nodo subdivide el espacio que representa en ocho octantes. En una región punto (PR) octree, el nodo almacena un punto tridimensional explicito, el cual es el "centro" de la subdivisión para ese nodo; el punto que define una de las esquinas para cada uno de los ocho hijos. En una octree MX, el punto de subdivisión es implícitamente el centro del espacio que el nodo representa. El nodo raíz de una PR octree puede representar un espace infinito; el nodo raíz de una octree MX debe representar un espacio con limite finito para que los centros implícitos estén bien definidos. Las grillas octree nunca se consideran árbol kd, ya que los árboles kd dividen en una dimensión mientras que las grillas octree dividen alrededor de un punto. Los árboles kd además son siempre binarios, lo cual no se cumple para las grillas octree.

Usos comunes de grillas octree

Aplicación para la cuantización del color

El algoritmo de cuantización del color de la grilla octree, inventado por Gervautz and Purgathofer en 1988, codifica datos de color de imagen como una grilla octree hasta de nueve niveles de profundidad. Las grillas octree son usadas ya que 23 = 8, y hay tres componentes de colores en el sistema modelo de color RGB (del inglés Red, Green, Blue; "rojo, verde, azul"). En índice nodo para ramificar desde en el nivel tope está determinado por una fórmula que usa los bits mas significativos de los componentes de colores rojo, verde, y azul, e.g. 4r + 2g ´b. el siguiente nivel bajo usa el siguiente bit significativo, y etc. los bits menos significativos se ignoran en algunas ocasiones para reducir el tamaño del árbol.

El algoritmo es de una memoria altamente eficiente ya que el tamaño del árbol se puede limitar. El nivel del fondo de la grilla octree consiste de nodos hojas que acumulan datos de color que no están representados en el árbol; estos nodos contienen inicialmente bits simples. Si en ingresan en la grilla octree muchos más números de colores de paletas que los deseados, su tamaño se puede reducir continuamente buscando un nodo de nivel bajo y promediando sus datos de bit hasta en un nodo hoja, podando parte del árbol. Una vez que el muestreo está completo, al explorar todas las rutas en el árbol hasta las hojas nodos, y al tomar nota de los bits a lo largo del camino, se obtendrá aproximadamente los números de colores requeridos.

Véase también

Enlaces externos

Referencia

  1. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Octree — Left: Recursive subdivision of a cube into octants. Right: The corresponding octree. An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by… …   Wikipedia

  • Octree — Des nœuds d octree dépeints en tant que division d un espace de couleur. Un octree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu à huit enfants. Les octrees sont le plus souvent utilisés pour partitionner …   Wikipédia en Français

  • Octree — Ein Octree (von lat. octo „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • octree — noun A treelike data structure each of whose nodes has up to eight children, most often used to partition a three dimensional space by recursively subdividing it …   Wiktionary

  • Sparse Voxel Octree — Построение воксельного октодерева Sparse Voxel Octree (SVO, рус. Разреженное воксельное октоде …   Википедия

  • OLI — octree level index …   Medical dictionary

  • OLI — • octree level index …   Dictionary of medical acronyms & abbreviations

  • Oktalbaum — Ein Octree (von lat. oct „acht“, und engl. tree „Baum“) ist eine Datenstruktur der Informatik. Ein Octree ist ein gewurzelter Baum, dessen Knoten jeweils entweder acht direkte Nachfolger oder gar keine Nachfolger haben. Octrees werden… …   Deutsch Wikipedia

  • Октодерево — Слева: Рекурсивное разделение куба на октанты. Справа: Соответствующее октодерево …   Википедия

  • Level set (data structures) — In computer science a level set data structure is designed to represent discretely sampled dynamic level sets functions.A common use of this form of data structure is in efficient image rendering.Chronological developmentsThe powerful level set… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.