Algoritmo di Canny

Nell'elaborazione di immagini, l'algoritmo di Canny è un operatore per il riconoscimento dei contorni (edge detection) ideato nel 1986 da John F. Canny. Utilizza un metodo di calcolo multi-stadio per individuare contorni di molti dei tipi normalmente presenti nelle immagini reali. Canny ha anche prodotto una teoria del riconoscimento dei contorni che si propone di spiegare i fondamenti di questa tecnica.

Sviluppo dell'algoritmo di Canny

Lo scopo di Canny era quello di trovare il miglior algoritmo possibile per riconoscere i contorni delle immagini. In questo contesto "migliore" può significare:

buon riconoscimento - l'algoritmo deve individuare e "marcare" quanti più contorni possibile nell'immagine
buona localizzazione - i contorni marcati devono essere il più vicini possibile ai contorni reali dell'immagine.
risposta minima - un dato contorno dell'immagine deve essere marcato una sola volta, e, se possibile, il rumore presente nell'immagine non deve provocare il riconoscimento di falsi contorni.

Per soddisfare questi requisiti Canny ha usato il calcolo delle variazioni, una tecnica basata sulla ricerca della funzione che ottimizza un dato funzionale. La funzione ottimale è definita come somma di quattro termini esponenziali, ma può essere approssimata dalla derivata prima di una funzione gaussiana.

Fasi di elaborazione dell'algoritmo di Canny

Riduzione del rumore

Per il riconoscimento dei contorni l'algoritmo di Canny usa un filtro basato sulla derivata prima di una gaussiana, e quindi i risultati prodotti sono disturbati dal rumore presente nei dati di un'immagine "grezza" (raw image). Per questo motivo, prima di iniziare l'elaborazione, l'immagine raw viene sottoposta a convoluzione con un filtro gaussiano. Il risultato è un'immagine con una leggera "sfocatura" gaussiana, in cui nessun singolo pixel è affetto da disturbi di livello significativo.

Ricerca del gradiente della luminosità di un'immagine

Un contorno di un'immagine può puntare verso una direzione qualsiasi, quindi l'algoritmo di Canny usa quattro filtri differenti per individuare i contorni orizzontale, verticale e diagonali dell'immagine, a cui è stato precedentemente applicato il filtro gaussiano. Per ciascun pixel risultante viene assunta come valida la direzione relativa al filtro che dà il valore maggiore. Questa direzione, combinata col valore ottenuto applicando il filtro, corrisponde a quella in cui si ha il massimo gradiente di luminosità in ciascun punto dell'immagine.

Soppressione dei non-massimi

La mappa dei gradienti fornisce il valore dell'intensità luminosa in ciascun punto dell'immagine. Una forte intensità indica una forte probabilità della presenza di un contorno. Tuttavia, questa indicazione non è sufficiente a decidere se un punto corrisponde oppure no ad un contorno. Solo i punti corrispondenti a dei massimi locali sono considerati come appartenenti ad un contorno, e saranno presi in considerazione dai successivi step di elaborazione. Un massimo locale si ha nei punti in cui la derivata del gradiente si annulla.

Individuazione dei contorni mediante sogliatura con isteresi

L'estrazione dei contorni dalla mappa generata dallo step precedente si esegue con un procedimento chiamato sogliatura con isteresi. Vengono definite due soglie, una bassa ed una alta, che vengono confrontate con il gradiente in ciascun punto. Se il valore del gradiente è:

inferiore alla soglia bassa, il punto è scartato;
superiore alla soglia alta, il punto è accettato come parte di un contorno;
compreso fra le due soglie, il punto è accettato solamente se contiguo ad un punto già precedentemente accettato.

La presenza di due soglie (da cui il riferimento all'isteresi) è giustificato dal fatto che è praticamente impossibile trovare un unico valore del gradiente di luminosità per discriminare se un punto appartiene o no ad un contorno. Al termine di questo step si ottiene un'immagine binaria dove ciascun pixel è marcato come appartenente o no ad un contorno. La mappa ottenuta in questo modo può essere trattata come un insieme di curve di contorno che, previa ulteriore elaborazione, può essere approssimato da una poligonale.

Parametri

L'algoritmo di Canny si basa su parametri che possono influenzare sia il tempo di elaborazione che la stessa qualità dei risultati prodotti. I parametri sono:

Dimensione del filtro gaussiano: il filtro sfuocatore applicato nel primo step di elaborazione influenza direttamente i risultati generati dall'algoritmo. Filtri più piccoli producono una minore sfuocatura, e permettono di riconoscere contorni più netti. Filtri più grandi producono una maggiore sfuocatura, facendo debordare i singoli pixel su aree più estese, e sono più indicati per riconoscere contorni più ampi e più sfumati - come ad esempio il contorno di un arcobaleno.
Soglie applicate: l'uso di due soglie con isteresi garantisce una maggior flessibilità rispetto alla soglia singola, ma non risolve tutti i problemi insiti nell'applicazione di un filtro di questo tipo. Una soglia settata ad un valore troppo alto può provocare la perdita di informazioni significative, mentre una soglia settata ad un valore troppo basso può far sì che informazioni irrilevanti - ad esempio semplici disturbi - possano essere interpretate come elementi importanti dell'immagine. È difficile trovare un valore generico di soglia che possa andar bene per tutte le immagini, ed in effetti non è stato ancora trovato un approccio che dia sempre risultati soddisfacenti.

Conclusioni

L'algoritmo di Canny può essere personalizzato per adattarsi a vari tipi di immagini. La possibilità di accettare parametri consente il riconoscimento di contorni con aspetto diverso, come spesso è richiesto in applicazioni specifiche. Nella formulazione originale l'operazione di derivazione comportava un filtraggio di tipo Finite impulse response, molto pesante in termini di potenza di calcolo necessaria, soprattutto quando l'entità dell'offuscamento necessario nel primo step di elaborazione è grande. Per questo motivo si usa spesso una variante del filtro di Canny, di tipo Infinite impulse response ricorsivo, che richiede tempi di elaborazione minori e predeterminati, in funzione dall'entità dell'offuscamento richiesto. Questa seconda opzione è adatta ad essere implementata in dispositivi che utilizzano FPGAs o DSP, oppure PC embedded molto prestanti. In questo contesto, comunque, l'implementazione ricorsiva dell'algoritmo di Canny non produce una buona approssimazione in tutte le direzioni, e quindi privilegia il riconoscimento di contorni disposti in direzione orizzontale e verticale.

Note

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su Algoritmo di Canny

Collegamenti esterni

(EN) John Canny's home page, su cs.berkeley.edu.
(EN) Edge detector di Canny On-line, su matlabserver.cs.rug.nl. URL consultato il 18 gennaio 2008 (archiviato dall'url originale il 15 giugno 2009).
(EN) Implementazione free Java dell'edge detector di Canny, su tomgibara.com. URL consultato il 18 gennaio 2008 (archiviato dall'url originale il 3 luglio 2011).
(EN) Pubblicazioni di Rachid Deriche, su www-sop.inria.fr.
(EN) Test on-line sull'uso dei parametri con l'algoritmo di Canny, su matlabserver.cs.rug.nl. URL consultato il 18 gennaio 2008 (archiviato dall'url originale il 15 giugno 2009).

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica