En informática, una estructura de datos de conjuntos de niveles está diseñada para representar funciones de conjuntos de niveles dinámicos muestreadas 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 densa matriz de valores d-dimensional , da como resultado la complejidad de tiempo y almacenamiento de, dónde 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.
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 del tiempo en tres dimensiones parapara la mayoría de las operaciones. Se requerían actualizaciones periódicas de la estructura de banda estrecha, para reconstruir la lista de voxels activos, lo que implicaba unoperación en la que se accedió a vóxeles de todo el volumen. La complejidad de almacenamiento para este esquema de banda estrecha todavía eraLas construcciones diferenciales sobre el borde del dominio de banda estrecha requieren esquemas cuidadosos de interpolación y alteración del dominio para estabilizar la solución. [3]
Campo disperso
Esto La complejidad del tiempo se eliminó en el método de conjunto de niveles de "campo disperso" aproximado 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 la extensión incremental de la región activa según sea necesario sin incurrir en gastos generales significativos. Mientras consistentemente eficiente en el tiempo, El método de conjunto de nivel de campo disperso aún requiere espacio de almacenamiento. Consulte [5] para obtener detalles sobre la implementación.
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 gruesa cuadrícula de tamañoluego almacena punteros solo para aquellos bloques que se cruzan con la banda estrecha del conjunto de niveles. La asignación y desasignación de bloques ocurren 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 de tiempo constante inherente a las rejillas densas.
Octree
El método de conjunto de niveles de octárbol , 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 hojas contienen una distancia con signo. valores. Los conjuntos de niveles de octárbol requieren actualmente un refinamiento uniforme a lo largo de la interfaz (es decir, la banda estrecha) para obtener una precisión suficiente. 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 octárbol 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 imagen y controles.
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 lejos de la banda estrecha a solo su representación de signo mientras 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 nivel de octárbol establecido. La adición de una tabla de búsqueda de aceleración permite una rápidaacceso aleatorio, donde r es el número de corridas por sección transversal. Se obtiene una eficiencia adicional aplicando el esquema RLE de forma recursiva dimensional, una técnica introducida por DT-Grid similar de Nielsen & Museth. [12]
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 Narrow Band. Método de ajuste de nivel, pero también solo almacena los datos en esa misma banda. Se utiliza una estructura de datos de tabla hash, que proporciona unaacceso a los datos. Sin embargo, Brun et al. concluyen que su método, aunque es más fácil de implementar, funciona peor que una implementación de cuatro árboles. Ellos encuentran que
tal como está, una estructura de [...] datos de cuatro árboles parece más adaptada que la estructura de datos de la tabla hash para los algoritmos de niveles.
Se enumeran tres razones principales para una peor eficiencia:
- para obtener resultados precisos, se requiere una banda bastante grande cerca de la interfaz, lo que contrarresta la ausencia de nodos de red lejos de la interfaz;
- los rendimientos se deterioran por los procedimientos de extrapolación en los bordes exteriores de la cuadrícula local y
- 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 conjunto 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 móviles .
Referencias
- ^ Osher, S. & 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.
- ^ Adalsteinsson, D. y Sethian, JA 1995. "Un método de establecimiento de nivel rápido para propagar interfaces". Revista de Física Computacional . 118 (2) 269–277.
- ↑ Adalsteinsson, D; Sethian, J (1994). "Un método de configuración de nivel rápido para la propagación de 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 .
- ^ 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.
- ^ 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/ >
- ^ Bridson, R. 2003. "Aspectos computacionales de superficies dinámicas (disertación)". Universidad de Stanford , Stanford, California.
- ^ Strain, J. 1999. "Métodos de árbol para mover interfaces". Revista de Física Computacional . 151 (2) 616–648.
- ^ Losasso, F., Gibou, F. y Fedkiw, R. 2004. Simulación de agua y humo con una estructura de datos de octárbol . Transacciones ACM en gráficos . 23 (3) 457–462.
- ^ Min, C. y Gibou, F. 2007. Un método de conjunto de niveles precisos de segundo orden en cuadrículas cartesianas adaptativas no graduadas. Revista de Física Computacional . 225 (1) 300–321.
- ^ http://www1.engr.ucsb.edu/~fgibou/Research.html
- ^ Houston, B., Nielsen, M., Batty, C., Nilsson, O. y K. Museth. 2006. "Conjunto jerárquico de niveles RLE: una representación de superficie deformable compacta y versátil". Transacciones ACM en gráficos . 25 (1).
- ^ Nielsen, MB y Museth K. 2006. "Rejilla tubular dinámica: una estructura de datos eficiente y algoritmos para conjuntos de niveles de alta resolución". Revista de Computación Científica . 26 (1) 1–39.
- ^ Eyiyurekli, M. & Breen, D. 2011. "Estructuras de datos para la edición interactiva de superficies de alta resolución," Proc. Interfaz gráfica. págs. 95-102.
- ^ 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". Revista de Física Computacional . 231 (6) 2528-2536.
- ^ 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á .