On AIR s.r.l.
Tecniche di riconoscimento statistico
Teoria e applicazioni industriali
Parte 5 – Tecniche OCR
Ennio Ottaviani - 2019
Ennio OttavianiOn AIR srl
[email protected]://www.onairweb.com/corsoPR
A.A. 2018-2019
Introduzione
• L’obiettivo delle tecniche OCR è classificare dei pattern 2D (espressi come immagini digitali) in simboli alfanumerici, ottenendo una versione digitale (ASCII) di una immagine contenente testo
• Le tecniche utilizzate combinano aspetti di tipo statistico con aspetti di elaborazione delle immagini
Ennio Ottaviani - 2019
di elaborazione delle immagini
• Applicazioni tipiche:– Data entry di archivi cartacei– Smistamento della corrispondenza– Lettura di moduli– Riconoscimento targhe e testi strutturati– Estrazione testi generici in scene complesse
Il processo OCR
• Un qualsiasi processo OCR viene di norma suddiviso logicamente in 4 passi base che si ritrovano in tutte le applicazioni– Localizzazione del testo– Segmentazione dei caratteri– Classificazione dei caratteri– Analisi contestuale
Ennio Ottaviani - 2019
– Analisi contestuale
• I primi due sono strettamente connessi alla problematica applicativa e coinvolgono metodi di elaborazione delle immagini
• La classificazione dei caratteri è un problema classico di PR
• L’analisi contestuale impiega metodi di ragionamento simbolico
Segmentazione caratteri
• Il processo di segmentazione è responsabile della estrazione dei singoli caratteri dall’immagine
• Vengono estratti di norma anche oggetti 2D che non sono caratteri, che il classificatore dovrà scartare
Ennio Ottaviani - 2019
• Per le immagini binarie, la segmentazione deve semplicemente analizzare la connessione tra pixel adiacenti
• Spesso è utile la morfologia matematica per regolarizzare le forme e correggere difetti (es. caratteri fusi o frammentati)
• La tendenza moderna è superare la segmentazione esplicita ed univoca, utilizzando ipotesi multiple o sliding windows
Esempio
• Anche su immagini di buona qualità, gli errori sono inevitabili
Ennio Ottaviani - 2019
• Un buon segmentatore deve usare strategie correttive, legate alla conoscenza della struttura del testo da leggere
Features per OCR
• Dal punto di vista del PR, le applicazioni OCR richiedono innanzitutto una definizione delle features da utilizzare
• Le features ideali devono rispondere a diversi requisiti:– Computabilità– Discriminatività
Ennio Ottaviani - 2019
– Discriminatività– Invarianza
• Il concetto di invarianza assume particolare importanza nelle applicazioni OCR dove il testo da leggere può essere deformato:– geometricamente (ruotato, scalato, distorto prospetticamente)– pittoricamente (chiaro, scuro, rumoroso, corrotto)
Zonatura
• Il metodo della zonatura prevede che l’immagine 2D a livelli di grigio del carattere da riconoscere venga tassellata in MxN regioni disgiunte rettangolari, e di ciascuna venga misurato il grigio medio
Ennio Ottaviani - 2019
• Il metodo è adatto per immagini binarie, mentre nel caso generico occorre una normalizzazione dei livelli di grigio prima della zonatura
• La scelta di M,N è critica– valori piccoli → poco discriminanti– valori grandi → computazione onerosa
Momenti
• Uno schema per generare feature invarianti per trasformazioni assegnate di una immagine f(x,y) si basa sui momenti
Ennio Ottaviani - 2019
• L’immagine viene interpretata come una distribuzione di probabilità
• Se le coordinate (x,y) sono riferite al baricentro (m10/m00, m10/m00), si parla di momenti centrali μpq (invarianti per traslazione)
• I momenti centrali del secondo ordine misurano le varianze di x,y. I momenti di ordine superiore (normalizzati), sono utili per la classificazione
Momenti invarianti
• Descrittori di forma
• Invarianti di scala
Ennio Ottaviani - 2019
• Invarianti per rotazione (Hu)
…….
Altri insiemi di feature per OCR
• Non esiste un insieme di features che sia il migliore in qualunque applicazione, e la scelta è spesso frutto di tentativi
• Schemi di feature extraction molto diffusi sono:– coefficienti di Fourier 2D– codifiche del contorno
Ennio Ottaviani - 2019
– codifiche del contorno– mappe di punti salienti
• La prassi suggerisce di calcolare molte più features di quanto realmente necessario, e di selezionare in seguito le migliori– feature selection (selezione di sottoinsiemi)– feature generation (combinazioni lineari ottimali)
Istogramma dei gradienti orientati
• Utilizza come features di base le componenti dell’istogramma delle direzioni del gradiente dell’immagine segmentata (HOG)
Ennio Ottaviani - 2019
Classificazione caratteri
• In un sistema OCR, se la segmentazione ha operato correttamente, la classificazione di solito non presenta problemi, almeno per applicazioni con testi basati su simbologie standardizzate
• Anche poche features riescono già a ottenere discriminazioni
Ennio Ottaviani - 2019
• La classificazione è difficile quando la distribuzione delle classi contiene anche una variabilità indotta dagli stadi precedenti, che complica la definizione delle superfici di separazione
• A volte il training iniziale non è sufficiente per rappresentare tutte le possibili variabilità. E’ importanza quindi la capacità di generalizzare
Esempio
• Esempio di OCR a font fisso usando solo due features (orientazione e skewness)
Ennio Ottaviani - 2019
Font per OCR
• I font tipicamente utilizzati nei sistemi OCR a larga diffusione sono solo una piccola parte di quelli possibili (es. in un editor per PC)
• Sono stati studiati apposta per facilitare il riconoscimento con elevate prestazioni
Ennio Ottaviani - 2019
OCR Postale
• Lo smistamento della corrispondenza usa da anni sistemi OCR per leggere indirizzi
• Le lettura del dattiloscritto o del manoscritto stampatello sono oggi considerate quasi “banali”
Ennio Ottaviani - 2019
• Ancora non disponibili invece OCR efficaci per il corsivo
• La localizzazione dell’indirizzo (Address Block Location, ABL) è il vero problema delle applicazioni postali, a causa di:– ambiguità (indirizzi multipli) – complessità dei pezzi postali (es. riviste)– diverse tipologie di scrittura dell’indirizzo
Form processing
• Indica la capacità di estrarre dati alfanumerici da moduli compilati a mano e quindi scannerizzati
• Richiede la definizione del layout del modulo, della tipologia e della posizione dei singoli campi
Ennio Ottaviani - 2019
Evoluzione OCR
Ennio Ottaviani - 2019
Evoluzione OCR
• L’amministrazione postale USA pubblica un database di caratteri manoscritti reali (MNIST) su cui i fornitori devono competere
Ennio Ottaviani - 2019
Evoluzione OCR
• Su questo dataset molto complesso (e su altri a contenuto molto eterogeneo) i risultati migliori sono stati ottenute mediante una rete neurale convolutiva (CNN)
Ennio Ottaviani - 2019
Sistemi ICR-IWR
• I normali sistemi OCR vanno del tutto ripensati quando si opera con testo manoscritto
• Si definiscono sistemi ICR quelli che, di solito grazie alla presenza di caselle, mantengono una segmentazione esplicita del testo in caratteri
Ennio Ottaviani - 2019
caratteri
• I sistemi IWR (Intelligent Word Recognition) analizzano invece la singola parola come un oggetto unico (approccio olistico)
• In questi sistemi è fondamentale la modellazione del linguaggio, per sfruttare al meglio l’informazione contestuale
Sistemi ICR-IWR
• Il modello sintattico del linguaggio consente di correggere errori
• Il modello semantico consente di creare frasi di senso compiuto
Ennio Ottaviani - 2019
Sistemi OCV/OMR
• Nella produzione di oggetti, occorre verificare che le informazioni testuali (codici) siano stampati correttamente
• In questi casi non interessa leggere ma verificare la leggibilità. E’ un tipico problema binario: codice ok o nok
Ennio Ottaviani - 2019
• Talvolta codici opportuni (marker) sono usati come riferimento per individuare e posizionare correttamente i documenti
Lettura targhe
• La lettura delle targhe (License Plate Recognition, LPR) è oggi un componente fondamentale per diverse applicazioni– Controllo di accessi (parcheggi, ZTL, … )– Rilevamento di violazioni (passaggio col rosso, eccesso di velocità,…)– Recupero dei veicoli rubati– Analisi dei tempi di percorrenza
Ennio Ottaviani - 2019
– Analisi dei tempi di percorrenza– Esazione del pedaggio– Controlli di frontiera– …..
• Le targhe rappresentano un caso classico di OCR in partenza semplice (mono-font) ma reso complesso dalla variabilità indotta dall’ambiente
Algoritmo base LPR
• Un algoritmo LPR non differisce da una normale OCR se non per gli aspetti legati alle immagini ed al tipo di testo da leggere
Ennio Ottaviani - 2019
Localizzazione della targa
• La presenza di un targa viene identificata utilizzando appositi filtri che identificano la presenza di transizioni di grigio (gradienti)
• Di norma queste analisi vengono condotte lungo le righe dell’immagine, e confermate su righe adiacenti
Ennio Ottaviani - 2019
Localizzazione della targa
• Un approccio più moderno utilizza uno schema basato su una rappresentazione della targa mediante semplici features (Haar).
• Con queste si cerca di apprendere una regola generale (complessa) per classificare regioni in targa/non targa
Ennio Ottaviani - 2019
Localizzazione della targa
• Approcci successivi usano un feature set predefinito (HOG) ed apprendono un modello mediante osservazione di casi positivi e negativi
Ennio Ottaviani - 2019
Localizzazione della targa
• I risultati sono buoni, ma dipendono molto dal training set utilizzato
Ennio Ottaviani - 2019
• La variabilità dei casi possibili è enorme, e quindi è difficile garantire a priori un livello minimo di prestazioni
• Un tuning locale spesso risolve i casi più difficili
Segmentazione della targa
• L’obiettivo della segmentazione è estrarre tutti i caratteri appartenenti alla targa. Sono di norma tollerati dei caratteri extra (spuri), ma è più complesso recuperare caratteri persi
• La segmentazione deve compensare le inevitabili variazioni pittoriche e geometriche dovute alle condizioni di ripresa
Ennio Ottaviani - 2019
• Ci si riconduce quasi sempre ad una immagine binaria facile da trattare con tecniche classiche di elaborazione delle immagini (analisi delle componenti connesse)
Segmentazione della targa
• L’analisi in componenti connesse prevede un passo critico di binarizzazione basato su una soglia.
• Questo fatto può essere corretto combinando l’approccio MSER (Maximally Stable Extremal Regions), che analizza le componenti al variare della soglia, con un classificatore
Ennio Ottaviani - 2019
Segmentazione della targa
• La segmentazione deve gestire la variabilità prospettica (skew e slant) fino ad angoli anche elevati
• I singoli caratteri devono essere tutti isolati prima di passare a OCR
Ennio Ottaviani - 2019
Analisi contestuale
• L’analisi contestuale comprende un insieme di metodologie per il trattamento di dati simbolici, finalizzato alla identificazione di termini appartenenti ad un lessico o comunque regolati da una grammatica
• Dati di ingresso– Lista di simboli candidati (caratteri veri e falsi) con significato univoco
Ennio Ottaviani - 2019
– Lista di simboli candidati (caratteri veri e falsi) con significato univoco oppure multiplo (con costi relativi)
– Grammatica espressa come insieme di regole che definiscono le concatenazioni di simboli ammissibili (sintassi)
– Eventuali criteri geometrici aggiuntivi (posizioni)
• L’obiettivo finale è produrre una stringa di testo valida
Analisi contestuale per le targhe
• Trattando testi di lunghezza limitata (e spesso nota a priori), si opera spesso per enumerazione diretta delle possibili concatenazioni di caratteri e successiva valutazione dell’ipotesi migliore
• Nei casi più complessi si usa un approccio markoviano (ogni simbolo viene scelto sulla base del precedente, cercando la
Ennio Ottaviani - 2019
simbolo viene scelto sulla base del precedente, cercando la sequenza ottimale). I sistemi di questo tipo sono detti parsers
• Attenzione: l’analisi contestuale permette di correggere errori di lettura e di saltare caratteri falsi ma non di recuperare caratteri persi!
• In questi casi sono utili strategie iterative in cui si opera una nuova segmentazione vicino a dove si è avuta una lettura valida
Esempio
• Si ricerca l’allineamento ottimo di una sequenza di 8 simboli compatibile con la grammatica delle targhe italiane (pre 1994)
• La funzione di costo cumula una quantità positiva legata alla distanza di Mahalanobis
Ennio Ottaviani - 2019
• Senza analisi contestuale la lettura a costo minimo sarebbe 6EB56B79 (costo 227). Con le regole della grammatica si ha invece GEB56879 (costo 247)
6 42G 60
E 35 B 338 41
5 21S 66
6 35 B 238 25
7 15Z 33
9 238 38
Evoluzione LPR
• Il traffico odierno ha una densità ed una distribuzione molto diversa rispetto agli anni ‘90, quando la tecnologia OCR in esterni è stata sviluppata
• Un sistema LPR oggi deve essere necessariamente– multi nazione
Ennio Ottaviani - 2019
– multi nazione– multi font– multi veicolo
• Questo pone problemi a livello di ripresa (risoluzione immagini), di OCR (addestramento) e di analisi contestuale (ambiguità)
Il controllo del traffico oggi
Ennio Ottaviani - 2019
Lettura testi generici
• Oggi molte applicazioni richiedono la capacità di estrarre e leggere testi in scene complesse e non strutturate
• Occorrono metodi più robusti e flessibili del semplice LPR
Ennio Ottaviani - 2019
Riconoscimento segnaletica
• Si tratta di un OCR molto particolare, che integra il riconoscimento di primitive geometriche semplici (es. triangoli, quadrati) anche se prospetticamente deformati
Ennio Ottaviani - 2019
Maker & model recognition (MMR)
• E’ una applicazione moderna delle tecniche di PR in esterni, che utilizza la lettura per definire una regione di interesse dove analizzare la struttura dell’immagine al fine di identificare costruttore e modello
• Un approccio semplice si basa sul riconoscimento di marchi (logo)
Ennio Ottaviani - 2019