Articoli,howto,guide di programmazione & Informatica generale.

Nota: per comprensione codice: le immagini elaborate dal progrmma sono ppm P3 o P1, il programma provvede comunque a convertire da .png a .ppm con il comando "convert".

0.Introduzione

Una delle innumerevoli applicazioni delle reti neurali è quella del riconoscimento dei caratteri nelle immagini, utile per realizzare 0CR e simili. In questo paper spiegherò come è possibile strutturare una rete neurale affinchè riconosca i captcha utilizzati da phpbb2 per evitare l'iscrizione automatica, mostrando come l'ho implementata in C. Si presuppone che si abbiano delle conoscenze di base sulle reti neurali, farò comunque del mio meglio per spiegare il funzionamento di quella che ho usato. Eviterò di commentare le parti banali del codice, anche perchè questo non è un tutorial su come programmare e se si hanno dei dubbi riguardo alla programmazione esistono già parecchie guide su cui ci si può fare le ossa. Per riconoscere i caratteri ho proceduto utilizzando un algoritmo che divide l'immagine di partenza nelle 6 lettere che poi la rete riconosce una per una. Poi dovendo sfruttare una rete neurale, la fase di implementazione di questa si suddivide in apprendimento ed in fine si può passare a far lavorare la rete e verificare se ha imparato correttamente. Durante il paper mostrerò volta per volta le funzioni C che compiono il lavoro che sarà necessario fare, lascerò alla fine i sorgenti dei vari programmi.

1.Divisione del captcha nelle 6 lettere

Bene cominciamo! Vediamo innanzitutto come è fatto un captcha di phpbb2.


Vediamo che ha tutti pixel con sfumature di grigio (stessi valori RGB per rosso,verde e blu ) e che i contorni delle lettere non sono ben definiti, anzi, le lettere stesse non sono perfettamente definite, ovverero hanno al loro interno pixel di varia sfumatura di grigio, questo ovviamente per rendere il riconoscimento più difficile per chiunque non sia...una persona reale :-) Il nostro obbiettivo è quello di dividere le varie lettere e renderle in bianco e nero, per rendere la vita più facile alla rete rete neurale, che vedremo, sarà davvero semplice ma farà bene il suo dovere. Per fare questo troveremo le coordinate verticali e orizzontali delle rispettive 6 lettere, e le ritaglieremo sistemandole un po' mettendo infine tutto in una immagine ppm. Cominciamo con le coordinate x ("larghezze"). In pratica troviamo i numeri delle colonne dove iniziano e finiscono le sei lettere, ciccando su tutte le colonne dell'immagine iniziale che sono in tutto 320. Come verificare dunque se in una colonna è presente o no una parte di una lettera? Abbiamo detto che le lettere non sono ben definite, ma per far distinguere all'occhio umano i contorni (che quando vediamo il captcha a dimensione normale ci appaiono comunque abbastanza finiti) i pixel diventano di un grigio più scuro, che talvolta diventa nero. Assumianmo quindi che i pixel con valore RGB (in questo paper parlerò sempre di valore RGB al singolare perchè vengono trattate solo le sfumature di grigio) minore o uguale a 100 sono scuri abbastanza da non poter essere presenti nello sfondo. Abbiamo così un criterio per decidere se un pixel appartiene o no ad una lettera. Ecco la funzione che cicla su una colonna e verifica la presenza di almeno un pixel "grigio scuro".

int is_black_c(int img[50][320],int n){	
	int k;
	for(k=0;k<50;k++)
		if(img[k][n]) return 1;
	return 0;
}

Dato un numero n che identifica la colonna la funzione ritorna 0 se non vi è nemmeno un pixel settato a uno altrimenti ritorna 1.(in precedenza sono stati settati a uno tutti i pixel "grigio scuri" ed a 0 tutti gli altri). Questa funzione ci servità per ciclare su tutte le colonne dell'immagine di partenza e memorizzare quando c'è un cambiamento assenza di 1-presenza di 1 (inizio di una lettera) ed un cambiamento presenza di 1-assenza di 1 (fine di una lettera) in questo modo:

k=0;
for(j=0;j<6;j++){
		for(;!is_black_c(img,k);k++);
		w[j][0]=k;
		for(;(is_black_c(img,k)||is_black_c(img,k+1));k++);
		w[j][1]=(k-1);
		if((w[j][1]-w[j][0]+1)>42){redo=1;break;}
}

Questa parte di codice ripete per 6 volte le seguenti operazioni: -cicla su tutte le colonne fino a quando non ne trova una con un pixel nero -memorizza il numero della colonna, che corrisponde alla "coordinata x" che identifica l'inizio dell'immagine -cicla fintantoche la colonna corrente ha un pixel nero o ce l'ha quella successiva, questo perchè vi sono alcune lettere che purtroppo hanno una colonna senza alcun pixel scuro al loro interno, ma possiamo ovviare a questo controllando quella successiva -memorizza la colonna a cui è arrivato (che identifica la "fine" della lettera) Leggendo il secondo punto una domanda più che legittima che potrebbe sorgere è: "e se vi sono due lettere abbastanza vicine da essere separate solamente da una colonna bianca?". Bene, questo può capitare (anche se nella maggioranza dei casi non è così), ed ecco il perchè dell'ultima riga del ciclo for qui sopra: se la larghezza della lettera riconosciuta (coord. fine - coord. inizio + 1) è maggiore di 42 (dimensione massima di una lettera) il programma setta a 1 la variabile "redo" e interrompe bruscamente il ciclo. Ecco come prosege il programma:

while(redo){
	k=0;redo=0;
	for(j=0;j<6;j++){
		for(;!is_black_c(img,k);k++);
		w[j][0]=k;
		for(;is_black_c(img,k);k++);
		w[j][1]=(k-1);
	        if((w[j][1]-w[j][0]+1)>42){
			bl=(w[j][1]+w[j][0])/2;
			for(m=0;m<50;m++) img[m][bl]=0;
			redo=1;break;
		}
	}
}

Il ciclo for che riconoscere le lettere questa volta è più selettivo, per riconoscere la fine di un'immagine tiene conto solo della colonna corrente e, una volta trovata una colonna bianca, il ciclo si interrompe. E allora perchè c'è ancora un'instruzione che verifica che la larghezza della lettera riconosciuta non sia maggiore di 42? Beh, talvolta compaiono addirittura delle immagini attaccata l'una all'altra, ovvero senza alcuna clonna bianca che le divida.
In questo caso il programma taglia le due lettere facendo diventare bianca la colonna a metà tra le due e fa ripartire ancora una volta il ciclo di riconoscimento delle lettere.
Ecco un'animazione che mostra molto indicativamente il funzionamento dell'alg:


Bene, ora abbiamo finalmente salvato in un array a che punto del captcha inizia e finisce ciascuna delle 6 lettere (bordi "verticali" all'interno dei quali sono contenute le varie lettere). Per dividerle però abbiamo ancora bisogno delle coordinate y dei bordi orizzontali dell'imagine. Il procedimento è analogo a quello di prima e utilizza una funzione del genere:

int is_black_l(int img[50][320],int l,int a,int b){
	int k;
	for(k=a;k<=b;k++)
		if(img[l][k]) return 1;
	return 0;
}

Questa funzione controlla se in una parte di una linea è presente un pixel nero, come argomenti la coordinata y della linea e due coordinate x, che sono le due trovate prima. In pratica vengono controllati i pixel di una linea all'interno dei "bordi verticali" di cui prima abbiamo trovato le coordinate. Ecco il codice che fa questo:

for(j=0;j<6;j++){
	k=0;
	for(;!is_black_l(img,k,w[j][0],w[j][1]);k++);
	h[j][0]=k;
	h[j][1]=k+26;
}

Viene trovata la prima "coordinata y" e l'altra viene memorizzata aggiungendo 26, siccome l'altezza delle lettere è sempre 27. Animazione indicativa:

Bene, ora abiamo le varie coordinate che ci servono per ritagliare le sei lettere. Un ulteriore operazione che si compie è quella di settare a 1 tutti i pixel che hanno tra gli 8 pixel attorno a se almeno un pixel settato a 1. ("grigio scuro"). Questo per rendere neri anche i pixel di grigio più chiaro contenuti all'interno della lettera da dare in pasto alla rete neurale. Ecco come si presentano le immagini che vengono passate come input alla rete neurale:

2.Il cuore del riconoscimento: la rete neurale

Ora, come progettare la rete neurale? La rete che useremo è abbastanza semplice, come input gli viene passato un vettore che rappresenta l'immagine, non ha alcun "hidden layer" e come routput restituisce 35 output numerici. Il vettore di input non è altro che l'insieme dei pixel che compongono l'immagine del carattere ottenuta con le varie operazioni spiegate prima. Per rendere tutti i vettori input della stessa dimensione, vengono aggiunti dei pixel bianchi al fondo di ogni riga, in modo da ottenere sempre un'immagine 42*27 cioè un vettore di 1134 pixel (1 o 0) Ecco uno schema che illustra la rete che viene utilizzata:

La rete neurale restituisce 35 output perchè 35 sono i possibili caratteri che si trovano nei captcha di phpbb2 (1..9, A..Z). A ogni "neurone" output sono collegati 42*27 pesi sinattici.
Come funzione di trasferimento usiamo la semplicissima f(x)=x, quindi per trovare il valore output dato da un neurone è sufficiente calcolare la media pesata tra input e pesi: Per addestrare la rete a riconoscere le lettere useremo l'apprendimento supervisionato, aggiornando ogni volta i pesi sfruttando questa formula: Δw_ij = -ηD_jx_i Dj è pari alla differenza tra l'output desiderato e quello fornito moltiplicata per f'(Pj) dove f'(x) è la derivata della funzione di trasferimento e Pj è il potenziale post-sinattico, mentre la lettera eta è il "coefficiente di apprendimento" Nel nostro caso la derivata della funzione di trasferimento è sempre pari a 1, quindi in generale la variazione ("delta") di un peso è pari al prodotto coefficiente di apprendimento (numero compreso tra 0 e 1)*differenza tra input desiderato e input fornito alla rete*input fornito. Per l'apprendimento verrà quindi calcolato ogni volta l'output della rete con la sommatoria input*pesi con i pesi correnti, e poi verrando modificati uno per uno i pesi aggiungendogli il prodotto: coeff.di appr.*(out.desiderato-input collegato al peso)* input_collegato al peso. Come output desiderato diamo 1, mentre i vari input possono essere 0 o 1 (pixel bianco/nero). Come coefficiente di apprendimento scegliamo 1/1134 che è 1/n.input , questo perchè se osserviamo la formula notiamo che la correzione su ogni singolo peso viene fatta tenendo conto dell'output generale della rete e di quello collegato al peso; questo andrebbe bene se ci fosse un unico input, ma ce ne sono diversi. Il coefficiente di apprendimento "mitiga" la correzione al peso, in modo da non far divergere la funzione d'errore, che noi invece vogliamo far convergere ad un valore prossimo a 0. In pratica durante l'apprendimento i pesi si modificano in modo tale un pixel che è sempre stato nero negli esempi forniti abbia un peso alto ed un pixel che è sempre stato bianco abbia un peso nullo. Poi ho avuto l'idea di dare come input il "negativo" dell'immagine di esempio e come output desiderato -1. In questo modo i pixel che sono bianchi nelle immagini di esempio assumono un peso negativo. Questo va bene quando diamo come input alla rete una lettera che non è quella che i pesi riconoscono: i pixel che normalmente erano bianchi nella lettera riconosciuta e che ora sono neri attivano un peso negativo e influenzano l'output della rete abbassandolo. Infatti sceglieremo come lettera riconosciuta quella a cui corrisponde l'output più alto tra i 35 dati dalla rete. Per preparare l'apprendimento è necessario avere una buona quantità di captcha di cui si conoscono già i caratteri, per fare questo ho installato phpbb2 in localhost e ho fatto uno script in php che scarica i captcha, leggendo dal database mysql quali sono i caratteri del captcha, dato che phpBB li salva nella tabella "confirm". Tutti i captcha vengono salvati in rispettivi file .png mentre i caratteri in un .txt ceh verrà poi utilizzato dal programma che istruisce la rete neurale. Ecco lo script php:

#!/opt/lampp/bin/php
<?
$i=0; //Ho scelto di scaricare 2000 captcha per addestrare la rete, ma l'unico limite è la capienza dell'hard disk!
while($i<2000){
	//prima parte, tramite delle richieste GET ottiene l'immagine captcha, che salva in un file,
	//e degli id che servono per la query al database
	$fp=fsockopen("localhost",80);
	fputs($fp,"GET /phpbb2/profile.php?mode=register&agreed=true HTTP/1.1\r\n".
		  "Host: localhost\r\n".
		  "Connection: Close\r\n\r\n");
	$reply="";
	while (!feof($fp)) $reply.=fgets($fp,1024);
	fclose($fp);
	$find=array();
 
	preg_match('/Set-Cookie: phpbb2mysql_data=(.+?);/'
,$reply,$find);
	$data=$find[1];
	preg_match('/\<img src="profile\.php\?mode=confirm&amp;id=(.+?)&amp;sid=(.+?)"/',$reply,$find);
	$cid=$find[1];
	$sid=$find[2];
	$fp=fsockopen("localhost",80);
	fputs($fp,"GET /phpbb2/profile.php?mode=confirm&id=".$cid."&sid=".$sid." HTTP/1.1\r\n".
		  "Host: localhost\r\n".
		  "Connection: Close\r\n".
		  "Cookie: phpbb2mysql_data=".$data."; phpbb2mysql_sid=".$sid.";\r\n\r\n");
	$img="";
	while (!feof($fp)) $img.=fgets($fp,1024);
	fclose($fp);
	preg_match('/PNG/',$img,$find,PREG_OFFSET_CAPTURE);
	$name=sprintf("%d.png",$i);
	$fp=fopen($name, "w");
	fwrite($fp,substr($img,$find[0][1]-1));
	fclose($fp);
 
	//seconda parte, effettua la query da cui ottiene i caratteri presenti nel captcha.
	//questo, ovvviamente,su un altro server non si può fare!
	$m=mysql_connect("localhost","root","mia_passwd");
	mysql_select_db("mio_db",$m);
	$query="SELECT code FROM phpbb_confirm WHERE session_id='".$sid."' AND confirm_id='".$cid."'";
	$res=mysql_query($query,$m);
	$r=mysql_fetch_row($res);
	$fp=fopen("let.txt","a+");     //salva i caratteri nel file "let.txt" che verrà poi utilizzato
	fwrite($fp,$r[0]);             //dal programma di apprendimento
	fclose($fp);
	$i++;
}
?>
 

Dopo questo ho utilizzato l'algoritmo di prima per dividere tutti i captcha ottenendo così le complessive 12000 lettere che verranno utilizzate per l'apprendimento. (per i sorgenti vedi al fondo del paper). Dopo queste operazioni si può finalmente addestrare la rete neurale e salvare i pesi finali, per poi riutilizzarli quando si vuole leggere un captcha. Ecco la parte principale del programma che fa questo, ampiamente commentata:

main(){
	double p[35][1134],n=(double)1/(double)1134,output,des; //notare le variabili p[35][1134] (tutti i pesi)
	int *inp=(int*)malloc(sizeof(int)*1134),t,i,j;          //e il coefficiente di apprendimento n=1/1134
	char img[25];
	FILE *fp;
	//tutti i pesi a zero
	for(i=0;i<35;i++)
		for(t=0;t<1134;t++) p[i][t]=0;
	//apro il file che contiene le lettere
	fp=fopen("let.txt","r");
	//apprendimento sulle 12000 immagini pre-scaricate,divise,numerate e poste nella cartella s
	for(i=0;i<11999;i++){
		j=fgetc(fp);
		j=(j<58) ? (j-49):(j-56);  //l'apprendimento verrà fatto sui p[j] ovvero i pesi che corrispondono
					   //alla lettera da apprendere, qui p[0] corrisponde a "1"...p[8] a "9" p[9] ad 
                                           //"A"...p[34] a "Z"
 
		sprintf(img,"s/%d.ppm",i); //nome del file da cui leggere i pixel (questi file sono numerati e salvati 
					   //nella cartella s
		inp=get_inp(img);          //funzione che salva nell'array inp il vettore di pixel input-vedi sorg. al fondo
		output=out(inp,p[j]);      //funz. sommatoria che calcola l'output con i pesi correnti 
		des=1;			   //l'output desiderato è 1
 
		for(t=0;t<1134;t++)        //ciclo di apprendimento su tutti i pesi
			p[j][t]+=n*(des-output)*inp[t]; //ecco la formula!
							//peso+=coeff.di appr.*(out.des.-out.corrente)*inp.collegato al peso
 
		des=-1;			   //seconda parte: output desiderato=-1
		for(t=0;t<1134;t++)	   //ciclo sugli input, che vengono inveriti ("immagine negativa")
			inp[t]=!inp[t];
 
		output=out(inp,p[j]);      //si ricalcola l'output con i pesi correnti
		for(t=0;t<1134;t++)	   //altro ciclo di apprendimento, esattamente identico a prima
			p[j][t]+=n*(des-output)*inp[t];
	}
	fclose(fp);                        //vengono salvati nel file p.txt tutti i pesi
	fp=fopen("p.txt","w");             //che verranno poi letti e utilizzati dal programma che legge i captcha
	for(i=0;i<35;i++){
		fprintf(fp,"/\n");
		for(t=0;t<1134;t++)
			fprintf(fp,"%.25lf\n",p[i][t]);
	}
	fclose(fp);
}
 

Il programma che legge i captcha non farà altro che caricare i pesi salvati e osservare quale "neurone ouput" fornisce l'output più alto. Questo output, che possiamo definire una sorta di "numero di attinenza", più è alto più la lettera passata in input assomiglia a quella con cui si sono addestrati i pesi collegati a quel neurone input. Il programma sceglie il maggiore e stampa la lettera ssociata.

Elenco completo sorgenti:

script in php per scaricare i captcha di apprendimento e memorizzare le lettere che questi contengono: down.php.
programma che estrae le lettere dai captcha di apprendimento e le salva nella directory s: split.c.
programma che addestra la rete utilizzando le lettere salvate nella cartella s e salva i pesi in un file: learn.c.
programma finale che carica i pesi e stampa in output le lettere contenute in un captcha: cap_r.c.
Il file con i pesi ("p.txt" usato dal prog. che legge i capathca) che ho generato io (2000 captcha per l'apprendimento) lo potete trovare qui.
Guida redatta da Certaindeath.