Trasformata di Hough

Figura 3.2: Esempio di Trasformata di Hough per individuare rette in coordinate polari: mappa accumulatore (in alto a destra) di un singolo punto (in alto a sinistra), e mappa accumulatore (in basso a destra) di una serie di punti colineari insieme ad outlier (in basso a sinistra).

Sia $g(\mathbf{x})=0$ una funzione (il modello) di cui si conosce la struttura ma che per definirla complementamente è necessario ottimizzare alcuni parametri $\boldsymbol\beta$. Per definirla completamente si conoscono delle coordinate $\mathbf{x}$ che dovrebbero appartenere al luogo dei punti della funzione, potenzialmente affetti da rumore. La funzione pertanto si può scrivere come $g(\boldsymbol\beta, \mathbf{x})=0$ con $\mathbf{x}$ i vincoli e $\boldsymbol\beta$ gli eventuali parametri del modello da stimare.

Siano pertanto $\beta_1 \ldots \beta_m$ parametri da stimare, quantizzabili e limitati, e sia $\beta_1$ un parametro tale che si possa scrivere la funzione $g$ come

$$\beta_1 = f(\beta_2 \ldots \beta_n, \mathbf{x})$$ (3.40)

Se la funzione $g$ è esprimibile come in equazione 3.40, è possibile attraverso il metodo della trasformata di Hough stimare i parametri $\boldsymbol\beta$ che rappresentano il modello più probabile dati i valori $\mathbf{x}$ con cui addestrare il modello. Per ogni elemento $\mathbf{x}$ è possibile far variare i parametri $\beta_2 \ldots \beta_n$ nel loro intervallo e inserire in una immagine accumulatore i valori di $\beta_1$ restituiti dalla funzione 3.40. In questo modo è possibile generare una mappa n-dimensionale di probabilità usando osservazioni $\mathbf{x}$ affette da errore ma soprattutto che possono essere sia Inliers che Outliers. Il metodo di Hough in questo caso riporta il modello più probabile tra le osservazioni in ingresso ed è molto robusto verso gli outliers. Allo stesso modo il metodo di Hough permette di stimare un modello in presenza di una mistura di modelli con parametri differenti.

Normalmente risulta interessante l'uso di Hough dove il modello ha solo 2 parametri in quanto facilmente graficabile su una mappa bidimensionale.

Per esempio, nel caso molto comune in cui $g$ (il modello) sia una retta, espressa come in equazione 1.19, dove i parametri da ricavare sono $\theta$ e $\rho$, risulta evidente che per ogni coppia di punti $(x,y)$ e per tutti i possibili angoli di $\theta$ quantizzati (in quanto angolo è un parametro limitato) esiste uno e un solo $\rho$ che soddisfa l'equazione 1.19.

È pertanto possible creare mappa in $(\theta,\rho)$ dove per ogni punto $(x,y)$ e per ogni $\theta$ viene incrementata sulla mappa accumulatore l'elemento associato a $(\theta, \cos \theta x + \sin \theta y )$, relazione che soddisfa l'equazione 1.19.