Basic Complexity Question - Convolution

Question

Hi All,

I'm trying to evaluate the complexity of some basic image filtering algorithms. I was wondering if you could verify this theory;

For a basic pixel by pixel filter like Inverse the number of operations grows linearly with the size of the input (In pixels) and

Let S = Length of the side of the image Let M = # pixels input

Inverse is of order O(M) or O(S^2).

A convolution filter on the other hand has a parameter R which determines the size of the neighborhood to convolve in establishing the next pixel value for each filter.

Let R = Radius of convolution filter

Convolution is of order O(M*((R+R*2)^2) = O(M*(4R^2) = O(MR^2)

Or should I let N = the size of the convolution filter (Neighbourhood) in pixels?

O(M*(N)) = O(MN)

Ultimately a convolution filter is linearly dependent on the product of the number of pixels and the number of pixels in the neighbourhood.

If you have any links to a paper where this has been documented it would be greatly appreciated.

Kind regards,

Gavin

Answer 1

O(MN) seems right if I understand that for each pixel in the image the convolution is the adjustment of pixel values in the neighbourhood N, regardless of N being square. N could be best-fit triangle ... but providing the pixels in the neighbourhood are adjusted for each pixel in the image then O(MN) makes more sense, because the dependency is in the pixels adjusted per pixel in the source image.

Interestingly, in a non-regular neighbourhood some pixels may be adjusted by the neighbourhood mask more than others, but O(MN) will still stand.

If the neighbourhood is central on a pixel P and then moved to the next P which was not in the neighbourhood (meaning each pixel is transformed once) then this doesn't stand.