3
$\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$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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