Time complexity of Canny edge detector

Question

I am currently writing a research paper about a new steganography algorithm. I have used canny edge detector at some point in my algorithm. In the paper I need to write the time complexity of the novel approach, which in turns depends on the time complexity of canny edge detector.

Problem is that nowhere on the web I could find any reference about the time complexity of canny. I've even read the original canny paper. I am unable to deduce it properly and need some help here.

Answer 1

Canny edge detection consists of

1. A convolution of the image with a blur kernel,
2. Four convolutions of the image with edge detector kernels,
3. Computation of the gradient direction,
4. Non-maximum suppression, and
5. Thresholding with hysteresis,

Steps (1), (2), (3), and (4) are all implemented in terms of convolutions of the image with kernels of a fixed size. Using the FFT, it's possible to implement convolutions in time O(n log n), where n is the number of elements. If the image has dimensions m × n, the time complexity will be O(mn log mn) for these steps.

The final step works by postprocessing the image to remove all the high and low values, then dropping all other pixels that aren't near other pixels. This can be done in time O(mn).

Therefore, the overall time complexity is O(mn log mn).

Hope this helps!