Rilevatore di Harris

Il rilevatore di Harris è un rilevatore di angoli introdotto da Chris Harris e Mike Stephens nel 1988, estensione del rilevatore di Moravec che ne migliora l'accuratezza nel distinguere gli angoli dai bordi.

Benché sia stato sopravanzato da altri rilevatori come SIFT, SURF e ORB, il rilevatore di Harris rimane un algoritmo importante in visione artificiale, del quale esistono diverse estensioni, e ha applicazioni in registratura, mosaicizzazione, ricostruzione tridimensionale, rilevamento del movimento, riconoscimento di oggetti, image retrieval e video tracking.

Descrizione

In un'immagine digitale, un angolo è un punto $P$ che si trova all'intersezione di due bordi, ovvero il gradiente dell'intensità in un intorno di $P$ presenta due direzioni dominanti distinte. Gli angoli sono caratteristiche importanti in un'immagine e contengono informazioni per rappresentarne il contenuto in molti problemi di visione artificiale.

Il rilevatore di Harris determina l'angolarità di un punto analizzando il cambiamento di intensità in un intorno del punto in funzione di una traslazione dell'intorno. Data un'immagine digitale $I$ in scala di grigi e un intorno $W$ centrato in $(x,y)$, se $W$ è soggetto a una traslazione $(\mathrm{\Delta }x,\mathrm{\Delta }y)$ la somma dei quadrati residui $SSD(\mathrm{\Delta }x,\mathrm{\Delta }y)$ dell'intensità tra $W$ e la sua traslazione assumerà un valore elevato se la direzione $(\mathrm{\Delta }x,\mathrm{\Delta }y)$ è ortogonale a un bordo, o un valore piccolo se l'intorno del punto è una regione piatta o se $(\mathrm{\Delta }x,\mathrm{\Delta }y)$ è parallela a un bordo.

Se si considerano tutte le possibili direzioni di traslazione, il punto in analisi è probabilmente parte di una regione piatta se la $SSD$ ha un valore limitato in ogni direzione, è probabilmente situato in prossimità di un bordo se la $SSD$ ha un valore dominante in una direzione (ortogonale al bordo), oppure è probabilmente situato in prossimità di un angolo se la $SSD$ assume valori elevati in ogni direzione.

La somma dei quadrati residui può essere espressa come

$SSD(\mathrm{\Delta }x,\mathrm{\Delta }y)=\sum (x_k,y_k)\in W{(I(x_k,y_k)-I(x_k+\mathrm{\Delta }x,y_k+\mathrm{\Delta }y))}^2.$

Approssimando $I(x+\mathrm{\Delta }x,y+\mathrm{\Delta }y)$ con un'espansione in serie di Taylor, dove $I_x$ e $I_y$ sono le derivate parziali dell'intensità $I$

$I(x+\mathrm{\Delta }x,y+\mathrm{\Delta }y)\approx I(x,y)+I_x(x,y)\mathrm{\Delta }x+I_y(x,y)\mathrm{\Delta }y$

si ottiene che

$SSD(\mathrm{\Delta }x,\mathrm{\Delta }y)\approx \sum (x,y)\in W{(I_x(x,y)\mathrm{\Delta }x+I_y(x,y)\mathrm{\Delta }y)}^2,$

che può essere riscritta in forma matriciale come

$SSD(\mathrm{\Delta }x,\mathrm{\Delta }y)\approx \left(\begin{array}{cc}\mathrm{\Delta }x& \mathrm{\Delta }y\end{array}\right)M\left(\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }y\end{array}\right),$

dove $M$ è noto come tensore di struttura

$M=\sum (x,y)\in W\left[\begin{array}{cc}{I}_x^2& I_x{I}_y\\ I_x{I}_y& I_y^2\end{array}\right]=\left[\begin{array}{cc}\sum (x,y)\in W{I}_x^2& \sum (x,y)\in W{I}_x{I}_y\\ \sum (x,y)\in W{I}_x{I}_y& \sum (x,y)\in W{I}_y^2\end{array}\right].$

Gli autovettori del tensore di struttura determinano le direzioni di massima e minima variazione della somma dei quadrati residui, e i corrispondenti autovalori ${\lambda }_1$ e ${\lambda }_2$ quantificano la variazione lungo le rispettive direzioni. Se entrambi gli autovalori sono piccoli, la SSD ha valori piccoli in ogni direzione e il punto in analisi è probabilmente parte di una regione piatta, se un autovalore è significativamente maggiore dell'altro, la SSD ha una direzione dominante e il punto è probabilmente locato in prossimità di un bordo, mentre se entrambi gli autovalori sono elevati la SSD ha valori elevati in ogni direzione e il punto è probabilmente locato in prossimità di un angolo.

Per quantificare l'angolarità di un punto viene definita una funzione di risposta $R$

$R=\det (M)-k(\mathrm{tr}(M){)}^2={\lambda }_1{\lambda }_2-k({\lambda }_1+{\lambda }_2{)}^2$

dove $k$ è una costante, empiricamente determinata come $k\in [0.04,0.06]$.

L'algoritmo di Harris può essere riassunto come:

1. conversione dell'immagine in scala di grigi;
2. riduzione del rumore tramite un filtro Gaussiano;
3. approssimazione del gradiente tramite l'operatore di Sobel;
4. per ogni pixel dell'immagine, calcolo della funzione di risposta $R$ in un intorno di dimensione $3\times 3$;
5. determinazione dei punti di massimo locale di $R$, che rappresentano gli angoli rilevati nell'immagine.

Voci correlate

• Rilevamento di caratteristiche
• Riconoscimento di angoli
• Tensore di struttura

Collegamenti esterni

• Learn OpenCV by Examples : Harris Corner Detection
• Harris Corner Detection - OpenCV Documentation
• Introduction to Harris Corner Detector
• Harris Corner Detection - OpenCV-Python Tutorials Template:Webarchive
• Online Implementation of the Harris Corner Detector - IPOL