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 developments

The powerful level set method is due to Osher and Sethian 1988 Osher, S. & Sethian, J. A. 1988. "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobiformulations". "Journal of Computation Physics" 79:12–49.] . However, the straightforward implementation via a dense d-dimensional array of values, results in both time and storage complexity of $O\left(n^d\right)$, where $n$ is the cross sectional resolution of the spatial extents of the domain and $d$ is the number of spatial dimensions of the domain.

Narrow band

The narrow band level set method, introduced in 1995 by Adalsteinsson and Sethian Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." "Journal of Computational Physics". 118(2)269–277.] , restricted most computations to a thin band of active voxels immediately surrounding the interface, thus reducing the time complexity in three dimensions to $O\left(n^2\right)$ for most operations. Periodic updates of the narrowband structure, to rebuild the list of active voxels, were required which entailed an $O\left(n^3\right)$ operation in which voxels over the entire volume were accessed. The storage complexity for this narrowband scheme was still $O\left(n^3\right).$

parse field

This $O\left(n^3\right)$ time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998 Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." "International Journal of Computer Vision." 29(3)203–231.] . The sparse field level set method employs a set of linked lists to track the active voxels around the interface. This allows incremental extension of the active region as needed without incurring any significant overhead. While consistently $O\left(n^2\right)$ efficient in time, $O\left(n^3\right)$ storage space is still required by the sparse field level set method.

parse block grid

The sparse block grid method, introduced by Bridson in 2003 Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." Stanford University, Stanford, California.] , divides the entire bounding volume of size $n^3$ into small cubic blocks of $m^3$ voxels each. A coarse grid of size $\left(n/m\right)^3$ then stores pointers only to those blocks that intersect the narrow band of the level set. Block allocation and deallocation occur as the surface propagates to accommodate to the deformations. This method has a suboptimal storage complexity of $Oleft\left(\left(nm\right)3 + m^3n^2 ight\right)$, but retains the constant time access inherent to dense grids.

Octree

The octree level set method, introduced by Strain in 1999 Strain, J. 1999. "Tree methods for moving interfaces." "Journal of Computational Physics". 151(2)616–648.] and refined by Losasso Losasso, F., Gibou, F., & Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Transactions on Graphics. 23(3)457–462.] , uses a tree of nested cubes of which the leaf nodes contain signed distance values. Octree level sets currently require uniform refinement along the interface (i.e. the narrow band) in order to obtain sufficient precision. This representation is efficient in terms of storage, $O\left(n^2\right),$ and relatively efficient in terms of access queries, $O\left(log, n\right).$

Run-length encoded

The run-length encoding (RLE) level set method, introduced in 2004 Houston, B., Nielsen, M., Batty, C., Nilsson, O. & K. Museth. 2006. "Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation." "ACM Transactions on Graphics". 25(1).] , applies the RLE scheme to compress regions away from the narrow band to just their sign representation while storing with full precision the narrow band. The sequential traversal of the narrow band is optimal and storage efficiency is further improved over the octree level set. The addition of an acceleration lookup table allows for fast $O\left(log r\right)$ random access, where r is the number of runs per cross section. Additional efficiency is gained by applying the RLE scheme in a dimensional recursive fashion, a technique introduced by Nielsen's similar DT-Grid Nielsen, M. B. & Museth K. 2006. "Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets." "Journal of Scientific Computing". 26(1) 1–39.] .

Point-based

::"Please improve this section"Corbett in 2005 Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." University of British Columbia, Canada.] introduced the point-based level set method. Instead of using a uniform sampling of the level set, the continuous level set function is reconstructed from a set of unorganized point samples via moving least squares.

References

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Level set — In mathematics, a level set of a real valued function f of n variables is a set of the form: { ( x 1,..., x n ) | f ( x 1,..., x n ) = c }where c is a constant. That is, it is the set where the function takes on a given constant value. For… …   Wikipedia

• Level set method — The level set method (sometimes abbreviated as LSM) is a numerical technique for tracking interfaces and shapes. The advantage of the level set method is that one can perform numerical computations involving curves and surfaces on a fixed… …   Wikipedia

• List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

• Data structure alignment — is the way data is arranged and accessed in computer memory. It consists of two separate but related issues: data alignment and data structure padding. When a modern computer reads from or writes to a memory address, it will do this in word sized …   Wikipedia

• Data-centric programming language — defines a category of programming languages where the primary function is the management and manipulation of data. A data centric programming language includes built in processing primitives for accessing data stored in sets, tables, lists, and… …   Wikipedia

• Data model — Overview of data modeling context: A data model provides the details of information to be stored, and is of primary use when the final product is the generation of computer software code for an application or the preparation of a functional… …   Wikipedia

• Data structure — In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2] Different kinds of data structures are suited to different kinds of applications, and some are highly …   Wikipedia

• Data mining — Not to be confused with analytics, information extraction, or data analysis. Data mining (the analysis step of the knowledge discovery in databases process,[1] or KDD), a relatively young and interdisciplinary field of computer science[2][3] is… …   Wikipedia

• Data type — For other uses, see Data type (disambiguation). In computer programming, a data type is a classification identifying one of various types of data, such as floating point, integer, or Boolean, that determines the possible values for that type; the …   Wikipedia

• Data modeling — The data modeling process. The figure illustrates the way data models are developed and used today. A conceptual data model is developed based on the data requirements for the application that is being developed, perhaps in the context of an… …   Wikipedia