RANSAC
- Detto anche: Random Sample Consensus
- Categoria: Sensing › Perception outputs
- Tag: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
Random Sample Consensus: un metodo di fitting robusto che adatta ripetutamente un modello a piccoli sottoinsiemi casuali dei dati e conserva il modello con cui concorda il maggior numero di punti, ignorando gli outlier.
Definizione
RANSAC (Random Sample Consensus), introdotto da Fischler e Bolles nel 1981, stima i parametri di un modello a partire da dati che contengono molti outlier. Il fitting ai minimi quadrati usa ogni punto, quindi pochi errori grossolani possono allontanare molto il risultato dal vero. RANSAC invece ripete un ciclo semplice: estrae il numero minimo di punti necessario a definire il modello (due per una retta, tre per un piano, un piccolo numero fisso per una posa della telecamera o una matrice fondamentale), adatta il modello a questi punti e conta quanti di tutti i punti dei dati si trovano entro una soglia da esso. Questi punti sono l'insieme di consenso, o inlier. Dopo un certo numero di iterazioni, si conserva il modello con l'insieme di consenso più grande, che di solito viene riadattato a tutti i suoi inlier ai minimi quadrati.
Il numero di iterazioni deriva dalla probabilità. Se w è la frazione di inlier e s la dimensione del campione, un campione casuale contiene solo inlier con probabilità wˢ, quindi il numero di iterazioni k necessario per estrarre almeno un campione pulito con confidenza p è k = log(1 − p) / log(1 − wˢ). Questo numero cresce rapidamente quando la frazione di inlier diminuisce o la dimensione del campione aumenta, ed è per questo che nella visione contano i risolutori minimi che richiedono meno punti, come quello a cinque punti per la posa relativa. La soglia per gli inlier è l'altro parametro chiave: deve corrispondere al rumore atteso dei veri inlier e va fissata nelle unità del residuo che si misura.
Molte varianti migliorano il ciclo di base. MSAC e MLESAC valutano le ipotesi con un costo robusto anziché con un semplice conteggio degli inlier, PROSAC campiona per prime le corrispondenze più promettenti, LO-RANSAC raffina localmente le ipotesi buone e le versioni adattive aggiornano k man mano che la frazione di inlier viene stimata. In robotica, RANSAC si usa per la segmentazione di piani e primitive nelle nuvole di punti, il filtraggio delle corrispondenze di feature nell'odometria visiva e nello SLAM, la stima della posa Perspective-n-Point, la registrazione di nuvole di punti da corrispondenze di feature e la calibrazione. Poiché la procedura è casuale, i risultati possono differire da un'esecuzione all'altra se il seed casuale non è fissato.
Perché è importante
I dati reali dei sensori sono pieni di outlier: corrispondenze di feature errate, riflessi, oggetti in movimento e punti appartenenti ad altre superfici. RANSAC è il modo standard per adattare modelli geometrici nonostante questi, ed è presente nella maggior parte delle pipeline di odometria visiva, SLAM, calibrazione e segmentazione di nuvole di punti.
Applicazioni principali
- Segmentazione di piani, cilindri e sfere nelle nuvole di punti
- Rigetto degli outlier nelle corrispondenze di feature per odometria visiva e SLAM
- Stima della posa della telecamera con Perspective-n-Point
- Stima di matrici fondamentali, essenziali e di omografia
- Registrazione globale di nuvole di punti da corrispondenze di feature
- Fitting di rette e modelli di calibrazione su dati rumorosi dei sensori
In pratica
Un manipolatore mobile deve trovare il piano di un tavolo in una nuvola di punti di una telecamera di profondità prima di posare degli oggetti. Il software sottocampiona la nuvola ed esegue un fitting di piano con RANSAC: sceglie ripetutamente tre punti, calcola il piano che passa per essi e conta i punti entro una soglia di distanza fissata poco sopra il rumore di profondità del sensore. Il piano con più inlier viene riadattato ai minimi quadrati, i suoi inlier vengono rimossi e i punti rimanenti sopra di esso vengono raggruppati in oggetti. Gli ingegneri verificano che la normale del piano punti all'incirca verso l'alto, perché con una parete o un pavimento grandi in vista RANSAC potrebbe restituire quella superficie, e nei test fissano il seed casuale così che i risultati siano ripetibili.
Idee sbagliate comuni
- RANSAC trova il modello ottimo — restituisce la migliore ipotesi che gli è capitato di campionare, quindi i risultati sono probabilistici e possono differire da un'esecuzione all'altra
- Più iterazioni compensano una soglia scelta male — la soglia decide che cosa conta come accordo, e una scelta sbagliata distorce il risultato per quante iterazioni si facciano
- RANSAC regge qualsiasi proporzione di outlier — le iterazioni necessarie crescono rapidamente al calare della frazione di inlier, e con pochissimi inlier può fallire o agganciarsi a una struttura spuria
- RANSAC può trovare un solo modello — l'algoritmo di base ne trova uno, ma le varianti sequenziali e multi-modello estraggono più strutture rimuovendo gli inlier e ripetendo
Chi dovrebbe saperlo
- Ingegneri di percezione e di visione artificiale
- Sviluppatori di SLAM e di odometria visiva
- Ingegneri che elaborano nuvole di punti per la manipolazione
- Ingegneri di calibrazione e di metrologia
Tecnologie correlate
- Fitting ai minimi quadrati (Least-Squares Fitting)
- M-stimatori (M-Estimators)
- MSAC e MLESAC
- PROSAC
- Trasformata di Hough (Hough Transform)
- Point Cloud Library
Termini correlati
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
Progetti correlati
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
- MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
- PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
- OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying
Video
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision