Trasformazione di Hough

) accumulatore sferico usando un kernel gaussiano trivariato. L’approccio è diversi ordini di grandezza più veloce delle tecniche esistenti (non deterministiche) per il rilevamento di piani in nuvole di punti, come RHT e RANSAC, e scala meglio con le dimensioni dei set di dati. Può essere utilizzato con qualsiasi applicazione che richiede il rilevamento veloce di caratteristiche planari su grandi insiemi di dati.

Trasformazione di Hough delle curve, e la sua generalizzazione per forme analitiche e non analiticheModifica

Anche se la versione della trasformazione descritta sopra si applica solo per trovare linee rette, una trasformazione simile può essere usata per trovare qualsiasi forma che può essere rappresentata da un insieme di parametri. Un cerchio, per esempio, può essere trasformato in un insieme di tre parametri, che rappresentano il suo centro e il suo raggio, in modo che lo spazio Hough diventi tridimensionale. Anche ellissi e curve arbitrarie possono essere trovate in questo modo, così come qualsiasi forma facilmente espressa come un insieme di parametri.

La generalizzazione della trasformata di Hough per rilevare forme analitiche in spazi di qualsiasi dimensionalità è stata proposta da Fernandes e Oliveira. In contrasto con altri approcci basati sulla trasformata di Hough per le forme analitiche, la tecnica di Fernandes non dipende dalla forma che si vuole rilevare né dal tipo di dati di input. Il rilevamento può essere guidato a un tipo di forma analitica cambiando il modello di geometria assunto in cui i dati sono stati codificati (ad esempio, spazio euclideo, spazio proiettivo, geometria conforme, e così via), mentre la formulazione proposta rimane invariata. Inoltre, garantisce che le forme desiderate siano rappresentate con il minor numero possibile di parametri, e permette il rilevamento simultaneo di diversi tipi di forme che si adattano meglio a un insieme di voci con diverse dimensionalità e diverse definizioni geometriche (ad esempio, il rilevamento simultaneo di piani e sfere che si adattano meglio a un insieme di punti, linee rette e cerchi).

Per forme più complicate nel piano (cioè forme che non possono essere rappresentate analiticamente in qualche spazio 2D), viene utilizzata la trasformata di Hough generalizzata, che permette di votare una caratteristica per una particolare posizione, orientamento e/o scalatura della forma utilizzando una tabella di look-up predefinita.La trasformata di Hough accumula i contributi di tutti i pixel nel bordo rilevato.

Processo di rilevamento del cerchioModifica

Modificare l’algoritmo per rilevare forme circolari invece di linee è relativamente semplice.

• Prima di tutto, creiamo lo spazio accumulatore, che è costituito da una cella per ogni pixel. Inizialmente ogni cella è impostata su 0.
• Per ogni punto di bordo (i, j) nell’immagine, incrementiamo tutte le celle che secondo l’equazione di un cerchio ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}
  

  potrebbe essere il centro di un cerchio. Queste celle sono rappresentate dalla lettera a {displaystyle a}

  

  nell’equazione.

• Per ogni possibile valore di a {displaystyle a}
  

  trovato nel passo precedente, trova tutti i possibili valori di b {displaystyle b}

  

  che soddisfano l’equazione.

• Cerca i massimi locali nello spazio accumulatore. Queste celle rappresentano cerchi che sono stati rilevati dall’algoritmo.

Se non conosciamo in anticipo il raggio del cerchio che stiamo cercando di localizzare, possiamo usare uno spazio accumulatore tridimensionale per cercare cerchi con un raggio arbitrario. Naturalmente, questo è più costoso dal punto di vista computazionale.

Questo metodo può anche rilevare i cerchi che sono parzialmente al di fuori dello spazio accumulatore, a condizione che abbastanza area del cerchio sia ancora presente al suo interno.

Rilevamento di oggetti 3D (Piani e cilindri)Edit

La trasformata di Hough può anche essere utilizzata per il rilevamento di oggetti 3D in dati di distanza o nuvole di punti 3D. L’estensione della classica trasformata di Hough per il rilevamento dei piani è abbastanza semplice. Un piano è rappresentato dalla sua equazione esplicita z = a x x + a y y + d {displaystyle z=a_{x}x+a_{y}y+d}

per il quale possiamo usare uno spazio Hough 3D corrispondente ad una x {\displaystyle a_{x}}

, a y {displaystyle a_{y}

e d {displaystyle d}

. Questa estensione soffre degli stessi problemi della sua controparte 2D, cioè, i piani quasi orizzontali possono essere rilevati in modo affidabile, mentre le prestazioni si deteriorano quando la direzione del piano diventa verticale (grandi valori di a x {\displaystyle a_{x}

e a y {displaystyle a_{y}

amplificano il rumore nei dati). Questa formulazione del piano è stata utilizzata per il rilevamento di piani nelle nuvole di punti acquisite da scansioni laser aeree e funziona molto bene perché in quel dominio tutti i piani sono quasi orizzontali.

Per il rilevamento generalizzato del piano usando la trasformata di Hough, il piano può essere parametrizzato dal suo vettore normale n {\displaystyle n}

(usando coordinate sferiche) e la sua distanza dall’origine ρ {displaystyle \rho }

risultante in uno spazio Hough tridimensionale. Questo risulta in ogni punto dei dati di input che vota una superficie sinusoidale nello spazio di Hough. L’intersezione di queste superfici sinusoidali indica la presenza di un piano. Un approccio più generale per più di 3 dimensioni richiede un’euristica di ricerca per rimanere fattibile.

La trasformata di Hough è stata usata anche per trovare oggetti cilindrici in nuvole di punti usando un approccio a due passi. Il primo passo trova l’orientamento del cilindro e il secondo passo trova la posizione e il raggio.

Usando le caratteristiche ponderateModifica

Un dettaglio di variazione comune. Cioè, trovare i bin con il conteggio più alto in una fase può essere usato per vincolare la gamma di valori ricercati nella fase successiva.

Spazio dei parametri scelto con curaModifica

Uno spazio dei parametri ad alta densità per la trasformata di Hough non è solo lento, ma se implementato senza precauzioni può facilmente superare la memoria disponibile. Anche se l’ambiente di programmazione permette l’allocazione di un array più grande dello spazio di memoria disponibile attraverso la memoria virtuale, il numero di swap di pagina richiesti per questo sarà molto impegnativo perché l’array di accumulatori viene utilizzato in modo casuale, fermandosi raramente in memoria contigua mentre salta da un indice all’altro.

Considerate il compito di trovare ellissi in un’immagine 800×600. Assumendo che i raggi delle ellissi siano orientati lungo gli assi principali, lo spazio dei parametri è quadridimensionale. (x,y) definisce il centro dell’ellisse, e a e b indicano i due raggi. Permettendo che il centro sia ovunque nell’immagine, si aggiunge il vincolo 0<x<800 e 0<y<600. Se ai raggi vengono dati gli stessi valori dei vincoli, ciò che rimane è una matrice di accumulatori scarsamente riempita di più di 230 miliardi di valori.

Un programma così concepito difficilmente potrà essere autorizzato ad allocare sufficiente memoria. Questo non significa che il problema non possa essere risolto, ma solo che bisogna trovare nuovi modi per vincolare la dimensione dell’array di accumulatori che lo rendano fattibile. Per esempio:

1. Se è ragionevole assumere che le ellissi siano ciascuna contenuta interamente nell’immagine, la gamma dei raggi può essere ridotta. Il più grande raggio può essere se il centro dell’ellisse è al centro dell’immagine, permettendo ai bordi dell’ellisse di allungarsi verso i bordi. In questo caso estremo, i raggi possono essere ognuno solo la metà della grandezza dell’immagine orientata nella stessa direzione. Riducendo la gamma di a e b in questo modo si riduce la matrice di accumulazione a 57 miliardi di valori.
2. L’accuratezza per lo spazio nella stima della trasformazione di Hough accumula contributi da tutti i pixel del bordo rilevato. La trasformata di Hough accumula i contributi di tutti i pixel del bordo rilevato: Se il centro è previsto fuori di 3 sia sull’asse x che sull’asse y, questo riduce la dimensione della matrice dell’accumulatore a circa 6 miliardi di valori.
3. Precisione di scambio per lo spazio nella stima dei raggi: Se i raggi sono stimati per essere ciascuno fuori di 5 si verifica un’ulteriore riduzione della dimensione della matrice di accumulazione, di circa 256 milioni di valori.
4. Tagliare l’immagine alle aree di interesse. Questo dipende dall’immagine, e quindi è imprevedibile, ma immaginate un caso in cui tutti i bordi di interesse in un’immagine sono nel quadrante superiore sinistro dell’immagine stessa. La matrice dell’accumulatore può essere ridotta ulteriormente in questo caso vincolando tutti e 4 i parametri di un fattore 2, per un fattore di riduzione totale di 16.

Applicando solo i primi tre di questi vincoli all’esempio citato, la dimensione della matrice dell’accumulatore si riduce di quasi un fattore 1000, portandola a una dimensione che è molto più probabile che entri nella memoria di un computer moderno.

Algoritmo efficiente di rilevamento delle ellissiModifica

Yonghong Xie e Qiang Ji danno un modo efficiente di implementare la trasformata di Hough per il rilevamento delle ellissi superando i problemi di memoria. Come discusso nell’algoritmo (a pagina 2 dell’articolo), questo approccio usa solo un accumulatore monodimensionale (per l’asse minore) per rilevare le ellissi nell’immagine. La complessità è O(N3) nel numero di punti non nulli nell’immagine.