# 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.

Let the 2D sequence $$x[n,m]$$ represent the original image, using the following convention: $$n$$ is horizontal-right, $$m$$ is vertical-up, and the origin is at the bottom left.

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

The output 2D sequence of the convolution is $$y[n,m] = x[n,m]\star h[n,m].$$

Write 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}

recognize the following: The summation inside the brackets indicate a 1D convolution between the sequence $$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]$$. Denote this intermediate sum as a new 2D sequence $$w[k,m]$$, parametrized according to $$k$$ and $$m$$. This's the intermediate image defined for each $$k$$ & $$m$$, and formed by convolving each column-$$k$$ of $$x[n,m]$$ by the 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, the last line represents a 1D convolution between the rows of the intermediate image (for each fixed $$m$$) and the 1D sequence $$f[n]$$ along horizontal direction, finishing the proof.