Open Source Robotics

Uma coleção selecionada de projetos, ferramentas e software de robótica de código aberto de alta qualidade.

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

Este site requer JavaScript. Por favor, habilite o JavaScript para explorar nossos projetos de robótica.