Tempo di complessità del rilevatore di bordo Canny

Question

Attualmente sto scrivendo un documento di ricerca su un nuovo algoritmo di steganografia. Ho usato il rilevatore di bordi canny a un certo punto del mio algoritmo. Nel documento ho bisogno di scrivere la complessità temporale del nuovo approccio, che a sua volta dipende dalla complessità temporale del rilevatore di bordi canny.

Il problema è che da nessuna parte sul web ho potuto trovare alcun riferimento sulla complessità temporale di Canny. Ho persino letto la carta canny originale. Non riesco a dedurlo correttamente e ho bisogno di aiuto qui.

Answer 1

Algoritmo di Canny costituito da

1. Una convoluzione dell'immagine con un kernel sfocatura,
2. Quattro circonvoluzioni dell'immagine con rivelatore bordo kernel,
3. calcolo della direzione del gradiente,
4. Soppressione non massima e
5. Soglia con isteresi,

I passaggi (1), (2), (3) e (4) sono tutti implementati in termini di convoluzioni dell'immagine con kernel di dimensioni fisse. Utilizzando la FFT, è possibile implementare le convoluzioni nel tempo O (n log n), dove n è il numero di elementi. Se l'immagine ha dimensioni m × n, la complessità temporale sarà O (mn log mn) per questi passaggi.

Il passaggio finale funziona postelaborando l'immagine per rimuovere tutti i valori alti e bassi, quindi eliminare tutti gli altri pixel che non sono vicini ad altri pixel. Questo può essere fatto nel tempo O (mn).

Pertanto, la complessità del tempo complessivo è O (mn log mn).

Spero che questo aiuti!