Reti neurali e riconoscimento di caratteri |
 |
 |
 |
|
|
|
Come abbiamo visto nella Sez. 2, il principale problema da affrontare nel progetto di un sistema OCR è costituito dal classificatore di caratteri, anche se altre questioni, come la segmentazione della pagina, non sono certamente da considerare secondarie. Il lavoro di ricerca nel campo del riconoscimento di caratteri e della costruzione dei relativi classificatori è stato notevolissimo in passato e si protrae ormai da parecchi anni; la valutazione di ogni innovazione in questo campo non può dunque prescindere dalla conoscenza del lavoro svolto e dei risultati conseguiti, per cui abbiamo ritenuto importante fornire, nonostante i limiti del presente rapporto, un breve resoconto delle varie tecniche che sono state via via sottoposte a sperimentazione.
Naturalmente, gli studi sul riconoscimento di caratteri hanno avuto per oggetto testi scritti non solo con caratteri dell'alfabeto latino, ma anche in lingue come il cinese, il giapponese, l'indiano, il coreano, l'arabo, e così via; è chiaro, tuttavia, che molte tecniche escogitate per il riconoscimento dei caratteri appartenenti a queste lingue possono essere senz'altro utilizzate anche nel caso dei caratteri latini. Allo stesso tempo, possono essere sfruttate in vario modo diverse procedure sviluppate per il riconoscimento di caratteri manoscritti, con esclusione di quelle dette on-line, nelle quali viene fatto pesante uso di informazioni legate al modo di scrivere i caratteri (traiettoria seguita, velocità di scrittura, pressione sul foglio, etc.), che ovviamente non sono disponibili nel caso di testi stampati o non direttamente manoscritti.
Le metodologie usate nei sistemi per il riconoscimento di caratteri possono essere classificate in base a diversi criteri (Govindan & Shivaprasad, 1990), tra i quali citeremo qui soltanto:
Nel corso di vari anni, la ricerca ha individuato due gruppi principali di metodi per il riconoscimento di caratteri (direttamente corrispondenti, peraltro, alle due tecniche fondamentali con cui viene affrontato il problema più generale del riconoscimento di forme): un primo metodo che parte da considerazioni desunte dalla statistica e dalla teoria della decisione (che chiameremo approccio statistico), e un secondo fondato su considerazioni sintattiche, linguistiche, grammaticali e strutturali (che chiameremo approccio strutturale). Nessuno dei due metodi può dirsi privo di inconvenienti (Aiserman, 1969; Watanabe, 1971): le tecniche statistiche, ad esempio, non sono in grado di trattare adeguatamente le informazioni di tipo strutturale sulle relazioni che intercorrono tra gli elementi di pattern complessi; vieceversa, il principale ostacolo all'approccio strutturale è costituito dal ricorso ai modelli della teoria dei linguaggi formali, dal momento che i pattern sono entità naturali che non possono obbedire strettamente alle condizioni imposte da tale teoria. L'imposizione di regole rigide alla struttura di un pattern non è in linea di massima applicabile al riconoscimento dei caratteri, poiché le variazioni all'interno di una stessa classe di caratteri possono essere considerate virtualmente infinite.
In queste condizioni, l'unica soluzione affidabile ai problemi concreti posti dal riconoscimento di caratteri sembra essere solamente un modello ibrido (Fu, 1982; Kanal & Chandrasekaran, 1972). Significativa in proposito può essere considerata l'affermazione di Fu (1982):
[...] la dicotomia tra gli approcci strutturali e quelli basati sulla teoria della decisione sembra essere conveniente solamente sotto l'aspetto degli studi teorici. In altre parole, la separazione tra i due approcci è talvolta piuttosto vaga, particolarmente al livello delle applicazioni pratiche.1
Le tecniche utilizzate nel riconoscimento di caratteri devono essere in grado sia di discriminare un gran numero di strutture simili appartenenti alla stessa categoria, sia di generare descrizioni distinguibili di pattern appartenenti a categorie diverse. L'obiettivo finale della ricerca nel campo del riconoscimento di caratteri è naturalmente quello di sviluppare macchine in grado di leggere qualunque testo, fino al manoscritto privo di limitazioni (unconstrained handwritten) con le stesse prestazioni di un operatore umano in termini di capacità di riconoscimento, ma a velocità nettamente superiori. L'idea centrale è che, se si riesce a descrivere adeguatamente le feature che un soggetto umano usa per riconoscere i caratteri, l'algoritmo che ne consegue dovrebbe avere le stesse prestazioni del soggetto umano. Questa è la motivazione di fondo per il cosiddetto approccio descrittivo, oggi diventato molto popolare nella ricerca sul riconoscimento di caratteri, anche perché ad esso può essere fornita con relativa facilità quella flessibilità indispensabile a trasformare le infinite variazioni della forma dei caratteri in una descrizione per categorie. Una descrizione rappresenta in un certo senso un livello superiore di intelligenza, paragonabile forse alla comprensione, quando riesce ad utilizzare non solo le feature (cioè i dettagli strutturali) ma anche le regole in base alle quali esse compongono il carattere. E' chiaro che una descrizione efficiente dovrebbe poter ricorrere solo a feature mutuamente indipendenti: in altri termini, l'aggiunta o l'eliminazione di qualche feature non dovrebbe alterare le feature rimanenti; solo così diventa possibile far fronte alle limitazioni del processo usato per estrarre le feature stesse.
Sulla base della natura delle applicazioni possiamo raggruppare i lavori sul riconoscimento di caratteri in due schemi principali: il riconoscimento off-line e il riconoscimento on-line. Nei sistemi off-line, il documento viene elaborato in un momento posteriore alla sua preparazione, mentre nei sistemi on-line il riconoscimento dei caratteri viene eseguito nel momento stesso in cui essi vengono scritti a mano, in modo da utilizzarne non solo l'immagine ma anche altre informazioni (essenzialmente di temporizzazione) relative al tratto. Non ci occuperemo qui dei lavori appartenenti a quest'ultima categoria, rimandando per ogni ulteriore dettaglio alla recentissima indagine di Tappert et al. (1990).
Sulla base delle capacità e della complessità gli schemi off-line possono essere ulteriormente classificati come:
Sulla base delle feature usate, le tecniche di riconoscimento di caratteri possono essere raggruppate in due vaste categorie, come abbiamo già stabilito in precedenza:
Le tecniche di template matching sono volte al confronto diretto tra il carattere da riconoscere e un insieme standard di prototipi memorizzati: il prototipo che viene ritenuto più "simile" (in un senso opportunamente definito) al carattere incognito rappresenta la categoria a cui quest'ultimo viene assegnato. I metodi di confronto possono variare dai più semplici, quale può essere il confronto diretto tra pixel, a quelli molto complessi, come l'analisi di un albero di decisioni dove vengono confrontati soltanto pixel opportunamente selezionati. La tecnica del template matching è tuttavia piuttosto sensibile al rumore, e si adatta solo con difficoltà alle differenze che intercorrono tra i vari stili di scrittura; per di più, secondo recenti indagini (Shapiro et al., 1987) vi sono evidenze secondo cui il template matching non è il metodo usato da un soggetto umano nella lettura di un testo.
Le tecniche di analisi e matching di feature, che ormai sono le più frequentemente usate nel riconoscimento di caratteri, si basano sull'estrazione delle caratteristiche significative del pattern in ingresso e sulla descrizione delle relazioni che intercorrono tra di esse; la descrizione così ottenuta viene poi confrontata con quella dei caratteri idealizzati. L'impressione attuale (Shapiro et al., 1987) è che i meccanismi del ragionamento umano possano essere meglio descritti in termini di feature matching che non in termini di altre metodologie. Come appare chiaro dall'indagine svolta da Suen et al. (1980), dalla quale sono in gran parte tratti i dettagli che seguono, la maggior parte delle tecniche di analisi delle feature sviluppate ed applicate al riconoscimento di caratteri sono in realtà solo l'adattamento di metodi tradizionali per la classificazione di pattern al caso di domini sottoposti a particolari limitazioni.
A seconda del metodo usato per l'estrazione delle feature, le tecniche di analisi sono classificate in:
Le tecniche di trasformazione globale e di espansione in serie sono essenzialmente rivolte a ridurre la dimensionalità del vettore delle feature, e sono di solito in grado di fornire feature invarianti per alcune deformazioni di carattere globale come la traslazione e la rotazione del pattern. In questo contesto, vari ricercatori hanno usato l'espansione in serie di Fourier (Li & Cheng, 1983; Persoon & Fu, 1987; Shridhar & Badreldin, 1984, 1985), di Walsh (Huang & Lung, 1987; Sarvarayudu & Sethi, 1983), di Haar (Wendling et al., 1976a, 1976b), di Hadamard (Wendling & Stamon, 1976); l'espansione di Karhunen-Loeve (Kimpan et al., 1987); la trasformata di Hough (Kushnir et al., 1983; Kushnir & Matsumoto, 1985; Oulamara & Duvernoy, 1988), la rappresentazione in proiezioni (Li & Cheng, 1983), la rappresentazione con codici a catena (chain-code) (Cheng & Leung, 1985), la trasformazione rispetto all'asse principale (Ott, 1974). In tutti questi casi, il processo di estrazione e generazione delle feature è per molti versi relativamente semplice, ma gli algoritmi necessari possono presentare requisiti computazionali anche molto pesanti.
Come feature derivate dalla distribuzione statistica dei pixel sono state sperimentate la zonatura (Hussain et al., 1972), i momenti geometrici (Tucker & Evans, 1974; Cash & Hatamian, 1987), le n-ple (Ullmann, 1969), i luoghi caratteristici (Knoll, 1969), le intersezioni e le distanze (Chen, 1965; Fu & Cardillo, 1967; Holt, 1974; Lewis, 1962). Questi tipi di feature sono abbastanza insensibili alle distorsioni, si adattano con relativa facilità alle varianti stilistiche dei caratteri, e possono essere calcolate con algoritmi veloci e di complessità computazionale accettabile; tuttavia, volendo eliminare le feature scarsamente significative, è di norma abbastanza difficile determinarne una scala di importanza.
Il metodo più diffuso tra quelli su cui i ricercatori hanno investigato si basa sull'analisi di feature di tipo geometrico e topologico, che hanno la capacità di rappresentare proprietà sia globali che locali del carattere. Le feature più usate sono i tratti (stroke), le curvature, i punti estremali (endpoint), le intersezioni tra segmenti rettilinei, i cappi (loop); si veda, per alcuni esempi, Ali & Pavlidis (1977) e Yamamoto & Mori (1978). Queste feature sono quasi del tutto insensibili alle distorsioni e alle variazioni stilistiche, e riescono entro certi limiti a tollerare anche la traslazione e la rotazione del pattern. Sebbene il loro impiego permetta di raggiungere velocità di riconoscimento elevatissime, i processi necessari per la loro estrazione sono tuttavia in generale molto complessi.
Forse il primo lavoro veramente notevole nella ricerca sul riconoscimento di caratteri è stato quello di Grimsdale et al. (1959): il pattern del carattere in ingresso, ottenuto mediante un flying spot scanner, viene descritto sia mediante la lunghezza e la pendenza di segmenti di retta che mediante la curvatura di archi di cerchio; la descrizione così ottenuta viene confrontata con quella dei prototipi immagazzinati nel calcolatore, ricavando così la classificazione del carattere incognito.
Un altro importante lavoro è stato basato sul metodo di analisi mediante sintesi (Eden, 1961, 1968), secondo cui i caratteri latini possono essere descritti mediante 18 tipi di tratto, a loro volta generabili da un sottoinsieme di sole 4 primitive geometriche. Altri lavori hanno seguito questa stessa direzione: Blesser et al. (1973) hanno proposto un approccio teorico basato su attributi fenomenologici; Cox et al. (1974) hanno presentato due gruppi principali di regole simili a quelle grammaticali con cui affrontare la variabilità del font dei caratteri; Shillman et al. (1974) hanno suggerito tre tecniche sperimentali per studiare le ambiguità dei caratteri e per investigarne le relazioni tra attributi fisici e funzionali; Yoshida e Eden (1973) hanno proposto un sistema di riconoscimento dei caratteri cinesi che usa un processo generativo per estrarre una sequenza di tratti dal pattern di ingresso, e un dizionario di tratti per completare e raffinare il riconoscimento; le primitive del lavoro di Eden, infine, sono poi state utilizzate anche da Berthold (1982) per l'analisi del manoscritto corsivo.
Negli anni '60, Narasimhan (1964) ha suggerito uno schema di etichettatura (labeling) per la descrizione sintattica di immagini, nonché un'interpretazione delle classi di immagini diretta dalla sintassi (Narasimhan, 1966). In un altro lavoro (Narasimhan, 1969), lo stesso autore ha proposto una tecnica di riconoscimento basata sulla descrizione mediante sintesi: ricorrendo a primitive e relazioni, egli ha introdotto un linguaggio di specificazione per il riconoscimento di caratteri Fortran manoscritti. Più tardi, Narasimhan e Reddy (1971) hanno sviluppato uno schema di riconoscimento supportato dalla sintassi, incorporando nelle regole di decisione alcuni elementi di flessibilità indispensabili per ottenere prestazioni soddisfacenti da un sistema di riconoscimento; nello stesso lavoro, gli autori hanno espresso un punto di vista oggi piuttosto diffuso secondo cui le regole usate vanno raffinate, modificate ed estese in continuazione sulla base dell'esperienza e di altre conoscenze rilevanti acquisite nel corso del processo.
Alcuni autori (Pavlidis & Ali, 1975; Ali & Pavlidis, 1977) hanno affrontato il riconoscimento sintattico delle cifre decimali utilizzando l'algoritmo split-and-merge (Pavlidis & Horowitz, 1974) per approssimare il contorno dei caratteri mediante una poligonale; un ulteriore raffinamento di questa tecnica, che prevede la decomposizione del carattere in base alle concavità del pattern relativo, è stato suggerito da Feng e Pavlidis (1975).
Le maggiori attività di ricerca nel riconoscimento di caratteri sono attualmente concentrate sui caratteri cinesi manoscritti: la soluzione a questo problema, considerato fino a non molto tempo fa estremamente arduo, è senz'altro uno degli obiettivi ultimi della ricerca. Nel 1966, Casey e Nagy hanno presentato uno dei primi tentativi di riconoscimento di caratteri cinesi; poiché il numero di caratteri considerati nel lavoro è di circa 1000, essi usano un processo a due stadi, costituito da una pre-classificazione grossolana per gruppi di caratteri simili e da una post-classificazione più fine per risolvere l'identità del singolo carattere. Come appare evidente in alcuni lavori di survey (Stallings, 1976; Mori et al., 1984) la tecnica della doppia classificazione è in seguito rimasta la strategia più comune nel riconoscimento dei caratteri cinesi, poiché sembra difficile trovare alternative valide in grado di trattare ugualmente bene il vastissimo set di caratteri delle lingue ideografiche.
Alla fine degli anni '70, Agui e Nagahashi (1979) hanno suggerito un metodo per la descrizione di caratteri cinesi manoscritti, secondo il quale un carattere viene rappresentato da pattern parziali legati da tre relazioni (concatenazione, intersezione e prossimità), e la descrizione così costruita viene poi usata per la categorizzazione. La barriera psicologica costituita dalla sensazione che un riconoscitore automatico di caratteri cinesi fosse estremamente difficile da realizzare crollò poco più tardi, quando Fuji et al. (1981) dimostrarono un modello di riconoscitore di caratteri Kanji manoscritti; questo risultato produsse un enorme interesse tra i ricercatori giapponesi, e stimolò un numero notevole di tentativi di estendere l'uso pratico dei sistemi OCR al cinese. Al giorno d'oggi, la tecnica più diffusa è senza dubbio il metodo del feature matching con normalizzazione del pattern rispetto alle dimensioni e all'inclinazione (skew); un grosso punto a favore di questa tecnica, di fronte al vastissimo set di caratteri da riconoscere, è la presenza di un solo template per ciascuno della maggior parte dei caratteri.
Nel 1983, Arakawa ha suggerito un sistema per il riconoscimento on-line dei caratteri giapponesi manoscritti, dove vengono usate come feature i coefficienti di Fourier della traiettoria della punta scrivente, e la classificazione usa un metodo basato sulla regola di decisione di Bayes. Sekita et al. (1988) hanno presentato un metodo di estrazione delle feature basato sull'approssimazione dei contorni del carattere con funzioni spline e sull'impiego di tecniche di rilassamento per il confronto delle feature. I metodi di rilassamento sono stati usati anche da Xie e Suk (1988) per distinguere caratteri di forma simile all'interno di un gruppo prodotto dalla pre-classificazione, e da Leung et al. (1987), che sono riusciti a ridurre in una certa misura il carico computazionale del processo di riconoscimento utilizzando anche la conoscenza acquisita dal sistema durante l'addestramento.
I lavori sul riconoscimento dei caratteri indiani sono relativamente pochi, ma in generale abbastanza significativi, soprattutto quelli che si occupano della classificazione dei caratteri Devanagari (un set usato per la scrittura del sanscrito, dell'indù e di alcuni altri linguaggi) e dei caratteri Tamil.
Il primo tentativo di riconoscimento del Devanagari è stato descritto da Sinha e Mahabala (1979), dove viene presentata una tecnica di analisi sintattica basata su certe primitive e sulle loro relazioni; in un lavoro successivo (Sinha, 1987) una tecnica analoga viene integrata con una post-elaborazione contestuale supportata da una base di conoscenza.
Il riconoscimento dei caratteri Tamil è stato affrontato, ad esempio, da Siromoney et al. (1978) mediante un dizionario di stringhe di caratteri opportunamente codificate, e da Chinnuswamy e Khrishnamoorthy (1980), dove la composizione strutturale del carattere viene descritta mediante primitive organizzate in grafi etichettati, dei quali viene poi calcolata la correlazione con dei grafi prototipo ai fini della classificazione. Il riconoscimento dei caratteri Brahmi è stato affrontato invece da Siromoney et al. (1983) utilizzando feature estratte dalla scansione orizzontale e verticale del carattere; mentre tra le varie tecniche di riconoscimento dei caratteri indù è da citare quella di Marudarajan et al. (1978) che hanno usato logiche adattative a soglia. In un lavoro relativamente recente (Dutta, 1984), infine, sono state sfruttate le somiglianze tra i principali set di caratteri manoscritti indiani per costruire un metodo formale generalizzato, adatto sia alla generazione che all'analisi di tutti i caratteri bengalesi e indù.
All'inizio del decennio scorso, la ricerca sul riconoscimento di caratteri comincia ad assumere dimensioni via via maggiori, e comincia a diventare sempre più difficile isolare i lavori veramente significativi.
Tanaka et al. (1982) hanno presentato un nuovo metodo per il riconoscimento di caratteri inglesi e giapponesi (Katakana) manoscritti, in cui la classificazione dei pattern distorti fa uso dell'algoritmo di Viterbi e di tecniche di attraversamento di grafi (trellis) con cui vengono eliminate tutte le categorie irrilevanti e lasciata solo la più probabile per la decisione finale. Il riconoscimento dei caratteri numerici è stato affrontato invece da Sarvarayudu e Sethi (1983), che hanno usato come feature i descrittori di Walsh calcolati sul contorno del pattern; da Shridhar e Badreldin (1984), che hanno ottenuto una buona accuratezza di riconoscimento usando i descrittori di Fourier e certe caratteristiche topologiche del pattern; e da Shridhar e Badreldin (1985), che hanno usato soltanto delle feature legate alla topologia del pattern, evitando così il ricorso ai descrittori di Fourier che richiedono grosse risorse computazionali.
Un sistema OCR di tipo economico, da usare come dispositivo di data entry per sistemi distribuiti di elaborazione dati, è stato proposto da Sato et al. (1983): l'acquisizione del testo avviene mediante uno scanner manuale, e possono essere letti caratteri sia stampati che dattiloscritti.
E' infine da citare un metodo (Evangelisti, 1983) per la valutazione degli scanner da usare in sistemi OCR prima del progetto della logica di riconoscimento, dove il pattern prodotto dallo scanner viene confrontato con dei pattern standard selezionati da un calcolatore.
Dalla metà degli anni '80 in poi, è stata condotta una notevolissima quantità di ricerca, della quale soltanto una piccola parte può essere qui passata in rassegna.
Nagy et al. (1987) hanno dimostrato un algoritmo euristico per la classificazione dei caratteri aiutata dal contesto, usando un piccolo vocabolario delle parole inglesi più frequenti, che ha requisiti piuttosto modesti sia di memoria che di calcolo. Un metodo analogo è stato proposto da Sinha (1987), dove la post-elaborazione consiste in una verifica sintattica basata su un automa a stati finiti, e le regole di sostituzione, che hanno la forma condizione-azione, sono associate ad una penalità il cui valore totale per una parola ne determina il grado di affidabilità.
Nel sistema per il riconoscimento di parole arabe corsive proposto da Almuallim e Yamaguchi (1987), le parole vengono segmentate in tratti che vengono classificati in base alle loro proprietà geometriche e topologiche; questi tratti vengono poi esaminati e combinati in una stringa di caratteri che rappresenta la parola riconosciuta. Ancora al riconoscimento dell'arabo manoscritto è rivolto il lavoro di El-Sheikh e Guindi (1988), dove la parola viene segmentata in caratteri che vengono poi riconosciuti ricorrendo anche all'analisi del contesto. Il lavoro di Hull (1985) descrive invece una specie di sistema esperto basato sull'elaborazione di conoscenza, capace di leggere testo sia stampato in una grande varietà di font sia scritto a mano; la singola parola viene caratterizzata da una sequenza di feature, e la descrizione che ne deriva viene classificata facendo ricorso a un dizionario. Aoki e Yamaha (1986) hanno presentato un riconoscitore sintattico per parole scritte a mano che fa uso di una procedura di apprendimento, mentre Wong e Fallside (1985) hanno suggerito un nuovo metodo di programmazione dinamica basato su tecniche solitamente usate nel riconoscimento del parlato continuo; infine, Srihari (1987) ha descritto un metodo che presenta molte affinità con le teorie della percezione multilivello.
La segmentazione delle parole manoscritte in caratteri è stata affrontata da Tampi e Chetlur (1986) con l'uso di un vocabolario dove a ciascuna parola vengono associate le feature essenziali per la segmentazione; una soluzione per lo stesso problema è stata anche suggerita da Ting e Ward (1987).
Lam e Suen (1988) hanno descritto un sistema per la classificazione di codici postali scritti a mano libera, che comprende un estrattore di feature per la decomposizione del carattere in primitive geometriche, e due algoritmi di classificazione: un classificatore strutturale veloce in grado di identificare la maggioranza dei pattern, e un algoritmo a rilassamento che classifica il resto dei dati. Le tecniche multilivello che si ritiene stiano alla base dell'elaborazione visiva da parte del cervello umano sono poi state utilizzate da Baptista e Kulkarni (1988) per ottenere un riconoscitore di caratteri manoscritti di notevole accuratezza.
Il riconoscimento multifont è stato affrontato con tecniche di apprendimento simbolico (Cannat & Kodratoff, 1986; Cannat et al., 1986), in base alle quali la conoscenza necessaria viene via via "scoperta" dal sistema in fase di esercizio, anziché essere fornita ad esso in fase di progetto, rendendo così possibile la costruzione autonoma di generalizzazioni valide anche per la discriminazione dei caratteri. All'apprendimento per esperienza hanno anche fatto ricorso Malyan e Sunthankar (1986), che hanno presentato alcuni risultati preliminari sullo sviluppo di un sistema a basso costo, da utilizzare come ausilio per i ciechi nella lettura di testi manoscritti.
Il riconoscimento di testi stenografati secondo il metodo di Pitman è invece stato affrontato da Leedham e Downton (1986), che hanno descritto diversi esperimenti preliminari e hanno in seguito suggerito (Leedham & Downton, 1987) una strategia di riconoscimento dove il testo viene segmentato in due classi di caratteri, dette rispettivamente shortform e vocalized outline; i caratteri della prima classe, a cui appartiene fino al 50% di un testo stenografico tipico, vengono classificati mediante una tecnica di template matching con programmazione dinamica, mentre quelli della seconda categoria vengono riconosciuti con un metodo sintattico supportato da una base di conoscenza costruita mediante l'analisi preliminare di un gran numero di testi stenografici.
Nagahashi e Nakatsuyama (1986) hanno riportato un metodo strutturale per la descrizione e la generazione di pattern per caratteri, suggerendo di considerare un carattere come un pattern composito costituito da diversi sub-pattern più semplici, legati tra loro mediante tre tipi di relazioni posizionali.
Un lavoro abbastanza importante della metà degli anni '80 è stato quello di Harjinder (1985), che comprende anche un survey delle metodologie usate nel riconoscimento di caratteri; l'approccio scelto per la classificazione dei caratteri latini manoscritti risulta estremamente flessibile, poiché dà luogo a schemi di descrizione dei caratteri praticamente illimitati. La tecnica usata si basa sull'analisi e la descrizione di curve su un reticolo a struttura esagonale, mentre i caratteri vengono descritti mediante le regole di una grammatica formale, e sia l'estrazione delle feature che il riconoscimento fanno ricorso ad alberi di decisione.
Un nuovo metodo, chiamato trasformazione in chain-code, adatto al riconoscimento di pattern contenenti segmenti rettilinei, è stato suggerito da Cheng e Leung (1985), in cui i tratti di un carattere vengono rappresentati in uno spazio parametrico bidimensionale simile a quello usato nella trasformata di Hough; nel lavoro viene altresì descritto un esperimento preliminare di classificazione di caratteri cinesi che sembra aver conseguito eccellenti tassi di riconoscimento.
Mediante opportuna codifica di determinate zone del pattern, i caratteri cinesi più comuni sono stati pre-classificati da Huang e Lung (1987) in circa 4096 classi, contenenti per lo più da 1 a 6 caratteri ciascuna; la classificazione finale viene poi ottenuta utilizzando la trasformata di Walsh.
Tra gli altri lavori importanti che meritano una citazione, possiamo annoverare un sistema omnifont sintattico (Wolberg, 1986) in grado di riconoscere una vasta gamma di font, compresi i caratteri manoscritti; una procedura di test delle prestazioni dei riconoscitori di caratteri a font misti e dimensioni variabili (Lam & Baird, 1987); un estrattore di feature per lettori di documenti (Pavlidis, 1986); e infine un insieme di direttive per la scelta dei vettori di feature da usare nel riconoscimento di vasti set di caratteri, discusse da Hagita e Masuda (1987).
Sebbene la progettazione automatica di classificatori per set di caratteri strutturalmente differenti possa costituire un interessantissimo tema di ricerca, non ci è noto alcun lavoro che affronti in maniera compiuta e sistematica il problema. Riteniamo tuttavia degni di menzione alcuni tentativi circoscritti e dagli obiettivi abbastanza ben delimitati.
Naylor (1971) ha descritto un sistema interattivo per la costruzione di un classificatore di caratteri latini dattiloscritti, dove l'operatore utilizza un terminale grafico per selezionare i pattern delle varie classi, e il sistema costruisce automaticamente l'albero decisionale utilizzato poi per la classificazione; le feature, del tipo "angolo retto" oppure "estremità di segmento rettilineo orizzontale", vengono estratte dal pattern considerandone il baricentro e 12 suoi punti estremali determinati mediante massimizzazione di certe funzioni quadratiche.
Il progetto e la generazione automatica di dizionari per il riconoscimento di caratteri numerici sono poi l'oggetto di due interessanti lavori. Nel primo (Ishii et al., 1978) la topologia del carattere viene rappresentata mediante feature binarie, selezionate sulla base della loro utilità nella discriminazione delle classi e della loro capacità di minimizzare l'ambiguità presente nella descrizione di certe classi. Nel secondo lavoro (Kami, 1984), il carattere viene invece descritto in termini di feature selezionate da un set ottimale mediante una procedura sequenziale e combinate in maniera da ottimizzare la distanza inter-classe.
La limitazione inerente a tutti questi tentativi, in realtà, è essenzialmente dovuta al fatto che le feature usate sono relativamente semplici, e non possono quindi rappresentare in modo compiuto e preciso i dettagli strutturali dei vari caratteri, dei vari font o dei vari set alfabetici. Solo recentemente è stato suggerito (Govindan, 1988) un approccio automatizzato al progetto di classificatori per set di caratteri strutturalmente differenti, che tuttavia per molti versi ricalca ancora quello proposto da Kami (1984).
Un ultimo lavoro che ci sembra particolarmente significativo, se non altro per le sue possibili implicazioni, è quello di Stentiford (1985), in cui il problema della determinazione delle feature da estrarre dal pattern del carattere viene affrontato mediante una ricerca casuale di tipo evolutivo. Le feature generate sono estremamente semplici, anche se nella gran parte dei casi non sembrano suscettibili di interpretazione intuitiva, e conducono a tassi di errore attorno all'1% su una base di dati relativi a caratteri dattiloscritti, suggerendo la possibilità di implementare sistemi di lettura estremamente veloci, economici ed affidabili.
Il vastissimo interesse che negli ultimi anni le architetture neurali hanno prodotto nel campo della classificazione di pattern si è in parte riflesso anche nella ricerca di nuove tecniche per il riconoscimento di caratteri. L'argomento delle reti neurali verrà ripreso più avanti, ma vogliamo qui anticipare, per completezza, qualche cenno su alcuni lavori significativi in quest'area.
Burr (1986) ha riportato alcuni risultati incoraggianti nel riconoscimento di testi manoscritti mediante l'uso di reti neurali addestrate mediante back-propagation (Sez. 8); la medesima tecnica è stata succesivamente raffinata e accoppiata a un dizionario (Burr, 1987). Le reti neurali con back-propagation sono ancora state utilizzate (Gullichsen & Chang, 1987) per il riconoscimento dei simboli usati in cartografia, processo per molti versi analogo a quello del riconoscimento di caratteri. Un metodo per il riconoscimento rapido dei caratteri cinesi manoscritti mediante reti neurali è stato poi riportato da Yong (1988).
Va infine citata una interessante discussione sulle possibilità applicative delle reti neurali nei sistemi OCR, presentata da Mehr e Richfield (1987), che si conclude con la convinzione che un lettore dotato di due tipi di reti neurali, l'una per il normale riconoscimento di caratteri, l'altra per l'immagazzinamento dell'esperienza acquisita attraverso gli errori della prima, dovrebbe essere in grado di superare in prestazioni qualunque sistema basato esclusivamente sulle tecnologie correnti.
(1) "[...] the dichotomy of syntactic and decision-theoretic approaches appears to be convenient only from the viewpoint of theoretical study. In other words, the division of the two approaches is sometimes not clear-cut particularly in terms of practical applications".
|
|||||||
© 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:29