RANSAC

L'algoritmo di RANdom Sample And Consesus è un algoritmo iterativo per la stima dei parametri di un modello dove l'insieme dei dati è fortemente condizionato dalla presenza di molti outlier. È 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=\{\mathbf{x}_1 , \ldots, \mathbf{x}_n \}$, 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 $\mathbf{x} \in S$ appartiene o meno al modello (ovvero è un inlier o un outlier) se la sua distanza rispetto al modello $d_{\boldsymbol\beta} (\mathbf{x})$ è inferiore o superiore a una soglia data $\tau$, soglia normalmente dipendente dal problema. La soglia $\tau$ si scontra con quei problemi pratici dove l'errore additivo è di tipo gaussiano, ovvero dove il supporto è infinito. In questo caso è comunque necessario definire una probabilità $p$ di individuazione degli inlier per definire una soglia $\tau$.

Tutti gli elementi in ingresso che soddisfano l'ipotesi si chiamano consensi (consensus).

L'insieme dei consensi $S$ associati all'ipotesi $\boldsymbol\beta$ è il consensus set di $\boldsymbol\beta$:

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

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à massima.

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$ di individuare una soluzione di soli inlier. Il numero di tentativi $N$ deve soddisfare $(1 - P)^N \le 1 - p$ ovvero

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

dove $P$ è la probabilità di avere scelto una soluzione fatta solamente di inlier.

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

$$N = \frac{ \log ( 1 - p ) } { \log ( 1 - (1 - \epsilon )^{s} ) }$$ (3.117)

con $\epsilon$ la probabilità a priori di outlier e $s$ il numero di punti necessari a definire un modello. La dimensione di un consensus set minimo può essere dedotta in via statistica semplicemente come $T = (1 - \epsilon) 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 è elevata, incrementando tuttavia il rischio di inglobare nei vincoli anche outliers.

Footnotes

...#tex2html_wrap_inline9765#^3.3

Una relazione non approssimata sarebbe $P=\frac{\binom{pn}{s}}{\binom{n}{s}}$ con $pn$ numero totale di inlier e $n$ numero totale di elementi.