2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.