5.26. Trovare linee e segmenti

Alcune caratteristiche della scena non sono regioni di colore connesse ma bordi diritti orientati: una linea dipinta sul pavimento, la giuntura tra due superfici, il lato di un rettangolo stampato, il bordo di una porta. Chiedere al rilevatore di blob di trovarli è la domanda sbagliata: il bordo è largo un pixel, l’algoritmo dei blob vuole un’area con colore, e la risposta torna vuota o rumorosa.

Il rilevatore corretto per i bordi orientati è la trasformata di Hough delle linee. Il modulo image la espone in due varianti: find_lines() restituisce linee infinite (ogni linea si estende per tutta l’immagine); find_line_segments() restituisce segmenti finiti (ogni linea ha estremità all’interno del frame). Quale delle due serve all’applicazione dipende dal fatto che i bordi di interesse siano continui su tutto il frame o ne coprano solo una parte.

5.26.1. Come funziona la trasformata di Hough

Entrambi i rilevatori condividono la stessa idea di fondo, quindi conviene comprenderla una volta sola. Il modulo image esegue dapprima un filtro di bordo in stile Sobel sull’input per assegnare a ogni pixel un punteggio in base alla probabilità che giaccia su un bordo orientato. Ciascuno di questi pixel di bordo vota poi per tutte le linee su cui potrebbe giacere. Le linee che raccolgono più voti vincono.

Una linea è parametrizzata nello spazio di Hough da due numeri: theta, l’angolo della linea (0 – 179 gradi), e rho, la distanza perpendicolare dall’origine dell’immagine alla linea (con segno, in pixel). Ogni linea contenuta nell’immagine è un punto nello spazio (theta, rho). Ciascun pixel di bordo nell’input contribuisce con un voto a ogni combinazione (theta, rho) coerente con la sua posizione – concettualmente, una curva attraverso lo spazio di Hough. Dove molte di queste curve si incrociano, molti pixel di bordo concordano sulla stessa linea, e quell’incrocio è un rilevamento.

Il rilevatore restituisce i massimi locali nello spazio di Hough i cui totali di voti superano una soglia. Ogni Line restituita porta con sé entrambe le rappresentazioni: x1, y1, x2, y2 per la forma a estremità (ritagliata ai confini dell’immagine nel caso infinito), theta, rho per la forma di Hough, e length e magnitude rispettivamente per la dimensione e il conteggio dei voti.

5.26.2. Linee infinite

find_lines() esegue la trasformata di Hough e restituisce le linee più forti, ciascuna estesa per tutta l’immagine:

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

threshold è il totale minimo di voti perché una linea venga accettata. Il totale dei voti somma le magnitudini dei bordi Sobel di ogni pixel che contribuisce, quindi valori di threshold più grandi richiedono bordi più lunghi o più forti per superare la soglia. Questo fa sì che il valore corretto dipenda dalla risoluzione dell’immagine (una linea più lunga a una risoluzione più alta accumula più voti) oltre che dalla scena, quindi deve essere tarato per la particolare applicazione. Come punti di partenza approssimativi da cui tarare: 1000 per una linea modesta in un’immagine pulita, 500 o meno per contrasto debole o linee corte, 2000 o più per scene affollate in cui linee falsamente positive si formano tramite raggruppamenti di rumore sui bordi.

theta_margin e rho_margin controllano la fusione dei massimi vicini. Un singolo bordo fisico produce un piccolo raggruppamento di bin ad alto voto attorno al suo vero (theta, rho), e il rilevatore collassa ciascun raggruppamento al suo picco prima di restituirlo. theta_margin=25 (gradi) fonde qualsiasi picco entro 25 gradi di orientamento; rho_margin=25 (pixel) fonde i picchi entro 25 pixel di distanza. I valori predefiniti sono ragionevoli; aumentarli restituisce meno linee, più distinte, e abbassarli restituisce più linee, talvolta duplicate.

x_stride e y_stride regolano il passo tra i pixel di bordo durante il voto, allo stesso modo in cui regolano il passo tra i pixel in find_blobs(). I valori predefiniti di 2 e 1 funzionano per il caso comune; aumentarli velocizza la ricerca a scapito della risoluzione. roi restringe la ricerca a una regione del frame, cosa che sia limita le linee restituite sia riduce il lavoro.

Ogni linea restituita è direttamente disegnabile: l’oggetto Line passa direttamente in draw_line(), che ne legge i campi delle estremità (x1, y1, x2, y2) dall’inizio. l.theta è l’angolo in gradi, che classifica la linea come orizzontale, verticale o diagonale con un solo confronto. l.magnitude è il totale dei voti, che ordina le linee restituite dalla più forte alla più debole.

5.26.3. Segmenti di linea

find_lines() è il rilevatore corretto per i bordi che attraversano l’intero frame, ma molti bordi reali – il lato sinistro di un codice a barre stampato, il bordo superiore di un’etichetta, il lato visibile di un righello – coprono solo una parte dell’immagine. find_line_segments() restituisce segmenti finiti le cui estremità sono all’interno del frame:

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

Il rilevatore di segmenti traccia direttamente lungo i pixel di bordo orientati, anziché votare nello spazio di Hough, e il risultato è una raccolta di brevi tratti diritti. merge_distance imposta il divario massimo in pixel che due brevi tratti collineari possono coprire pur fondendosi in un unico segmento restituito; max_theta_difference imposta quanti gradi di orientamento il modulo di fusione tollera tra tratti adiacenti. Una fusione generosa (merge_distance=10, max_theta_difference=15) restituisce un piccolo numero di segmenti lunghi a costo di unire talvolta bordi realmente separati; una fusione rigorosa (merge_distance=0, max_theta_difference=5) restituisce molti segmenti corti e lascia all’applicazione il compito di smistarli in Python.

Gli oggetti risultato sono dello stesso tipo Line restituito da find_lines(), con le stesse proprietà, cosicché una pipeline può elaborare entrambi i tipi di rilevamento attraverso lo stesso percorso di codice a valle. L’unica differenza pratica è che le estremità dei segmenti sono i veri estremi della linea nell’immagine, mentre le estremità delle linee infinite sono ovunque la linea attraversi il bordo dell’immagine.

5.26.4. Quando usare ciascuno

La scelta tra i due metodi si riduce a una sola domanda: all’applicazione interessa dove finisce la linea?

find_lines() è lo strumento giusto quando la risposta è no. Un robot che segue una linea ha bisogno di sapere in quale direzione va la linea e dove attraversa il fondo del frame; la linea stessa corre fino all’orizzonte e oltre. Un rilevatore di orizzonte vuole il bordo orientato più forte nell’immagine; non ha bisogno di sapere dove finisce l’orizzonte.

find_line_segments() è lo strumento giusto quando la risposta è sì. Identificare i quattro lati di un rettangolo stampato richiede quattro segmenti con estremità note. Tracciare un dito che punta verso un display significa seguire un breve segmento le cui estremità sono la punta e la base del dito. Misurare la lunghezza di un graffio visibile richiede l’estensione reale del segmento in pixel.

Entrambi i rilevatori condividono una limitazione comune: hanno bisogno di contrasto. Il filtro di bordo Sobel su cui si basano risponde ai gradienti di luminosità; un bordo colorato contro uno sfondo ugualmente luminoso (una linea rossa su una parete verde della stessa luminanza) non produce alcun gradiente e nessun rilevamento. Quando questo caso si presenta nella pratica, la soluzione è estrarre un singolo canale LAB come immagine in scala di grigi con il contrasto corretto prima di cercare – to_grayscale() con il canale b selezionato isola il rosso contro il verde dove il solo canale di luminanza è piatto – e passare quell’immagine di canale al rilevatore di linee.