Convolution is convolution; it's NOT dot product

Yao Yao on May 20, 2019

我真的是出离愤怒。我不知道最开始把 convolution 看做 dot product 的人是怎么想的!有 convolution 的公式不用,非要用这么蹩脚的 intuition?而且明显 convolution 和 Hadamard product 的关系更大一点呢,咋没见人提?

本文主要参考:

1-D Convolution

首先 convolution 不是限定于 matrix 间、也不是限定于 tensor 间的运算,它其实是两个 functions 之间的运算:

在 engineering 领域也有 $f(t) \ast g(t)$ 的写法。

因为 $(f \ast g)(t) = (g \ast f)(t)$,所以也可以有:

物理上的一个 intuition 是:if signal $f(t)$ is applied to an LTI (linear time-invariant) system with impluse response $g(t)$, the final output is $f(t) \ast g(t)$.

For complex-valued functions $f$, $g$ defined on $\mathbb{Z}$, the discrete convolution of $f$ and $g$ is:

2-D Convolution

一般有:

如果 $f$, $g$ 是 discrete functions,则有:

Matrix 2-D Convolution for Image Processing / Image & Kernel

如果我们把 matrix $A$ 看做其自身 indice 的函数 (所以自然是 discrete 的函数) (而不是把 matrix $A$ 看做是关于 vector $\mathbf{x}$ 的函数),比如最基本的:

where $0 \leq i < m, 0 \leq j < n$. 那么两个 matrice 也可以做 convolution (以下下标都从 0 记起)。

但是要注意在 image processing 领域,这个 matrix 的函数式写法没有这么简单。一般有一个 image matrix $A_{m_A \times n_A}$,一个 kernel matrix $K_{m_K \times n_K}$,$m_K < m_A, n_K < n_A$。然后我们有函数:

where $K^{HV} = JKJ$ and $J$ is the anti-diagonal “identity” matrix (或者看成是 row-reversed identity matrix) like $\icol{0 & 1 \newline 1 & 0}$.

  • $JK$ 的作用是将 $K$ 上下翻转 (horizontally flip)
  • $KJ$ 的作用是将 $K$ 左右翻转 (vertically flip)

如果有 matrix $C = f_A \ast f_K$,那么有:

  • 注意,如果下标从 1 开始计的话,上面的下标都要 +1
  • 另外,参考 kernel method 的思想,实际应用中我们并不需要构造 $f_A$ 和 $f_K$,直接写出 $C(i, j) = \sum_{i’} \sum_{j’} K_{?, ?} A_{?, ?}$ 的形式拿来用就好了

考虑个具体的例子,假设 $K_{2 \times 2}, A_{3 \times 3}$,则 $C = (f_A \ast f_K)$ 有:

这个例子给出了一个很直观的 intuition:

  1. 把 kernel $K$ 覆盖在 image $A$ 之上,$K_{0,0}$ 对齐到 $A_{0,0}$ (左上角对齐)
  2. 移动 kernel $K$ 使 $K_{0,0}$ 对齐到 $A_{i,j}$,假设覆盖到的 image $A$ 的部分是 $A_{i:i+m_K, j:j+n_K}$
  3. 那么 $C(i, j) = \operatorname{sum} \big( K \odot A_{i:i+m_K, j:j+n_K} \big)$ (sum of Hadamard product)
    • 我再次强调一遍,这不是 dot product!

很明显我们可以把 $C$ 看做一个 matrix $C_{i, j} = C(i, j)$。最后考虑下这个 matrix $C$ 的 size:

进而有:

所以 matrix $C$ 最大的 size 只可能是 $(m_A - m_K + 1) \times (n_A - n_K + 1)$



blog comments powered by Disqus