Level set (data structures): Difference between revisions

Revision as of 05:34, 22 August 2008

Latest revision as of 12:06, 27 June 2025

(40 intermediate revisions by 27 users not shown)

Line 1:

{{Short description|Data structure used in image rendering}}

In [[computer science]] a [[level set]] [[data structure]] is designed to represent discretely [[Sampling (statistics)|sampled]] dynamic level sets functions.

{{Use British English|date=June 2025}}

In [[computer science]], a [['''level set]]''' is a [[data structure]] is designed to represent discretely [[Sampling (statistics)|sampled]] dynamic level sets of functions.

A common use of this form of data structure is in efficient image [[Rendering (computer graphics)|rendering]]. The underlying method constructs a [[distance transform|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]] is due to [[Stanley Osher|Osher]] and [[James Sethian|Sethian]] 1988 .<ref name=Osher>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.</ref>. However, the straightforward implementation via a dense d-dimensional [[array data structure|array]] of values, results in both time and storage complexity of <math>O(n^d)</math>, where <math>n</math> is the cross sectional resolution of the spatial extents of the ___domain and <math>d</math> is the number of spatial dimensions of the ___domain.

The powerful [[level set method]] is due to [[Stanley Osher|Osher]] and [[James Sethian|Sethian]] 1988 <ref name=Osher>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.</ref>. However, the straightforward implementation via a dense d-dimensional [[array]] of values, results in both time and storage complexity of <math>O(n^d)</math>, where <math>n</math> is the cross sectional resolution of the spatial extents of the ___domain and <math>d</math> is the number of spatial dimensions of the ___domain.

===Narrow band===

The narrow band level set method, introduced in 1995 by Adalsteinsson and Sethian ,<ref name="Adalsteinsson">Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." ''[[Journal of Computational Physics]]''. 118(2)269–277.</ref>, restricted most computations to a thin band of active voxels[[voxel]]s immediately surrounding the interface, thus reducing the time complexity in three dimensions to <math>O(n^2)</math> for most operations. Periodic updates of the narrowband structure, to rebuild the list of active voxels, were required which entailed an <math>O(n^3)</math> operation in which voxels over the entire volume were accessed. The storage complexity for this narrowband scheme was still <math>O(n^3).</math> Differential constructions over the narrow band ___domain edge require careful interpolation and ___domain alteration schemes to stabilise the solution.<ref>{{cite journal|title=A fast level set Method for Propagating Interfaces|author1=Adalsteinsson, D |author2=Sethian, J|journal=Journal of Computational Physics |volume=118 |issue=2 |pages=269 |year=1994|citeseerx=10.1.1.46.1716 |bibcode=1995JCoPh.118..269A |doi=10.1006/jcph.1995.1098 }}</ref>

===Sparse field===

This <math>O(n^3)</math> time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998 .<ref name=Whitaker>Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." ''[[International Journal of Computer Vision]].'' 29(3)203–231.</ref>. 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 <math>O(n^2)</math> efficient in time, <math>O(n^3)</math> storage space is still required by the sparse field level set method. See<ref name=Lankton>S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/></ref> for implementation details.

This <math>O(n^3)</math> time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998 <ref name=Whitaker>Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." ''[[International Journal of Computer Vision]].'' 29(3)203–231.</ref>. 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 <math>O(n^2)</math> efficient in time, <math>O(n^3)</math> storage space is still required by the sparse field level set method.

===Sparse block grid===

The sparse block grid method, introduced by Bridson in 2003 ,<ref name=Bridson>Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." [[Stanford University]], Stanford, California.</ref>, divides the entire [[bounding volume]] of size <math>n^3</math> into small cubic blocks of <math>m^3</math> voxels each. A coarse grid of size <math>(n/m

)^3</math> 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 <math>O\left((nm)3 + m^3n^2\right)</math>, but retains the constant time access inherent to dense grids.

===Sparse hash grid===

Bridson also suggests in his dissertation replacing the coarse grid with a hashtable, obtaining optimal storage complexity while retaining constant time access and the same cache friendliness of the small blocks. However, he does not report any experiments with this structure.

===Octree===

The [[octree]] level set method, introduced by Strain in 1999 <ref name=Strain>Strain, J. 1999. "Tree methods for moving interfaces." ''[[Journal of Computational Physics]]''. 151(2)616–648.</ref> and refined by Losasso, Gibou and Fedkiw,<ref name=Losasso>Losasso, F., Gibou, F., & Fedkiw, R. 2004. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.459.1489&rep=rep1&type=pdf Simulating water and smoke with an octree data structure]. [[ACM Transactions on Graphics]]. 23(3)457–462.</ref> and more recently by Min and Gibou<ref name=MinGibou>Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. [[Journal of Computational Physics]]. 225(1)300–321.</ref> 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, <math>O(n^2),</math> and relatively efficient in terms of access queries, <math>O(\log\, n).</math> 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<ref name=CASL>{{Cite web |last=Gibou |first=Frederic |title=Frederic Gibou - Research |url=https://engineering.ucsb.edu/~fgibou/Research.html |url-status=dead |archive-url=https://web.archive.org/web/20170203080700/https://engineering.ucsb.edu/~fgibou/Research.html |archive-date=2017-02-03 |website=UCSB Engineering Department}}</ref> has developed this line of work in computational materials, computational fluid dynamics, electrokinetics, image-guided surgery and controls.

The [[octree]] level set method, introduced by Strain in 1999 <ref name=Strain>Strain, J. 1999. "Tree methods for moving interfaces." ''[[Journal of Computational Physics]]''. 151(2)616–648.</ref> and refined by Losasso <ref name=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.</ref>, 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, <math>O(n^2),</math> and relatively efficient in terms of access queries, <math>O(\log\, n).</math>

===Run-length encoded===

The [[run-length encoding]] (RLE) level set method, introduced in 2004 ,<ref name=Houston2004>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).</ref>, 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 <math>O(\log r)</math> 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 .<ref name="Nielsen">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.</ref>.

===Hash Table Local Level Set===

The [[run-length encoding]] (RLE) level set method, introduced in 2004 <ref name=Houston2004>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).</ref>, 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 <math>O(log r)</math> 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 <ref name=Nielsen>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.</ref>.

The Hash Table Local Level Set method was introduced in 2011 by Eyiyurekli and Breen <ref name=Eyiyurekli>Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.</ref> and extended in 2012 by Brun, Guittet, and Gibou,<ref name=BrunGuittetGibou>Brun, E., Guittet, A. & Gibou, F. 2012. "A local level-set method using a hash table data structure." ''[[Journal of Computational Physics]]''. 231(6)2528-2536.</ref> 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 <math>O(1)</math> 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 {{blockquote|as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms.}} 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===

{{Expand section|date=December 2009}}

Corbett in 2005 <ref name=Corbett>Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." [[University of British Columbia]], [[Canada]].</ref> 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]].

::''Please improve this section''

Corbett in 2005 <ref name=Corbett>Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." [[University of British Columbia]], [[Canada]].</ref> 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==

<references />

{{DEFAULTSORT:Level Set (Data Structures)}}

[[Category:Computer graphics data structures]]

[[Category:Image processing]]