Förstner-Harris

L'algoritmo di Förstner-Harris (FG87,HS88) è stato esplicitamente progettato per ottenere un'elevata stabilità geometrica dei punti caratteristici. L'idea alla base del metodo è individuare punti per i quali una piccola traslazione dell'intorno produce una variazione significativa dell'errore ai minimi quadrati tra la finestra originale e la sua versione traslata. Questo algoritmo ha avuto così tanto successo perché permette di caratterizzare le variazioni dell'intensità dell'immagine nell'intorno di un punto attraverso il tensore di struttura (matrice di autocorrelazione), costruito a partire dalle derivate prime dell'immagine.

Si definiscano le immagini dei gradienti (queste possono essere generate da un operatore differenziale, Sobel, Prewitt o Roberts) $I_x(x,y)$ e $I_y(x,y)$ rispettivamente gradiente orizzontale e gradiente verticale dell'immagine da analizzare.

Da queste due immagini è possibile calcolare una funzione $\mathbf{C}(x,y)$^6.1 delle immagini dei gradienti in un intorno di $(x,y)$, definita come

$$\mathbf{C}(x,y)=\begin{bmatrix} \sum_{\boldsymbol\delta... ...y(\boldsymbol\delta) w(\boldsymbol\delta) \\ \end{bmatrix}$$ (6.3)

con $\boldsymbol\delta \in \Omega$ intorno di $(x,y)$ e $w(\boldsymbol\delta)$ un kernel opzionale, normalmente o una gaussiana centrata in $(x,y)$, per permettere di pesare in maniera differente i punti nell'intorno, o una finestra costante su $\Omega$. Originariamente $w(\boldsymbol\delta)$ erano filtri molto piccoli ma, man mano che la potenza di calcolo è aumentata, si è passati a kernel gaussiani via via maggiori.

Di fatto in Harris si usano due filtri di convoluzione: uno derivativo per calcolare le immagini derivate e uno integrale per calcolare gli elementi della matrice. La dimensione di questi filtri e l'utilizzo di filtro gaussiano per pesare i punti rimanda alla lettura della sezione seguente riguardo la scala di individuazione delle feature.

La matrice $\mathbf{C}$ è la matrice dei momenti del secondo ordine. Per individuare punti caratteristici si possono analizzare gli autovalori $\lambda_0$ e $\lambda_1$ della matrice $\mathbf{C}$ (si legga per una trattazione più approfondita la sezione 2.9.1). Gli autovalori della matrice di auto-correlazione $\mathbf{C}$ permettono di caratterizzare il tipo di immagine contenuta nella finestra intorno al punto dato.

La matrice $\mathbf{C}$ rappresenta pertanto la distribuzione locale dei gradienti dell'immagine intorno al punto considerato. I suoi autovalori forniscono una misura della variazione dell'intensità lungo due direzioni ortogonali e costituiscono la base teorica degli operatori di Harris, Shi-Tomasi e del tracker Kanade-Lucas-Tomasi.

Se sono presenti due autovalori molto elevati il punto è un corner, se è presente un solo autovalore di valore elevato è un edge, altrimenti è una zona ragionevolmente piatta, ovvero in forma di funzione come

$$C = \min( \lambda_0, \lambda_1 )$$ (6.4)

i cui massimi locali rappresentano i corner ricavati dall'algoritmo di Shi-Tomasi (ST94).

Per una matrice $2 \times 2$ gli autovalori si ottengono come soluzioni del polinomio caratteristico quadratico

$$p(x) = x^2 - \trace (\mathbf{C}) x + \det(\mathbf{C})$$ (6.5)

Harris, per evitare di calcolare esplicitamente gli autovalori di $\mathbf{C}$, introduce un operatore $H(x,y)$ definito come

$$H(x,y) = \det(\mathbf{C}) - \alpha \trace (\mathbf{C})^{2}$$ (6.6)

dove $\alpha$ è un parametro compreso tra $0$ e $0.25$ e solitamente posto a $0.04$.

Figura 6.1: Risposta nel piano degli autovalori fornita dall'equazione di Harris a diversi valori della soglia avendo posto $\alpha =0.04$. L'area interessata è molto simile a quella fornita dal metodo di Shi-Tomasi ma senza la necessità di calcolare esplicitamente gli autovalori.

Per Harris il punto $(x,y)$ è un punto caratteristico (corner) se $H(x,y) > H_{thr}$, con $H_{thr}$ soglia da definire. Il parametro $\alpha$ regola la sensitività del rilevatore di feature. Qualitativamente alzare $\alpha$ rimuove i bordi mentre alzare $H_{thr}$ rimuove le zone piatte (figura 6.1).

Footnotes

...#tex2html_wrap_inline16755#^6.1

In letteratura questa matrice è nota indifferentemente come matrice di auto-correlazione (specialmente nel contesto originario di Harris), matrice dei momenti del secondo ordine (per il suo legame con la statistica dei gradienti) o tensore di struttura (Structure Tensor) termine oggi molto diffuso nelle trattazioni più formali.