RANSAC
- Também chamado: Random Sample Consensus
- Categoria: Sensing › Perception outputs
- Tags: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
Random Sample Consensus: um método de ajuste robusto que ajusta repetidamente um modelo a pequenos subconjuntos aleatórios dos dados e mantém o modelo com que mais pontos concordam, ignorando os outliers.
Definição
RANSAC (Random Sample Consensus), introduzido por Fischler e Bolles em 1981, estima os parâmetros de um modelo a partir de dados que contêm muitos outliers. O ajuste por mínimos quadrados usa todos os pontos, então alguns erros grosseiros podem afastar muito o resultado da verdade. O RANSAC, em vez disso, repete um laço simples: sorteia o número mínimo de pontos necessário para definir o modelo (dois para uma reta, três para um plano, um pequeno número fixo para uma pose de câmera ou uma matriz fundamental), ajusta o modelo a eles e conta quantos de todos os pontos de dados ficam dentro de um limiar em relação a ele. Esses pontos são o conjunto de consenso, ou inliers. Depois de um número de iterações, o modelo com o maior conjunto de consenso é mantido e geralmente reajustado a todos os seus inliers por mínimos quadrados.
O número de iterações decorre da probabilidade. Se w é a fração de inliers e s o tamanho da amostra, uma amostra aleatória contém apenas inliers com probabilidade wˢ, então o número de iterações k necessário para sortear pelo menos uma amostra limpa com confiança p é k = log(1 − p) / log(1 − wˢ). Esse número cresce rapidamente quando a fração de inliers cai ou o tamanho da amostra aumenta, e é por isso que solucionadores mínimos que precisam de menos pontos, como o de pose relativa de cinco pontos, são importantes em visão. O limiar de inliers é o outro parâmetro-chave: ele deve corresponder ao ruído esperado dos inliers verdadeiros e precisa ser definido nas unidades do resíduo que está sendo medido.
Muitas variantes melhoram o laço básico. MSAC e MLESAC pontuam hipóteses com um custo robusto em vez de uma contagem bruta de inliers, PROSAC amostra primeiro as correspondências mais promissoras, LO-RANSAC refina localmente as boas hipóteses e versões adaptativas atualizam k à medida que a fração de inliers é estimada. Em robótica, o RANSAC é usado para segmentação de planos e primitivas em nuvens de pontos, filtragem de correspondências de features em odometria visual e SLAM, estimativa de pose Perspective-n-Point, registro de nuvens de pontos a partir de correspondências de features e calibração. Como o procedimento é aleatório, os resultados podem diferir entre execuções, a menos que a semente aleatória seja fixada.
Por que importa
Dados reais de sensores estão cheios de outliers: correspondências erradas de features, reflexos, objetos em movimento e pontos pertencentes a outras superfícies. O RANSAC é o modo padrão de ajustar modelos geométricos apesar deles, e está dentro da maioria dos pipelines de odometria visual, SLAM, calibração e segmentação de nuvens de pontos.
Principais aplicações
- Segmentação de planos, cilindros e esferas em nuvens de pontos
- Rejeição de outliers em correspondências de features em odometria visual e SLAM
- Estimativa de pose da câmera com Perspective-n-Point
- Estimativa de matrizes fundamentais, essenciais e de homografia
- Registro global de nuvens de pontos a partir de correspondências de features
- Ajuste de retas e modelos de calibração a dados ruidosos de sensores
Na prática
Um manipulador móvel precisa encontrar o tampo de uma mesa em uma nuvem de pontos de uma câmera de profundidade antes de colocar objetos. O software subamostra a nuvem e executa um ajuste de plano com RANSAC: sorteia repetidamente três pontos, calcula o plano que passa por eles e conta os pontos dentro de um limiar de distância definido um pouco acima do ruído de profundidade do sensor. O plano com mais inliers é reajustado por mínimos quadrados, seus inliers são removidos e os pontos restantes acima dele são agrupados em objetos. Os engenheiros verificam se a normal do plano aponta aproximadamente para cima, porque com uma parede ou um piso grande à vista o RANSAC pode devolver essa superfície no lugar, e fixam a semente aleatória nos testes para que os resultados sejam repetíveis.
Equívocos comuns
- O RANSAC encontra o modelo ótimo — ele devolve a melhor hipótese que por acaso amostrou, então os resultados são probabilísticos e podem diferir entre execuções
- Mais iterações compensam um limiar ruim — o limiar decide o que conta como concordância, e uma escolha ruim enviesa o resultado por mais iterações que se façam
- O RANSAC lida com qualquer proporção de outliers — as iterações necessárias crescem rapidamente à medida que a fração de inliers cai, e com pouquíssimos inliers ele pode falhar ou se fixar em uma estrutura espúria
- O RANSAC só consegue encontrar um modelo — o algoritmo básico encontra um, mas variantes sequenciais e multimodelo extraem várias estruturas removendo inliers e repetindo
Quem deve saber
- Engenheiros de percepção e de visão computacional
- Desenvolvedores de SLAM e de odometria visual
- Engenheiros que processam nuvens de pontos para manipulação
- Engenheiros de calibração e de metrologia
Tecnologias relacionadas
- Ajuste por mínimos quadrados (Least-Squares Fitting)
- M-estimadores (M-Estimators)
- MSAC e MLESAC
- PROSAC
- Transformada de Hough (Hough Transform)
- Point Cloud Library
Termos relacionados
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
Projetos relacionados
- 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
Vídeos
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision