L’algoritmo di RANdom Sample And Consesus `e un algoritmo iterativo per la stima dei parametri di un modello dove l’insieme dei dati `e fortemente condizionato dalla presenza di molti outlier. `E un algoritmo non deterministico, pubblicato da Fisher [FB81], basato sulla selezione casuale degli elementi generatori del modello.
RANSAC, e tutte le sue varianti, possono essere viste come un algoritmo che iterativamente si alterna tra due fasi: la fase di generazione delle ipotesi (hypothesis generation) e la fase di valutazione delle ipotesi (hypothesis evaluation).
L’algoritmo consiste nel selezionare casualmente s campioni fra tutti gli n campioni in ingresso X = {x1, . . . , xn}, con s sufficientemente grande per ricavare un modello (l’ipotesi). Ottenuta un’ipotesi, vengono contati quanti degli n elementi di X sono abbastanza vicini ad essa per appartenergli. Un campione x ∈ S appartiene o meno al modello (ovvero `e un inlier o un outlier ) se la sua distanza rispetto al modello dβ(x) `e inferiore o superiore a una soglia data τ , soglia normalmente dipendente dal problema. La soglia τ si scontra con quei problemi pratici dove l’errore additivo `e di tipo gaussiano, ovvero dove il supporto `e infinito. In questo caso `e comunque necessario definire una probabilit`a p di individuazione degli inlier per definire una soglia τ .
Tutti gli elementi in ingresso che soddisfano l’ipotesi si chiamano consensi (consensus).
L’insieme dei consensi S associati all’ipotesi β `e il consensus set di β:
S(β) = {x ∈ X : dβ(x) < τ } (3.110)
Tra tutti i modelli generati casualmente viene infine scelto il modello che soddisfa una determinata metrica, per esempio, per RANSAC originale, quella che ha il consenso di cardinalit`a massima.
Uno dei problemi `e scegliere quante ipotesi generare per avere una buona probabilit`a di ottenere il modello corretto.
Esiste una relazione statistica tra il numero di iterazioni N e la probabilit`a p di individuare una soluzione di soli inlier : N = log(1 − p)
log(1 − (1 − )s) (3.111)
con la probabilit`a a priori della densit`a degli outlier e s il numero di punti necessari a definire un modello. La dimensione di un consensus set minimo pu`o essere dedotta in via statistica semplicemente come T = (1 − )n.
Normalmente s viene scelto uguale al numero di elementi necessari per creare il modello ma, se superiore a questo numero, il modello che viene generato deve essere un modello costruito attraverso una regressione numerica rispetto ai vincoli forniti, condizione necessaria quando la varianza del rumore `e elevata, incrementando tuttavia il rischio di inglobare nei vincoli anche outliers.
3.9.1 M-SAC
La politica di RANSAC `e quella di restituire, fra tutte le ipotesi generate, quella che possiede il minor numero di elementi esterni a una soglia fissata. Questa politica pu`o essere vista come un M-estimator che minimizza una loss function del tipo
ρ =
0 |e| < τ
1 |e| > τ (3.112)
ovvero che assegna come voto 1 a tutti gli elementi pi`u distanti della soglia dal modello valutato e a 0 gli elementi all’interno della soglia τ .
Il concetto si pu`o pertanto generalizzare, nelle tecniche M-SAC (M-Estimator Sample and Consensus), dove la loss function di RANSAC viene modificata.
Come segnalato nella sezione precedente il rumore sui dati pu`o essere visto in parte come rumore gaussiano sugli inliers associato a una distribuzione uniforme di outliers. La negative Maximum Likelihood `e di fatto la loss function teoricamente corretta, base dei metodi MLESAC, ma abbastanza onerosa dal punto di vista computazionale.
Una buona approssimazione, propria delle tecniche M-SAC, `e usare come loss function ρ =
e2 |e| < τ
τ2 |e| > τ (3.113)
Questa loss function modella abbastanza bene il caso di inlier affetti da errore gaussiano a media nulla, e outlier distribuiti uniformemente.
3.9.2 LMedS
L’algoritmo di rigetto degli outlier chiamato Least Median of Squares (LMedS ) `e molto simile concettualmente a RANSAC:
come per RANSAC viene generato un modello partendo da campionamenti casuali dai dati in ingresso ma, invece che scegliere il modello che raccoglie il maggior numero di consensi (o che minimizza una loss function), LMdeS seleziona fra tutti il modello che ha il valore mediano degli errori minore. Tutti i dati in ingresso pertanto vengono confrontati con il modello, ordinati per errore, ed esaminato il valore mediano.
La relazione tra probabilit`a di individuare inlier e numero di iterazioni `e lo stesso di RANSAC. RANSAC tuttavia richiede due parametri (il numero di iterazioni e la soglia per discriminare se un elemento appartiene o meno al data-set), mentre LMedS richiede solo il primo. Per costruzione, LMedS tuttavia tollera al massimo la presenza del 50% di outlier.
Una buona panoramica delle tecniche RANSAC, M-SAC e LMedS si pu`o trovare in [CKY09].
Capitolo 4
Classificazione
Un ruolo predominante nella Visione Artificiale rivestono le tecniche di Classificazione e di machine learning. La grande quantit`a di informazione che si pu`o estrarre da un sensore video supera di gran lunga in quantit`a quella che si pu`o ottenere da altri sensori ma richiedono tecniche complesse che permettano di sfruttare questa ricchezza di informazione.
Come gi`a detto in precedenza, statistica, classificazione e fitting di modelli si possono vedere di fatto come diverse facce di un unico argomento. La statistica ricerca il modo pi`u corretto dal punto di vista bayesiano per estrarre i parametri (dello stato o modello) nascosti di un sistema, affetto eventualmente da rumore, cercando, dati gli ingressi, di restituire l’uscita pi`u probabile mentre la classificazione propone tecniche e modi su come modellare il sistema in maniera efficiente. Infine se si conoscesse il modello esatto che sottost`a a un sistema fisico, qualunque problema di classificazione si ricondurrebbe a un problema di ottimizzazione. Per queste ragioni non `e pertanto facile ne netto capire dove finisca un argomento e inizi l’altro.
Il problema della classificazione si riconduce a quello di ricavare i parametri di un modello generico che permetta di generalizzare il problema avendo a disposizione un numero limitato di esempi.
Un classificatore pu`o essere visto in due modi, a seconda di che tipo di informazione tale sistema voglia fornire:
1. come funzione di “verosomiglianza” verso un modello, come in equazione (4.1);
2. come partizionamento dello spazio degli ingressi, come in equazione (4.2).
Nel primo caso un classificatore viene rappresentato da una generica funzione
f : Rn → Rm (4.1)
che permette di associare all’elemento x in ingresso, formato dalle n caratteristiche rappresentanti l’esempio da classificare, dei valore di confidenza rispetto alle possibili {y1, . . . , ym} classi di uscita (categorie):
f (x) = (p(y1|x), . . . , p(ym|x))
ovvero la probabilit`a che l’oggetto osservato sia proprio yi data la quantit`a osservata x.
A causa sia dell’infinit`a delle possibili funzioni sia della mancanza di ulteriori informazioni specifiche sulla forma del problema, la funzione f non potr`a essere un funzione ben specifica ma verr`a rappresentata da un modello a parametri nella forma
y = f (x, β)
dove y ∈ Rm `e lo spazio degli output, x ∈ Rn spazio degli input mentre β sono i parametri del modello f da determinare nella fase di addestramento.
La fase di addestramento si basa su un insieme di esempi (training set ) formato da coppie (xi, yi) e attraverso questi esempi la fase di addestramento deve determinare i parametri β della funzione f (x, β) che minimizzino, sotto una determinata metrica (funzione di costo), l’errore sul training set stesso.
Per addestrare il classificatore bisogna pertanto individuare i parametri ottimi β che minimizzano l’errore nello spazio delle uscite: la classificazione `e anche un problema di ottimizzazione. Per questa ragione machine learning, fitting di modelli e statistica risultano ambiti di ricerca strettamente legati. Le medesime considerazioni usate in Kalman o per Hough e tutto ci`o detto nel capitolo di fitting di modelli ai minimi quadrati si possono usare per classificare e gli algoritmi specifici di classificazione possono essere usati ad esempio per adattare una serie di osservazioni affette da rumore a una curva.
Normalmente non `e possibile produrre un insieme di addestramento completo: non `e infatti sempre possibile ottenere qualsiasi tipo di associazione ingresso-uscita in modo da mappare in maniera sistematica tutto lo spazio degli input nello spazio degli output e, se ci`o fosse anche possibile, risulterebbe comunque dispendioso disporre della memoria necessaria per rappresentare tali associazioni sotto forma di Look Up Table. Queste solo le principali ragioni dell’utilizzo di modelli nella classificazione.
Il fatto che il training set non possa coprire tutte le possibili combinazioni ingresso-uscita, combinato alla generazione di un modello ottimizzato verso tali dati incompleti, pu`o provocare una non-generalizzazione dell’addestramento: elementi
62
non presenti nell’insieme di addestramento potrebbero essere classificati in maniera errata a causa dell’eccessivo adattamento al training set (problema dell’overfitting). Questo fenomeno `e causato normalmente da una fase di ottimizzazione che si preoccupa pi`u di ridurre l’errore sulle uscite piuttosto che di generalizzare il problema.
Tornando ai modi per vedere un classificatore, risulta spesso pi`u semplice e pi`u generalizzante ricavare direttamente dai dati in ingresso una superficie in Rn che separi le categorie nello spazio n-dimensionale degli ingressi. Si pu`o definire una nuova funzione g che ad ogni gruppo di ingressi associ una ed una sola etichetta in uscita, nella forma
g : Rn→ Y = {y1, . . . , ym} (4.2)
Questo `e il secondo modo di vedere un classificatore.
L’espressione (4.1) pu`o essere sempre convertita nella forma (4.2) attraverso una votazione per maggioranza:
g(x) = arg max
yi
p(yi|x) (4.3)
Il classificatore, sotto questo punto di vista, `e una funzione che restituisce direttamente il simbolo pi`u somigliante all’in-gresso fornito. Il training set ora deve associare a ogni inall’in-gresso (ogni elemento dello spazio) una ed una sola classe y ∈ Y in uscita. Solitamente questo modo di vedere un classificatore permette di ridurre la complessit`a computazionale e l’utilizzo di risorse.
Se la funzione (4.1) rappresenta effettivamente una funzione di trasferimento, una risposta, la funzione (4.2) pu`o essere vista come un partizionamento dello spazio Rn dove a regioni, generalmente molto complesse e non contigue dello spazio degli ingressi, `e associata un’unica classe.
Per le motivazioni addotte in precedenza non `e fisicamente possibile realizzare un classificatore ottimo (se non per problemi di dimensioni molto contenute o per modelli semplici e conosciuti perfettamente) ma esistono diversi classificatori general purpose che a seconda del problema e delle performance richieste possono considerarsi sub-ottimi. Nel caso dei classificatori (4.2) il problema `e quello di ottenere un partizionamento ottimo dello spazio e pertanto `e richiesto un set di primitive veloci e tali da non usare troppa memoria nel caso di alti valori di n, mentre nel caso (4.1) `e richiesta espressamente una funzione che modelli molto bene il problema evitando per`o specializzazioni.
Le informazioni (features) che si possono estrarre da una immagine per permetterne la classificazione sono molteplici. In genere usare direttamente i toni di grigio/colore dell’immagine `e raramente usato in applicazioni pratiche perch´e tali valori sono normalmente influenzati dalla luminosit`a della scena e sopratutto perch´e rappresenterebbero uno spazio di ingresso molto vasto, difficilmente gestibile. `E necessario pertanto estrarre dalla parte di immagine da classificare delle informazioni essenziali (features) che ne descrivano l’aspetto al meglio. Per questa ragione, tutta la teoria mostrata in sezione 6 `e ampiamente usata in machine learning. Sono ampiamente usati infatti, sia le feature di Haar grazie alla loro velocit`a di estrazione o gli Istogrammi dell’Orientazione del Gradiente (HOG, sez.6.2) per la loro accuratezza. Come compromesso, e loro generalizzazione, tra le due classi di feature di recente sono state proposte le Feature su Canali Integrali (ICF, sez.6.3).
Per ridurre la complessit`a del problema di classificazione questo pu`o essere diviso in pi`u strati da affrontare in maniera indipendente: un primo strato trasforma lo spazio degli ingressi nello spazio delle caratteristiche, mentre un secondo livello esegue la classificazione vera e propria partendo dallo spazio delle caratteristiche.
Sotto questa considerazione le tecniche di classificazione si possono dividere in 3 categorie principali:
Rule-based learning In questo caso sia lo spazio delle caratteristiche che i parametri della funzione di classificazione sono decisi da un utente umano, senza sfruttare alcun insieme di dati o esempi di addestramento;
Machine Learning La trasformazione tra spazio di ingressi a spazio delle caratteristiche `e scelta dall’utente tra un insieme finito di funzioni, mentre l’estrazione dei parametri del modello `e lasciata all’elaboratore analizzando gli esempi forniti;
Representation learning Sia la trasformazione in spazio delle caratteristiche che l’estrazione dei parametri del modello sono attuati dal calcolatore.
Recentemente tecniche di Representation learning costruite con pi`u strati in cascata tra loro (Deep Learning) hanno avuto molto successo a risolvere problemi di classificazione complesse.
Tra le tecniche per trasformare lo spazio di ingressi nello spazio delle caratteristiche `e importante citare la PCA, tecnica lineare non supervisionata. La Principal Component Analysis (sezione2.10.1) `e una tecnica che permette di ridurre il numero di ingressi al classificatore, rimuovendo le componenti linearmente dipendenti o ininfluenti, riducendo pertanto la dimensione del problema cercando comunque di preservare al massimo l’informazione.
Per quanto riguarda i modelli e le tecniche di modellazione general purpose molto utilizzate sono
Regressione una regressione di dati ad un modello `e di fatto un classificatore. Di conseguenza, tutta la teoria del capitolo3 pu`o e deve essere usata per classificare dati;Tra
Neural Network Le reti neurali permettono di generare funzioni di tipo (4.1) concatenando tra loro somme, moltiplicazioni e funzioni fortemente non lineari come le sigmoidi. Tecniche di regressione permettono di stimare i parametri di questo modello generico;
Classificatori Bayesiani `e possibile usare il teorema di Bayes direttamente come classificatore o per unire insieme pi`u classificatori in modo da massimizzare la probabilit`a a posteriori di individuare la classe corretta (sezione4.2);
Albero di decisione dove i classificatori sono messi in cascata con altri classificatori (ed ogni nodo rappresenta un qualche attributo estratto dai dati in ingresso);
Decision Stump albero di decisione degenere (1 nodo), permette di partizionare lo spazio delle features usando una semplice soglia, diventando cos`ı il pi`u semplice classificatore di tipo (4.2) ed esempio di classificatore debole;
Ensemble Learning Pi`u classificatori deboli (weak ) possono essere messi in relazione tra loro (Ensemble Learning, sezio-ne4.6) in modo da massimizzare qualche metrica globale (ad esempio il margine di separazione tra le classi). Di fatto non sono veri e propri classificatori ma sono tecniche per unire pi`u classificatori semplici e generare un classificatore complesso (ensemble).
Figura 4.1: Esempio di Template Matching. L’approccio funziona bene sull’immagine di origine, ma non `e possibile estenderlo ad altre immagini, soprattutto con variazioni di luminosit`a e scala sensibili.