Level set (data structures)
Encyclopedia
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
. The underlying method constructs a signed distance field
that extends from the boundary, and can be used to solve the motion of the boundary in this field.
is due to Osher
and Sethian
1988 . However, the straightforward implementation via a dense d-dimensional array of values, results in both time and storage complexity of
, where 
is the cross sectional resolution of the spatial extents of the domain and 
is the number of spatial dimensions of the domain.
s immediately surrounding the interface, thus reducing the time complexity in three dimensions to
for most operations. Periodic updates of the narrowband structure, to rebuild the list of active voxels, were required which entailed an 
operation in which voxels over the entire volume were accessed. The storage complexity for this narrowband scheme was still 
Differential constructions over the narrow band domain edge require careful interpolation and domain alteration schemes to stabilise the solution.
time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998 . 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 
efficient in time, 
storage space is still required by the sparse field level set method. See for implementation details.
into small cubic blocks of 
voxels each. A coarse grid of size 
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 
, but retains the constant time access inherent to dense grids.
level set method, introduced by Strain in 1999 and refined by Losasso , 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,
and relatively efficient in terms of access queries, 
(RLE) level set method, introduced in 2004 , 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
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 .
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
a level set
Level set
In mathematics, a level set of a real-valued function f of n variables is a set of the formthat is, a set where the function takes on a given constant value c....
data structure
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.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
is designed to represent discretely sampled
Sampling (statistics)
In statistics and survey methodology, sampling is concerned with the selection of a subset of individuals from within a population to estimate characteristics of the whole population....
dynamic level sets functions.
A common use of this form of data structure is in efficient image rendering
Rendering (computer graphics)
Rendering is the process of generating an image from a model , by means of computer programs. A scene file contains objects in a strictly defined language or data structure; it would contain geometry, viewpoint, texture, lighting, and shading information as a description of the virtual scene...
. The underlying method constructs a signed distance field
Distance transform
A distance transform, also known as distance map or distance field, is a derived representation of a digital image. The choice of the term depends on the point of view on the object in question: whether the initial image is transformed into another representation, or it is simply endowed with an...
that extends from the boundary, and can be used to solve the motion of the boundary in this field.
Chronological developments
The powerful level set methodLevel set method
The level set method 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 Cartesian grid without having to parameterize these objects...
is due to Osher
Stanley Osher
Stanley Osher is an American mathematician, known for his many contributions in shock capturing, level set methods, and PDE-based methods in computer vision and image processing...
and Sethian
James Sethian
James Albert Sethian is a professor of mathematics at the University of California, Berkeley, and the head of the Mathematics Group at the United States Department of Energy's Lawrence Berkeley National Laboratory....
1988 . However, the straightforward implementation via a dense d-dimensional array of values, results in both time and storage complexity of
, where is the cross sectional resolution of the spatial extents of the domain and is the number of spatial dimensions of the domain.Narrow band
The narrow band level set method, introduced in 1995 by Adalsteinsson and Sethian , restricted most computations to a thin band of active voxelVoxel
A voxel is a volume element, representing a value on a regular grid in three dimensional space. This is analogous to a pixel, which represents 2D image data in a bitmap...
s immediately surrounding the interface, thus reducing the time complexity in three dimensions to
for most operations. Periodic updates of the narrowband structure, to rebuild the list of active voxels, were required which entailed an operation in which voxels over the entire volume were accessed. The storage complexity for this narrowband scheme was still Differential constructions over the narrow band domain edge require careful interpolation and domain alteration schemes to stabilise the solution.Sparse field
This time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998 . 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 efficient in time, storage space is still required by the sparse field level set method. See for implementation details.Sparse block grid
The sparse block grid method, introduced by Bridson in 2003 , divides the entire bounding volume of size into small cubic blocks of voxels each. A coarse grid of size 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 , but retains the constant time access inherent to dense grids.Octree
The octreeOctree
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 recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
level set method, introduced by Strain in 1999 and refined by Losasso , 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,
and relatively efficient in terms of access queries, Run-length encoded
The run-length encodingRun-length encoding
Run-length encoding is a very simple form of data compression in which runs of data are stored as a single data value and count, rather than as the original run...
(RLE) level set method, introduced in 2004 , 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
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 .Point-based
Corbett in 2005 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 squaresMoving least squares
Moving least squares is a method of reconstructing continuous functions from a set of unorganized point samples via the calculation of a weighted least squares measure biased towards the region around the point at which the reconstructed value is requested....
.