Line integral convolution

Last updated
The Large Magellanic Cloud (LMC), one of the nearest galaxies to our Milky Way. This image was created with LIC Rotation of the Large Magellanic Cloud ESA393163.png
The Large Magellanic Cloud (LMC), one of the nearest galaxies to our Milky Way. This image was created with LIC

In scientific visualization, line integral convolution (LIC) is a method to visualize a vector field, such as fluid motion.

Contents

Features

Convolution

In signal processing this process is known as discrete convolution. [1]

Integration-based method

It is the integration-based method (technique). More precisely it is based on the discrete line integral on uniform grids. Discrete numerical integration is performed along a line (more precisely curve). Line here means field line of vector field.

Global method

Compared to other integration-based techniques that compute field lines of the input vector field, LIC has the advantage that all structural features of the vector field are displayed, without the need to adapt the start and end points of field lines to the specific vector field. In other words, it shows the topology of the vector field.

In user testing, LIC was found to be particularly good for identifying critical points. [2]

other

With the availability of high-performance GPU-based implementations, the former disadvantage of limited interactivity is no longer present.

Texture-based method

LIC takes texture as an input and gives texture ( output). So it is texture synthesis.

History

LIC technique was proposed by Brian Cabral and Leith Casey Leedom. [3]

Algorithm

Informal description

Principle: the pixel values along the field lines are strongly correlated, but orthogonally to them almost uncorrelated. As a result, the field lines stand out visually from the background and become visible.

Intuition:

Intuitively, the flow of a vector field in some domain is visualized by adding a static random pattern of dark and light paint sources. As the flow passes by the sources, each parcel of fluid picks up some of the source color, averaging it with the color it has already acquired in a manner similar to throwing paint in a river. The result is a random striped texture where points along the same streamline tend to have similar color.

Formal mathematical description

Although the input vector field and the result image are discretized, it pays to look at it from a continuous viewpoint. [5] Let be the vector field given in some domain . Although the input vector field is typically discretized, we regard the field as defined in every point of , i.e. we assume an interpolation. Streamlines, or more generally field lines, are tangent to the vector field in each point. They end either at the boundary of or at critical points where . For the sake of simplicity, in the following critical points and boundaries are ignored. A field line , parametrized by arc length , is defined as . Let be the field line that passes through the point for . Then the image gray value at is set to

where is the convolution kernel, is the noise image, and is the length of field line segment that is followed.

has to be computed for each pixel in the LIC image. If carried out naively, this is quite expensive. First, the field lines have to be computed using a numerical method for solving ordinary differential equations, like a Runge–Kutta method, and then for each pixel the convolution along a field line segment has to be calculated.

The output image will normally be colored in some way. Typically some scalar field in is used, like the vector length, to determine the hue, while the gray-scale LIC image determines the brightness of the color.

Different choices of convolution kernels and random noise produce different textures: for example pink noise produces a cloudy pattern where areas of higher flow stand out as smearing, suitable for weather visualization. Further refinements in the convolution can improve the quality of the image. [6]

Description for programmers

Algorithmically, the technique starts by generating in the domain of the vector field a random gray level image at the desired output resolution. Then, for every pixel in this image, the forward and backward streamline of a fixed arc length is calculated. The value assigned to the current pixel is computed by a convolution of a suitable convolution kernel with the gray levels of all the pixels lying on a segment of this streamline. This creates a gray level LIC image.

Problem

Visualize field lines and singularities of a 2D stationary vector field (stream lines of a 2D steady flow)

Input

  • vector field: 2D stationary vector field
  • noise: stationary white noise (scalar field = texture)

Output

result (output image) = final LIC image of input vector field

Steps

constraints

  • false singularities

Versions

Basic

Basic LIC visualization of a flow field. Line integral convolution visualisation.png
Basic LIC visualization of a flow field.

Basic LIC images are grayscale images, without color and animation. While such LIC image conveys the orientation of the field vectors, it does not indicate their direction; for stationary fields, this can be remedied by animation. Basic LIC images do not show the length of the vectors (or the strength of the field).

Color

LIC visualization with color denoting velocity magnitude. Line integral convolution visualisation (color).png
LIC visualization with color denoting velocity magnitude.

The length of the vectors (or the strength of the field) is usually coded in color; alternatively, animation can be used. [3] [5]

Animated version

Illustration on how to animate. Above: Normal Box Filter (average). Middle: Sinusoidal Filter at
t
{\displaystyle t}
. Bottom: Sinusoidal Filter at
t
+
d
t
{\displaystyle t+\delta t} Animated LIC.svg
Illustration on how to animate. Above: Normal Box Filter (average). Middle: Sinusoidal Filter at . Bottom: Sinusoidal Filter at

LIC images can be animated by using a kernel that changes over time. Samples at a constant time from the streamline would still be used, but instead of averaging all pixels in a streamline with a static kernel, a ripple-like kernel constructed from a periodic function multiplied by a Hann function acting as a window (in order to prevent artifacts) is used. The periodic function is then shifted along the period to create an animation.

FLIC

Fast Lic ( FLIC)

The computation can be significantly accelerated by re-using parts of already computed field lines, specializing to a box function as convolution kernel and avoiding redundant computations during convolution. [5] The resulting fast LIC method can be generalized to convolution kernels that are arbitrary polynomials. [7]

OLIC

Oriented Line Integral Convolution (OLIC)

UFLIC

For time-dependent vector fields ( unsteady flow) a variant (UFLIC = Unsteady Flow LIC), has been designed that maintains the coherence of the flow animation. [10]

Parallel versions

Since the computation of a LIC image is expensive but inherently parallel, it has also been parallelized [11] and, with availability of GPU-based implementations, it has become interactive on PCs. Also for UFLIC an interactive GPU-based implementation has been presented. [12]

Multidimensional

Note that domain does not have to be a 2D domain: the method is applicable to higher dimensional domains using multidimensional noise fields. However, the visualization of the higher-dimensional LIC texture is problematic; one way is to use interactive exploration with 2D slices that are manually positioned and rotated. The domain does not have to be flat either; the LIC texture can be computed also for arbitrarily shaped 2D surfaces in 3D space. [13]

Applications

This technique has been applied to a wide range of problems since it first was published in 1993.

Applications:

Implementations

See also

Related Research Articles

Continuum mechanics is a branch of mechanics that deals with the deformation of and transmission of forces through materials modeled as a continuous medium rather than as discrete particles. The French mathematician Augustin-Louis Cauchy was the first to formulate such models in the 19th century.

<span class="mw-page-title-main">Maxwell's equations</span> Equations describing classical electromagnetism

Maxwell's equations, or Maxwell–Heaviside equations, are a set of coupled partial differential equations that, together with the Lorentz force law, form the foundation of classical electromagnetism, classical optics, electric and magnetic circuits. The equations provide a mathematical model for electric, optical, and radio technologies, such as power generation, electric motors, wireless communication, lenses, radar, etc. They describe how electric and magnetic fields are generated by charges, currents, and changes of the fields. The equations are named after the physicist and mathematician James Clerk Maxwell, who, in 1861 and 1862, published an early form of the equations that included the Lorentz force law. Maxwell first used the equations to propose that light is an electromagnetic phenomenon. The modern form of the equations in their most common formulation is credited to Oliver Heaviside.

<span class="mw-page-title-main">Navier–Stokes equations</span> Equations describing the motion of viscous fluid substances

The Navier–Stokes equations are partial differential equations which describe the motion of viscous fluid substances. They were named after French engineer and physicist Claude-Louis Navier and the Irish physicist and mathematician George Gabriel Stokes. They were developed over several decades of progressively building the theories, from 1822 (Navier) to 1842–1850 (Stokes).

<span class="mw-page-title-main">Magnetic flux</span> Surface integral of the magnetic field

In physics, specifically electromagnetism, the magnetic flux through a surface is the surface integral of the normal component of the magnetic field B over that surface. It is usually denoted Φ or ΦB. The SI unit of magnetic flux is the weber, and the CGS unit is the maxwell. Magnetic flux is usually measured with a fluxmeter, which contains measuring coils, and it calculates the magnetic flux from the change of voltage on the coils.

In continuum mechanics, vorticity is a pseudovector field that describes the local spinning motion of a continuum near some point, as would be seen by an observer located at that point and traveling along with the flow. It is an important quantity in the dynamical theory of fluids and provides a convenient framework for understanding a variety of complex flow phenomena, such as the formation and motion of vortex rings.

In fluid dynamics, Stokes' law is an empirical law for the frictional force – also called drag force – exerted on spherical objects with very small Reynolds numbers in a viscous fluid. It was derived by George Gabriel Stokes in 1851 by solving the Stokes flow limit for small Reynolds numbers of the Navier–Stokes equations.

<span class="mw-page-title-main">Stream function</span> Function for incompressible divergence-free flows in two dimensions

In fluid dynamics, two types of stream function are defined:

<span class="mw-page-title-main">Sobel operator</span> Image edge detection algorithm

The Sobel operator, sometimes called the Sobel–Feldman operator or Sobel filter, is used in image processing and computer vision, particularly within edge detection algorithms where it creates an image emphasising edges. It is named after Irwin Sobel and Gary M. Feldman, colleagues at the Stanford Artificial Intelligence Laboratory (SAIL). Sobel and Feldman presented the idea of an "Isotropic 3 × 3 Image Gradient Operator" at a talk at SAIL in 1968. Technically, it is a discrete differentiation operator, computing an approximation of the gradient of the image intensity function. At each point in the image, the result of the Sobel–Feldman operator is either the corresponding gradient vector or the norm of this vector. The Sobel–Feldman operator is based on convolving the image with a small, separable, and integer-valued filter in the horizontal and vertical directions and is therefore relatively inexpensive in terms of computations. On the other hand, the gradient approximation that it produces is relatively crude, in particular for high-frequency variations in the image.

<span class="mw-page-title-main">Radon transform</span> Integral transform

In mathematics, the Radon transform is the integral transform which takes a function f defined on the plane to a function Rf defined on the (two-dimensional) space of lines in the plane, whose value at a particular line is equal to the line integral of the function over that line. The transform was introduced in 1917 by Johann Radon, who also provided a formula for the inverse transform. Radon further included formulas for the transform in three dimensions, in which the integral is taken over planes. It was later generalized to higher-dimensional Euclidean spaces and more broadly in the context of integral geometry. The complex analogue of the Radon transform is known as the Penrose transform. The Radon transform is widely applicable to tomography, the creation of an image from the projection data associated with cross-sectional scans of an object.

<span class="mw-page-title-main">Scientific visualization</span> Interdisciplinary branch of science concerned with presenting scientific data visually

Scientific visualization is an interdisciplinary branch of science concerned with the visualization of scientific phenomena. It is also considered a subset of computer graphics, a branch of computer science. The purpose of scientific visualization is to graphically illustrate scientific data to enable scientists to understand, illustrate, and glean insight from their data. Research into how people read and misread various types of visualizations is helping to determine what types and features of visualizations are most understandable and effective in conveying information.

In physics and mathematics, the Helmholtz decomposition theorem or the fundamental theorem of vector calculus states that any sufficiently smooth, rapidly decaying vector field in three dimensions can be resolved into the sum of an irrotational (curl-free) vector field and a solenoidal (divergence-free) vector field. This is named after Hermann von Helmholtz.

<span class="mw-page-title-main">Smoothed-particle hydrodynamics</span> Method of hydrodynamics simulation

Smoothed-particle hydrodynamics (SPH) is a computational method used for simulating the mechanics of continuum media, such as solid mechanics and fluid flows. It was developed by Gingold and Monaghan and Lucy in 1977, initially for astrophysical problems. It has been used in many fields of research, including astrophysics, ballistics, volcanology, and oceanography. It is a meshfree Lagrangian method, and the resolution of the method can easily be adjusted with respect to variables such as density.

<span class="mw-page-title-main">Field line</span> Visual aid to depiction of a vector field

A field line is a graphical visual aid for visualizing vector fields. It consists of an imaginary integral curve which is tangent to the field vector at each point along its length. A diagram showing a representative set of neighboring field lines is a common way of depicting a vector field in scientific and mathematical literature; this is called a field line diagram. They are used to show electric fields, magnetic fields, and gravitational fields among many other types. In fluid mechanics, field lines showing the velocity field of a fluid flow are called streamlines.

The derivation of the Navier–Stokes equations as well as their application and formulation for different families of fluids, is an important exercise in fluid dynamics with applications in mechanical engineering, physics, chemistry, heat transfer, and electrical engineering. A proof explaining the properties and bounds of the equations, such as Navier–Stokes existence and smoothness, is one of the important unsolved problems in mathematics.

<span class="mw-page-title-main">Generalized chi-squared distribution</span>

In probability theory and statistics, the generalized chi-squared distribution is the distribution of a quadratic form of a multinormal variable, or a linear combination of different normal variables and squares of normal variables. Equivalently, it is also a linear sum of independent noncentral chi-square variables and a normal variable. There are several other such generalizations for which the same term is sometimes used; some of them are special cases of the family discussed here, for example the gamma distribution.

<span class="mw-page-title-main">Stokes' theorem</span> Theorem in vector calculus

Stokes' theorem, also known as the Kelvin–Stokes theorem after Lord Kelvin and George Stokes, the fundamental theorem for curls or simply the curl theorem, is a theorem in vector calculus on . Given a vector field, the theorem relates the integral of the curl of the vector field over some surface, to the line integral of the vector field around the boundary of the surface. The classical theorem of Stokes can be stated in one sentence: The line integral of a vector field over a loop is equal to the surface integral of its curl over the enclosed surface. It is illustrated in the figure, where the direction of positive circulation of the bounding contour ∂Σ, and the direction n of positive flux through the surface Σ, are related by a right-hand-rule. For the right hand the fingers circulate along ∂Σ and the thumb is directed along n.

In image processing, a kernel, convolution matrix, or mask is a small matrix used for blurring, sharpening, embossing, edge detection, and more. This is accomplished by doing a convolution between the kernel and an image. Or more simply, when each pixel in the output image is a function of the nearby pixels in the input image, the kernel is that function.

In machine learning, the kernel embedding of distributions comprises a class of nonparametric methods in which a probability distribution is represented as an element of a reproducing kernel Hilbert space (RKHS). A generalization of the individual data-point feature mapping done in classical kernel methods, the embedding of distributions into infinite-dimensional feature spaces can preserve all of the statistical features of arbitrary distributions, while allowing one to compare and manipulate distributions using Hilbert space operations such as inner products, distances, projections, linear transformations, and spectral analysis. This learning framework is very general and can be applied to distributions over any space on which a sensible kernel function may be defined. For example, various kernels have been proposed for learning from data which are: vectors in , discrete classes/categories, strings, graphs/networks, images, time series, manifolds, dynamical systems, and other structured objects. The theory behind kernel embeddings of distributions has been primarily developed by Alex Smola, Le Song , Arthur Gretton, and Bernhard Schölkopf. A review of recent works on kernel embedding of distributions can be found in.

Kernel methods are a well-established tool to analyze the relationship between input data and the corresponding output of a function. Kernels encapsulate the properties of functions in a computationally efficient way and allow algorithms to easily swap functions of varying complexity.

<span class="mw-page-title-main">Gradient vector flow</span> Computer vision framework

Gradient vector flow (GVF), a computer vision framework introduced by Chenyang Xu and Jerry L. Prince, is the vector field that is produced by a process that smooths and diffuses an input vector field. It is usually used to create a vector field from images that points to object edges from a distance. It is widely used in image analysis and computer vision applications for object tracking, shape recognition, segmentation, and edge detection. In particular, it is commonly used in conjunction with active contour model.

References

  1. Line Integral Convolution for Flow Visualization by Dr. Matthew O. Ward
  2. Laidlaw, David H.; Kirby, Robert M.; Davidson, J. Scott; Miller, Timothy S.; da Silva, Marco; Warren, William H.; Tarr, Michael J. (October 21–26, 2001). "Quantitative Comparative Evaluation of 2D Vector Field Visualization Methods". IEEE Visualization 2001, VIS '01. Proceedings. San Diego, CA, USA. pp. 143–150.
  3. 1 2 Cabral, Brian; Leedom, Leith Casey (August 2–6, 1993). "Imaging Vector Fields Using Line Integral Convolution". Proceedings of the 20th annual conference on Computer graphics and interactive techniques. SIGGRAPH '93. Anaheim, California. pp. 263–270. CiteSeerX   10.1.1.115.1636 . doi:10.1145/166117.166151. ISBN   0-89791-601-8.
  4. LIC by Zhanping Liu
  5. 1 2 3 Stalling, Detlev; Hege, Hans-Christian (August 6–11, 1995). "Fast and Resolution Independent Line Integral Convolution". Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. SIGGRAPH '95. Los Angeles, California. pp.  249–256. CiteSeerX   10.1.1.45.5526 . doi:10.1145/218380.218448. ISBN   0-89791-701-4.
  6. Weiskopf, Daniel (2009). "Iterative Twofold Line Integral Convolution for Texture-Based Vector Field Visualization". In Möller, Torsten; Hamann, Bernd; Russell, Robert D. (eds.). Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration . Mathematics and Visualization. Berlin, New York: Springer. pp.  191–211. CiteSeerX   10.1.1.66.3013 . doi:10.1007/b106657_10. ISBN   978-3-540-25076-0.
  7. Hege, Hans-Christian; Stalling, Detlev (1998), "Fast LIC with Piecewise Polynomial Filter Kernels", in Hege, Hans-Christian; Polthier, Konrad (eds.), Mathematical Visualization, Berlin, Heidelberg: Springer-Verlag, pp. 295–314, CiteSeerX   10.1.1.31.504 , doi:10.1007/978-3-662-03567-2_22, ISBN   978-3-642-08373-0
  8. Fast Oriented Line Integral Convolution for Vector Field Visualization via the Internet by Rainer Wegenkittl and Eduard Gr¨oller
  9. Java Exploration Tool for Dynamical Systems by R. Wegenkittl and E. Gröller.
  10. Shen, Han-Wei; Kam, David L. (1998). "A New Line Integral Convolution Algorithm for Visualizing Time-Varying Flow Fields" (PDF). IEEE Trans Vis Comput Graph. 4 (2). Los Alamitos: IEEE: 98–108. doi:10.1109/2945.694952. ISSN   1077-2626.
  11. Zöckler, Malte; Stalling, Detlev; Hege, Hans-Christian (1997). "Parallel Line Integral Convolution" (PDF). Parallel Computing. 23 (7). Amsterdam: North Holland: 975–989. doi:10.1016/S0167-8191(97)00039-2. ISSN   0167-8191.
  12. Ding, Zi'ang; Liu, Zhanping; Yu, Yang; Chen, Wei (2015). "Parallel unsteady flow line integral convolution for high-performance dense visualization". 2015 IEEE Pacific Visualization Symposium, PacificVis 2015. Hangzhou, China. pp. 25–30.
  13. Battke, Henrik; Stalling, Detlev; Hege, Hans-Christian (1997). "Fast Line Integral Convolution for Arbitrary Surfaces in 3D". In Hege, Hans-Christian; Polthier, Konrad (eds.). Visualization and Mathematics: Experiments, Simulations, and Environments . Berlin, New York: Springer. pp.  181–195. CiteSeerX   10.1.1.71.7228 . doi:10.1007/978-3-642-59195-2_12. ISBN   3-540-61269-6.
  14. DAAC: Line Integral Convolution
  15. Visual exploration of 2D autonomous dynamical systems Thomas Müller2,1 and Filip Sadlo1 Published 26 February 2015 • © 2015 IOP Publishing Ltd European Journal of Physics, Volume 36, Number 3
  16. A real-time map of the wind in the U.S. by Fernanda Viégas and Martin Wattenberg.
  17. researchgate publication: Sun, Shuo & Huang, Dongwei. (2022). Efficient Region-Based Pencil Drawing.
  18. S. Yamamoto, Xiaoyang Mo and A. Imamiya, "Enhanced LIC pencil filter," Proceedings. International Conference on Computer Graphics, Imaging and Visualization, 2004. CGIV 2004., 2004, pp. 251-256, doi: 10.1109/CGIV.2004.1323994.
  19. Xiaoyang Mao, M. Kikukawa, K. Kashio and A. Imamiya, "Automatic generation of hair texture with line integral convolution," 2000 IEEE Conference on Information Visualization. An International Conference on Computer Visualization and Graphics, 2000, pp. 303-308, doi: 10.1109/IV.2000.859772.
  20. Xiaoyang Mao, Toshikazu Suzuki, and Atsumi Imamiya. 2003. AtelierM: a physically based interactive system for creating traditional marbling textures. In Proceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia (GRAPHITE '03). Association for Computing Machinery, New York, NY, USA, 79–ff. https://doi.org/10.1145/604471.604489
  21. Bernhard Jenny (2021) Terrain generalization with line integral convolution, Cartography and Geographic Information Science, 48:1, 78-92, DOI: 10.1080/15230406.2020.1833762