Aggirare un CAPTCHA per divertimento e divulgazione – Parte 3

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

Filtraggio e rimozione delle imperfezioni

Sistemato il rumore, il compito successivo è quello di separare i caratteri uno dall’altro. In effetti è abbastanza ovvio: riconoscere una lettera è essenzialmente indipendente dalla sua posizione in un dato testo.

Questo passaggio, che all’uomo risulta naturale, è un po’ più ostico per le macchine: bisogna pensare a un modo per distinguere i contorni delle lettere, che però non sempre sono ben definiti.

Per semplificare il problema, si applica generalmente un filtro threshold, ossia “di soglia”. Il suo funzionamento è molto semplice: ogni pixel dell’immagine viene “riscritto” in colore bianco se aveva un colore chiaro, al di sotto di una certa soglia, oppure in nero in caso contrario. Credo che un esempio sia molto più facile da capire:

Applicazione di un filtro threshold a un CAPTCHA

Come si vede, i contorni sono più netti dopo il filtraggio, e adesso l’immagine è praticamente pronta per essere segmentata. Anche se si potrebbe procedere direttamente, ho preferito fare ancora qualche ulteriore operazione di miglioramento per eliminare alcune imperfezioni (più propriamente, artefatti) creati dal filtro precedente. Ne vediamo un esempio nell’immagine che segue:

Esempi di artefatti sorti dopo l'applicazione del filtro thresholdNella “B”, come si può notare, c’è un punto isolato nero, mentre nella “N” ce n’è uno bianco. In generale, siccome il filtro threshold viene applicato a immagini con una certa variabilità, può capitare che si creino delle piccole aree di colore isolate. Una soluzione per rimuovere questi difetti è contare, per ogni punto, quanti dei punti adiacenti sono bianchi: se sono la gran maggioranza, ad esempio più di 6 su 9, siamo di fronte a un pixel quasi isolato, e possiamo ricolorarlo in bianco. Discorso analogo si può fare, all’inverso, per i punti neri. Un’altra soluzione è quella di calcolare l’area di ogni parte dell’immagine con lo stesso colore, ed “eliminare” le aree molto piccole, ad esempio sotto i 10 pixel (certamente non rappresentano lettere). Io ho usato entrambi questi approcci, combinati, per rimuovere la maggior parte delle imperfezioni.

Correzione degli artefatti introdotti dal filtro threshold

Segmentazione dei caratteri

A questo punto siamo pronti per la segmentazione vera e propria. Nel caso del CAPTCHA di Vodafone, a questo punto, i caratteri sono ben separati fra di loro e contigui nei loro tratti, quindi l’operazione è particolarmente semplice. In generale questo è il punto più difficile in assoluto!

L’algoritmo che ho scritto per separare le lettere usa il “flood fill” ed è usato nei programmi di grafica per riempire aree dello stesso colore. L’esempio più noto è lo strumento “secchiello” di Microsoft Paint, che permette di riempire di un certo colore porzioni uniformi dell’immagine.
Schermata del funzionamento di Paint che illustra il flood fill
Dettagli tecnici: l’algoritmo percorre l’immagine da sinistra a destra a varie altezze ed ogniqualvolta incontra un punto nero:

  1. lo colora,
  2. colora tutti i punti adiacenti fino a riempire l’area contigua (ossia la lettera) ed infine
  3. cambia il colore (in modo che sia diverso per la prossima lettera).

Altri dettagli sugli algoritmi di flood fill, in particolare sul passo 2, sono reperibili sull’ottima pagina di Wikipedia.

Il risultato, anche se un po’ carnevalesco, rende perfettamente l’idea: le lettere sono separate.

Un CAPTCHA segmentato
A questo punto non resta che individuare, per ogni lettera, il più piccolo rettangolo che contenga tutti i punti dello stesso colore, quindi si possono estrarre le singole lettere.

Consiglio agli interessati dell’argomento una lettura dei manuali di Intelligenza Artificiale, in particolare consiglio caldissimamente il Russel-Norvig, una vera colonna portante della materia.

Prossimi passi

Scomposta l’immagine in lettere occorrerà normalizzarle per dimensione e, soprattutto, riconoscere i singoli caratteri, materia della prossima parte di questa serie di articoli. Si tratta della parte concettualmente più difficile, ma anche più interessante!

Tutto chiaro finora? Vai alla quarta parte!

3 Comments

  • Mitico Silvio, articoli interessantissimi. 😉

  • Bellissimo. Spiegato con una chiarezza disarmante…

  • davvero interessante, attendo i prossimi articoli 😉

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>