# Prove that convolution with a separable filter is equivalent to convolution on each 1D filter

I would like to prove that convolution of an image $$I \in \mathcal{M}_{m_1 \times n_1}$$ with respect to a separable 2D filter $$F$$, (i.e., $$F = F_1 F_2$$, where $$F \in \mathcal{M}_{m_2\times n_2}(\mathbb{R})$$, $$F_1 \in \mathcal{M}_{m_2\times1}$$, and $$F_2 \in \mathcal{M}_{1\times n_2}$$) is equivalent to convolution with respect to $$F_1$$ and then $$F_2$$. If $$A*B$$ represents convolution of an image matrix $$A$$ under a filter matrix $$B$$, then we need to show that $$I*F=(I*F_1)*F_2$$.

We define convolution as such: $$(I*F)_{(m,n)} = \sum_{i=-m_2/2}^{m_2/2}\sum_{j=-n_2/2}^{n_2/2}F[i,j]\cdot I[m-i,n-j]$$, or $$\sum_{i=-m_2/2}^{m_2/2}\sum_{j=-n_2/2}^{n_2/2} I[i,j]\cdot F[m-i,n-j]$$.

Here's what I've tried starting with the left side (using the matrix indexing notation [m,n]):

$$((I*F_1)*{F_2}){[m,n]} = \sum_{j=-n_2/2}^{n_2/2}(\sum_{i=-m_2/2}^{m_2/2}{I{[m-i,n-1]}} \cdot {{F_1}{[i,1]}}){[m-1,n-j]}{F_2}{[1,j]}$$

Now, I notice that the terms $${F_1}{[i,1]}$$ and $$F_2[1,j]$$ as placed in the summations can be combined to yield $$F[i,j]$$, however, we are indexing this entire term, so I don't believe we can combine these two terms as such. Additionally, the I don't see how to get terms involving $$I$$ to become $$I[m-i,n-j]$$.

Any advice would be much appreciated.

## 1 Answer

It requires a good deal of interpretation and a few clear sketches.I will try to provide a clean and easy approach, may be not very rigorous.

Let $$x[n,m]$$ be the original image (2D sequence) where $$n$$ is along the horizontal and $$m$$ is along the vertical axes and the origin being at the bottom left.

Consider the separable 2D filter sequence $$h[n,m] = f[n]g[m]$$ where $$f[n]$$ and $$g[m]$$ are the corresponding 1D filter sequences along the horizontal and vertical axes respectively.

The 2D output sequence of the convolution is denoted similarly as $$y[n,m] = x[n,m]\star h[n,m]$$ The procedure proceeds by writing the convolutiom sum:

\begin{align} y[n,m] &= \sum_k \sum_r h[n-k,m-r] x[k,r] \\ &= \sum_k \sum_r f[n-k] g[m-r] x[k,r] \\ &= \sum_k f[n-k] \left( \sum_r g[m-r] x[k,r] \right) \\ \end{align}

At the this point, recognize the following: The summation inside the brackets indicate a 1D convolution between the filter $$g[m]$$ and the $$k-th$$ column of the original image: $$x[k,m]$$. Remember that during the summation the dummy index $$k$$ is fixed, whereas the other dummy index $$r$$ is ranging through the vertical samples of $$x[k,r]$$. We shall denote this intermediate sum as a new 2D sequence called $$w[k,m]$$, parametrized according to $$k$$ and $$m$$. That's the intermediate image defined for each value of $$k$$ and $$m$$ and formed by convolving each column-$$k$$ of $$x[n,m]$$ by the filter sequence $$g[m]$$. Then the equation follows as:

\begin{align} y[n,m] &= \sum_k f[n-k] \left( \sum_r g[m-r] x[k,r] \right) \\ &= \sum_k f[n-k] w[k,m] \\ y[n,m] &= f[n] \star w[n,m] \\ \end{align}

Where we interpret the last line as a 1D convolution between the rows of the intermediate image (for each fixed $$m$$) and the 1D sequence $$f[n]$$ along horizontal direction. Which finishes the proof.

Indeed, it's hard to visualize the process, as it's a two step approach. Nevertheless, relience on the assumed interpretations and verificaton by matlab coding would rather help.