How to accomplish 2D convolution using 1D convolution?

Question

Suppose,

u = [1 2 1 3 ; 1 2 1 3 ; 1 2 1 3];
v = [2 0 1 ; 2 0 1 ; 2 0 1];

I want to achieve

w = conv2(u, v);    % [2 4 3 8 1 3 ; 4 8 6 16 2 6 ; 6 12 9 24 3 9 ; 4 8 6 16 2 6 ; 2 4 3 8 1 3]

And, suppose, I don't want to use conv2().

Using Matlab, I discovered that,

w1 = conv([1 2 1 3], [2 0 1])   % [2 4 3 8 1 3]
w2 = conv([1 2 1 3], [2 0 1])   % [2 4 3 8 1 3]
w3 = conv([1 2 1 3], [2 0 1])   % [2 4 3 8 1 3]

So, we get:

w123 = [w1 ; w2 ; w3]           % [2 4 3 8 1 3 ; 2 4 3 8 1 3 ; 2 4 3 8 1 3];

Using Matlab, I also discovered that,

x = [2 ; 2 ; 2]
y = [1 ; 1 ; 1]
z = conv(x, y); % [2 ; 4 ; 6 ; 4 ; 2];

x = [4 ; 4 ; 4]
y = [1 ; 1 ; 1]
z = conv(x, y); % [4 ; 8 ; 12 ; 8 ; 4];

x = [3 ; 3 ; 3]
y = [1 ; 1 ; 1]
z = conv(x, y); % [3 ; 6 ; 9 ; 6 ; 3];

x = [8 ; 8 ; 8]
y = [1 ; 1 ; 1]
z = conv(x, y); % [8 ; 16 ; 24 ; 16 ; 8];

x = [1 ; 1 ; 1]
y = [1 ; 1 ; 1]
z = conv(x, y); % [1 ; 2 ; 3 ; 2 ; 1];

x = [3 ; 3 ; 3]
y = [1 ; 1 ; 1]
z = conv(x, y); % [3 ; 6 ; 9 ; 6 ; 3];

Which means, if we perform 1D convolution on each row of u with kernel [2 0 1], and then apply 1D convolution on each column with kernel [1; 1; 1], we obtain:

2  4  3  8  1  3
4  8  6 16  2  6
6 12  9 24  3  9
4  8  6 16  2  6
2  4  3  8  1  3

So, my question is, where does this [1 ; 1 ; 1] come from?

And, most importantly, what would happen if the rows are not same?

Your search term for the day is Separable Convolution Filter. — beaker
@beaker, So, in short: 2d convolution, in general, isn't achievable from 1d conv. unless the kernel is seperable. — user366312
@beaker, post your comment as an answer and I will accept that. — user366312

beaker beaker · Accepted Answer · 2018-10-28T17:40:24

The reason that your 1D convolutions combine to give you the same results as the 2D convolution is that your filter is separable. Steve Eddins discussed separable convolutions on his MATLAB blog here.

Your filter is separable because:

[1;1;1] * [2,0,1] = 

   2   0   1
   2   0   1
   2   0   1

But in general, not all 2D filters are separable and only those that are can be turned into separate 1D convolutions.

How to accomplish 2D convolution using 1D convolution?

2 Answers