Conjunto de niveles (estructuras de datos)

En informática, una estructura de datos de conjunto de niveles está diseñada para representar funciones de conjuntos de niveles dinámicos muestreados discretamente.

Un uso común de esta forma de estructura de datos es la representación eficiente de imágenes . El método subyacente construye un campo de distancia con signo que se extiende desde el límite y puede usarse para resolver el movimiento del límite en este campo.

Desarrollos cronológicos

El poderoso método de conjunto de niveles se debe a Osher y Sethian 1988. ^{[1] Sin embargo, la implementación sencilla a través de una densa} matriz d-dimensional de valores, da como resultado una complejidad tanto en el tiempo como en el almacenamiento de , donde está la resolución de la sección transversal del espacio. extensiones del dominio y es el número de dimensiones espaciales del dominio. ${\displaystyle O(n^{d})}$ ${\displaystyle n}$ ${\displaystyle d}$

Banda estrecha

El método de conjunto de niveles de banda estrecha, introducido en 1995 por Adalsteinsson y Sethian, ^[2] restringió la mayoría de los cálculos a una banda delgada de vóxeles activos que rodean inmediatamente la interfaz, reduciendo así la complejidad temporal en tres dimensiones para la mayoría de las operaciones. Se requirieron actualizaciones periódicas de la estructura de banda estrecha para reconstruir la lista de vóxeles activos, lo que implicó una operación en la que se accedía a los vóxeles de todo el volumen. La complejidad del almacenamiento para este esquema de banda estrecha todavía era. Las construcciones diferenciales sobre el borde del dominio de banda estrecha requieren esquemas cuidadosos de interpolación y alteración de dominio para estabilizar la solución. ^[3] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3}).}$

campo escaso

Esta complejidad temporal se eliminó en el método aproximado de conjunto de niveles de "campo disperso" introducido por Whitaker en 1998. ^[4] El método de conjunto de niveles de campo disperso emplea un conjunto de listas enlazadas para rastrear los vóxeles activos alrededor de la interfaz. Esto permite una extensión incremental de la región activa según sea necesario sin incurrir en gastos generales significativos. Si bien es consistentemente eficiente en el tiempo, el método de conjunto de niveles de campo disperso aún requiere espacio de almacenamiento. Consulte ^[5] para obtener detalles de implementación. ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$

Cuadrícula de bloques dispersos

El método de cuadrícula de bloques dispersos, introducido por Bridson en 2003, ^[6] divide todo el volumen delimitador de tamaño en pequeños bloques cúbicos de vóxeles cada uno. Luego , una cuadrícula de tamaño aproximado almacena punteros solo a aquellos bloques que intersectan la banda estrecha del conjunto de niveles. La asignación y desasignación de bloques se produce a medida que la superficie se propaga para adaptarse a las deformaciones. Este método tiene una complejidad de almacenamiento subóptima de , pero conserva el acceso en tiempo constante inherente a las redes densas. ${\displaystyle n^{3}}$ ${\displaystyle m^{3}}$ ${\displaystyle (n/m)^{3}}$ ${\displaystyle O\left((nm)3+m^{3}n^{2}\right)}$

octree

El método de conjunto de niveles de octree , introducido por Strain en 1999 ^[7] y perfeccionado por Losasso, Gibou y Fedkiw, ^[8] y más recientemente por Min y Gibou ^[9] utiliza un árbol de cubos anidados cuyos nodos de hoja contienen distancias con signo. valores. Actualmente, los conjuntos de niveles de octárbol requieren un refinamiento uniforme a lo largo de la interfaz (es decir, la banda estrecha) para obtener suficiente precisión. Esta representación es eficiente en términos de almacenamiento y relativamente eficiente en términos de consultas de acceso. Una ventaja del método de nivel en estructuras de datos de octree es que se pueden resolver las ecuaciones diferenciales parciales asociadas con problemas típicos de límites libres que utilizan el método de conjunto de niveles. El grupo de investigación CASL ^[10] ha desarrollado esta línea de trabajo en materiales computacionales, dinámica de fluidos computacional, electrocinética, cirugía guiada por imágenes y controles. ${\displaystyle O(n^{2}),}$ ${\displaystyle O(\log \,n).}$

Longitud de ejecución codificada

El método de conjunto de niveles de codificación de longitud de ejecución (RLE), introducido en 2004, ^[11] aplica el esquema RLE para comprimir regiones alejadas de la banda estrecha solo a su representación de signos mientras se almacena con total precisión la banda estrecha. El recorrido secuencial de la banda estrecha es óptimo y la eficiencia del almacenamiento se mejora aún más con respecto al nivel de octree establecido. La adición de una tabla de búsqueda de aceleración permite un acceso aleatorio rápido, donde r es el número de ejecuciones por sección transversal. Se obtiene eficiencia adicional aplicando el esquema RLE de forma recursiva dimensional, una técnica introducida por DT-Grid similar de Nielsen & Museth. ^[12] ${\displaystyle O(\log r)}$

Conjunto de niveles locales de tabla hash

El método Hash Table Local Level Set, introducido en 2011 por Eyiyurekli y Breen ^[13] y ampliado en 2012 por Brun, Guittet y Gibou, ^[14] solo calcula los datos del conjunto de niveles en una banda alrededor de la interfaz, como en la Banda Estrecha. Método Level-Set, pero también solo almacena los datos en esa misma banda. Se utiliza una estructura de datos de tabla hash, que proporciona acceso a los datos. Sin embargo, Brun et al. Concluyen que su método, si bien es más fácil de implementar, funciona peor que una implementación de quadtree. ellos encuentran que ${\displaystyle O(1)}$

tal como están las cosas, una estructura de datos de cuatro árboles parece más adaptada que la estructura de datos de tabla hash para algoritmos de conjunto de niveles.

Se enumeran tres razones principales de una peor eficiencia:

1. para obtener resultados precisos, se requiere una banda bastante grande cerca de la interfaz, lo que contrarresta la ausencia de nodos de la red lejos de la interfaz;
2. las prestaciones se deterioran por los procedimientos de extrapolación en los bordes exteriores de la red local y
3. el ancho de la banda restringe el paso de tiempo y ralentiza el método.

Basado en puntos

Corbett en 2005 ^[15] introdujo el método de establecimiento de niveles basado en puntos. En lugar de utilizar un muestreo uniforme del conjunto de niveles, la función de conjunto de niveles continuo se reconstruye a partir de un conjunto de muestras puntuales no organizadas mediante mínimos cuadrados en movimiento .

Referencias

1. Osher, S. & Sethian, JA 1988. "Frentes que se propagan con velocidad dependiente de la curvatura: algoritmos basados ​​en formulaciones de Hamilton-Jacobi". Revista de Física de la Computación 79:12–49.
2. Adalsteinsson, D. & Sethian, JA 1995. "Un método rápido de establecimiento de niveles para propagar interfaces". Revista de Física Computacional . 118(2)269–277.
3. Adalsteinsson, D; Sethian, J (1994). "Un método rápido de establecimiento de niveles para propagar interfaces". Revista de Física Computacional . 118 (2): 269. Código bibliográfico : 1995JCoPh.118..269A. CiteSeerX  10.1.1.46.1716 . doi :10.1006/jcph.1995.1098.
4. Whitaker, RT 1998. "Un enfoque de nivel establecido para la reconstrucción 3D a partir de datos de rango". Revista Internacional de Visión por Computadora . 29(3)203–231.
5. S. Lankton. "Método de campo disperso - Informe técnico". 21 de abril de 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/>
6. Bridson, R. 2003. "Aspectos computacionales de superficies dinámicas (disertación)". Universidad de Stanford , Stanford, California.
7. Strain, J. 1999. "Métodos de árbol para mover interfaces". Revista de Física Computacional . 151(2)616–648.
8. Losasso, F., Gibou, F. y Fedkiw, R. 2004. Simulación de agua y humo con una estructura de datos de octree. Transacciones ACM sobre gráficos . 23(3)457–462.
9. Min, C. y Gibou, F. 2007. Un método de establecimiento de niveles preciso de segundo orden en cuadrículas cartesianas adaptativas no graduadas. Revista de Física Computacional . 225(1)300–321.
10. Gibou, Federico. "Frederic Gibou - Investigación". Departamento de Ingeniería de UCSB . Archivado desde el original el 3 de febrero de 2017.
11. Houston, B., Nielsen, M., Batty, C., Nilsson, O. y K. Museth. 2006. "Conjunto de niveles RLE jerárquicos: una representación de superficie deformable compacta y versátil". Transacciones ACM sobre gráficos . 25(1).
12. Nielsen, MB y Museth K. 2006. "Dynamic Tubular Grid: una estructura de datos y algoritmos eficientes para conjuntos de niveles de alta resolución". Revista de Computación Científica . 26(1) 1–39.
13. Eyiyurekli, M. & Breen, D. 2011. "Estructuras de datos para la edición interactiva de superficies de niveles de alta resolución", Proc. Interfaz gráfica. págs. 95-102.
14. Brun, E., Guittet, A. & Gibou, F. 2012. "Un método de conjunto de niveles local que utiliza una estructura de datos de tabla hash". Revista de Física Computacional . 231(6)2528-2536.
15. Corbett, R. 2005. "Conjuntos de niveles basados ​​en puntos y progreso hacia conjuntos de niveles de partículas no organizados (tesis)". Universidad de Columbia Británica , Canadá .