Raddrizzare il contenuto di un’immagine
In questo secondo articolo spiegherò come raddrizzare un’immagine che contenga elementi per i quali sia evidente una direzione comune e prevalente. Fanno parte di questa categoria le immagini contenenti testo.
Una delle pre-elaborazioni che si rendono necessarie con più frequenza nell’applicazione di un motore OCR ad un’ immagine è appunto l’eventuale raddrizzamento del suo contenuto, pena un‘inefficace segmentazione delle righe di testo.
Strumenti
Anche in questo articolo, come nel precedente al quale rimando per l’installazione degli strumenti necessari, utilizzerò Python 2.7, OpenCV e Anaconda per il codice di esempio. La tecnica che vado a spiegare coinvolge delle computazioni abbastanza pesanti, quindi Python non è il linguaggio più indicato in un’applicazione reale, a causa della nota lentezza (in particolare sui cicli); tuttavia quello che mi interessa è spiegare il metodo… e con Python si fa prima :).
Un po’ di teoria
Nell’applicazione del metodo oggetto di quest’articolo si parte dall’assunto che esista un’ angolatura prevalente nell’immagine e che questa corrisponda effettivamente al grado di inclinazione del suo contenuto. Per individuare tale angolatura, si può utilizzare la tecnica della trasformata di Hough. Questa trasformazione è il metodo più noto per rilevare la presenza di linee rette nelle immagini. Per una spiegazione approfondita rimando al link di wikipedia o alla grande quantità di informazioni che si trovano on-line, io mi limito a spiegarne l’idea in breve.
Come tutti sanno, per ogni punto di un piano passano infinite rette; si può quindi pensare ai punti come a “rappresentanti” di fasci di rette. Consideriamo ora due punti di un piano e le rispettive infinite rette passanti per essi: solo una di queste rette passa per entrambi i punti, ed è quindi l’unica ad avere due “rappresentanti” e ad appartenere ad entrambi i fasci. Continuiamo con l’immagine in Figura 2 e guardiamo in particolare la scritta “zetta ufficiale”.
E’ evidente che tutti i pixel del bordo superiore della scritta sono allineati sulla stessa retta; per ognuno di essi passano infinite rette, tuttavia solo una di queste passa attraverso tutti i pixel considerati, ed è quindi più “rappresentata” delle altre. La trasformata di Hough è un metodo per stabilire la rappresentanza di una retta all’interno di un’ immagine, e quindi poterne valutare l’effettiva presenza. Per rilevare l’angolazione del contenuto di un’immagine non è necessario arrivare fino alla segmentazione delle rette ma è sufficiente fermarsi al calcolo dello “Spazio di Hough”, dal quale è semplice estrarre l’angolo più “votato”.
Lo spazio di Hough
L’equazione della retta che tutti conoscono è:
y = mx + q (Equazione 1)dove m è il coefficiente angolare e q l’intercetta con l’asse delle ordinate. Questi due coefficienti definiscono una retta specifica e possono essere usati come coordinate per rappresentarla univocamente come punto di un piano.
Un’equazione della retta un po’ meno nota è la forma polare
ρ = x cos(θ) + y sin(θ) (Equazione 2)dove i coefficienti che definiscono la retta sono l’ angolazione θ e la distanza ρ dall’origine degli assi. Questa seconda forma è preferibile nel nostro caso, in quanto con la prima notazione c’è un problema di rappresentazione delle rette parallele all’asse delle ordinate, che hanno coefficiente angolare m di valore infinito.
Definiamo lo spazio di Hough come uno spazio a due dimensioni e a valori reali, sui cui assi mettiamo θ in ascisse e ρ in ordinate. Una retta del normale piano cartesiano è proiettata in un punto dello spazio di Hough tramite l’ equazione 2, mentre un fascio di rette passante per il punto (x,y) assume quindi una forma sinusoidale.
In Figura 5, ogni punto sulla sinusoide è una retta passante per il punto di coordinate (2, 2) del normale piano cartesiano, ognuna rappresentata dalla coppia di parametri (θ,ρ).
Ogni punto dell’immagine di partenza genera quindi una sinusoide nello spazio di Hough, che è la proiezione del fascio di rette passante per esso. Accumulando le sinusoidi nello spazio di Hough, è possibile sapere quanti punti dell’immagine sono attraversati da ogni retta, valutando il valore di accumulazione nei punti d’intersezione delle sinusoidi. I punti in cui le sinusoidi si intersecano, corrispondono alle rette appartenenti a più di un fascio (e che quindi attraversano più di un punto) nel piano di origine.
Dalla teoria alla pratica
Chiedo scusa per la carrellata teorica, ma è il consueto “male necessario” per comprendere quello che si sta facendo. Tutto questo per arrivare alla conclusione che lo spazio di Hough può essere utilizzato come contatore delle rette di un’immagine, e di conseguenza, anche per individuare l’angolazione prevalente di queste rette, che si spera corrisponda all’angolatura con la quale l’immagine dovrà essere raddrizzata.
Passiamo finalmente al codice. Consiglio di scaricare il repository iniziale tramite il comando
git clone --branch step1 https://github.com/lucapiccinelli/DeskewTutorial.gitcol quale vi troverete nella seguente situazione
e con la seguente immagine di test nella cartella img
Dall’immagine originale facciamo un paio di step di pre-processing prima di poter arrivare al calcolo dell’angolazione:
Ridimensioniamo l’immagine arrivando a 1/9 rispetto all’originale. Il resize serve per aumentare la velocità di computazione e nella maggioranza dei casi non impatta sulla precisione del calcolo, essendo ancora ben evidenti le linee dell’immagine di partenza. La seconda operazione è invece l’applicazione del Canny edge detector che è un algoritmo che permette la rilevazione dei bordi del contenuto dell’immagine; questo ci serve per selezionare i punti su cui ha senso andare a calcolare i fasci di rette, permettendo sia un incremento di prestazione (diminuendo il numero di punti), sia un incremento della precisione (vengono presi in considerazione solo i punti più significativi).
La funzione houghSpace
Veniamo ora al calcolo vero e proprio: ha senso definire una funzione apposita per il calcolo dello spazio di Hough.
Definiamo la funzione houghSpace in cui andiamo a calcolare i valori di accumulazione dello spazio. Usiamo una matrice per rappresentare lo spazio, quindi la prima domanda da porsi è: “quanto è grande la matrice?” Tornando alla teoria, abbiamo detto che sull’asse delle ascisse ci sta l’angolazione θ delle rette, quindi il numero di colonne dipende da quanto possiamo permetterci di esserci imprecisi nel calcolo dell’angolo: per renderci la vita più facile, poniamo che ci sia sufficiente essere in grado di cogliere angolature per valori nell’insieme dei numeri naturali, quindi 0,1,2,3 ecc… fino a 180, lasciando perdere i numeri con la virgola. Non ci interessa calcolare angoli superiori a 180 perché non ci è possibile distinguere il verso delle rette, quindi che una retta sia angolata a 45° oppure a 225° non fa alcuna differenza.
Il numero di colonne della matrice sarà quindi 180.
Passiamo ora alla dimensione delle righe della matrice: sappiamo dalla teoria che sulle righe mettiamo la distanza dall’origine ρ e siamo certi che una retta in un’immagine non può mai essere più lontana della lunghezza della diagonale dell’immagine stessa.
Le rette di coefficiente angolare positivo ma di intercetta negativa hanno però dei valori ρ negativi
(Math alert)questo perchè una retta proiettata nello spazio di Hough ha due punti di rappresentanza: uno con θ compreso tra 0 e 180 e un altro con valori θ compresi tra 180 e 360. Come dicevo prima, essendo una retta priva di verso, ogni angolo di un intervallo ha il suo duale nell’altro, il quale ha però ρ di segno opposto.
ma, non disponendo di indici negativi in una matrice, possiamo comunque conteggiarli traslando tutti gli indici per il valore massimo di ρ, che abbiamo appena stabilito essere la diagonale. Quindi il numero di righe è il doppio della diagonale dell’immagine.
Ora che abbiamo stabilito le dimensioni della matrice che fa da accumulatore per lo spazio di Hough non resta che valorizzarla: inizializziamo a 0 tutta la matrice e poi scorriamo l’immagine di input; per ogni pixel di valore diverso da zero proiettiamo il relativo fascio di rette usando θ come variabile indipendente e calcolando il corrispondente valore ρ utilizzando l’equazione
ρ = x cos(θ) + y sin(θ)e incrementiamo di uno il valore presente nella matrice agli indici (ρ,θ), ricordandosi che ρ va traslato del valore della diagonale.
Per velocizzare il tutto conviene farsi un paio di array in cui precalcolare seno e coseno tra 0 e 180.
Dichiariamo houghSpace come array monodimensionale e scorriamolo quindi linearmente per comodità, calcolando l’indice corrispondete a (ρ,θ) come
c = ρ * colonne + θInfine normalizziamo tra 0 e 1 lo spazio di Hough e facciamo un reshape in forma matriciale (cioè, al posto di definire lo spazio come un array monodimensionale lungo n * m, lo ridefiniamo come matrice bidimensionale di n righe e m colonne).
Segue la funzione completa.
Istogramma di angolatura
Ora che abbiamo la funzione per il calcolo dello spazio di Hough, la possiamo applicare sulla nostra immagine di test; aggiungo anche la visualizzazione del risultato utilizzando matplotlib
Dalla visualizzazione dello spazio di Hough dell’immagine di input in figura 8, vediamo dei picchi (di colore giallo/rosso) intorno ai 75 gradi.
A questo punto è banale estrarre l’angolatura: filtriamo lo spazio per tenere solamente i picchi superiori a 0.8 (sono quegli angoli dove si concentra il maggior numero di rette), in modo da eliminare il rumore degli angoli meno “votati”, dopodiché sommiamo le colonne per ottenere l’istogramma degli angoli e infine selezioniamo l’angolo con valore di istogramma più elevato.
I più attenti avranno notato dalla Figura 4 che l’angolo θ utilizzato per rappresentare la retta tramite coordinate polari, è in realtà perpendicolare alla retta stessa, e di conseguenza alla sua inclinazione. L’angolo corretto quindi non è il valore θ selezionato, bensì il suo valore perpendicolare
θ' = 90 - θθ’ è quindi l’angolo col quale dovremo ruotare l’immagine.
Conclusioni
In questo articolo è stato presentato un metodo per calcolare l’angolatura del contenuto di un’immagine, così da permetterne l’eventuale raddrizzamento. Il metodo esposto fa utilizzo della trasformata di Hough, per questo motivo c’è molta matematica: ho cercato di essere il più chiaro e preciso possibile, tuttavia non sono un matematico, quindi chiedo scusa e un po’ di clemenza nel caso avessi commesso qualche errore o imprecisione :).
L’implementazione proposta è volutamente limitata alla possibilità di calcolare angoli con valori appartenenti ai numeri naturali; qualora fosse necessaria maggiore precisione, è sufficiente aumentare il numero di colonne della matrice utilizzata come rappresentazione dello spazio di Hough, facendo i dovuti adattamenti per il calcolo degli indici e ricordandosi che il tempo di calcolo aumenterà inevitabilmente.
Ultima nota: la trasformata di Hough è la versione utilitaristica o “da informatico” della molto più elegante, ma meno applicabile, trasformata di Radon, che consiglio vivamente di approndire agli appassionati dei dettagli matematici.
Materiale
Segue il codice completo
Ecco il link del repository github con tutto il codice, l’immagine di test utilizzata nell’esempio ed altre immagini per testare il codice:
https://github.com/lucapiccinelli/DeskewTutorialQuesto è tutto, spero sia chiaro e come solito sono graditi domande, commenti e suggerimenti.
Grazie per la lettura!
