Reti neurali e riconoscimento di caratteri |
 |
 |
 |
|
|
|
Il grande interesse di questi ultimi anni per le reti neurali si è in parte riflesso anche nel campo del riconoscimento di caratteri. E' da notare tuttavia come la gran parte dei lavori sull'argomento utilizzino reti feedforward multistrato con addestramento a back-propagation (Rumelhart et al., 1986), mentre solo una piccola frazione di ricercatori si è indirizzata verso le reti di Kohonen (1984) e altre architetture. Lo scopo che questo capitolo si prefigge è fornire una breve panoramica dello stato della ricerca in questo campo, individuando alcuni lavori significativi e riportandone in sommario gli obiettivi e i risultati.
Il problema del riconoscimento dei caratteri maiuscoli usati sulle carte idrografiche, indipendentemente dalle dimensioni, dalla posizione e dall'orientamento dei caratteri stessi, è stato affrontato da Gullichsen e Chang (1987). Una volta isolato dall'immagine, il pattern del carattere viene trasformato in una matrice normalizzata da 16x16 pixel e sottoposto ad un processo di scheletrizzazione (Rosenfeld & Kak, 1976), in conseguenza al quale viene prodotta una matrice da 7x7 pixel a 16 livelli di grigio. Questo esperimento non prevede l'estrazione di feature, ma la semplice presentazione di quest'ultima matrice ad una rete feedforward a due strati, con 26 neuroni sia nello strato di uscita che in quello nascosto, addestrata col metodo della back-propagation. Nel lavoro citato non vengono riportate misure quantitative delle prestazioni, che vengono peraltro qualificate come buone sia sotto l'aspetto del tasso di riconoscimento, sia sotto quello della velocità di esecuzione.
L'invarianza per traslazione, rotazione e variazione di dimensioni nel riconoscimento di caratteri maiuscoli è ancora il tema del lavoro di Khotanzad e Lu (1988), in cui viene utilizzata una rete feedforward a due strati con 7 ingressi e 26 uscite, addestrata con l'algoritmo di back-propagation. Le feature usate come componenti del vettore di ingresso sono costruite con degli invarianti ricavati dai momenti geometrici del pattern (Hu, 1962), e vengono eseguiti diversi esperimenti per stabilire il numero ottimale di neuroni nascosti. Facendo variare tale valore tra 5 e 200, il risultato migliore, pari a un tasso di riconoscimento del 98%, viene ottenuto con 51 neuroni nascosti.
Lo studio di Denker et al. (1989) riguarda invece il riconoscimento dei caratteri numerici manoscritti usati nei codici postali. La sequenza di cifre viene in primo luogo localizzata sulla busta -- problema di per sé tutt'altro che semplice -- mediante tecniche specifiche messe a punto da Wang e Srihari (1988); i singoli caratteri vengono quindi normalizzati rispetto all'inclinazione facendo ricorso al metodo dei momenti (Casey, 1970), digitalizzati in una matrice da 20 x 32 pixel e sottoposti infine a un algoritmo di thinning. A questo punto, in analogia con i processi che si ritiene abbiano luogo nella corteccia visiva primaria (Hubel & Wiesel, 1962), vengono utilizzate tecniche di convoluzione per estrarre dal pattern un insieme di 49 feature distinte, corrispondenti ai vari orientamenti possibili di un segmento rettilineo e delle sue estremità; il vettore di feature così costruito viene infine applicato a un classificatore. A scopo di valutazione e confronto, vengono sperimentati tre tipi diversi di classificatori, di cui due di tipo classico (metodo delle Parzen windows e metodo dei K-nearest neighbors), entrambi descritti molto lucidamente nel libro di Duda e Hart (1973), e il terzo implementato mediante una rete neurale feed-forward a due strati, dotata di 40 neuroni nascosti. Su una base di dati costituita da 10 000 pattern reali forniti dallo U.S. Postal Service, la rete neurale risulta avere il comportamento migliore fra i tre classificatori sia quando viene ammesso il rifiuto di un pattern che quando viene richiesta una classificazione qualsivoglia: nel primo caso, viene riportato un tasso di rifiuto del 14% associato a un tasso di errore dell'1%, mentre nel secondo caso si ha un tasso di riconoscimento del 94%.
Ancora sull'impiego di reti feedforward a due strati per il riconoscimento di caratteri numerici manoscritti verte la ricerca di Yamada et al. (1989). Ciascun carattere viene digitalizzato producendo una matrice binaria da 32 x 40 pixel che viene poi sottoposta a un filtro gaussiano per ottenere una matrice da 9 x 11 valori continui, oppure viene utilizzata per estrarre i contorni del pattern e con questi costruire un vettore di feature da 640 elementi. Vengono sperimentate tre diverse reti neurali: le prime due accettano come ingresso la matrice 9 x 11, alla terza viene invece applicato il vettore di feature; i neuroni nascosti della prima e della terza rete ricevono connessioni da tutti gli elementi di ingresso, mentre quelli della seconda vengono connessi solo a determinati sottoinsiemi degli ingressi. La base di dati utilizzata contiene 10 000 caratteri, e tutte le reti vengono addestrate sia con l'algoritmo standard di back-propagation che con una sua variante, appositamente proposta per verificarne le migliori prestazioni. I risultati riportati dimostrato innanzi tutto che quest'ultima variante, oltre a richiedere un tempo di addestramento tre volte inferiore, consente alle reti di memorizzare tutti i vettori del training set, contrariamente a quanto accade invece con la back-propagation standard; i tassi di riconoscimento ottenuti sono poi del 98.3%, del 98.8% e del 99.1% rispettivamente per le tre reti utilizzate.
La lettura di testi manoscritti più generali dei codici postali è trattata da Burr (1987), che descrive un sistema in cui la classificazione dei caratteri, basata su una rete neurale feed-forward a due strati, viene verificata e raffinata con l'ausilio di un dizionario di parole. Il vettore di feature utilizzato è formato da 13 componenti, ricavate dalle proiezioni del pattern incognito lungo altrettante rette variamente orientate; la rete viene addestrata con l'algoritmo di back-propagation, e vengono eseguiti vari esperimenti con un numero variabile di neuroni (da 12 a 24) nello strato nascosto, mediante i quali viene messo in evidenza un fenomeno piuttosto curioso, per cui il tasso di riconoscimento della rete peggiora sensibilmente quando il numero di neuroni nascosti supera una certa soglia. In ogni caso, le migliori prestazioni riportate parlano di tassi di riconoscimento del 94% e del 99.7%, rispettivamente senza e con l'ausilio del dizionario. A conclusione della sperimentazione, vengono poi proposti due metodi di implementazione dello stesso dizionario con reti neurali.
Un altro sistema per il riconoscimento di caratteri manoscritti che non fa uso di feature viene descritto da Martin e Pittman (1990). Il pattern viene confinato in una matrice da 15 x 24 pixel ed applicato all'ingresso di una rete feed-forward a due strati, addestrata mediante back-propagation; come in ricerche analoghe, il numero dei neuroni nascosti viene fatto variare tra 50 e 383 per determinarne l'influenza sul tasso di riconoscimento. Le migliori prestazioni ottenute danno un tasso di errore del 4-5% con nessun pattern rifiutato, e dell'1-2% con un tasso di rifiuto del 10%.
I ricercatori giapponesi hanno particolarmente a cuore il problema del riconoscimento automatico dei circa 3000 caratteri Kanji manoscritti usati comunemente in Giappone, e il lavoro di Mori e Yokosawa (1989) si prefigge di affrontare alcune fasi preliminari di questo difficile problema. I caratteri Kanji sono costituiti dalla combinazione di due tipi di radicali sinistri e di due tipi di radicali destri, piuttosto somiglianti tra di loro e quindi difficili da discriminare. Nel metodo di classificazione descritto da Mori e Yokosawa, dove viene usata una rete neurale feed-forward a due strati addestrata mediante back-propagation, vengono sperimentati due tipi diversi di vettori di feature, rispettivamente a 64 e 256 componenti, ottenendo tassi di riconoscimento rispettivamente dell'82.5% e del 92.0% su pattern non facenti parte del training set. Al di là delle prestazioni misurate, il risultato probabilmente più interessante di questo studio risiede nella scoperta che i neuroni dello strato nascosto sembrano in grado di discriminare la struttura a due radicali in cui si articolano i caratteri Kanji.
L'obiettivo più ambizioso, relativo al riconoscimento di caratteri sia stampati che manoscritti, di varie dimensioni e font, con bassi tempi di elaborazione e buoni livelli di efficienza e versatilità, costituisce il tema del lavoro di Rajavelu et al. (1989). Il pattern del carattere viene convertito in un vettore di 20 feature costruite mediante la trasformata di Walsh ed applicato ad una rete feed-forward a due strati con 40 neuroni nascosti e 7 neuroni di uscita, i cui valori di attività, una volta discretizzati, vengono usati per codificare la classe di appartenenza del carattere. La rete viene addestrata con l'algoritmo di back-propagation, e richiede da 1153 a 5127 iterazioni per la convergenza, a seconda del training set selezionato, fornendo tassi di riconoscimento dal 97% al 99%.
Non vi è mai stato accordo tra i ricercatori su quali, tra tutti i tipi di feature proposti nella letteratura sul riconoscimento di caratteri manoscritti, siano i più adatti e come vadano combinati per ottimizzare le prestazioni dei classificatori. L'argomento viene affrontato ancora una volta nel lavoro di Weideman et al. (1989), dove vengono valutati diversi tipi di feature (i momenti geometrici, le feature topologiche, i coefficienti della trasformata bidimensionale di Fourier e le proiezioni) applicandole ad un classificatore di tipo nearest neighbor e ricavando così una stima della loro utilità attraverso la categorizzazione dei pattern contenuti in una vasta base di dati. Lo studio conclude che le feature utilizzate, anche se combinate tra di loro, non sono da ritenersi sufficienti per una classificazione esente da errori, anche perché il numero di pattern di riferimento necessari risulta essere eccessivamente grande. Viene poi fatto un confronto di prestazioni tra il classificatore nearest neighbor e una rete feed-forward con 100 ingressi, 90 neuroni nello strato nascosto e 10 neuroni nello strato di uscita, addestrata con back-propagation. I due classificatori risultano avere prestazioni analoghe, sebbene, analizzando i requisiti computazionali, la rete neurale appaia più efficiente per un fattore 20-30 in termini sia di quantità di memoria utilizzata che di numero di operazioni necessarie per ciascuna decisione.
Accanto alla semplicità della struttura delle reti feed-forward e dell'algoritmo di back-propagation, vi sono due problemi importanti ad essi connessi che i ricercatori si trovano continuamente a dover affrontare: la lentezza della procedura di addestramento, dovuta al gran numero di iterazioni richieste per la convergenza dei pesi della rete, e il numero ottimale di neuroni da prevedere negli strati nascosti, che in genere viene determinato per tentativi o fissato senza particolari motivazioni teoriche. Tra i molti lavori che si sono occupati di queste questioni, citiamo qui solo quello di Kramer e Sangiovanni-Vincentelli (1989), che danno una lettura del processo di addestramento delle reti neurali feed-forward in termini di un problema di ottimizzazione, mostrando come diventi così possibile utilizzare molti algoritmi di programmazione che sono stati sviluppati nel corso degli anni per altre classi di applicazioni. In particolare, il lavoro dimostra come uno di tali algoritmi, noto come regola di Polak-Ribiere, goda di proprietà di convergenza e di velocità di esecuzione significativamente migliori che non l'algoritmo di back-propagation, e sia particolarmente adatto ad essere implementato su macchine parallele come la Connection Machine (Hillis, 1986). La nuova procedura proposta viene sperimentata su una rete feed-forward a due strati con 26 neuroni nello strato di uscita (tante quante sono le lettere maiuscole nell'alfabeto inglese) e 10 neuroni nello strato nascosto; viene poi utilizzato un training set di 64 insiemi distinti delle 26 lettere maiuscole, tracciate a mano, digitalizzate in una matrice da 80 x 120 pixel convertita in un vettore a 100 componenti. L'obiettivo di un tasso di riconoscimento del 99.6% viene raggiunto dopo sole 46 iterazioni dell'algoritmo proposto, contro le 657 richieste dall'algoritmo standard di back-propagation.
La grande popolarità delle reti feed-forward multistrato non deve tuttavia offuscare certi significativi risultati che nel campo del riconoscimento di caratteri sono stati ottenuti utilizzando altre architetture neurali. Un interessante passo preliminare all'uso di reti neurali capaci di autoorganizzazione nel riconoscimento di caratteri viene descritto da Allinson et al. (1989), dove in concomitanza all'impiego di una rete di Kohonen per la classificazione, l'eliminazione del rumore e il centraggio dei pattern, viene anche proposto un ingegnoso metodo per accelerare l'esecuzione degli algoritmi necessari su un calcolatore sequenziale.
Nel lavoro di Lee e Oldham (1990) vengono utilizzati due poco usuali ma molto interessanti modelli sincroni di reti neurali introdotti da Hogg e Huberman (1984, 1985), di tipo feed-forward, che si comportano in maniera per certi versi analoga ai sistemi dinamici dissipativi e che trasformano un ingresso in uno stato finale stabile, assimilabile a un bacino di attrazione. Le due reti, ciascuna costituita da una cascata di reti di piccole dimensioni, vengono addestrate su un set di 156 caratteri inglesi maiuscoli stampati appartenenti a 6 font diversi, digitalizzati in una matrice da 18 x 18 pixel e trasformati in vettori da 14 feature (Fujii & Morita, 1971). Il tasso di riconoscimento riportato è dato al 100%.
Il confronto tra varie architetture di reti neurali ai fini del riconoscimento di caratteri numerici manoscritti è l'oggetto di tre lavori piuttosto interessanti. Nel primo, dovuto a Pawlicki et al. (1988), vengono discusse le prestazioni dei sistemi lineari auto-associativi (Cooper et al., 1979), delle reti di Hopfield (Hopfield, 1982), delle reti con logica a soglia (Brown, 1987), delle reti addestrate con back-propagation e delle macchine di Boltzmann (Hinton & Sejnowski, 1986), e si perviene alla conclusione che, a parità di rappresentazione dei dati, non vi è evidenza che le reti neurali siano significativamente migliori degli approcci standard con matching simbolico: le due tecniche vanno tuttavia considerate non tanto mutuamente esclusive ma piuttosto complementari. Il secondo lavoro, dovuto a Guyon et al. (1989), utilizza sia la rappresentazione in pixel del pattern sia la rappresentazione in feature (punti estremali, segmenti, etc., ottenuti dopo scheletrizzazione del pattern) per valutare le prestazioni di diversi classificatori organizzati come reti neurali modulari complesse, ognuna costituita da tante sottoreti rivolte alla soluzione di singoli sottoproblemi; come sottoreti vengono sperimentate strutture a uno o più strati con connessioni adattative, strutture ricorrenti completamente connesse e strutture con pesi predeterminati. Nel terzo lavoro (Taraglio, 1990) vengono infine valutati i risultati di una serie di esperimenti condotti sulle macchine di Boltzmann e sulle reti di Kohonen, individuandone e discutendone i relativi vantaggi e inconvenienti nelle applicazioni OCR (si veda in proposito la Sez. 11).
Sembra che tra i ricercatori vi sia una crescente consapevolezza che la complessità del problema del riconoscimento di caratteri non consenta di trovare soluzioni accettabili utilizzando strutture neurali semplici, ma che sia indispensabile il ricorso ad architetture piuttosto complesse, preferibilmente di tipo modulare.
Mehr e Richfield (1987) propongono un'architettura a due reti neurali per un sistema OCR commerciale, dove la prima rete, pre-addestrata e senza possibilità di alterazione della configurazione, viene utilizzata per la gran parte del processo di riconoscimento, e la seconda interviene in maniera adattativa quando la prima incorre in errori. Il lavoro citato presenta una discussione piuttosto interessante delle problematiche che deve affrontare un classificatore di caratteri a reti neurali; tuttavia, va sottolineato come gli evidenti fini commerciali dello studio condotto inducano gli autori a tacere ulteriori particolari sulle architetture di rete utilizzate e sulle prestazioni misurate.
La possibilità di evitare l'estrazione di feature, e di applicare quindi il pattern originale alla rete classificatrice, viene dimostrata da LeCun et al. (1990) in un sistema per il riconoscimento di codici postali manoscritti. La base di dati è un soprainsieme di quella usata da Denker et al. (1989), ed è costituita da 9298 caratteri forniti dall'U.S. Postal Service, cui sono state aggiunte 3349 cifre stampate in 35 font diversi. I pattern vengono normalizzati con una trasformazione lineare in una matrice da 16 x 16 pixel a valori continui, che viene direttamente applicata ad una rete feed-forward di struttura piuttosto complessa (LeCun et al., 1990a), per conseguire un certo grado di invarianza alle traslazioni e alle distorsioni del pattern. Sono previsti quattro strati nascosti, ognuno a sua volta strutturato in lamine bidimensionali di neuroni: i vari strati hanno rispettivamente 4 lamine da 24 x 24 neuroni ciascuna, 4 lamine da 12 x 12 neuroni, 12 lamine da 8 x 8 neuroni, e 12 lamine da 4 x 4 neuroni; infine, lo strato di uscita ha 10 neuroni, tante quante sono le cifre da riconoscere. La rete viene addestrata mediante back-propagation, e, dopo un numero sorprendentemente basso (30) di iterazioni, fornisce un tasso di errore del 3.4%.
Szu e Scheff (1989) partono dall'osservazione che i classificatori operano in maniera tanto più affidabile quanto più i vettori di feature relativi a categorie diverse sono mutuamente ortogonali, e giungono così ad una variante della procedura di ortogonalizzazione di Gram-Schmidt implementata mediante una rete neurale multilayer, addestrata con un algoritmo parzialmente supervisionato e applicata infine al riconoscimento di codici postali manoscritti.
Ancora al problema dei caratteri Kanji più comuni è dedicato lo studio di Mori e Joe (1990), dove viene usata una rete neurale molto complessa, costituita da 30 piccole reti addestrate a riconoscere sottoinsiemi di caratteri, le cui uscite vengono applicate ad una rete finale che provvede alla classificazione definitiva. Il tasso di riconoscimento riportato per un insieme di 270 caratteri Kanji si aggira attorno al 93%.
In questa sezione riportiamo alcune informazioni su ricerche che non riguardano direttamente il problema della classificazione di caratteri, ma che in misura più o meno significativa possono avere interesse nel contesto di un sistema OCR completo.
Il problema della verifica del corretto montaggio dei circuiti integrati nei sottoassiemi elettronici viene affrontato da Morris et al. (1989) sperimentando due diverse reti neurali per la determinazione dell'orientamento -- verso l'alto o verso il basso -- delle sigle stampate sui contenitori dei dispositivi, a partire dall'immagine del sottoassieme. I risultati riportati per le due reti, l'una di tipo feed-forward con pesi predeterminati, l'altra di tipo Kohonen, sono buoni per entrambe, a parte il tempo di addestramento che per la prima rete è ovviamento nullo.
Mighell et al. (1989) affrontano invece il problema della verifica delle firme. La firma viene ripresa da una telecamera CCD, digitalizzata in una matrice da 128 x 64 pixel ed applicata, a fini di confronto, a diversi tipi di reti neurali feed-forward, sia a singolo che a doppio strato; queste ultime vengono addestrate con l'algoritmo della back-propagation, sottoposto però ad alcune modifiche (Rosenberg & Sejnowski, 1986; Rumelhart et al., 1986). Nelle migliori prestazioni ottenute, è stato ottenuto il 2% di firme vere ma classificate come false, e il 2% di firme false accettate come vere.
Nel lavoro di Jackel et al. (1988), infine, viene proposto un chip per il riconoscimento di caratteri numerici manoscritti, dotato di circa 3000 connessioni programmabili. Il pattern viene digitalizzato in una matrice da 16 x 16 pixel e, tramite il chip, viene sottoposto a un processo di thinning; il chip viene poi riprogrammato e utilizzato per l'estrazione di un certo numero di feature, con le quali si procede infine alla classificazione, sperimentando diverse tecniche a fini di confronto. I tassi di riconoscimento riportati variano dal 90% al 99%, in funzione della qualità del carattere.
Il riconoscimento di caratteri è uno di quei problemi ancora non del tutto soddisfacentemente risolti che continuano ad attirare l'interesse dei ricercatori nel campo delle reti neurali. Allo stato attuale, non sembra che i risultati ottenuti siano significativamente migliori di quelli che è possibile conseguire con tecniche classiche come il pattern matching e l'analisi delle feature, sebbene in molti casi le strutture neurali usate possano essere considerate come implementazioni alternative degli algoritmi classici. Il fatto che la grandissima maggioranza delle reti neurali utilizzate per il riconoscimento e la classificazione siano di tipo feed-forward multistrato, induce a ritenere che non sia possibile dare un parere definitivo senza prima aver indagato a fondo le possibilità offerte da architetture diverse. Ad esempio, è nostra opinione che strutture come le reti di Kohonen, usate eventualmente come moduli nel contesto di architetture più complesse, possano essere di grande aiuto nella classificazione multifont per via delle loro caratteristiche peculiari e probabilmente ancora non del tutto esplorate.
|
|||||||
© 1997-2003 Paolo Marincola (Rome, Italy)
e-mail: pmaNOSPAM@acm.org (eliminare
i caratteri "NOSPAM" per ottenere l'indirizzo esatto)
Commenti, osservazioni e suggerimenti sono estremamente graditi.
Last revised: 2003-11-09 00:30