In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
a
level set
In mathematics, a level set of a real-valued function of real variables is a set where the function takes on a given constant value , that is:
: L_c(f) = \left\~,
When the number of independent variables is two, a level set is calle ...
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
is designed to represent discretely
sampled
Sample or samples may refer to:
Base meaning
* Sample (statistics), a subset of a population – complete data set
* Sample (signal), a digital discrete sample of a continuous analog signal
* Sample (material), a specimen or small quantity of so ...
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.
Chronological developments
The powerful
level-set method
Level-set methods (LSM) are a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. The advantage of the level-set model is that one can perform numerical computations involving curves and surfaces on a ...
is due to
Osher Osher may refer to:
* Osher (name)
*Osher Lifelong Learning Institutes
Osher Lifelong Learning Institutes (OLLI) offer noncredit courses with no assignments or grades to adults over age 50. Since 2001 philanthropist Bernard Osher has made grants ...
and
Sethian
The Sethians were one of the main currents of Gnosticism during the 2nd and 3rd century CE, along with Valentinianism and Basilideanism. According to John D. Turner, it originated in the 2nd century CE as a fusion of two distinct Hellenistic ...
1988.
[Osher, S. & Sethian, J. A. 1988. "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi
formulations". ''Journal of Computation Physics'' 79:12–49.] However, the straightforward implementation via a dense d-dimensional
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
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,
[Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." '']Journal of Computational Physics
The ''Journal of Computational Physics'' is a bimonthly scientific journal covering computational physics that was established in 1966 and is published by Elsevier. As of 2015, its editor-in-chief is Rémi Abgrall (University of Zurich). According ...
''. 118(2)269–277. restricted most computations to a thin band of active
voxel
In 3D computer graphics, a voxel represents a value on a regular grid in three-dimensional space. As with pixels in a 2D bitmap, voxels themselves do not typically have their position (i.e. coordinates) explicitly encoded with their values. Ins ...
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.
[Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." '']International Journal of Computer Vision
The ''International Journal of Computer Vision'' (IJCV) is a journal published by Springer. The senior editor-in-chief is Jean Ponce, and the editors-in-chief are Jiri Matas, Yasuyuki Matsushita, and Svetlana Lazebnik
Svetlana Lazebnik (born 197 ...
.'' 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
efficient in time,
storage space is still required by the sparse field level set method. See
[S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 ] for implementation details.
Sparse block grid
The sparse block grid method, introduced by Bridson in 2003,
[Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." ]Stanford University
Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...
, Stanford, California. divides the entire
bounding volume
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operatio ...
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
octree
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 ana ...
level set method, introduced by Strain in 1999
[Strain, J. 1999. "Tree methods for moving interfaces." '']Journal of Computational Physics
The ''Journal of Computational Physics'' is a bimonthly scientific journal covering computational physics that was established in 1966 and is published by Elsevier. As of 2015, its editor-in-chief is Rémi Abgrall (University of Zurich). According ...
''. 151(2)616–648. and refined by Losasso, Gibou and Fedkiw,
[Losasso, F., Gibou, F., & Fedkiw, R. 2004]
Simulating water and smoke with an octree data structure
ACM Transactions on Graphics
''ACM Transactions on Graphics'' (TOG) is a bimonthly peer-reviewed scientific journal that covers the field of computer graphics. It was established in 1982 and is published by the Association for Computing Machinery. TOG publishes two special ...
. 23(3)457–462. and more recently by Min and Gibou
[Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. ]Journal of Computational Physics
The ''Journal of Computational Physics'' is a bimonthly scientific journal covering computational physics that was established in 1966 and is published by Elsevier. As of 2015, its editor-in-chief is Rémi Abgrall (University of Zurich). According ...
. 225(1)300–321. 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,
An advantage of the level method on octree data structures is that one can solve the partial differential equations associated with typical free boundary problems that use the level set method. The CASL research group
[http://www1.engr.ucsb.edu/~fgibou/Research.html] has developed this line of work in computational materials, computational fluid dynamics, electrokinetics, image guided surgery and controls.
Run-length encoded
The
run-length encoding
Run-length encoding (RLE) is a form of lossless data compression in which ''runs'' of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original ...
(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
''ACM Transactions on Graphics'' (TOG) is a bimonthly peer-reviewed scientific journal that covers the field of computer graphics. It was established in 1982 and is published by the Association for Computing Machinery. TOG publishes two special ...
''. 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
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 & Museth'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.]
Hash Table Local Level Set
The Hash Table Local Level Set method, introduced in 2011 by Eyiyurekli and Breen
[Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.] and extended in 2012 by Brun, Guittet and Gibou,
[Brun, E., Guittet, A. & Gibou, F. 2012. "A local level-set method using a hash table data structure." '']Journal of Computational Physics
The ''Journal of Computational Physics'' is a bimonthly scientific journal covering computational physics that was established in 1966 and is published by Elsevier. As of 2015, its editor-in-chief is Rémi Abgrall (University of Zurich). According ...
''. 231(6)2528-2536. only computes the level set data in a band around the interface, as in the Narrow Band Level-Set Method, but also only stores the data in that same band. A hash table data structure is used, which provides an
access to the data. However, Brun et al. conclude that their method, while being easier to implement, performs worse than a quadtree implementation. They find that Three main reasons for worse efficiency are listed:
# to obtain accurate results, a rather large band is required close to the interface, which counterbalances the absence of grid nodes far from the interface;
# the performances are deteriorated by extrapolation procedures on the outer edges of the local grid and
# the width of the band restricts the time step and slows down the method.
Point-based
Corbett in 2005
[Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." ]University of British Columbia
The University of British Columbia (UBC) is a public university, public research university with campuses near Vancouver and in Kelowna, British Columbia. Established in 1908, it is British Columbia's oldest university. The university ranks a ...
, Canada
Canada is a country in North America. Its ten provinces and three territories extend from the Atlantic Ocean to the Pacific Ocean and northward into the Arctic Ocean, covering over , making it the world's second-largest country by tot ...
. 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 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 ...
.
References
{{DEFAULTSORT:Level Set (Data Structures)
Computer graphics data structures
Image processing
Numerical analysis