Find the optimal way for the convolution

Question

Based on my code on Gabor filter, this Gabor, as its name suggests, is used to filter an image and Highlight everything that it is oriented in the same direction of the filtering.

By the way, it exists some ways to convolve an image with this Gabor:

• The image can be convolved directly with the Gabor by using the 2-D convolution. But all we know that the 2-D convolution needs a lot of computations. So if we consider an image of size MxN and a filter size PxQ, so to achieve the 2-D convolution, we need MN X PQ multiplications and additions. Thus, convolution 2D is very expensive to perform multiply and accumulate operation.

• in the other hand, we take advantage of separable convolution. So the filter can be firstly separable, then we could have replace the point wise 2D convolution, with two 1D convolutions corresponding to convolution in x-direction and in the y-direction. In this case, we reduce the complexity of computations to MNP+MNQ = (MN(P+Q)) multiplies and adds.

• But the principle problem with separable Gabor filter is convolution in complex domain. So we can treat this Gabor as a two dimensional matrix that has a low rank. So Singular Value Decomposition (SVD) can then be used.

Are there another ways to convolve the image with the Gabor in order to more reduce the complexity of computations? can we find another method more optimal than SVD ? Can apply some operations to the image before filtering? Please I need all your appreciated opinions.

Can I use for example the Gabor wavelets instead? does the Gabor wavelet is more optimal than the normal Gabor ?

Answer 1

To my knowledge, separate the Gabor filter may be both the least space complexity (O(2N^2)) and time complexity (O(6MN^2)), where M and N are the width of the filter mask and the image respectively. This is achieved by separate the exponential part with only u2 from the original function with both u1 and u2. In this paper, the author compared different implementation of Gabor filters.

I don't think SVD is a good choice combined with Gabor filter. If the mask size is small, SVD won't help a lot but compromise the performance; if the mask size is large, SVD is time consuming as well.