1
$\begingroup$

I know separability of a Gaussian filter enhances the computational complexity from $\mathcal{O}(L^2*N*M) \to \mathcal{O}((L*N*M)$. How this really reflect on my program? I suppose the number of for loops that I need for the convolution less compare to nonseparable case? What real disadvantages ?

$\endgroup$
1
$\begingroup$

Assuming the simplest case with a square image $x[n,m]$ of size $N \times N$ and a square filter kernel $h[n,m]$ of size $M \times M$, the raw 2D convolution to produce the, cropped, output image $y[n,m]$ of size $N \times N$ requires about $N^2 \times M^2$ MACs.

The raw 2D convolution between $x[n,m]$ and the filter $h[n,m]$ is implemented by using two for loops to range through each output pixel and two additional for loops to perform the 2D convolution at that pixel location. Hence a total of 4 nested for-loops are required; a complexity of $\mathcal{O}(N^2M^2)$

When the filter kernel $h[n,m]$ is separable, such as $h[n,m] = f[n]g[m]$, then in this case the convolution between the image $x[n,m]$ and the filter $h[n,m]$ can be performed without a raw 2D convolution sum, by the following approach:

  1. First, perform a 1D convolution between columns of $x[n,:]$ and the 1D filter $f[n]$, which requires about $N \times M$ MACs to complete. This operation should be performed for each column of $x[n,m]$ by proceeding along its horizontal, $N$ many, columns. Hence a total of $N \times M \times N$ MACs will be required to complete the first step to produce the intermediate image $w[n,m]$
  2. Then, apply the similar algorithm, with the filter $g[m]$ and rows of the intermediate image $w[:,m]$, which will require similar number of MACs as $N \times M \times N$.

Hence as a total you will need about $2N^2M$ MACs for the separable implementation of the 2D convolution. The actual number depends on the cropping type you apply. Thus a complexity of about $\mathcal{O}(N^2M)$ is attained.

It can be seen that, to implement the separable convolution algorithm, you will only need 3 nested for loops, which is where the gain comes from.

The main advantage of separable filtering is quite clear; much reduced computational cost. In fact even the 2D-FFT algorithm makes use of it as the 2D-DFT kernel is separable.

Another advantage is that since there are less number of MACs involved to produce the same output compared to the raw 2D convolution, it's less prone to numerical issues and likely to produce more accurate results.

A disadvantage of separation is that it requires an extra ram memory to store the intermediate image, which can be a concern in certain applications.

$\endgroup$
  • $\begingroup$ Thank you so much for your answers. Quick question, is your filter same size of the image? h[n,m] and image is x[n,m]? $\endgroup$ – OmegaD Aug 26 '18 at 17:40
  • $\begingroup$ No it's not assumed to be so. You can take any size you want, assuming you follow the proper steps in performing the algorithm. $\endgroup$ – Fat32 Aug 26 '18 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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