RICERCA ITALIANA     

Metodi basati sulla similarita' per la visione artificiale e il riconoscimento delle forme: Teoria, algoritmi, applicazioni

Università "Ca' Foscari" di Venezia

Abstract

Le tecniche tradizionali di riconoscimento automatico delle forme (pattern recognition) sono centrate attorno alla nozione di "feature". Secondo questa visione, gli oggetti da classificare sono rappresentati in termini di proprietà intrinseche all'oggetto stesso. Di conseguenza, un tipico sistema di pattern recognition prende le sue decisioni semplicemente considerando uno o più vettori di feature in ingresso. La forza di questo approccio sta nel fatto che può sfruttare un ampio spettro di strumenti matematici che vanno dalla statistica, alla geometria, all'ottimizzazione. In molte applicazioni pratiche, però, gli oggetti non sono naturalmente rappresentabili in termini di vettori di feature. Per esempio, le rappresentazioni basate su grafi (o strutture relazionali) non posseggono un ordine canonico o una corrispondenza tra vertici. D’altra parte, è spesso possibile ottenere una misura di (dis)similarità tra gli oggetti da classificare. È quindi importante essere in grado di progettare un sistema di pattern recognition che, diversamente dai sistemi tradizionali, accetti in input una matrice contenente le similarità tra gli oggetti e produca in uscita etichette di classe. Questo consente lo sviluppo di algoritmi indipendenti dalla reale rappresentazione dei dati e consente l'uso di dissimilarità non metriche. Inoltre, rende gli approcci applicabili a problemi che non hanno una naturale immersione in uno spazio di feature uniforme, come, per esempio, il clustering di rappresentazioni strutturali o basate su grafi, o l’analisi di sequenze. Queste rappresentazioni si adattano bene sia a problemi supervisionati che non supervisionati.

In questo progetto intraprenderemo uno studio approfondito su diversi aspetti della pattern recognition basata sulla similarità, dal punto di vista teorico, algoritmo ed applicativo, avanzando quindi lo stato dell'arte in questo campo. Precisamente, affronteremo problemi ed algoritmi riguardanti dati non vettoriali, quali strutture relazionali e modelli grafici quali i modelli Markoviani a stati nascosti (HMM), dove gli approcci basati sulla similarità mostrano il meglio della loro potenza e flessibilità nei confronti degli approcci tradizionali basati su feature. Il progetto intende coprire un ampio spettro di problemi e prospettive. Considereremo sia l'apprendimento supervisionato sia quello non supervisionato, modelli sia generativi sia discriminativi, e il nostro interesse spazierà da problemi puramente teorici ad applicazioni nel mondo reale. La rete di ricerca è stata attentamente strutturata in modo da includere competenze di alto livello in tutte le aree considerate. In aggiunta, vogliamo realizzare una rete altamente coesa dove, non solo ogni unità di ricerca è ben caratterizzata in termini di competenze, problemi affrontati, metodologie utilizzate ed obiettivi, ma è pure strettamente legata al resto del gruppo. <<<

Coordinatore Scientifico del Programma di Ricerca

Marcello Pelillo Università "Ca' Foscari" di VENEZIA

Obiettivo del Programma di Ricerca

La sfida del riconoscimento automatico delle forme (pattern recognition) sta nello sviluppare metodi computazionali che imparino a distinguere tra un certo numero di classi rappresentate da esempi. Le tecniche di pattern recognition classiche sono centrate attorno alla nozione di "feature" [DHS01]. Secondo questa visione, gli oggetti da classificare sono rappresentati in termini di proprietà intrinseche all'oggetto stesso. Di conseguenza, un tipico sistema di pattern recognition prende le sue decisioni semplicemente considerando uno o più vettori di feature di input. La forza di questo approccio sta nel fatto che può sfruttare un ampio spettro di strumenti matematici che vanno dalla statistica, alla geometria, all'ottimizzazione.

D'altra parte, in molte applicazioni pratiche è difficile ottenere una buona descrizione degli oggetti in termini di feature. Tipicamente, questo avviene quando è difficile definire le feature, quando i dati hanno una dimensione molto alta, quando le feature contengono quantità sia continue sia categoriali o, infine, quando gli oggetti da classificare sono rappresentati in termini di grafi o strutture relazionali. In questi casi, è spesso possibile ottenere una misura di (dis)similarità tra gli oggetti da classificare e, in alcune applicazioni quali il riconoscimento della figura [E99], l'uso delle (dis)similarità rende il problema più immediato. È quindi importante essere in grado di progettare un sistema di pattern recognition che, diversamente da quelli tradizionali, accetti in input una matrice contenente le similarità tra gli oggetti e produca in uscita etichette di classe. Questo consente lo sviluppo di algoritmi indipendenti dalla rappresentazione dei dati e consente l'uso di dissimilarità non metriche. Inoltre, tale approccio è supportato dal fatto che le similarità possono essere viste come una connessione tra la percezione umana e la conoscenza di alto livello, essendo questa un fattore cruciale nel processo umano di riconoscimento e categorizzazione [G99,E99,W+92].

In questo progetto intraprenderemo uno studio approfondito su diversi aspetti della pattern recognition basata sulla similarità, dal punto di vista teorico, algoritmico ed applicativo, avanzando quindi lo stato dell'arte in questo campo. Precisamente, affronteremo problemi ed algoritmi riguardanti dati non vettoriali, quali strutture relazionali e modelli grafici quali i modelli Markoviani a stati nascosti (HMM), dove gli approcci basati sulla similarità mostrano il meglio della loro potenza e flessibilità nei confronti degli approcci tradizionali basati su feature.

Il progetto intende coprire un ampio spettro di problemi e prospettive. Considereremo sia l'apprendimento supervisionato sia quello non supervisionato, modelli sia generativi sia discriminativi, e il nostro interesse spazierà da problemi puramente teorici ad applicazioni nel mondo reale. La rete di ricerca è stata attentamente strutturata in modo da includere competenze di alto livello in tutte le aree considerate. In aggiunta, vogliamo realizzare una rete altamente coesa dove, non solo ogni unità di ricerca è ben caratterizzata in termini di competenze, problemi affrontati, metodologie utilizzate ed obiettivi, ma è pure strettamente legata al resto del gruppo. I nostro obiettivi principali sono i seguenti.


1. Teoria

Dal punto di vista teorico, verranno perseguiti due obiettivi principali. Anzitutto, definiremo nuove misure di (dis)similarità (metriche) per strutture relazionali dove non sia posta alcuna restrizione sulla natura degli attributi e sulla topologia, portando quindi il lavoro già compiuto in questa direzione alla sua massima generalità. Il problema sarà affrontato utilizzando un nuovo approccio basato sulla teoria dei grafi che nasce dallo studio di una formulazione continua del problema della clique massima pesata sugli archi.

Il secondo obiettivo è di condurre uno studio teorico sui modelli generativi basati sulla similarità. Nello specifico, verranno esplorate le capacità espressive dei modelli generativi, modelli HMM e modelli grafici in generale, per risolvere direttamente problemi di classificazione e clustering o per estrarre similarità intrinseche e non esplicitamente calcolabili con approcci standard. Verranno inoltre studiate le caratteristiche estrinseche degli spazi risultanti dall'uso del paradigma di rappresentazione per similarità.


2. Algoritmi

Da una punto di vista algoritmico (ed indipendente dall'applicazione), verranno presi in considerazione sia modelli discriminativi che generativi. Dal lato discriminativo, svilupperemo algoritmi per risolvere due problemi classici legati alle strutture relazionali: il matching ed il clustering di strutture. I due problemi saranno affrontati in un unico framework di minimizzazione d'energia, e saranno sviluppati algoritmi basati sulla teoria evoluzionistica dei giochi e sulla teoria della complementarietà lineare.

Nel contesto generativo, svilupperemo algoritmi sia supervisionati che non supervisionati. Esploreremo le potenzialità dei modelli grafici a partire da istanze specifiche quali HMM fino ai modelli più complessi e generali e studieremo come questi modelli possano essere accoppiati a modelli di tipo discriminativo all'interno del paradigma di rappresentazione per similarità.


3. Applicazioni

Considereremo vari problemi reali di visione in cui tecniche basate sulla similarità si sono dimostrate particolarmente promettenti. Una prima applicazione sarà il rilevamento ed il riconoscimento di volti ed espressioni del viso. In particolare, in contrasto con la maggior parte degli attuali sistemi di riconoscimento di volti, lavoreremo con immagini a colori ad alta risoluzione, acquisite in ambito non vincolato (ovvero con sfondo e condizioni di illuminazione arbitrarie). Nel tentativo di migliorare l'accuratezza del riconoscimento, useremo anche informazioni geometriche in 3D. In questo contesto diventa appropriato l'uso di strutture relazionali. Modelli generativi (quali HMM) saranno utilizzati per l'analisi di sequenze video.

Una seconda applicazione riguarderà l'interrogazione per contenuto di basi di dati visuali e le tecniche di "relevance feedback", che
consentono di raffinare i risultati di una interrogazione sulla base di informazioni fornite dall'utente. In particolare, verranno affrontati diversi aspetti riguardanti la rappresentazione delle immagini (tramite vettore di feature, mediante grafi, ecc.), e la rappresentazione dell'informazione di feedback. In questo contesto, verranno utilizzate strutture relazionali e approcci basati sulla teoria dei grafi.

L'ultima applicazione riguarderà l'analisi di sequenze video. In questo contesto, l'obiettivo è quello di analizzare sequenze video per estrarre conoscenza sulla scena, sia in termini di semplice suddivisione tra sfondo e informazione rilevante (figura/sfondo), sia in termini di comprensione della semantica. Queste tecniche saranno applicate a problemi quali sorveglianza, riassunto di sequenze video (ovvero estrazione dei frame più significativi), estrazione di informazione a super-risoluzione da sequenze video di bassa qualità, e analisi e classificazioni di espressioni facciali spontanee. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

La classificazione basata sulla similarità è stato un tema ricorrente, ma sotto-studiato, per oltre 40 anni. Un approccio diretto alla classificazione supervisionata basata su rappresentazioni a dissimilarità è dato dalla regola "nearest neighbor" (NN) [CH67,F90] o, più in generale, dall'apprendimento basato su istanze [AKA91]. Questi classificatori dipendono solamente dall'ordine delle distanze ottenute. La regola NN, nella sua forma più semplice (1-NN) assegna un nuovo oggetto alla classe con il rappresentante più vicino. La regola k-NN basa la decisione su di un voto a maggioranze: un oggetto diventa membro della classe che occorre più di frequente tra i k rappresentanti più vicini.

La regola NN ha trovato applicazione in molti domini. Per esempio, Jain e Zongker [JZ97] la applicano al riconoscimento di cifre scritte a mano. Qui la misura di dissimilarità è ottenuta da dei template deformabili ed è usata una regola 1-NN per la classificazione finale dei pattern.

Anche se la regola NN si basa su decisioni locali, è comunque computazionalmente onerosa, visto che devono essere ricavate le dissimilarità con tutti gli esempi di training. Per superare questa limitazione, Pekalska e Duin [PD02] hanno recentemente proposto di addestrare i classificatori usando le dissimilarità con un insieme di prototipi chiamato l'insieme rappresentante. Graepel et al. [G+99] hanno investigato il problema della classificazione basata su (dis)similarità usando un approccio basato sulla minimizzazione del rischio strutturale di Vapnik [V98]. Jacobs e Weinshall [JW00] hanno studiato l'uso di classificatori basati su distanze non metriche.

In [PD01] Duin e Pekalska mostrano come un classificatore Bayesiano (un classificatore RLNC-regolarizzato lineare basato su densità normali) nello spazio delle dissimilarità funzioni meglio della regola NN su due applicazioni reali. Questi aspetti sono stati approfonditi in [PD02], dove altri classificatori nello spazio delle dissimilarità sono stati applicati a problemi di riconoscimenti di cifre e bioinformatica. Infine, in [PPD02] è stato introdotto un approccio a kernel generalizzato e sono stati analizzati gli aspetti di classificazione dei kernel di dissimilarità.

Classicamente, il clustering basato sulle similarità (pairwise) usa concetti ed algoritmi sviluppati nell'ambito della teoria dei grafi [JD88,DHS01]. Questi metodi sono di notevole interesse perché formulano il problema del clustering in termini di puri problemi di teoria dei grafi, per i quali si conosce una solida teoria ed esistono potenti algoritmi risolutivi. Fondamentalmente, gli algoritmi di clustering basati su grafi consistono nel cercare determinate strutture combinatorie nel grafo di similarità, quali un albero di copertura minimo [Z71] o un taglio minimo [WL93] e, tra questi metodi, un approccio ben noto (l'algoritmo complete-link [JD88]) si riduce alla ricerca di un sottografo completo, ovvero di una clique. A tal proposito, alcuni autori (p. es., [RY81]) ipotizzano che questa sia la definizione più appropriata di cluster. Come notato in [DHS01], questi metodi possono produrre cluster piuttosto intricati, ma raramente ottimizzano una funzione costo globale che sia facilmente specificabile.

Una strategia radicalmente differente consiste nel formulare il problema del clustering (pairwise) come un problema di ottimizzazione [HH93,HB97,FB03,KSS03]. In questo caso, dapprima si costruisce una funzione costo con lo scopo di quantificare la qualità di una soluzione (ovvero di un cluster o di una partizione dei dati). Successivamente si sviluppa un algoritmo che trovi i massimi globali della funzione costo. Quasi invariabilmente, gli algoritmi di minimizzazione sviluppati finora incorporano tecniche prese dalla meccanica statistica, in particolare dalla teoria di campo medio, che permettono di evitare soluzioni locali insoddisfacenti. Il merito maggiore delle tecniche di clustering basate sull'ottimizzazione è la loro abilità di fornire (per definizione) una misura quantitativa della qualità di un cluster. A livello computazionale, comunque, non c'è alcuna garanzia che le soluzioni trovate dall'algoritmo di ottimizzazione siano ottimi globali.

Come compromesso tra gli approcci basati sulla teoria dei grafi e quelli basati sull'ottimizzazione, i metodi di clustering spettrale stanno diventando molto diffusi nelle comunità di machine learning e visione artificiale [SB98,PF98,SM00]. Questi metodi sono interessanti in quanto basati su algoritmi semplici la cui stabilità è ben nota. In sintesi, le tecniche di clustering spettrale identificano partizioni rilevanti dei dati attraverso gli autovettori della matrice di similarità, o altre matrici derivate da essa. Questi metodi, in generale, possono essere visti come utili euristiche, non sono associati a nessuna funzione costo globale esatta, e non offrono nessuna interpretazione combinatoria esatta. Di fatto, essi forniscono una connessione tra gli approcci basati sulla teoria dei grafi e quelli basati sull'ottimizzazione, ma tale connessione è debole e vale solo in termini di approssimazione.

Come accennato in precedenza, una rappresentazione non-vettoriale che si presta particolarmente bene ad un approccio pairwise, è quella delle relazioni strutturali, chiamate anche grafi etichettati, grafi relazionali con attributi, reti semantiche, etc. Esse sono da tempo utilizzate con successo in visione artificiale e pattern recognition, specialmente per il loro potere descrittivo e la loro flessibilità, e recentemente si è registrato un rinnovato e crescente interesse attorno ad esse. (si veda, ad esempio, [DPZ01,BC04,BB05]).

Usando questo framework possiamo trasformare un problema di riconoscimento in uno di matching strutturale. Il problema di come misurare la similarità (o distanza) di informazione pittorica usando astrazioni relazionali è stato un argomento di ricerca per più di vent'anni. I primi lavori sull'argomento includono l'idea di Barrow e Burstall di caratterizzare la similarità tra due grafi usando la cardinalità del loro massimo sottografo comune [BB76], e le estensioni al concetto di string edit-distance al graph matching di Fu e dei sui collaboratori [E86]. Shapiro e Haralick [SH82] hanno descritto una distanza relazionale tra descrittori strutturali. Ci sono anche stati tentativi di usare un approccio basato sulla teoria dell'informazione. Wong e You [WY85] usano l'entropia dei grafi random, mentre Boyer e Kak [BK88] hanno usano l'informazione mutua. Più recentemente, Christmas, Kittler e Petrou [CKP95], e Wilson and Hancock [WH97] hanno sviluppato una misura probabilistica della similarità tra grafi. Sfortunatamente, con la notevole eccezione di edit-distance, le misure risultanti non sono metriche, cioè sono non simmetriche, negative o violano la disuguaglianza triangolare. La mancanza di proprietà metriche rende impossibile un embedding non distorto in uno spazio vettoriale ed impedisce un ordine naturale in un database di grafi. D'altra parte, calcolare l'edit-distance è un problema computazionalmente difficile [ZSS92], quindi per calcolarla sono necessarie approssimazioni che, invariabilmente, annullano le proprietà metriche della misura.

Recentemente è emerso un nuovo approccio alla definizione di misure di distanza. In [BS98], Bunke e Shearer hanno introdotto una misura di distanza tra grafi basata sul massimo sottografo comune, e hanno dimostrato che essa è una metrica. Wallis et al. [WSKR01], hanno introdotto una variante di questa distanza basata sulla cardinalità del minimo supergrafo comune. L'approccio può gestire in maniera naturale vari tipi di rumore e distorsione, quali l'aggiunta o la cancellazione di nodi in entrambi i grafi, ed è particolarmente vantaggioso in quanto non richiede l'uso di alcuna funzione costo, evitando quindi il maggior svantaggio degli approcci basati sull'edit-distance. Tutte queste misure basate sulle sottostrutture, comunque, possono gestire solo distorsioni strutturali, e non sono pertanto applicabili a strutture relazionali munite di attributi numerici.

I modelli di Markov a stati nascosti (Hidden Markov Models, HMM) rappresentano una famiglia di modelli probabilistici utilizzati per catturare caratteristiche dinamiche di dati sequenziali [R89]. Le HMM possono essere viste come generalizzazioni stocastiche di automi a stati finiti, dove sia le transizioni tra stati ed i simboli generati in output sono regolati da distribuzioni probabilistiche che osservano la proprietà di Markov.

Questa rete di dipendenze stocastiche diviene immediatamente evidente se si usa il formalismo dei modelli grafici (Graphical Models, GM in breve), dove i nodi del grafo sono variabili casuali e gli archi rappresentano le dipendenze immediate [L96]. La potenza delle HMM risiede nel fatto che lo schema di base sfrutta la proprietà di Markov, una caratteristica fortemente radicata in molti fenomeni naturali, per gestire la complessità delle sequenze complete sfruttando solamente interazioni locali e limitate.

Tali modelli sono stati utilizzati negli ultimi anni in svariati contesti, tutti implicanti un'analisi di dati sequenziali. Ciononostante, l'avvento di nuove e più difficili applicazioni, quali ad esempio l'analisi di sequenze video, ha portato alla necessità di sviluppare e definire nuove e più complesse strutture di dipendenze Markoviane, cioè nuove tipologie di modelli grafici. Alcuni sforzi in questa direzione sono stati fatti ad esempio con la definizione di varianti complesse di HMM (e.g., HMM accoppiati, gerarchici, Input-Output HMM, etc.) [BOP97][FST98].

Nonostante ciò, una maggiore sofisticazione e lavori più ambiziosi hanno reso i problemi così intricati da richiedere sovrastrutture informative comprendenti molti strati di componenti "nascoste" (cioè non osservabili/osservate). Fortunatamente, i recenti progressi nei GM hanno fornito un formalismo rigoroso per rappresentare tali conoscenze a priori e combinarle con le osservazioni empiriche in modo da ottenere sistemi stocastici altamente strutturati [HSSS]. Infatti, i GM hanno generalizzato le HMM ed altri modelli, espandendo enormemente la flessibilità dell'approccio generativo [P97]. Le strutture dei GM incorporano diversi tipi di proprietà di Markov che permettono di introdurre vincoli dedotti o ipotizzati dalla natura dei problemi [L96], proponendosi spesso come modelli di processi invece che di dati.

Un'importante applicazione in cui gli approcci pairwise hanno recentemente dimostrato di offrire vantaggi rispetto alla classificazione basata su feature è il recupero di immagini basato sul contenuto. Nell'interrogazione di basi di dati visuali, i risultati delle query di solito soddisfano le esigenze dell'utente solo in parte. Per questo motivo si ritiene indispensabile che il sistema di interrogazione della base di dati visuale preveda delle interazioni con l'utente. Questa fase, denominata "relevance feedback", sta diventando negli ultimi anni uno dei temi maggiormente rilevanti nel settore dell'interrogazione di basi di dati visuali [ZH03].

Di recente, sono stati proposti alcuni metodi basati sulla formulazione del relevance feedback come un problema di classificazione [ZH01]. Obiettivo di questo problema di classificazione è stabilire, per ciascuna immagine, la probabilità che appartenga alla classe delle immagini rilevanti. Per ottenere questo risultati, sono state proposte alcune tecniche di pattern recognition opportunamente adattate. Il problema principale nell¹uso di tali tecniche per il relevance feedback è il forte sbilanciamento fra le classi rilevante/non-rilevante. Infatti le immagini rilevanti sono quelle (in genere poche) che l'utente ha giudicato rilevanti, mentre per definizione le non-rilevanti sono tutte le altre immagini del database. Allo stato dell¹arte gli approcci di relevance feedback basati su tecniche di pattern recognition che hanno fornito buone prestazioni utilizzano il concetto di kernel [T+06a,T+06b]. Un approccio diverso al relevance feedback è rappresentato dall'uso di
tecniche di pattern recognition basate su uno "spazio di similarità"
("dissimilarity space") [PD01,PD02]. Alcuni risultati preliminari mostrano che l'accuratezza della fase di relevance feedback può essere migliorata rispetto ad altre tecniche proposte in letteratura [GR05]. <<<