RANSAC

RANSAC sta per "RANdom SAmple Consensus". È un metodo iterativo per la stima dei parametri di un modello matematico a partire da un insieme di dati contenente outlier. È un algoritmo non deterministico nel senso che produce un risultato corretto solo con una data probabilità, che aumenta al crescere delle iterazioni consentite. L'algoritmo è stato pubblicato per la prima volta da Fischler e Bolles nel 1981.

L'assunzione di base per il funzionamento è che i dati siano costituiti da inlier, i.e. dati la cui distribuzione può essere caratterizzata dall'insieme di parametri di un modello, e outlier cioè dati che non sono rappresentati da tale modello. Inoltre, i dati possono essere affetti da rumore. Gli outlier possono provenire, ad esempio, da valori estremi del rumore o da misure erronee o ipotesi incorrette sull'interpretazione dei dati. RANSAC assume inoltre che, dato un insieme (solitamente ridotto) di inlier, esiste una procedura che può stimare i parametri di un modello che rappresenta in modo ottimale i dati.

Esempio

Un semplice esempio è il "fitting" (cioè della costruzione di una funzione matematica che rappresenti dei dati in modo appropriato) di una retta (bidimensionale) su un insieme di osservazioni. Ipotizzando che questo insieme contenga sia inlier (cioè punti che in questo caso possano essere rappresentati da questa retta), che outlier (cioè punti che "non sono vicini" alla retta), un semplice metodo dei minimi quadrati produrrà una retta che non rappresenta adeguatamente gli inlier. La ragione è che viene cercata una retta che sia ottimale rispetto a tutti i punti, inclusi gli outlier. RANSAC, invece, può produrre un modello che è calcolato solo sulla base degli inlier, sempre che la probabilità di scelta di soli inlier tra i dati sia abbastanza alta. Questo non è in ogni caso garantito e c'è una serie di parametri dell'algoritmo che devono essere scelti in modo accurato per mantenere tale probabilità abbastanza alta.

• 
  Un dataset con molti outlier, sul quale deve essere stimata una retta.
• 
  Retta stimata con RANSAC, gli outlier (in rosso) non ne influenzano la stima.

Panoramica

L'input dell'algoritmo RANSAC è un insieme di dati osservati, un modello parametrizzato che può rappresentare o essere adattato alle osservazioni, e alcuni parametri di confidenza. RANSAC raggiunge il suo obiettivo scegliendo iterativamente un sottoinsieme casuale dei dati originali. I dati sono considerati come inlier ipotetici e l'ipotesi viene testata nel modo seguente:

1. Un modello viene assegnato agli inlier ipotetici, i.e. tutti i parametri liberi del modello vengono ricostruiti dai dati.
2. Tutti gli altri dati vengono testati sul modello stimato e, se un punto rientra in tale modello, viene considerato anch'esso un inlier ipotetico.
3. Il modello stimato è abbastanza buono se un numero sufficiente di punti è stato classificato come inlier ipotetici.
4. Il modello viene nuovamente stimato su tutti gli inlier ipotetici, perché era stato stimato solo su quelli iniziali.
5. In conclusione, il modello viene valutato attraverso una stima dell'errore che si commette associando agli inlier ipotetici il modello.

Questa procedura viene ripetuta un numero fissato di volte, producendo ad ogni iterazione o un modello che viene rifiutato a causa del basso numero di punti classificati come inlier, o un modello corretto assieme ad una corrispondente misura dell'errore.

Algoritmo

La variante LO-RANSAC (Locally Optimized Ransac) procede, in pseudocodice, nel modo seguente:

input:

    dati - un insieme di osservazioni
    modello - un modello che può essere assegnato ai dati
    n - il numero minimo di dati per cui si richiede la appartenenza al modello
    k - il numero di iterazioni eseguite dall'algoritmo
    t - un valore di soglia per determinare quando un dato appartiene al modello
    d - il numero di dati "vicini" richiesti per asserire che un modello rappresenta bene i dati

output:

    miglior_modello - parametri del modello che meglio rappresenta i dati (o nil se nessun modello sufficientemente buono viene trovato)
    miglior_consensus_set - dati dai quali il modello è stato stimato
    miglior_errore - l'errore del modello stimato relativo ai dati

algoritmo:

iterazioni := 0
miglior_modello := nil
miglior_consensus_set := nil
miglior_errore := infinito
while iterazioni < k 
    possibili_inlier := n valori scelti casualmente dai dati
    possibile_modello := parametri del modello stimati su possibili_inlier
    consensus_set := possibili_inlier

    for ogni punto di dati not in possibili_inlier 
        if punto appartiene a possibile_modello con un errore minore di t
            aggiungi punto a consensus_set
    
    if numero di elementi in consensus_set > d 
        (implica che abbiamo trovato un buon modello,
        testiamo ora quanto è buono)
        modello_migliorato := parametri del modello stimato su tutti i punti di consensus_set
        errore_attuale :=misura di quanto bene modello_migliorato si adatta ai punti
        if errore_attuale < miglior_errore
            abbiamo trovato un modello migliore dei precedenti,
            salviamolo fino a che non ne viene trovato uno ancora più buono)
            miglior_modello := modello_migliorato
            miglior_consensus_set := consensus_set
            miglior_errore := errore attuale
     
    incrementa iterazioni

return miglior_modello, miglior_consensus_set, miglior_errore

Possibili varianti dell'algoritmo includono:

• Interrompi il loop principale se è stato trovato un modello sufficientemente buono, cioè uno con un errore abbastanza piccolo. Può salvare del tempo computazionale ma aggiunge un ulteriore parametro.
• Calcola errore_attuale direttamente da possibile_modello senza riestimare il modello da consensus_set (algoritmo di RANSAC originale). Può ridurre il tempo a spese di una maggiore sensibilità al rumore, dato che vengono comparati errori relativi a modelli stimati con un numero ridotto di punti.
• Usare una funzione peso differente (M-SAC e simili) per pesare i potenziali inlier dai potenziali outlier.

Parametri

I valori dei parametri t e d devono essere calcolati da specifici requisiti relativi all'applicazione e ai dati, a volte basati su valutazioni sperimentali. Il parametro k (il numero di iterazioni), invece, può essere determinato da risultati teorici. Sia p la probabilità che RANSAC in qualche iterazione selezioni solo inlier dai dati in input quando va a scegliere gli n punti dai quali i parametri del modello vengono stimati. Quando succede questo, è facile che il modello risultante sia utile, quindi p ci dà la probabilità che l'algoritmo produca un risultato utile. Sia w la probabilità di scegliere un inlier ogni volta che un singolo punto viene scelto, cioè,

$w$ = numero di inlier / numero di punti nei dati

Comunemente succede che $w$ non è conosciuto a priori, ma sappiamo dei valori di massima. Assumendo che gli n punti necessari alla stima del modello siano selezionati indipendentemente, $w^{n}$ è la probabilità che tutti gli n punti siano inlier e $1-w^{n}$ è la probabilità che almeno uno degli n punti sia un outlier, il che implica che da questo insieme di punti verrà stimato un modello "cattivo". Quella probabilià al variare di k è la probabilità che l'algoritmo non scelga mai un insieme di n punti che siano tutti inlier e deve essere uguale a $1-p$. Perciò,

$1-p=(1-w^{n})^{k}$

che, applicando il logaritmo su entrambi i lati, ci dà

$k={\frac {\log(1-p)}{\log(1-w^{n})}}$

Da notare che questo risultato assume che gli n punti dei dati sono selezionati in modo indipendente, cioè, un punto che è stato già selezionato viene sostituito e può essere selezionato ancora nella stessa iterazione. Questo è spesso un approccio poco ortodosso e il valore ottenuto per k deve essere considerato come un limite superiore nel caso i punti vengano scelti senza sostituzione. Per esempio, nel caso della ricerca di una retta che rappresenti i dati illustrata precedentemente in figura, l'algoritmo RANSAC sceglie tipicamente 2 punti in ogni iterazione e calcola possibile_modello come la retta che passa per i due punti ed è quindi necessario che i due punti siano distinti.

Per guadagnare ulteriore confidenza, deviazione standard o suoi multipli devono essere aggiunti a $k$. La deviazione standard di $k$ è definita come

$SD(k)={\frac {\sqrt {1-w^{n}}}{w^{n}}}$

Vantaggi e svantaggi

Un vantaggio di RANSAC è l'abilità di produrre stime robuste del modello dei parametri, cioè è capace di stimare parametri con un alto grado di accuratezza anche quando è presente un numero significativo di outliers nel data set. Uno svantaggio di RANSAC è che non esiste un limite superiore al tempo che potrebbe impiegare per calcolare tali parametri. Quando il numero di iterazioni è limitato, la soluzione ottenuta potrebbe non essere ottimale. Per ovviare a questo, RANSAC offre un compromesso: calcolando un grande numero di iterazioni, la probabilità di ottenere un modello ragionevole aumenta. Un altro svantaggio di RANSAC è che richiede il settaggio dei parametri in base al problema.