Mapeamento Robótico 2,5-D com Representação em Grade de …€¦ · rei; bendirei o teu nome para todo sempre! Todos os dias te bendirei e louvarei o teu nome para todo sempre!

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E

DE COMPUTAÇÃO

Mapeamento Robótico 2,5-D comRepresentação em Grade de

Ocupação-Elevação

Anderson Abner de Santana Souza

Orientador: Prof. Dr. Luiz Marcos Garcia Gonçalves

Tese de Doutoradoapresentada ao Pro-grama de Pós-Graduação em EngenhariaElétrica e de Computação da UFRN (área deconcentração: Engenharia de Computação)como parte dos requisitos para obtenção dotítulo de Doutor em Ciências.

Número de ordem PPgEE: D74Natal, RN, Agosto de 2012

UFRN / Biblioteca Central Zila Mamede

Catalogação da Publicação na Fonte.

Souza, Anderson Abner de SantanaMapeamento robótico 2,5-D com representação em grade de ocupação-

elevação/ Anderson Abner de Satana Souza - Natal, RN, 2012109 f.:il

Orientador: Luiz Marcos Garcia Gonçalves

Tese (Doutorado) - Universidade Federal do Rio Grande do Norte. Centrode Tecnologia. Programa de Pós-Graduação em Engenharia Elétrica e de Com-putação.

1. Inteligência artificial - Mapeamento - Tese. 2. Grade de ocupação-elevação- Computação - Tese. 3. Visão estéreo - Computação - Tese. 4. Modelagemprobabilística - Computação - Tese. 5. Robótica - Tese. I. Gonçalves, LuizMarcos Garcia. II. Universidade Federal do Rio Grande do Norte. III. Título.

RN/UF/BCZMCDU 004.896

Mapeamento Robótico 2,5-D comRepresentação em Grade de

Ocupação-Elevação

Anderson Abner de Santana Souza

Tese de Doutorado aprovada em 03 de agosto de 2012 pela banca examinadora compostapelos seguintes membros:

Prof. Dr. Luiz Marcos Garcia Gonçalves (orientador) . . . . . .. . . . . . . . . . . UFRN

Prof. Dr. Pablo Javier Alsina . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . UFRN

Prof. Dr. Diogo Fernandes Pedrosa . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . UFRN

Prof. Dr. Flávio Tonidandel . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . FEI

Prof. Dr. André Macedo Santana . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . UFPI

“Eu te exaltarei, meu Deus e meurei; bendirei o teu nome para todo

sempre! Todos os dias te bendirei elouvarei o teu nome para todo

sempre! Grande é o Senhor e dignode ser louvado; sua grandeza não

tem limites.” Sl. 145.1-3

Agradecimentos

Ao Senhor criador de todas as coisa por ser o meu constante ajudador e sustentador.“Todas as coisas foram feitas por ele, e sem ele nada do que foifeito se fez”. Toda honrae glória ao Deus supremo.

Agradeço aos meus pais Marlene e Abdênego pelo grande incentivo, apoio e orações, queforam e são de fundamental importância para alcançar os objetivos da minha vida. Porme ensinar o verdadeiro caminho a ser trilhado na busca de umavida justa e íntegra.

Não posso deixar de agradecer a minha preciosa e amável esposa Verónica, por sempreme inspirar e incentivar, mesmo quando isso significava renunciar momentos juntos. Sougrato pelas sua orações e súplicas diante do nosso Deus, pedindo-lhe forças para tornar-me um vencedor.

Aos meus irmãos Afrânio e Andressa, pessoas importantíssimas na minha vida.

Ao meu orientador, professor Dr. Luiz Marcos Garcia Gonçalves, sou grato pelas orien-tações, conselhos e ensinamentos. Pelo apoio e incentivo para que essa valiosa conquistana minha formação fosse alcaçada.

Sou grato ao meu grande amigo e companehiro de trabalho AndréMacedo, à compan-heira de doutorado Rosiery pelos conselhos e incentivo, e aosdemais companheiros dolaboratório NatalNet.

Deixo o meu muito obrigado a todos que direta ou indiretamente participaram dessa con-quista. Que Deus os recompense grandemente.

Resumo

Este trabalho apresenta um novo método de mapeamento de ambientes com robôsmóveis com informações tridimensionais para navegação. Muitas abordagens de mapea-mento 3D, usam o método em grade de ocupação, o que resulta no uso de muito recursocomputacional tanto na construção como no armazenamento desses mapas. A presentepesquisa apresenta o mapeamento 2,5-D em grade de ocupação-elevação, a qual é definidacomo uma representação discreta, onde cada célula armazenauma probabilidade de ocu-pação, a altura do espaço mapeado e a variância desse valor dealtura.

Essa representação permite que um robô móvel tenha a ciênciase um lugar do seuambiente está ocupado por um obstáculo e qual a altura desse obstáculo. Dessa forma,ele pode decidir se é possível navegar sobre o obstáculo ou não, de acordo com suashabilidades motoras. As informações sensoriais necessárias para construir o mapa sãoprovidas por um sistema de visão estéreo, o qual foi modeladoatravés de uma robustaanálise estatística, considerando os ruídos presentes no processamento estéreo. Os mapasresultantes favorecem a execução de tarefas como tomadas dedecisões na navegaçãoautônoma, exploração, localização e planejamento de caminhos. Experimentos práticosreais mostram que o método de mapeamento apresentado é útil para a navegação de robôsautônomos.

Palavras-chave: Grade de Ocupação-Elevação. Visão Estéreo, Modelagem Proba-bilística.

Abstract

This work introduces a new method for environment mapping with three-dimensionalinformation from visual information for robotic accurate navigation. Many approachesof 3D mapping using occupancy grid typically requires high computacional effort to bothbuild and store the map. We introduce an 2.5-D occupancy-elevation grid mapping, whichis a discrete mapping approach, where each cell stores the occupancy probability, theheight of the terrain at current place in the environment andthe variance of this height.

This 2.5-dimensional representation allows that a mobile robot to know whether aplace in the environment is occupied by an obstacle and the height of this obstacle, thus,it can decide if is possible to traverse the obstacle. Sensorial informations necessary toconstruct the map is provided by a stereo vision system, which has been modeled witha robust probabilistic approach, considering the noise present in the stereo processing.The resulting maps favors the execution of tasks like decision making in the autonomousnavigation, exploration, localization and path planning.Experiments carried out with areal mobile robots demonstrates that this proposed approach yields useful maps for robotautonomous navigation.

Keywords: 2.5-D Occupancy-Elevation Grid, Stereo Vision, Probabilistic Modeling.

Sumário

Sumário i

Lista de Figuras iii

Lista de Tabelas v

1 Introdução 11.1 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Motivação e Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . .61.3 Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Produções Científicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Mapeamento 112.1 O Problema do Mapeamento Robótico . . . . . . . . . . . . . . . . . . . 112.2 Desafios do problema de mapeamento robótico . . . . . . . . . . .. . . 12

2.2.1 Imprecisões sensoriais . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Dimensionalidade . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.3 Associação de dados -Matching . . . . . . . . . . . . . . . . . . 142.2.4 Dinamicidade do ambiente . . . . . . . . . . . . . . . . . . . . . 142.2.5 Estratégia de exploração . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Tipos de Representações . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.1 Mapas Topológicos . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.2 Mapas Métricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.3 Mapas topológicos vs. Mapas métricos - Vantagens e Desvantagens 192.3.4 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . 20

3 Mapeamento Visual 233.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Configurações de Câmeras mais Utilizadas no Mapeamento Visual . . . . 24

3.2.1 Visão Monocular . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2.2 Visão Estéreo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Estereoscopia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3.1 Geometria Estéreo e Reconstrução 3D . . . . . . . . . . . . . . . 263.3.2 Disparidade Estéreo . . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

i

4 Grade de Ocupação e Mapas de Elevação 334.1 Grade de Ocupação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.1 Modelo Probabilístico do Sensor . . . . . . . . . . . . . . . . . .354.1.2 Algoritmo de Mapeamento em Grade de Ocupação . . . . . . . .374.1.3 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . 38

4.2 Mapas de Elevação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.1 Filtro de Kalman . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . 45

4.3 Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Grade de Ocupação-Elevação 475.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.2 Definição - Grade de Ocupação-Elevação . . . . . . . . . . . . . . .. . 48

5.2.1 Etapas do Mapeamento em Grade de Ocupação-Elevação . .. . . 505.3 Posicionamento - Modelagem Cinemática . . . . . . . . . . . . . . .. . 525.4 Aquisição e Interpretação de Dados Sensoriais . . . . . . . .. . . . . . . 54

5.4.1 Aquisição de Imagens . . . . . . . . . . . . . . . . . . . . . . . 545.4.2 Calibração Estéreo . . . . . . . . . . . . . . . . . . . . . . . . . 555.4.3 Retificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.4.4 Correspondência Estéreo . . . . . . . . . . . . . . . . . . . . . . 565.4.5 Cálculo das Coordenadas dos Pontos Detectados . . . . . . . .. 56

5.5 Modelagem Sensorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.5.1 Modelagem Sensorial para Estimar o Valor de Ocupação .. . . . 575.5.2 Modelagem Sensorial para Estimar o Valor de Elevação .. . . . 595.5.3 Modelagem das Incertezas e Ruídos Sensoriais . . . . . . . .. . 60

5.6 Integração de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.6.1 Integração dos Valores de Ocupação . . . . . . . . . . . . . . . .635.6.2 Integração dos Valores de Elevação . . . . . . . . . . . . . . . .635.6.3 Definição do Campo Visual de Células Atualizáveis . . . . . .. 64

5.7 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6 Experimentos e Resultados 676.1 Visão Geral do Sistema Robótico . . . . . . . . . . . . . . . . . . . . . .676.2 Calibração Estéreo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.3 Estimativa das Incertezas Visuais . . . . . . . . . . . . . . . . . .. . . . 696.4 Tratamento de Incoerências no Valor de Elevação . . . . . . .. . . . . . 706.5 Experimento em Ambiente Interno . . . . . . . . . . . . . . . . . . . .. 726.6 Experimento em Ambiente Externo . . . . . . . . . . . . . . . . . . . .756.7 Experimento em Ambiente Misto . . . . . . . . . . . . . . . . . . . . . .766.8 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816.9 Análise Geral dos Resultados . . . . . . . . . . . . . . . . . . . . . . . .81

7 Conclusão e Perspectivas 83

Referências bibliográficas 85

Lista de Figuras

1.1 Diagrama hierárquico do processo de navegação. . . . . . . .. . . . . . 21.2 Processo de contrução do mapa em grade de ocupação-elevação. . . . . . 5

2.1 Grafico de composição do mapeamento. . . . . . . . . . . . . . . . . .. 122.2 Mapa corrompido por erros de odometria. . . . . . . . . . . . . . .. . . 132.3 Mapa corrompido por erros de odometria. . . . . . . . . . . . . . .. . . 142.4 O problema da exploração é a integração do Mapeamento como Planeja-

mento de caminhos [Stachniss 2009]. . . . . . . . . . . . . . . . . . . . 152.5 Mapemento topológico. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.6 Representação de uma medição de um sonar em uma grade de ocupação. . 182.7 Construção de um mapa de características a partir da detecção de retas. . . 19

3.1 Câmeras monoculares. . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 Câmeras estereoscópicas: (a) câmeras binocular e trinocular; (b) câmera

ominidirecional. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.3 Geometria estéreo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.4 Mapa de disparidade gerado pelo algoritmo de janela variável; (a) imagem

original; (b) mapa de disparidade. . . . . . . . . . . . . . . . . . . . . .293.5 Mapa de disparidade gerado pelo algoritmo degraph-cuts; (a) imagem

original; (b) mapa de disparidade. . . . . . . . . . . . . . . . . . . . . .30

4.1 Gráfico da Distribuição Normal. . . . . . . . . . . . . . . . . . . . . .. 364.2 Modelo de medição sensorial. Valores de ocupação para medições de

20m, 30m e 40m. O valor de ocupação se dá com as médias (medidas) evariâncias (erros) das medições. . . . . . . . . . . . . . . . . . . . . . .37

4.3 Modelagem Gaussiana bidimensional de um sensor. . . . . . .. . . . . . 374.4 Ilustração da representação em grade de ocupação 3D. . . .. . . . . . . 424.5 Representação em grade de ocupação 2.5D. É necessária umaestrutura

de dados de 72 elementos para mapear o ambiente ilustrado. . .. . . . . 43

5.1 Formação da grade de ocupação-elevação. . . . . . . . . . . . . .. . . . 495.2 Etapas do mapeamento em grade de ocupação-elevação. . . .. . . . . . 515.3 Modelagem cinemática de movimento. . . . . . . . . . . . . . . . . .. . 535.4 Câmera estéreo Minoru 3D utilizada no mapeamento. . . . . . .. . . . . 545.5 Processo de retificação estéreo. . . . . . . . . . . . . . . . . . . . .. . . 555.6 Construção do mapa de disparidade. . . . . . . . . . . . . . . . . . . .. 56

iii

5.7 Modelo inverso do sensor aplicado ao cálculo de ocupaçãoparalp = 10me lp = 15m. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.8 Referenciais de coordenadas envolvido no mapeamento. . .. . . . . . . 595.9 Comportamento do modelo sensorial para o cálculo de elevação de uma

célula, levando em consideração as incertezas, para uma madiçãoht = 2m,com distânciaslp = 1m, lp = 2m e lp = 3m, σt = 0.032m, σt = 0.13m eσt = 0.28m, respectivamente. . . . . . . . . . . . . . . . . . . . . . . . . 60

5.10 O efeito de escorço da superfície não paralelaSé diferente para as duascâmeras: a projeção deSnos planos de imagens tem comprimentos difer-entesl l e lr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.11 Desalinhamento vertical dos planos de imagens. . . . . . .. . . . . . . . 62

6.1 Plataforma robótica utilizada nos experimentos. . . . . .. . . . . . . . . 686.2 Cena de uma possível passagem: (a) Mesa de computador; (b)Imagem

capturada pela câmera do robô; (c) Mapa de disparidade estimado. . . . . 706.3 Mapas estimados: (a) Valores de ocupação; (b) valores deelevação sem

heurística; (c) valores de elevação com heurística. . . . . . .. . . . . . . 716.4 Cenas visualizadas pelo robô durante o mapeamento: (a) Visão do corre-

dor e armários presentes; (b) Portão gradeado; (c) Terminalde consultas. . 726.5 Vistas superiores do ambiente: (a) Visão superior do prédio explorado a

partir doGoogle Earthcom latitude -5.842853 e longitude -35.197341;(b)Planta baixa do corredor mapeado. . . . . . . . . . . . . . . . . . . .73

6.6 Mapeamento em grade de ocupação-elevação para o ambiente interno.(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das ele-vações. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.7 Imagens capturadas pelo robô durante o mapeamento. . . . .. . . . . . . 766.8 Ambiente externo mapeado: (a) Visão superior do ambiente, limitado

pelo retângulo em amarelo (visão do Google Earth) de latitude -5.842677e longitude -35.19724; (b) Planta baixa. . . . . . . . . . . . . . . . .. . 77

6.9 Mapeamento em grade de ocupação-elevação para o ambiente externo:(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das ele-vações. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.10 Vista superior do ambiente mapeado: (a) vista do GoogleEarth de latitude-5.842677 e longitude -35.19724; (b) Planta baixa. . . . . . . .. . . . . 79

6.11 Diferentes cenas encontradas durante o mapeamento: (a) e (b) Cenas deambiente interno. (c) e (d) Cenas de ambiente externo. . . . . . .. . . . 79

6.12 Resultado do mapeamento do ambiente misto: (a) Valores de ocupação;(b) Valores de elevação.(c) Variância das elevações. . . . . .. . . . . . . 80

Lista de Tabelas

6.1 Comparação de requisitos de memória. . . . . . . . . . . . . . . . . .. . 81

v

Capítulo 1

Introdução

A robótica vem se destacando como uma das áreas das ciências exatas de mais rá-pida evolução. Com o objetivo de conceber máquinas (os robôs)que auxiliem ou mesmosubstituam os homens em tarefas repetitivas, fastidiosas,de grande precisão e perigosas,a robótica vem sendo explorada com grande empolgação por cientistas de todo mundo.Thrun et al. (2005) definem, de uma maneira mais formal, a Robótica como sendo aciência de perceber e manipular o mundo físico através de dispositivos controlados com-putacionalmente.

Pode-se dividir a robótica em duas grandes categorias: a robótica de manipuladores ea robótica móvel. O objetivo principal da robótica de manipuladores é desenvolver braçosrobóticos, que emulam os movimentos dos braços humanos. Tais robôs são aplicadosprincipalmente nas indústrias, com destaque maior para as linhas de montagens automo-bilísticas. Porém, apesar do seu grande sucesso, os robôs manipuladores possuem umadesvantagem fundamental: falta de mobilidade. Um manipulador tem uma região limi-tada de trabalho que depende de onde está fixado [Siegwart & Nourbakhsh 2004]. Poroutro lado, a robótica móvel trata com robôs que possuem a habilidade de se locomover,isto é, robôs móveis que podem trafegar através de um ambiente, o que flexibiliza a at-uação destes. A robótica móvel é constituída pela classe dosrobôs terrestres, aéreos,subaquáticos e robôs híbridos (capazes de se movimentar em diferentes espaços).

Aliando a capacidade de locomoção dos robôs móveis com recursos computacionais,poder de comunicação de dados, capacidade de percepção (sensores), entre outros, é pos-sível empregá-los em diversos tipos de aplicações práticas. Como ilustração, pode-se citaraplicações domésticas (por exemplo, aspiradores de pó e cortadores de grama), industri-ais (por exemplo, transporte automatizado), urbanas (por exemplo, transportes públicos,cadeiras de rodas robotizadas), militares (por exemplo, sistemas de monitoramento aéreoremoto, transporte de suprimentos e de armazenamento em zonas de guerra, sistemas táti-cos de e combate), de segurança e defesa civil, e militar (porexemplo, patrulhamentode ambientes, resgate e exploração em ambientes hostis, combate a incêndios) [Wolfet al. 2009]. Assim, fica clara a importância de se investir empesquisas para o desen-volvimento desta área tão promissora.

Um dos grandes desafios para a comunidade dos roboticistas é fazer com que os robôsmóveis executem suas tarefas de forma eficiente e segura com omínimo de interferênciahumana, isto é, que sejam autônomos. Para isso, o sistema robótico deve apresentar

2 CAPÍTULO 1. INTRODUÇÃO

características importantes. A primeira delas é a capacidade depercepção, onde atravésde sensores, o robô deve perceber o ambiente no qual esta inserido. Como segunda ca-racterística o robô deve ser capaz deagir por meio de atuadores e motores, que o habilitama produzir ações tais como deslocamento. Por fim, um robô autônomo deve apresentarrobusteze inteligênciapara lidar com as mais diversas situações, de modo a resolvereexecutar tarefas, por mais complexas que sejam [Wolf et al. 2009].

Analisando essas características fundamentais, pode-se entender que um robô móvelautônomo deve ser capaz de se locomover no seu ambiente de trabalho partindo de umaconfiguração inicial até alcançar uma configuração final, guiando-se por um determinadocaminho planejado, de forma segura, ou seja, desviando-se de obstáculos, e obedecendoàs restrições temporais impostas para o cumprimento dessa tarefa. Isto é, o robô deveestar apto anavegarno seu ambiente de trabalho. O processo de navegação pode sersubdividido em etapas hierarquizadas (Figura 1.1) que devem ser seguidas e executadas:Mapeamento de Ambientes, Localização, Planejamento de Caminho, Geração de Tra-jetória e Execução de Trajetória [Alsina et al. 2002].

Mapeamentode

Ambientes

Localização

Planejamentode

Caminho

Geraçãode

Trajetória

Execuçãode

Trajetória

Figura 1.1: Diagrama hierárquico do processo de navegação.

3

• Mapeamento de Ambientes - percepção e construção de um modelo do ambiente apartir de informações sensoriais;

• Localização - baseando-se do modelo obtido na etapa anterior juntamente com in-formações sensoriais extras, é deduzida a pose do robô dentro do ambiente;

• Planejamento de Caminho - o robô calcula um caminho partindo de sua configu-ração inicial até a configuração final desejada, evitando obstáculos;

• Geração de Trajetória - o caminho gerado é adaptado às restrições temporais e en-tão é calculada a velocidade com que se deseja movimentar;

• Execução da Trajetória - os atuadores são controlados de forma a executarem atrajetória gerada o mais fielmente possível.

No nível de mapeamento de ambientes, o robô deve coletar dados do seu entorno,utilizando sensores, visando gerar modelos computacionais com as principais caracterís-ticas estruturais do ambiente. Para isso, é necessário que os robôs sejam equipados comdispositivos de percepção capazes de fornecer algum tipo deinformação de seu entorno,de modo que, a partir de algum processamento, essas informações sejam empregadas naconstrução de um mapa do ambiente. Além disso, para que um sistema robótico possaconstruir um mapa consistente, é necessário determinar suapose (posição e orientação)com relação a algum referencial fixo no mundo. Esse processo de obtenção de dados sen-soriais, seu subsequente processamento mais a inferência da pose do robô, tendo comoobjetivo a construção de um mapa do espaço no qual o robô está inserido, é chamado demapeamento robótico.

O mapeamento pode ser realizado em diferentes tipos espaços, seja em ambientes in-ternos (indoor), ambientes externos (outdoor), ambientes subterrâneos e ambientes sub-aquáticos. Quanto à utilização, os mapas construídos podemser considerados na re-alização de diversas tarefas, desde as mais simples, tais como, desvio de obstáculos,planejamento de caminhos e localização, às tarefas de maiorcomplexidade, por exem-plo, exploração de minas subterrâneas, de instalações nucleares, limpeza de ambientestóxicos, combate a incêndios e resgate de suas vítimas, entre outras atividades de maiordificuldade. Os robôs de diferentes capacidades motoras podem utilizar-se de mapas pararealizar tais missões, por exemplo, Dryanovski et al. (2010) utilizaram um micro veículoaéreo para mapear ambientes para fins de localização e planejamento de caminho. Notrabalho de Marjovi et al. (2009) foi desenvolvido um time derobôs terrestres que uti-lizam um mapa para exploração e detecção de fogo em um ambiente. Já no trabalho deJohannsson et al. (2010) um algoritmo de mapeamento foi implementado em um robôsubaquático com o objetivo de aplica-lo em vigilância de portos e inspeções de casco denavios.

As primeiras pesquisas mais aprofundadas na linha de mapeamento robótico forampublicadas no fim dos anos 1980, quando foram divulgados os primeiros estudos com re-sultados relevantes sobre o assunto. Nesse período, váriasformas de mapeamento forampropostas, empregando diversas estruturas geométricas e topológicas, com o intuito de se


obter a melhor precisão possível na representação do ambiente, sempre com a preocu-pação de lidar com a alta dimensionalidade dos espaços.

No ano de 2002, Thrun (2002) propôs uma classificação para as representações emmapeamento robótico, segundo duas abordagens principais:a abordagem métrica e atopológica. Enquanto os mapas da abordagem métrica armazenam propriedades ge-ométricas do ambiente, os mapas da abordagem topológica descrevem a conectividadeentre diferentes compartimentos do espaço mapeado. Essa classificação é a mais adotadaaté hoje, entretanto, uma variação sutil da abordagem métrica, acrescentando a classe demapas baseados em características aparece em alguns trabalhos.

Diversos tipos de sensores podem ser utilizados no mapeamento robótico. Os maiscomuns são os sonares, os lasers e as câmeras. Os sonares são atrativos por conta docusto, são sensores relativamente baratos e podem ser facilmente encontrados no mercado.Entretanto, apresentam imprecisões significativas nas suas medições. Os lasers, por outrolado, são altamente precisos e propiciam a aquisição de mapas bem detalhados. Mas,devido o seu elevado custo monetário deixam de ser atrativos. As câmeras são sensoresque a cada dia estão ficando mais baratos e possibilitam a aquisição de grande quantidadede dados no entorno do robô. Por esses motivos, as câmeras estão alcançando um papelde destaque dentre os sensores mais utilizados para mapeamento robótico.

No próximo capítulo o problema do mapeamento robótico será apresentado com maiorprofundidade, no qual o problema será mais bem fundamentadocom sua formalização, esuas principais características serão exploradas.

1.1 Contribuições

O presente trabalho propõe um método de mapeamento robóticode ambientes inter-nos e/ou externos, baseado em um sistema de visão com câmerasestéreo usando umarepresentação inspirada em uma abordagem métrica probabilística do ambiente mapeadoatravés de grade de ocupação com informações tridimensionais (mapa 2,5-D), chamadade grade de ocupação-elevação. Com o sistema de visão estéreo, o robô pode coletarinformações de diferentes lugares com variados tipos de obstáculo, não ficando depen-dente do tipo de ambiente em que se encontra, tampouco do tipode características queeste lugar possui. O algoritmo de mapeamento proposto considera uma modelagem prob-abilística para o sistema de visão utilizado pelo robô, bem como para os movimentosrealizados pelo mesmo. Com isso, os resultados obtidos (os mapas) estarão coerentescom as informações sensoriais colhidas pelo robô.A Figura 1.2 ilustra de forma simplifi-cada o processo proposto de construção do mapa em grade de ocupação-elevação, onde apartir dos dados processados e interpretados do sistema de visão, integrados com a pose(coordenadas e orientação) do robô estimada, o mapa em gradeé construído.

Por meio de uma modelagem probabilística do problema de mapeamento, as incertezasrelacionadas aos movimentos do sistema robótico e as imprecisões inerentes ao sistemade percepção serão tratadas de forma adequada. O processo demodelagem de ambientesem grade de ocupação-elevação torna o mapeamento independente de quais estruturas

1.1. CONTRIBUIÇÕES 5

Modelo deOdometria

Imagem direita

Cálculo Estéreo

Imagem esquerda

Mapa deDisparidade

CâmeraEstéreo

Robô

Coordenadas (x, y)Orientação ( )θ

Grade deOcupação-Elevação

Figura 1.2: Processo de contrução do mapa em grade de ocupação-elevação.

estão presentes no espaço de trabalho do robô, diferente de outros tipos de mapas, quedependem, por exemplo, detecção de características ou marcos presentes no ambiente.

Além disso, com as informações 3D o robô terá condições de identificar obstáculospossíveis de serem transpassados ou não. Cada célula que compõe o mapa em grade deocupação-elevação tem armazenada, por meio de técnicas probabilísticas, informações deocupação e altura dos obstáculos. Com isso, o robô pode identificar se um determinadolocal do ambiente está ocupado por um obstáculo e se o mesmo pode ser superados.

Com o mapa construído a partir da abordagem aqui apresentada,o robô será capazde utilizá-lo para realizar diferentes tarefas, desde as mais simples e diretas como, lo-calização, exploração, planejamento de caminhos, à tarefas de maior complexidade, porexemplo, limpeza de lixos tóxicos, regates de vítimas de desastres, combate a incêndios,exploração de minas subterrâneas, entre outras.


Assim, pode-se destacar como contribuições principais a modelagem probabilísticado sensor utilizado, no caso um sistema de visão estéreo, de modo que o mapa adquiridopossa representar com fidelidade as informações capturadase também a construção de ummapa em grade de ocupação probabilística com informações 3D, sem a necessidade deuma estrutura de dados tridimensional (mapa 2,5-D, aqui chamado de grade de ocupação-elevação), que seria custosa computacionalmente.

Diferente das abordagens existentes na literatura, cada célula do mapa gerado terá umvalor da probabilidade de ocupação, terá uma estimativa da altura dos obstáculos e davariância da altura, indicando sua acurácia. Deste modo, pode-se identificar obstáculospossíveis de serem superados a partir do mapa de ocupação-elevação construído, con-siderando os erros inerentes ao sistema perceptivo robô, osquais são modelados por meiode técnicas probabilísticas,

1.2 Motivação e Justificativa

Uma das etapas capitais do problema de navegação inteligente consiste no mapea-mento de ambientes. Esta fase requer que o robô esteja munidode sensores que o habilitea construir uma descrição espacial do ambiente no qual está inserido, a partir de infor-mações desses sensores. De posse da descrição espacial ou mapa construído o robô écapaz de interagir de forma coerente com seu ambiente, realizando uma navegação efi-ciente e agindo de modo flexível frente a situações inesperadas. Assim, o robô poderárealizar diferentes tipos de tarefas de forma inteligente esem a interferência humana,por exemplo, planejamento de caminhos, exploração, manipulação de objetos, resgates,limpeza de ambientes contaminados, entre outras.

Entre as maneiras mais difundidas de representação de ambientes mapeados está agrade de ocupação, proposta inicialmente por Elfes (1987),que modela o estado de ocu-pação de um ambiente. Nesta abordagem o mapa é representado por uma matriz de célu-las, que podem estar ocupadas, livres ou pode não ter sido mapeadas. Através dessaabordagem é possível representar o ambiente mapeado de forma relativamente precisa.Além disso, os mapas em grade de ocupação facilitam a aplicação direta de algoritmos deplanejamento de caminhos, de exploração, de desvio de obstáculo e de localização. Emanos posteriores, alguns pesquisadores propuseram a expansão da grade de ocupação parao mapeamento tridimensional dos ambientes, aplicando-o, principalmente, para os casosonde o terreno de navegação dos robôs não é plano, e nos casos onde é necessário queseja realizada uma navegação precisa entre os objetos, considerando a altura deles dentrodo ambiente [Moravec 1996, Andert 2009, Dryanovski et al. 2010]. Porém, a construçãodesses tipos de mapas requer um vasto custo computacional para o seu armazenamentoe processamento. Para superar esse problema, surgiram, então, os mapas 2,5-D, que ar-mazenam informação tridimensionais em uma estrutura de dados bidimensional.

No tocante aos sensores utilizados no mapeamento, devem serconsideradas certaspropriedades, por exemplo, preço do sensor, custo computacional, consumo de ener-gia, tipo de dados coletados e precisão. Considerando esses requisitos, as câmeras seapresentam como uma interessante alternativa para os sistemas de percepção robóticos.Propriedades como baixo custo monetário, portabilidade, baixo consumo de energia e a

1.3. ORGANIZAÇÃO DO TRABALHO 7

grande quantidade de dados que podem ser obtidos por esses sensores, fazem com essesdispositivos alcancem um papel de destaque em aplicações atuais com robô autônomos.

Entretanto, certas características relacionadas aos sensores podem interferir na quali-dade dos mapas construídos pelos robôs, e devem ser consideradas no processo de mapea-mento. Os sistemas de percepção possuem imprecisões intrínsecas à natureza do disposi-tivo de percepção utilizado, que podem distorcer as medições dos dados coletados. Comoconsequência, o mapa construído pode possuir incoerênciasimportantes que por sua vez,comprometem a interação do robô com o seu ambiente de trabalho. Ou seja, o robô podeconstruir um mapa inconsistente, fora da realidade espacial do ambiente mapeado. Paralidar de forma adequada com as imprecisões e incertezas sensoriais surgiram as abor-dagens de mapeamento baseadas em técnicas e ferramentas probabilísticas. Através dasteorias da probabilidade é possível modelar explicitamente as diversas fontes de ruído eseus efeitos nas medições.

Diante desse contexto, este trabalho propõe o método de mapeamento em grade deocupação-elevação, onde informações tridimensionais dosambientes mapeamedos serãoarmazenadas juntamanete com a probabilidade de ocupação dos mesmos. As informaçõesque compõem o mapa são tratadas com ferramentas estocásticas para garantir a manipu-lação adequada dos dados sensoriais, providos por um sistema de câmeras estéreo.

1.3 Organização do trabalho

A apresentação desse trabalho prossegue de acordo com a seguinte organização:

• O Capítulo 2 aborda o tema do mapeamento robótico mais formalmente, apresen-tando os fundamentos teóricos do problema, desafios que devem ser superados eclassificações;

• O Capítulo 3 trás uma explicação geral sobre o mapeamento de ambientes atravésde sistemas de visão e posteriormente aborda o mapeamento visual em grade deocupação;

• O Capítulo 4 descreve o mapeamento em grade de ocupação e os mapas de elevaçãocom suas formalizações matemáticas;

• O Capítulo 5 define o método de mapeamento proposto formalmente, detalhandoa estrutura de construção do mapa em grade de ocupação-elevação e a forma deintegração das informações sensoriais no mapa.

• O Capítulo 6 apresenta os experimentos realizados com o sistema proposto, con-siderando a aplicabilidade do mesmo tanto em ambientes internos quanto em am-bientes externos;

• Finalmente, no Capítulo 7 são apresentadas as consideraçõesfinais do trabalho,delineando as perspectivas futuras para o sistema em questão.


1.4 Produções Científicas

Capítulos de Livro

• Souza, A. A. S., A. M. Santana, A. A. D. Medeiros, L. M. G. Gonçalves.Mapea-mento de Ambientes. In: Robótica Móvel. (Org.) Roseli A. Francelin Romero;Edson Prestes; Fernando Osório; Denis Wolf. LTC/Elsevier, Em publicação.

• Souza, A. A. S., R. S. Maia, L. M. G. Gonçalves.3D Probabilistic OccupancyGrid to Robotic Mapping with Stereo Vision. In: Current Advancements in StereoVision. Dr. Asim Bhatti. (Org.). Rijeka: InTech, v. 1, p. 1-21,2012.

• Souza, A. A. S., A. M. Santana, A. A. D. Medeiros, L. M. G. Gonçalves.Prob-abilistic Mapping by Fusion of Range-Finders Sensors and Odometry. In: SensorFusion, Aleksandar Lazinica. (Org.). Rijeka: SCIYO, 2010.

• Santana, A. M., A. A. S.Souza, P. J. Alsina, A. A. D. Medeiros, L. M. G. Gonçalves.Fusion of Odometry and Visual Datas to Localization a MobileRobot Using Ex-tended Kalman Filter. In: Sensor Fusion, Aleksandar Lazinica (Org.). Sensor Fu-sion. Rijeka: SCIYO, 2010.

Artigos em Congressos

• Souza, A. A. S., L. M. G. Gonçalves.2.5-Dimensional Grid Mapping from StereoVision for Robotic Navigation. In: LARS/SBR - Latin American Robotics Sympo-sium, Fortaleza-CE, 2012.

• Souza, A. A. S., L. M. G. Gonçalves.3D Probabilistic Occupancy Grid to RoboticMapping. In: ICINCO - International Confrrence on Informatics in Control, Au-tomation and Robotics, Noordwijkerhout, 2011.

• Souza, A. A. S., L. M. G. Gonçalves.Mapeamento de Ambientes em Grade deOcupação Probabilística a Partir de Visão Estéreo. In: Simpósio Brasileiro de Au-tomação Inteligente - SBAI São João Del Rei-MG, 2011.

• Souza, A. A. S., R. S. Maia, L. M. G. Gonçalves.Uma Proposta de um Time deRobôs Heterogêneos Baseados na Tecnologia Sun SPOT para Mapeamento de Am-bientes. In: ROBOCONTROL 2010 Workshop de Robótica Aplicada e Automação,Bauru, 2010.

• Nascimento, C. V., L. M. G. Gonçalves, A. A. S.Souza, R. Q. Gardiman.TowardsFine Control Based on Sun SPOT Architecture. In: ROBOCONTROL 2010 Work-shop de Robótica Aplicada e Automação, Bauru. 2010.

1.4. PRODUÇÕES CIENTÍFICAS 9

• R. S. Maia, A. A. S.Souza, L. M. G. Gonçalves.Um modelo do Processo deAprendizagem proposto para um ambiente multi-robô. In: Peruvian ComputingWeek, 2010, Trujillo, Peru. JPC, 2010.


Capítulo 2

Mapeamento

Este capítulo apresenta a fundamentação teórica relacionada ao problema de Mapea-mento de ambientes com robôs móveis. Aqui serão apresentados os desafios a seremsuplantados, a classificação adotada para distinguir os diferentes tipos de mapas robóti-cos, destacando as vantagens e desvantagens de cada abordagem. Ao final do capítuloserá apresentada uma seção ressaltando trabalhos recentesda literatura que utilizam omapeamento de ambientes com robôs, com distintos sensores etipos de mapas, na reali-zação de diferentes tarefas.

2.1 O Problema do Mapeamento Robótico

A tarefa de mapeamento é muitas vezes considerada o mais importante problema narobótica, cujo progresso pode impactar uma grande parte dosproblemas baseados em per-cepção como, localização, navegação, exploração, assim por diante [Yang & Wang 2011].E para formalizar melhor o problema do mapeamento algumas observações devem serdestacadas. A primeira delas diz respeito ao sistema perceptivo dos robôs. Para realizaro mapeamento de um determinado espaço, um robô deve possuir um conjunto de sen-sores, que o habilite a obter dados sobre o ambiente. A segunda observação é que estemesmo sistema de percepção deve fornecer uma estimativa exata da pose (coordenadas eorientação) do robô em relação a algum referencial fixo global.

Feitas essas observações, o mapeamento de ambientes com robôs pode ser visto comoo problema de construir um modelo espacial do ambiente do robô, com uma representaçãocomputacional, baseando-se nos dados fornecidos pelos sensores internos e externos dosistema robótico. A Figura 2.1 é uma forma clássica de ilustrar o processo de mapeamentoem gráfico. A referida figura, representa a pose do robô porx e as medições sensoriaisadquiridas a partir de inspeções no ambiente no decorrer do tempo porz. Ambas asvariáveis devem ser conhecidas para que o robô tenha a possibilidade de construir o mapam. Perceba que o mapeamento é um processo que se desenvolve como tempo.

Porém, considerar verdadeira a suposição de que os sensorespodem fornecer umaestimativa exata da pose do robô não é válido, visto que, existem diversas fontes de in-certezas no mundo físico que contribuem com a degradação dasinformações sensoriais[Thrun et al. 2005]. Então, para ser obter uma estimativa mais precisa da pose do robôseria necessário a existência de um mapa a priori. Tem-se nesse caso, um paradoxo: o

12 CAPÍTULO 2. MAPEAMENTO

Figura 2.1: Grafico de composição do mapeamento.

sucesso na construção de um mapa coerente depende do conhecimento preciso da pose dorobô, e para inferir uma estimativa correta da pose do robô é necessário um mapa do am-biente apriori . Percebe-se que existe uma interdependência entre localização (inferênciada posição e orientação do robô no ambiente) e mapeamento. Por conta dessa dificul-dade muitos pesquisadores desdobram o problema de mapeamento para uma problema delocalização e mapeamento simultâneos ou SLAM (do inglês,Simultaneous Localizationand Mapping)[Grisetti et al. 2007].

Neste trabalho será considerado que o robô possui um sistemade localização baseadoem odometria que fornece uma estimativa relativamente precisa de sua pose, dado que éfeita uma calibração anterior apresentada em [Souza 2008].Esta abordagem é conhecidacomo mapeamento com pose conhecida [Thrun et al. 2005]. O foco do trabalho estaem fornecer um novo modelo de representação para mapeamentobaseado em grade deocupação com informações 3D, a fim de que o robô possua a capacidade de determinar seum dado obstáculo pode ser transposto ou não.

2.2 Desafios do problema de mapeamento robótico

Em um dos trabalhos mais referenciados na área de mapeamentorobótico, Thrun(2002) evidencia alguns desafios que devem ser consideradosdurante o processo de ma-peamento. A seguir, cada desafio será exposto de forma concisa.

2.2.1 Imprecisões sensoriais

Como já mencionado, os robôs necessitam de sensores para realizar o mapeamento.Esses sensores são limitados no que podem perceber. O alcance e a precisão estão su-jeitos a limitações físicas; são susceptíveis a ruídos, quepodem degradar suas medições;e podem sofrer danos estruturais. Além disso, existem incertezas inerentes aos movimen-tos realizados pelos robôs em seus ambientes. Os motores, responsáveis pela locomoção,são dispositivos que podem ocasionalmente falhar ou danificar-se. Ademais, os sinaisde controle que os aciona podem variar com a ação de ruídos. Fatores sistemáticos, tais

2.2. DESAFIOS DO PROBLEMA DE MAPEAMENTO ROBÓTICO 13

como as incertezas presentes nos parâmetros que fazem parteda modelagem cinemáticado robô (diferenças no tamanho das rodas, medição equivocada de eixo, etc.) e/ou fatoresnão sistemáticos, como as incertezas oriundas de situaçõesinesperadas (colisão com ob-jetos inesperados, escorregamentos das rodas, derrapagens, etc.), também são fontes deincertezas, que tornam imprecisas as informações do sistema robótico.

Aqui, a grande dificuldade está na natureza do ruído presentenas medições, isto é,modelar o problema de mapeamento robótico seria relativamente fácil se o ruído emdiferentes medições fosse estatisticamente independente. No entanto, o que se vê é umadependência estatística, pois os erros intrínsecos aos movimentos do robô interferem naforma como as medições sensoriais são interpretadas.

A Figura 2.2 ilustra uma situação em que erros de medição dos movimentos preju-dicaram a construção de um mapa preciso, em um robô equipado com sonares. O contornomais contínuo em vermelho representa a configuração das paredes do ambiente mapeado,no caso, um corredor. O ponto na extremidade direita da figurarepresenta a posição dorobô ao término da tarefa de mapeamento.

Figura 2.2: Mapa corrompido por erros de odometria.

Uma boa alternativa para se alcançar o sucesso diante desse desafio é modelar asfontes de erros por funções probabilísticas, permitindo que os dados sensoriais, mesmoincertos, sejam tratados de forma adequada durante o processo de mapeamento. Quandoesses fatores são desconsiderados, estamos propensos a testemunhar a construção de ma-pas inconsistentes e imprecisos.

2.2.2 Dimensionalidade

No mapeamento com robôs deve ser observado também a dimensãodos ambientes.Não se pode considerar que o mapeamento de um ambiente simples e estruturado, comoum corredor, é igual ou possui os mesmos requisitos e complexidade que o mapeamentode um ambiente de grandes dimensões, por exemplo, um bairro de uma cidade. Questõescomo, tipo de representação utilizada para reproduzir o ambiente mapeado, nível de de-talhamento do mapa, dimensões do mapa (2D ou 3D), espaço computacional disponível(memória), recursos de processamento, entre outras, devemser analisadas.

Ademais, não se pode esquecer que, quanto maior e mais complexo o ambiente, maiora probabilidade de ocorrer algum tipo de erro nos movimentosdo robô, o que pode acar-retar em prejuízos na qualidade do mapa construído.


2.2.3 Associação de dados -Matching

É natural que um objeto inserido em um ambiente a ser mapeado seja detectadomais de uma vez durante o mapeamento em diferentes instantesde tempo. É impor-tante que o robô tenha a capacidade de diferenciar objetos jámapeados dos que aindanão o foram. Este problema é conhecido como associação de dados ou correspondên-cia de dados (matching). Com o auxílio da Figura 2.3 pode-se entender melhor essaquestão. Nesta figura há duas imagens coletadas, em instantes e posições diferentes, poruma câmera embarcada em um robô móvel. Todos os pontos interligados por segmen-tos de retas entre as duas imagens foram reconhecidos, mesmotendo sido capturadas apartir de locais distintos. Para outros pontos não foi possível encontrar o seu correspon-dente. Caso os movimentos realizados dentro do intervalo de captura das imagens fossemainda mais acentuados a dificuldade de se encontrar pontos correspondentes nas imagensaumentaria.

Figura 2.3: Mapa corrompido por erros de odometria.

Ignorar o problema da associação de dados no mapeamento podeconduzir a incon-sistências e divergências nos mapas. Um esquema eficiente e efetivo de associação dedados deve estabelecer diferenças entre medições espúriase novas medições juntamentecom uma função básica para integrar ao mapa disponível, novas medidas sensorais.

2.2.4 Dinamicidade do ambiente

A grande maioria dos trabalhos relacionados à navegação e mapeamento consideramos ambientes de trabalho dos robôs como sendo estáticos. Quando o interesse está no ma-peamento de ambientes dinâmicos ou não estacionários, como, por exemplo, escritóriosonde pessoas trafegam constantemente e manufaturas onde objetos são transportados paradiferentes lugares, a complexidade do processo de mapeamento aumenta consideravel-mente. O robô passa a operar com a imprevisibilidade do ambiente, especialmente quandohá pessoas em movimento constante.

2.3. TIPOS DE REPRESENTAÇÕES 15

Um local já mapeado que sofre em algum instante, determinadas mudanças estruturaispode não ser reconhecido pelo robô. Dessa forma, há uma grande chance de o robôconsiderar esse espaço como sendo uma nova área ainda não mapeada ou até mesmodesconsiderar as medições coletadas e classificá-las como incoerentes.

2.2.5 Estratégia de exploração

Durante o mapeamento, o sistema robótico deve escolher certos caminhos a seremseguidos. A questão central é: dado que o robô tem algum conhecimento sobre o mundo,para onde ele deverá se mover para adquirir novas informações? A resposta a essa per-gunta é de responsabilidade da estratégia de exploração, a qual deve estabelecer princípiospara que o robô se movimente com o objetivo de explorar todo o ambiente a ser mapeado.

A estratégia de exploração admite que a pose do robô é precisamente conhecida eprocura direcioná-lo, de modo eficiente, ao longo do ambiente a fim de que o mapa sejaconstruído em sua totalidade [Stachniss 2009]. Diante disso, é preciso considerar o mod-elo do ambiente parcialmente montado, e a partir dele, planejar o movimento a ser reali-zado. O diagrama da Figura 2.4 adaptado do trabalho de Stachniss (2009), considera quea exploração é uma tarefa que engloba o problema de mapeamento e o planejamento decaminhos.

MapeamentoLocalização

Planejamento

Exploração Localização ativa

SLAM

Abordagemintegrada

Figura 2.4: O problema da exploração é a integração do Mapeamento com o Planejamentode caminhos [Stachniss 2009].

Neste mesmo trabalho, Stachniss (2009) apresenta um apanhado geral das várias téc-nicas de exploração desenvolvidas, traçando um comparativo com sua proposta, baseadaem mapas de cobertura (coverage maps).

2.3 Tipos de Representações

Existem duas classes principais que diferenciam os tipos derepresentações de ma-pas: as representações baseadas em topologia e representações baseadas em informaçõesmétricas [Thrun 2002]. Alguns pesquisadores sugerem acrescentar mais um paradigma


de representação baseado em características encontradas nos ambientes [Choset & Fox2004][Rocha 2006]. Porém, os mapas de características armazenam, na verdade, infor-mações métricas relacionadas às características, por essemotivo essa abordagem seráconsiderada, nesse trabalho, como uma instância dos mapas métricos. A seguir, as duasabordagens serão mais bem explanadas.

2.3.1 Mapas Topológicos

A abordagem topológica representa computacionalmente um ambiente mapeado pormeio de um grafo. Em termos gerais, os grafo descrevem a conectividade entre compar-timentos de um ambiente mapeado. Os nós do grafo correspondem a áreas que possueminformações sensoriais homogêneas e as arestas reproduzema relação de conexão entreessas regiões representadas por nós.

Do ponto de vista do sistema computacional do robô, a representação de um ambi-ente mapeado através de um grafo é uma boa alternativa, vistoque os grafos são estru-turas compactas e podem ser armazenados em uma quantidade relativamente reduzida dememória. Além disso, a representação em grafos favorece a execução de tarefas de maisalto nível, como planejamento de caminhos, simplesmente pela aplicação de algoritmostradicionais de busca em grafos.

Um problema importante desta abordagem é verificado quando se procura um padrãode definição de quais estruturas poderão ser consideradas nós e quais relações serão pon-deradas para a criação das arestas. Ademais, esse tipo de representação trata o problemade localização de uma forma abstrata, isto é, não é possível inferir de forma explícitaas coordenadas e a orientação de um robô em um mapa topológico. É possível apenasafirmar em qual nó, ou seja, em qual área do ambiente o robô se encontra.

Para explicar o processo de construção de um mapa topológico, a Figura 2.5 traz ailustração de um cenário típico de um escritório simples, noqual um robô (marco emvermelho) munido de sonares está encarregado de criar uma representação topológicado ambiente. Na Figura 2.5(a), o robô começa o processo de mapeamento colhendoinformações de seu entorno, a partir das medidas sensoriais(as 16 linhas que se origi-nam do robô), e identifica os limites do primeiro cômodo. Neste momento, o primeirocompartimento passa a ser classificado como o nó inicial do mapa topológico. Com oobjetivo de mapear as demais áreas do ambiente, o robô sai do espaço mapeado e segue ocaminho tracejado que o leva a um segundo compartimento, passando a explorá-lo (Figura2.5(b)). Esse novo espaço, após ser identificado, é classificado como um novo nó do mapatopológico. Seguindo a trajetória especificada, o robô passa a um novo compartimento,explorando-o (Figura 2.5(c)) e posteriormente classificando-o como o terceiro nó do grafo(Figura 2.5(d)). O processo de mapeamento segue (Figura 2.5(e)) e a cada novo cômodoidentificado um novo nó é adicionado ao mapa topológico. É importante observar que asarestas estão identificando a conexão que existe entre os compartimentos.

Percebe-se que o mapa topológico do exemplo dado pode ser facilmente armazenadono sistema computacional do robô, essa é uma vantagem constatada neste tipo de repre-sentação. Porém, quando se trata da construção de um mapa topológico de ambientes dedimensões maiores, essa construção pode se tornar mais complicada em virtude das am-


( a ) ( b )

( c ) ( d )

( e )

1

1

2 3

1

2

3

1

2 4

Figura 2.5: Mapemento topológico.

biguidades que podem existir nas informações sensoriais, que geralmente são esparsas.Isso pode ter como consequência direta, falhas na identificação de áreas já mapeadas enão mapeadas (problema de associação de dados). Essa característica dificulta a cons-trução e a manutenção de mapas desse tipo.

2.3.2 Mapas Métricos

A abordagem de representação métrica tem como objetivo armazenar informações deobjetos e formações geométricas presentes no ambiente do robô, com certa fidelidademétrica em relação ao mundo real. Os mapas métricos podem serdivididos nos mapasbaseados em grade de ocupação e nos mapas baseados em características. A seguir, essasduas classes serão detalhadas.


Grade de Ocupação (occupancy grid maps)

O modelo de mapeamento em grade de ocupação foi proposto inicialmente em 1987 eformalizado em 1989 pelo cientista brasileiro Alberto Elfes [Elfes 1987][Elfes 1989]. É ométodo de mapeamento mais representativo, cuja função é reproduzir um espaço em umagrade (grid) de células, as quais modelam o estado de ocupação do ambiente [Yang &Wang 2011]. A Figura 2.6 ilustra uma medição realizada por umsonar e como seria a suarepresentação em uma grade de ocupação. As células preenchidas de preto representamprováveis obstáculos detectados pelo sonar, as células em branco representam regiões doambiente possivelmente livres ou não ocupadas, por fim, as células em cinza representamregiões ainda não mapeadas pelo sonar.

Figura 2.6: Representação de uma medição de um sonar em uma grade de ocupação.

O valor de ocupação atribuído às células é inferido por uma função probabilística,cujo resultado indica a probabilidade de um lugar estar ocupado, a partir de uma mediçãosensorial interpretada. A cada nova medição sensorial o valor de ocupação das célulasdentro do campo visual dos dispositivos de percepção é atualizado. O modelo espacialprobabilístico baseado em grade de ocupação se apresenta como uma forma de represen-tação que pode ser usada diretamente na realização de tarefas de navegação, tais comoplanejamento de caminho com desvio de obstáculo e estimativa de posição [Elfes 1989].

Neste trabalho o mapeamento em grade de ocupação é utilizadopara representar oambiente mapeado por um robô munido de um sistema de visão estéreo. A grade de ocu-pação foi escolhida por apresentar algumas interessantes vantagens em relação a outrasrepresentações de mapas. Em um capítulo posterior, o mapeamento em grade de ocupaçãoserá explorado com mais detalhes.

Mapas de características (feature-based maps)

Uma característica pode ser entendida como um objeto ou alguma forma facilmentedetectável presente em um ambiente, por exemplo, retas, cantos, quinas, bordas, círcu-los, planos ou regiões com alguma propriedade específica. Osmapas de característicasregistram informações a respeito desses tipos de elementos. Geralmente são informaçõescontendo alguma relação métrica com o mundo real como, coordenadas cartesianas e co-ordenadas polares. A Figura 2.7 ilustra um exemplo de características sendo detectadasem um corredor típico de um ambiente interno. Nesta figura, segmentos de retas presentes


em contornos de portas, janelas, piso, etc., são vistos comoformas notáveis e adequadaspara a construção de um mapa de características.

Figura 2.7: Construção de um mapa de características a partirda detecção de retas.

Uma vantagem significativa desse tipo de mapa é que muitas vezes possibilita umaconstrução compacta se comparada a representações em gradede ocupação. Porém, tam-bém possui desvantagens, e a principal delas é a dependênciade um procedimento pré-definido para detectar e extrair características do ambiente [Stachniss 2009].

2.3.3 Mapas topológicos vs. Mapas métricos - Vantagens e Desvan-tagens

Diante do apresentado acima é interessante traçar um diagnóstico comparativo entreas duas abordagens citadas, conferindo vantagens e desvantagens de cada uma. Para isso,serão adotados como base os parâmetros levantados no trabalho de Thrun [Thrun 1998].

Uma vantagem importante dos mapas métricos em relação aos topológicos, é quesão mais simples de serem construídos e mantidos, ainda que sejam considerados osambientes complexos e grandes. Ainda, a representação métrica torna mais fácil o re-conhecimento de lugares diferentes com base na posição geométrica do robô dentro deum sistema de coordenadas global. Com base em uma boa estimativa da pose do robô,as diversas medições sensoriais semelhantes, tomadas de diferentes posições, podem serdistinguíveis. Com isso, locais geometricamente próximos são diferenciados com certafacilidade. Porém, deve-se atentar para a prerrogativa de se ter uma boa estimativa dapose do robô, o que não é tão trivial de se obter.

Como já mencionado anteriormente, existe certa dificuldade na construção de mapastopológicos, ligada a definição de quais estruturas serão classificadas como nós e de quaisinformações serão compostas as arestas. Isso se torna aindamais dificultoso se as in-formações sensoriais do robô forem esparsas e ambíguas. Porém, como vantagem emrelação à abordagem métrica, a pose do robô não precisa ser exatamente conhecida.

Uma desvantagem da representação métrica está no alto custocomputacional que estarequer para ser construída, armazenada e atualizada. É necessário um maior espaço com-


putacional para armazenar mapas dessa abordagem, principalmente quando se tem mapasem grade de ocupação com uma resolução fina ou mapas de características com grandesquantidades de características armazenadas. Os mapas topológicos, por sua vez, são com-pactos de resolução proporcional à complexidade do ambiente. Essa estrutura compactafavorece o armazenamento em reduzido espaço de memória e a resolução de problemasde mais alto nível com menor necessidade de processamento.

É possível também, combinar diferentes tipos de representação de mapas em umaabordagem híbrida [Blanco et al. 2008]. O principal objetivodesta representação é in-tegrar as principais vantagens das abordagens métrica e topológica, o que deve reduziras desvantagens pontuais de cada enfoque. Assim, o robô pode, eficientemente, executaras tarefas mais adequadas para cada tipo de representação. Por exemplo, o robô podenavegar pelo seu ambiente, planejando rotas através de algoritmos de busca em grafopelo mapa topológico, e ao mesmo tempo, pode adotar estratégias locais de desvio deobstáculos utilizando a representação métrica.

2.3.4 Trabalhos Relacionados

As primeiras investigações que se destacaram na linha de mapeamento de ambi-entes com robôs surgiram no final da década de 1980. Nesta época foram publicados osprimeiros trabalhos com resultados relevantes. Com essas primeiras pesquisas aparece-ram vários modelos de mapeamento usando diversas estruturas geométricas e topológicas,com o objetivo de se alcançar a melhor precisão possível na representação do ambiente,considerando a dificuldade de lidar com a alta dimensionalidade dos espaços.

Os pesquisadores propuseram em seus trabalhos formas de representações como, rep-resentação geométrica 3D por esferas [Goldstein et al. 1987], representação poligonal[de Saint Vincent 1987], representação por meio de características como pontos, arestase cantos [Merat & Wu 1987], modelos geométricos hierárquicos [Kriegman et al. 1987],representação por grade de ocupação [Elfes 1987], representação baseada na topologia doambiente [Kuipers & Byun 1988], entre outras [Angelopoulou et al. 1992].

Posteriormente, em um artigo descrevendo o estado da arte domapeamento robótico,Thrun (2002) propôs uma classificação das representações demapas nas duas classesapresentadas anteriormente: topológica e métrica. De forma simplista, a abordagemtopológica engloba todas as representações cujo enfoque é reproduzir mapas na formade grafo, onde os nós são lugares e a conectividade entre os locais é descrita por suasarestas. E a abordagem métrica passou a compreender as representações que presam emarmazenar propriedades geométricas do ambiente.

Uma forma mais recente de representar ambientes é através douso de informaçõessemânticas que podem ser extraídas dos mapas. É possível, por exemplo, obter umaclassificação dos obstáculos mapeados (cadeiras, mesas, portas abertas ou fechadas, etc.)através de técnicas semânticas [Wolf & Sukhatme 2008].

A tarefa de mapeamento se estende a distintos ambientes. Os robôs podem ser utiliza-dos para mapear ambientes internos (indoor), ambientes externos (outdoor), ambientessubterrâneos e ambientes subaquáticos. No trabalho de Santana & Medeiros (2009), elesaproveitaram o fato de que muitos ambientes internos tem o piso formado por blocos,


para implementar um sistema de mapeamento de linhas no planodo piso do ambiente,sabendo-se que os espaços entre os bloco acabam originando linhas. Gallelos & Rives(2010), por sua vez, utilizaram um robô equipado de diferentes sensores para mapear am-bientes internos e construíram uma representação 3D do ambiente mapeado. Passandopara ambientes externos, Yang & Wang (2011) apresentaram uma abordagem de mapearambientes urbanos considerando a existência de objetos estáticos e dinâmicos. Eles exibi-ram os resultados de seus estudos em mapas baseados em gradesde ocupação. Silver et al.(2004) utilizaram um robô para mapear e explorar minas subterrâneas, atividade essa, quepode apresentar riscos a seres humanos. Johannsson et al. (2010), por sua vez apresen-taram um robô submarino que detecta características a partir de imagens de sonares paraconstruir um mapa que é posteriormente utilizado em vigilância submarina. Esses sãoalguns exemplos de trabalhos que mostram a diversificação deambientes que podem sermapeados utilizando-se diferentes técnicas de mapeamento.

Para que um sistema robótico tenha sucesso em seu mapeamentoé interessante quepossua sensores que capturem informações do seu entorno, com certas característicasdesejáveis: campo de visão amplo, acurácia, dados de fácil interpretação, baixo consumode energia, tamanho e peso reduzidos, entre outras. Distintos tipos de sensores podem serutilizados, porém os de maior destaque são os sonares, os scanners lasers e as câmeras.

Os sonares são sensores atrativos pelo seu baixo custo, entretanto possuem proprieda-des que os tornam sensores em desuso. Muitas medições são imprecisas por serem afe-tadas por problemas de falsas reflexões das ondas sonoras em superfícies planas. Umrecente trabalho que se utiliza de sonares para extrair características de ambientes desor-denados foi apresentado por [Lee & Son 2010].

Uma interessante alternativa para a construção de mapas densos são os scanners lasers,esses são sensores bastante precisos, eficientes e forneceminformações de fácil interpre-tação e que não necessitam de processamento complexo. Porém, esses sensores não sãohábeis no tratamento de superfícies de vidro. Ademais, são sensores que apresentam umalto custo monetário. Ruhnke et al. (2011) implementaram um algoritmo de mapeamentode alta precisão baseado em informações de sensores lasers.Eles propuseram a aplicaçãode técnicas de otimização para melhorar as estimativas da pose do robô e das mediçõessensoriais, a fim de obter um mapa mais acurado do ambiente.

As câmeras vêm ganhando destaque nos trabalhos relacionados a mapeamento de am-bientes e navegação com robôs, por serem dispositivos que podem prover uma grandequantidade de informações sobre o ambiente no qual estão inseridas. Além disso, sãocompactas, leves e podem ser encontradas com custo moderado. Seja com um sistemade múltiplas câmeras, como os sistemas de visão estéreo e sistemas de câmeras omnidi-recionais, ou com sistemas monoculares, são inúmeras as possibilidades de técnicas parageração de mapas a partir das câmeras, que dependem do tratamento dado às imagens.

O grande desafio encontrado está no processamento das informações em tempo real,porém este problema vem sendo amenizado com o desenvolvimento de processadoresmais poderosos e de baixo custo. Um interessante trabalho com base em um sistema devisão foi desenvolvido por Marks et al. (2009). Os autores desenvolveram um mapea-mento em grade para ambientes não estruturados com um robô munido de uma câmeraestéreo. O mapa em grade é preenchido com os resultados computados por um modelo


sensorial probabilístico que adota a função Gama em seu cerne. Ao final,o mapa adquiridocomporta informações sobre o quão navegável é um determinado terreno.

Com frequência se encontra na literatura autores propondo o uso em conjunto de sen-sores distintos. O objetivo principal é fundir as informações de todas as fontes para al-cançar um mapeamento mais rico e eficiente. Gallelos & Rives (2010), por exemplo,utilizam um robô provido de uma câmera omnidirecional e um laser para realizar o ma-peamento de ambientes internos. No trabalho de Ahn et al. (2007), os autores fundiraminformações de um sistema de visão estéreo e sonares para coletar informações planaresde ambientes internos.

O presente trabalho está no contexto do mapeamento de ambientes com sistema decâmeras estéreo e representação em grade. As câmeras apresentam inúmeras caracterís-ticas que as tornam atraentes para serem aplicadas no mapeamento de ambientes. Essaabordagem de mapeamento utilizando câmeras (monocular, estéreo ou omnidirecional) étambém conhecida por mapeamento visual (Visual Mapping), que será tema do próximocapítulo.

Capítulo 3

Mapeamento Visual

Este capítulo contextualiza o problema de mapeamento com sensores visuais, ou seja, aconstrução de uma representação espacial a partir de imagens. Este procedimento é tam-bém conhecido como mapeamento visual. O capítulo exporá as técnicas de mapeamentovisual com diferentes configurações de câmeras. Ademais, alguns pontos importantesserão destacados para explicar quais e como as informações visuais podem extraídase manipuladas para a construção de mapas robóticos. Semelhantemente ao capítuloanterior, serão apresentados trabalhos correlacionados ao tema, expondo as técnicas enovidades utilizadas mais recentemente.

3.1 Contextualização

Como anteriormente explicitado, a tarefa de mapeamento tem um grande impacto emtarefas que dependem do sistema perceptivo dos robôs como, localização, navegação, ex-ploração, entre outras. Quando este problema é consideradona conjunção dos sensoresvisuais ou câmeras, passa a ser denominado de mapeamento visual. Neste contexto, as in-formações visuais capturadas são utilizadas para que o robôrealize sua tarefa empregandouma navegação visual segura e eficiente, podendo abranger a vigilância de ambientes,resgate em acidentes ou catástrofes, identificação e rastreamento de objetos, exploraçãoaérea, patrulhamento, entre outras.

A inspiração para essa abordagem vem da fisiologia humana. O principal sentidoempregado na navegação e localização de uma pessoa entre objetos e obstáculos é o davisão. Do mesmo modo, na robótica um sistema visual artificial construído a partir decâmeras pode ser muito útil na navegação e localização de um robô em seu ambiente.

A grande vantagem de se utilizar um sistema de percepção baseado em sensores vi-suais está na significativa quantidade de informações que podem ser coletadas do entornodo robô. Isso proporciona uma ampla gama de aplicações possíveis para os sistemasrobóticos quando o principal meio de percepção externo são câmeras. Além dessa impor-tante questão, as câmeras são compactas, leves, consomem pouca energia, são facilmenteintegradas ao hardware de um robô, podem ser encontradas no mercado com diferentespreços, tais características as tornam bastante atrativas. Atualmente, até mesmo as pe-quenas câmeras embarcadas em celulares estão sendo utilizadas na navegação (odome-tria visual) de robôs, quando estes utilizam o próprio celular como processador [Aroca

24 CAPÍTULO 3. MAPEAMENTO VISUAL

& Gonçalves 2012]. Essas são características que permitem odesenvolvimento de umgrande conjunto de funcionalidades essenciais na robótica: detecção de obstáculos, ras-treamento de pessoas, servovisão, etc. [Lemaire et al. 2007].

Quando aplicadas ao mapeamento robótico, o uso das câmeras traz algumas outrasvantagens: primeira, os dados são percebidos em um ângulo sólido, o que permite abor-dagens de mapeamento 3D. Segunda, técnicas visuais de estimativa de movimento podefornecer um resultado muito preciso sobre os movimentos do robô. E por fim, caracterís-ticas muito estáveis podem ser detectadas em diferentes imagens, o que dá a possibilidadede derivar algoritmos que permitam o associação de dados (matching) entre elas mesmocom alterações significativas do ponto de vista [Lemaire et al. 2007].

Um grande desafio relacionado aos sistemas de visão artificial está em como tirarproveito dos sensores visuais com algoritmos confiáveis e eficazes que possam extrair asinformações necessárias para a resolução de problemas [Santana 2011]. Muitas pesquisasmais antigas ressaltam a dificuldade de que os sistemas baseados em câmeras necessitamde grandes recursos de processamento para se obter resultados em tempo real. Porém,com os grandes avanços alcançados no desenvolvimento de processadores mais rápidos,se percebe um aumento significativo de pesquisas recentes que utilizam os sistemas vi-suais como fontes de informações sensoriais. O rápido aumento no poder de proces-samento dos computadores faz com que seja possível lidar comuma maior quantidadede informações, permitindo melhor compreensão do ambiente, facilitando a tomada dedecisões por parte dos robôs.

3.2 Configurações de Câmeras mais Utilizadas no Ma-peamento Visual

Os principais sistemas de percepção visual utilizados em robôs móveis são: visãomonocular e visão estéreo.

3.2.1 Visão Monocular

Os sistemas de visão monocular utilizam apenas uma câmera para coletar informaçõesdo entorno do robô (Figura 3.1). Civera et al. (2008) definem umsistema monocularcomo um sensor projetivo cujo objetivo é medir o deslocamento das características emuma imagem. Com isso, dada uma sequência de imagens de uma cena, tomadas a partirde uma câmera em movimento, é possível computar a estrutura da cena e o movimento dacâmera a menos de um fator de escala. Geralmente as informações 3D são representadaspor um conjunto esparso de pontos de interesses ou características detectadas. Ou seja, ouso de sistemas monoculares é mais relevante na construção de mapas de características.

Um dos principais desafios no uso desses sistemas está em dar,inicialmente, estima-tivas corretas de informações tridimensionais de objetos contando apenas com imagens[Piniés et al. 2010]. O problema está em determinar um fator de escala para definir alocalização correta dos objetos detectados no mundo. Algumas soluções foram propostaspara lidar com essa problemática. Uma das mais expressivas foi proposta por Civera et al.

3.2. CONFIGURAÇÕES DE CÂMERAS MAIS UTILIZADAS NO MAPEAMENTO VISUAL25

Figura 3.1: Câmeras monoculares.

(2008). Os autores apresentaram uma solução baseada em uma parametrização da profun-didade inversa para representar pontos detectados. Essa informação pode ser incorporadana estimativa dos dados de uma característica, a partir da primeira imagem capturadaonde a característica é observada. Para calcular as estimativas os autores utilizaram oFKE (Filtro de Kalman Estendido).

3.2.2 Visão Estéreo

Visão estéreo se refere à habilidade de inferir informaçõesde estruturas 3D e distânciaà uma cena a partir de duas ou mais imagens tomadas de diferentes pontos de vista. Ossistemas de visão estéreo se baseiam no sistema visual humano. A diferença na localiza-ção da retina esquerda e direita é usada pelo cérebro para reconstruir uma representação3D do que se vê [Trucco & Verri 1998]. Tendo isso como inspiração, foram desenvolvi-dos os sistemas de visão estéreo artificiais, os quais podem conter duas ou mais câmeraspara adquirir informações de estruturas 3D. Alguns sistemas dispõem de várias câmerasarranjadas estrategicamente para capturar imagens em um ângulo de 360 graus, dandouma visão esférica do ambiente, tais câmeras são chamadas deomnidirecionais. A Figura3.2 abaixo, ilustra alguns desses sistemas de câmeras estéreo.

(a) (b)

Figura 3.2: Câmeras estereoscópicas: (a) câmeras binoculare trinocular; (b) câmeraominidirecional.


Um sistema de visão estéreo provê, de forma direta, medidas de distâncias aos objetoscapturados em ambas as imagens. Essa é considerada a principal vantagem desse sistemaem relação à visão monocular. O presente trabalho faz uso de um sistema de visão estéreode baixo custo com duas câmeras para o mapeamento de ambientes. Por esse motivo,a seguir, será explanado todo o processo de visão estéreo responsável pela inferência deinformações 3D de estruturas presentes em um ambiente.

3.3 Estereoscopia

Para inferir informações de estruturas 3D a partir de duas imagens tomadas de locaisdistintos, usando ferramentas computacionais, é preciso considerar a resolução de doisproblemas principais. O primeiro é conhecido como problemade correspondência, queconsiste em determinar quais pontos capturados na câmera esquerda estão sendo vistostambém pela câmera direita. O segundo está relacionado com areconstrução da cenavista pelas câmeras, dados os pontos identificados no problema anterior e a geometria dosistema estéreo [Trucco & Verri 1998].

Esse processo segue alguns passos importantes: primeiro, calibração das câmeras,o qual possibilita estimar parâmetros internos das câmerase parâmetros relativos entrecâmeras; segundo, retirada de distorções das imagens, efeitos esses que são introduzidospor defeitos de fabricação das lentes; terceiro, retificação das imagens, alinhando-se osplanos das imagens e os eixos óticos; e quarto, estimação do mapa de disparidade ouimagem de profundidade. Para entender melhor esses problemas é interessante analisarprimeiro a geometria estéreo, usando o modelo de câmerapinhole.

3.3.1 Geometria Estéreo e Reconstrução 3D

Com o auxílio da Figura 3.3 é possível analisar geometricamente como se dá todo oprocesso de calculo de coordenadas 3D de um objeto a partir deimagens 2D capturadaspor duas câmeras. Formulando matematicamente, considere opontoP no mundo de coor-denadas desconhecidas, o qual é detectado pelas câmeras esquerda e direita de um sistemaestéreo. Para simplificação do problema, deve-se ponderar que as câmeras possuem osplanos de imagem coplanares e eixos óticos paralelos. Na Figura 3.3,O′ eO representamos centros de projeção das câmeras,f é a distância focal das câmeras (distância entre ocentro de projeção e o plano de imagem), a distânciab entre os centros de projeçãoO′ eO, é chamada de linha de base.f e b são parâmetros do sistema estéreo que podem serinferidos por uma calibração estéreo.

As coordenadas(xlo,y

lo) e (xr

o,yro) representam os pontos pelos quais os eixos óticos

intersectam os planos de imagens em ambas as câmeras. O pontoP é representado pelospixels de coordenadas(xl ,yl ) e (xr ,yr) nos planos de imagem, ou seja,(xl ,yl ) e (xr ,yr)são as projeções do pontoP na imagem esquerda e direita respectivamente. Como osplanos de imagem são coplanares e os eixo óticos paralelos, então podemos assumir queyl = yr . E zc é a distância ou profundidade do pontoP em relação ao sistema estéreo.

3.3. ESTEREOSCOPIA 27

P

b

f

f

zc

eix

o ó

ptico

eix

o ó

ptico

plano da imagem

O’

O

),( 00

llyx

),( 00

rryx

),( llyx

),( rryx

Figura 3.3: Geometria estéreo.

O método pelo qual a posição do pontoP no espaço tridimensional é determinada échamado de triangulação, o qual considera a intersecção dosraios definidos pelos centrosde projeção (O′ e O) e as coordenadas de imagem do pontoP ((xl ,yl ) e (xr ,yr)). Porém,a triangulação depende da solução do problema de correspondência, ou seja,(xl ,yl ) e(xr ,yr) devem classificados por algum método como pontos correspondentes. Posterior-mente, serão apresentados alguns métodos utilizados para encontrar a correspondênciaentre pontos de ambos os planos de imagens.

A profundidadezc pode ser encontrada por semelhança de triângulos, como segue naEquação 3.1.

b− (xl −xr)

zc− f=

bzc

(3.1)

Desenvolvendo a Equação 3.1 chega-se a Equação 3.2.

zc =b. f

(xl −xr)(3.2)

Essa equação mostra que a profundidadezc é inversamente proporcional à diferença oudisparidadeentre as duas vistas, assim a disparidade pode ser definida matematicamentepord = xl −xr . Modificando a Equação 3.2 tem-se a Equação 3.3.

zc =b. fd

(3.3)


Com essa expressão tem-se a definição de uma das coordenadas dopontoP em relaçãoao referencial da câmera estéreo, o qual será descrito porPc. A disparidade é dada pelasolução do problema de correspondência, a qual deve apresentar como resultado finaluma imagem bidimensional, também chamada de mapa de disparidade, cujos valores dospixelsd(x,y) descrevem a diferença entre duas imagens [Andert 2009]. Usando o mesmoraciocínio de triangulação e as informações do mapa de disparidade, pode-se encontrar ascoordenadasxc e yc do pontoPc = (xc,yc,zc)

T . As Equações 3.4 e 3.5 expressam essasrelações.

xc = zc.(x−x0)

f(3.4)

yc = zc.(y−y0)

f(3.5)

Nas equações acima(x,y) e (x0,y0) são coordenadas de uma das imagens (esqueda oudireita). Na prática se limita o valor assumindo valores máximo e mínimo para a distânciazcmin < zc < zcmax, com zcmin > 0 [Andert 2009]. Com as coordenadas do pontoPc =(xc,yc,zc)

T , a matrix de orientaçãoRe o vetor de translaçãoT que mapeiam o sistema decâmera em coordenadas de mundo, pode-se, agora, calcular ascoordenadas deP.

P= RT .Pc+T (3.6)

Assim, têm-se as coordenadas do pontoP, antes desconhecida, calculadas através dosartifícios da geometria estéreo. Nesse ponto, a etapa de reconstrução 3D é concluída.

3.3.2 Disparidade Estéreo

O termodisparidadefoi relacionado primeiro ao sistema preceptivo visual humanopara descrever a diferença entre cenas correspondentes enxergadas pelo olho esquerdo edireito [Sharstein & Szeliski 2002]. Trazendo essa definição para o campo da visão com-putacional, a disparidade pode ser entendida como a diferença entre as coordenadas deimagem de um ponto no mundo, capturado pelas câmeras esquerda e direita de um sis-tema estéreo. Alguns pesquisadores têm definido a disparidade como uma transformaçãoprojetiva tridimensional do espaço 3D [Sharstein & Szeliski 2002].

Neste trabalho, considera-se o uso de um sistema estéreo cujos planos de imagens sãocoplanares e os eixos óticos estão alinhados. Essa restrição limita a dedução da dispari-dade para apenas as coordenadasx das imagens (d = xl − xr), podendo ser chamada dedisparidade horizontal. Essa prerrogativa facilita a busca e a identificação dos pixels cor-respondentes(xl ,yl ) e (xr ,yr), fazendo com que seja realizada uma redução no espaço debusca de 2D para 1D, que será apenas uma linha horizontal, restrita ao eixox dos planosde imagem esquerdo e direito. Essa consideração é conhecidapor restrição epipolar.

Para encontrar os pixels,(xl ,yl ) e (xr ,yr), correspondentes a projeção do pontoP emambos os planos de imagens, e gerar um mapa de disparidade existem vários algoritmos.Sharstein & Szeliski (2002) elaboraram um apanhado geral departe desses algoritmos,fazendo uma análise comparativa entre eles. Em seu trabalho, Hong & Chen (2004)

3.3. ESTEREOSCOPIA 29

classificaram os algoritmos de correspondência estéreo em duas categorias: algoritmoslocais (baseados no conceito de janelas) e algoritmos globais (baseados em técnicas deminimização).

Algoritmos Locais

Os algoritmos locais, também chamados de algoritmos de janela variável de pixel (oublock-macthing), procuram fazer a associação de pixels entre duas imagens de maneirarápida e com redução de ruído. No momento de realizar uma comparação entre imagens,não só o valor do pixel buscado é levado em consideração e sim,uma janela de pixelsvizinhos. A premissa por trás dessa abordagem é que a disparidade entre pixels da mesmajanela é aproximadamente igual, isso favorece a redução de ambiguidades na associaçãodos pixels entre duas imagens. Basicamente este método gera omapa de disparidadeseguindo três passos principais: o primeiro passo tem como função a normalização dobrilho das imagens e o realce de textura. O segundo passo, é a busca de pixels correspon-dentes considerando a restrição epipolar. Aqui, utiliza-se a soma das diferenças absolutasentre janelas de mesmo tamanho em ambas as imagens para se encontrar a correspondên-cia. O terceiro passo consiste na eliminação de falsas correspondências. Finalmente, apósa execução desses passos a disparidade é calculada para os pixels com valores de dispari-dade válidos [Bradski & Kaehler 2008]. Essa abordagem gera resultados razoáveis emtempo-real. A Figura 3.4 apresenta um resultado de um mapa dedisparidade gerado peloalgoritmo de janela variável.

(a) (b)

Figura 3.4: Mapa de disparidade gerado pelo algoritmo de janela variável; (a) imagemoriginal; (b) mapa de disparidade.

Algoritmos Globais

Dentre os algoritmos globais que utilizam a minimização para a geração de um mapade disparidade se destacam os algoritmos que aplicam princípios de programação dinâmicae algoritmos baseados em grafos. Apreciando o uso da programação dinâmica, os algo-ritmos empregados se baseiam no princípio de dividir para conquistar. Neste princípioum grande problema é dividido em subproblemas, que são solucionados de maneira in-dependentes e suas soluções são organizadas para formar a solução do problema original.


Analisando na visão estéreo, uma imagem deve ser dividida emlinhas (subproblemas) esoluciona-se a associação para cada uma delas separadamente, considerando a aplicaçãode técnicas de minimização de custos em torno da busca do pixel de maior credibilidadepara a associação.

Os algoritmos globais baseados em grafos, também conhecidos na literatura comograph-cuts, fundamentam-se no conceito de energia de pixels. Nessa abordagem ummapa de disparidade é calculado previamente para depois seraprimorado. Com isso écalculado um valor de energia a qual deve ser globalmente minimizada. A estratégia éprocurar minimizar a energia do mapa de disparidade construindo um grafo, no qual cadavértice representa um pixel do mapa e cada aresta possui o valor de energia associadoaos pixels conectados a ela. São criadas tabelas com possíveis valores de disparidadeassociados a cada vértice e então, é executado um processo deescolha de um melhorvalor de disparidade para todos os pixels da imagem, considerando a minimização deenergia. Ograph-cutsapresenta resultados significantes quando comparados a outrastécnicas, em contrapartida possui um grande custo computacional atrelado à geração dosseus resultados [Hong & Chen 2004]. A Figura 3.5 ilustra um resultado de um mapa dedisparidade gerado pelo algoritmosgraph-cuts.

(a) (b)

Figura 3.5: Mapa de disparidade gerado pelo algoritmo degraph-cuts; (a) imagem origi-nal; (b) mapa de disparidade.

Melhorias podem ser realizadas para que o uso dessa técnica possa ter viabilidade emtarefas de tempo real. Alguns desses avanços foram propostos no trabalho de [Zureikiet al. 2007]. Diante dos estudos feitos e resultados analisados a partir de alguns testesrealizados com as duas abordagens apresentadas, foi decidido trabalhar nesta pesquisacom o algoritmo baseado emgraph-cutspor apresentar um mapa de disparidade maisrico em detalhes, o que é mais interessante para o mapeamentode ambientes.

3.4 Trabalhos Relacionados

Nesta seção serão apresentados alguns trabalhos científicos que lidam com o mapea-mento robótico baseado em sistemas de visão monocular e estéreo. Aqui serão levantadasas diferentes estratégias de escolha de informações relevantes para a construção das dis-tintas representações de mapas.

3.4. TRABALHOS RELACIONADOS 31

Os primeiros trabalhos sobre mapeamento robótico utilizando visão foram apresenta-dos na década de 1980 [Moravec 1988, de Saint Vincent 1987]. Essas primeiras evoluçõesforam alcançadas com estudos baseados em visão estéreo. Nesta época surgiram asprimeiras pesquisas relacionadas a representação em gradede ocupação e dentro dessecontexto Moravec (1988) propôs um sistema de mapeamento composto por um conjuntode sonares e um sistema de visão estéreo com duas câmeras. As informações de ambosos tipos de sensores eram fundidas para construir o mapa de ocupação.

As pesquisas baseadas em visão monocular são mais contemporâneas, elas começarama ser desenvolvidas a partir de 2002, quando as primeiras investigações com resultadossignificativos foram publicados por Davison [Davison 2002,Davison 2003]. Anos maistarde, em um trabalho mais completo, o mesmo pesquisador juntamente com colegasformalizaram a proposta aplicando-a na localização e mapeamento simultâneos. Eles de-nominaram a técnica de MonoSLAM [Davison et al. 2007]. Essestrabalhos focaram nomapeamento em tempo real, algo complexo quando se tem o processamento de grandequantidade de informações envolvidas.

As soluções robóticas para mapeamento de ambientes com câmeras estéreo se es-tende desde o uso de sistemas com duas câmeras até o uso de sistemas várias câmeras.Por exemplo, Andert (2009) utilizou um sistema de visão estéreo de duas câmeras em-barcado em um helicóptero para construir um mapa 3D, cujo objetivo final do mapa era anavegação do aeromodelo. Já no trabalho apresentado por Ogawa et al. (2007), um robômóvel terrestre equipado com uma câmera estéreo trinocularfoi utilizado para construirum mapa 3D de pontos notáveis do seu ambiente de navegação. Emum trabalho mais re-cente, Gallelos & Rives (2010) implementaram um mapeamento robótico 3D, desta feitafundindo as informações de um sistema de câmeras omnidirecional com um laser 2D. Osensor laser foi utilizado por fornecer dados mais exatos sobre a profundidade de objetose obstáculos.

As informações utilizadas para a construção de mapas robóticos com sistemas de visãomonocular ou estéreo podem ser escolhidas de acordo com as particularidades do ambi-ente de trabalho do robô, de modo a facilitar a detecção das características mais aparentes,ou podem ser ainda abstraídas para que mapas mais genéricos sejam construídos. Den-tro do primeiro raciocínio, existem trabalhos que se concentram na construção de mapasde características fundamentados em pontos, retas e planos. No âmbito dos sistemasde visão monocular, Wu et al. (2010) propuseram em seu trabalho uma abordagem deseleção de pontos notáveis baseada no algoritmo SIFT (Scale-Invariant Feature Trans-form). Os autores apresentam uma maneira de reduzir a quantidadede pontos-chaves narealização do mapeamento, consequentemente diminuindo o tempo de convergência domapeamento. Já na esfera da visão estéreo Davison (2002), por exemplo, implementaramum mapeamento com um sistema estéreo onde as características armazenadas eram can-tos detectados pelo detector de cantos de Harris. Em outro trabalho [Ogawa et al. 2007],foi empregado o algoritmo SIFT para detectar as características relevantes do ambientecapturadas por um sistema estéreo.

Soluções que utilizam a extração de linhas para a construçãode mapas com o uso desistemas de visão são facilmente encontradas na literatura. Em geral, estas técnicas estãoatreladas ao uso da transformada de Hough para detectar as retas nas imagens. Santana


& Medeiros (2011) propuseram um sistema de visão monocular para detectar linhas noplano do chão de pisos de ambientes internos e externos, construindo, posteriormente,um mapa para armazenamento dessas formas geométricas. Quando se trata de sistemasestéreo, Chang et al. (2010) apresentaram o mapeamento de linhas verticais detectadaspelo sistema de visão. Neste caso, informações 3D a respeitodas linhas são armazenadasem um mapa de características. Gallelos & Rives (2010) implementaram a mesma ideia,porém eles contaram com um robô munido de uma composição de sensores: uma câmeraomnidirecional e um laser, fundindo as informações de ambos.

Na detecção de plano, o uso de sistemas monoculares está na maioria das vezes atre-lado a fusão com outros sensores [Servant et al. 2010]. Porém, alguns pesquisadoresutilizam apenas a câmera como fonte de informação [Aires & Medeiros 2010]. O uso devisão estéreo na detecção de plano também pode ser verificadona literatura. Murarka &Kuipers (2009), por exemplo, implementaram em seu trabalhouma forma de detecção deplanos e regiões possíveis de serem navegadas por um robô móvel.

Como mencionado anteriormente, os sistemas de visão estéreopodem ser utilizadosna construção de mapas robóticos mais genéricos, isto é, sema necessidade de se deter adetecção de um tipo de características particular do ambiente. Grande parte dos trabalhosque levam em conta essa solução adota o mapeamento em grade deocupação [Agrawaet al. 2007] [Andert 2009]. Esses e outros trabalhos serão mais bem explorados em umcapítulo posterior.

Além dessa abrangência de possibilidades na representaçãode mapas, os sistemasde visão monocular e estéreo podem ser aplicados na construção de mapas de diferentesambientes: internos [Gallelos & Rives 2010, Chang et al. 2010,Santana & Medeiros2011] e externos [Agrawa et al. 2007, Marks et al. 2009, Andert 2009].

Capítulo 4

Grade de Ocupação e Mapas deElevação

Neste capítulo serão apresentadas de maneira mais detalhadaa representação em Gradede Ocupação e os Mapas de Elevação, que formam o fundamento dométodo de ma-peamento proposto. O foco do capítulo está em como se dá a construção, atualizaçãoe manutenção desses tipos de mapas. Apresentaremos o formalismo matemático proba-bilístico que rege a identificação do estado de ocupação das áreas do ambiente mapeadoe calcula uma estimativa da elevação desses locais, considerando o tratamento dado àsincertezas sensoriais presentes nos dados de medição. Paracada tipo de representaçãoserão abordados alguns trabalhos relacionados à construção, à aplicações e melhoriaspropostas para essas representações.

4.1 Grade de Ocupação

A abordagem de mapeamento em Grade de Ocupação se apresenta como uma repre-sentação estocástica das informações espaciais de um ambiente. Cada célula da grademantém uma estimativa probabilística do estado de ocupaçãodo lugar por ela represen-tado, que pode ser livre, ocupada ou ainda desconhecida ou não mapeada [Elfes 1989]. Afunção estimativa probabilística fornece valores dentro do intervalo [0,1], onde 0 significacélula livre e 1 representa uma célula ocupada.

A construção da grade envolve a determinação dessas estimativas de maneira iterativa,levando-se em conta o conhecimento da pose do robô em cada instante de tempo. Nesteponto, considera-se a hipótese de que as células são estatisticamente independentes, issofavorece a construção eficiente do mapa em Grade de Ocupação.Embora esta não sejauma suposição totalmente verdadeira quando se trata, por exemplo, de células que repre-sentam um mesmo objeto físico, isso não afeta de forma significativa a precisão de ummapa. Portanto, a estimativa de um mapaM pode ser fatorada no produto das probabili-dades de cada célulamn, como mostra matematicamente a Equação 4.1. Por esta equação,percebe-se que a inferência do mapa depende do histórico de todas as poses do robô até oinstante atual,x0:t , e de todas as leituras sensoriais realizadas em cada pose,z0:t .

34 CAPÍTULO 4. GRADE DE OCUPAÇÃO E MAPAS DE ELEVAÇÃO

p(M |x0:t ,z0:t) = ∏n

p(mn|x0:t ,z0,t) (4.1)

As estimativas dos estados das célulasp(mn|x0:t ,z0,t) são obtidas através da inter-pretação dos dados dos sensores, empregando modelos probabilísticos, que tratam deforma adequada as incertezas nas informações espaciais obtidas. Um procedimento deestimação Bayesiano permite a atualização incremental da Grade de Ocupação a partirde novas leituras obtidas de múltiplos sensores, desde vários os pontos de vista. Então,aplicando a Regra de Bayes àp(mn|x0:t ,z0,t), tem-se:

p(mn|x0:t ,z0,t) =p(zt |mn,x0:t ,z0,t−1).p(mn|x0:t ,z0,t−1)

p(zt |x0:t ,z0:t−1)(4.2)

Assumindo-se quezt é independente dex0:t e dez0:t−1, dado que o valor de ocupação demn é conhecido, a Equação 4.2 pode ser simplificada (Equação 4.3).

p(mn|x0:t ,z0,t) =p(zt |mn,xt).p(mn|x0:t ,z0,t−1)

p(zt |x0:t ,z0:t−1)(4.3)

Aplicando a Regra de Bayes ap(zt |mn,xt) tem-se a seguinte equação,

p(zt |mn,xt) =p(mn|zt ,xt).p(zt |xt)

p(mn|xt)(4.4)

Substituindo a Equação 4.4 na Equação 4.3 e assumindo quext não provê qualquer infor-mação a respeito demn se não há medições sensoriaiszt , tem-se,

p(mn|x0:t ,z0:t) =p(mn|zt ,xt).p(zt |xt).p(mn|x0:t−1,z0:t−1)

p(mn).p(zt |x0:t ,z0:t−1)(4.5)

Assumindo-se ainda quemn é uma variável binária, a Equação 4.6 pôde ser derivadausando-se o mesmo raciocínio.

p(¬mn|x0:t ,z0:t) =p(¬mn|zt ,xt).p(zt |xt).p(¬mn|x0:t−1,z0:t−1)

p(¬mn).p(zt |x0:t ,z0:t−1)(4.6)

Dividindo a Equação 4.5 pela Equação 4.6 e aplicando as devidas manipulações algébri-cas, tem-se a seguinte expressão,

p(mn|x0:t ,z0:t)

p(¬mn|x0:t ,z0:t)=

p(mn|zt ,xt).p(¬mn).p(mn|x0:t−1,z0:t−1)

p(¬mn|zt ,xt).p(mn).p(¬mn|x0:t−1,z0:t−1)(4.7)

Sabendo-se quep(¬A)= 1−p(A), pode-se manipular ainda mais a Equação 4.7, chegando-se a Equação 4.8.

p(mn|x0:t ,z0:t)

1− p(mn|x0:t ,z0:t)=

p(mn|zt ,xt)

1− p(mn|zt ,xt).1− p(mn)

p(mn).

p(mn|x0:t−1,z0:t−1)

1− p(mn|x0:t−1,z0:t−1)(4.8)

Por questões de inconsistências numéricas, pode-se representar a Equação 4.8 em sua

4.1. GRADE DE OCUPAÇÃO 35

forma logarítmica (Equação 4.9).

logp(mn|x0:t ,z0:t)

1− p(mn|x0:t ,z0:t)= log

p(mn|zt ,xt)

1− p(mn|zt ,xt)−

− log1− p(mn)

p(mn)+ log

p(mn|x0:t−1,z0:t−1)

1− p(mn|x0:t−1,z0:t−1)(4.9)

Para simplificar, considere,

logp(mn|x0:t ,z0:t)

1− p(mn|x0:t ,z0:t)= ℓt

n

Realizando as devidas substituições, a Equação 4.9 se tranforma na Equação 4.10, pelaqual se dá a atualização do valor de ocupação das células.

ℓtn = log

p(mn|xt ,zt)

1− p(mn|xt ,zt)− log

1− p(mn)

p(mn)+ ℓt−1

n (4.10)

Ondeℓt−1n computa a ocupação da célulamn calculada anteriormente no tempot − 1,

p(mn) é uma constante que inicializa a grade com uma probabilidadede ocupação, quepode ser atribuído um valor de acordo com a densidade dos obstáculos no ambiente,porém, no geral se utilizap(mn) = 0.5. A parte mais importante da Equação 4.10 é aprobabilidadep(mn|xt ,zt), a qual é chamada de modelo inverso do sensor. No próximocapítulo o modelo proposto neste trabalho será devidamenteapresentado, considerandotodo o formalismo estocástico necessário para um bom tratamento de informações rui-dosas, que é o caso das informações oriundas de sensores. A Equação 4.10 realiza itera-tivamente a atualização do valor de ocupação de cada célulamn pertencente ao campo devisão do sensor, a cada nova leitura sensorial.

O valor da probabilidade de ocupação de uma célulamn pode ser recuperado facil-mente através da Equação 4.11.

p(mn|x0:t ,z0:t) = 1− 11+exp(ℓt

n)(4.11)

4.1.1 Modelo Probabilístico do Sensor

O modelo probabilístico do sensor deve refletir o seu comportamento, considerandosuas incertezas. Na literatura é comum encontrar a nomenclaturamodelo inverso do sen-sor [Thrun et al. 2005, Hahnel 2004, Stachniss 2006]. Esse modelo deve retornar o valorde p(mn|xt ,zt), o qual fará parte da função de atualização da probabilidadede ocupaçãodo mapa (Equação 4.10).

Os modelos baseados nas funções gaussianas se mostram interessantes quando se estátratando de sensores ruidosos. As técnicas Gaussianas compartilham a ideia de que adensidade de probabilidade de que algo aconteça é representada por uma distribuiçãonormal. Essa distribuição foi estudada pela primeira vez noséculo XVIII, quando foiobservado que padrões de erros e medidas seguiam uma distribuição simétrica em forma


de sino [Hines et al. 2006]. A Equação 4.12 expõe a função de densidade de probabilidadede uma Distribuição Normal unidimensional.

p(x) =1√2πσ

.exp

(

−12(x−µ)2

σ2

)

(4.12)

Na equação acima,x é a variável analisada (também chamada de variável aleatória) commédiaµ e variânciaσ2. Frequentemente, se observa na literatura essa expressão em suaforma abreviadaN (x;µ,σ2), a qual especifica a variável aleatória, sua média e sua variân-cia. A Figura 4.1 esboça graficamente uma distribuição normal de médiaµ= 3 e variânciaσ2 = 0.15.

2 2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 40

0.05

0.1

0.15

0.2

0.25

0.3

0.35

x

P(x

)

Distribuição Normal − µ = 3, σ2 = 0.15

Figura 4.1: Gráfico da Distribuição Normal.

Em geral, os modelos probabilísticos Gaussianos para sensores que medem distânciacaracterizam três regiões principais: 1) região de baixa probabilidade de ocupação ouregião possivelmente livre; 2) região possivelmente ocupada; 3) região fora do alcance dosensor. A Figura 4.2 ilustra resultados típicos de um modelounidimensional gaussianode sensor baseado na Equação 4.12, derivados de medições de distância de um sensor.As regiões de menor valor de probabilidade representam áreas possivelmente livres, asáreas de pico representam os locais possivelmente ocupadospor obstáculos e as regiõescom valor de probabilidade 0.5 representam áreas fora do alcance do campo de visão dosensor, isto é, áreas não mapeadas.

Porém, essa modelagem pode ser mais sofisticada com o uso de uma DistribuiçãoNormal bivariada, que estende a derivação de um modelo a duasdimensões espaciais(Equação 4.13).

p(x1,x2) =1

2πσ1σ2.exp

(

−12

(

(x1−µ1)2

σ21

+(x2−µ2)

2

σ22

))

(4.13)

Essa distribuição é interessante quando o sensor se caracteriza por ter incertezas em maisde uma variável. Por exemplo, os sonares apresentam incertezas tanto na medição dedistâncias como no seu ângulo de orientação, logo, os sonares podem ser modelados por


10 15 20 25 30 35 40 45 500

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Distância medida(m)

P(m

n|zt, x

t)

Modelo Gaussiano 1D de sensor

Figura 4.2: Modelo de medição sensorial. Valores de ocupação para medições de 20m,30m e 40m. O valor de ocupação se dá com as médias (medidas) e variâncias (erros) dasmedições.

uma distribuição normal bivariada, onde as variáveis de análise são à distância e o ângulode orientação. A Figura 4.3 esboça um gráfico típico da modelagem de um sensor dedistância com incertezas na medida de profundidade e no ângulo de orientação.

010

2030

4050

6070

80

010

2030

4050

6070

80

0.48

0.49

0.5

0.51

0.52

Modelo Gaussiano 2D de sensor

P(m

n|zt, x

t)

Figura 4.3: Modelagem Gaussiana bidimensional de um sensor.

Essas são as funções probabilísticas mais comuns na modelagem de sensores no ma-peamento em Grade de Ocupação. No próximo capítulo, será exposto o modelo propostoneste trabalho, o qual tem como objetivo dar o tratamento adequado aos ruídos e in-certezas provenientes das imagens capturadas pelo sistemade câmeras estéreo.

4.1.2 Algoritmo de Mapeamento em Grade de Ocupação

Em forma de procedimento o mapeamento em Grade de Ocupação pode ser arranjadode acordo com o Algoritmo 1. O pseudocódigo apresentado estábaseado no exemploexposto por Thrun et al. (2005).


Algoritmo 1 : mapeamento_em_grade_de_ocupação({ℓt−1n },xt ,zt)

Entrada: {ℓt−1n }, xt , zt .

Saída: {ℓtn}.

para cada célula mn pertence ao mapafaça

semn está dentro do campo de visão do sensorentão

calculep(mn|zt ,xt) (modelo inverso do sensor);

atualize o valor da célulamn comℓtn = log p(mn|xt ,zt)

1−p(mn|xt ,zt)− log 1−p(mn)

p(mn)+ ℓt−1

n ;

senão

ℓtn = ℓt−1

n ;

fim sefim para

O algoritmo apresenta como dados de entrada{ℓt−1n }, que são os valores de ocupação

de todas as células calculados previamente,xt , que é vetor com a posição e orientaçãodo robô ezt , que é o resultado da medição sensorial; e como saída{ℓt

n} que representaos valores de ocupação atualizados. Existe um laço que varretodas as células do mapa etesta se estão no campo visual do sensor do robô. Caso a célula esteja sendo alcançadapelo sensor o seu valor de ocupação é atualizado de acordo como modelo adotado para osensor através da Equação 4.10. Senão, permanece com o valorde ocupação previamentecalculado no passot −1.

Não há necessidade de varrer todo o mapa em grade para verificar células dentroou fora do campo de visão do sensor. Na prática, se faz uma heurística simples paraque somente as células alcançadas pelo sensor sejam percorridas e atualizadas, evitandoassim, maior tempo de processamento.


Uma importante característica do mapeamento em Grade de Ocupação é que ele podeser realizado por robôs com distintos sensores. A construção de um mapa em gradenão se restringe a um determinado tipo de sensor. Investigando os sensores mais citadosnesse trabalho (sonar, lasers e câmeras), é fácil encontrarna literatura inúmeras referên-cias que mensionam a construção de mapas em grade com esses dispositivos. Como jádeclarado em um capítulo anterior, os primeiros trabalhos em Grade de Ocupação surgi-ram na década de 1980 [Elfes 1987][Moravec 1988][Elfes 1989]. Esses primeiros estudosforam elaborados com robôs equipados com sonares. Ainda hoje esses sensores são uti-lizados nesse tipo mapeamento, apesar de eles apresentaremsignificantes falhas em suasmedições. Gupta et al. (2007), por exemplo, utilizaram o mapeamento em Grade de Ocu-pação a partir de informações coletadas por sonares para mapear ambientes dinâmicos.Uma rede neural é aplicada para que as mudanças percebidas noambiente sejam tratadasde forma adequada e expressas corretamente no mapa em grade.


Porém, os sonares estão desuso por conta de suas deficiências, pelo barateamento desensores mais precisos e pelo desenvolvimento de novas alternativas para a percepçãode ambientes. Outra opção para mapeamento em grade é o uso de lasers. Esses sãosensores precisos, de longo alcance e que podem fornecer dados suficientes para se al-cançar a construção de mapas bem detalhados. Alguns trabalhos com laser podem sercitados. Konrad et al. (2011), por exemplo, implementaram um sistema de mapeamentoem Grade de Ocupação de grandes áreas através um veículo equipado com um laser. JáShi et al. (2010), apresentaram uma técnica de mapeamento semântico a partir de umaGrade de Ocupação criada com dados captados por um laser. Os autores apresentaram omapa semântico em grade chamado deSemantic Grid Map, cujo o objetivo é facilitar aclassificação de ambientes em corredores ou salas (escritórios).

O uso de câmeras na construção de mapas em Grade de Ocupação é bem frequentenas pesquisas mais atuais. Esses dispositivos se destacam pelo seu baixo custo e pelagrande quantidade de informações que podem ser aproveitadas a partir de uma coleta dedados. Desde sistemas monoculares até sistemas omnidirecionais podem ser aplicados namontagem de mapas em Grade de Ocupação. Choi & Oh (2006), por exemplo, aplicarama técnica de sonar visual às imagens capturadas por um sistema de visão monocular efizeram a associação desses dados de distância através de um algoritmo baseado na técnicachamadaIterative Closest Point(ICP), para produzir um mapa em Grade de Ocupação.

Em seu trabalho de doutorado, Santana (2011) utilizou um robô equipado com umaúnica câmera na construção de um mapa híbrido de características e Grade de Ocupação.Enquanto um procedimento de localização e mapeamento simultâneos está sendo exe-cutado sobre um mapa de características, uma estrutura em Grade de Ocupação 2D foiconstruída em paralelo a partir de informações de imagens segmentadas. De acordo como autor, o mapa em grade serve para realização de um planejamento de caminhos comdesvio de obstáculos de forma mais direta.

Quando se trata de sistemas de visão estéreo em mapeamento emGrade de Ocupação,deve-se voltar no tempo e mencionar o trabalho de Moravec (1996). Este foi o primeirotrabalho em Grade de Ocupação com visão estéreo. Além disso,Moravec (1996) tambémintroduziu a ideia da Grade de Ocupação tridimensional chamada no trabalho de Grade deEvidência (Evidence Grid), por ser baseada na Teoria da Evidência de Dempster-Shafer,diferente da abordagem Bayesiana proposta por Elfes (1989).

Vários trabalhos mais recentes que destacam o uso de sistemas de visão estéreo po-dem ser citados. No trabalho de Andert (2009), por exemplo, um aeromodelo munidode um sistema estéreo foi utilizado para mapear ambientes externos em uma Grade deOcupação tridimensional. Este trabalho mostra com certa profundidade uma interessanteabordagem na construção de mapas em Grade de Ocupação 3D. Em outro interessantetrabalho, Gallelos & Rives (2010) implementaram o mapeamento em Grade de Ocupaçãoem um robô provido de um laser e uma câmera omnidirecional.

Diversas são as possibilidades de sensores utilizados no mapeamento em Grade deOcupação, incluindo a fusão de informações providas de distintas fontes. Uma nova eeficiente alternativa no mapeamento em Grade de Ocupação surge com o uso do Mi-crosoft Kinect (câmeras RGB-D), um dispositivo que combina uma câmera com sensorinfravermelho em uma única estrutura. Várias são as pesquisas que se aproveitam dessa


interessante combinação de informações para realizar o mapeamento de ambientes sejaem Grade de Ocupação ou em outras forma de representação [Georgiev et al. 2011, Pirkeret al. 2011, Einhorn et al. 2011]. Já existem bibliotecas de código livre com compatibil-idade para diferentes plataformas que atraem ainda mais o uso desses dispositivos empesquisas na Robótica.

São inúmeras as possibilidades de aplicação dos mapas em Grade de Ocupação, aquiforam mencionados apenas alguns exemplos, porém vários outros trabalhos podem serencontrados na literatura. Thrun et al. (2005) afirmaram quea principal utilidade da téc-nica de mapeamento em Grade de Ocupação está no pós-processamento, ou seja, no quese pode realizar a partir do mapa resultante. Com o processo demapeamento concluído aGrade de Ocupação pode ser útil para várias aplicações como:planejamento de caminhos,navegação, desvio de obstáculos, localização, entre outras.

Por exemplo, Lai e colegas [Lai et al. 2006] implementaram ummétodo prático deplanejamento de caminhos para robôs móveis em ambientes desconhecidos. Eles uti-lizaram uma instância modificada do algoritmo A* sobre um mapa em Grade de Ocupaçãoparcialmente construído para realizar um planejamento de caminhos de forma incremen-tal. A cada nova medição sensorial incorporada ao mapa o algoritmo busca o melhor ca-minho a ser seguido. Os autores apresentaram no final do trabalho inúmeros experimentosratificando a factibilidade do método proposto. Cherubini & Chaumette (2011) apresen-taram em seu trabalho um framework para navegação e desvio deobstáculos baseado emum sistema de fusão sensorial composto por uma câmera e um laser. A navegação con-siste em seguir um caminho tomado a partir de um conjunto de imagens, enquanto que odesvio de obstáculos é realizado com o auxílio de um mapa em grade construído a partirdo sensor laser.

No contexto do problema de localização, Dryanovski et al. (2011) apresentaram umaabordagem para solucionar o problema do robô sequestrado. Aabordagem proposta uti-liza um mapa em Grade de Ocupação para representar os dados sensoriais capturados porum sensor laser. Tal mapa é posteriormente utilizado em conjunto com outras técnicaspara inferir uma localização precisa para o robô.

Um dos grandes desafios no mapeamento em Grade de Ocupação está no mapea-mento de ambientes muito grandes ou mesmo no mapeamento de ambientes com riquezade detalhes. Essas duas possibilidades introduzem um pontofundamental no mapeamentoem Grade de Ocupação, que por muitas vezes é fortemente assinalado como a principaldesvantagem dessa abordagem: o custo computacional. O mapeamento de ambientes comgrandes dimensões e o mapeamento detalhado requerem um razoável poder computa-cional para serem construídos e processados, além de necessitarem de uma grande quan-tidade de memória para serem armazenados principalmente emuma representação 3D.Diante desses problemas, ultimamente surgiram pesquisas que lidam diretamente essesfatores para encontrar uma solução plausível.

Dryanovski e colegas [Dryanovski et al. 2011] apresentaramuma abordagem para omapeamento 3D usando uma Grade de Ocupação multi-volume ou MVOG (Multi-VolumeOccupancy Grid). A MVOG armazena explicitamente informações sobre a ocupação deespaços 3D. Essa proposta supera as abordagens tradicionais probabilísticas existentes demapeamento 3D em termos de uso de memória, devido ao fato de que as observações

4.2. MAPAS DE ELEVAÇÃO 41

sensoriais são agrupadas em volumes verticais contínuos para economizar espaço. Odesempenho da abordagem proposta é analisado por meio de experimentos em ambientesinteriores e exteriores com um robô aéreo.

Ainda dentro das representações tridimensionais, Wurm et al. (2010) expuseram umaabordagem para a modelagem de ambientes 3D baseados em octrees utilizando uma esti-mativa de ocupação probabilística denominada de OctoMap. Atécnica utilizada é capazde representar modelos 3D completos, incluindo áreas livres e desconhecidas. A abor-dagem foi bem avaliada utilizando-se diferentes conjuntosde dados reais e simulados. Osresultados demonstram que a proposta é útil para modelar os dados probabilisticamente,enquanto, ao mesmo tempo, mantem a exigência de memória no mínimo.

Outra interessante pesquisa publicada por Einhorn et al. (2011), traz uma nova técnicade mapeamento de ambientes que escolhe a resolução de cada célula adaptativamente pelafusão ou divisão das células, de acordo com uma modelagem estatística apresentada pelospesquisadores. Os autores argumentam que essa abordagem permite uma implementaçãomais genérica de mapas 2D, 3D e até de mais alta dimensão usando o mesmo algoritmo.Com essa ideia é possível diminuir o custo computacional relativo ao armazenamento deum mapa em grade pela fusão de células com medições idênticas.

4.2 Mapas de Elevação

A representação em grade de ocupação é uma interessante ferramenta para representarinformações sobre de ocupação de lugares de um ambiente. E pode ser utilizada tambémna representação de informações tridimensionais. Desde a década de 1996 com Moravec(1996), pouco depois do surgimento do mapeamento em grade deocupação 2D, até anosmais atuais, como no trabalho de Andert (2009), pesquisadores introduziram a ideia demodelar o espaço tridimensional dos robôs em uma grade de ocupação 3D.

O mapeamento tridimensional dos ambientes foi pensado principalmente para os ca-sos onde o terreno de navegação dos robôs não é plano, e nos casos onde é necessário queseja realizada uma navegação precisa entre os objetos, considerando a altura deles dentrode um ambiente. Além disso, Liu et al. (2001) apresentam duasimportantes vantagensque justificam a construção de modelos 3D. Primeira, mapas 3Dfacilitam a solução doproblema da associação de dados, visto que os modelos 3D são mais ricos que os 2D,portanto apresentam menos ambiguidades. Isso facilita a identificação e distinção de lu-gares no processo de mapeamento. Segunda, os mapas 3D são interessantes quando omapeamento também for utilizado em outras atividades. Modelos 3D são muito maisadequados para os usuários remotos interessados no interior de um edifício tais como ar-quitetos, equipes de resgate humanos, ou bombeiros que gostariam de se familiarizar comum ambiente antes de entrar.

Porém, existe uma grande dificuldade no mapeamento 3D quandoo objetivo é repre-sentar o ambiente em uma grade de ocupação tridimensional, principalmente ambientescom grandes dimensões. Perceba que para isso seria necessária uma estrutura 3D ondecada lugar do ambiente tridimensional seria representado por um cubo, também chamadode voxel (em inglês,volumetric pixel), o que pode representar a necessidade uma degrande quantidade de processamento e memória na construçãoe armazenamento desse


mapa (ver Figura 4.4). Desconsiderando qualquer tipo de otimização, uma estrutura paraarmazenar a grade 3D mostrada na Figura 4.4 deveria conter pelo menos 216 elementos(12x6x3).

12

6

3

Figura 4.4: Ilustração da representação em grade de ocupação 3D.

Para evitar essa grande demanda de recursos de processamento e memória, algunspesquisadores propuseram uma solução já usada no mapeamento de terrenos por imagensde radares, os mapas de elevação ou mapas 2,5-D. Os mapas de elevação são úteis paramodelar o espaço 3D de um robô móvel, de uma maneira compacta.Esta representaçãomantem uma grade bidimensional, onde cada célula armazena aaltura ou elevação doterreno no ponto mapeado [Pfaff et al. 2007] (Figura 4.5). Usando o mesmo exemplo daFigura 4.4, uma grade de elevação para representar a mesma situação deveria conter pelomenos 72 (12x6) elementos, onde cada elemento teria um valorde elevação associado,indicando a altura dos obstáculos.

A modelagem e interpretação dos dados sensoriais para a construção desse tipo demapa não é guiada por uma formulação padrão, como no caso dos mapas baseados emgrade de ocupação no âmbito da robótica. Diferentes formulações são propostas para ainicialização e atualização dos valores de elevação das células, a partir de distintos sen-sores. Aqui, será focada a abordagem baseada no Filtro de Kalman, a mesma ferramentautilizada por Pfaff et al. (2007).

4.2.1 Filtro de Kalman

O Filtro de Kalman (FK) é um conjunto de equações matemáticasas quais definemum processo eficiente de estimação, minizando o erro de estado. Através da análise davariável denominada variável de observação, outra variável não observável, a variável deestado, pode ser estimada eficientemente [Kalman 1960]. O Filtro de Kalman padrãopresupõe que uma determinada variável a ser estimada tenha seu modelo linear e quepossa ser descrito sob a forma de um sistema de equações de estado (Equação 4.14).


5 3h

2 1h

71h

2h

1h

12

6

Figura 4.5: Representação em grade de ocupação 2.5D. É necessária uma estrutura dedados de 72 elementos para mapear o ambiente ilustrado.

{

st = Atst−1+Btut +δt

zt = Ctst + γt(4.14)

Ondes∈ Rn é o vetor de estados do sistema;ut ∈ R

l é o vetor das entradas de sinais decontrole;zt ∈ R

m é o vetor com as medições sensoriais; a matrizAt , de tamanhon×né a matriz de transição de estados;Bt , de dimensõesn× l , é a matriz de coeficientes deentrada; a matrizCt , de tamanhom× n, é chamada de matriz de observação;δt ∈ R

n

representa o vetor de ruídos do processo eγt ∈Rm é o vetor de erros de medição;t e t −1

representam os instantes de tempo atual e anterior respectivamente.

O filtro é dividido em duas etapas: predição e atualização. A etapa de predição uti-liza o modelo evolutivo do sistema e as propriedades estatísticas dos ruídos presentes nosistema. Já a etapa de atualização leva em conta medições sensoriais para computar umanova estimativa atualizada dos dados estimados na predição. O Algoritmo 2 mostra ospassos do Filtro de Kalman padrão. As entadas do algoritmo são: o estado do sistemaµt−1 no tempo instante anterior; a matriz de covariânciaΣt−1, que descreve o ruído deestado no instantet − 1; os sinais de controleut ; e as mediçõeszt . A saída será umaestimativa atualizada do estado,µt , e sua convariância,Σt .

Algoritmo 2 : Filtro de Kalman

Entrada: µt−1,Σt−1,ut , zt1

Saída: µt , Σt2

µ̄t = Atµt−1+Btut ;3

Σ̄t = AtΣt−1ATt +Rt ;4

Kt = Σ̄tCTt (Ct Σ̄tCT

t +Qt)−1;5

µt = µ̄t +Kt(zt −Ct µ̄t);6

Σt = (I −KtCt)Σ̄t7


As linas 3 e 4 compõem a etapa de predição, onde é realizada a computação do estadodo sistema ¯µt e os ruídos inerentes ao mesmoΣ̄t , considerando o estado passado. Amédiaµ̄t é conseguida pela aplicação do sinal de controleut ao modelo determinísticode transição de estado. A covariância,Σ̄t , é calculada através da matriz de transição deestadoAt , a qual expressa a dependência entre o estado atual com o estado anterior. Aslinhas de 5 a 7 fazem parte da etapa de atualização, onde ¯µt é transformada emµt pelaincorporação da mediçãozt . A variávelKt , chamada de ganho de Kalman, especifica oquanto uma nova medição influencia na nova estimativa do estado,µt , e sua variânciaΣt .

No contexto do mapa de elevação as variáveis a serem estimadas são a elevação deuma célula, representada pela médiaµ0:t , e sua variância,σ2

0:t , considerando o históricodas estimativas passadas. O passo de predição do Filtro de Kalman não causa modifi-cações nos valores de elevação e variância previamente calculados, visto que esta etapanão considera as novas medições de altura e variância realizadas. Logo, a predição podeser descrita pelas Equações 4.15 e 4.16.

µ̄0:t = µ0:t−1 (4.15)

σ̄20:t = σ2

0:t−1 (4.16)

A cada nova medição do sistema visual devem ser derivadas a altura de um lugar,agora representada porht , e sua variância,σ2

t , que serão inseridas na etapa de atualizaçãoda formulação do Filtro de Kalman para gerar uma nova estimativa da elevação da célula esua variância. Na fase de atualização, o primeiro passo do algoritmo é o cálculo do ganhode Kalman,Kt , como descrito na linha 5 do Algoritmo 2. Considera-seCt = 1, pois nãoinfluencia o valor da medição sensorial, eQt = σ2

t a variância dessa nova medição. Comisso, o cálculo deKt passa a ser feito pela Equação 4.17.

Kt =σ̄2

0:t

σ̄20:t +σ2

t(4.17)

Ou, aplicando-se as igualdades das Equações 4.15 e 4.16, tem-se a Equação 4.18:

Kt =σ2

0:t−1

σ20:t−1+σ2

t(4.18)

Neste ponto, as novas estimativas da elevação,µ0:t , e sua variância,σ20:t , podem ser calcu-

ladas, levando-se em conta a nova medição sensorial,ht , tomada no tempot, e sua variân-cia σ2

t . A partir das equações descritas nas linhas 6 e 7 do Algoritmo2, pode-se deduziras expressões de atualização descritas pelas Equações 4.19e 4.20, as quais computamas novas estimativas de elevação de uma célula e sua variância, utilizando-se o ganho deKalman dado pela Equação 4.18 e fazendo-se as devidas manipulalções matemáticas.

µ0:t =σ2

t µ0:t−1+σ20:t−1ht

σ20:t−1+σ2

t(4.19)


σ20:t =

σ20:t−1σ2

t

σ20:t−1+σ2

t(4.20)


Os primeiros trabalhos baseados em mapas de elevação no contexto da robótica foramapresentados por Bares et al. (1989) e Hebert et al. (1989). Estes trabalhos estão voltadosà navegação de robôs ou sondas planetárias com pernas. A partir das ideias apresentadasnessas investigações novas pesquisas foram surgindo.

Assim como nos mapas em grade de ocupação, diferentes sensores podem ser utiliza-dos para o mapeamento em grade de elevação, porém se destacamos lasers e as câmeras.Ye & Borenstein (2003) propõem um algoritmo para adquirir mapas de elevação comum veículo móvel equipado com um sensor laser. Eles apresentaram a formulação deuma filtragem especial para eliminar erros de medição ou ruídos do sensor laser e dosmovimentos do robô. Em uma pesquisa mais recente, Kwon et al.(2010) também apre-sentaram sua proposta para representação de ambientes com mapas de elevação a partirde informações de um laser. Eles utilizam o mapa para realizar a localização do robô como método de Monte Carlo (Monte Carlo Localization) com base na associação de dadossensoriais com o mapa adquirido.

Quando a principal fonte sensorial são as câmera, várias técnicas podem ser encon-tradas na literatura. Lacroix et al. (2002) extraíram um mapa de elevação a partir deimagens estéreo com o objetivo final de prover a navegação outdoor de um robô. JáHygounenc et al. (2004) construíram um mapa de elevação com um dirigível autônomoprovido de um sistema de visão estéreo. Eles propuseram um algoritmo para detecção decaracterísticas e realizar a correspondência oumatchingentre mapas localmente construí-dos usando essas características. Cappalunga et al. (2010) implementaram um sistema demapeamento em mapa de elevação com visão estéreo, onde eles se fundamentaram emum algoritmo biologicamente inspirado para segmentar pontos no terreno.

Como já mencionado, a construção dos mapas de elevação não obedece a uma formu-lação básica como é o caso das grades de ocupação. Por esse motivo, diferentes aborda-gens são adotadas na construção desse tipo de representação. Aqui, serão evidenciadasduas interessantes abordagens estocásticas, a primeira proposta por Pfaff et al. (2007) e asegunda apresentada por Marks et al. (2009). Pfaff et al. (2007) apresentam a construçãode mapas de elevação baseado em sensor laser. Em sua proposta, os autores consideramuma abordagem probabilística baseada no Filtro de Kalman para construir o mapa. Aatribuição de valores de elevação à cada célula do mapa é calculada e atualizada a cadanova medição de elevação provida pelos sensores, além disso, uma medida de variância,que indica o intervalo de variação dessa elevação, também é computada obedecendo asimprecisões sensoriais. Assim, cada célula registra uma média e uma variância da ele-vação do lugar representado.

Marks et al. (2009) propuseram uma abordagem de construção de mapas de elevação,a qual é aplicada em um algoritmo de SLAM, denominado por elesde Gamma-SLAM.O mapa é composto de células quadradas, onde cada uma armazena um valor de altura


atribuído de acordo com uma distribuição Gaussiana, com umaprecisão (inversa da va-riância) e média desconhecida. A distribuição utilizada é aGama, daí vem o nome doalgoritmo de SLAM proposto. O mapa é utilizado para que o robôconheça lugares pos-síveis de serem atravessados de acordo com um custo de navegação (o termo usado eminglês étraversability). Segundo os pesquisadores, o algoritmo de mapeamento rodaemtempo real mesmo em processadores convencionais.

Neste trabalho foi adotada a abordagem de Pfaff et al. (2007), a qual será explicadade forma detalhada no capítulo posterior, por dar a possibilidade de expressar uma esti-mativa concreta da elevação de um espaço em medidas métricas, o que é uma informaçãointeressante no processo de tomada de decisões durante a navegação autônoma.

4.3 Considerações

Neste capítulo foram apresentadas as definições formais da representação em gradede ocupação e dos mapas de elevação. Diante do exposto neste capítulo, é interessanteressaltar, que a grade de ocupação e a grade de elevação armazenam informações dife-rentes. Uma, a grade de ocupação, registra informações sobre a probabilidade de ocu-pação de uma célula, ou seja, a possibilidade de existir um obstáculo em um determinadolugar do ambiente. A segunda, grade de elevação, considera aexistência de um obstáculoem um determinado lugar com certa altura. Perceba que a gradede elevação ignora apossibilidade de existência de obstáculo, ela assume a existência de obstáculo. Isso é in-desejável por desprezar as influências das incertezas presentes nas informações sensoriaisna avaliação da existência de obstáculos.

Este trabalho expõe uma representação em grade com informações de ocupação e ele-vação dos lugares mapeados. A abordagem adotada considera uma formulação estocásticatanto para a ocupação das células quanto para a estimação da elevação, manipulando deforma adequada incertezas nas presentes informações sensoriais. Cada célula, registra aprobabilidade de estar ocupada, a altura do local mapeado e avariância dessa altura, quepode ser considerada uma medida de confiabilidade. Para isso, foi adotada uma formu-lação estocástica baseada no Filtro de Kalman, a qual será abordada no próximo capítulo,onde se dará a explicação aprofundada da proposta deste trabalho.

Capítulo 5

Grade de Ocupação-Elevação

Este capítulo tem como objetivo apresentar o sistema de mapeamento proposto nestetrabalho, com as metodologias e técnicas utilizadas na implementação de cada etapa doframework. De início, será apresentada uma contextualização do sistema de mapeamentoproposto, destacando superficialmente suas características. Em seguida será apresentadaa definição formal da abordagem de representação em grade de ocupação-elevação. Pormeio de um diagrama, serão expostas as técnicas utilizadas para a implementação dasdiferentes partes que compõem o sistema de mapeamento proposto. Posteriormente, cadafase será explorada de forma minuciosa a fim de proporcionar uma correta compreenssãodo projeto como um todo.

5.1 Contextualização

A execução eficiente de tarefas de forma autônoma por robôs móveis está fortementevinculada à quantidade de informações que o robô possui de seu ambiente. A construçãode um mapa em grade de ocupação que possua informações confiáveis sobre a localizaçãode objetos e obstáculos presentes no ambiente do robô, pode contribuir significativamentepara que um robô alcance a autonomia. Quando se requer uma navegação mais precisa,levando-se em conta a altura dos obstáculos e estruturas de um ambiente, é interessanteque o mapeamento em grade seja expandido para o espaço tridimensional. Os mapas3D facilitam a solução de problemas de associação de dados, visto que possuem maiorquantidade de informações, que resulta em menos ambiguidades [Liu et al. 2001]. Alémdisso, são ideais no mapeamento de lugares onde o terreno se apresenta de forma irregular.

Porém, a grande desvantagem dos mapas em grade tridimensional está no seu elevadocusto computacional necessário para construí-los e armazená-los, principalmente quandoo ambiente mapeado é extenso. Uma interessante alternativapara se alcançar a soluçãodesse problema, seria o uso dos mapas de elevação 2,5-D. Estarepresentação mantemuma grade bidimensional, onde cada célula armazena a alturaou elevação do terrenono ponto mapeado, constituindo-se uma forma compacta de mapeamento em grade cominformações tridimensionais.

Existem alguns robôs que possuem a capacidade de transpor certos obstáculos den-tro de uma determinada faixa de altura, principalmente aqueles que são preparados para

48 CAPÍTULO 5. GRADE DE OCUPAÇÃO-ELEVAÇÃO

a navegação em ambientes externos. Um exemplo clássico seria a navegação dos robôsque realizam explorações planetárias, que lidam com diversas dificuldades de movimen-tação em terrenos com diferentes características e desafios. Assim, é interessante queo robô tenha meios de classificar se uma determinada área podeser explorada mesmoque seja povoada por obstáculos. Os mapas de elevação munem os robôs com essa ha-bilidade, permitindo que os lugares mapeados sejam classificados como navegáveis ounão-navegáveis, de acordo com as capacidades locomotoras deles.

É interessante ressaltar, que a grade de ocupação e a grade deelevação armazenaminformações diferentes. A primeira, a grade de ocupação, registra informações sobre aprobabilidade de ocupação de uma célula, ou seja, apossibilidadede existir um obs-táculo em um determinado lugar do ambiente. A última, a gradede elevação,consideraa existência de um obstáculo em um determinado lugar com certa altura. Perceba que agrade de elevação ignora apossibilidadede existência de obstáculo, elaassumea existên-cia de obstáculo. Isso é indesejável por desprezar as influências das incertezas presentesnas informações sensoriais na avaliação da existência de obstáculos.

Diante desse contexto, esse trabalho apresenta um arcabouço para o mapeamento deambientes interno ou externos baseados em informações visuais (providas por um sis-tema de câmeras estéreo) e com uma representação em grade cominformações sobrea ocupação e elevação dos espaços mapeados, que concede a um robô a capacidade declassificar a navegabilidade de uma determinada área do seu ambiente de trabalho, con-siderando suas habilidades motoras. A abordagem desenvolvida está fundamentada emuma formulação estocástica tanto para o cálculo de ocupaçãodas células quanto paraa estimação da elevação, manipulando de forma adequada incertezas presentes nas infor-mações sensoriais. Cada célula registra a probabilidade de estar ocupada, a altura do localmapeado e a variância dessa altura, que pode ser consideradauma medida de confiabili-dade. Para o caso do valor de ocupação é utilizada a formulação padrão apresentada noCapítulo 4, porém com uma modelagem robusta para o tratamentodas incertezas sensori-ais. Já para o valor de elevação é utilizada uma formulação baseada no Filtro de Kalman.Assim, tem-se as vantagens de ambas as representações cobinadas em um só mapa.

5.2 Definição - Grade de Ocupação-Elevação

Definindo de uma maneira mais formal, a grade de ocupação-elevação proposta con-siste de uma grade bidimensionalM de células regularesmn, onden∈N, que armazenama probabilidade de ocupação, a elevação (ou altura) e a variância da elevação de um lugarmapeado do ambiente do robô. Expressando matematicamente,pode ser descrita comomostra a Expressão 5.1.

M = {〈O0:t,n,µ0:t,n,σ20:t,n〉, n= 1, ...,N} (5.1)

OndeN representa o número de células no mapa em grade. Cada célula domapa pode serdescrita por uma tripla, como mostra a Expressão 5.2.

5.2. DEFINIÇÃO - GRADE DE OCUPAÇÃO-ELEVAÇÃO 49

mn = 〈O0:t ,µ0:t ,σ20:t〉 (5.2)

Nesta expressão,O0:t representa o valor de ocupação da célulamn calculado, ou seja,O0:t = p(mn|x0:t ,z0:t); µ0:t computa a estimativa do valor de elevação; eσ2

0:t é o valorda variância da elevação da célula. Essas grandezas são estimadas de forma iterativaseguindo a evolução temporal do mapeamento até o instante detempot. A Figura 5.1ilustra a composição do mapa em grade, de acordo com a especificação acima.

Grade 2D

Ocupação Elevação

Figura 5.1: Formação da grade de ocupação-elevação.

Note que, tanto a estimação da ocupação quanto o cálculo da elevação estão sendorealizados através de ferramentas probabilísticas, as quais permitem o tratamento cor-reto das incertezas inerentes ao sistema perceptivo robótico. O valor de ocupação (leia-se probabilidade de ocupação) é dado por uma função de densidade de probabilidade,p(mn|x0:t ,z0:t), e o valor da elevação é descrito por uma distribuição normalcaracteri-zada por uma médiaµ0:t e uma variânciaσ2

0:t , ou N (µ0:t ,σ20:t). Assim, cada ponto,

PM = (xM,yM,zM) ∀ PM ∈R3, do ambiente do robô é projetado em uma célula pertencente

à grade de ocupação-elevação.Como mencionado anteriormente, uma grade de ocupação, registra informações so-

bre a probabilidade de ocupação de uma célula, ou seja, apossibilidadede existir umobstáculo em um determinado lugar do ambiente. A grade de elevaçãoassumea existên-cia de um obstáculo em um determinado lugar com certa altura.Isso é indesejável pordesprezar as influências das incertezas presentes nas informações sensoriais na avaliaçãoda existência de obstáculos. E mapear um espaço em uma grade de ocupação tridimen-sional demanda grande quantidade de recursos de processamento e memória.


Para solucionar essas restrições, a representação em grade2.5D de ocupação-elevaçãoconsidera uma formulação estocástica tanto para a ocupaçãodas células quanto para a es-timação da elevação (informação da terceira dimensão), manipulando de forma adequadaincertezas nas presentes informações sensoriais, com uma estrutura de dados bidimen-sional, onde cada célula registra a probabilidade de estar ocupada, a altura do local ma-peado e a variância dessa altura, que pode ser considerada uma medida de confiabilidadesobre a altura de um obstáculo.

Com isso, além de possuir uma representação que habilite a execução direta de algo-ritmos de planejamento de caminhos e execução de trajetóriacom desvio de obstáculos(característica da grade de ocupação), o robô terá condições de classificar áreas do seuambiente, definindo se são adequadas para a navegação ou possuem obstáculos grandes osuficiente para impossibilitar tal ação.

5.2.1 Etapas do Mapeamento em Grade de Ocupação-Elevação

O diagrama da Figura 5.2 mostra a sequência das etapas necessárias para se alcançaro mapeamento proposto. De forma resumida essas etapas são decritas a seguir:

• Estimativa da pose: inferência das coordenadas e orientação do robô em relaçãoa algum referencial fixo no mundo. Neste trabalho esta etapa foi implementadaatravés do modelo movimento de odometria.

• Aquisição e interpretação de dados sensoriais: corresponde a ciência que o robô temsobre o seu entorno. Neste caso, através de uma câmera estéreo o robô coleta asinformações e com a manipulação desses dados, são calculadas as coordenadas dospontos pertencentes aos objetos presentes no entorno do robô, em relação ao sis-tema de câmeras. Por meio de processamento de imagens e do modelo geométricodo sistema de câmeras é possível realizar tal estimativa.

• Modelagem sensorial: a partir dos dados resultantes das duas etapas anteriores épossível criar um mapa de ocupação-elevação local de acordocom a modelagemprobabilística proposta, considerando as incertezas das informações sensoriais.

• Integração de dados: através das equações de atualização, responsáveis por atribuiro valor de ocupação e de elevação às células, é possível integrar ou incorporar asinformações do mapeamento local realizado na etapa anterior com as informaçõesjá existentes no mapa em grade global.

A seguir cada uma dessas etapas será explorada de forma detalhada e concisa, acen-tuando as principais técnicas utilizadas e propostas sugeridas.

5.2. DEFINIÇÃO - GRADE DE OCUPAÇÃO-ELEVAÇÃO 51

Figura 5.2: Etapas do mapeamento em grade de ocupação-elevação.


5.3 Posicionamento - Modelagem Cinemática

Como já citado em capítulos anteriores, o mapeamento de ambientes com robôs de-pende de uma estimativa da posição do robô, o ideal seria ter uma localização precisa.Porém, devido a erros sistemáticos e não sistemáticos a situação ideal não pode ser al-cançada. Existem certas técnicas que podem amenizar os erros causados nessa etapa.

Através da modelagem cinemática é possível realizar um cálculo aproximado a res-peito dos movimentos realizados por um robô e, consequentemente, inferir a sua posição.O modelo cinemático tradicional para um robô de drive diferencial, se baseia nos sinaisde controle (geralmente medidas de velocidade linear e velocidade angular) enviados aosmotores para estimar as coordenadas e orientação do robô. Seo robô possui sensores derotação (encoders) acoplados em suas rodas, alternativamente pode-se utilizar as medidasde odometria como base para o cálculo dos movimentos do robô sobre o tempo.

A odometria é comumente obtida pela integração das informações fornecidas por en-coders acoplados aos robôs. A pose é calculada a partir da integração de pulsos lidos dosencoders em intervalos de tempo periódicos (por exemplo, a cada 10ms). Experiênciaspráticas sugerem que a odometria, mesmo que ainda errônea, égeralmente mais precisaque os modelos baseados em velocidades. As duas abordagens sofrem com escorrega-mento e derrapagens, porém o modelo de velocidade é ainda afetado por erros inerentesaos próprios sinais de controle [Thrun et al. 2005]. O modelode movimento de odome-tria se difere por utilizar as medições odométricas como sinais de controle e não comoinformações sensoriais.

Para se analisar essa modelagem, assuma que a Equação 5.3 descreve a evoluçãotemporal da localização do robô.

st = f (st−1,ut) (5.3)

Ondest = (x,y,θ) é a pose (posição e orientação) sendo calculada;ut = (∆l ,∆θ) são ossinais de controle providos pelo sistema de odometria com∆l sendo o deslocamento lineare∆θ o deslocamento angular, ambos executados dentro do intervalo de tempo[t−1, t]. AEquação 5.3 pode ser colocada de forma mais detalhada, como mostra a Equação 5.4.

st = f (st−1,∆l ,∆θ) (5.4)

A Figura 5.3 explicita melhor os parâmetros da equação por meio da representaçãode um robô móvel com acionamento diferencial, o qual possui encoders acoplados emsuas rodas. Dessa figura,r representa o raio das rodas,b diz respeito à distância entreeixos do robô, e∆l l e ∆lr são os deslocamentos lineares das rodas esquerda e direitarespectivamente, e fazem parte da expressão matemática para estimar∆l e ∆θ, comomostram as expressões abaixo.

∆l =∆lr +∆l l

2(5.5)

∆θ =∆lr −∆l l

b(5.6)

5.3. POSICIONAMENTO - MODELAGEM CINEMÁTICA 53

Y

X

y

x

b

r

llD

rlD

lD

qD

rqD

lqD

Figura 5.3: Modelagem cinemática de movimento.

Sabendo-se que∆l l e ∆lr são grandezas valoradas a partir das medidas de odometria, épossível detalhar ainda mais essas equações, baseando-se nos deslocamentos angulares∆θl e ∆θr de cada roda,

∆l =∆θr r +∆θl r

2(5.7)

∆θ =∆θr r −∆θl r

b(5.8)

Pode-se ainda chegar a uma expressão que esteja diretamenterelacionada com as infor-mações fornecidas pelos encoders, sabendo-se que,

∆θl =πNl

Nrese ∆θr =

πNr

Nres(5.9)

OndeNl e Nr são o número de pulsos lidos pelos encoders esquerdo e direito respec-tivamente eNres é a resolução do encoder, que indica o número de pulsos em um girocompleto da roda. Tendo essa sequência de informações a respeito da odometria, é con-veniente expandir a Equação 5.4, com as devidas relações de movimento para as variáveisque representam o estadost do robô, como mostra a Equação 5.10.

xt

yt

θt

=

xt−1

yt−1

θt−1

+

∆l∆θ sin(θt−1+∆θ)− ∆l

∆θ sinθt−1∆l∆θ cos(θt−1)+∆θ)+ ∆l

∆θ cosθt−1

∆θ

(5.10)

Quando não há movimentos angulares ocorrem inconsistências numéricas na Equação 5.10,portanto o modelo passa então a ser descrito pela Equação 5.11, alcançada quando aEquação 5.10 é levada ao limite.

xt

yt

θt

=

xt−1

yt−1

θt−1

+

∆l cosθt−1

∆l sinθt−1

0

(5.11)


É importante relembrar que mesmo sendo mais preciso que o modelo de velocidade, omodelo de odometria é afetado por erros que ocorrem por deslizamentos, escorregamen-tos, eventos não previstos, entre outros, que influenciam namedição dos encoders. Logo,é importante que essas fontes de ruídos sejam consideradas no modelo, como mostra aEquação 5.12.

{

∆θr = ∆θ̂r +N (0,ε2r )

∆θl = ∆θ̂l +N (0,ε2l )

(5.12)

Onde∆θ̂r e ∆θ̂l são as medições de deslocamento angulares realizadas pelosencoders, eN (0,ε2

r ) eN (0,ε2l ) são os erros inerentes a essas medidas, que são representados por uma

distribuição normal de média zero e variânciasε2r e ε2

l . Essas grandezas foram estimadaspor meio de exaustivos experimentos práticos publicados emum trabalho anterior [Souza2008]. O modelo de odometria foi implementado neste trabalho visando uma melhorestimativa das variáveis que descrevem o estado do robô dentro do seu ambiente.

5.4 Aquisição e Interpretação de Dados Sensoriais

A etapa de dedução do mapa de disparidade pode ser subdividida em sub etapas,são elas: aquisição de imagens, calibração estéreo, retificação, correspondência estéreo,cálculo de disparidade, cálculo dos pontos 3D no referencial de câmera para posteriorestimação da distância entre câmera e pontos calculados. Neste trabalho, todo o proces-samento e manipulação de imagens foi realizado por meio da biblioteca OpenCV (OpenSource Computer Vision Library).

5.4.1 Aquisição de Imagens

Na sub etapa de aquisição foi utilizado um sistema de visão estéreo de baixo custonomeado de Minoru 3D (Figura 5.4), cujo funcionamento simultâneo de ambas câmerasno sistema operacional Linux deve ser aliado à API V4L (Video For Linux). O sistemaestéreo pode ser facilmente conectado a qualquer sistema decomputacional com portaUSB.

Figura 5.4: Câmera estéreo Minoru 3D utilizada no mapeamento.

5.4. AQUISIÇÃO E INTERPRETAÇÃO DE DADOS SENSORIAIS 55

A captura das imagens de ambas as câmeras foi realizada por chamadas de funçõesda API V4L, a qual favorece o acesso em baixo nível às câmeras através do barramentoUSB de forma paralela.

5.4.2 Calibração Estéreo

O segundo passo realizado dentro do procedimento de estimação do mapa de dispari-dade é a calibração estéreo, processo pelo qual se computa a relação entre as duas câmerasno espaço tridimensional [Bradski & Kaehler 2008]. O objetivo então é encontrar umamatriz de rotaçãoRe um vetor de translaçãoT que estabelecem relações métricas entre ascâmeras. Esses parâmetros são de fundamental importância para os cálculos de deduçãodas coordenadas dos pontos no mundo a partir de imagens estéreo. Além disso, outrasvariáveis podem ser encontradas também durante esse processo, por exemplo, a distânciafocal, coordenadas de centro de imagens e coeficientes de distorção, os quais são utiliza-dos para retirar as distorções radiais e tangenciais nas imagens, produzidos por defeitosnas lentes das câmeras.

5.4.3 Retificação

Durante o calculo de disparidade é mais fácil se aferir valores de disparidade quandoos planos das duas imagens estão exatamente alinhados, restrição assumida durante aexplicação dada sobre geometria estéreo no Capítulo 3. Porém, um alinhamento perfeitode um sistema estéreo real é raramente conseguido, assim as duas câmeras quase nuncatem os planos de imagens exatamente coplanares. O passo de retificação estéreo temcomo objetivo reprojetar os planos de imagens das duas câmeras tal que eles possam sercoplanares, com as linhas das imagens estando alinhadas em uma configuração paralelafrontal [Bradski & Kaehler 2008]. A retificação contribui para o passo de correspondênciaestéreo restringindo o espaço de busca por pixels correspondentes, para linha epipolar dasimagens. Isso torna a correspondência mais confiável e computacionalmente tratável. AFigura 5.5 mostra a execução da retificação estéreo em imagens capturadas pelo sistemade câmeras empregado nesse trabalho.

Figura 5.5: Processo de retificação estéreo.


5.4.4 Correspondência Estéreo

Após a retificação das imagens, considerando-as agora sobreum mesmo plano, opasso de correspondência pode ser executado. Os pontos correspondentes são computadosapenas sobre as áreas nas quais os campos de visão de ambas as câmeras de sobrepõem.Neste trabalho foi adotada a correspondência baseada na abordagemgraph-cuts, cujosresultados alcançados se mostraram mais ricos em informações úteis para a construçãodo mapa proposto. Detalhes sobre ograph-cutspodem ser encontrados no trabalho deHong & Chen (2004).

Terminada a sub etapa de correspondência estéreo, o cálculode disparidade é auto-maticamente realizado, finalizando a construção do mapa de disparidade também chamadode imagem de profundidade. Uma grande dificuldade que pode ser encontrada no cálculode disparidade, se verifica quando as imagens são pobres em texturas. Neste caso, adetecção de pontos correspondentes se torna mais complexa,o que afeta diretamente aestimação de um mapa de disparidade de qualidade. Esse efeito poderia ser amenizadocom o uso de técnicas de multi-resolução [Gonçalves et al. 2000].

A Figura 5.6 mostra um resultado da estimação do mapa de disparidade, de uma cenaextraída de um experimento realizado em um ambiente interno, utilizandograph-cuts.

(a) (b)

Figura 5.6: Construção do mapa de disparidade.

5.4.5 Cálculo das Coordenadas dos Pontos Detectados

Com o mapa de disparidade estimado é possível agora, através da geometria estéreo,estabelecer as coordenadas dos pontos do mapa de disparidade em relação ao referencialda câmera,Pc = (xc,yc,zc). As equações do Capítulo 3 da seção 3.3.1, utilizadas nessescálculos, podem ser relembradas.

zc =b. fd

(5.13)

xc = zc.(x−x0)

f(5.14)

yc = zc.(y−y0)

f(5.15)

5.5. MODELAGEM SENSORIAL 57

Onded é a disparidade de cada pixel de coordenada(x,y) de uma das imagens (esquerdaou direita),(x0,y0) são as coordenadas do centro da imagem ef é a distância focal dacâmera, que pode ser obtida no processo de calibração, citado anteriormente.

5.5 Modelagem Sensorial

Essa etapa aufere o resultado das etapas anteriores, funde essas informações para obterum valor de ocupação e elevação de acordo com uma formulação estocástica, a qual con-sidera a existência de ruídos inerentes aos dados recebidos, tratando-os de forma ade-quada.

5.5.1 Modelagem Sensorial para Estimar o Valor de Ocupação

No presente trabalho é adotado um modelo probabilístico Gaussiano, o qual modelao comportamento do sensor visual e das suas incertezas inerentes ao cálculo do mapade disparidade. Para isso se faz necessária a computação da distância entre o centrodo sistema estéreo e os pontosPc = (xc,yc,zc) calculados para cada pixel com valor dedisparidade válido inferido na etapa anterior. Essa medidade distância é obtida atravésda Equação 5.16.

lp =√

x2c +y2

c +z2c (5.16)

O modelo inverso do sensor utilizado no cálculo de ocupação de uma célula a partir dadistância calculada é dado pela Equação 5.17.

p(mn|st ,zt) = pocc(l)+

(

k

∆lp√

2π+0.5− pocc(l)

)

exp

{

−12

(

l − lp

∆lp

)2}

(5.17)

com,

pocc=

{

pmin se 0< l ≤ lp

0 sel > lp(5.18)

O parâmetrok pondera a importância de uma única medição realizada e seu valor éatribuído observando-se o comportamento do sensor utilizado, epmin é um valor de ocu-pação mínimo atribuído às células que estão provavelmente livres. A restrição∀l ≥ lmin :p(mn|st ,zt) ∈ [0;1] deve ser satisfeita para assegurar que os valores de probabilidade re-sultantes sejam válidos [Andert 2009]. O erro,∆lp, no cálculo da distância entre a câmeraestéreo e os pontosPc = (xc,yc,zc) no espaço, vistos do referencial de câmera, é calculadopela Equação 5.19.

∆lp = ∆zclp

zc(5.19)


Perceba que essa equação tem uma relação direta com a incerteza presente na estima-tiva da coordenadazc, especificada por∆zc. Essa incerteza, por sua vez, é diretamenteproporcional aos ruídos causados por erros durante o processo de estimação do mapa dedisparidade. A Equação 5.20 mostra como deve ser calculada aincerteza∆zc.

∆zc =z2c

b. f∆d (5.20)

Nessa equação os parâmetros de câmerab (distância entre os centros de projeção) ef (dis-tância focal) são novamente utilizados. Porém, o termo maisimportante dessa equação,que reflete os erros inerentes à estimação do mapa de disparidade, é∆d (em pixels), tam-bém chamado de resolução de profundidade [Xiong & Matthies 1997] ou incremento dedisparidade [Bradski & Kaehler 2008]. Assim, as coordenadaspassam a ser expressas porzc+∆zc, yc+∆yc e xc+∆xc, onde incertezas nas coordenadasxc e yc do pontoPc podemser calculadas de acordo com a Equaçãos 5.21, derivada das Equações 5.14 e 5.15 quandouma entradax+∆d ey+∆d é imputada [Andert 2009].

∆xc = ∆yc = zc∆df

(5.21)

A Figura 5.7 ilustra os efeitos das incertezas sensoriais naestimação de ocupaçãoinferida pelo modelo inverso do sensor da Equação 5.17. Noteque, quanto maior a dis-tância medida entre a câmera até um objetolp, maior será a incerteza dessa medição.Esse efeito pondera o valor de ocupação atribuído ao ponto mapeado, considerando osruídos de processamento estéreo. Na figura estão exemplificados dois caso de mediçõesdistintas:lp = 10me lp = 15m. Para a primeira medição, representada pela curva em ver-melho, a incerteza inerente azc é∆zc = 0.2. A segunda medição, em ciano, tem incerteza∆zc = 0.3

0 2 4 6 8 10 12 14 16 18 200

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Distância [m]

p(m

n|zt, x

t)

Efeitos das Incertezas na Probabilidade de Ocupação

Figura 5.7: Modelo inverso do sensor aplicado ao cálculo de ocupação paralp = 10m elp = 15m.


5.5.2 Modelagem Sensorial para Estimar o Valor de Elevação

Para encontrar o valor de elevação ou altura de uma célula, cuja projeção do pontoPc cai sobre ela, é realizada uma transformação das coordenadas do ponto em relação aosistema de câmera para um ponto,PM, com coordenadas relacionadas a um referencialglobal. Para isso, deve-se considerar a posição da câmera emrelação ao referencial fixono robô e a posição do robô em relação ao referencial global. AFigura 5.8 ilustra osreferenciais de coordenadas envolvidos nas transformações necessárias para o cálculo daaltura de uma célula

MY

MX

MZ

M

RT

Figura 5.8: Referenciais de coordenadas envolvido no mapeamento.

O sistema de referência definido pelos eixos(XM,YM,ZM) representa o referencialglobal fixo no mundo, o sistema de referência definido pelos eixos(XR,YR,ZR) representao referencial do robô e o sistema de referência determinado pelos eixos(Xc,Yc,Zc) repre-senta o referencial da câmera. A transformação homogêneaTR

c calcula as coordenadas dopontoPc no referencial do robô e a transformação homogêneaTM

R estima as coordenadasno referencial global de um ponto expresso no referencial dorobô. Logo, para expres-sar as coordenadas do pontoPc no referencial global deve ser aplicada uma sequência detransformações homogêneas, de acordo com a Equação 5.22.

PM = TMR .TR

c .Pc (5.22)

Com as coordenadas do pontoPc expressas no referencial global definidas porPM =(xM,yM,zM), a altura ou elevação do local do ambiente do robô capturado pela câmerano instantet passa a ser conhecida,ht = zM. Essa estimativa sofre efeito dos ruídoscalculados pelas Equações 5.20 e 5.21, que com as devidas manipulações algébricas daráuma estimativa do erro imposto sobreht , que será expressa como a variância da elevação,σ2

t . A Equação 5.23, extraída a partir das manipulações algébricas citadas, realiza ocálculo do desvio padrãoσt .

σt = ∆zM = ∆yccosα+∆zcsinα (5.23)

Ondeα é o ângulo de orientação dos eixos do referencial da câmera emrelação ao refe-rencial do robô, cujo valor foi escolhido de forma que o campovisual da câmera alcaçasse


a maior área frontal possível, respeitando os intervalos dedistância impostos, e∆yc e∆zc são as incertezas calculadas pelas Equações 5.20 e 5.21. A Figura 5.9 illustra ocomportamento do modelo sensorial para a elevação. Nesta figura, as linhas verticais(verde, vernelha e azul) representam a variação da elevaçãomedida,ht = 2m. Percebaque, a medida que a distância,lp, entre câmera e ponto detectado aumenta, há uma maiorvariação (dada pela Equação 5.23) sobre o valor de elevação estimado.

0 0.5 1 1.5 2 2.5 3 3.5 41.6

1.7

1.8

1.9

2

2.1

2.2

2.3

2.4

Distancia [m]

Allt

ura

[m]

Efeito das incertezas no cálculo de Elevação

Figura 5.9: Comportamento do modelo sensorial para o cálculode elevação de uma célula,levando em consideração as incertezas, para uma madiçãoht = 2m, com distânciaslp =1m, lp = 2m e lp = 3m, σt = 0.032m, σt = 0.13me σt = 0.28m, respectivamente. .

5.5.3 Modelagem das Incertezas e Ruídos Sensoriais

Neste trabalho, foi adotada uma modelagem criteriosa das incertezas que podem afe-tar a qualidade das informações contidas em um mapa de disparidade e que, consequente-mente, podem contribuir de forma negativa na precisão do cálculo dos pontos 3D noespaço, detectados pelo sistema de câmera estéreo. Baseando-se no trabalho de Xiong &Matthies (1997), foi levantada uma investigação dos principais fatores que influenciamna qualidade da estimação de um mapa de disparidade. De acordo com os pesquisadoresduas das principais fontes de erros no cálculo do mapa de disparidade são: efeito de es-corço (foreshortening error) e desalinhamento (misalignment error) do sistema estéreo.A combinação desses erros pode facilmente exceder três décimos de um pixel, o que podeser traduzido em um erro significativo no cálculo delp.

Efeito de escorço

Explicando melhor o erro pelo efeito de escorço (foreshortening error), é interessantea priori saber o significado de escorço, que se refere ao efeito de perspectiva ou ilusão de


ótica que apresenta os objetos em proporções menores do que são na realidade. Isso acon-tece quando o plano de imagem da câmera não está fronto-paralelo à cena 3D, causandocerta deformação da imagem direitaIr em relação a imagem esquerdaIl . A Figura 5.10ilustra a consequência do efeito de escorço.

eix

o ó

ptic

o

eix

o ó

ptic

o

plano da imagem plano da imagem

b

f f

S

ll rl

lOrO

Figura 5.10: O efeito de escorço da superfície não paralelaS é diferente para as duascâmeras: a projeção deSnos planos de imagens tem comprimentos diferentesl l e lr .

O erro causado por essa deformação no cálculo de disparidadepode ser encontradopela Equação 5.24.

∆ef = a.ef (5.24)

Ondea é o gradiente de disparidade eef é chamada de sensibilidade de escorço (fore-shortening sensitivity). O gradiente de disparidadea indica se certas áreas das imagensdireita e esquerda podem ser comparadas e correlacionadas,e pode ser calculado pelaEquação 5.25 [Li & Hu 2002].

a= 2.|(xl

2−xr2)− (xl

1−xr1)|

‖(pl2− pl

1)+(pr2− pr

1)‖(5.25)

pl1 = (xl

1,yl1) e pl

2 = (xl2,y

l2) são pontos na imagem esquerdaIl , enquanto quepr

1 = (xr1,y

r1)

e pr2 = (xr

2,yr2) são pontos na imagem direitaIr . A sensibilidade de escorçoef é definida

pela Equação 5.26.

ef =Σ3

x=−3Σ3y=−3y

(

∂Il∂x

)2

Σ3x=−3Σ3

y=−3

(

∂Il∂x

)2 (5.26)

Esta grandeza mede, em cada pixel, a razão entre a magnitude do erro de disparidade e a


magnitude do gradiente de disparidade [Xiong & Matthies 1997].

Desalinhamento do sistema estéreo

O problema do desalinhamento do sistema estéreo pode ser resolvido através do passode calibração e posterior retificação, explicados anteriormente. Porém, em sistemas robóti-cos desenvolvidos para navegar em terrenos externos é verificada a existência de vibraçõesmecânicas, que muitas vezes podem ser intensas, e podem deturpar a estimativa dosparâmetros de câmera, desalinhado o sistema estéreo, como ilustra a Figura 5.11.

b

plano da imagem plano da imagem

Figura 5.11: Desalinhamento vertical dos planos de imagens.

Os erros causados por esse fator podem ser modelados atravésda computação de umparâmetro de sensibilidade de desalinhamento, definido pela Equação 5.27.

∆em = m.em (5.27)

O parâmetrom representa o desalinhamento vertical e a medida de sensibilidade de de-salinhamento vertical, que pode ser calculada através da Equação 5.28.

em =Σ3

x=−3Σ3y=−3

∂Il∂x

∂Il∂y

Σ3x=−3Σ3

y=−3

(

∂Il∂x

)2 (5.28)

Nos trabalhos de Xiong & Matthies (1997) e Kim et al. (2005) são sugeridos valorespara o desalinhamento verticalm dentro do intervalo[0,11;0,31], mesmo que o sistemaestéreo tenha passado por um estágio de calibração anterior. O valor total do erro inerenteao cálculo do mapa de disparidade, devido aos dois fatores explanados acima pode serobtido através da Equação 5.29.

∆d = ∆ef +∆em (5.29)

Este erro afeta diretamente a estimação das coordenadas dospontos detectados pelo sis-tema de câmeras, como já explicado na subseção 5.5.1, anteriormente. Com essa mode-lagem os dados sensoriais podem ser tratados de forma adequada, levando-se em contaseus ruídos que produzem incertezas, que por sua vez, serão tratadas de maneira corretana construção do mapa em grade de acordo com a formulação probabilística adotada paraestimação da ocupação e elevação.

5.6. INTEGRAÇÃO DE DADOS 63

5.6 Integração de Dados

A fase de integração atualiza os valores de ocupação e elevação de acordo com as for-mulações que serão apresentadas. Aqui, a integração não se refere à operação matemática,mas sim, ao ato de incorporar novas informações à dados já existentes. Nesta etapa as no-vas medições sensoriais são incorporadas ao mapa produzindo novos valores da ocupaçãoe de elevação juntamente com sua variância.

5.6.1 Integração dos Valores de Ocupação

Para os valores de ocupação foi adotada a formulação padrão explicada no Capítulo 4,logo, através da equação de atualização da formulação da grade de ocupação todas ascélulas dentro do campo visual do sistema estéreo devem ter aprobabilidade de ocupaçãoatualizada, a partir do valor retornado pelo modelo sensorial. A equação de atualizaçãoapresentada no Capítulo 4 pode ser relembrada neste ponto.

ℓtn = log

p(mn|xt ,zt)

1− p(mn|xt ,zt)− log

1− p(mn)

p(mn)+ ℓt−1

n (5.30)

Comℓt−1n refletindo a ocupação calculada anteriormente;p(mn) é um valor de inicializa-

ção da grade, neste trabalho foi utilizadop(mn) = 0.5; p(mn|zt ,xt) representa o modeloinverso do sensor (Equação 5.17). O valor da probabilidade de ocupação atualizado deuma célulamn pode ser recuperado através da Equação 5.31.

p(mn|x0:t ,z0:t) = 1− 11+exp(ℓt

n)(5.31)

5.6.2 Integração dos Valores de Elevação

Para os valores relacionados à elevação a atualização é realizada através do Filtro deKalman, o qual permite que uma nova medição de elevaçãoht tomada no tempot e suaincertezaσ2

t sejam incorporadas na estimativa do valor de elevação registrado na grade.As Equações 5.32 e 5.33 relembram as expressões utilizadas para o calculo dos valoresatualizados da elevação e sua variância respectivamente, para uma célula.

µ0:t =σ2

t µ0:t−1+σ20:t−1ht

σ20:t−1+σ2

t(5.32)

σ20:t =

σ20:t−1σ2

t

σ20:t−1+σ2

t(5.33)

Nessa formulação matemática,µ0:t representa o valor de elevação da célula após umaleitura sensorialht ; σ2

0:t se refere à variância deµ0:t atualizada a partir da variância cal-culada da leitura sensorialht ; e por fim,µ0:t−1 e σ2

0:t−1 são os valores de elevação e suavariância estimados no instantet − 1. A formulação apresentada no capítulo anterior erelembrada neste ponto, segue as mesmas ideias apresentadapor Pfaff et al. (2007).


5.6.3 Definição do Campo Visual de Células Atualizáveis

A atualização dos valores de ocupação e elevação se dá de forma iterativa nas célulasque pertencem ao campo visual do sistema estéreo, definido pelo mapa de disparidade.Para isso, este trabalho adota uma expansão do algoritmo de Bresenham para o espaço3D. Para cada pixel(x,y) do mapa de disparidadeDt , com valor de disparidade válido1

é calculado um raio desde o centro da câmera até um pontoPM capturado. Os pontossobre o raio traçado são projetados em uma célula no mapa de ocupação-elevação, asquais terão os valores de ocupação atualizados de acordo comos valores retornados pelomodelo inverso do sensor exposto anteriormente. O raio é percorrido através do algoritmode Bresenham 3D.

O valor de elevação será atualizado na célula correspondente à projeção do pontoPM na grade, considerando o valor de elevação resultante do modelo sensorial adotado.O Algoritmo 3 descreve a sequência de passos realizados paraatualização das célulasno mapa 2,5-D de ocupação-elevação. O algoritmo possui comovariáveis de entrada omapa em gradeM , o mapa de disparidadeDt processado a partir das imagens tomadasno instantet e a pose (coordenadas e orientação) do robô no ambiente. Como saída,o algoritmo retorna o mapaM com as células pertencentes ao campo visual do sensoratualizadas. A variávelc na linha 9 representa o tamanho de uma célula.

Algoritmo 3 : Atualização do Campo VisualEntrada: M, Dt , xt .Saída: M.para cada pixel Dt(x,y) com valor de disparidade válidofaça1

Calcule as coordenadas de mundoPM do ponto detectado;2

Calcule a distâncialp entre a câmera e o ponto detectado (Equação 5.16);3

Trace um raio desde o centro da câmera até o pontoPM;4

// Uso do Algoritmo de Bresenhampara cada ponto do raio, projetado sobre uma célula mn da gradefaça5

Calculel (distância entre câmera e ponto projetado);6

Calcule o valor da probabilidade de ocupação,P(mn|xt ,zt), da célulamn7

(Equação 5.17);

Atualize o valor de ocupação da célulamn na grade (Equação 5.31);8

Atualize o valor de elevação demn (Equação 5.32);9

Atualize o valor da variância da elevação demn (Equação 5.33);10

fim para11

fim para12

1Valores que resultam em profundidades dentro de um intervalo deduzido de acordo com observaçõesfeitas sobre o comportamento do sensor em relação a sua precisão.

5.7. CONCLUSÃO 65

5.7 Conclusão

Neste capítulo foi exposta de maneira aprofundada a proposta deste trabalho. Foidefinida formalmente a grade de ocupação-elevação que tem como objetivo armazenar in-formações sobre a ocupação do ambiente do robô juntamente com a altura dos obstáculosmapeados. Cada etapa do processo de mapeamento proposto foi explicada, considerandoa formulação matemática de cada técnica empregada.

O conjunto de todas as técnicas explicitadas nesse capítuloforma um arcabouço parao mapeamento de ambientes interno ou externos baseados em informações visuais, comuma representação em grade, cujos dados registrados contribuem para que um robô móvelpossa navegar de forma autônoma dentro do seu ambiente, permitindo-o classificar anavegabilidade de uma determinada área do seu espaço, considerando suas habilidadesmotoras.

O próximo capítulo apresenta experimentos reais realizados para demonstrar a factibili-dade do mapeamento proposto. Foi realizado o mapeamento de diferentes ambientes, como fim de mostrar a robustez da proposta tanto para o mapeamentode ambientes internosquanto para ambientes externos.


Capítulo 6

Experimentos e Resultados

Este capítulo tem como objetivo apresentar os resultados dométodo de mapeamento ex-plicado no capítulo anterior. O sistema tem como entrada mapas de disparidades cal-culados através do processamento das imagens capturadas pelas câmeras do sistemaestéreo. Os passos para o mapeamento são realizados de acordo com as etapas expostasno capítulo anterior até se chegar ao resultado final: mapa deocupação-elevação. Serãoapresentados diversos experimentos englobando diferentes situações possíveis de seremencontradas nos ambientes reais, sejam internos ou externos. Para contextualizar os ex-perimentos realizados, o capítulo começará identificando osistema robótico utilizado,seguindo, posteriormente, com os experimentos feitos em umambiente interno e finali-zando com os experimentos alcançando o mapeamento de ambientes externos e mistos(com características de ambientes internos e externos).

6.1 Visão Geral do Sistema Robótico

Na validação do mapeamento proposto foram realizados vários experimentos como robô de drive diferencial Pioneer 3-AT. Essa plataforma robótica foi construída parapossibilitar a navegação em diferentes tipos de terrenos, daí a sigla AT (All Terrains). Orobô está equipado com 16 sonares, sensores de toque (bumpers), motores diferenciais,um sistema de câmera estéreo de baixo custo (Minoru 3D) e um PCembarcado, quepossibilita a comunicação do robô com outras centrais de processamento via comunicaçãoRS-232, porta LAN e Wi-Fi. A Figura 6.1 mostra a plataforma robótica utilizada nosexperimentos deste trabalho.

Neste trabalho o sistema de câmera estéreo foi elegido como fonte única de infor-mações sensoriais externoceptivas para o mapeamento, os demais sensores do robô foramdesconsiderados, bem como o processamento através do PC embarcado. Um notebookcom CPU Intel Core i3, 2.13GHz, com 4GB de memória RAM e HD 500GB, foi conec-tado ao robô, para atuar como central de processamento. Foi instalado o sistema de opera-cional Linux Ubuntu 11.04 para operar com as bibliotecas quehabilitam a manipulaçãodas informações internas do robô (velocidade, leitura de encoders, nível de bateria, etc.)e para lidar com as funções de chamada de sistema necessáriaspara a câmera estéreo.

Como já foi adiantado no capítulo anterior, na aquisição e processamento imagensfoi utilizada a biblioteca de visão computacional OpenCV (Open Source Computer Vi-

68 CAPÍTULO 6. EXPERIMENTOS E RESULTADOS

CâmeraEstéreo

Motores(Drive diferencial)

Sonares

Bumpers

PCEmbarcado

Figura 6.1: Plataforma robótica utilizada nos experimentos.

sion Library), versão 2.3-1 aliada com a API V4L (Video For Linux), a qual possibilitouaquisição simultânea de imagens capturadas.

6.2 Calibração Estéreo

Antes da realização dos experimentos foi realizado o passo de calibração a fim deinferir os parâmetros internos das câmeras, os parâmetros relativos entre câmeras e oscoeficientes de distorção, necessários para eliminar distorções radiais produzidas pelaslentes das câmeras. Para tal foi utilizado o método de Zhang [Zhang 2000], já imple-mentado no OpenCV, cujos resultados pode ser verificados abaixo. A matrixM, chamadade matriz de câmera ou matriz de parâmetros intrínsecos, contém uma estimativa dosparâmetros internos das câmeras, os quais possuem valores praticamente iguais para am-bas as câmeras.

M =

fx 0 cx

0 fy cy

0 0 1

=

439,581 0 159,0440 439,581 113,120 0 1

(6.1)

onde fx = fy é a distância focal das câmeras,cx e cy são as coordenadas o centro daimagem. Os eixos de coordenadas das câmeras estão relacionados de acordo com aEquação 6.2.

6.3. ESTIMATIVA DAS INCERTEZAS VISUAIS 69

Pl = RT(Pr −T) (6.2)

R e T são, respectivamente, a matrix de rotação e o vetor de translação entre as câmeras.Com a etapa de calibração estéreo os seguintes valores foram computados:

R=

0,999 0 −0,0090 1 0

0,009 0 0,999

(6.3)

T =

−6,230,177−0,227

(6.4)

O vetor de translação entre câmeras,T, tem os seus valores expressos em centímetros.Esses parâmetros são de fundamental importância para o cálculo das coordenadas emrelação ao espaço 3D dos pontos capturados pelas câmeras. Além desses, foram estimadosos coeficientes de distorção, os quais são empregados na correção dos efeitos de distorçãodas imagens e na etapa de retificação das imagens, realizado pelo algoritmo de Bouguet[Bradski & Kaehler 2008].

6.3 Estimativa das Incertezas Visuais

Como explicado no capítulo anterior, existem duas fontes de erros importantes, quepodem afetar significativamente a qualidade ou confiabilidade do mapa de disparidadeem um sistema de visão estéreo: efeito de escorço e desalinhamento. Para aferir essasmedidas, experimentos no processo de estimação de mapas de dispadidade foram realiza-dos, considerando as imagens capturadas durante a exploração dos diferentes ambientesmapeamdos. O resultado dessa análise, considerando as formulações explicadas no Capí-tulo 5, seção 5.5.3, podem ser contemplados em seguida, ondeconsta as médias dos dadosestimados.

∆ef = 0,04 (6.5)

∆em = 0,2 (6.6)

Relembrando,∆ef representa o efeito de escorço e∆em identifica o erro causado pelodeslinhamento vertical do sistema estéreo. Essas duas grandezas são combinadas pararesultar na estimativa do incremento de disparidade,∆d, dado em medidas de pixels,como mostra a Equação 6.7.

∆d = ∆ef +∆em = 0,04+0,2= 0,24 (6.7)

Essas estimativas entram no tratamento estocástico dado àsmedições sensoriais vi-suais nos cálculos da probabilidade de ocupação e da elevação no mapa 2,5-D apresentadoneste trabalho.


6.4 Tratamento de Incoerências no Valor de Elevação

Um desafio nos mapas 2,5-D de elevação é representar de forma coerente lugaresque possuem passagens abaixo de alguma estrutura, por exemplo, pontes, dutos, mesas,bancadas, entre outros. A Figura 6.2 ilustra uma situação semelhante às descritas.

Figura 6.2: Cena de uma possível passagem: (a) Mesa de computador; (b) Imagem cap-turada pela câmera do robô; (c) Mapa de disparidade estimado.

Nesta figura o robô se depara com uma mesa de escritório, a qualpossui uma áreaabaixo de sua estrutura não ocupada por obstáculos, e que pode servir de passagem parao robô, dependendo de suas dimensões físicas. Na maioria dostrabalhos com mapas deelevação, essa situação geraria um mapa que desconsideraria essa possibilidade de pas-sagem. Um mapa de elevação tradicional não refletiria a real condição de navegabilidadedo ambiente, visto que o robô utilizado no trabalho poderia passar pela área vazia porbaixo da estrutura da mesa.

Para contornar situações como essas, foi desenvolvida uma heurística simples paraidentificar quando um local do ambiente possui estruturas com lacunas ou passagens pos-síveis de serem exploradas pelo robô que mapeia o ambiente. Durante o mapeamento,os obstáculos detectados acima da altura do robô não foram computados no mapa deocupação-elevação, pelo fato de que eles não fazem parte do espaço navegável do robô.Considerando a mesma situação mostrada na Figura 6.2, foi aplicada a heurística pro-posta, onde o resultado pode ser visualizado na Figura 6.3.

6.4. TRATAMENTO DE INCOERÊNCIAS NO VALOR DE ELEVAÇÃO 71

(b) ( c )

(a)

Figura 6.3: Mapas estimados: (a) Valores de ocupação; (b) valores de elevação semheurística; (c) valores de elevação com heurística.

A subfigura 6.3(a) traz os valores de ocupação da cena mostrada na Figura 6.2, es-timados a partir do processo de mapeamento explicado do capítulo anterior. A barra decores ao lado identifica a probabilidade de ocupação das células de acordo com a cor,células com tendência ao azul escuro representam áreas possivelmente livres; as célulascom tendência ao vermelho são as áreas que têm maior probabilidade de estar ocupadaspor obstáculos; e as células em verde ilustram os lugares ainda não mapeados. O pontoem preto representa o lugar no qual o robô estava no momento dacaptura da imagem.

As subfiguras 6.3(b) e 6.3(c) representam os valores de elevação sem heurística e comheurística respectivamente, estimados a partir do cenárioda Figura 6.2. Os valores deelevação são identificados de acordo com a barra de cores. Assim, células em azul maisescuro representam áreas com pouca ou nenhuma elevação e células mais avermelhadasesboçam áreas com elevações acentuadas, considerando a navegabilidade do ambientepara o robô utilizado. O robô com a sua câmera está representado pelos polígonos emcinza. Na subfigura 6.3(b) a mesa de escritório é representada por várias células comvalores de elevação que chega a aproximadamente 1m. A área livre abaixo da estrutura éconsiderada obstáculo, o que não reflete a real condição de navegabilidade do espaço. Jána subfigura 6.3(c), resultante da aplicação da heurística adotada, percebe-se que há um


espaço livre entre células que possuem valores de elevação acentuados, o que permite odeslocamento do robô por esse trecho. Neste caso, com base nos resultados da heurísticaproposta, o robô pode transitar por baixo da mesa.

6.5 Experimento em Ambiente Interno

Neste e nos demais experimentos, foi utilizada uma estrutura de mapeamento comcélulas de 10×10cm, valores considerados adequados para alcançar uma representaçãorelativamente detalhada [Souza 2008]. O tempo de processamento de um mapa local,construído a partir de um mapa de disparidade computado, foiem média de 20ms. Éimportante ressaltar que o trabalho não está focado em como omapa de disparidade foiestimado, portanto não é considerado o tempo de processamento necessário na inferênciado mapa de disparidade.

Este experimento foi realizado nas dependências do Laboratório de Engenharia deComputação e Automação da Universidade Federal do Rio Grande do Norte. O objetivofoi apresentar o mapeamento de um ambiente estruturado tipicamente encontrado em es-paços interiores. Nesta experiência o robô mapeou uma partede um corredor habitado poralguns obstáculos (armários e terminal de consulta). A Figura 6.4 mostra cenas distintasencontradas pelo robô durante o mapeamento do corredor e a Figura 6.5 apresenta umavisão superior (Google Earth) e detalha, através de uma planta baixa do espaço mapeado.

(a)

(b) ( c)

Figura 6.4: Cenas visualizadas pelo robô durante o mapeamento: (a) Visão do corredor earmários presentes; (b) Portão gradeado; (c) Terminal de consultas.

6.5. EXPERIMENTO EM AMBIENTE INTERNO 73

Figura 6.5: Vistas superiores do ambiente: (a) Visão superior do prédio explorado a par-tir do Google Earthcom latitude -5.842853 e longitude -35.197341; (b)Planta baixa docorredor mapeado.

Neste experimento, o robô se desloca realizando o trajeto indicado pela linha trace-jada da Figura 6.5, composto por movimentos lineares e angulares, o que resultou emuma distância linear percorrida de 15,4m. A grande dificuldade no mapeamento desseambiente esteve no processo de estimação de mapas disparidades, visto que, o corredorera pobre em texturas contrastantes o que dificulta significativamente a inferência de ima-gens de profundidade. Apesar disso, o processo de mapeamento originou uma grade deocupação-elevação coerente com o ambiente, podendo ser aplicada, sem dificuldades, emuma tarefa de navegação autônoma. A Figura 6.6 exibe os resultados alcançados, onde asubfigura 6.6(a) expressa os valores de ocupação, a subfigura6.6(b) exibe os valores deelevação e a subfigura 6.6(c) apresenta os valores das variâncias referentes às elevações.

Na subfigura 6.6(a) os valores de ocupação obedecem a barra decores ao lado, aqual identifica a probabilidade de ocupação de cada célula nomapa, variando de 0 a 1.Logo, as regiões da figura que tendem ao vermelho representamas células (ou espaços doambiente) que têm maior probabilidade de estarem ocupadas por obstáculos; as regiõesem verde claro são os espaços não mapeados, cujas probabilidades de ocupação não in-formam se os espaços mapeados estão livres ou ocupados. Por fim, as regiões em azulescuro representam as células com maior probabilidade de estarem livres. A linha amarelaindica o caminho real realizado pelo robô, de acordo com o modelo de movimento apre-sentado no capítulo anterior. Nesta mesma subfigura, o círculo em amarelo representa omapeamento da entrada verificada pela porta aberta ilustrada na subfigura 6.5(a) e o cír-culo preto representa o mapeamento do portão existente no corredor (ver subfigura 6.4(b)e subfigura 6.5(b)), o qual tinha uma de suas partes aberta.

A subfigura 6.6(b), contendo os valores de elevação, segue asespecificações da barrade cores ao lado. As células mais avermelhadas representam os prováveis obstáculoscom maior altura, no caso, foram limitados à uma altura de até80 cm. As células comtendência a cor azul representam os lugares com elevações mais baixas, incluindo as queestão no nível do plano do solo. A subfigura 6.6(c) apresenta os valores das variânciasdas elevações estimadas, que podem ser consideradas como medidas de confiabilidade


Figura 6.6: Mapeamento em grade de ocupação-elevação para oambiente interno.(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das elevações.

6.6. EXPERIMENTO EM AMBIENTE EXTERNO 75

sobre a altura dos obstáculos. Neste caso, o mapa apresenta variâncias baixas, o quesignifica que as medidas de elevação são relativamente precisas. Assim, em uma tarefa denavegação, o robô pode verificar se um determinado local, possivelmente ocupado por umobstáculo, com uma determinada altura, oscilando no intervalo definido pela sua medidade variância, pode ser superado.

Caso esse mesmo ambiente fosse mapeado em uma grade de ocupação tridimensional,como proposto por Andert (2009) e limitando-se o mapeamentode obstáculo até a alturado robô (80 cm), seria necessária uma estrutura de dados com 250× 50× 8 = 100 milposições, já na abordagem apresentada neste trabalho foi necessária uma estrutura de250×50×3= 35.750 posições, que pode ser usada para mapear além da altura máximado robô sem a necessidade de mais memória.

6.6 Experimento em Ambiente Externo

Para validar o método de mapeamento apresentado também em ambientes externos,foi realizado um novo experimento em um espaço contendo algumas peculiaridades dosespaços exteriores. Neste experimento o robô teve de lidar com arbustos, postes e com umterreno mais irregular. A Figura 6.7 mostra algumas imagenscaptadas pelo robô duranteo seu trajeto no mapeamento.

A Figura 6.8 exibe uma visão geral do espaço mapeado, destacando os principaisobstáculos encontrados. Na subfigura 6.8(b) os círculos verdes representam os arbustose árvores presentes no cenário os pequenos quadrados marrons representam os postesde concreto e a área amarelada identifica o terreno arenoso. Alinha tracejada mostra ocaminho aproximado realizado pelo robô. O resultado do mapeamento executado podeser visualizado na Figura 6.9. A subfigura 6.9(a) apresenta os valores de ocupação, asubfigura 6.9(b) mostra os valores de elevação e a subfigura 6.9(c) exibe os valores devariâncias das elevações. A linha em amarelo na subfigura 6.9(a) representa o trajeto realrealizado pelo robô calculado pelo modelo cinemático de odometria.

Da mesma forma que no experimento anterior, para cada subfigura as barras de coreslaterais identificam os valores das grandezas representadas. O mapa de ocupação-elevaçãoconstruído representa de forma concisa o ambiente real, incluindo seus obstáculos ine-rentes, como, os arbustos e colunas de concreto. Nas subfiguras 6.9(a) e 6.9(b) estãodestacados alguns lugares específicos, cujas cenas podem ser visualizadas. A elipse emamarelo corresponde ao mapeamento do espaço mostrado na subfigura 6.7(a), a elipseem branco representa o mapeamento da cena identificada na subfigura 6.9(d) e o círculoem vermelho representa o mapeamento da cena vista na subfigura 6.9(e). Nota-se que osobstáculos foram detectados sem problemas, e a estimativa de suas alturas foram com-putadas de forma coerente ao cenário real.

Nota-se também, na subfigura 6.9(b), que para as coordenadasx> 200 aparecem maisregiões com elevações entre 0,1m e 0,2m, próximas ao caminhodo robô. Isso ocorre devi-do as irregularidade do terreno arenoso na região mapeada. Porém, seguindo a trajetóriarealizada pelo robô a elevação do terreno favorece a navegação livre, ou seja, não existemelevações significativas no caminho do robô. Isso acontece devido às maiores quantidades


(a)

( c )

(e)

(b)

(d)

(f)

Figura 6.7: Imagens capturadas pelo robô durante o mapeamento.

de informações sensoriais estarem nas regiões frontais ao sistema de câmeras, o que pos-sibilita a atualização frequente do mapa com mais dados oriundos do sensor. Fazendoa mesma comparação do experimento anterior, considerando uma grade tridimensionalapresentada por Andert (2009), seria necessária uma estrutura de 280 mil posições, en-quanto que o mapa construído com o método proposto foi gravado em uma estrutura de105 mil posições.

6.7 Experimento em Ambiente Misto

Para este experimento foi escolhido um ambiente misto, que apresenta cenas típicasde cenários internos e de espaços externos, situado no Núcleo de Tecnologia da Univer-

6.7. EXPERIMENTO EM AMBIENTE MISTO 77

12,6m

(a) (b)

Figura 6.8: Ambiente externo mapeado: (a) Visão superior doambiente, limitado peloretângulo em amarelo (visão do Google Earth) de latitude -5.842677 e longitude -35.19724; (b) Planta baixa.

sidade Federal do Rio Grande do Norte. A subfigura 6.10(a), tomada doGoogle Earth,mostra uma visão superior do ambiente mapeado com a trajetória executada pelo robô,representada pela linha tracejada. O ponto amarelo ilustrao local de partida e o pontoem ciano identifica a posição de finalização do mapeamento. A planta baixa mostradana subfigura 6.10(b) identifica estruturalmente o ambiente mapeado. Os círculos verdesidentificam pequenas plantas no solo, os círculos negros representam jarros de plantas eos pequenos retângulos são bancas de assento.

Durante o mapeamento o robô se depara com cenas típicas de ambientes internos,como corredores, bem como imagens vistas em ambientes externos (plantas), a Figura 6.11ilustra essas situações. Percebe-se pelas imagens da Figura 6.11 que, como consequên-cia das mudanças de cenários, existe uma brusca mudança de iluminação, o que afeta deforma expressiva a qualidade dos mapas de disparidade, mesmo com o ajuste de brilho au-tomático disponível para as câmeras. Esse efeito, prejudica a interpretação desses dadospara o cálculo das informações de profundidade.

Apesar dos diferentes cenários encontrados pelo robô e das bruscas mudanças de ilu-minação ocorridas durante o mapeamento, o que resulta distintas situações e dificuldadesna estimação do mapa de disparidade, o método proposto apresentou resultado interes-santes, como podem ser vistos na Figura 6.12. A subfigura 6.12(a) mostra o mapa dosvalores de ocupação e a subfigura 6.12(b) os valores de elevação. As elipses vermelhasmarcadas nas figuras destacam o mapeamento da região típica de um ambiente interno(subfigura 6.11(a)), e os círculos em preto (no mapa de ocupação) e em amarelo (no mapade elevação) evidenciam o mapeamento do cenário típico de umambiente externo (sub-figura 6.11(c)). Esta generalidade de aplicações (ambientecom cenas estruturadas e nãoestruturadas) é uma característica interessante do métodode mapeamento apresentadoneste trabalho, mostrando sua utilidade em diferentes situações práticas.

Comparando-se ao mapeamento em grade de ocupação 3D, é necessária uma grade3D com 500 mil posições, enquanto que com o mapa de ocupação-elevação propostoutilizou-se uma estrutura de 187.500 posições.


(a)

(b)

12,6m

( c )

Figura 6.9: Mapeamento em grade de ocupação-elevação para oambiente externo:(a)Valores de ocupação. (b) Valores de elevação; (c) Variância das elevações.

6.7. EXPERIMENTO EM AMBIENTE MISTO 79

(a) (b)

15,4m

jard

imsalas

salas jardim

Figura 6.10: Vista superior do ambiente mapeado: (a) vista do Google Earth de latitude-5.842677 e longitude -35.19724; (b) Planta baixa.

(a) (b)

( c ) (d)

Figura 6.11: Diferentes cenas encontradas durante o mapeamento: (a) e (b) Cenas deambiente interno. (c) e (d) Cenas de ambiente externo.


(a)

(b)

15,4m

( c )

Figura 6.12: Resultado do mapeamento do ambiente misto: (a) Valores de ocupação; (b)Valores de elevação.(c) Variância das elevações.

6.8. COMPARAÇÕES 81

6.8 Comparações

Nesta seção, é feita uma comparação da quantidade de espaço de memória necessáriopara o armazenamento dos mapas em grade de ocupação 3D e os mapas em grade deocupação-elevação propostos neste trabalho. As comparações serão consideradas sobreos ambientes mapeados nos experimentos exibidos e explicados, variando a altura limitedo mapeamento. Para todas as condições de mapeamento foi utiliza uma dimensão padrãopara as células de 10×10 cm. De acordo com as comparações realizadas na Tabela 6.1,quanto maior o limite de altura do mapeamento maior o nível deredução de memória.Isto é, quanto mais alto se deseja mapear, maior a quantidadede memória necessária parauma grade de ocupação 3D, enquanto que uma grade de ocupação-elevação tem o seucusto estável. A sigla G.O. significa Grade de Ocupação e G. O-E significa Grade deOcupação-Elevação.

Tabela 6.1: Comparação de requisitos de memória.Experimento Limite Num. de elem. Num. de elem. Redução

de altura (cm) (G. O. 3D) (G.O-E) de Memória

Exp. 1 80 100 mil 37,5 mil 62,5%Dim: 25x5m 100 125 mil 37,5 mil 70 %Cel: 10cm 150 187,5 mil 37,5 mil 80%

Exp. 2 80 280 mil 105 mil 62,5%Dim: 35x10m 100 350 mil 105 mil 70 %Cel: 10cm 150 525 mil 105 mil 80%

Exp. 3 80 500 mil 187,5 mil 62,5%Dim: 25x25m 100 625 mil 187,5 mil 70 %Cel: 10cm 150 937,5 mil 187,5 mil 80%

6.9 Análise Geral dos Resultados

Neste capítulo, foram apresentado vários experimentos realizados com diferentes situa-ções a fim de validar o método de mapeamento proposto. O sistema foi testado em umambiente interno, em um ambiente externo e em um ambiente “misto” com peculiaridadesde ambientes internos e externos. Em todos os casos os mapas resultantes se mostram coe-rentes com o ambiente real mapeado, mesmo com as dificuldadesapresentadas, como porexemplo, iluminação e falta de textura, fatores esses que influenciam a qualidade dos ma-pas de disparidade. Além disso, é importante ressaltar a redução expressiva do uso dememória com o método de mapeamento proposto em relação a grade de ocupação 3D,principalmente quando o mapeamento pondera a representação de estruturas altas.


Capítulo 7

Conclusão e Perspectivas

O problema de mapeamento de ambientes através de robô móveisé uma etapa funda-mental em direção ao alcance da autonomia. Com uma descrição espacial do seu ambiente(mapa), indicando a localização de estruturas e obstáculos, um robô pode ser programadopara realizar diferentes tarefas como, desvio de obstáculos, planejamento de caminhos,localização, exploração, reconhecimento de objetos, limpezas, resgate, combate a incên-dios, entre outras.

Diante dessa necessidade, o presente trabalho apresentou uma solução para o mapea-mento de ambientes internos e/ou externos com informações tridimensionais, baseadasem informações sensoriais de distâncias, no presente caso,fornecidas pelo processamentode imagens capturadas por um sistema de visão estéreo. O mapaem uma grade regular ar-mazena informações de ocupação e elevação dos ambientes mapeados possibilitando queum robô possa tomar decisões se um local específico pode ser explorado ou não, de acordocom a probabilidade de ocupação, a elevação dos obstáculos esua variância. Ouseja, orobô pode classificar a navegabilidade do terreno do seu ambiente. O mapeamento apre-sentado considera uma modelagem estocástica a fim de que as informações ruidosas derobô e sensor sejam tratadas de forma adequada. Tal tratamento se dá por meio de umaanálise robusta das principais fontes de erros no cálculo das informações sensoriais.

O processo de mapeamento que foi descrito obedece uma sequencia de passos: 1)Cálculo das coordenadas e orientação do robô em relação ao seuambiente através domodelo de movimento de odometria. 2) Aquisição e interpretação de dados sensoriaisatravés de uma câmera estéreo, contendo informações sobre oentorno do robô; 3) Mode-lagem do comportamento sensorial para a interpretação dos dados da etapa anterior eminformações sobre ocupação e elevação. 4) Integração de dados através de equações es-tocásticas, responsáveis por integrar as novas medições interpretadas às informações jáexistentes sobre a ocupação e elevação das células.

Na validação do mapeamento proposto foram realizados experimentos com um robôreal Pioneer 3-AT equipado com um sistema de visão estéreo debaixo custo (Minoru 3D),onde procurou-se comprovar a factibilidade do mapeamento para diferentes tipos de am-bientes, apresentando distintas situações. Os resultadosobtidos se mostraram coerentes àrealidade dos ambientes mapeados consolidando assim, o método proposto. É importantefrisar que o arcabouço de mapeamento proposto pode perfeitamente ser adaptado paraser utilizado com outros tipos de sensores além das câmeras,como por exemplo, lasers ekinect.

84 CAPÍTULO 7. CONCLUSÃO E PERSPECTIVAS

Diante disso, a principal contribuição científica desse trabalho relaciona-se com odesenvolvimento de uma solução para o mapeamento probabilístico de ambientes cominformações 3D, utilizando uma estrutura de dados bidimensional para o armazenamentodo modelo, chamado de grade de ocupação-elevação. Diferentemente das abordagens ex-istentes na literatura, cada célula do mapa construído tem uma função de probabilidadeque remete informações de ocupação, uma média da altura dos obstáculos e a variân-cia da altura, indicando a precisão da medição de altura. Com isso, torna-se possível aidentificação de obstáculos possíveis de serem transpostosa partir do mapa construído.Além disso, foi realizada uma modelagem probabilística do sistema de visão estéreo, comidentificação das principais fontes de incertezas, o que implica na construção de um mapacoerente com as informações sensoriais ruidosas.

Considera-se o modelo apresentado uma interessante alternativa para o problema denavegação de ambientes com desvio e/ou transposição de obstáculos.

Com relação às perspectivas, relacionadas com trabalhos queainda deverão ser real-izados, pretende-se:

1. Testar a abordagem de mapeamento proposta com outros tipos de sensores a fim deque o sistema seja utilizado em outras plataformas robóticas;

2. Investigar a possibilidade de fusão de células com o objetivo de diminuir ainda maisa estrutura necessária para armazenar os mapas, tornando-os mais compactos;

3. Adaptar o mapeamento proposto ao problema do SLAM (Simultaneous Localiza-tion and Mapping), ponderando sua aplicação em ambientes internos e externos;

4. Serão investigadas as abordagens baseadas no filtro de partículas, comoFastSLAM[Hähnel et al. 2003] e oRao-Blackwellized particle filterpara SLAM [Grisettiet al. 2007] adequado para mapas em grades;

5. Evoluir a técnica de SLAM para um sistema de localização, mapeamento e plane-jamento simultâneos (SPLAM), dado que o mapa em grade favorece a aplicação dealgoritmos de planejamento de caminhos de forma direta.

Referências Bibliográficas

Agrawa, M., K. Konolige & R. C. Bolles (2007), Localization and mapping for au-tonomous navigation in outdoor terrains : A stereo vision approach,em‘IEEE Work-shop on Application of Computer Vision’.

Ahn, S., K. Lee, W. K. Chung & S.-R. Oh (2007), Slam with visual plane: Extracting ver-tical plane by fusing stereo vision and ultrasonic sensor for indoor environment,em‘Proc. Of IEEE International Conference on Robotics and Automation’, pp. 4787–4794.

Aires, K. R. T. & A. A. D. Medeiros (2010), A plane segmentationsystem based on affinehomography and optical,em‘Proc. of Conference on Graphics, Petterns and Images(SIBIGRAPI)’, pp. 346–352.

Alsina, Pablo J., Luiz M. G. Gonçalves, Adelardo A. D. Medeiros, Diogo P. F. Pedrosa &Frederico C. Vieira (2002), Navegação e controle de robôs móveis,em‘Mini-Curso:Congresso Brasileiro de Automática (CBA)’.

Andert, F. (2009), Drawing stereo disparity images into occupancy grids: Measurementmodel and fast implementation,em ‘Proc. Of IEEE International Conference onIntelligent Robots and Systems’, pp. 5191–5197.

Angelopoulou, E., T. Hong & A. Wu (1992), World model representation for mobilerobots,em‘In Proc. of Intelligent Vehicles ’92 Symposium’, pp. 293–297.

Aroca, R. V. & L. M .G. Gonçalves (2012), ‘Method for reading sensors and controllingactuators using audio interfaces of mobile devices’,Sensorspp. 1572–1593.

Bares, J., M. Hebert, T. Kanade, E. Krotkov, T. Mitchell, R. Simmons & W. R. L. Whit-taker (1989), ‘Ambler: An autonomous rover for planetary exploration’, IEEE Com-puter Society Press22(6), 18–22.

Blanco, J.-L., J.-A Fernandez-Madrigal & J. Gonzalez (2008), ‘Toward a unified bayesianapproach to hybrid metric-topological slam’,IEEE Transactions on Robotics24(2), 259–270.

Bradski, G. & A. Kaehler (2008),Learning OpenCV: Computer Vision with the OpenCVLibrary, O’Reilly Media.

85

86 REFERÊNCIAS BIBLIOGRÁFICAS

Cappalunga, A., S. Cattani, A. Broggi, M. S. McDaniel & S. Dutta (2010), Real t ime 3dterrain elevation mapping using ants optimization algorithm and stereo vision,em‘Proc. of IEEE Intelligent Vehicles Symposium, Universityof California’, pp. 21–25.

Chang, H.-H., S.-Y. Lin & Y.-C. Chen (2010), Slam for indoor envinonment using stereovision, em ‘Proc. of Second WRI Global Congress on Intelligent Systems(GCIS)’,pp. 266–269.

Cherubini, A. & F. Chaumette (2011), Visual navigation with obstacle avoidance,em‘Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems’,pp. 1593–1598.

Choi, Y.-H & S.-Y Oh (2006), Grid-based visual slam in complexenvironment,em‘Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems’,pp. 2563–2569.

Choset, H. & D. Fox (2004), The world of mapping,em‘Proc. of the Workshop on Reviewof United States Research in Robotics - National Science Foundation (NSF).’.

Civera, J., A. J. Davison & M. Montiel (2008), ‘Inverse depth parametrization for monoc-ular slam’,IEEE Transactions on Robotics24(5), 932–945.

Davison, A. (2002), Slam with a single camera,em ‘SLAM/CML Workshop at Interna-tional Conference on Robotics and Automation’.

Davison, A. (2003), Real-time simultaneous localization and mapping with a single cam-era, em ‘IEEE International Conference on Computer Vision’, Vol. 2, pp. 1403–1410.

Davison, A., I. D. Reid, N. D. Molton & O. Stasse (2007), ‘Monoslam: Real-time sin-gle camera slam’,IEEE Transaction on Pattern Analysis and Machine Intelligence29(6).

de Saint Vincent, A. (1987), Visual navigation for a mobile robot building a map of theoccupied space from sparse 3d stereo data,em‘Proc. of IEEE Int. Conf. on Roboticsand Automation’, Vol. 4, pp. 1429–1435.

Dryanovski, I., W. Morris & J. Xiao (2010), Multi-volume occupancy grids: an efficientprobabilistic 3d mapping model for micro aerial vehicles,em ‘Proc. of IEEE/RSJInternational Conference on Robotics and Systems’, pp. 1553–1559.

Dryanovski, I., W. Morris & J. Xiao (2011), Multi-volume occupancy grids: an efficientprobabilistic 3d mapping model for micro aerial vehicles,em ‘Proc. of IEEE/RSJInternational Conference on Intelligent Robots and Systems’, pp. 1553–1559.

Einhorn, E., C. Schröter & H.-M. Gross (2011), Finding the adequate resolution for gridmapping - cell size locally adapting on-the-fly,em‘Proc. of IEEE International Con-ference on Robotics and Automation’, pp. 1843–1848.

REFERÊNCIAS BIBLIOGRÁFICAS 87

Elfes, A. (1987), ‘Sonar-based real-world mapping and navigation’, IEEE Journal ofRobotics and Automation3(3), 249–265.

Elfes, A. (1989), Occupancy Grid: A Probabilistic Framework for Robot Perception andNavigation, Tese de doutorado, Carnegie Mellon University,Pensylvania, USA.

Gallelos, G. & P. Rives (2010), Indoor slam based on compositesensor mixing laserscans and omnidirectional images,em ‘Proc. of IEEE International Conference onRobotics and Automation’, pp. 3519–3524.

Georgiev, K., R. T. Creed & R. Lakaemper (2011), Fast plane extraction in 3d rangedata based on line segments,em ‘Proc. of IEEE/RSJ International Conference onIntelligent Robots and Systems’.

Goldstein, M., F. Pin, G. Saussure & C. Weisbin (1987), 3d world modeling based oncombinatorial geometry for autonomous robot navigation,em ‘Proc. of IEEE Int.Conf. on Robotics and Automation’, Vol. 4, pp. 727–733.

Gonçalves, L., R. Grupen, A. Oliveira, D. Wheeler & A. Fagg (2000), ‘Tracing patternsand attention: Humanoid robot cognition’,The Intelligent Systems and their Appli-cations15(1).

Grisetti, G., C. Stachniss & W. Burgard (2007), ‘Improved techniques for grid mappingwith rao-blackwellized particle filters’,IEEE Transactions on Robotics23.

Gupta, V., G. Singh, A. Gupta & A. Singh (2007), Occupancy grid mapping using ar-tificial neural networks,em ‘Proc. of 2010 International Conference on IndustrialElectronics, Control and Robotics’, pp. 247–250.

Hahnel, D. (2004), Mapping with Mobile Robots, Tese de doutorado, University ofFreiburg, Freiburg, Germany.

Hebert, M., C. Caillas, E. Krotkov, I. S. Kweon & T. Kanade (1989), Terrain mappingfor a roving planetary explorer,em‘Proc. of the IEEE International Conference onRobotics and Automation’, pp. 997–1002.

Hines, W. W., D. D. Montgomery, D. M. Goldsman & C. M. Borror (2006),Probabilidadee Estatística na Engenharia, 4a edição, Ed. LTC, Rio de Janeiro-RJ.

Hong, L. & G. Chen (2004), Segment-based stereo macthing using graph-cuts,em‘Proc.Of EEE Computer Society Conference on Computer Vision and Pattern Recognition,CVPR’, Vol. 1, pp. 74–81.

Hygounenc, E., I.-K. Jung, P. Souères & S. Lacroix (2004), ‘The autonomous blimpproject of laas-cnrs: Achievements in flight control and terrain mapping’,Inter-national Journal of Robotics Research23(4-5), 473–511.


Hähnel, D., D. Fox, W. Burgard & S. Thrun (2003), A highly efficient fastslam algo-rithm for generating cyclic maps of large-scale environments from raw laser rangemeasurements,em‘Proc. Conference on Intelligent Robots and Systems (IROS)’.

Johannsson, H., M. Kaess, B. Englot, F. Hover & J. Leonard (2010), Imaging sonar-aidednavigation for autonomous underwater harbor,em‘Proc. of IEEE/RSJ InternationalConference on Intelligent Robots and Systems’, pp. 4396–4403.

Kalman, R. E. (1960), ‘A new approach to linear filtering and predictive problems’,Trans-actions of the Journal of Basic Engineeringpp. 35–45.

Kim, W. S., A. I. Ansar & R. D. Steele (2005), Performance analysis and validation of astereo vision system,em‘Proc. of IEEE System, Man and Cybernetics’.

Konrad, M., M. Szczot, F. Schule & K. Dietmayer (2011), Generic grid mapping for roadcourse estimation,em‘Proc. of IEEE Intelligent Vehicles Symposium’.

Kriegman, D., E. Triendl & T. Binfold (1987), A mobile robot: Sensing, planning andlocomotion,em ‘Proc. of IEEE Int. Conf. on Robotics and Automation’, Vol. 4,pp. 402–408.

Kuipers, B. & Y.-T. Byun (1988), A robust, qualitative method for spatial learning inunknown environments,em‘Proc. of AAAI-88’, pp. 1–12.

Kwon, T.-B, J.-B. Song & S.-H. Joo (2010), ‘Elevation moment ofinertia: A new featurefor monte carlo localization in outdoor environment with elevation map’,Journal ofField Robotics27(3), 371–386.

Lacroix, S., A. Mallet, D. Bonnafous, G. Bauzil, S. Fleury, M. Herrb & R. Chatila (2002),‘Autonomous rover navigation on unknown terrains: Functions and integration’,In-ternational Journal of Robotics Research27, 917–942.

Lai, X. C., S. S. Ge, P. T. Ong & A. Mamun (2006), Incremental path planning usingpartial map information for mobile robots,em‘Proc. of International Conference onControl, Automation, Robotics and Vision’, pp. 1–6.

Lee, S.-J. & J.-B. Son (2010), A new sonar salient feature structure for ekf-based slam,em‘In Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems’,pp. 5966–5971.

Lemaire, T., C. Berger, I.-K. Jung & S. Lacroix (2007), ‘Vision-based slam: Stereo andmonocular approaches’,International Journal of Computer Vision74(3), 343–364.

Li, Z.-N. & G. Hu (2002), ‘Analysis of disparity gradient based cooperative stereo’,IEEETransactions on Image Processing5(11), 1493–1506.

Liu, Y., R. Emery, D. Chakrabarti, W. Burgard & S. Thrun (2001), Using EM to learn 3Dmodels with mobile robots,em ‘Proc. of the International Conference on MachineLearning (ICML)’.


Marjovi, A., J. G. Nunes, L. Marques & A. Almeida (2009), Multi-robot explorationand fire searching,em‘Proc. of IEEE/RSJ International Conference on IntellingentRobots and Systems’, pp. 1929–1934.

Marks, T., A. Howard, M. Bajracharya, G. Cotrell & L. Mathies (2009), ‘Gamma-slam:Visual slam in unstructured environments using variance grid maps’, Journal ofField Robotics26(1), 26–51.

Merat, F. & F. Wu (1987), Generation of object descriptions from range data using featureextraction by demands,em‘Proc. of IEEE Int. Conf. on Robotics and Automation’,Vol. 4, pp. 941–946.

Moravec, H. P. (1988), ‘Sensor fusion in certainty grids formobile robots’,Computer9(2), 61–74.

Moravec, H. P. (1996), Robot spacial perception by stereoscopic vision on 3d evidencegrid, Relatório Técnico CMU-RI-TR-96-34, CMU Robotics Institute, Pittsburg,Pensylvania.

Murarka, A. & B. Kuipers (2009), A stereo vision based mappingalgorithm for detectingincline, drop-offs, and obstacles for safe local navigation, em ‘Proc. of IEEE/RSJInternational Conference on Intelligent Robotis and Systems’, pp. 1646–1653.

Ogawa, Y., N. Shimada & Y. Shirai (2007), Environmental mapping for mobile robot bytracking sift feature points using trinocular vision,em ‘SICE Annual Conference’,Vol. 1, pp. 1996–2001.

Pfaff, P., R. Triebel & W. Burgard (2007), ‘An efficient extension to elevation maps foroutdoor terrain mapping and loop closing’,The International Journal of RoboticsResearch26(217), 217–230.

Piniés, P., L. M. Paz, D. Gálvez-Lopes & J. D. Tardós (2010), ‘Ci-graph simultaneouslocalization and mapping for three-dimensional reconstruction of large and complexenvironments using a multicamera system’,Journal of Robotics27(5), 561–586.

Pirker, K., M. Ruther, H. Bischof & G. Schweidhofer (2011), Fast and accurate environ-ment modeling using three-dimensional occupancy grids,em ‘IEEE InternationalConference on Computer Vision Workshops’, pp. 1134–1140.

Rocha, R. (2006), Building Volumetric Maps whit Cooperative Mobile Robots and UsefulInformation Sharing: A Distributed Control Approach based on Entropy, Tese dedoutorado, Universidade do Porto, Porto,Portugal.

Ruhnke, M., R. Kummerle, G. Grisetti & W. Burgard (2011), Highlyaccurate maxi-mum likelihood laser mapping by jointly optimizing laser points and robot poses,em‘Proc. Of IEEE International Conference on Robotics and Automation’, pp. 2812–2817.


Santana, A. M. (2011), Localização e Mapeamento Simultâneos de Ambientes PlanosUsando Visão Monocular e Representação Híbrida do Ambiente,Tese de doutorado,Universidade Federal do Rio Grande do Norte, Natal, Brasil.

Santana, A. M. & A. A. D. Medeiros (2011), ‘A line-based approach to slam using monoc-ular vision’, IEEE Latin America Transaction9(3), 231–239.

Santana, André M. & Adelardo A. D. Medeiros (2009),Contemporary Robotics - Chal-lenges and Solutions, INTECH, capítulo Simultaneous Localization and MappingSLAM of a Mobile Robot Based on Fusion of Odometry and Visual Data UsingExtended Kalman Filter.

Servant, F., P. Houlier & E. Marchand (2010), Improving monocular blane-based slamwith inertial measures,em ‘IEEE/RSJ International Conference on IntelligentRobots and Systems’, pp. 3810–3815.

Sharstein, D. & R. Szeliski (2002), ‘A taxonomy and evaluation of dense two-frame stereocorrespondence algorithms’,International Journal of Computer Vision47(1/2/3), 7–42.

Shi, L., S Kodagoda & G. Dissanayake (2010), Environment classification and seman-tic grid map building based on laser range finder data,em ‘Semantic Perception,Mapping and Exploration (SPME) Workshop 2010’.

Siegwart, Roland & Illah R. Nourbakhsh (2004),Introduction to Autonomous MobileRobots, MIT Press.

Silver, D., D. Ferguson, A. Morris & S. Thayer (2004), Features extraction for topolog-ical mine maps,em ‘Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots andSystems’, pp. 773–779.

Souza, A. (2008), Mapeamento, Dissertação de mestrado, Universidade Federal do RioGrande do Norte, Natal, RN, Brasil.

Stachniss, C. (2006), Exploration and Mapping with Mobile Robots, Tese de doutorado,University of Freiburg, Freiburg, Germany.

Stachniss, C. (2009),Robotic Mapping and Exploration, Springer Tracts in AdvancedRobotics.

Thrun, S. (1998), ‘Learning metric-topological maps for indoor mobile robot navigation’,Artificial Inteligence99(1), 21–71.

Thrun, S. (2002), Robotic mapping: A survey, Morgan Kaufmann.

Thrun, Sebastian, Wolfram Burgard & Dieter Fox (2005),Probabilistic Robotics, 1a

edição, MIT Press.


Trucco, E. & A. Verri (1998),Introductory Techniques for 3D Computer Vision, Prentice-Hall, USA.

Wolf, D. F, E. V. Simões, F. S. Osório & O. Trindade Junior (2009), Robótica móvelinteligente: Da simulação às aplicações no mundo real,em‘Mini-Curso: Jornada deAtualização em Informática (JAI), Congresso da SBC’.

Wolf, D. & G. Sukhatme (2008), ‘Semantic mapping using mobile robots’,IEEE Trans-actions on Robotics and Automation24, 244–258.

Wu, E., L. Zhao, Y. Guo & W. Zhou (2010), Monocular vision slambased on key featurepoints selection,em ‘Proc. of IEEE International Conference on Information andAutomation’, pp. 1741–1745.

Wurm, K. M., A. Hornung, M. Bennewitz, C. Stachniss & W. Burgard (2010), Octomap:A probabilistic, flexible, and compact 3d map representation for robotic systems,em‘ICRA, Workshop on 3D Perception and Modeling’.

Xiong, Y. & L. Matthies (1997), Error analysis of a real-timestereo system,em‘Proc. ofIEEE Computer Society Conference on Computer Vision and Pattern Recognition’,pp. 1087–1093.

Yang, Shao-Wen & Chieh-Chih Wang (2011), Feasibility grids for localization and map-ping in crowded urban scenes,em ‘Proc. of IEEE International Conference onRobotic and Automation’, pp. 2322–2326.

Ye, C. & J. Borenstein (2003), A new terrain mapping method for mobile robot obsta-cle negotiation,em ‘Proc. of the UGV Technology Conference at the 2002 SPIEAeroSense Symposium’, pp. 21–25.

Zhang, Z. (2000), ‘A fl exible new technique for camera calibration’, IEEE Transactionson Pattern Analysis and Machine Intelligence22, 1330–1334.

Zureiki, A., M. Devy & R. Chatila (2007), Stereo matching usingreduced-graph cuts,em‘IEEE International Conference Image Processing’, Vol. 1.

Documents

Mapeamento Robótico 2,5-D com Representação em Grade de …€¦ · rei; bendirei o teu nome para todo sempre! Todos os dias te bendirei e louvarei o teu nome para todo sempre!