I am using image filtering for an image processing algorithm I'm developing. I'm using a predefined Matlab function to do the convolution, but I'd like to know what the computational complexity is for this algorithm.The simple way of thinking of this is that an $M \times N$ (grayscale) image and a $m \times n$ filter, each pixel needs $\mathcal{O}(mn)$ computations, so the 2D convolution would have an approximate complexity of $\mathcal{O}(MNmn)$. (Of course it would matter is you're padding the sides of the images or not, but assuming that $m$ and $n$ are small compared to $M$ and $N$, it shouldn't make too much of a difference.)My questionis : Is this true? Is the complexity of 2D convolution $\mathcal{O}(MNmn)$, or are there optimizations that make it less?
Computational Complexity of 2D Convolution
complexity;image processing