Conjunto de niveles (estructuras de datos)

En ciencias de la computación, 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 se puede utilizar 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} matriz densa de valores de dimensión d , da como resultado una complejidad de tiempo y almacenamiento de , donde es la resolución de la sección transversal de las extensiones espaciales 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 rodeaban inmediatamente la interfaz, reduciendo así la complejidad temporal en tres dimensiones a para la mayoría de las operaciones. Se requerían actualizaciones periódicas de la estructura de banda estrecha para reconstruir la lista de vóxeles activos, lo que implicaba una operación en la que se accedía a los vóxeles de todo el volumen. La complejidad de almacenamiento para este esquema de banda estrecha seguía siendo Las construcciones diferenciales sobre el borde del dominio de banda estrecha requieren una interpolación cuidadosa y esquemas de alteración del dominio para estabilizar la solución. ^[3] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{3}).}$

Campo disperso

Esta vez, la complejidad se eliminó con 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 una sobrecarga significativa. Si bien el método de conjunto de niveles de campo disperso es consistentemente eficiente en el tiempo, 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. Una cuadrícula gruesa de tamaño almacena entonces punteros solo a aquellos bloques que intersecan 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 cuadrículas densas. ${\displaystyle n^{3}}$ ${\displaystyle m^{3}}$ ${\displaystyle (n/m)^{3}}$ ${\displaystyle O\left((nm)3+m^{3}n^{2}\right)}$

Octárbol

El método de conjunto de niveles de octree , introducido por Strain en 1999 ^[7] y refinado por Losasso, Gibou y Fedkiw, ^[8] y más recientemente por Min y Gibou ^[9] utiliza un árbol de cubos anidados de los cuales los nodos de hoja contienen valores de distancia con signo. Los conjuntos de niveles de octree actualmente 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 las estructuras de datos de octree es que se pueden resolver las ecuaciones diferenciales parciales asociadas con los problemas típicos de contorno libre 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).}$

Codificación de longitud de ejecución

El método de conjunto de niveles de codificación por longitud de ejecución (RLE), introducido en 2004, ^[11] aplica el esquema RLE para comprimir regiones alejadas de la banda estrecha a solo su representación de signo mientras se almacena con total precisión la banda estrecha. El recorrido secuencial de la banda estrecha es óptimo y la eficiencia de almacenamiento se mejora aún más con respecto al conjunto de niveles de octree. 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 una eficiencia adicional al aplicar el esquema RLE de manera recursiva dimensional, una técnica introducida por DT-Grid, un proyecto similar de Nielsen y Museth. ^[12] ${\displaystyle O(\log r)}$

Conjunto de nivel local 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 el método Narrow Band Level-Set, pero también solo almacena los datos en esa misma banda. Se utiliza una estructura de datos de tabla hash, que proporciona un 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 árbol cuádruple. Encuentran que ${\displaystyle O(1)}$

Tal como están las cosas, [...] una estructura de datos de árbol cuaternario parece más adaptada que la estructura de datos de tabla hash para algoritmos de conjunto de niveles.

Se enumeran tres razones principales para una peor eficiencia:

1. Para obtener resultados precisos, se requiere una banda bastante grande cerca de la interfaz, que contrarreste la ausencia de nodos de la red lejos de la interfaz;
2. Los resultados se deterioran mediante 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

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

Referencias

1. Osher, S. y Sethian, JA 1988. "Frentes que se propagan con velocidad dependiente de la curvatura: algoritmos basados ​​en formulaciones de Hamilton-Jacobi". Journal of Computation Physics 79:12–49.
2. Adalsteinsson, D. y Sethian, JA 1995. "Un método de conjunto de niveles rápido para propagar interfaces". Journal of Computational Physics . 118(2)269–277.
3. Adalsteinsson, D; Sethian, J (1994). "Un método de conjunto de niveles rápido para propagar interfaces". Journal of Computational Physics . 118 (2): 269. Bibcode :1995JCoPh.118..269A. CiteSeerX  10.1.1.46.1716 . doi :10.1006/jcph.1995.1098.
4. Whitaker, RT 1998. "Un enfoque de conjunto de niveles para la reconstrucción 3D a partir de datos de rango". Revista Internacional de Visión por Computador . 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 (tesis)." Universidad de Stanford , Stanford, California.
7. Strain, J. 1999. "Métodos de árbol para mover interfaces". Journal of Computational Physics . 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. ACM Transactions on Graphics . 23(3)457–462.
9. Min, C. y Gibou, F. 2007. Un método de conjunto de niveles preciso de segundo orden en cuadrículas cartesianas adaptativas no graduadas. Journal of Computational Physics . 225(1)300–321.
10. Gibou, Frederic. "Frederic Gibou - Investigación". Departamento de Ingeniería de la 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árquico: una representación de superficie deformable compacta y versátil". ACM Transactions on Graphics . 25(1).
12. Nielsen, MB y Museth K. 2006. "Cuadrícula tubular dinámica: una estructura de datos eficiente y algoritmos para conjuntos de niveles de alta resolución". Journal of Scientific Computing . 26(1) 1–39.
13. Eyiyurekli, M. y Breen, D. 2011. "Estructuras de datos para edición interactiva de superficies de conjuntos de niveles de alta resolución", Proc. Graphics Interface, págs. 95-102.
14. Brun, E., Guittet, A. y Gibou, F. 2012. "Un método de conjunto de niveles locales que utiliza una estructura de datos de tabla hash". Journal of Computational Physics . 231(6)2528-2536.
15. Corbett, R. 2005. "Conjuntos de niveles basados ​​en puntos y progreso hacia conjuntos de niveles de partículas no organizadas (tesis)." Universidad de Columbia Británica , Canadá .