# Riconoscimento dei contorni

Il riconoscimento dei contorni (edge detection) è utilizzato allo scopo di marcare i punti di un'immagine digitale in cui l'intensità luminosa cambia bruscamente. Bruschi cambiamenti delle proprietà di un'immagine sono di solito il sintomo di eventi o cambiamenti importanti del mondo fisico di cui le immagini sono la rappresentazione. Questi cambiamenti possono essere ad esempio: discontinuità della profondità, discontinuità dell'orientamento delle superfici, modifica delle proprietà dei materiali, e variazioni dell'illuminazione proveniente dall'ambiente circostante. Il riconoscimento dei contorni è un campo di ricerca del trattamento delle immagini e della visione artificiale, in particolare della branca del riconoscimento delle caratteristiche (feature extraction).
L'operazione di riconoscimento dei contorni genera immagini contenenti molte meno informazioni rispetto a quelle originali, poiché elimina la maggior parte dei dettagli non rilevanti al fine dell'individuazione dei contorni, conservando invece le informazioni essenziali per descrivere la forma e le caratteristiche strutturali e geometriche degli oggetti rappresentati.
Esistono molti metodi per riconoscere i contorni, ma la maggior parte può essere raggruppata in due categorie: metodi basati sulla ricerca (search-based) e metodi basati sull'attraversamento dello zero (zero-crossing). I metodi basati sulla ricerca riconoscono i contorni cercando i massimi ed i minimi della derivata del primo ordine dell'immagine, di solito cercando la direzione in cui si ha il massimo gradiente locale. I metodi zero-crossing cercano i punti in cui la derivata del secondo ordine passa per lo zero, solitamente la funzione laplaciana o un'espressione differenziale di una funzione non-lineare.

## Proprietà dei contorni

I contorni possono essere dipendenti dal punto di osservazione, quando possono cambiare al cambiare del punto di osservazione, rispecchiando la disposizione e la configurazione geometrica dell'ambiente circostante, come, ad esempio, oggetti che si frappongono l'un l'altro, oppure possono essere indipendenti dal punto di osservazione, quando rispecchiano proprietà intrinseche degli oggetti stessi, come ad esempio segni tracciati sulle superfici oppure forme geometriche delle superfici degli oggetti. In due o più dimensioni bisogna tener presenti gli effetti della prospettiva.
Un tipico contorno potrebbe essere, ad esempio, il confine fra un'area di colore rosso ed una gialla, oppure una linea con spessore di pochi pixel e di colore diverso rispetto ad uno sfondo uniformemente colorato. In quest'ultimo caso i contorni sono per l'esattezza due, uno per ciascun lato della linea. I contorni giocano un ruolo molto importante in molte applicazioni di computer vision, anche se, in tempi recenti, in questo campo sono stati fatti sostanziali progressi utilizzando anche altri approcci, che non usano il riconoscimento dei contorni come step preliminare dell'elaborazione.

## Modello matematico semplificato

Nelle immagini reali i contorni non sono quasi mai netti, ma sono solitamente affetti da una o più delle seguenti distorsioni:
* messa a fuoco imperfetta a causa della profondità di campo non infinita dell'ottica dello strumento di acquisizione;
* presenza di ombre sfumate create da sorgenti di illuminazione non puntiformi;
* scale di grigio con cui sono resi gli spigoli arrotondati;
* effetti di specularità o di interriflessione in prossimità degli spigoli.
Il modello qui illustrato, sebbene non perfetto, ha una funzione errore $\operatorname {erf}$ che può essere usata per creare un modello matematico degli effetti dello sfuocamento sufficiente preciso per descrivere molte applicazioni pratiche. Un'immagine mono-dimensionale $f$ con un contorno posizionato esattamente in $0$ può essere rappresentata quindi dalla seguente funzione:
$f(x)={\frac {I_{r}-I_{l}}{2}}\left(\operatorname {erf} \left({\frac {x}{{\sqrt {2}}\sigma }}\right)+1\right)+I_{l}$
Alla sinistra del contorno l'intensità luminosa vale $I_{l}=\lim _{x\rightarrow -\infty }f(x)$, e a destra $I_{r}=\lim _{x\rightarrow \infty }f(x)$; $\sigma$ è chiamato scala di sfuocatura del contorno. Notare che $f$ può essere definita come una convoluzione $f=g_{\sigma }*u$ dove $g_{\sigma }$ è il kernel gaussiano avente deviazione standard $\sigma$, e $u$ è una funzione a gradini definita come:
$u(x):=\left\{{\begin{matrix}I_{l},&\mathrm {se} \;x\leq 0\\I_{r},&\mathrm {altrimenti} \end{matrix}}\right.$

## Tecniche di riconoscimento

Basandosi sul fatto che un contorno consiste in un cambiamento di intensità dell'immagine - che ha luogo gradualmente su un certo numero di pixel - gli algoritmi di riconoscimento solitamente calcolano la derivata di questo cambiamento di intensità. Per semplificare la trattazione consideriamo il riconoscimento di un contorno eseguito percorrendo una linea di pixel - la cui intensità è indicata nella tabella seguente. Esaminando i cambiamenti di intensità fra ciascun pixel ed il successivo, è intuitivo ipotizzare la presenza di un contorno fra il quarto ed il quinto pixel:
| 5 | 7 | 6 | 4 | 152 | 148 | 149 |
Trovare un criterio univoco che stabilisca quanto ampia deve essere la differenza di intensità fra due pixel per poter dire che fra di essi sia presente un contorno, non è tuttavia sempre problema di facile soluzione. Questa è una delle ragioni per cui il riconoscimento dei contorni è spesso difficile, a meno che gli oggetti presenti sulla scena siano di forma geometricamente molto semplice e le condizioni di illuminazione possano essere controllate ed ottimizzate.

## Calcolo della derivata prima

Molti algoritmi di riconoscimento dei contorni operano sulla derivata del primo ordine dell'intensità luminosa - che corrisponde al gradiente dell'intensità dell'immagine di partenza. Basandosi su questo output si può andare alla ricerca dei valori di picco del gradiente dell'intensità.
Se I(x) rappresenta l'intensità del pixel x, e I′(x) rappresenta la derivata prima (gradiente dell'intensità) al pixel x, si ottiene:
    $I'(x)=-1/2\cdot I(x-1)+0\cdot I(x)+1/2\cdot I(x+1).$
Per ottenere i migliori risultati la derivata prima può essere calcolata mediante convoluzione dei dati originari con una maschera:
| −1/2 | 0 | +1/2 |

## Calcolo della derivata seconda

Altri operatori per il riconoscimento dei contorni si basano sul calcolo della derivata seconda dell'intensità, che corrisponde grosso modo alla rapidità di cambiamento del gradiente. Nel caso ideale - in cui l'intensità varia in modo continuo - la derivata seconda si annulla nei punti di massimo del gradiente. Questo metodo, d'altra parte, funziona bene solo se l'immagine è rappresentata in scala opportuna. Come prima spiegato, una linea corrisponde ad un doppio contorno, quindi si avrà un gradiente di intensità su un lato della linea, subito seguito da un gradiente di valore opposto sul lato opposto. Per questo motivo ci si può attendere di avere grandi variazioni del gradiente in immagini contenenti linee.
Se I(x) rappresenta il valore dell'intensità nel punto x, e I"(x) è la derivata seconda nel punto x, allora vale la relazione:
    $I''(x)=1\cdot I(x-1)-2\cdot I(x)+1\cdot I(x+1).$
Come già detto, la maggior parte degli algoritmi usano una maschera di convoluzione per elaborare più velocemente le immagini:
| +1 | −2 | +1 |

### Sogliatura

Dopo aver calcolato la derivata, il passo successivo è applicare una sogliatura, per valutare i punti dell'immagine in cui potrebbe essere presente un contorno. Più bassa è la soglia, più linee verranno individuate, ed i risultati diverranno sempre più affetti da disturbi causati dal rumore di fondo, con conseguenti maggiori possibilità di falsi riconoscimenti. Più alta è la soglia e più ci sarà il rischio di non rilevare contorni formati da linee sottili o segmentate. Per cercare di ovviare a questi due opposti inconvenienti si usa spesso il metodo della sogliatura adattiva con isteresi, che usa soglie multiple per trovare i contorni. Si comincia ad applicare la soglia superiore per trovare il punto iniziale di una linea di contorno, dopodiché si cerca il percorso della linea pixel per pixel, attribuendo i pixel man mano incontrati al contorno ogni volta che si supera la soglia inferiore. La ricerca si arresta solamente quando il valore cade al di sotto della soglia inferiore. Questo approccio si basa sull'ipotesi che i contorni sono normalmente costituiti da linee continue, e consente di percorrere la parte meno marcata di una linea di contorno riducendo il rischio che tutti i pixel estranei siano erroneamente attribuiti al contorno.

## Operatori per il riconoscimento dei contorni

* Operatori del primo ordine: Roberts, Prewitt, Sobel
* Operatori del secondo ordine: Marr-Hildreth, passaggio per lo zero della derivata del secondo ordine nella direzione del gradiente (Zero crossing).
Attualmente l'algoritmo di Canny - e le sue varianti - sono il metodo più usato per il riconoscimento dei contorni. Nessuno dei numerosi altri metodi proposti successivamente si è finora dimostrato più efficace, salvo che in applicazioni molto specifiche. Nel suo lavoro originario, Canny si proponeva di trovare un filtro che eliminasse i disturbi presenti nell'immagine (ovvero un filtro di smoothing), filtro che potesse essere ben approssimato da una kernel gaussiano del primo ordine. Canny introdusse anche la nozione di soppressione dei non-massimi, cioè l'assunto che i punti dei contorni sono quelli in cui il gradiente raggiunge il valore massimo nella direzione stimata del gradiente. La ricerca dei non-massimi in una griglia di punti può essere implementata calcolando la direzione del gradiente con la derivata prima, arrotondando la direzione trovata a multipli di 45°, e infine confrontando con i valori di ampiezza del gradiente nella direzione calcolata. Un metodo più accurato per ricercare i contorni con precisione maggiore del pixel è usare la seguente espressione differenziale per trovare il passaggio per lo zero della derivata del secondo ordine nella direzione del gradiente (Lindenberg 1998)
    $L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy}+L_{y}^{2}\,L_{yy}=0,$
che soddisfa l'uguaglianza del segno della derivata del terzo ordine nella stessa direzione
    $L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\,L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}<0$
dove $L_{x}$, $L_{y}$ ... $L_{yyy}$ rappresentano le derivate parziali calcolate in una rappresentazione spaziale multi-scala (scale-space) $L$ ottenuta sfuocando l'immagine originaria con un kernel gaussiano. Con questo procedimento, i contorni saranno ottenuti automaticamente come curve continue con precisione del sub-pixel. Anche la sogliatura con isteresi può essere applicata a segmenti sub-pixel.

## Riduzione dei disturbi

La ricerca dei contorni è complicata dai falsi riconoscimenti provocati da disturbi presenti nelle immagini. Per ridurre il numero dei falsi contorni si possono sottoporre preliminarmente le immagini a tecniche di riduzione dei disturbi (noise reduction).