Scan Matching
- Também chamado: scan registration, point cloud registration
- Categoria: State estimation & navigation › Localisation
- Tags: lidar, localization, slam, point-clouds, registration
Estimar a transformação rígida que alinha uma varredura de distâncias com outra varredura ou com um mapa; usado em odometria LiDAR, localização e SLAM para transformar dados brutos de distância em estimativas de pose.
Definição
Alinhamento de varreduras (scan matching) pega uma nova varredura de distâncias de um LiDAR, sonar ou sensor de profundidade e encontra a rotação e a translação que melhor a alinham com uma referência: a varredura anterior, um mapa local recente ou um mapa global. A transformação resultante é uma medição de como o sensor se moveu ou de onde ele está. É a operação central da odometria LiDAR, da localização baseada em mapa de robôs com rodas e dos front-ends da maioria dos sistemas de SLAM com LiDAR. O alinhamento varredura a varredura é simples, mas acumula deriva rapidamente; o alinhamento varredura a mapa alinha cada nova varredura com um mapa acumulado, o que reduz a deriva e torna a estimativa menos sensível a varreduras individuais esparsas.
Há várias famílias de métodos. Métodos baseados em pontos, como o Iterative Closest Point (ICP) e suas variantes ponto a plano e generalizada, alternam entre encontrar correspondências e resolver a transformação. A transformada de distribuições normais (NDT), introduzida por Biber e Straßer (2003), representa a referência como uma grade de distribuições gaussianas locais e maximiza a verossimilhança da nova varredura sob elas. O alinhamento correlativo de varreduras, descrito por Olson (2009), busca sobre um conjunto discretizado de poses em relação a uma grade de probabilidade, o que tolera estimativas iniciais ruins. Métodos baseados em características, popularizados pelo LOAM (Zhang e Singh, 2014), extraem pontos de borda e planares e os casam com linhas e planos do mapa, reduzindo o custo computacional. Alinhadores 2D baseados em grade também estão no centro de pacotes de SLAM a laser como Hector SLAM e Cartographer.
A maioria dos alinhadores de varreduras converge apenas localmente e precisa de uma estimativa inicial razoável, geralmente da IMU, da odometria de rodas ou de um modelo de velocidade constante. Eles falham em situações previsíveis: corredores longos, túneis e campos abertos onde a geometria restringe mal algumas direções; objetos em movimento que parecem estrutura; e distorção de movimento quando o sensor se move durante uma única varredura, que precisa ser corrigida removendo a distorção dos pontos com dados da IMU. Bons sistemas inspecionam a hessiana ou a covariância de cada alinhamento para detectar direções fracamente restringidas e ponderam o resultado de acordo ao fundi-lo com outros sensores.
Por que importa
Sensores de distância fornecem geometria precisa, mas nenhuma pose direta. O alinhamento de varreduras é a forma como essa geometria se torna estimativas de movimento e de posição, por isso sua precisão e seus modos de falha determinam em grande parte o desempenho da navegação baseada em LiDAR.
Principais aplicações
- Odometria LiDAR e SLAM
- Localização de robôs de armazém e de serviço em relação a um mapa prévio
- Verificação de candidatos a fechamento de loop entre varreduras distantes
- Alinhamento de varreduras para mapeamento 3D e levantamento topográfico
- Calibração extrínseca entre vários LiDAR
Na prática
Em um robô terrestre com um LiDAR 3D giratório, cada varredura primeiro tem sua distorção removida usando a rotação medida pela IMU, e depois são extraídos pontos característicos de borda e planares. Partindo da pose prevista pela IMU, as características do quadro-chave atual são alinhadas a um mapa de características construído a partir de quadros-chave anteriores, e a transformação resolvida entra no estimador como um fator de odometria LiDAR, como em sistemas LiDAR-visual-inerciais como o LVI-SAM. Em um corredor longo e sem características marcantes, o alinhamento restringe apenas fracamente o movimento ao longo do eixo do corredor, por isso a equipe verifica os autovalores da hessiana do alinhamento e deixa as medições da IMU e visuais sustentarem essa direção até que a geometria melhore.
Equívocos comuns
- Alinhamento de varreduras e ICP são a mesma coisa — o ICP é um algoritmo de alinhamento de varreduras entre vários, ao lado dos métodos NDT, correlativos e baseados em características
- Um bom alinhador de varreduras funciona sem estimativa inicial — a maioria dos métodos converge apenas localmente e precisa de uma pose prévia vinda da odometria ou de uma IMU
- O alinhamento de varreduras restringe todas as direções igualmente — em corredores, túneis e áreas abertas, a geometria pode deixar algumas direções quase sem restrição
Quem deve saber
- Engenheiros de SLAM com LiDAR e de localização
- Desenvolvedores de navegação de robôs móveis
- Equipes de percepção de veículos autônomos
- Engenheiros de levantamento topográfico e mapeamento
Tecnologias relacionadas
- Normal Distributions Transform (NDT)
- Generalized ICP
- LOAM
- Cartographer
- Point Cloud Library (PCL)
- KISS-ICP
Termos relacionados
Projetos relacionados
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- oomwoo: Open-source DIY robot vacuum: 3D-printed, ROS2 + 2D LiDAR, fully local.
- PCL: Industry-standard C++ library for point cloud processing in robotics perception
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
Vídeos
- SLAM Course - 12 - Scan-Matching in 5 Min - Cyrill Stachniss: Cyrill Stachniss