Questo è il quarto articolo della serie sui CAPTCHA – meglio tornare al primo se non l’hai già letto.

Normalizzazione delle dimensioni delle lettere

Come si nota dall’immagine seguente, nel CAPTCHA di Vodafone solitamente le lettere  sono di dimensioni diverse.

Questo è chiaramente un meccanismo per rendere più difficile l’individuazione delle lettere – peccato che è anche particolarmente semplice da aggirare. Vediamo come.

Il primo passo è di calcolare il rettangolo minimo che contiene ogni lettera. Il procedimento è semplicissimo: basta individuare le coordinate minime e massime per ogni colore. Graficamente è possibile rappresentare il procedimento come segue:

A questo punto, senza neanche troppa fatica, normalizzare le immagini delle singole lettere significa semplicemente ridimensionarle tutte a una stessa grandezza fissata, in questo come 15×15.

Fatto il ridimensionamento, voilà, le distorsioni delle lettere sono praticamente sparite!

Il ridimensionamento è una funzione presente in qualunque libreria di manipolazione delle immagini, quindi non entro nemmeno nei dettagli dei possibili algoritmi.

Dopo aver rimosso il rumore all’immagine, segmentato i singoli caratteri ed averli normalizzati, siamo finalmente pronti per il riconoscimento vero e proprio.

Riconoscimento: prima la teoria…

Premessa: mi spiace per il titolo un po’ deprimente, ma proprio non riesco a spiegare questo argomento diversamente! I paragrafi seguenti richiedono un minimo di conoscenze matematiche, in particolare sul concetto di funzione, che è meglio aver compreso prima di gettarsi nella lettura della parte che segue.

Il problema del riconoscimento si può porre così: possiamo costruire una funzione matematica f che, dati in input i valori dei pixel che compongono l’immagine, produca in output la lettera rappresentata?

Dettaglio matematico: in modo un po’ più rigoroso il problema è:

definire una funzione y=f(x), dove:

x è un vettore di 225 numeri (corrispondenti a 15×15 pixel) tra 0 (bianco) ed 1 (nero)

y è un vettore di 34 numeri tra 0 ed 1 (uno per ogni carattere che può comparire nel CAPTCHA) e

y_i vale 1 se x rappresenta il carattere i e 0 altrimenti

Se siete arrivati fino a questo punto, dovreste avere una domanda in testa: come è possibile definire un mostro di funzione come questo?

Una possibilità è di spendere qualche mese ragionando su come definire analiticamente la funzione f, cosa non particolarmente comoda, in particolare a causa del gran numero di variabili in ingresso. Una via più conveniente, e decisamente più furba, è usare le reti neurali, che possiamo definire molto grossolanamente come “funzioni imitatrici“.

Al di là del nome esotico, le reti neurali non sono altro che funzioni matematiche, con la particolarità che sono in grado di “imitare” (approssimando) altre funzioni. La cosa divertente è che le funzioni imitate possono anche essere ignote!

Nel nostro caso, possiamo ipotizzare senza troppa fantasia che una funzione f esista; non sapendola scrivere ci limitiamo ad imitarla con una rete neurale!

Dettaglio matematico: in modo un po’ più preciso, ed in estrema sintesi, una rete neurale è una funzione parametrica che a seconda dei valori assunti dai suoi parametri può approssimare una qualunque altra funzione (non necessariamente nota). Esiste un simpatico teorema il quale prova che una particolare classe di reti neurali, le reti a percettrone con strato nascosto singolo, possono approssimare con arbitraria precisione arbitrarie funzioni, sotto ipotesi molto permissive e certamente verificate qui. Ovviamente, ci concentreremo su questo particolare tipo di rete nel seguito dell’articolo.

Incredibile… Ma funziona!

Come è possibile che una rete neurale possa approssimare la sfuggente funzione f, che non abbiamo mai visto?

L’idea è che la rete è in grado di apprendere da alcuni esempi che gli vengono forniti.

Si può infatti “esporre” un insieme di input ed output preparati a mano ad una rete neurale ed aspettarsi che questa “impari per esempi” come funzionare. Una volta terminato questo allenamento, la rete dovrebbe essere in grado di calcolare dei “buoni output” anche a partire da input nuovi.

Sembra incredibile? Eppure funziona!

Infatti, non è un caso che attualmente tutti i migliori software OCR facciano esattamente così. Ricordo tra gli altri tesseract, il software usato da Google per la scansione dei libri in Google Books.

Per l’allenamento è necessario, innanzitutto, preparare un bel po’ di caratteri e dividerli per lettera a mano. In questo modo avremo un certo insieme di coppie input-output da dare in pasto alla rete durante l’allenamento. Personalmente ci ho messo diverso tempo, il risultato è qualcosa di questo genere:

Poi occorre procurarsi un’implementazione degli algoritmi delle reti neurali che, in particolare, permetta l’allenamento. Esistono ottimi “motori di reti neurali” già fatti che fortunatamente permettono di evitare un bel po’ di complessità numeriche.

Nota tecnica: calcolare l’output di una rete neurale, in particolare di una rete a percettrone con strato singolo nascosto come quelle usate qui, è un gioco da ragazzi, si tratta infatti di poco più di addizioni e prodotti per costanti. L’allenamento, invece, è un processo ripetititivo abbastanza complesso, soprattutto se si tiene conto delle problematiche di efficienza – ecco perchè è utile trovare un motore “chiavi in mano”.

Io ho scelto Encog, che ho trovato veramente ottimo. Tra le altre cose è gratuito ed open source, il che è utile anche per chi volesse approfondire la tematica. Encog ha una bella interfaccia grafica per comporre la rete neurale di interesse, per allenarla e verificarne il funzionamento su dati nuovi senza dover scrivere codice, quindi si adatta bene ai casi in cui è necessaria un po’ di sperimentazione.

Quanti neuroni allenare?

A questo punto il problema principale è la scelta del numero di neuroni che compongono la rete neurale. Come detto la terminologia è un po’ esotica ma non è casuale: nella sua formulazione matematica, infatti, la rete è definita proprio come un’interconnessione di unità minime dette neuroni, e il loro numero determina l'”intelligenza” della rete stessa!

Più precisamente, variare il numero di neuroni in una rete significa controllarne la complessità: tanti più sono i neuroni tanto più complessa potrà essere la funzione che collettivamente vanno ad emulare. Il problema è che una rete con molti neuroni, oltre ad essere molto potente, ha anche due svantaggi:

1. richiede moltissima potenza computazionale per essere allenata, quindi questa fase potrebbe richiedere ore o giorni, inoltre
2. rischia di imparare “troppo bene” dagli esempi forniti, nel senso che dopo l’apprendimento riconosce perfettamente quelli, ma poi sbaglia completamente con qualunque dato nuovo anche solo leggermente diverso. Questa “impossibilità di generalizzare” è detta in gergo overfitting ed è naturalmente da evitare.

Non sapendo cosa far di meglio ho seguito un approccio sperimentale variando più volte il numero di neuroni e vedendo quali risultati riuscivo a raggiungere.

Nota tecnica: l’effettiva efficacia di una rete va valutata su un insieme di lettere diverso da quello usato per l’allenamento, altrimenti si corrono grossi rischi di overfitting. Questa tecnica è generale e viene detta cross-validation, ed è supportata da Encog.

E’ obbligatorio che ogni rete a percettrone a strato nascosto singolo abbia:

• un neurone per ogni variabile in input (nel nostro caso, 225),
• un neurone per ogni variabile in output (nel nostro caso, 34),
• uno o più neuroni ulteriori detti “nello strato nascosto”.

Ovviamente, il punto cruciale è scegliere bene il numero di neuroni in quest’ultimo punto! Al termine delle mie prove il numero ottimo sembrava essere 75, uno per ogni 3 pixel in ingresso, portando quindi il totale a 334 neuroni (una rete di complessità medio-moderata). Stabilito questo si può “disegnare” la rete in Encog: qui sotto riporto una schermata del programma che mostra la struttura della rete ed il numero di neuroni.

Fatto questo si procede all’allenamento, che è un processo generalmente abbastanza lungo in cui la rete impara dagli esempi fino a ridurre la percentuale di errori sotto a un certo limite stabilito. Nella figura seguente, tratta ancora da Encog, si vede l’andamento dell’errore durante l’apprendimento.

Come si può notare la linea rossa che rappresenta il tasso di errore cala progressivamente fino a un minimo al quale l’allenamento si arresta, e la rete è pronta all’uso!

Note tecniche: per i dettagli di funzionamento di Encog rimando al sito ufficiale, poichè una spiegazione particolareggiata richiederebbe uno spazio eccessivo. Chiarisco soltanto alcuni punti:

• Encog ha bisogno di file CSV piuttosto che di immagini per l’allenamento, la conversione non è descritta perchè tutto sommato banale per chiunque sappia programmare;
• l’allenamento, in pratica, consiste nella taratura dei parametri della rete neurale in modo che approssimi la funzione voluta;
• esistono più algoritmi per l’allenamento, molti dei quali sono ancora in stato di attiva ricerca. L’algoritmo di default di Encog, detto resilient backpropagation, è molto buono e più che sufficiente per i nostri scopi;
• dall’interfaccia grafica dell’Encog Workbench si può esportare codice Java o C# che implementa la rete allenata, a questo punto il codice va integrato con tutte le procedure di trattamento delle immagini viste finora.

Prossimi passi

Se siete arrivati fin qui, complimenti, la parte dura è passata! Nel prossimo articolo tirerò le somme di quanto visto, farò un minimo di analisi statistica dei risultati e pubblicherò qualche spezzone di codice.

Scommetto che stavolta non era tutto così semplice e chiaro, fatevi sentire nei commenti che rispiego quel che manca oppure è confuso!

A breve pubblicherò la parte 5, se volete restare aggiornati abbonatevi al feed RSS! (a proposito, cos’è un feed RSS?)