​ 本文第一次提出了线积分卷积的方法。线积分卷积是一种特殊的卷积滤波方法，主要用于实现矢量场可视化。

1. DDA卷积

   ​ DDA卷积是一种从传统DDA线条绘制技术以及一种空间卷积算法一般化而来的矢量场可视化方法。矢量场中的每一个向量都定义了一条与其成切向的DDA生成的直线形滤波核（filter kernel）。其以向量的位置为起始点，向其正向与反向分别前进一定的距离$L$，直线的总长便为$2L$。接着滤波核下的输入纹理图像的像素就被加起来，其值在归一化后就成为输出图像中，原向量的位置所对应的像素的值。

   ​ 需要注意的是这一方法对DDA算法与滤波器的对称性非常敏感。同时，这一方法虽然高效，但准确性不足。该方法假设局部的矢量场能够用一条直线来近似，因而对于某些具有较大曲率半径的向中的点，这一假设是有效的；但对于某些区域，其复杂的结构可能比DDA生成的直线长度还要小，也就是说某些点的曲率半径过小以至于无法使用一条长度固定的直线来近似。于是总的来说，DDA卷积对向对应图像的生成是不均匀的，曲率半径大的或是更具线性性的区域的生成结果更为清晰，而细小的漩涡就显得紊乱，即细节被丢失。

   DDA算法（数值微分法）是一个非常基础的直线生成算法，主要利用了增量的思想，通过同时对$x$和$y$各增加一个小增量，计算下一步的$x$和$y$值。与最直接的根据直线方程计算函数值来求下一点的方法相比，避免了浮点数的乘法运算。

   ​ \(y_i=kx_i+b\\y_{i+1}=kx_{i+1}+b=kx_i+b+k\Delta x=y_i+k\Delta x\)

2. 线积分卷积

   ​ 矢量场的局部特征可以通过计算一条流线来近似，这条流线从像素$ (x,y) $的中心出发，向原向量的正向与反向各前进一定的距离。坐标的向前对流（the forward coordinate advection，我们需要追踪的坐标在矢量场中就像是小球在河流中）有着下面方程的形式：

   ​ \(\begin{aligned}P_0&=(x+0.5,y+0.5)\\P_i&=P_{i-1}+\frac{V(\lfloor P_{i-1}\rfloor)}{\Arrowvert V(\lfloor P_{i-1}\rfloor)\Arrowvert} \Delta s_{i-1}\end{aligned}\)

   \[s_e=\begin{cases}\infty \ \rm{if} \ V\parallel e \\0 \ \rm{if} \frac{\lfloor P_c \rfloor -P_c}{V_c}<0\\\frac{\lfloor P_c \rfloor -P_c}{V_c} \ \rm{otherwise}\end{cases}\rm{for} \ (e,c) \in \{ (top,y),(bottom,y),(left,x),(right,x) \}\]

   ​ \(\Delta s_i=\rm{min} (s_{top},s_{bottom},s_{left},s_{right})\)

   其中$ V(\lfloor P \rfloor) $表示输入矢量场中格点$ (\lfloor P_x \rfloor, \lfloor P_y \rfloor) $处的向量。此方程的含义是，对于像素$ (x,y) $，取其中心点$ P_0 $为起始点，然后沿原向量的正方向加一个值$ \Delta s_i $来找到下一个点，如此不断进行下去，直到生成一条具有指定长度的流线（由许多直线线段共同构成）。$ \Delta s_i $是一条与原向量平行的，一个端点是当前点$ P_i $而另一个端点在最邻近的像素格点边缘上的线段的长度。为满足DDA算法对对称性的要求，还要向原向量的反方向同样地生成一条流线（由许多前述线段组成）。在整个LIC方法中，这一步所做的工作就是从一个起始点出发，在整个矢量场中一定的范围内，不断地沿着矢量的方向找点（追踪）。需要注意的是$ \Delta s_i $的计算对舍入错误（round off errors）敏感。$ \Delta s_i $必须使得生成的对流后的坐标（advected coordinate）存在于第$ i+1 $个像素格子中。也就是要能够将正在生成的流线“带出”当前点$ P_i $所在的像素格子。为实现这一效果，算法实现时为每个$ \Delta s_i $都加上了一个小的舍入项（round off term）。

   ​ 于是，通过前述方法生成的一条由直线段构成的流线能够被看做是区域中的一条参数化的曲线，而输入的纹理图像（图像中每个像素块（x,y）都对应着一个像素值）的每个像素块与其像素值之间的对应可以看作一个以x和y为自变量的标量函数。于是我们就能够沿着每条参数化的空间曲线来对这一标量场进行积分，这种积分方法就是第一型曲线积分。总的来说，线积分卷积LIC就是将DDA卷积中的卷积概念与第一型曲线积分结合到了一起。

   ​ \(\begin{aligned}h_i &= \int^{s_i+\Delta s_i}_{s_i}k(w)dw\\\rm{where}\\s_0&=0\\s_i&=s_{i-1}+\Delta s_{i-1}\end{aligned}\)

   对上面的公式，$ k(w) $是卷积核函数（在此可以是任意的数学函数），$ k(w) $定义上是一个连续的数学函数，但实现需要离散化（图像的像素是离散的），于是就需要在$ \Delta s_i $的区间（直线段）上对其进行积分，用以作为$ P_i $点的卷积权重$ h_i $。输出图像中像素$ (x,y) $的值$ F’(x,y) $的完整计算方程如下所示：

   ​ \(F'(x,y)=\frac{\sum^l_{i=0}F(\lfloor P_i \rfloor)h_i+\sum^{l'}_{i=0}F(\lfloor P'_i \rfloor)h'_i}{\sum^l_{i=0}h_i+\sum^{l'}_{i=0}h'_i}\)

   上式中$ F(\lfloor P \rfloor) $是矢量图中位于$ (\lfloor P_x \rfloor, \lfloor P_y \rfloor) $的向量所对应的输入纹理图中的像素值。分母是卷积核的线积分，起到归一化的作用。总的来说，LIC与DDA卷积相比，能够局部地跟踪矢量场的特征（生成流线），从而更精确地反映矢量场中曲率半径较小区域的情况，细节更加清晰。

   ​ 下面是师兄的部分讲解：

   • LIC的输入有两张图像，一张图记录矢量场的分布，另一张图是待卷积的纹理图。LIC根据矢量场的分布对纹理图进行卷积，输出的是LIC卷积后的纹理图。LIC直接处理的是纹理图。卷积的区域$s$是由一个个直线线段拼接而成的曲线，这个曲线可以看成$s$上的参数化的空间曲线（也就是类似于椭圆曲线的形式）。输入纹理图中的每个像素块都对应着一个像素值，可以看成以$x$和$y$为输入参数的连续标量函数，即$f(x,y)$，对于一个指定的$(x,y)$点，都会有一个纹理值$f(x,y)$。可以沿着这个参数化的空间曲线，对输入的标量场（也就是$d(x,y)$）进行积分。
   • DDA卷积和LIC卷积的区别主要在于卷积的区域不同，DDA卷积直接沿着$(x,y)$处的矢量方向画一条直线，对这条直线覆盖区域的像素进行卷积；而LIC则以$(x,y)$作为起始点，沿着矢量的方向$v(x,y)$追踪下去，每追踪到一个新的点$(x_i,y_i)$，就以$(x_i,y_i)$处的矢量$v(x_i,y_i)$作为新的追踪方向，追踪到一定长度后就停止。因此LIC的卷积区域是一个更为精确的曲线区域，更贴近矢量场的流动分布情况。