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^[1] che ne migliora l'accuratezza nel distinguere gli angoli dai bordi.^[2]

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,^[3]^[4]^[5]^[6]^[7] e ha applicazioni in registratura,^[8] mosaicizzazione,^[9] ricostruzione tridimensionale,^[10] rilevamento del movimento,^[11] riconoscimento di oggetti,^[12] image retrieval^[13] e video tracking.^[14]

Descrizione[modifica | modifica wikitesto]

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.^[15] 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 $(\Delta x,\Delta y)$ la somma dei quadrati residui $SSD(\Delta x,\Delta y)$ dell'intensità tra $W$ e la sua traslazione assumerà un valore elevato se la direzione $(\Delta x,\Delta y)$ è ortogonale a un bordo, o un valore piccolo se l'intorno del punto è una regione piatta o se $(\Delta x,\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(\Delta x,\Delta y)={\underset {(x_{k},y_{k})\in W}{\sum }}\left(I(x_{k},y_{k})-I(x_{k}+\Delta x,y_{k}+\Delta y)\right)^{2}.

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

I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y

si ottiene che

SSD(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2},

che può essere riscritta in forma matriciale come

SSD(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},

dove $M$ è noto come tensore di struttura^[1]

M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}.

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(\operatorname {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:^[16]^[17]^[18]

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

Note[modifica | modifica wikitesto]

^ ^a ^b Chris Harris and Mike Stephens, A Combined Corner and Edge Detector, in Alvey Vision Conference, vol. 15, 1988.
^ Nilanjan Dey, A Comparative Study between Moravec and Harris Corner Detection of Noisy Images Using Adaptive Wavelet Thresholding Technique, 2012, arXiv:1209.1558.
^ F. Bellavia, D. Tegolo e C. Valenti, Improving Harris corner selection strategy, in IET Computer Vision, vol. 5, n. 2, 1º marzo 2011, p. 87, DOI:10.1049/iet-cvi.2009.0127.
^ (EN) Edward Rosten e Tom Drummond, Machine Learning for High-Speed Corner Detection, a cura di Leonardis Aleš, Lecture Notes in Computer Science, Springer Berlin Heidelberg, 7 maggio 2006, pp. 430-443, DOI:10.1007/11744023_34, ISBN 978-3-540-33832-1.
^ A Comparison of Affine Region Detectors, su scholar.google.com. URL consultato il 29 novembre 2015.
^ L. Gueguen e M. Pesaresi, Multi scale Harris corner detector based on Differential Morphological Decomposition, in Pattern Recognition Letters, vol. 32, n. 14, 2011, pp. 1714-1719, DOI:10.1016/j.patrec.2011.07.021.
^ A Multi-scale Bilateral Structure Tensor Based Corner Detector, su scholar.google.com. URL consultato il 29 novembre 2015.
^ Juan Kang, Chuangbai Xiao, M. Deng, Jing Yu e Haifeng Liu, Image registration based on harris corner and mutual information, in 2011 International Conference on Electronic and Mechanical Engineering and Information Technology (EMEIT), vol. 7, 1º agosto 2011, pp. 3434-3437, DOI:10.1109/EMEIT.2011.6023066, ISBN 978-1-61284-087-1.
^ Underwater Mosaic Creation using Video sequences from Different Altitudes, su scholar.google.com. URL consultato il 2 dicembre 2015.
^ Automated reconstruction of 3D scenes from sequences of images, su scholar.google.com. URL consultato il 2 dicembre 2015.
^ Meng Liu, Chengdong Wu e Yunzhou Zhang, Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature, in Control and Decision Conference, 2008. CCDC 2008. Chinese, 1º luglio 2008, pp. 5287-5291, DOI:10.1109/CCDC.2008.4598340, ISBN 978-1-4244-1733-9.
^ Object Recognition from Local Scale-Invariant Features, su scholar.google.com. URL consultato il 29 novembre 2015.
^ Salient Points for Content Based Retrieval, su scholar.google.com. URL consultato il 2 dicembre 2015.
^ Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection, su scholar.google.com. URL consultato il 2 dicembre 2015.
^ Konstantinos G. Derpanis, The harris corner detector., York University, 2004.
^ Harris Operator Corner Detection using Sliding Window Method, su scholar.google.com. URL consultato il 29 novembre 2015.
^ The Comparison and Application of Corner Detection Algorithms, su scholar.google.com. URL consultato il 29 novembre 2015.
^ Javier Sánchez, Nelson Monzón and Agustín Salgado, An Analysis and Implementation of the Harris Corner Detector., in Image Processing on Line (IPOL), vol. 8, 2018, pp. 305-328, DOI:10.5201/ipol.2018.229.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[harris-1] Chris Harris and Mike Stephens, A Combined Corner and Edge Detector, in Alvey Vision Conference, vol. 15, 1988.

[dey-2] Nilanjan Dey, A Comparative Study between Moravec and Harris Corner Detection of Noisy Images Using Adaptive Wavelet Thresholding Technique, 2012, arXiv:1209.1558.

[note10-3] F. Bellavia, D. Tegolo e C. Valenti, Improving Harris corner selection strategy, in IET Computer Vision, vol. 5, n. 2, 1º marzo 2011, p. 87, DOI:10.1049/iet-cvi.2009.0127.

[note11-4] (EN) Edward Rosten e Tom Drummond, Machine Learning for High-Speed Corner Detection, a cura di Leonardis Aleš, Lecture Notes in Computer Science, Springer Berlin Heidelberg, 7 maggio 2006, pp. 430-443, DOI:10.1007/11744023_34, ISBN 978-3-540-33832-1.

[note12-5] A Comparison of Affine Region Detectors, su scholar.google.com. URL consultato il 29 novembre 2015.

[note13-6] L. Gueguen e M. Pesaresi, Multi scale Harris corner detector based on Differential Morphological Decomposition, in Pattern Recognition Letters, vol. 32, n. 14, 2011, pp. 1714-1719, DOI:10.1016/j.patrec.2011.07.021.

[note14-7] A Multi-scale Bilateral Structure Tensor Based Corner Detector, su scholar.google.com. URL consultato il 29 novembre 2015.

[note1-8] Juan Kang, Chuangbai Xiao, M. Deng, Jing Yu e Haifeng Liu, Image registration based on harris corner and mutual information, in 2011 International Conference on Electronic and Mechanical Engineering and Information Technology (EMEIT), vol. 7, 1º agosto 2011, pp. 3434-3437, DOI:10.1109/EMEIT.2011.6023066, ISBN 978-1-61284-087-1.

[note2-9] Underwater Mosaic Creation using Video sequences from Different Altitudes, su scholar.google.com. URL consultato il 2 dicembre 2015.

[note3-10] Automated reconstruction of 3D scenes from sequences of images, su scholar.google.com. URL consultato il 2 dicembre 2015.

[note4-11] Meng Liu, Chengdong Wu e Yunzhou Zhang, Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature, in Control and Decision Conference, 2008. CCDC 2008. Chinese, 1º luglio 2008, pp. 5287-5291, DOI:10.1109/CCDC.2008.4598340, ISBN 978-1-4244-1733-9.

[note5-12] Object Recognition from Local Scale-Invariant Features, su scholar.google.com. URL consultato il 29 novembre 2015.

[note6-13] Salient Points for Content Based Retrieval, su scholar.google.com. URL consultato il 2 dicembre 2015.

[note7-14] Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection, su scholar.google.com. URL consultato il 2 dicembre 2015.

[derpanis-15] Konstantinos G. Derpanis, The harris corner detector., York University, 2004.

[note8-16] Harris Operator Corner Detection using Sliding Window Method, su scholar.google.com. URL consultato il 29 novembre 2015.

[note9-17] The Comparison and Application of Corner Detection Algorithms, su scholar.google.com. URL consultato il 29 novembre 2015.

[sanchez-18] Javier Sánchez, Nelson Monzón and Agustín Salgado, An Analysis and Implementation of the Harris Corner Detector., in Image Processing on Line (IPOL), vol. 8, 2018, pp. 305-328, DOI:10.5201/ipol.2018.229.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Rilevatore di Harris

Indice

Descrizione[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Menu di navigazione

Rilevatore di Harris

Descrizione[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Menu di navigazione

Ricerca