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

Riassunto delle puntate precedenti

Ecco la ricetta per “leggere” il CAPTCHA di Vodafone!

• rimuovere il rumore dal fondo dell’immagine, per sottrazione con un’immagine di solo rumore ottenuta comparando molti CAPTCHA;
• applicare un filtro a soglia per rendere netti i contorni dei caratteri;
• opzionalmente, correggere le aree bianche o nere troppo piccole e (semi)isolate dal resto;
• segmentare l’immagine nei vari caratteri, ad esempio con un algoritmo flood fill;
• ridimensionare ogni lettera individuata a 15×15 pixel;
• dare in pasto ogni carattere a una rete neurale a percettrone propriamente allenata.

Ciò detto, quale è l’accuratezza del sistema?

Risultati

Ho testato un’implementazione dell’algoritmo di cui sopra e i risultati sono stati i seguenti:

1. il CAPTCHA viene decodificato correttamente al primo tentativo in più del 90% dei casi su un campione di circa 100 immagini;
2. come spiegato nella parte 4 questo dato si riferisce a prove fatte su un campione di immagini diverse da quelle usate per l’allenamento della rete neurale (cross-validation), quindi la percentuale del 90% è rappresentativa dell’accuratezza reale;
3. ovviamente, se la decodifica non funziona al primo colpo si può ritentare. Visto che basta un solo tentativo a buon fine per rompere la protezione fornita dal CAPTCHA, la probabilità di successo nella pratica è ancora più alta: con con 3 tentativi si sbaglia su una sola lettura su mille, e con 6 tentativi una su un milione!

Note statistiche: nella ragionevolissima ipotesi che gli esiti delle letture di CAPTCHA siano indipendenti, segue che i risultati del punto 1 sono sufficienti per affermare che la percentuale di successo è sopra al 90% con significatività del 99%. Quanto descritto al punto 3 discende dalla stessa ipotesi, in quanto la probabilità P di successo complessiva è data da

P = 1-[(1-p)(1-p)(1-p)…] n volte

dove p è la probabilità di successo del singolo tentativo ed n il numero di tentativi.

Tecniche implementative

Nota Bene: i prossimi paragrafi sono dedicati ai programmatori ed alle persone con esperienza in ambito informatico – è normale che non risulti di facile comprensione agli altri lettori.

Come si possono tradurre in pratica le idee esposte fino a questo punto? Io ho usato questi strumenti:

• il linguaggio di programmazione Scala;
• l’ambiente di sviluppo Eclipse con il plugin Scala-IDE;
• il motore di reti neurali Encog;
• GIMP e (ugh!) LibreOffice Calc per alcune prove e prototipi.

Scala

Il linguaggio Scala è stato scelto per due ragioni:

1. è molto, molto compatibile con Java, permettendo in particolare di utilizzare librerie e classi Java esistenti. Naturalmente questo fa molto comodo per usare Encog, che è scritto proprio in Java!
2. rispetto a Java ha alcune caratteristiche interessanti, che se ben usate portano produrre a codice, a mio parere, molto più compatto e leggibile.

Ad esempio, è possibile definire classi i cui oggetti si usano come i vettori. Sembra inutile? Si pensi a come semplifica la vita poter scrivere codice come questo in una libreria che fa trattamento di immagini:

if (image(2, 3) == BLACK)){
    image(2, 3) = WHITE
}

Sfido qualunque programmatore a non capire il significato! E’ interessante anche notare che, per raggiungere questo risultato, non c’è bisogno di sintassi astruse, basta infatti definire due metodi particolari, apply ed update, come nell’esempio che segue:

class Image(...) {
    def apply(x:Int, y:Int):Int = {
        // ritorna in un intero il colore alla posizione (x,y)
    }
    def update(x:Int, y:Int, color:Int):Unit = {
        // cambia in color il colore del pixel alla posizione (x,y)
    }
}

Ancora una volta, a mio parere, estremamente leggibile. Ho usato codice di questo tipo per costruire un wrapper attorno a java.awt.Image, la classe Java per la gestione delle immagini, ottenendo una classe allo stesso tempo potente e semplice, in poche righe di codice.

Un’altra chicca simile è la possibilità di definire metodi con nomi strani, ad esempio +, – oppure |, ridefinendo in pratica gli operatori del linguaggio per classi specifiche. Ho usato questa particolarità per implementare i filtri delle immagini con una sintassi simile a quella delle shell Unix.

Credo che sia immediato capire il senso di questo codice:

image = read(new FileInputStream(file))
filteredImage = image | new DesaturateFilter() | new RemovePatternFilter(new FileInputStream("data/pattern.png")) | new ThresholdFilter(170) | ...

Per poter scrivere la riga di cui sopra basta implementare il metodo | di Image e definire una “classe astratta” che rappresenti un filtro:

class Image(...) {
  def |(filter:ImageFilter):Image = {
    filter.filter(this)
  }
}

trait ImageFilter {
  def filter(image:Image):Image
}

E’ da notare come in Scala è possibile usare semplici spazi al posto dell’operatore “.” tipico di Java, e si possano anche omettere le parentesi ove non ambiguo, e questo permette di scrivere

filteredImage = image | filter

al posto di

filteredImage = image.|(filter)

A mio parere, un vero colpo di genio! Scegliendo nomi appropriati per i metodi, infatti, questa caratteristica da sola porta a scrivere codice molto più simile al linguaggio naturale, quindi facile da comprendere, rispetto alle controparti Java. Altri esempi illuminanti:

count = collection size
heightInPixels = image height
calculator compute inputs

In questi esempi si sarà notato che sono omessi anche i terminatori di riga (“;” in Java). Questo è l’ennesimo piccolo beneficio di Scala: i terminatori si possono omettere ovunque non sia ambiguo. Perchè consumare tasti inutilmente?

Un’altro aspetto che mi piace molto di Scala è che nonostante sia un linguaggio staticamente tipato (come Java e a differenza di Groovy, Ruby o Python) non costringe ad usare sintassi prolissa per specificare i tipi degli oggetti ovunque. Mi spiego: supponendo di avere un metodo che accetta un oggetto Car e poi lo usa, in Java occorre scrivere qualcosa del tipo:

Brick demolish(Car car){
  Car myCar = car;
  return myCar.demolish();
}

In questo esempio, i tipi in grassetto non sono strettamente necessari: è evidente che myCar debba essere di tipo Car (poichè car è di tipo Car), analogamente dal momento che il metodo ritorna sempre e solo il risultato di Car.demolish() è ovvio che il risultato sia un’istanza di Brick. In Scala, dal momento che tutto questo è superfluo, può essere omesso:

def demolish(car:Car){
  val myCar = car;
  return myCar demolish
}

Il compilatore controlla tutti i tipi e completa le definizioni ovunque possibile, il che risparmia un bel po’ di digitazioni inutili (e facili da sbagliare). Ovviamente in caso di ambiguità ci sarà una segnalazione di errore, solo in quel caso sarà necessario specificare i tipi come in Java. L’aspetto interessante è che si arriva a scritture concise simili a quelle dei linguaggi tipati dinamicamente senza rinunciare agli utili controlli di coerenza del compilatore.

Encog

L’uso di Encog di per sè non è particolarmente bizzarro, nel senso che segue esattamente l’interfaccia Java documentata sul sito ufficiale. Ad esempio, questo è il codice per caricare una rete neurale allenata con l’Encog Workbench:

network = new BasicNetworkPersistor().load(new ReadXML(new FileInputStream("model.eg"))).asInstanceOf[BasicNetwork]

L’unica cosa degna di nota è l’ultima parte, asInstanceOf[BasicNetwork], che è l’equivalente di un cast in Java richiesto dal fatto che BasicNetworkPersistor.load() ritorna un EncogPersistedObject che è una sopraclasse di BasicNetwork. L’uso della rete vera e propria è addirittura banale:

inputs = new BasicNeuralData(rawInputs toArray)
outputs = network compute inputs

dove rawInputs non è che una List[Double].

Ecco il codice!

Viste le tecniche principali ed alcune curiosità sulla stesura del codice non resta, per chi ha ancora voglia di studiare, che prendere in mano il codice sorgente del programma!

Scarica il Progetto Eclipse per la decodifica dei CAPTCHA (zip, 1MB)

Il progetto contiene:

• la cartella training che contiene un sufficiente numero di CAPTCHA scaricati e decodificati manualmente per l’allenamento;
• il package net.moioli.moiosms.imagefilters contenente le implementazioni in Scala dei filtri grafici descritti nelle puntate precedenti;
• il package net.moioli.moiosms.training contenente:
  • il programma TrainingImagePreparer che prende i CAPTCHA nella cartella training, applica i filtri grafici e li scompone in singole lettere divise per allenamento e validazione;
  • il programma TrainingCsvGenerator che, prendendo le lettere generate dal programma precedente, crea file CSV che possono essere importati in Encog Workbench;
• data/letters.eg, un esempio di rete Encog già allenata in questo modo e soprattutto
• OCRTester, un programma che legge effettivamente i CAPTCHA come descritto in questi articoli!

Il modo più semplice per provare tutto questo è:

1. installare l’ultima versione di Eclipse per Java;
2. installare il plugin Scala-IDE, che contiene il compilatore Scala;
3. decomprimere lo zip;
4. importare il progetto (menù File, Import…, General, Existing Project into Workspace);
5. lanciare uno dei programmi con la voce Run as… Scala Application dal menù che compare cliccando con il tasto destro sul file corrispondente.

Dovreste ritrovarvi con una schermata simile alla seguente:

Conclusioni

Con questo articolo chiudo la serie sui CAPTCHA iniziata qualche mese fa. So che non è molto rispetto alla fine del progetto MoioSMS ma spero possa essere un adeguato punto di ripartenza per chi volesse ricominciarlo o semplicemente ampliare le proprie conoscenze. Scrivete pure nei commenti opinioni e domande!