RANSAC

L'algoritmo di RANdom Sample And Consensus (RANSAC) è un algoritmo iterativo e non deterministico per la stima dei parametri di un modello in presenza di outlier (FB81). Il metodo si basa sulla selezione casuale degli elementi generatori del modello.

RANSAC, e tutte le sue varianti, possono essere viste come algoritmi che iterativamente alternano tra due fasi: la fase di generazione delle ipotesi (hypothesis generation) e la fase di valutazione delle ipotesi (hypothesis evaluation).

L'algoritmo, in breve, consiste nel selezionare casualmente $s$ campioni fra tutti gli $n$ campioni in ingresso $X=\{\mathbf{x}_1 , \ldots, \mathbf{x}_n \}$, con $s$ grande abbastanza per ricavare un modello (l'ipotesi). Ottenuta un'ipotesi, vengono contati quanti degli $n$ elementi di $X$ sono abbastanza vicini ad essa da esserne compatibili.

Un campione $\mathbf{x} \in X$ viene classificato come inlier oppure outlier rispetto all'ipotesi considerata se la sua distanza dal modello $d_{\boldsymbol\beta}(\mathbf{x})$ risulta rispettivamente inferiore o superiore a una soglia $\tau$, normalmente dipendente dal problema.

La soglia $\tau$ si scontra con quei problemi pratici in cui l'errore additivo è di tipo gaussiano e ha quindi supporto infinito. In questo caso è comunque necessario fissare una probabilità di classificazione degli inlier per determinare una soglia $\tau$.

Tutti i campioni che soddisfano l'ipotesi sono detti inlier rispetto all'ipotesi considerata.

L'insieme di tali inlier costituisce il consensus set associato all'ipotesi $\boldsymbol\beta$:

$$S(\boldsymbol\beta) = \left\{ \mathbf{x} \in X : d_{\boldsymbol\beta}(\mathbf{x}) < \tau \right\}$$ (4.140)

Tra tutti i modelli generati casualmente viene scelto il modello che massimizza una determinata metrica; nel RANSAC classico tale metrica è la cardinalità del consensus set.

Uno dei problemi è scegliere quante ipotesi generare per avere una buona probabilità di ottenere il modello corretto.

Esiste una relazione statistica tra il numero di iterazioni $N$ e la probabilità $p$ che almeno una delle ipotesi generate sia costituita esclusivamente da inlier. Il numero di tentativi $N$ deve soddisfare

$$(1-P)^N \le 1-p$$

ovvero

$$N \ge \frac{\log(1-p)}{\log(1-P)}$$ (4.141)

dove $P$ è la probabilità che un singolo campione casuale sia formato esclusivamente da inlier.

Normalmente come approssimazione di $P$ si può usare $P=(1-\epsilon)^s$^4.3 e perciò

$$N = \frac{\log(1-p)} {\log\!\left(1-(1-\epsilon)^s\right)}$$ (4.142)

con $\epsilon$ la probabilità a priori di selezionare un outlier e $s$ il numero di elementi necessari a definire il modello.

Assumendo nota la frazione di outlier $\epsilon$, il numero atteso di inlier presenti nel dataset è

$$T = (1-\epsilon)n.$$

Normalmente $s$ viene scelto uguale al numero minimo di elementi necessari per definire il modello. Qualora si scelga un valore maggiore, il modello deve essere stimato mediante una regressione numerica sui vincoli forniti. Questa strategia può risultare utile quando il rumore di osservazione è elevato, ma incrementa il rischio di includere nel campione anche degli outlier.

Footnotes

...#tex2html_wrap_inline15919#^4.3

La stima esatta è

$$P = \frac{\binom{n_i}{s}}{\binom{n}{s}},$$

dove $n_i$ è il numero totale di inlier, $n$ il numero totale di elementi e $s$ il numero di elementi necessari a definire il modello.