Il corso di

Visione Artificiale e Riconoscimento

Annalisa Franco

annalisa.franco@unibo.it

http://bias.csr.unibo.it/VR/

2

Definizioni

Visione Artificiale (VA) è una disciplina molto ampia che studia

gli aspetti connessi allo studio e alla progettazione di sistemi

artificiali in grado di eseguire compiti visivi e percettivi (tipici

dell’uomo e di alcune specie animali):

Acquisizione di immagini

Elaborazione di immagini

Ricostruzione 3D delle forme (shape from X)

Comprensione della scena (scene understanding)

Riconoscimento di forme (pattern recognition)

Localizzazione di oggetti

Detection del movimento e tracking di oggetti

▫ In grassetto le tematiche oggetto di questo corso …

3

Definizioni

Pattern recognition (PR) è una delle più importanti “sotto-

discipline” della VA; PR viene solitamente tradotto in italiano come

“Riconoscimento di Forme” ma è forse meglio non tentare di

tradurre con Forme il termine Pattern.

Cos’è allora un pattern ?

Watanabe [Wata85] definisce un pattern come l’opposto del

caos e come un entità vagamente definita cui può essere

dato un nome.

Ad esempio un pattern può essere un volto, un carattere

scritto a mano, un’impronta digitale, un segnale sonoro,

l’andamento di un titolo di borsa, ...

4

Definizioni

Riconoscimento e Classificazione

Nel contesto del pattern recognition il riconoscimento è inteso come

classificazione o categorizzazione ovvero l’assegnamento del

pattern a una classe.

Per classe intendiamo un insieme di entità aventi proprietà comuni

(ad. esempio i diversi modi in cui le persone scrivono il carattere

“A”). Il concetto di classe è semantico e dipende strettamente

dall’applicazione:

21 classi per il riconoscimento di lettere dell’alfabeto

2 classi per distinguere le lettere dell’alfabeto italiano da quello

cirillico

Le classi possono essere definite dal progettista (classificazione

supervisionata) o “imparate” autonomamente dal sistema

(classificazione non supervisionata).

5

Perché è importante il PR ?

Gran parte dei fenomeni dell’esistenza umana si manifestano sotto

forma di pattern: i simboli della scrittura, gli elementi costitutivi del

parlato, disegni e immagini, il volto di persone care, ...

L’importanza del PR è legata non solo alla percezione, ma anche alla

conoscenza: gli esseri umani valutano le situazioni in termini di pattern

e agiscono in base alla loro valutazione di tali pattern.

Il PR è una componente intrinseca del comportamento umano.

L’estensione al computer di capacità di riconoscimento di pattern può

renderlo in grado di svolgere compiti percettivi e cognitivi. Obiettivo

ultimo del PR: costruire macchine che possiedano le nostre stesse

capacità di riconoscimento di pattern.

6

Perché è così difficile?

http://www1.idc.ac.il/toky/ImageProc-10/

Perché è così difficile?

8

Human and Mechanical PR

L’uomo esegue il riconoscimento mediante una

classificazione del pattern. Il mapping è opaco, i

dettagli del processo sono inaccessibili agli

osservatori e quasi sempre anche al riconoscitore

stesso.

L’implementazione su computer di un metodo di PR

richiede che il mapping opaco sia sostituito da uno

trasparente, di cui sia possibile dare una descrizione

precisa (algoritmo).

9

Progetto di applicazioni di VA

In TEORIA

Dare una descrizione appropriata degli oggetti, fisici o

concettuali, in termini di caratteristiche (features),

appartenenti a uno spazio di rappresentazione.

Specificare uno spazio di interpretazione (lo spazio

delle classi)

Fornire un mapping fra lo spazio di rappresentazione e

quello di interpretazione (Simon 74).

Determinare un operatore (algoritmo) che esegua

questo mapping, ovvero che esegua la classificazione.

10

Progetto di applicazioni di VA

In PRATICA

Perdere giorni nel tentativo di far funzionaretelecamere, frame grabber e altri sensori con la nostraversione di Sistema Operativo setacciando il web allacaccia dei driver necessari.

Cercare in letteratura quali approcci sono statiutilizzati con successo per la soluzione dello stessoproblema (o di un problema analogo).

Scaricare da Internet codice sviluppato da altri,adattandolo se possibile alle nostre esigenze.

Anche un tale approccio PRATICO richiedeesperienza: nella VA e nel PR per risolvere in modoottimale ogni problema specifico è necessario unmetodo ad-hoc !!!

11

Stato dell’arte: alcuni esempi

OCR

12

OCR Face detection Face recognitionRealtà

aumentata

3D modelingVideo-basedinteraction

AutomotiveRiconoscimento

oggetti

OCR

13

Face detection

14

Face recognition

15

Realtà aumentata

16

3D modeling

17

Video-based interaction / gaming

18

Automotive

19

Supermercati/acquisti

20

https://www.amazon.com/b?ie=UTF8&no

de=16008589011

Applicazioni di VA

21

Dominio Applicazione Input: Pattern Output: Classe

Analisi di documentiOCR: conversione di

immagini in testoImmagini di documenti

Caratteri alfanumerici, parole

Automazione industrialeIspezione di circuiti

stampatiImmagine del circuito Difettoso / Non difettoso

Bioinformatica Analisi delle sequenze Sequenza DNA/Proteine Tipo conosciuto di gene

Classificazione documenti

Ricerca su Internet Documento di testo Categoria semantica

Data miningRicerca di pattern

“significativi”Punti multi-dimensionali

Cluster compatti e ben separati

Database ImmaginiRicerca su database

immaginiCollezioni di immagini Specifici soggetti o temi

EconomiaPredizione mercato

azionarioSequenze storiche Acquista / Vendi

Applicazioni di VA

22

Dominio Applicazione Input: Pattern Output: Classe

MedicinaAnalisi immagini

radiograficheImmagine alta

risoluzioneSano / Malato

MilitareAbbattimento automatico

missiliImmagini “live” Direzione di calibrazione

Riconoscimento del parlato

Risponditori telefonici autom.

Segnale audio del parlato Parole dette

Sistemi BiometriciRiconoscimento di

personeVolto, Iride, Impronta

digitaleUtente autorizzato

Sorveglianza Sistema anti-intrusioneImmagine “live” del

localeNormale / Allarme

Telerilevamento Stimare densità di colture Immagini multispettrali Tipi di coltivazioni

Visione roboticaGuida automatica di un

veicoloImmagini “live” Direzione sterzo

PR e discipline affini

Intelligenza artificiale (AI) è una disciplina molto vasta che

comprende diversi settori disciplinari tra cui:

Metodi di rappresentazione della conoscenza e

ragionamento

Pianificazione, coordinamento e manipolazione.

Sistemi esperti e sistemi tutoriali intelligenti

Dimostrazione automatica di teoremi

Programmazione automatica

Agenti autonomi

Elaborazione del linguaggio naturale

VISIONE

APPRENDIMENTO

23

PR e discipline affini

Machine learning (ML)

Un sistema di learning (o apprendimento automatico) “impara

dagli esempi a migliorare le proprie prestazioni per la gestione

di nuovi dati provenienti dalla stessa sorgente” (Mickey 91).

Diversi sono i punti in comune con PR; ma in PR i sistemi che

imparano dagli esempi sono solo una parte: possiamo

affermare pertanto che PR ML ?

“Learning from Data” è il titolo di un libro [Cher98] che mette

in luce come gli stessi concetti nell’ambito di discipline diverse

vengano ogni volta reinventati. La disciplina madre comune

alla maggior parte dei sistemi di apprendimento da esempi è la

statistica, e gli autori incolpano gli statistici di non essere stati

in grado di esportare la loro conoscenza alle altre discipline.

24

PR e discipline affini

25

Reti Neurali (NN)

Elaborazione delle

Immagini (IP)

Pattern Recognition

Fuzzy Systems (FS)

Computer Grafica (CP)

Si tratta di risolvere il problema inverso! infatti nel PR data un’immagine l’obiettivo è

estrarre e classificare gli oggetti presenti mentre in CP dato un oggetto (costituito da una serie

di primitive) si vuole generare una rappresentazione (immagine) realistica di tale oggetto.

Confronto diretto di immagini:

distanza nello spazio multidimensionale |I1 – I2|: perché non funziona ?

Traslazione, rotazione, scala e prospettiva.

Deformazione e variabilità dei pattern.

Cambiamenti di illuminazione.

Rumore e diverse tecniche di acquisizione.

Un esempio

26

4524.84

3990.34

I 4 principali approcci del PR (1)

Template matching

La distanza diretta tra immagini non fornisce

buoni risultati spesso a causa di traslazioni,

rotazioni, variabilità dei pattern.

Idea: costruire uno o più pattern modello

(template) e “cercarlo/i” all’interno

dell’immagine misurando il grado di

“matching” nelle diverse possibili posizioni.

27

[Jain00] [Duda00]

Template matching

28

immagine di riferimento

2 template

Posizione di

max. matching

di ciascuno dei

due template

all’interno

dell’immagine

I 4 principali approcci del PR (2)

Approccio Statistico

Ogni pattern è rappresentato da un punto

nello spazio multidimensionale.

Prevede una fase di estrazione delle

caratteristiche che mappa il pattern nel punto

e una fase di classificazione che associa il

punto a una classe.

I classificatori utilizzati sono fondati su solide

basi statistiche.

29

[Jain00] [Duda00]

Approccio statistico

Estrazione delle caratteristiche

30

Di ogni oggetto viene

misurata l’estensione dei

pixel rispetto al baricentro

(primo momento

invariante).

Classificazione

Se E è l’estensione dell’oggetto da classificare in una delle 2 classi T

(oggetti allungati a forma di T) e C (oggetti più circolari):

dove AvgT ed AvgC sono le estensioni medie degli oggetti delle 2 classi

T e C misurate su di un set di addestramento.

classe di è oggettol'

22

altrimentiC

AvgCEAvgTEseT classificatore di

minima distanza

euclidea

I 4 principali approcci del PR (3)

Approccio Strutturale (sintattico)

I pattern sono codificati in termini di componenti

primitive e di relazioni che intercorrono tra esse.

Il confronto avviene confrontando primitive e relazioni.

31

Approccio strutturaleEs. classificazione di impronte digitali

32

Calcolo Immagine

Direzionale

Costruzione grafo

Relazionale

Inextact Graph

Matching

Segmentazione

Immagine

Direzionale

I 4 principali approcci del PR (4)

Reti Neurali

Sono costituite da grafi orientati i cui nodi (neuroni)

processano le informazioni trasmesse da altri neuroni

ad essi collegati.

Consentono di “codificare” complessi mapping non-

lineari, che vengono solitamente “appresi” da esempi.

33

Reti Neurali

Cervello vs Computer

Neuroni e reti nel cervello

I neuroni ricevono input chimici attraverso le connessioni sinaptiche dei dendriti.

Tali input sono convertiti in segnali elettrici; se il livello di “eccitazione” eccede una certaquantità sparano un impulso che provoca il rilascio di sostanze chimiche alle terminazioniassoniche.

Altri neuroni nella rete vengono eccitati dagli elementi chimici rilasciati.

L’efficacia delle sinapsi si modifica con l’esperienza (learning).

34

Programma del corso• Introduzione

• Richiami di elaborazione di immagini digitali, filtraggio

• Feature di colore:

▫ color histograms e metriche di similarità/distanza;

▫ color moments;

▫ segmentazione di oggetti basata sull’analisi del colore;

• Feature di tessitura:

▫ matrici di co-occorrenza dei livelli di grigio e relative misure;

▫ filtri di Gabor: banchi di filtri, filtraggio contestuale e applicazioni

all’enhancement di impronte digitali;

▫ Haar features: immagine integrale ed estrazione efficiente delle

feature, applicazioni alla localizzazione del volto;

▫ Local Binary Pattern: descrittore e applicazioni al riconoscimento del

volto.

• Feature di forma:

▫ estrazione del contorno e indicatori di base, rappresentazioni

monodimensionali della forma (centroid distance function, ecc…);

▫ Beam Angle Statistics, shape matrix, descrittori di Fourier.

35

Programma del corso

• Keypoints e descrittori locali:

▫ Localizzazione dei punti di interesse: Harris corner detector;

▫ Localizzazione invariante per cambiamenti di scala: Harris Laplace,

Laplacian of Gaussian, Difference of Gaussian;

▫ Keypoints e descrittori: descrittori SIFT, SURF, BRIEF, Histogram of

Oriented Gradients.

• Bag of visual Words:

▫ Tecniche per la creazione del dizionario;

▫ Applicazioni alla classificazione di immagini;

• Tecniche di localizzazione di oggetti:

▫ Template matching rigido basato su feature e applicazioni alla

localizzazione di oggetti;

▫ Trasformata di Hough con applicazioni all’allineamento di impronte

digitali;

▫ Template deformabili: tipologie di template, algoritmo Ransac per

l’allineamento di immagini tramite keypoint.

36

Conoscenze minime consigliate dal corso di VA1

• Dispense

▫ 1 - Immagini (Immagini digitali, Modelli di colore, Operazioni sui

pixel, Operazioni locali);

▫ 2 - Estrazione dei bordi, Segmentazione;

▫ 3 - Template matching (Introduzione, Correlazione);

▫ E2 (Per chi non ha mai programmato in C#);

▫ E3;

• Esercitazioni

▫ Es. 1;

▫ Es. 9;

▫ Es. 10.

N.B. Le principali tecniche di base per l’elaborazione di immagini e

il filtraggio saranno comunque riprese durante le lezioni di questo

corso.

Potete trovare tutto il materiale su:

http://bias.csr.unibo.it/FEI/

Informazioni generali

• Modalità d’esame▫ Consegna e discussione di un elaborato concordato con il docente

▫ Prova teorica (colloquio orale) sugli argomenti visti a lezione.

• Materiale didattico▫ Dispense fornite dal docente, disponibili nella pagina del corso:

http://bias.csr.unibo.it/VR/

• Testi di riferimento Sistemi Biometrici▫ S.Z. Li, A.K. Jain, Handbook of Face Recognition, Springer, 2005.

▫ J.L. Wayman, A.K. Jain, D. Maltoni, D. Maio, Biometric Systems -

Technology, Design and Performance Evaluation, Springer, 2005.

▫ H. Wechsler, Reliable Face Recognition Methods: System Design,

Implementation and Evaluation, Springer, 2007.

▫ A.K. Jain, P. Flynn, A.A. Ross, Handbook of Biometrics, Springer, 2008.

▫ D. Maltoni, D. Maio, A.K. Jain, S. Prabhakar, Handbook of Fingerprint

Recognition (Second Edition), Springer, 2009.

38

Altre risorse…

Survey: articoli introduttivi ai diversi argomenti o settori applicativi.

Articoli su Riviste: esistono decine di riviste dedicate al settore del PR; le più note:

IEEE Transactions on Pattern Analysis and Machine Intelligence

Pattern Recognition

Pattern Recognition Letter

Archivi e motori di ricerca

Google (oramai universale anche per letteratura scientifica)

Computer Vision Bibliography - USC Los Angeles

http://www.visionbib.com/bibliography/contents.html

Pagine Interessanti

Computer Vision Homepage: http://www.cs.cmu.edu/~cil/vision.html

Pattern Recognition on the Web: http://cgm.cs.mcgill.ca/~godfried/teaching/pr-web.html

International Association for Pattern Recognition (IAPR): http://www.iapr.org/

BIOLAB: http://biolab.csr.unibo.it/

39

Bibliografia

[Cher98] V. Cherkassky e F. Mulier, Learning from data -

Concepts, Theory and Methods, Wiley 1998.

[Duda00] R. Duda, P. Hart e G. Stork, Pattern classification,

Wiley 2000.

[Wata85] S. Watanabe, Pattern Recognition: Human and

Mechanical, Wiley, New York 1985.

[Jain00] A.Jain, R.Duin e J. Mao, “Statistical Pattern

Recognition: a Review”, IEEE Transactions on Pattern

Analysis Machine Intelligence, Vol. 22, No. 1, Jan. 2000.

40