Aggirare un CAPTCHA per divertimento e divulgazione – Parte 4

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.

Un CAPTCHA preso dal sito Vodafone, così com'è.

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!

Processo di normalizzazione delle dimensioni delle lettere.

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

yi 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:

Esempio di lettere catalogate per l'allenamento di una rete neurale

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?

I neuroni di Homer Simpson (pochi).

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.

Schermata di Encog di creazione della rete.

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.

Schermata di Encog durante l'allenamento di una rete neurale.

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?)

14 Comments

  • Hai vinto la scommessa: “stavolta non era tutto così semplice e chiaro” (:

  • Okay 🙂

    Fatemi sapere cosa resta oscuro che tento di spiegarlo meglio!

  • ciao … sono veramente incuriosito con orc , mi piacerebbe tantissimo fare qualche prova di addestramento di reti neurali … mi puoi dire tu che programmi usi , volevo sapere pure se è conveniente iniziare a programmare su un sistema operativo linux o windows … thx

  • ciao .. sono uno studente di ingegneria sono rimasto affascinato di questo tuo progetto .. volevo sapere se e’ possibile sapere che programmi usi per programmare tutto quanto cosi magari ci posso dare un-occhiata anch’io dentro questa rete neurale …

  • Il prossimo articolo darà alcuni dettagli implementativi in più, quindi tieni guardato il sito (o meglio, abbonati via RSS).

    In ogni caso il mio codice è scritto in Scala e usa Encog. Encog è scritto in Java e questo è il linguaggio di programmazione preferibile, Scala va bene lo stesso poichè è compatibile – anche se per alcuni aspetti è un po’ più difficile.

    Se usi Encog, essendo basato su Java, non c’è alcuna differenza nell’uso di Windows o Linux. Per la cronaca, io ho usato sempre e solo Mac OS X. A seconda della piattaforma puoi scegliere l’ambiente di sviluppo che più ti aggrada, anche se io consiglierei in ogni caso Eclipse.

  • Ma è una figata… a livello concettuale è tutto chiaro, peccato sappia programmare solo in php… 🙁

    ps: le reti neurali le utilizzano anche per il facial recognition??

  • Questa serie di articoli e` *FANTASTICA*: sei molto chiaro e semplice nella tua descrizione! Ne vogliamo leggere altri cosi`!

  • Non sono sicuro sul fatto che si possano usare le reti neurali per il riconoscimento dei volti ma in linea concettuale direi che si può fare. Tieni conto che un’immagine è sempre e comunque un segnale bidimensionale, quindi la vedo possibile di categorizzarne le istanze con una rete neurale. Altra cosa interessante è che il riconoscimento dei visi si basa essenzialmente sulla forma delle sopracciglia, quindi immagina un qualche filtro grafico che tolga il resto, un bel po’ di immagini di allenamento… E il resto potrebbe essere simile a quanto descritto in questi articoli!

  • Molto bella questa serie di articoli. A quando la quinta e l’ultima parte?

  • L’ho appena pubblicata!

    Avevo solo bisogno di qualche minuto per confezionare l’articolo, visto che i contenuti erano pronti da tempo.

    Buona lettura!

  • Ciao:) Esistono programmi che ti compilano il captcha automaticamente?

  • Certo! Dipende dal sito che stai usando, però.

  • Perchè ho cercato un po’ su google, ma ci sono programmi che ti compilano i captcha dei downloads, ma a me non serve questo. Mi servirebbe un programma per compilare automaticamente captcha di un sito che ti conta quante volte vedi il video ma ogni volta devi inserire il captcha. Cosa posso fare?

  • ?

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>