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

Question

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.

Answer 1

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.