Zeit Komplexität von Canny Kantendetektor

Question

Ich schreibe gerade eine Forschungsarbeit über einen neuen Steganographie-Algorithmus. Ich habe irgendwann in meinem Algorithmus einen schlauen Kantendetektor benutzt. In der Arbeit muss ich die Zeitkomplexität des neuartigen Ansatzes schreiben, der wiederum von der Zeitkomplexität des schiefen Kantendetektors abhängt.

Problem ist, dass nirgends im Web ich einen Hinweis auf die Zeit Komplexität von canny finden konnte. Ich habe sogar das originale Papier gelesen. Ich kann es nicht richtig ableiten und brauche hier Hilfe.

Answer 1

Canny-Algorithmus besteht aus

1. eine Faltung des Bildes mit einem Unschärfe-Kernel,
2. vier Faltungen des Bildes mit Flankendetektor Kernen,
3. Berechnung der Gradientenrichtung,
4. Nicht-maximale Unterdrückung und
5. Schwellenwertbildung mit Hysterese,

Die Schritte (1), (2), (3) und (4) sind alle in Form von Faltungen des Bildes mit Kernen einer festen Größe implementiert. Mit der FFT ist es möglich, Faltungen in der Zeit O (n log n) zu implementieren, wobei n die Anzahl der Elemente ist. Wenn das Bild die Dimensionen m × n hat, ist die Zeitkomplexität O (mn log mn) für diese Schritte.

Der letzte Schritt besteht in der Nachbearbeitung des Bildes, um alle hohen und niedrigen Werte zu entfernen und dann alle anderen Pixel, die nicht in der Nähe anderer Pixel sind, fallenzulassen. Dies kann in der Zeit O (mn) erfolgen.

Daher ist die gesamte Zeitkomplexität O (mn log mn).

Hoffe, das hilft!