# Convolution is convolution; it's NOT dot product

Yao Yao on May 20, 2019
$\DeclareMathOperator*{\argmin}{argmin} \newcommand{\icol}[1]{ \bigl[ \begin{smallmatrix} #1 \end{smallmatrix} \bigr] } \newcommand{\icolplus}[1]{ \Bigl[ \begin{smallmatrix} #1 \end{smallmatrix} \Bigr] }$

## 1-D Convolution

$(f \ast g)(t) \overset{\Delta}{=} \int_{-\infty}^{\infty} f(\tau) g(t-\tau) \mathrm{d} \tau$

$(f \ast g)(t) \overset{\Delta}{=} \int_{-\infty}^{\infty} f(t-\tau) g(\tau) \mathrm{d} \tau$

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

$(f \ast g)(n)=\sum_{m} f(m) g(n-m)$

## 2-D Convolution

$(f \ast g)(x, y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(\sigma, \tau) g(x - \sigma, y - \tau) \mathrm{d} \sigma \mathrm{d} \tau$

$(f \ast g)(x, y) = \sum_{\sigma} \sum_{\tau} f(\sigma, \tau) g(x - \sigma, y - \tau)$

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

$A(i, j) = A_{i,j}$

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

\begin{aligned} f_A(i, j) &= A_{m_K + i, n_K + j} \newline f_K(i, j) &= K^{HV}_{i, j} = K_{m_K - i, n_K - j} \end{aligned}

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)

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

\begin{aligned} C(0,0) &= \sum_{i'} \sum_{j'} K_{2 - i', 2 - j'} A_{2 - i', 2 - j'} \newline &= K_{0,0}A_{0,0} + K_{0,1}A_{0,1} + K_{1,0}A_{1,0} + K_{1,1}A_{1,1} \newline C(0,1) &= \sum_{i'} \sum_{j'} K_{2 - i', 2 - j'} A_{2 - i', 3 - j'} \newline &= K_{0,0}A_{0,1} + K_{0,1}A_{0,2} + K_{1,0}A_{1,1} + K_{1,1}A_{1,2} \newline C(1,0) &= \sum_{i'} \sum_{j'} K_{2 - i', 2 - j'} A_{3 - i', 2 - j'} \newline &= K_{0,0}A_{1,0} + K_{0,1}A_{1,1} + K_{1,0}A_{2,0} + K_{1,1}A_{2,1} \newline C(1,1) &= \sum_{i'} \sum_{j'} K_{2 - i', 2 - j'} A_{3 - i', 3 - j'} \newline &= K_{0,0}A_{1,1} + K_{0,1}A_{1,2} + K_{1,0}A_{2,1} + K_{1,1}A_{2,2} \end{aligned}

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！

\begin{aligned} 0 \leq i' < m_K \newline 0 \leq j' < n_K \newline 0 \leq m_K - i' + i < m_A \newline 0 \leq m_K - i' + i < n_A \end{aligned}

\begin{aligned} 0 \leq i < m_A - m_K \newline 0 \leq j < n_A - n_K \end{aligned}