02 Line (Hough)

Lo scopo è trovare la griglia che definisce lo schema di sudoku definito in FIGURA1, passando per l'immagine dei bordi ottenuta alla fine del paragrafo precedente.

Mi avvalgo per far ciò di un algoritmo per la rilevazione delle rette molto famoso, la trasformata di Hough (N.B.: si legge “Aff”).

L'idea della trasformata di Hough (nel seguito HT) è relativamente semplice, geniale e dunque vincente.

2.1 Rette in rappresentazione polare

Si consideri la matrice binaria contenente i bordi come un piano, l'origine del sistema di riferimento (O) sia il centro dell'immagine. Dato un punto di edge (P) considero il fascio di rette passanti tale punto.

Le rette vengono definite utilizziando la rappresentazione polare:

L'immagine seguente dovrebbe essere esplicativa di come si definisce una retta in rappresentazione polare.

Dove ρ è la distanza della retta dell'origine è θ è l'angolo della normale alla retta passante per l'origine (che viene utilizzata, per l'appunto, per trovare la distanza tra origine e retta).Da notare che, dato un punto nel piano, una retta che passi per tale punto viene definita usando solo due parametri (ρ, θ).

2.2 Dalla retta sul piano immagine alla sinusoide nello spazio di Hough

Esprimendo anche P con coordinate polari ed utilizzando la nota formula del coseno della differenza:

Si ottiene facilmente:

Si noti dunque che dato un punto (φ ed α costanti) il fascio di rette è definito da una sinusoide, quindi, per ogni punto di bordo che andremo ad analizzare, genereremo nel piano (ρ, θ) una sinusoide, questo nuovo piano bidimensionale è detto spazio di Hough (nel seguito HS). A titolo esemplificativo si osservino i grafici che seguono, a sinistra si vedono 5 punti nel piano immagine, dei quali 4 allineati, a destra lo HS dei 5 punti. Si nota qualcosa di decisamente interessante, vero?

Altra considerazione da fare è che il numero di rette che passano per un punto è noto essere infinito. Nel mondo digitale però la discretizzazione è sempre dietro l'angolo, inoltre ha anche l'innegabile vantaggio di rendere finito nel tempo e nello spazio gli algoritmi e nel caso specifico dobbiamo rendere lo HS finito. Si sceglie, in prima battuta, di discretizzare le due variabili misurando la distanza ρ in numero di pixel e l'angolo θ in gradi. L'intervallo di definizione di un angolo è [-180,180] ma, nel nostro caso, scegliamo di cercare le rette “orrizzontali” tra [-30, + 30], sperando che chi effettuerà la scansione degli schemi non abbia bevuto troppo. Rimane da capire dato un punto qual'è il ρ massimo, la risposta è semplice data l'ultima equazione, φ è massimo negli angoli dell'immagine ed il coseno al massimo ritorna un coefficiente moltiplicativo unitario, dunque la distanza massima è pari alla lunghezza della semi-diagonale dell'immagine.

2.3 Votazione

Una volta dimensionato lo spazio di Hough, per ogni punto di bordo dell'immagine binaria, assegno un voto a tutte le rette definite dalle coppie (ρ, θ) che passano per esso. Nello specifico significa eseguire per ogni punto di bordo una scansione di tutti i possibili valori dell'angolo θ e trovare per ognuno di questi la distanza dall'origine ρ associata (si utilizza banalmente l'equazione della retta in rappresentazione polare, paragrafo 2.1). Da prestare particolare attenzione al fatto che per un punto non è detto che passino le rette di coordinata θ qualunque, è banale dirlo ma è bene ricordare che il discriminante per l'ammissibilità di una retta nello HS è che ρ sia non negativo, del resto essendo una distanza direi che il fatto non stupisce per nulla. Attenzione dunque a non farsi vincere dalla tentazione di utilizzare la funzione valore assoluto per il calcolo di ρ.

Al termine le rette ricavate dall'immagine saranno tutti gli elementi dello HS che hanno ricevuto una votazione elevata, è possibile impostare una soglia oppure (come nel nostro caso) selezionare le rette più probabili ed effettuare delle valutazioni su quest'ultime.

2.4 Applicazione dell'algoritmo nel caso specifico

Finita la breve trattazione teorica, passiamo alla parte operativa. Nel nostro caso è da tener presente che ci sono più rette nell'immagine, dunque non possiamo cercare “la” retta, inoltre ci sono anche coppie di rette “vicine” che tendono ad accentrare molti voti in quella zona dell'immagine. Il tutto è reso evidente dalla seguente immagine, risultato dell'algoritmo sopra esposto, dove vengono rappresentate le 10 rette che hanno vinto le elezioni (ebbene sì, hanno preso più voti ed è giusto così).

Prima di proseguire riportiamo di seguito anche la graficazione dello spazio di Hough relativo, dove i punti più luminosi rappresentano le rette più probabili.

Il risultato evidenzia, come prevedibile, che effettivamente le due linee attigue che separano i quadrati interni danno luogo ad un ammassamento di voti (e dunque rette), mentre la retta più esterna è invece ben evidente e “sola”, decidiamo di isolarla e per far ciò ci basta prendere la retta più esterna, ovvero quella più distante dall'origine.

Un paio di note operative:

• la discretizzazione di ρ e θ scelta è più che accettabile ai nostri scopi, l'algoritmo è esoso in termini computazionali, è di fondamentale importanza non discretizzare in modo troppo fine le grandezze in gioco;
• visto l'uso intensivo di seno e coseno è bene creare delle look-up table per tali funzioni.

Ripetendo il procedimento descritto ricercando le rette più distanti dal centro con angolo negli inervalli angolari [60;120] , [150;210] e [240;300] si ottiene la seguente.

Bene, ora direi che abbiamo ricavato il quadrato esterno dello schema sudoku!

Ricavare la suddivisione interna direi che è parecchio semplice.

Il risultato finale è raffigurato nella seguente immagine.

Le rette tratteggiate in verde rappresentano i due assi di simmetria della griglia e si intersecano al centro dello schema sudoku mentre le rette tratteggiate blu rappresentano le rette mediane dell'immagine e si intersecano nell'origine, ovvero al centro dell'immagine.

Anche questa è fatta! Passiamo ora a dare una raddrizzata all'immagine.