I'm still confused as to why the cost of convolution with a separable filter is 2xNxM^2. Can someone explain this to me more in depth?
kyriaki
A separable filter can be decomposed as a column vector and a row vector as shown in the slide. Applying the separable filter (a matrix) to an image is equivalent to first applying the column vector and then applying the row vector. Applying the column vector to a pixel takes O(N), and there are MxM pixels. Therefore, overall NxMxM. Same for applying the row vector to all pixels. Therefore, overall you get 0(NxMxM) + O(NxMxM), which is O(2xNxM^2). Hope this helps :)
I'm still confused as to why the cost of convolution with a separable filter is 2xNxM^2. Can someone explain this to me more in depth?
A separable filter can be decomposed as a column vector and a row vector as shown in the slide. Applying the separable filter (a matrix) to an image is equivalent to first applying the column vector and then applying the row vector. Applying the column vector to a pixel takes O(N), and there are MxM pixels. Therefore, overall NxMxM. Same for applying the row vector to all pixels. Therefore, overall you get 0(NxMxM) + O(NxMxM), which is O(2xNxM^2). Hope this helps :)