# 2D Convolution as a Doubly Block Circulant Matrix Operating on a Vector

I was reading Fundamental Image Processing, Chapter 5 (Image Transforms), I encountered the following problem:
Given the arrays $x_1(m,n)$ and $x_2(m,n)$ as follows:

Write their convolution $x_3(m,n) = x_2(m,n)\ast x_1(m,n)$ as a doubly block circulant matrix operating on a vector of size 16 and calculate the result.
Can anyone please explain what the meaning of problem is and how it should be solved?

• could you please denote the full name of the book? – Ivan Talalaev Apr 17 at 12:34

The point is that circular convolution of two 1-D discrete signals can be expressed as the product of a circulant matrix and the vector representation of the other signal.

The circulant matrix is a toeplitz matrix which is constructed by different circular shifts of a vector in different rows. For example, consider two signls $h[n]$ and $g[n]$, each of length $4$. If we assume $\mathbf{h}=\begin{bmatrix} h_0 & h_1 & h_2 & h_3 \end{bmatrix}$, then the circulant matrix denoted by $\mathrm{circ}(h)$ is $$\mathrm{circ}(\mathbf{h})=\mathbf{H}=\begin{bmatrix} h_0 & h_3 & h_2 & h_1\\ h_1 & h_0 & h_3 & h_2\\ h_2 & h_1 & h_0 & h_3\\ h_3 & h_2 & h_1 & h_0 \end{bmatrix}.$$ So we can calculate $h[n]*g[n]$ by evaluating the product $\mathbf{H}\mathbf{g}$, where $\mathbf{g}=\begin{bmatrix} g_0 & g_1 & g_2 & g_3 \end{bmatrix}^T$.

This can be extended to 2-D signals. I explain it through the given example.

The size of signals are $2\times2$ and $3\times3$. The size of convolution is $(2+3-1)\times(2+3-1)=4\times4$. So we need to pad zeros to adjust the size of 2-D signal $x_2(m,n)$: $$\mathbf{A}=\begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & -1 & 0 & 0\\ -1 & 4 & -1 & 0\\ 0 & -1 & 0 & 0 \end{bmatrix}$$ Now construct four circulant matrices corresponding to the four rows of $\mathbf{A}$ denoted by $\mathbf{a}_i$ as follows:

\begin{align} \mathbf{X}_0&=\mathrm{circ}(\mathbf{a}_0)=\mathrm{circ}(\begin{bmatrix} 0 & -1 & 0 & 0 \end{bmatrix})\\ \mathbf{X}_1&=\mathrm{circ}(\mathbf{a}_1)=\mathrm{circ}(\begin{bmatrix} -1 & 4 & -1 & 0 \end{bmatrix})\\ \mathbf{X}_2&=\mathrm{circ}(\mathbf{a}_2)=\mathrm{circ}(\begin{bmatrix} 0 & -1 & 0 & 0 \end{bmatrix})\\ \mathbf{X}_3&=\mathrm{circ}(\mathbf{a}_3)=\mathrm{circ}(\begin{bmatrix} 0 & 0 & 0 & 0 \end{bmatrix}) \end{align} and construct the $16\times16$ doubly circuland matrix $$\mathbf{X}=\begin{bmatrix} \mathbf{X}_0 & \mathbf{X}_3 & \mathbf{X}_2 & \mathbf{X}_1\\ \mathbf{X}_1 & \mathbf{X}_0 & \mathbf{X}_3 & \mathbf{X}_2\\ \mathbf{X}_2 & \mathbf{X}_1 & \mathbf{X}_0 & \mathbf{X}_3\\ \mathbf{X}_3 & \mathbf{X}_2 & \mathbf{X}_1 & \mathbf{X}_0 \end{bmatrix}.$$ Now we need to construct the vector corresponding to $x_1(m,n)$. Pad zeros from left and bottom to adjust indices considering $m,n$, and pad zeros from top and right to make the size $4\times4$: $$\mathbf{B}=\begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 3 & 4 & 0\\ 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix},$$ then construct a $16\times 1$ vector $\mathbf{b}=\begin{bmatrix} \mathbf{b}_0 \ |& \mathbf{b}_1 \ |& \mathbf{b}_2 \ |&\mathbf{b}_3 \end{bmatrix}^T$ by concatenating the rows of matrix $\mathbf{B}$.

Finally, the 2-D circular convolution is $$\boxed{\mathbf{G}=\mathbf{X}\mathbf{b}}$$

• Why are you working on the rows instead of columns? – Royi Jan 16 '19 at 12:28