OpenCV & Python – Harris Corner Detection – un metodo per rilevare i vertici in un’immagine

Introduzione

Ecco come promesso, un altro articolo della lunga serie di articoli riguardanti il mondo di OpenCV e della programmazione con Python. In un precedente articolo abbiamo già visto il concetto di edge detection,  in questo articolo analizzeremo insieme un altro algoritmo chiamato Harris Corner Detection.

Se vuoi sapere di più, questo è l’articolo precedente:

Altri algoritmi di edge detection già trattati:

L’algoritmo Harris Corner Detection

Questo particolare algoritmo è stato sviluppato per individuare i corner all’interno di una immagine. I corner (angoli, estremi o spigoli) sono delle regioni all’interno di una immagine in cui si hanno grandi variazioni di intensità di gradiente in tutte le direzioni.

Uno di questi tentativi fu fatto nel 1988 da Chris Harris & Mike Stephens, che svilupparono un algoritmo che lavorasse sia sulla edge detection ma anche sulla corner detection, da cui il nome di questo algoritmo.

I due autori calcolarono la differenza di intensità attraverso una formula matematica, E(u,v).

E(u,v) = \sum _{x,y} w(x,y)[ I(x+u,y+v) - I(x,y)]^{2}

La funzione finestra w(x,y) da applicare può essere o una funzione gaussiana o una funzione rettangolare. Questa funzione E(u,v) deve essere massimizzata per la corner detection. Applicando quindi l’espansione di Taylor all’equazione e dopo alcune approssimazioni si arriva alla espressione:

E(u,v) \approx \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}

dove

M = \displaystyle \sum_{x,y} w(x,y) \begin{bmatrix} I_x^{2} & I_{x}I_{y} \\ I_xI_{y} & I_{y}^{2} \end{bmatrix}

Ix e Iy sono le derivate dell’immagine nelle direzioni x e y.  Possono essere facilmente trovate con OpenCV utilizzando la funzione cv2.Sobel().

Adesso arriva la parte principale dell’algoritmo. Infatti si crea uno score (punteggio) basandosi su una equazione che determina se una finestra può contenere un corner oppure no.

R = det(M) - k(trace(M))^{2}

dove

  • det(M)=λ1λ2
  • trace(M)=λ1+λ2
  • λ1 and λ2 sono gli autovalori di M

I valori assunti dagli autovalori determinano se una regione è un corner, un edge oppure flat (senza nulla).

  • Flat: quando |R| è piccolo, cioè quando λ1 e λ2 sono piccoli.
  • Edge: quando R<0, cioè quando λ1>>λ2 o λ2>>λ1.
  • Corner: quando R è grande, cioè quando λ1 e λ2 sono grandi e di valore simile λ1λ2.

Il quadro sopra descritto si può rappresentare nel piano degli autovalori.

Alla fine il risultato dell’algoritmo è un’immagine in scala di grigi, in cui le tonalità di grigio equivalgono appunto agli score (punteggio).

Prerequisiti prima di cominciare a programmare

Per eseguire il codice presente in questo articolo sono necessari alcuni prerequisiti. Per prima cosa è necessario far partire l’ambiente virtuale su cui avete compilato ed installato la libreria OpenCV.

Se non aveste ancora installato OpenCV, seguite la procedura di installazione descritta in questo articolo.

Inoltre in questo esempio per migliorare la visualizzazione di più immagini contemporaneamente, sfrutteremo la libreria grafica matplotlib. Se ancora non l’avete installata sul vostro ambiente virtuale potete farlo scrivendo

poi installate il pacchetto TKinter necessario per il corretto funzionamento di matplotlib.

Dapprima faremo qualche prova su un’immagine semplice con cui testare l’efficacia dell’algoritmo. Per esempio l’immagine seguente:

Scaricatela e salvatela come blackandwhite.jpg.

Programmiamo con Python l’algoritmo Harris Corner Detection

In OpenCV, questo tipo di edge detection è già stata implementata e si attiva richiamando la funzione cv2.cornerHarris().

cv2.cornerHarris(image, blockSize, ksize, k)

Questa funzione accetta quattro argomenti.

  • img – immagine da analizzare, deve essere in scala di grigi e con valori float32.
  • blockSize – dimensione delle finestre considerate per la corner detection
  • ksize – parametro per la derivata di Sobel
  • k – parametro libero per l’equazione di Harris.

Scrivi il codice seguente e proviamolo sull’immagine di prova con le due frecce bianche su sfondo nero. I valori passati come argomenti sono valori ottimali per avere buone prestazioni nella maggior parte dei casi.

Se eseguiamo il codice otterremo i risultati seguenti.

Come si può ben vedere l’algoritmo di Harris Corner Detection riesce a rivelare per bene sia i bordi delle due frecce (edge detection) sia i loro vertici (corner detection).

Altre prove sulle immagini

Passiamo ora ad effettuare l’analisi su una fotografia ricca di particolari e contorni. A tale proposito ho scelto una foglia.

Ed ecco l’elaborazione dei corner

Conclusione

In questo articolo abbiamo visto nell’ambito della edge detection, l’algoritmo Harris Corner Detection che è in grado di rilevare i corner all’interno di una immagine. Grazie alla libreria OpenCV, tutta questa analisi può essere richiamata attraverso l’uso di una sola funzione cv2.cornerHarris(), rendendoci il lavoro molto più semplice per effettuare analisi di immagini a più alto livello con Python.

[sg_popup id=7]

5 commenti:

  1. Hi, there is a very good work!
    But i have a this problem:

    img2[corners2>0.01*corners2.max()] = [255,0,0]
    ^
    SyntaxError: invalid syntax

    Anyone can i help me?

    Thank for your time.

  2. Salve a tutti,

    quando vado ad eseguire il codice mi da questo errore:

    img2[corners2>0.01*corners2.max()] = [255,0,0]
    ^
    SyntaxError: invalid syntax

    Qualcuno sa spiegarmi il perché?

    Grazie mille a tutti.

    • Non so, la riga di comando sembra corretta. Può essere un carattere non corretto nella riga precedente? La versione di Python che stai usando?

      • Al momento utilizzo python 2.7.13.
        Ma programmo usando pycharm, secondo questo software l’errore risiede nel “gt;”.

        • Ho capito….
          & gt; è il modo di HTML per visualizzare il simbolo “>”. Copiando dal sito ti sei portato appresso la codifica sottostante e non il simbolo >.
          Nel codice che hai copiato su PyCharm sostituisci i & gt; con “>” e & lt; con “<". Dopo dovrebbe funzionare.

Lascia un commento