Förstner-Harris

L'algoritmo di Förstner-Harris (HS88,FG87) è stato esplicitamente disegnato per ottenere una elevata stabilità geometrica. Esso definisce punti caratteristici quei punti che hanno un massimo locale nel confronto ai minimi quadrati alla propria versione sottoposta a traslazione. Questo algoritmo ha avuto così tanto successo perchè permette di individuare le variazione dell'intensità dell'immagine nell'intorno di un punto usando la matrice di auto-correlazione tra le derivate prime dell'immagine.

Si definiscano le immagini dei gradienti (queste possono essere generate da un operatore differenziale, Sobel, Prewit 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)$, rappresentate la matrice di covarianza (autocorrelazione) 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}$$ (5.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.10.1). Gli autovalori della matrice di auto-correlazione $\mathbf{C}$ permettono di caratterizzare il tipo di immagine contenuta nella finestra intorno al punto dato.

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 )$$ (5.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})$$ (5.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}$$ (5.6)

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

Figura 5.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 5.1).