约定记号

首先，我们生成一个序列，比如 $ [3,5,1,7,9] $，命名为 $ a $，记作 $ a=[3,5,1,7,9] $．并且记 $ a $ 序列中这五个数的下标分别为 $ 0,1,2,3,4 $，即 $ a_0=3,\; a_1=5,\; a_2=1,\; a_3=7,\; a_4=9 $．此时我们可以定义一种将 $ a $ 的下标视为原像，序列的值视为像的离散函数，也记作 $ a $．即，$ a(0)=3,\; a(1)=5,\; a(2)=1,\; a(3)=7,\; a(4)=9 $，我们将这种离散函数简记作 $ a=[3_A,5,1,7,9] $．其中，$ A $ 代指锚 $ (anchor) $，用以标记原像为 $ 0 $ 的点．不作标注时一般指第一个数原像为 $ 0 $．约定下标总是连续的整数．

[admonition color="red"]该约定仅为方便理解，并不作为流行标准使用．[/admonition]


离散卷积

对于两个离散函数 $ a=[x_{0_{A}},x_1,x_2,\cdots ,x_m] $ 和 $ b=[y_{0_{A}},y_1,y_2,\cdots ,y_n] $，定义卷积 $ \ast $，

$ c=a\ast b $

表示

$ \displaystyle c(i+j)=\sum_{0\leqslant i\leqslant m,\, 0\leqslant j\leqslant n}a(i)\times b(j) $．

还有一种左侧只有一个元的表示

$ \displaystyle c(i)=\sum_{0\leqslant j\leqslant m,\, 0\leqslant i-j\leqslant n}a(j)\times b(i-j) $，

和前者是完全一样的．

实例

取 $ a=[3_A,5,1,7,9] $，$ b=[2_A,6,4] $，则 $ c=a\ast b $ 中，
$ c(0)=a(0)\times b(0)=3\times 2=6 $，
$ c(1)=a(0)\times b(1)+a(1)\times b(0)=3\times 6+5\times 2=28 $，
$ c(2)=a(0)\times b(2)+a(1)\times b(1)+a(2)\times b(0)=3\times 4+5\times 6+1\times 2=44 $，
$ c(3)=a(1)\times b(2)+a(2)\times b(1)+a(3)\times b(0)=5\times 4+1\times 6+7\times 2=40 $，
$ c(4)=a(2)\times b(2)+a(3)\times b(1)+a(4)\times b(0)=1\times 4+7\times 6+9\times 2=64 $，
$ c(5)=a(3)\times b(2)+a(4)\times b(1)=7\times 4+9\times 6=46 $，
$ c(6)=a(4)\times b(2)=9\times 4=36 $，
于是 $ a\ast b=c=[6_A,28,44,40,64,46,36] $．

着重看中间三行，这看起来好像是用 $ b=[2_A,6,4] $ 倒序遍历 $ a $ 的每一个三元组，进行乘积加和．而这正是很多时候我们需要的东西．

卷积有很多优秀的性质，比如

交换律$\;$ $ a\ast b = b\ast a $，
结合律$\;$ $ a\ast(b\ast c)=(a\ast b)\ast c $，
对加法的分配律$\;$ $ a+(b\ast c)=(a\ast b)+(a\ast c) $，

这些都是很容易证明的．


引申：连续卷积

这里仅给出函数式

$$ \displaystyle h(x)=\int_{-\infty}^{+\infty}f\left(\tau\right)g\left(x-\tau\right)\,{\rm d}\tau, $$

它是一种反常积分，可以分步求解．这里的 $ x $ 类似于上面的原像（下标），$ f(x),g(x),h(x) $ 则是 $ x $ 下的像．


引申：狄利克雷卷积

另外，有另一种数论上的卷积叫做狄利克雷卷积（链接来自 oi-wiki），它也是离散的卷积 QwQ．


离散相关

我们发现卷积的遍历是倒序的，于是自然会想到正序的遍历．相关便是一种．仍然是两个离散函数 $a=[x_0,x_1,x_2,\cdots ,x_m] $ 和 $ b=[y_0,y_1,y_2,\cdots ,y_n]$，定义相关 $\star$，

$c=a\star b$，

表示

$\displaystyle c(i-j)=\sum_{0\leqslant i\leqslant m,\, 0\leqslant j\leqslant n}a(i)\times b(j)$．

这里，它还有另两种形式，它们形如

$\displaystyle c(i)=\sum_{0\leqslant i+j\leqslant m,\, 0\leqslant j\leqslant n}a(i+j)\times b(j)$，
$\displaystyle c(i)=\sum_{0\leqslant j\leqslant m,\, 0\leqslant j-i\leqslant n}a(j)\times b(j-i)$．

实例，第二回

仍然取 $a=[3_A,5,1,7,9]$，$b=[2_A,6,4]$，若 $c=a\star b$，则有，
$c(-2)=a(0)\times b(2)=3\times 4=12$，
$c(-1)=a(0)\times b(1)+a(1)\times b(2)=3\times 6+5\times 4=38$，
$c(0)=a(0)\times b(0)+a(1)\times b(1)+a(2)\times b(2)=3\times 2+5\times 6+1\times 4=40$，
$c(1)=a(1)\times b(0)+a(2)\times b(1)+a(3)\times b(2)=5\times 2+1\times 6+7\times 4=44$，
$c(2)=a(2)\times b(0)+a(3)\times b(1)+a(4)\times b(2)=1\times 2+7\times 6+9\times 4=80$，
$c(3)=a(3)\times b(0)+a(4)\times b(1)=7\times 2+9\times 6=68$，
$c(4)=a(4)\times b(0)=9\times 2=18$，
于是 $a\star b=c=[12,38,40_A,44,80,68,18]$．

仍然着重看中间三行，这次是正序遍历了．

但是，相关并不具有卷积的那些性质，它甚至不具有交换性．这也导致了我们很多时候宁可颠倒一下使用卷积，也很少使用相关．


定义一个序列 $a$ 的颠倒记为 $a^R$（$A$ 的位置也跟着变动，并以 $A$ 为锚重新分配下标），显然，我们有

$a\ast b=a\star b^R$，

并且，如果 $a=a^R$，不难证明，它需要满足如下三个性质：
$1$，$a$ 的原像有奇数个；
$2$，$a$ 的锚点在正中央；
$3$，$a$ 的像中心对称．

引申：连续相关

同样仅给出函数式

$$\displaystyle h(x)=\int_{-\infty}^{+\infty}f\left(\tau\right)g\left(\tau-x\right)\,{\rm d}\tau.$$

应用

注意到，如果 $a=a^R$，那么使用 $a$ 的卷积和相关实际上是没有区别的（使用 $a$ 指 $a$ 在运算符右侧）．在向量或 $n$ 阶方阵中，一个锚在中心且中心对称的元素就满足这个性质．比如在图像处理中，使用中心对称核进行滤波时，就会采用相关（可以看成卷积）．

以下给出一个实例．

$\displaystyle I=\left[ \begin{matrix} 1_A & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{matrix} \right]$，

$\displaystyle C=\left[ \begin{matrix} 0.027 & 0.110 & 0.027 \\ 0.110 & 0.443_A & 0.110 \\ 0.027 & 0.110 & 0.027 \end{matrix} \right]$，

其中 $I$ 是图像，$C$ 是滤波所用的核（$\sigma=0.6$ 的三阶高斯滤波）．那么

$\displaystyle I\star C=I\ast C^R=I\ast C=\left[ \begin{matrix} x_A & x & x & x & x \\ x & 6.937 & 7.928 & 8.919 & x \\ x & 11.892 & 12.883 & 13.874 & x \\ x & 16.847 & 17.838 & 18.829 & x \\ x & x & x & x & x \end{matrix} \right]$，

这里 $x$ 是边框值，暂不考虑．
它是一个让图像变模糊（和周围更接近）的滤波．

而在计算梯度时，由于核不再中心对称（如 $Sobel$ 算子），有时要区别卷积和相关．这里就不举例了．