I'm trying to understand a book chapter on "Algorithms For Efficient Computation of Convolution" (Also on Doc Droid or Scribd) and I know that when calculating the convolution of an image represented by two dimensional matrix (array) with a mask matrix the result is the treated two dimensional image.

How to calculate the convolution of two signals represented by a row and a column?

The chapter I'm reading says that:

Separable convolution kernel must fullfil the condition that its matrix has rank equal to one. In other words, all the rows must be linearly dependent. Why? Let us construct such a kernel. Given one row vector

$$ \vec{u}=\left(u_1, u_2, u_3, \ldots, u_m\right) $$ and one column vector $$ \vec{v}^T=\left(v_1, v_2, v_3, \ldots, v_n\right) $$ let us convolve them together: $$ \vec{u}*\vec{v}=\left(u_1, u_2, u_3, \ldots, u_m\right)*\begin{pmatrix}v_1\\v_2\\v_3\\\vdots\\v_n\end{pmatrix}=\begin{pmatrix}u_1v_1&u_2v_1&u_3v_1&\cdots&u_mv_1\\ u_1v_2&u_2v_2&u_3v_2&\cdots&u_mv_2\\ u_1v_3&u_2v_3&u_3v_3&\cdots&u_mv_3\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ u_1v_n&u_2v_n&u_3v_n&\cdots&u_mv_n\end{pmatrix}=A\tag{4}\\ $$


1 Answer 1


Following the wiki page on the subject, you are looking to create a 2 dimensional filter from two one-dimensional filters.

I found that the second example was more relevant for your question. I want to give a $\begin{bmatrix}1&2 &1 \end{bmatrix}$ weight column wise and on top of that give a $\begin{bmatrix}1\\2 \\1 \end{bmatrix}$ weight to each row. The result is the filter $\begin{bmatrix}1&2 &1\\2&4&2 \\1&2 &1 \end{bmatrix}$ which take into consideration both your demands. By the way this spesific filter will smooth you image.

The simple fact that this filter can be expressed as the outer product of two vectors renders this filter separable, Hence separable convolution. This post considers, also, non-separable filters.


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.