ads:
UNIVERSIDADE ESTADUAL PAULISTA
"Júlio de Mesquita Filho"
Pós-Graduação em Ciência da Computação
Luciana Leal da Silva
CLASSIFICAÇÃO E CARACTERIZAÇÃO DE AMBIENTES PARA
NAVEGAÇÃO DE ROBÔS MÓVEIS BASEADA EM MAPAS
São José do Rio Preto
2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
LUCIANA LEAL DA SILVA
Classificação e Caracterização de Ambientes para NAvegação de Robôs Móveis
Baseada em Mapas
Orientador: Mário Luiz Tronco
Dissertação apresentada para obtenção do título de Mestre em Ciência da Computação, área de
Processamento de Imagens e Visão Computacional, junto ao Programa de Pós-Graduação em
Ciência da Computação do Instituto de Biociências, Letras e Ciências Exatas da Universidade
Estadual Paulista "Júlio de Mesquita Filho", Campus de São José do Rio Preto.
São José do Rio Preto
2008
ads:
LUCIANA LEAL DA SILVA
Classificação e Caracterização de Ambientes para Navegação de Robôs Móveis
Baseada em Mapas
Dissertação apresentada para obtenção do título de Mestre em Ciência da Computação, área de
Processamento de Imagens e Visão Computacional, junto ao Programa de Pós-Graduação em
Ciência da Computação do Instituto de Biociências, Letras e Ciências Exatas da Universidade
Estadual Paulista "Júlio de Mesquita Filho", Campus de São José do Rio Preto.
BANCA EXAMINADORA
Prof. Dr. Mário Luiz Tronco
Professor Doutor
UNESP - São José do Rio Preto
Orientador
Prof. Dr. Aparecido Nilceu Marana
Professor Doutor
UNESP - Bauru
Prof. Dr. Orides Morandir Júnior
Professor Doutor
Universidade de Federal de São Carlos - UFSCAR
São José do Rio Preto
2008
Agradecimentos
Agradeço a Deus pela graça, misericórdia e salvação concedida.
Agradeço ao meu esposo pelo amor e incentivo, supo rtando minhas ausências com compreensão e
saudade.
Agradeço aos meus pais p ela educação e suporte em todos as áreas, o que possibilitou chegar até
aqui.
Agradeço aos meus irmão s, Luis e Leandro por toda ajuda e incentivo, e a minha cunhada Aline
pelas orações.
Agradeço aos amigos da ADNIPO pela ajuda e incentivo.
Agradeço ao professor Mário por todo suporte técnico, incentivo, tempo disponibilizado ajudando
no desenvolvimento deste trabalho, sem os quais nada disso teria sido realizado.
Agradeço aos amigos do Laboratório do LACE, Henrique, Tiago, Otávio, Miriam, Giovana e
Luciano por toda ajuda dispensada.
Agradeço aos amigos Rodrigo, Henrique e Tiago pela ajuda e compreensão durante o estágio em
docência, realizado numa fase muito complicada de minha vida.
Agradeço a estes e a todas as outras amizades que nasceram durante o mestrado, que muitas vezes
suavizam as dificuldades encontradas durante este processo.
Agradeço as amigas Carol e Lívia pela verdadeira amizade.
Por fim, agradeço a todos os professores que em conjunto contribuíram para minha formação e
conclusão desta etapa.
i
Resumo
Robôs autônomos precisam ser capazes de aprender e manter mo delo s de seus ambientes. Neste
contexto o presente trabalho contempla o uso de redes neurais artificiais em conjunto co m técnicas
de cla ssificaçã o e extração de características a partir de imagens com o objetivo usá-las no desen-
volvimento do sistema de mapeamento e localização do robô movel do Laboratório de Automação
e Controle Evolutivo (LACE). Para perceber o ambiente explorado o robô usa seu sistema sensorial
formado por sensores de ultra-som e um sistema catadióptrico, composto por uma câmera e um
espelho cônico. Dois módulos do sistema de mapeamento são apresentados: módulo classificador
de nós e módulo caracterizador de nós. O primeiro utiliza uma rede neural hierárquica para tarefa
de classificação. Já o segundo usa técnicas de extração de atributos e reconhecimento de padrões
invariantes aplicadas em imagens coleta das do ambiente. A rede neural utilizada pelo módulo
classificador é estruturada em duas camadas: razão e intuição, e é treinada para classificar cada
local explorado pelo robô dentre quatro classes pré-definidas. O resultado final da exploração é
a construção de um mapa topológico do ambiente. Resultados obtidos por meio da simulação de
ambos os módulos do sistema são apresentados neste trabalho.
ii
Abstract
Autonomous robots must be able to learn and maintain models of their environments. In this
context, the present work co nsiders techniques for the classification and extraction of features
from images in joined with artificial neural networks in order to use them in the mapping and
localization system of the mobile robot of the Laboratory of Automation and Evolutive Computer
(LACE). To do this, the robo t uses a sensorial system composed by ultrasound sensors and a
catadioptric vision system formed by a camera and a conical mirror. Two mapping system modules
are presented: the classifier and the characterizer modules. The first module uses a hierarchical
neural network to do the classification; the second uses image attributes extraction techniques and
recognition of invariant patterns extracted from the places images set. The neural network of the
classifier module is structured in two layers, reason and intuition, and is trained to classify each
place explored for the robot among st four predefine classes. The final result of the exploration is
the construction of a topological map of the explored environment. Results gotten through the
simulation of the both modules of the mapping system are presented in this thesis.
iii
Lista de Figuras
2.1 Procedimento ge ral para localização baseada em mapas. . . . . . . . . . . . . . . . 4
2.2 Modelo do sensor usado para inferir informações sobre lugares do ambiente não
visitados (Adaptado de (FILLIAT e MEYER, 2003).) . . . . . . . . . . . . . . . . 6
2.3 Modelo do sensor usado para inferir a posição relativa I1 a partir da comparação
entre dados sensoriais de dois lugares visitados A1 e A2. . . . . . . . . . . . . . . 7
2.4 Ilustração da Representação Clássica dos Mapas Geométricos e Mapas Topológicos. 8
2.5 Exemplo de mapeamento das características de um ambiente contendo segmentos
detectados sobre as fronteiras dos obstáculos. . . . . . . . . . . . . . . . . . . . . . 9
2.6 Exemplo de Grade de Ocupação. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7 Dois diferentes tipos de mapas obtidos quando informações métricas são adicionadas
aos mapas topológicos. A parte a ilustra o mapa dikitiométrico, o qual armazena
a posição relativa entre nós adjacentes. Já a parte b ilustra o mapa dikitiométrico
absoluto, que armazena a posição absoluta dos nós. . . . . . . . . . . . . . . . . . 13
2.8 Função de discriminação definindo as duas classes. . . . . . . . . . . . . . . . . . . 16
2.9 Classificação pelo vizinho mais próximo. . . . . . . . . . . . . . . . . . . . . . . . 17
2.10 Detecção dos extremos locais. O pixel marcado com X é comparado a seus 26
vizinhos , numa janela de 3x3x3 onde é aplicada a função DoG. . . . . . . . . . . 18
2.11 Camera com mecanismo de rotação (MECANISMO, 2008). . . . . . . . . . . . . . 19
2.12 Lente olho-de-peixe NIKON FC-E8 (NIKON, 2008). . . . . . . . . . . . . . . . . . 20
2.13 Exemplo de um espelho cônico com webcam. . . . . . . . . . . . . . . . . . . . . . 20
2.14 Sensor omnidirecional com espelho hiperbólico (CAMERA, 2008). . . . . . . . . . 21
2.15 Imagem omnidirecional obtida a partir de um espelho hiperbólico alinhado a uma
câmera. Note o realce dado aos objetos centrais da imagem (céu) (SPACEK, 2003). 21
2.16 Imagem obtida a partir de um esp elho cônico alinhado a uma câmera. O realce é
dado a objetos úteis ao longo do horizonte refletido (SPACEK, 2003). . . . . . . . 22
2.17 Geometria do espelho cônico (SPACEK, 2003). . . . . . . . . . . . . . . . . . . . . 23
2.18 Projeção em um espelho cônico (SPACEK, 2003). . . . . . . . . . . . . . . . . . . 24
2.19 Imagem omnidirecional não pré-processada. . . . . . . . . . . . . . . . . . . . . . 24
2.20 Imagem panorâmica obtida a partir de uma imagem omnidirecional. . . . . . . . . 25
2.21 Modelo de McCulloch e Pitts, (Haykin, 2 001 ). . . . . . . . . . . . . . . . . . . . . 25
2.22 Hiperplano dividindo duas classes, (HAYKIN, 2001). . . . . . . . . . . . . . . . . 26
2.23 Perceptron multicamadas (HAYKIN, 2001 ). . . . . . . . . . . . . . . . . . . . . . 27
2.24 Aprendizado supervisionado, (HAYKIN, 2001). . . . . . . . . . . . . . . . . . . . 28
2.25 Aprendizado não-supervisionado, (BRAGA et. al., 2000). . . . . . . . . . . . . . . 28
2.26 Procedimento geral de localização baseada em marcos. . . . . . . . . . . . . . . . 30
3.1 Disposição Física dos Sensores no Chassi do Robô. . . . . . . . . . . . . . . . . . . 33
3.2 Procedimento de leitura amgular dos sonares laterais do robô. . . . . . . . . . . . 33
3.3 Sistema de Visão Omnidirecional do Robô Móvel do LACE, (CAVANI 2004). . . . 34
3.4 Interação entre os módulos do sistema de visão omnidirecional (CAVANI, 2004). . 35
iv
3.5 Interface utilizada para captura de imagens omnidirecional. . . . . . . . . . . . . . 36
3.6 Coordenadas polares - utilizada para retificação da imagem omni. . . . . . . . . . 36
3.7 Imagem panorâmica gerada pelo módulo de visão omnidirecional. . . . . . . . . . 37
3.8 Imagem panorâmica resultante do pré-processamento pelo módulo de visão. . . . . 37
3.9 Esquema Funcional do Sistema de Mapeamento. . . . . . . . . . . . . . . . . . . . 38
3.10 Diagrama em máquina de estados das decisões de navegação do robô. . . . . . . . 39
3.11 Estrutura da Rede Neural Hierárquica - RNAH. . . . . . . . . . . . . . . . . . . . 40
3.12 Estrutura da Rede Razão. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.13 Estrutura da Rede Intuição. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1 Imagens Binárias Panorâmicas da Porta 1: a) Visão1; b) Visão 2 ; c) Visão 1 com
baixa iluminação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Imagem Real da Porta 1 (P1)- a) Visão 1 b) Visão 2 c) Visão 1 com baixa iluminação. 44
4.3 Imagens Binárias Panorâmicas do Corredor 1: a) Visão1; b) Visão 2; c) Visão 3. . 45
4.4 Imagens Reais do Corredor 1 - C1: a) Visão 1, b) Visão 2, c) Visão 3. . . . . . . . 45
4.5 Imagem Real do Corredor 2 (C2) - a) Visão 1: classificada corretamente com va =
0.994; b) Visão 2: classificada corretamente com va=0.993; c) Visão 3: classificada
incorretamente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.6 Procedimento de leitura real dos sensores. Cinco posições de leitura para os sonares
laterais direito e esquerdo; vinte e cinco posições de leitura para o sonar dianteiro. 48
4.7 Locais onde os sonares coletaram medidas de distâncias do robô em relação a obs-
táculos: corredores e portas localizadas tanto à frente quanto nas laterais do robô. 48
4.8 Ta bela das distâncias calculadas pelos sonares no local L1: corredor localizado à
direita do robô. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.9 Características SIFT extraídas a partir de imagens omnidirecional do Corredor 3 ,
visto sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As carac-
terísticas SIFT são representadas por um retângulo localizado onde a característica
foi encontrada. O tamanho da característica é representado pelo número inteiro no
interior do mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.10 Características SIFT extraídas a partir de imagens omnidirecional do Corredor 4,
visto sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As carac-
terísticas SIFT são representadas por um retângulo localizado onde a característica
foi encontrada. O tamanho da característica é representado pelo número inteiro no
interior do mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.11 Características SIFT extraídas a partir de imagens omnidirecional do Porta 2, visto
sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As carac-
terísticas SIFT são representadas por um retângulo localizado onde a característica
foi encontrada. O tamanho da característica é representado pelo número inteiro no
interior do mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.12 Características SIFT extraídas a partir de imagens omnidirecional do Porta 3, visto
sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As carac-
terísticas SIFT são representadas por um retângulo localizado onde a característica
foi encontrada. O tamanho da característica é representado pelo número inteiro no
interior do mesmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
A.1 Imagem real de L1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
A.2 Distâncias calculadas pelos sonares laterais e frontal para L1. . . . . . . . . . . . . 56
A.3 Imagem Rea l de L2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
A.4 Distâncias calculadas pelos sonares laterais e frontal para L2. . . . . . . . . . . . . 58
v
A.5 Imagem Rea l de L3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
A.6 Distâncias calculadas pelos sonares laterais e frontal para L3. . . . . . . . . . . . . 59
A.7 Imagem Rea l de L4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
A.8 Distâncias calculadas pelos sonares laterais e frontal para L4. . . . . . . . . . . . . 60
A.9 Imagem Rea l de L5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
A.10 Distâncias calculadas pelos sonares laterais e frontal para L5. . . . . . . . . . . . . 61
A.11 Imagem Real de L6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
A.12 Distâncias calculadas pelos sonares laterais e frontal para L6. . . . . . . . . . . . . 62
A.13 Imagem Real de L7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
A.14 Distâncias calculadas pelos sonares laterais e frontal para L7. . . . . . . . . . . . . 63
A.15 Imagem Real de L8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
A.16 Distâncias calculadas pelos sonares laterais e frontal para L8. . . . . . . . . . . . . 64
A.17 Imagem Real de L9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
A.18 Distâncias calculadas pelos sonares laterais e frontal para L9. . . . . . . . . . . . . 65
vi
Lista de Tabelas
4.1 Exemplos de locais classificados pela RNAH durante a etapa de testes . . . . . . . 44
4.2 Porcentagem Geral da Classificação Correta das Camadas Razão e Intuição . . . . 46
4.3 Classificação das Classes Corredor e Porta - Camada Intuição . . . . . . . . . . . 47
4.4 Porcentagem Geral da Cla ssificaç ão Correta das Camadas Razão e Intuição - Teste 2 47
4.5 Classificação das Classes Corredor e Porta: Camada Intuição - Abertura lateral:
Camada Razão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Resultado Geral da Clas sificaçã o da RNAH razão e intuição nas duas etapas de
testes: Teste 1 e Teste 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.7 Porcentagem Geral da Classificação Correta da Camada Intuição - Teste 3 . . . . 50
4.8 Porcentagem Geral da Classificação Correta da Camada Intuição - Teste 3 . . . . 50
vii
Sumário
1 Introdução 1
1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Estrutura do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Fundamentação Teórica 4
2.1 Técnicas de Mapeamento de Ambientes para Navegação de Robôs Móveis . . . . . 5
2.1.1 Origens das Informações para Construção de Mapas . . . . . . . . . . . . . 5
2.1.2 Mapas Geométricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 Mapas To pológicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Aprendendo Mapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Aprendizagem de mapas topológicos . . . . . . . . . . . . . . . . . . . . . 13
2.3 Visão Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Reconhecimento de Padrões . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Imagem Omnidirecional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Redes Neurais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Neurônios Artificiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.2 Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.3 Perceptron Multicamadas (MLP) . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.4 Aprendizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.5 Back-propagatio n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.6 Uso de RNAs em Visão Computacional . . . . . . . . . . . . . . . . . . . . 29
2.5 Navegação Baseada em Marcos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5.1 Marcos Artificiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.2 Marcos Naturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Sistema de Mapeamento do Robô Móvel do LACE 32
3.1 Sistema Sensorial do Robô Móvel do Lace . . . . . . . . . . . . . . . . . . . . . . 32
3.1.1 Sensores de Ultra-Som . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2
3.1.2 Sistema de Visão Omnidirecional . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Estrutura do Sistema de Mapeamento . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Módulo Classificador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Módulo Caracterizador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Resultados Experimentais 43
4.1 Módulo Classificador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Módulo Caracterizador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
viii
5 Conclusões 53
5.1 Proposta para Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
A Testes - RNAH-Razão 55
B Publicações 66
ix
Capítulo 1
Introdução
A grande variedade de tarefas que podem ser realizadas por robôs tem impulsionado o interesse
por esse campo do conhecimento. Atualmente, eles estão inseridos em diversas aplicações que vão
desde as associadas à substituição do homem na realização de tarefas em ambientes hostis até o
uso dos mesmos pela indústria do entretenimento. Robô s móveis apareceram mais recentemente.
Um exemplo de aplicação de rob ôs móveis em ambiente hostil é a exploração interplanetária, a
qual utiliza robôs móveis c om o objetivo de explorar ambientes desconhecidos, com condições
totalmente adversas ao explorador humano.
O desenvolvimento de técnicas para navegação autôno ma de robôs móveis constitui uma das
maiores tendências em pesquisas na área da robótica (GOLDBERG, 2002; BACZYK, 2003; AN-
DREASSON, 2004; MARTINEZ, 2005). A autonomia dos robôs móveis é importante e necessária
para que os mesmos possam navegar, detectar e desviar de obstáculos, localizar-se e planejar sua
trajetória. Ela também é essencial quando o robô precisa reagir com rapidez às mudanças do
ambiente ou a um certo estímulo recebido.
A tarefa chave durante a navegação de um robô móvel é a capacidade de se localizar pre-
cisamente em seu ambiente. Ele pode realizar esta tarefa reconhecendo sua posição através de
informações coletadas por um sistema sensorial e confrontando tais informações com um mapa
global do ambiente, o qual consiste numa representação de sua estrutura física. Nas tarefas de
exploração de ambientes o robô navega adquirindo informações para a construção do mapa, e
neste caso surge uma tarefa adicional: o robô precisa se auto-localizar enquanto constrói o mapa.
O robô pode ainda navegar baseando-se em um mapa existente, resolvendo assim os problemas
de localização, planejamento de trajetórias e verificar se a posição final foi atingida. Tarefas de
navegação local, como desvio de obstáculos, podem ser realizadas sem o recurso de mapas do
ambiente, já para tarefas mais globais, como navegação, a utilização de algum tipo de descrição
ou representação do espaço se torna necessária. Além disso, para realizar eficientemente missões
mais complexas, robôs móveis autônomos precisam ser capazes de adquirir e manter modelos de
seus ambientes.
O problema de construir modelos é complexo e difícil de ser resolvido. Os seguintes fatores
impõem limitações práticas sobre a habilidade dos robôs de aprender e usar modelos precisos:
1. Sensores. Freqüentemente, sensores não são capazes de medir diretamente a quantidade de
interesse. Por exemplo, câmeras medem cor, iluminação e saturação de luz, enquanto que
para navegação pode ser interessante informações do tipo "existe uma porta em frente ao
robô".
2. Limitações Perceptuais. O alcance perceptual da maioria dos sensores é limitado. Para
adquirir informações globais, o robô tem que explorar ativamente seu ambiente.
1
3. Ruído nos sensores. Medidas dos sensores são tipicamente corrompidas por ruídos. Freqüen-
temente, a distribuição deste ruído não é conhecida.
4. Movimento. O movimento dos robôs pode ser impreciso. Além disso, é fato que erros
odométricos se acumulam ao longo do tempo.
5. Complexidade e Dinâmica. Ambientes de robôs são complexos e dinâmicos, sendo impossível
manter modelo s exatos do ambiente e predizer a precisão dos mesmos.
6. Necessidades de tempo real. Necessidades de tempo real demandam que os modelos sejam
simples e facilmente acessíveis. Por exemplo, modelos CAD de granulosidade fina de ambi-
entes internos complexos são freqüentemente inapropriados quando ações devem ser tomadas
em tempo real.
Para a construção de um mapa, o ambiente pode ser classificado segundo sua estrutura. Am-
bientes que contêm estruturas regulares, tais como planos e retas, são classificados como ambi-
entes estruturados. Já os ambientes que não possuem regularidade na informação utilizada para
representá-los, ou seja, não podem ser representados segundo quaisquer primitivas geométricas,
são considerados ambientes não estruturados. Uma outra classificação do tipo de ambiente é se
este é externo ou interno, podendo ser estruturado ou não. Um exemplo de ambiente externo
e estruturado é uma estrada utilizada como ambiente de navegação para carros autônomos, a
qual pode ser caracterizada (representada) por um plano de navegação com faixas que a delimita
(GUIACHETTI, CAMPANI e TORRE, 1998). Como exemplo de navegação em ambientes ex-
terno e desestruturado tem-se a navegação em planetas (GOLDBERG, MAIMONE e MATTHIES,
2002), ou em ambientes aquáticos (VAN DER ZAAN e SANTOS-VICTOR, 2001), onde nenhuma
estrutura regular pode ser extraída. Já os ambientes internos, como salas, laboratórios, escritórios,
podem ser considerados estruturados, pois em sua maioria contêm retas e planos, os quais podem
ser identificados para criação do modelo estrutural do ambiente (mapa).
Os mapas de ambientes internos podem ser construídos durante a exploração do ambiente, em
uma etapa anterior a navegação (YAMAUCHI, 1997), ou durante a execução desta (REKLEITIS
e DUJMOVIC, 1999). Têm-se também abordagens onde a navegação é executada sem o auxilio de
qualquer mapa (GOLDBERG, MAIMONE e MATTHIES, 2002). O processo de construção dos
mapas envolve então uma etapa de exploração, na qual a questão central é saber quais lugares do
ambiente, bem como suas relações serão identificadas e representadas. Classicamente, a construção
de mapas segue duas abordagens: geométrica e topológica. Uma vez que um mapa do ambiente
de navegação esteja disponível pa ra o robô, o mesmo pode ser utilizado como auxilio às tarefas de
localização e planejamento de trajetórias.
Além disso é indispensável a constante obtenção de informações do mundo externo por meio de
sensores, possibilitando uma adequada interação entre o robô e seu meio de navegação. A tarefa
de auto-localização pode fazer uso de um mapa do ambiente e da capacidade do robô perceber
sua posição local através de seu sistema sensorial, confrontando a informação deste com o mapa
armazenado. Dessa maneira, é interessante para o sistema de navegação obter a maior quantidade
de informações sobre o ambiente. Existem inúmeros tipos de sensores utilizados em aplicações de
robótica móvel, entre eles o ultra-som, laser e visão computacio nal. Na área de visão, sistemas de
visão omnidirecional têm sido amplamente utilizados por aumentarem o número de informaçõ es
disponíveis.
Dentro deste contexto - mapeamento de ambientes usando informações coletadas a partir de
imagens e sensores de ultrasom - que o presente trabalho se insere. Dessa maneira, são apre-
sentados métodos e técnicas utilizadas no desenvolvimento de sistemas de navegação de robôs
móveis, abordando problemas típicos de mapeamento de ambientes e autolocalização, bem como
apresentando diversas soluções propo stas na literatura da área.
2
1.1 Objetivo
Locomover-se, navegar com o objetivo de alcançar um local de destino partindo de um local de
origem, é a mais básica necessidade de um ser vivo. Sem tal capacidade, o mesmo não seria capaz
de obter recursos energéticos, evitar colisões com obstáculos perigosos que vêm em sua direção ou
escapar de possíveis predadores. Tal capacidade também é muito importante quando se deseja
dar autonomia e mobilidade aos robôs, fato este evidenciado pelo crescimento de p e squisas nesta
área e a grande variedade de métodos desenvolvidos. Entretanto, dentre os muitos modelos e
estratégias de navegação que os robôs podem usar para este fim, este trabalho foca a navegação
de robôs móveis basea da em mapas, os quais são representações internas do layout espacial do
ambiente explorado pelo robô. Neste contexto o presente trabalho contempla o uso de redes
neurais artificiais em co njunto com técnicas de classifica ção e extração de características a partir
de imagens com o objetivo usá-las no desenvolvimento do sistema de mapeamento e localização
do robô movel do Laboratório de Automação e Controle Evolutivo (LACE).
1.2 Motivação
O crescente uso e atribuição de tarefas a robôs móveis tem motivado pesquisas que objetivam
aumentar o grau de autonomia com que estes agentes realizam suas tarefas. Tendo em vista que
navegação é a tarefa mais básica e necessária para a realização das demais tarefas, um mapa,
construído pelo próprio robô, considerando neste processo suas características estruturais e sua
capacidade perceptual, é uma ferramenta extremamente útil, tanto para propósitos de navegação,
quanto para planejamento e otimização de trajetórias.
1.3 Estrutura do Trabalho
No Capítulo 2, define-se o problema de mapear ambientes, abordando técnicas que tratam do
mesmo num contexto da visão computacional e redes neurais artificiais. No Capítulo 3, descreve-
se o sistema de mapeamento proposto para o robô móvel do LACE. No Capítulo 4 , apresentam-se
os resultados obtidos a partir de testes de alguns módulos do sistema de mapeamento. No Capítulo
5, apresenta-se uma discussão sobre o trabalho em questão, b em como conclusões e propostas para
trabalhos futuros.
3
Capítulo 2
Fundamentação Teórica
Para navegar com sucesso dentro de seu ambiente, robôs móveis precisam ter a capacidade de
se auto-localizar precisamente, utilizando para isso um mapa. Localização baseada em mapas
é a técnica em que o robô usa seus sensores para perceber o ambiente e com essas informações
constrói um mapa local, o qual é comparado com o mapa global do ambiente já armazenado em sua
memória. Caso o resultado da comparação seja positivo, então um "match"foi alcançado e o robô
pode assim calcular sua posição dentro de seu ambiente. O procedimento geral para localização
baseada em mapas está ilustrado na Figura 2.1
O mapa global utilizado neste processo de comparação pode ser um modelo CAD do ambiente,
ou ser construído p elo próprio robô numa etapa anterior à navegação, chamada de exploração
do ambiente. Existem problemas no uso de modelos CAD, pois em geral eles são co mplexos e
o tempo de acesso aos mesmos inviavibiliza seu uso em aplicações de tempo-real. Já a segunda
abordagem, chamada de SLAMB - Simultaneous Localization And Map Building - consiste no
processo simultâneo de se construir um mapa do ambiente e se auto-localizar dentro dele. Tal
problema tém sido tópico central de muitas pesquisas na área, po is é fator crítico para navegação
em ambientes g randes, já que localização precisa é um pré-requisito para construção de um bom
mapa, e possuir um mapa preciso é essencial para se localizar precisamente dentro do ambiente.
Neste contexto, este capítulo contempla o estado da arte da literatura no que diz respeito
a técnica s de mapeamento e extração de características de ambientes para navegação de robôs
móveis. O objetivo deste estudo é fornecer uma base teórica de tais técnicas para se desenvolver
um método de mapeamento e localizaçã o para o rob ô móvel do LACE, o qual utilize os recursos
sensoriais disponíveis: sensores de ultra-som e visão computacional. Desse modo, o foco será dado
a métodos dentro deste contexto.
Figura 2.1: Procedimento geral para localizaçã o basea da em mapas.
4
2.1 Técnicas de Mapea mento de Ambientes para Navegação
de Robôs Móveis
Navegação baseada em mapas exige um processo de reconhecimento e análise de alto nível com o
objetivo de interpretar o mapa e estabelecer sua correspondência com mundo real. Os primeiros
esforços em navegação de robôs baseada em mapas f oram principalmente inspirados pelos processos
cognitivos dos seres humanos, assumindo-se que os erros de sensores e atuadores poderiam ser
detectados e corrigidos por um processo de nível mais alto, ou usando algum tipo de modificação
do ambiente para tornar a navegação mais fácil.
Basicamente, navegação baseada em mapas inclui três processos (BALAKRISHNAN, BOUS-
QUET e HONAVAR, 1999):
• Aprendizagem do mapa - processo de representar adequadamente o ambiente utilizando para
isso dados coletados durante sua exploração.
• Loca lizaçã o - processo que calcula a posição atual do robô utilizando para isso o mapa.
• Planejamento do caminho - tarefa de definir um percurso até um lugar de destino a partir
de uma posição inicial conhecida.
O terceiro processo depende dos dois primeiros, já que a p os ição atual do robô bem como o
mapa do ambiente são necessários para se calcular o percurso entre dois luga res. Num processo de
construção de mapas em tempo-real os dois primeiros processos estão intimamente relacionados,
pois o mapa é utilizado para se obter a posição atual e esta é utilizada para se construir o mapa.
Desta relação surge o problema SLAMB.
Ta l interdependência torna o problema de aprendizagem de mapas difícil e complexo, pois
erros que surgem a partir do cálculo da localização do robô são consequentemente incorp o rados
ao mapa e precisam ser detectados e corrigidos. Além disso, a tarefa de se autolocalizar durante
a aprendizagem do mapa (SLAMB) é mais difícil para um robô móvel se comparada quando a
mesma tarefa é executada usando-se um mapa já pronto e conhecido do ambiente. Isto porque
um problema adicional surge: o robô precisa garantir que a posição atualmente explorada ainda
não tenha sido mapeada.
Dessa forma, Filliat e Meyer (2003) dividem as estratégias de navegação de robôs móveis em
duas abordagens: (i) tratamento simultâneo dos problemas de localização e aprendizagem do
mapa, juntamente com uma análise de métodos de planejamento, e; (ii) estratégias de localização
que contam com um mapa completo e já conhecido do ambiente. Tendo em mente tal divisão,
neste capítulo é definida a abordagem clássica de construção de mapas, citando-se também as
principais estratégias definidas na literatura utilizadas para este fim.
2.1.1 Origens das Informações para Construção de Mapas
O processo de construção de mapas por robôs móveis necessita receber informações tanto do
meio explorado quanto do movimento e estado do robô. Tem-se então duas origens distintas de
informações que podem ser usadas para navegação baseada em mapas. A primeira origem é a
odométrica, que fornece informações internas sobre os movimentos e estado atual do robô, como
por exemplo, velocidade, aceleração, direção das rodas. A segunda origem é sensorial, a qual
fornece informações externas sobre o ambiente. De acordo com Filliat e Meyer (2003), os dados
provenientes de ambas as origens podem ser utilizados principalmente para:
• Loca lizar diretamente um lugar ou uma situação.
5
Figura 2.2: Modelo do sensor usado para inferir informações sobre lugares do ambiente não visi-
tados (Adaptado de (FILLIAT e MEYER, 2003).)
• Criar uma representação espacial bidimensiona l do ambiente através da fusão de ambas as in-
formações, usando para isso um modelo métrico (modelo de sensor) que converte informações
puramente externas numa representação espacial do ambiente. Neste caso, propriedades geo-
métricas do ambiente, tais como a posição dos objetos, são inferidas (Figura 2.2).
A primeira conseqüência do uso de um mo delo métrico, ou modelo do sensor é a possibilidade
da fusão das informações das diferentes origens em uma representação geométrica comum. Tal
propriedade é ilustrada na Figura 2.2.b, onde a utilização de um modelo do sensor permite que in-
formações sensoriais e odo métricas sejam fundidas para criar um quadro de referência global(parte
b superior), caso contrário, armazena-se apenas dados sensoriais que caracterizem cada local,
correlacionando-os utilizando odometria (parte b inferior). Uma outra importante conseqüência
é que um modelo do sensor permite que informações externas ou sensoriais sobre determinados
locais do ambiente ainda não explorados fisicamente sejam inferidas a partir de o utros locais já
fisicamente explorados. Na Figura 2.2.c a situação A3 pode ser inferida e relacionada a posiçã o
anterior sem que aquela seja fisicamente explorada (parte c superior). Sem tal modelo , somente
lugares não visitados podem ser reconhecidos e armazenados (parte c inferior).
Assim, se, por exemplo, um robô sentir uma parede a 3 metros e se mover 1 metro, ele pode
concluir que a parede está agora a 2 metros de distância. A conseqüência direta é que a relação
entre informações adquiridas em lugares diferentes pode ser usada para inferir a posição relativa
destes lugares. Como ilustrado na Figura 2.3, a utilização de um modelo do sensor permite: a)
detectar as similaridades entre as cenas (neste exemplo, uma abertura na parede) b) inferir a
posição geométrica relativa entre as duas situações percebidas (A1 e A2). Sem tal modelo pode-se
apenas concluir se as situações A1 e A2 correspondem ao mesmo local ou não.
As vantagens e desvantagens dessas duas origens de informações são complementares. O prin-
cipal problema com as informações de origem odométrica é seu erro acumulativo, que surge do fato
das mesmas serem resultado de um processo de integração de diferentes informações coletadas a
partir de diferentes recursos ou estados do robô. A conseqüência disso é a diminuição da qualidade
das mesmas, as quais não podem ser tomadas como verdadeiras em todo o período do tempo. O
contrário acontece com a qualidade das informações sensoriais, a qual é estacionária ao longo do
6
Figura 2.3: Modelo do sensor usado para inferir a p osiçã o relativa I1 a partir da comparação entre
dados sensoriais de dois lugares visitados A1 e A2.
tempo. Entretanto, existem dois principais problemas. O primeiro ocorre quando dois lugares
distintos são identificados pelo sistema como sendo o mesmo lugar, o u seja, quando dois lugares
distintos são confundidos e identificados como único. Tal problema é chamado na literatura de
perceptual aliasing. Já o segundo ocorre quando um dado lugar parece diferente ao lo ngo do tempo
devido, por exemplo, a diferentes condições de iluminação (KUIPERS e BEESON, 2002).
Cox (1991) define uma abordagem que integra as informações de ambas a s origens com o
objetivo de compensar as vantagens e desvantagens das mesmas. O obj etivo é permitir a navegação
por longos períodos de tempo. Em outras palavras, as informações sensoriais compensam o erro
acumulativo da origem odométrica, usando para isso, por exemplo, um sistema de controle em
malha fechada, enquanto as informações odométricas precisam tornar a origem sensorial não-
ambígua.
De maneira geral, o processo de integração de diferentes informações coletadas durante a
exploração do ambiente pode ser usado com objetivo de criar uma representação do ambiente
explorado, ou seja, a construção do mapa do ambiente pelo robô. Classicamente, os modelos
de representação espacial são divididos em duas grandes categorias: mapas geométricos e mapas
topológicos. Nos mapas geométricos, as posições de alguns objetos, principalmente os obstáculos
que o robô pode encontrar, são armazenadas em um sistema de referência global. Já nos mapas
topológicos, os lugares são definidos como posições que o robô pode alcançar. Tais definições
são armazenadas juntamente com alguma informação sobre a posição relativa entre eles, como
ilustrado na Figura 2.4.
Nas seções a seguir descrevemos a abordagem clássica de construção de mapas geométricos e
topológicos, citando alguns trabalhos de pesquisa nesta área.
2.1.2 Mapas Geométricos
No modelo geométrico, o ambiente é representado como um conjunto de objetos com suas res-
pectiva s coordenadas globais em um espaço bi-dimensional. Em outras palavras, o ambiente é
representado através de grades igualmente espaçadas, onde cada célula da grade pode, por exem-
plo, indicar a presença de um obstáculo na correspondente região do ambiente (MORAVEC e
7
Figura 2.4: Ilustração da Representação Clássica dos Mapas Geométricos e Mapas Topológicos.
ELFES, 1985).
A origem odométrica de informações é muito útil nesta representação, pois torna possível o
monitoramento direto da posição do robô neste espaço. O processo de construção de um mapa geo-
métrico começa quando as informações sensoriais são armazenadas e depois transformadas numa
representação bi-dimensional do ambiente, ou seja, num modelo geométrico. Esta transformação
produz um conjunto de objetos, ou obstáculos e suas respectivas posiç ões em relação ao robô.
A diferença chave em relação à abordagem topológica está no uso de modelos sensoriais, os
quais permitem a fusão das informações lidas pelos sensores com as informações odométricas
numa representação comum do ambiente. A estimativa de p o sição é contínua e usualmente mais
precisa do que na abordagem topológica, pois os lugares do ambiente são definidos de maneira
não-ambígua , sendo representados por suas respectivas coordenadas.
A dificuldade de se conseguir um modelo do sensor realístico é uma importante questão na
construção de mapas geométricos. Tal dificuldade surge do fato de que os dados lidos pelos sensores
podem depender não só das características intrínsecas a cada sensor, mas também de propriedades
físicas do meio. A construção de um mapa geométrico também depende da qualidade das infor-
mações odométricas, principalmente das estimativas de posição do robô. Já o planejamento de
caminhos em tais mapas é caro computacionalmente, pois a discretização do ambiente não se dá
num alto nível, a qual é a maneira mais natural a s eres humanos.
Representação de Características do Meio
Mapas geométricos podem armazenar explicitamente as características percebidas pelo robô, jun-
tamente com suas posições. Tais características podem ser representadas de diversas maneiras
e usando diferentes níveis de abstração. Pontos, ou objetos pontuais podem ser usados, como
uma definição intuitiva de um marco , como ponto de referência (LEVITT e LAWTON, 1990;
PRESCOTT,1995; FEDER, LEONARD e SMITH, 1999). A dificuldade desta técnica está no
desafio de se perceber um único p o nto e utilizá-lo para se estimar a posição do robô. Uma alterna-
tiva seria utilizar vários pontos espalhados sobre a superfície dos objetos, de modo que a união dos
mesmos através da leitura de sensores permita definir sua configuração espacial (LU e MILIOS,
1997; GUTMANN e KONOLIGE, 2000; THRUN, BUGARD e FOX, 2000).
8
Figura 2.5: Exemplo de mapeamento das características de um ambiente contendo segmentos
detectados sobre as fronteiras dos obstáculos.
Obstáculos ou as fronteiras dos objetos podem também ser representadas em um mapa geo-
métrico. Pode-se usar linhas para se definir as fronteiras poligonais dos objetos, as quais são
reconstruídas a partir da percepção dos pontos sobre sua superfície. A Figura 2.5 ilustra um
método de representação de caracterísitcas do meio utilizando linhas (Figura 2.5.b), as quais de-
finem as fronteiras das paredes encontradas no ambiente real (Figura 2.5 .b). Cilindros e Planos
detectados por sonares são usados em (LEONARD, DURRANT-WHYTE e COX, 1992) e carac-
terísticas de mais alto nível, tais como planos contendo linhas detectados por visão estéreo, são
usadas por Ayache e Faugeras (1989).
Alguns modelos geométricos podem incluir rótulos a cada cara cterística percebida no ambi-
ente representando com ele o grau de incerteza da mesma, o qual é usado para decidir se uma
determinada medida corresponde a uma determinada característica ou não. Em (LEONARD,
DURRANT-WHYTE e COX, 1992) os autores atribuem um valor de credibilidade a cada carac-
terística a fim de modelar se um dado objeto está realmente presente no ambiente ou s e é resultado
de erro de percepção. Conjuntos Fuzzy também podem ser usados para representar incertezas nas
posições das características (GSÓS e MARTIN, 1997).
Representação do Espaço Livre
Ao invés de se usar um conjunto de características pa ra representar objetos no mapa, pode-se
representar a porção do ambiente que está acessível ao robô. A abordagem mais popular que
segue esta idéia é a chamada grade de ocupação (MORAVEC e ELFES, 1985; THRUN, 1999,
YAMAUCHI, 1997). Neste caso o ambiente é discretizado em uma grade regular de alta resolução,
como ilustrado na Figura 2.6. Cada célula da grade é rotulada com uma probabilidade de estar
ocupada por algum obstáculo. Implementado desta maneira, o resultado é o consumo de muita
memória para armazenar mapas de ambientes grandes. A solução pode ser a discretização irregular
do espaço (ARLEO e GERSTNER, 2000).
9
Figura 2.6: Exemplo de Grade de Ocupação.
2.1.3 Mapas Topológicos
Na abordagem topológica, o ambiente é representado por um conjunto de lugares distintos entre
si, e de uma maneira que o robô possa ir de um lugar para o outro (KUIPERS e BYUN, 1991).
Isto significa que tal abordagem é baseada na relaçã o geométrica estabelecida entre os lugares
identificados e não nas suas respectivas posições absolutas com relação a um sistema coordenado
global, como acontece com a abordag em geométrica. O resultado é a representação do ambiente
de acordo com um grafo, de modo que os lugares identificados formam o conjunto de vértices ou
nós e todas as passagens ou ligações existentes entre cada par de vértices formam o conjunto de
arestas.
Kortenkamp e Weymouth (1994) definiram duas funções básicas de um mapa topológico:
1. Reconhecimento dos luga res: através desta função determina-se a posição atual do robô
dentro de seu ambiente. Em gera l, cada local identificado, ou nó definido, está relacionado
a sua respectiva descrição; e o processo de reconhecimento consiste em "casar"os dados
sensoriais percebidos com a descrição do nó.
2. Planejamento de caminhos: definição de um caminho que liga uma posição atual a uma
posição objetivo.
De acordo com Borenstein, Everett e Feng (1996), os mapas topológicos podem ser construí-
dos e mantidos sem qualquer estimativa da posição do robô. Isto sig nifica que os erros desta
representação são independentes dos erros relacionados ao cálculo da posição (TAYLOR, 1991 ).
Uma consequência direta é que uma grande área pode ser mapeada sem sofrer com erros acu-
mulativos gerados através de cálculos odométricos, já que todas as conexões são relativas e não
absolutas. Além disso, uma vez que o mapa esteja disponível, o processo de localização consiste
essencialmente em comparar um mapa local com as definições dos nós armazenadas no mapa
global.
A primeira vantagem da abordagem topológica sobre a geométrica é que aquela nã o necessita
de um modelo do sensor métrico ca paz de converter info rmações sensoriais numa representação
bi-dimensional do ambiente, ou seja, não necessita de um processo capaz de fundir as informações
de ambas as origens. A única necessidade é de um método capaz de armazenar e reconhecer os
10
lugares a partir de alguma leitura sensorial. Além disso, mapas topológicos estão intimamente
relacionados às capacidades perceptuais dos robôs, sendo desnecessária a extração da forma dos
objetos presentes no ambiente, como acontece na modelagem geométrica.
Ta l representação do ambiente permite a aplicação de process os de alto nível com menor
custo computacional. Por exemplo, a tarefa de planejar rotas é mais facilmente implementada
neste modelo, pois o tamanho do correspondente espaço de pesquisa é menor se comparado com
o conjunto de possíveis trajetórias num espaço bidimensional com alto grau de discretização.
Paralelamente a isso, o modo em que o ambiente é discretizado na abordagem topológ ica é mais
natural quando é feita por seres humanos, permitindo que os problemas sejam descritos e resolvidos
de ma neira mais intuitiva (por exemplo, dar a ordem vá ao quarto 10, ao invés de vá ao ponto
(x,y)).
A principal desvantagem desta abo rdagem é a necessidade de se explorar fisicamente todos os
lugares do ambiente para se adquirir informações sensoriais sobre os mesmos, sempre que estas
forem necessárias pa ra aumentar a precisão da estimativa da posição. O resultado disto é uma
exploração mais exaustiva do ambiente. Uma outra dificuldade reside no processo de definição
dos lugares, que pode ser prejudicado caso a leitura dos sensores não seja confiável ou o ambiente
seja muito dinâmico. Tal processo pode ser ainda mais difícil se existir a possibilidade de lugares
distintos serem confundidos (perceptual aliasing), ou o mesmo lugar parecer diferente dependendo,
por exemplo, do ponto de vista captado pelo sensor (perceptual variability).
Definição dos Nós
A primeira decisão de projeto de um sistema de mapeamento topológico é a escolha de quais
lugares serão representados. De acordo com Filliat e Meyer, (2003), esta decisão pode ser condi-
cionada a escolha de um agente humano ou ser completamente dependente do ambiente que será
explorado. Sendo assim, ele define em seu trabalho três abordagens distinta s para se definir os
nós do mapa. Na primeira, os nós são definidos por operadores humanos, e ao robô cabe apenas a
responsabilidade de detectar os tipos de lugares já pré-definidos. Neste caso, a escolha mais comun
para a representação dos nós são corredores, portas e intersecções. O problema desta técnica está
na po ssibilidade de ocorrer a confusão de diferentes lugares, os quais deveriam ser definidos como
nós distintos.
Na segunda abordagem, ao invés de se especificar completamente os nós, o projetista pode
especificar apenas os lugares que devem ser detectados, deixando ao robô a tarefa de definir
precisamente cada nó. Esta é a metodo log ia adotada pelo método lugares distintos, desenvolvido
por Kuipers e Byun (1991). Neste modelo os lugares são definidos como áreas onde uma lei
de controle pode ser definida sendo capaz de guiar o robô através desta área. Os lugares são
então caracterizados por situações sensoriais únicas no ponto onde a lei de controle é definida e
aplicada. Esta técnica é importante, pois fornece uma solução ao problema do ponto-de vista,
o qual surge quando o ambiente é discretizado por humanos de maneira que os lugares não são
caracterizados por situações sensoriais únicas do ponto-de-vista do robô. Em outras palavras, uma
situação senso rial nunca encontrada antes nem sempre co rresponde a um novo lugar, mas pode
corresponder a um lugar já conhecido e definido, contudo, sobre um diferente ponto-de-vista.
Outras técnicas foram desenvolvidas seguindo a mesma abordagem. Engelson e McDermott
(1992) definiram os gateways, os quais são como lugares, detectados por sonares, definidos nos
locais onde o robô pode alterar a direção do seu percurso. Exemplos típicos para a escolha
desses nós são portas e interseção de corredores. Além disso, ele sugere a gravação das chamadas
assinaturas de imagens tomadas em cada lugar para definir cada nó, sendo que uma assinatura
de imagem consiste num conjunto de medidas (tais como distribuição de cor) feitas sobre uma
imagem e que a caracteriza. Tal representação compacta da imagem (comparada com o tamanho
11
da imagem original) resulta num armazenamento otimizado e possibilita a comparação entre as
imagens. No modelo desenvolvido em (FILLIAT e MEYER, 2003), os lugares pré-definidos que
devem ser encontrados e caracterizados pelo robô são chamados de lugares canônicos. Em cada
um deles uma situação sensorial é gravada com o objetivo de caracterizá-lo mais precisamente.
O terceiro método é caracterizado pela definição automática do s nós. De acordo com ele os
nós são definidos como áreas onde as percepções do robô são similares, sem levar em consideração
a posição do robô em tais áreas. As definições dos nós são feitas obtendo-se os dados sensoriais
e classificando-os, de uma maneira não supervisionada, de modo que cada classe de percepção
corresponde ao lugar onde o robô pode estar loc alizado . Conclui-se então que tal abordagem de-
pende unicamente da capacidade perceptual do robô e não depende de qualquer definição humana
de qual lugar deve ser caracterizado. Este último tipo de discretização do espaço é uma escolha
natural dos modelos que tentam imitar as capacidades de navegação dos animais, porque não
pressupõe qualquer definição de lugar de a lto nível, tais como portas ou corredores (FILLIAT e
MEYER, 2003). Seguindo a mesma abordagem, lugares também podem ser definidos usando-se as
direções ou distâncias de marcos (LEVITT e LAWTON, 1990), ou através de alguma característica
extraída a partir de imagens panorâmicas (ULRICH e NOURBAKHSH, 2000).
Quando a terceira estratégia é escolhida, deve-se então definir um critério para determinar
quando o robô deve representar um novo lugar, ou nó. Considerando a hipótese de que num
nó a situação sensorial percebida permaneça constante, a escolha mais natural seria definir um
novo nó quando a variação perceptual ultrapassar um certo limiar. Isto é usado em vários métodos
(MATARIC,1992; FRANZ et. al, 1998), mas exige que as situações perceptuais sejam monitoradas
em tempo-real. Outros modelos se baseia m na distância entre os lugares, definindo um novo nó
sempre que a distância do nó anterior exceder um certo limite (YAMAUCHI e BEER, 1996;
WICHERT, 1998).
Definição das Arestas
Uma aresta consiste numa ligação, conexão entre dois nós de um grafo, o qual representa o layout
espacial do ambiente. Logo, a principal informação fornecida por uma aresta é quais nós estão em
suas extremidades. Além disso, pode-se obter e armazenar em cada aresta informações adicio nais
extraídas através de sensores odométricos, tais como a posição relativa dos nós. Tal procedimento
tem a vantagem de limitar o erro da informação lida, pois a mesma é atualizada sempre que um
novo nó é encontrado. Este tip o de uso e armazenamento de informações gera o chamado Mapa
Diktiométrico (ENGELSON e MCDERMOTT) (Figura 2.7.a).
Cada nó também pode assumir uma p o sição global referenciada no mapa. Isto torna possível
a recuperação geral do layout do ambiente, com o cuidado de sempre compensar os erros contidos
nos dados de origem odométrica. Neste caso, cada nó a rmazena as informações métricas sobre
sua posição absoluta, o que gera o chamado Mapa Diktiométrico Absoluto (MATARIC, 1992;
WICHERT, 1998) (Figura 2.7.b).
Alguns tipos de informações sensoriais definem implicitamente as arestas entre do is nós. Isto
acontece, por exemplo, quando marcos pontuais e suas respectivas distâncias e direções são usadas
para caracterizar os nós no mapa. Marcos comuns detectados de diferentes lugares podem indicar
adjacência entre os diferentes nós, e o fato de que os nós tenham marcos em comum pode ser
usado como uma aresta implícita (LEVITT e LAWTO N, 1990 ).
2.2 Aprendendo Mapas
Como mencionado anteriormente, o processo de construção de mapas não p ode ser tratado sem
levar em consideração o problema da auto-localização, surgindo assim o termo SLAMB (Simulta-
12
Figura 2.7: Dois diferentes tipos de mapas obtidos quando informações métricas são adicionadas
aos mapas topo lóg icos. A parte a ilustra o mapa dikitiométrico, o qual armazena a posição relativa
entre nós adjacentes. Já a parte b ilustra o mapa dikitiométrico absoluto, que armazena a posição
absoluta dos nós.
neous Localization and Map Building). Como resultado, a tarefa de aprender um mapa torna-se
muito difícil, já que erros no cálculo da posição atual do robô sã o incorporados ao mapa e precisam
ser detectados e corrigidos.
Paralelamente a isto, pode-se dizer que se autolo ca lizar durante a construção do mapa é mais
difÍcil para um robô se comparada quando a mesma tarefa utiliza um mapa já pronto do ambiente.
Isto porque uma questão adicional surge: identificar se o local atualmente ocupado já foi ou não
mapeado. Esta avaliação é essencial para a construção de um mapa que descreva o ambiente com
fidelidade, além de, neste caso, inviabilizar muitas técnicas aplicáveis ao problema de localização
utilizando um mapa já conhecido do ambiente.
Tendo isto em mente, nesta seção definiremos algumas das técnicas utilizadas para auto-
localização de robôs móveis, as quais podem ser aplicadas ao problema do SLAMB. Entretanto,
nos restringiremos aos métodos de localização aplicados na construção de mapas topológicos,
abordagem esta adotada neste trabalho.
2.2.1 Aprendizagem de mapas topológicos
Construir um mapa topológico de um ambiente consiste em criar um nó no mapa para cada local
novo identificado, fazendo também sua respectiva conexão com os nós adjacentes. As informações
sobre a descrição do nó e sua respectiva posição rela tiva são armazenadas nos nós e arestas,
respectivamente. Em geral, utiliza-se informações sensoriais para se descrever os nós, sem a
necessidade de se recorrer a modelos sensoriais métricos, como mencionado na Seção 2.1.1. Já
as informações armazenadas nos arestas variam desde a simples definição de adjacência até uma
definição precisa e métrica da posição relativa do nó.
Entretanto, o processo de adição de um novo nó no mapa é antecedido por uma etapa de reco-
nhecimento, através da qual verifica-se se a situação atual corresponde ou não a um nó já existente
no mapa. Neste caso, duas situações distintas devem ser tratadas durante o reconhecimento dos
nós: a existência ou não de ambiguidade sensorial (perceptual aliasing).
13
Quando não ocorre o problema da confusão perceptual descrito na Seção 2.1.1, o processo de
criação e inserção de um novo nó no mapa ocorre diretamente: a situação atualmente percebida é
comparada com as descrições dos nós já definidos; o nó mais parecido com tal situação sensorial não
é diretamente reconhecido, mas sim aplica-se um limiar para decidir se a posição atual corresponde
a este nó ou a um lugar nunca antes visto. Se a similaridade máxima estiver acima deste limiar,
reconhece-se o respectivo nó como a posição atual do robô; caso contrário assume-se que o robô está
em um novo lugar, criando-se e inserindo-se um novo nó no mapa (BOREINSTEIN, EVERETT
e FENG, 1996).
Quando o sistema tem que lidar com o problemas de ambiguidades perceptual, a estratégia
descrita acima é útil somente para reconhecer uma situação sensorial nunca antes vista, mas não
é eficiente caso o contrário aconteça. Por exemplo, quando uma situação sensorial for similar
a uma situação descrita por um nó já definido, aquela pode corresponder ao respectivo nó ou
consistir em um novo lugar. Para resolver tal conflito o usual é levar em consideração informações
odométricas. Em geral, sistemas que usam informações de origem odométrica na estratégia de
localização calculam uma previsão para a posição atual e aplicam a técnica usada em situações não-
ambíguas em uma área limitada da vizinhança da posição predita. Neste caso, a área pesquisada
pode incluir os nós conectados ao nó reconhecido na etapa a nterior da exploraçã o ou a uma
determinada distância do nó predito.
Paralelamente ao reconhecimento e criação dos nós, existe também a preocupação com as
conexões que devem ser estabelecidas entre o nó atual e o nó reconhecido o u criado na etapa
anterior da exploração. Neste caso, o resultado é a fusão de informações odométricas, já que o
último nó reconhecido é usado para atualizar ou criar a conexão entre estes dois nós. Têm-se
na literatura duas abordagens: métodos que atualizam as informaçõ es dos arestas localmente e
métodos que propagam estas atualizações para todo o mapa.
Na primeira abordagem estão os traba lhos de Burgess et. al. (1997) e Levitt e Lawton (1990).
Nestes, os nós são definidos por marcos visíveis a partir de po sições específicas, de modo que
a adjacência entre dois nós está implicitamente definida, a qual pode ser inferida quando dois
nós compartilham um mesmo marco. Bachelder (BACHELDER e Waxman, 1995) usa uma rede
neural para prever qual nó pode ser alcançado a partir do nó atual, de modo que a informação de
adjacência também é implícita. Entretanto, a maioria dos modelos criam explicitamente arestas
entre os nós, podendo armazenar nos mesmos alguma informação métrica de distância relativa,
por exemplo, ou apenas indicar adjacência (BOREINSTEIN, EVERETT e FENG, 1996).
Finalmente, alguns métodos são capazes de atualizar as informações dos arestas globalmente,
sempre que novas informações odométricas estiverem disponíveis. Os procedimentos correspon-
dentes consideram os arestas do mapa como espécies de molas. A deformação das mesmas corres-
ponde ao tamanho do aresta medido por odometria. As molas são conectadas segundo o layout do
mapa, e o objetivo do algoritmo é estabelecer o estado de equilíbrio na rede de molas, o que resulta
num mapa consistente, cujos tamanhos dos arestas se aproximam ao máximo dos tamanhos real-
mente medidos. Tais algoritmos fornecem um método heurístico para reconsiderar atualizações
passadas na presença de novas informações odométricas, mas provam serem eficientes e confiáveis.
2.3 Visão Computacional
Para Gomes e Velho (1994) o objetivo da Visão Computacional é "obter, a partir de uma imagem,
informações geométricas, topológicas ou físicas sobre o cenário que deu origem a essa imagem."
Segundo Fairhurst (1988) Visão Computacional pode ser dividida em duas áreas inter-relacionadas:
Processamento de Imagens e Reconhecimento de Padrões. A primeira compreende técnicas uti-
lizadas com o objetivo de enfatizar alguma característica da imagem como, por exemplo, bordas
14
e contornos de objetos. Já a segunda, recebe a imagem pré-processada como entrada e aplica
técnicas com o objetivo de extrair informações de alto nível.
Dessa maneira, um sistema computacional pode realizar algum tipo de tarefa tendo como
entrada uma ima gem. O procedimento g eralmente adotado consiste em pré-processar a imagem
adequando-a para a etapa subsequente: extração de conhecimento através de reconhecimento de
padrões. Neste ca so, tal sistema utiliza uma imagem como fonte de informações externas para
executar a tarefa para a qual ele foi programado.
Dentro deste contexto muitos métodos para mapeamento, localização e navegação de robôs
móveis têm sido desenvolvidos, os quais se utilizam da visão computacional para aumentar a
autonomia com que os robôs realizam suas tarefas (RAO et. al.,2002; ANDREASSON, 2004;
MARTINEZ, 2005; CHEN e BIRCHFIELD, 2006).
2.3.1 Reconhecimento de Padrões
Tendo em vista que o objetivo da Visão Computacional é extrair informações a partir de imagens,
uma análise de alto nível da mesma é de fundamental importância, pois com ela é possível obter
as informações daquilo que a imagem tenta comunicar.
Um sistema de reconhecimanto de padrões é dividido em dois estágios: extração de atributos
e classificação. O atributo é a medida de uma característica feita no padrão de entrada, que
pode ser numérica (área ou volume) ou simbólica (cor). Além disso, os atributos podem ser
globais (perímetro, área, momentos), locais (segmentos de reta, vértices) ou relacionais (regiões
do objeto, distâncias) e sua escolha deve considerar o contexto da aplicação, pois na maioria das
vezes, ela determina o desempenho do sistema de reconhecimento de padrões (CHIN e DYER,
1986).
Normalmente, a escolha dos tipos de atributos utilizados pelo sistema depende dos tipos de
objetos ou padrões a serem reconhecidos. Idealmente um atributo invariante teria valor constante,
independente do grau de transformação sofrido pela imagem do objeto. Porém, na prática, diversas
fontes de incerteza são acrescentadas ao mo delo ideal, resultando, em uma variabilidade de valores
medidos.
Para obter-se uma classificação correta os atributos devem definir adequadamente os tipos de
classes. Após a extração do atributo, o classificador a partir do valor calculado deve mapear um
padrão para a sua classe correspondente. As técnicas mais comuns são: medida de distâncias e
métodos estatísticos (BEALE e JACKSON, 1992).
O uso de apena s um atributo geralmente não é suficiente para determinar a que classe um
padrão pertence. Para que a classificação seja correta vários atributos relevantes são extraídos
do padrão. Estes farão parte de um vetor com tamanho n, onde n é o número de características.
Então, este vetor, chamado de vetor atributos, fará parte de um espaço com n dimensões chamado
de espaço de atributos.
O desenvolvimento do sistema de reconhecimento de padrões se dá em três fases: a primeira
fase consiste no treino do sistema, onde é determinada a forma de discriminaçã o das classes; na
segunda fase o sistema é testado com exemplos não usados na primeira fase, para determinar a
sua capacidade de generalização; e na terceira fase o sistema é usado em um ambiente real.
Para exemplificar o funcionamento de um sistema de reconhecimento de padrões, sup o nha um
espaço bi-dimensional onde estão os vetores associados aos atributos de uma imagem de treino,
cada imagem associada a dois atributos, como ilustrado pela Figura 2.8. De forma simplificada é
possível determinar duas classes diferentes, pois é clara a distinção entre os grupos de círculos e
quadrados. Uma função de discriminação irá definir as duas classes posicionando um hiperplano
entre elas, como mostra a mesma Figura. Esta função decide a qual classe um padrão pertence.
Ta mbém é possível determinar a qual classe uma imagem pertence medindo a distância entre
15
Figura 2.8: Função de discriminação definindo as duas classes.
os vetores mais próximos de ambas as classes, como mostra a Figura 2.9. Por isso este método é
chamado de vizinho mais próximo. O vetor que estiver mais perto determina a qual classe a nova
imagem pertence. Em um espaço de atributos onde as classes estão bem separadas este método é
adequado, caso as classes estejam próximas, o padrão pode ser classificado incorretamente.
Extração de Características Invariantes Lo cai s
Como descrito anteriormente, um espaço de atributos invariantes, idealmente, deve permanecer
constante independente das transformações sofridas pelos padrões descritos por ele. Num contexto
da visão computacional, as características extraídas a partir de imagens devem permanecer cons-
tantes independente de alterações sofridas por elas, como por exemplo, mudanças de iluminação,
projeção, escala, dentre outras. Tal propriedade tem sido tópico de pesquisas na área da robótica,
o que pode ser justificado pela necessidade de métodos de reconhecimento de cenas robustos a
transformações sofridas pelas imagens, as quais são inerentes ao processo de coleta.
Lowe (1999) definiu em seu trabalho uma nova proposta para extração de características locais
invariantes a escala, rotação, translação e parcialmente invariantes a mudanças de iluminação,
transformações afim e projeções 3D. O método chamado de Scale Invariant Feature Transform
- (SIFT), transforma a imagem numa coleção de vetores de características locais invariantes às
transformações citadas anteriormente. O algoritmo SIFT é dividido em 4 fases:
1. Construção do espaço-esca la:
O algoritmo SIFT é baseado na definição de locais dentro de espaço-escala de uma imagem
onde caracterísitcas possam ser extraídas. O primeiro estágio é a construção de um espaço-
escala que consiste de um conjunto de versões suavizadas da imagem original. Para a imagem
I, o espaço-escala é construído usando-se a função gaussiana com valores diferentes de σ:
L(x, y, σ) = G(x, y, σ) ∗ I(x, y) (2.3.1)
16
Figura 2.9: Classificação pelo vizinho mais próximo.
onde ∗ indica a operação de convolução em x e y, e
G(x, y, σ) =
1
(2πσ
2
)
exp
−(x
2
+y
2
)
σ
2
(2.3.2)
O passo inicial é convoluir a imagem original I usando a função G(x, y, σ). O resultado é uma
imagem suavizada L(x, y, σ). Esta operação é repetida usando-se G(x, y, kσ), resultando em
outra imagem suavizada L(x, y, kσ). A diferença D(x, y, σ) entre estas duas imagens é dada
por:
D(x, y, σ) = (G(x, y, kσ) − G(x, y, σ)) ∗ I(x, y) = L(x, y, kσ) − L(x, y, σ) (2.3.3)
A função D(x, y, σ) é chamada de Imagem Diferença da Guassiana (Difference of Gaussians
- DoG), a qual pode ser calculada a partir da diferença entre duas imagens localizadas em
escalas adjacentes.
As imagens convoluidas são agrupadas por oitavas, onde uma oitava correspo nde ao dobro
do valor de σ, e o valor de k é selecionado a fim de se obter um numero fixo de imagens
suaves por oitava.
2. Detecção dos pontos extremos no espaço-escala:
Nesta fase, o algoritmo SIFT utiliza a função DoG para selecionar extremos locais na sua
própria escala, e nas escalas adjacentes (uma escala acima e uma escala abaixo). Estes
pontos são candidatos aos chamados pontos-chave. Para acelerar a pesquisa, cada ponto é
comparado com os 8 vizinhos de sua escala, e com seus 9 vizinhos em cada escala adjacente,
como ilustrado na Figura 2.10.
O extremo local pode ser definido como um dentre dois casos:
17
Figura 2.10: Detecção dos extremos locais. O pixel marcado com X é comparado a seus 26 vizinhos
, numa janela de 3x3x3 onde é aplicada a função DoG.
• o ponto positivo maior que seus 26 vizinhos
• o ponto negativo menor que seus 26 vizinhos
Uma vez que todos os po ntos-chave são encontrados, três operações são realizadas:
• determinar precisamente a posição de cada ponto-chave
• o contraste dos pontos-chave são comparados com um dado limiar; os que possuirem
contraste abaixo deste valor são removidos.
• respos tas ao longo das arestas são eliminadas
3. Definição da orientação:
Para determinar a orientação de um ponto-chave, um histograma de orientação do gradiente
é calculado na vizinhança do ponto-chave. A contribuição de cada pixel vizinho é ponderada
pela magnitude do gradiente e por uma janela gaussiana com um valor de σ 1.5 vezes maior
que a escala do ponto-chave. Os picos no histograma correspondem a orientações dominantes.
Todas as propriedades do ponto-chave são medidas com relação a sua orientação, a qual
garante invarância a rotação.
4. Descritores dos pontos-chave:
O descritor é definido por um vetor contendo os valores de todas as entradas do histograma
definido na fase anterior. Tamini et al. (2006) utilizou em seu trabalho um vetor com 128
elementos descrevendo cada ponto-chave, s endo este vetor também modificado para reduzir
os efeitos da variação de iluminação. Se, Lowe e Little (2001 ) usaram restrições de escala e
orientação para "casa r"imag ens stereo num processo de localizaçã o de robôs móveis.
18
2.3.2 Imagem Omnidirecional
Imagens omnidirecionais são imagens que representam a cena co m um ângulo de visão de 360
◦
ao
redor do sensor, expandindo, assim, a capacidade dos sensores convencionais de gerar apenas ima-
gens restritas a uma pequena região. O reusltado disso é o aumento na quantidade de informações
disponíveis na imagem.
Os sensores omnidirecionais podem ser construídos de diversas maneiras: uso de várias câmeras,
mecanismos de rotação, lente olho-de-peixe ou, sistemas catadióptricos formados por câmeras
alinhadas a espelhos.
Sensores que utilizam várias câmeras dispostas ao redor de um po nto em forma de círculo
geram um imagem panorâmica sem distorções e com alta resolução geométrica, entretanto tais
sensores têm alto custo. As imagens com maior resolução geométrica também demandam maior
tempo de processamento.
Uma câmera omnidirecional que utiliza um motor para executar o movimento de rotação tem
uma construção mais elaborada, além de gerar imagens com boa resolução. Um exemplo deste
mecanismo é mostrado na Figura 2.11. O tempo para capturar a imagem dos 360
◦
da câmera
depende da velocidade de rotação do motor e de quantas imagem serão necessárias para formar a
imagem panorâmica, isso torna esta abordagem inadequada para o uso em robôs móveis.
Figura 2.11: Camera com mecanismo de rotação (MECANISMO, 2008).
Uma lente olho de peixe tem um grande campo de visão, entretanto as imagens geradas por
ela são muito distorcidas. Lentes que po ssuem um menor ângulo de visão, como a ilustrada na
Figura 2.12, geram imagens menos distorcidas.
Sistemas catadióptricos formados por espelhos cônicos, esféricos ou hiperbólicos alinhados a
uma câmera de vídeo são muito usados em robótica móvel. A simplicidade deste sistema, e conse-
quentemente o baixo custo, são pontos favoráveis. Contudo, as imagens são de baixa resolução e
apresentam algumas distorçõ es , que podem ser corrigidas. A Figura 2.13 mostra um sensor omni-
direcional construído com um espelho cônico e uma webcam. A Figura 2.14 mostra uma câmera
omnidirecional que utiliza um espelho hiperbólico.
Espelho Cônico
Como foi mencionado acima câmeras que fazem uso de espelhos trazem vantagens sobre os outros
tipos de câmeras omnidirecionais, principalmente por sua simplicidade. Entretanto, dentre estas
câmeras o espelho cônico apresenta vantagens em relação ao esp elho com curvatura radial (LIN e
BAJCSY, 2001). Estes espelhos produzem imagens com distorções radiais, ao contrário do espelho
19
Figura 2.12: Lente olho-de-peixe NIKON FC-E8 (NIKON, 2008).
Figura 2.13: Exemplo de um espelho cônico com webcam.
cônico que não tem curvatura radial e consequentemente não produz tais distorções. Espelhos com
seção tranversal curva realçam os objetos refletidos no centro e comprimem a imagem relativa ao
horizonte, prejudicando a imagem na área de maior interesse para o robô. Ta l propriedade está
ilustrada na Figura 2.15, onde pode-se perceber que os objetos loca lizados no centro do espelho
(céu) são realçados, em detrimento dos objetos de maior interesse.
Espelhos cônicos não possuem esta deficiência, pois sua seção transversal é plana. Isto pode
ser observado na Figura 2.16.
A Figura 2 .17 mostra a seção tranversal de um espelho cônico e a sua geometria. A câmera,
com campo de visão Φ é refletida em dois espelhos planares, criando dois pontos de vista efetivos.
Cada ponto de vista tem campo de visão
Φ
2
entre seu raio de projeção central e o raio extremo.
O ângulo do cone é de 90
◦
para garantir que as duas linhas efetivas de visão (raios centrais 1 e 2)
estejam diretamente orientada s, uma em relação a outra. R é o raio da base do espelho (SPACEK,
2003).
O valor máximo do campo de visão da câmera é dado pela equação 2.3.4, onde d é a distância
da câmera até o espelho e R é o raio do espelho.
Φ
m
ax = 2 × arctan(
R
R + d
) (2.3.4)
A Figura 2.18 mostra a seção tranversal do espelho, onde P é um ponto no espaço com altura
h e distância do espelho r. O valor de d + v representa um cilindro virtual que envolve o espelho,
onde é projetada a imagem de P com altura h
i
. O ponto corespondente na imagem é determinado
pelas coordenadas polares (r
i
, θ). Então a altura de h
i
é calculada pela a equação 2.3.5 e a altura
de h
c
é calculada pela equação 2.3.6.
20
Figura 2.14: Sensor omnidirecional com espelho hipe rbólico (CAMERA, 2008).
Figura 2.15: Imagem omnidirecional obtida a partir de um espelho hiperbólico alinhado a uma
câmera. Note o realce dado aos objetos centrais da imagem (céu) (SPACEK, 2003).
h
i
=
vh
d + r
(2.3.5)
h
c
=
dh
d + r
(2.3.6)
Imagem Panorâmica
Sensores omnidirecionas que utilizam espelho geram imagens, como a da Figura 2.19, onde o
ambiente ao redor do espelho é apresentado ao redor de um ponto central, determinado pela
parte mais alta do espelho. Não é possível observar o ambiente nesta imagem, para isto deve ser
extraida uma imagem panorâmica, como a da Figura 2.20, onde cada coluna representa um ângulo
da imagem refletida no espelho.
A imagem panorâmica é obtida com o mapeamento da imagem original em coordenadas pola res,
onde o centro das coordenadas é o ponto mais alto do espelho e o raio máximo é a borda inferior
21
Figura 2 .16: Imagem obtida a partir de um espelho cônico alinhado a uma câmera. O realce é
dado a objetos úteis ao longo do horizonte refletido (SPACEK, 2003).
do espelho. Desta forma a partir das coordenadas na imagem panorâmica é possível calcular as
coordenadas do pixel correspondentes na imagem original com as equações 2.3.7 e 2.3.8, onde
(x, y) são coordenadas da imagem panorâmica, x
m
e y
m
são as dimensões da imagem desejada,
r
m
raio do esp elho, θ
i
ângulo em radianos do pixel desejado e h
i
é a distância do centro ao pixel
(SPACEK, 2003).
x =
x
m
2π
θ
i
(2.3.7)
y =
y
m
r
m
h
i
(2.3.8)
Para determinar as dimensões da imagem panorâmica o valor de x
m
ou y
m
deve ser escolhido
e o outro deve ser calculado com a equação 2.3.9. A escolha do valor interfere diretamante na
qualidade da imagem obtida; valores muito altos levam a uma imagem com pouca qualidade,
principalmente na região correspondente ao centro da imagem omnidirecional.
x
m
y
m
= 2π (2.3.9)
É possível obter uma imagem panorâmica com melhor qualidade com o uso de uma imagem
omnidirecional com resoluçãao geométrica alta. Com o valor máximo de h
i
maior, o número de
pixels da circunferência determinada por h
i
é maior, então para todos os outros valores de h
i
haverá mais pixels nas circunferências menores. A região central da imagem é a que apresenta
menor qualidade devido ao baixo número de pixels, como pode ser observado na Figura 2.20 , então
esta região pode ser desprezada.
22
Figura 2.17: Geometria do espelho cônico (SPACEK, 2003).
2.4 Redes Neurais
A motivação para utilizar o paradigma da computação neural com o objetivo de extrair conhe-
cimento vem do fato de esta ser executada de uma maneira essencialmente paralela, o que não
acontece quando se utiliza um computador convencional.
O paradigma da computação neural surge para complementar a computação convencional
através de um modelo inspirado no cérebro humano, que é capaz de lidar com tarefas que exi-
gem paralelismo. Tal modelo é formado por estruturas de processamento simples, chamadas de
neurônios, que estão altamente interconectadas.
De acordo com Haykin (2001 ), uma rede neural artificial (RNA) se assemelha ao cérebro
humano em dois aspectos:
• Aprendizagem: processo utilizado pela RNA para obtenção de conhecimento a partir de seu
ambiente.
• Pesos Sinápticos: forças de conexão emtre os neurônios utilizadas para armazenar o conhe-
cimento adquirido.
A computação neural difere da computação co nvencional no método utilizado para determinar
qual será o resultado gerado pelo sistema. Computadores são programados com instruções simples,
que juntas formam um programa, que irá desempenhar uma tarefa e gerar resultados. Uma RNA
ao invés de ser programada, é treinada durante o processo de aprendizagem para reconhecer
padrões e abstrair conhecimento, para, a partir dele, gerar resultados.
Não existe a necessida de de devenvolver uma máquina com neurônios interconectados para im-
plementar a computação neural. Ao contrário, um neurônio pode ser representado por um modelo
23
Figura 2.18: Projeção em um espelho cônico (SPACEK, 2003).
Figura 2.19: Imagem omnidirecional não pré-processa da.
matemático que pode ser implementado em um computador convencional e, co nsequentemente,
podem ser implementados diversos neurônios interconectados que formarão uma RNA.
2.4.1 Neurônios Artificiais
O neurônio artificial é uma simplificação matemática do modelo biológico. É a unidade fundamen-
tal de processamento de informaçã o de uma RNA. A Figura 2.21 mostra o modelo de um neurônio.
Ele possui entradas, que representam os dendritos, um corpo, que realiza a soma ponderada das
entradas, e uma saída que representa o axônio. Cada sinal de entrada possui um peso as sociado
que é utilizado na soma ponderada.
Da mesma forma que um neurônio biológico emite um sinal pelo axônio, mediante um estímulo
acima de um limiar, o neurônio artificial também possui um limiar que é co mparado ao resultado
da soma ponderada e, caso o valor seja maior, o neurônio dispara. A equação 2.4.10 representa o
mencionado acima, onde n é o número de nodos, X
i
é o valor de entrada do nodo i, W
i
é o peso
do nodo i e θ é o limiar.
n
i=1
x
i
w
i
≥ θ (2.4.10)
O modelo apresentado acima é conhecido na literatura como modelo de neurônio de McCulloch
e Pits. Com o objetivo de simplificar o modelo biológico, McCulloch e Pits consideram que as
entradas são disparadas sincronicamente e um disparo não recebe influência do disparo anterior.
24
Figura 2.20: Imagem panorâmica obtida a partir de uma imagem omnidirecional.
Figura 2.21: Modelo de McCulloch e Pitts, (Haykin, 2001).
2.4.2 Perceptron
Até então os nodos de McCulloch e Pits implementavam somente funções boo leana s, entretanto
o perceptron e seu algoritmo de aprendizado possibilitam a implementação de qualquer função
linearmente separável.
O perceptron é um modelo de rede composto por neurônios de McCulloch e Pits, que estão
distribuídos em suas diversas camadas que são: retina ou camada de entrada, com nodos de pesos
fixos; e camada de saída formada por nodos com pesos variáveis, cada nodo representando duas
classes. Como só a última camada é ajustada pelo algoritmo de aprendizado, o perceptron é
considerado de uma só camada.
Rosenblatt, além de propor este modelo, demonstrou o teorema de convergência do percep-
tron, que garante o funcionamento do algoritmo de aprendizado para a classificação de pa drões
linearmente separáveis. Este tipo de RNA posiciona o hiperplano que separa as classes, como é
mostrado na Figura 2.22.
2.4.3 Perceptron Multicamadas (MLP)
Para aumentar o poder computacional do perceptron foi criada uma RNA com mais de uma
camada de neurônios. As redes multicamadas (multilayer perceptron - MLP) possuem uma camada
de entrada, uma ou mais camadas intermediárias, chamadas de camadas escondidas, e uma camada
de saída, como ilustrado na Figura 2.23. Estas camadas estão conectadas de tal forma que a saída
dos neurônios de uma camada está ligada à entrada de neurônios de outra camada. Uma rede
alimentada adiante ( feed forward), onde o sinal é propagado da primeira camada até a última e
todos os neurônios de uma camada estão conectados a todos os neurônios da próxima camada é
chamada de rede totalmente conectada. Caso algum neurônio não esteja conectado a um outro
25
Figura 2.22: Hiperplano dividindo duas classes, (HAYKIN, 2001).
da camada seguinte, a rede é chamada de parcialmente conectada.
Além do aumento no número de camadas, foi definido que a função de ativação deve ser
contínua, não linear e diferenciável em qualquer ponto, para ser pos sível minimizar o erro. A
função deve ser não linear, pois uma rede onde as funções de ativação são lineares comportar-se
como um perceptron. A demonstração deste fato pode ser encontrada em um estudo de (BRAGA
et al., 2000). A função deve ser também diferenciável para que seja possível o cálculo do gradiente
e o ajuste dos pesos na direção correta. A função de ativação é responsável por determinar a
saída do neurônio com base nos valores da soma ponderada e do limiar. Uma função utilizada é a
logística, definida na equação 2.4.11, pois ela representa bem a fase refratária de neurônios reais,
ou seja, a fase que o axônio não pode ser novamente estimulado. Na equação 2.4.11, x é o valor
da soma ponderada mais o limiar e y é o valor de saída do neurônio (HAYKIN, 2001).
y =
1
1 + e
−x
(2.4.11)
As RNAs, que não eram capazes de resolver problemas não lineares, tornaram-se ferramentas
muito poderosas, capazes de implementar funções contínuas, quando usada uma camada escon-
dida, ou qualquer função, quando utilizadas duas camadas escondidas.
2.4.4 Aprendizado
É notável nas RNAs a sua capacidade de aprender e também de melhorar seu desempenho no
decorrer do tempo a partir de exemplos retirados do seu ambiente. Em (HAYKIN, 2001) apren-
dizagem é definida no contexto de redes neurais como: "Aprendizagem é um processo pelo qual os
parâmetros livres de uma rede neural são adaptados através de um processo de estimulação pelo
ambiente no qual a rede está inserida. O tipo de aprendizagem é determinado pela maneira pela
qual a modificação dos parâmetros ocorre."
A fase de aprendizado também é conhecida como fase de treino da RNA. Os parâmetros livres
que devem ser alterados são : os pesos dos neurônios e os limiares de ativação. Os dois principais
paradigmas de aprendizado são: o aprendizado supervisionado e o aprendizado não supervisionado.
No aprendizado supervisionado existe um professor que conhece o ambiente que a RNA deve
representar, como ilustra a Figura 2.24. A princípio a RNA não conhece este ambiente, então o
professor deverá avaliar os resultados obtidos pela RNA quando é apresentado algo deste ambiente
a ela. Como medida de desempenho é calculada a diferença do resultado esperado pelo resultado
obtido, que é chamado de erro, então este valor é usado para ajustar os parâmetros livres da rede
26
Figura 2.23: Perceptron multicamadas (HAYKIN, 2001).
de tal forma a minimizar o erro. O processo se repete até que o erro seja aceitável. Este processo
é conhecido como correção por erro.
O ajuste ótimo do erro é feito com a minimização da função 2.4.12 conhecida como Regra Delta
ou Regra de Widrow-Hoff, onde e representa o erro, k o neurônio que terá seu peso ajustado e n é
a medida de tempo discreta. A regra delta se relaciona com a regra de aprendizado do perceptron
e é generalizada no algoritmo back-propagation, que é discutido na Seção 2.4.5.
E(n) =
1
2
e
2
k
(n) (2.4.12)
Ao fim da fase de treino, a rede deve-se comportar como seu professo r. Entretanto, uma
desvantagem do aprendizado supervisionado é que perante um ambiente desconhecido a rede não
é capaz de lidar com ele sem um novo treinamento. Apesar do paradigma supervisionado ser
muito poderoso e consequentemente muito utilizado, ele não representa o modelo biológico, pois
não possui as estruturas necessárias para a correção de erros e nem os meios nervosos para aprender
com o mundo exterior.
A aprendizagem não-supervisionada é inspirada em modelos biológicos, como no modelo dos
primeiros estágios do sistema de visão e audição. Na aprendizagem não-supervisionada não existe
a presença de um professor que conheça a resposta certa para determinado estímulo, como mostra
a Figura 2.25. Somente os padrões de entrada são aprensentados e a RNA fica responsável por
relacionar a sua saída com a regularidade estatística da entrada de dados, ou seja, classificar
adequadamente os padrões de entrada. A redundância dos dados de entrada é importante para
que a rede possa estabelecer uma relação entre eles.
27
Figura 2.24: Aprendizado supervisionado, (HAYKIN, 2001).
Figura 2.25: Aprendizado não-supervisiona do, (BRAGA et. al., 2000).
2.4.5 Back-propagation
O algoritmo de aprendizado do perceptron não lida com redes com mais de uma camada. A
generalização da regra delta pelo algoritmo de treino back-propagation torna possível o treino de
redes com mais de uma camada (BRAGA et al., 2000).
O treino de uma rede perceptron multicamadas é executado em duas fases, uma chamada
forward e outra chamada backward. Na primeira fase, a saída da rede é calculada a partir de um
padrão a presentado a ela, em um primeiro momento a saída será aleatória pois a rede nã o tem
nenhum conhecimento. A segunda fase utiliza a saída calculada e a saída desejada para calcular
o erro e ajustar os pesos da última camada. O erro é então propagado para a penúltima camada
levando em conta os pesos de cada conexão. O processo se repete até a primeira camada.
Este procedimento é chamado de modo on-line do algoritmo back-propagation e se repete para
todos os exemplos que serão usados durante o treino da rede. Em oposição ao modo on-line está
o modo off-line, onde os pesos são ajustados após cada ciclo de treino, ou seja, após todos os
exemplos serem apresentados à rede.
Muito utilizado em grandes problemas e em classificação, o modo on-line é menos suscetível a
mínimos locais. É constatada a vantagem sobre o modo off-line quando os padrões de treino são
redundantes.
Uma RNA converge se o algoritmo encontra o ponto mínimo na sup erfície de erro. A coor-
denada de um ponto nessa superfície sã o os p e sos dos neurônios e a altura é o valor do erro. O
algoritmo deve p erco rrer essa sup e rfície procurando por vales onde es tá o mínimo global, evitando
os mínimos locais.
28
2.4.6 Uso de RNAs em Visão Computacional
O Reconhecimento de Padrões, um segmento da Visão Computacional, utiliza técnicas para extrair
informações de uma imagem ou classificar o seu conteúdo, com o intuito de obter uma interpretação
de alto-nível da imagem.
Como foi visto, o modelo de RNA perceptron é capaz de implementar f unções linearmente
separáveis que podem ser usadas para classificar imagens, pois o perceptron posiciona um hiper-
plano entre as classes como é feito em Reconhecimento de Padrões. O modelo de rede MLP pode
implementar qualquer função contínua e consequentemente é um ótimo classificador (BRAGA et
al., 2000, BEALE e JACKSON, 1992).
Uma rede neural com sua camada de entrada associada aos pixels de uma imagem é adequada
para extrair os atributos da imagem e a classificar de acordo com o treino ao qual a RNA foi
submetida. A RNA tem o conhecimento de quais caracteríssticas levar em conta na classificação
armazenado em sua estrutura.
Outra abordagem, seria extrair as características relevantes da imagem de forma convencional
e armazená-las em um vetor de atributos, que será usado como entrada pa ra a rede neural. Com
base neste vetor a rede neural o classificará da mesma forma que uma função de discriminação ou
medida de distância. Então, a rede neural terá implementado apenas o classificador.
2.5 Navegação Basead a em Marcos
Marcos são características distintivas do ambiente que o robô consegue reconhecer a partir de
informações sensoriais. Devem ser de fácil identificação e possuir uma posição fixa e conhecida no
ambiente, a qual é utilizada para localização do robô.
Antes, entretando, de utilizá-los para localização, os mesmos devem ser armazenados na
memória do robô. Assim, a tarefa de localização consiste na identificação do marco atual e sua
correspondência com um dos marcos armazenados em sua memória, calculando assim sua posição.
A Figura 2.26 ilustra tal procedimento.
Figura 2.26: Proce dimento geral de localização baseada em marcos.
Existem na literatura pesquisas envolvendo dois tipos de marcos: naturais e artificiais. De
acordo com Boreinstein, Everett e Feng (1996), marcos naturais são aplicados com mais frequência
e sucesso em ambientes altamente estruturados, como é o caso das edificações construídas por seres
humanos. Com base nisso, ele define marcos artificiais e naturais como segue: marcos naturais são
características ou objetos que já estão presentes no ambiente e são utilizados para propósito de
navegação do robô; marcos artificiais são objetos especialmente projetados e inseridos no ambiente
para servirem como ponto de referência durante a navegação do robô.
Nas seções a seguir descrevemos ambas as abordagens, citando exemplos de trabalhos desen-
volvidos nestas áreas.
29
2.5.1 Marcos Artificiais
Detectar um marco artificial é uma tarefa mais facilmente implementada se comparada com a
mesma tarefa no contexto de marcos naturais (ATIYA e HAGER, 1993). Isso porque marcos arti-
ficiais são especialmente projetados para atingir um contraste ótimo, além de terem seu tamanho
e forma conhecidos a priori. Tais informações são utilizadas para produzir informações de caráter
geométrico, as quais podem ser utilizadas pelo método de reconhecimento de marcos.
Muitos sistemas de localizaçã o baseados em marcos artificiais usam recursos da visão com-
putacional. Baczyk, Kasi’nski e Skrzypczy’nski (2003) apresentam em seu trabalho um sistema
de localização para robôs móveis em ambientes parcialmente conhecidos. O sistema utiliza marcos
artificiais codificados de maneira única e não ambígua, os quais possuem sua localização conhecida
no ambiente de navegação do robô. A maneira pela qual os marcos são unicamente codificados
permite sua identificação a partir das imagens e posterior localização global do robô.
O projeto de marcos artificiais deve levar em consideração mudanças no ponto de vista da
câmera, o que resulta em possíveis distorções dos marcos, as chamadas transformações afim.
Flusser e Suk (1993) definiram um conjunto de seis equações invariantes de momento afim, as
quais aplicadas sobre um padrão resulta numa característica robusta a tais transformações. Em
trabalho posterior com Zitovà (ZITOVA e FLUSSER, 1999), os autores desenvolveram um projeto
de marcos artificiais circulares para aplicação dos invariantes de momento afim, resultando num
método de reconhecimento de marcos artificiais para navegação de robôs móveis.
Scharstein e Briggs (2000) definiram um projeto para construção de marcos artificiais formados
por variação de padrões de intensidade e seu respectivo algoritmo de detecção robusto a transfor-
mações afim. O método faz uso da definição e teoria de funções periódicas para construção dos
marcos, resultando em um algoritmo de aplicação direta e adequado para aplicações de tempo-real.
2.5.2 Marcos Naturais
O principal problema a ser resolvido em sistemas de navegação baseado em marcos naturais é
detectar as características dos candidatos a marcos e fazer sua correspondência com os dados do
mapa, a partir de informações sensoriais. O sistema sensorial que atualmente têm sido usado para
tal tarefa é a visão computacional.
A seleção dos elemento s é importante já que isso determina a complexidade da descrição,
detecção e correspondência das características, ao mesmo temp o que reduz problemas com am-
biguidades e aumenta a precisão da localizaç ão .
Boreinstein, Everett e Feng (1 99 6) definiram os seguintes componentes básicos para um sistema
de localização baseado em marcos naturais:
• Um sensor para detectar e segmentar os marcos
• Um método para estabelecer a relação entre as características observadas e os marcos ar-
mazenados no mapa
• Um método que calcula a loca lizaçã o dos robôs e os erros relacionados ao cálculo.
Va sudevan et. al. (2007) em seu trabalho descreve um sistema de mapeamento bas eado
na extração de portas e objetos típicos de um ambiente estruturado. O objetivo é criar uma
representação topológica global do ambiente seguindo a abordagem de representação hierárquica
do espaço proposta por Kuipers (2000). Além disso, os autores usam o método proposto por Lowe
(1999), Scale Invariant Features Transform - SIFT - com o objetivo de extrair as características
do ambiente a partir de imagens coletadas por uma câmera estéreo.
30
A transformada SIFT (LOWE, 1999) tem sido amplamente utilizada no contexto de navegação
de robôs baseada em marcos. Suas principais características são: invariância total a mudança de
escala, translação, rotação e parcial a mudanças de iluminação e transformações afim. Isto significa
que as ca racterísticas extraídas pela SIFT possuem estas propriedades, o que justifica sua ampla
utilização nesta área. Em um de seus trabalhos em conjunto com Se, Lowe e Little (2001), os
autores propõem uma solução para o SLAMB baseada em visão computacional, a qual usa as
características em escala invariante como marcos naturais em ambientes não modificados. De
acordo com os resultados obtidos, os autores afirmam que a invariância de tais caracterísitcas a
translação, mudança de escala e rotação torna os marcos adequados para a aplicação proposta.
Wa hlgren e Duckett (2005) propuseram um algoritmo probabilístico de mapeamento topológico
usando visão omnidirecional. O método utiliza características locais extraídas a partir de ima-
gens panorâmicas em conjunto com técnicas de segmentação, com o objetivo de criar marcos
naturais para descrever cada nó do mapa. Os autores utilizam uma versão modificada da SIFT,
a MSIFT (ANDREASSON e DUCKETT, 2004), para extrair as características das imagens, as
quais definem os marcos.
Ta mimi et. al. (2006) propuseram uma nova abordagem para a implementaçao da SIFT, a
SIFT iterativa (Iterative SIFT). Tal modificação reduz o número de características geradas pela
SIFT b em como o tempo de extração e casamento das mesmas. Além disso, o método faz uso do
método de localização de Monte Carlo para demonstrar que o robô ainda consegue se autolocalizar
usando um número reduzido de características.
31
Capítulo 3
Sistema de Mapeamento do Robô Móvel do
LACE
Como já citado, um procedimento de localização para robôs móveis pode utilizar uma mapa já
existente ou o robô deve construir seu próprio mapa . Rencken (1993 ) definiu o problema de
construção de mapas como segue: dada a posição atual do robô e um conjunto de medidas, o que
os sensores estão percebendo? De tal definição pode-se concluir que a habilidade do robô construir
um mapa está intimamente relacionada à sua capacidade de perceber o ambiente. Além disso,
pode-se dizer que a autonomia do robô também é influenciada por este fato r. Dessa maneira, o
tipo de sensoreamento utilizado afeta diretamente as estratégias desenvolvidas.
Técnicas de sucesso têm utilizado fusão de sensores, o que permite que diferentes informações
oriundas de diferentes origens seja m utilizadas para modelagem. Um outro recurso que pode ser
utilizado para se melhorar o desempelho de tal tarefa é aumentar a quantidade de informações
percebidas, usando para isso imagens coletadas sobre o ambiente explorado. Tais técnicas usam es-
tas imagens para extrair características do ambiente, as quais podem ser utilizadas para propósitos
de mapeamento e localização.
Dentro desse contexto, neste capítulo são definidas a estrutura do sistema de mapeamento
do robô móvel do LACE, bem como as técnicas utilizadas para seu desenvolvimento. Antes,
entretanto, será apresentado o sistema sensorial do robô utilizado como fonte de informações
externas para o sistema.
3.1 Sistema Sensorial do Robô Móvel do Lace
O sistema sensorial do robô móvel do LACE é formado por quatro sensores de ultra-som, sensores
de infra-vermelho e um sistema de visão omnidirecional. Existe um sonar em cada lado do chassi
do robô, os quais são utilizados para medirem distâncias do robô em relação a objetos. Os sensores
de infra-vermelho são utilizados apenas em situações emergenciais, como por exemplo um objeto
que se aproxime inesperadamente e neste caso o robô tenha que parar. Já o sistema de visão
omnidirecional do robô, formado por uma câmera e um espelho cônico, tem a função de coletar
imagens de 360
o
da vizinhança do robô. A Figura 3.1 ilustra a maneira como os sensores estão
dispostos na estrutura física do chassi do robô. Nas próximas seções são descritas a estrutura e o
procedimento de leitura das distâncias e coleta das imagens.
3.1.1 Sensores de Ultra-Som
O robô é dotado de quatro sonares, cada um deles localizados em um dos quatro lados do chassi
do robô, como ilustrado na Figura 3.1. Os sonares localizados nas laterais direita e esquerda se
32
Figura 3.1: Disposição Física dos Sensores no Chassi do Robô.
Figura 3.2: Procedimento de leitura amgular dos sonares laterais do robô.
movem na horizontal enquanto realizam a leitura das distâncias. O resultado desse processo é
a criação de um vetor de números reais, onde cada número representa a distância do robô com
relação a algum obstáculo, calculada de acordo com o ângulo formado entre a respectiva posição
de leitura e a posição central do sensor. Esse procedimento está ilustrado na Figura 3.2.
O sensor dianteiro se move tanto na horizontal quanto na vertical enquanto realiza as leituras.
Isso gera uma matriz de leitura, formada por números reais que correspondem as distâncias medi-
das nas respectivas posições de leitura do sonar. Isto é necessário para garantir que o espaço livre
a frente do robô seja "alto" o suficiente para permitir sua passagem.
O conjunto total de medidas, ou seja , os dois vetores e a matriz de leitura são fornecidos como
dados de entrada a um do s módulos do sistema de mapeamento do robô, como é descrito na Seçã o
3.2.1.
3.1.2 Sistema de Visão Omnidirecional
Nesta seção é apresentado o sistema de visão omnidirecional embarcado no robô móvel do LACE
utilizado para captura de cenas do ambiente explorado. O hardware do sistema é composto
por uma câmera com foco alinhado a um espelho cônico. Este reflete uma imagem de 360
o
da
vizinhança do robô, a qual é capturada pela câmera. Esta imagem omnidirecional contêm uma
quantidade maior de informações se comparada com uma imagem tradicional. Tal propriedade é
aproveitada para propósitos de extração de características do ambiente nas tarefas de mapeamento
33
Figura 3.3: Sistema de Visão Omnidirecional do Robô Móvel do LACE, (CAVANI 2004).
e localização. A Figura 3.3 ilustra o procedimento de captura e pré-processamento da imagem
omnidirecional.
O software de captura e pré-processamento das imagens omnidirecional foi desenvolvido por
(CAVANI, 2004), o qual é divido em módulos. Os três primeiros módulos deste sistema foram
utilizados neste projeto. O primeiro é o módulo de captura, responsável por comunicar-se com
a câmera; o segundo é o de visão omnidirecional, que transforma a imagem omnidirecional em
imagem panorâmica; o terceiro é o de pré-processamento, responsável pela detecção de bordas
e binarização da imagem. Os demais módulos, foram desenvolvidos neste trabalho, os quais
consistem no módulo gerador de padrões e no módulo de mapeamento, onde é implementado
o sistema de mapeamento proposto. Cada módulo passa os dados processados para o módulo
seguinte. A Figura 3.4 mostra como os módulos estão integrados.
Os três primeiros módulos fazem parte de um módulo maior, o gerador de padrões, o qual
disponibiliza uma interface gráfica para coleta e vizualização das imagens por parte do usuário.
A Figura 3.5 ilustra esta interface.
Uma vez capturada a imagem, esta é imediatamente submetida ao processo de retificação no
módulo de visão omnidirecional, e em seguida a imagem panorâmica resultante é pré-processada.
Os procedimentos adotados em ambo s os processos serão descritos ainda nesta seção.
Módulo de visão omnidirecional
O módulo de captura disponibiliza ao módulo de visão omnidirecional uma imagem retangular
com um círculo onde, a partir do centro é possível ver o ambiente ao redor do espelho, co mo
mostra a Figura 2.19. A imagem panorâmica é criada traçando-se círculos concêntricos dentro do
círculo definido pelo espelho. Cada círculo representa uma linha da imagem panorâmica.
O cálculo para a obtenção do pixel correspondente da imagem panorâmica na imagem omni-
direcional é feito usando coordenadas polares, segundo as equações 2.3.7 e 2.3.8, onde x e y são
34
Figura 3.4: Interação entre os módulos do sistema de visão omnidirecional (CAVANI, 2004).
coordenadas da imagem panorâmica, x
m
e y
m
são as dimensões da imagem panorâmica, r
m
raio
do espelho na imagem omnidirecional, θ ângulo em radianos do pixel desejado e h é a distância
do centro a um ponto na imagem omnidirecional. A dimensão adotada para x, y, x
m
, y
m
, r
m
e h
é o pixel (SPACEK, 2003).
Na Figura 3.6 o círculo representa a imagem do esp elho cônico. As coordenadas (x, y) podem
ser obtidas quando os valores de θ e h variam de forma a percorrer toda a superfície determinada
pelo círculo.
A partir das equações 2.3.7 e 2.3.8 obtemos as equações 3.1.1 e 3.1.2, com x
i
e y
i
sendo as
coordenadas na imagem omnidirecional, x
c
e y
c
as coordenadas do centro do espelho na imagem
omnidirecional, rm o raio da imagem do espelho, x
m
e y
m
a dimensão da imagem panorâmica e x
e y as coordenadas da imagem panorâmica.
x
i
= x
c
+
r
m
y
y
m
cos(
2πx
x
m
) (3.1.1)
y
i
= y
c
+
r
m
y
y
m
sin(
2πx
x
m
) (3.1.2)
O processamento executado por esse módulo resulta em uma imagem panorâmica como a da
Figura 2.20. A imagem não apresenta nitidez pois a resolução da câmera não é suficiente para
35
Figura 3.5: Interface utilizada para captura de imagens omnidirecional.
Figura 3.6: Coo rdenadas polares - utilizada para retificação da imagem omni.
uma imagem panorâmica com esse tamanho. Entretanto, é suficiente para a aplicação, como visto
adiante. A faixa preta na parte inferior da imagem corresponde ao centro do espelho, a qual é
desprezada nesta aplicação.
Módulo de pré-processamento
No módulo de pré-processamento a imagem é preparada para a sua utilização pelo sistema de ma-
peamento proposto. Aqui, elas são submetidas a um processo de detecção de bordas e binarização.
1. Detecção de bordas
Algoritmos de detecção de bordas identificam descontinuidades na imagem que caracterizam
uma borda. Com o objetivo de apresentar uma imagem simplificada à rede neural, a detecção
de bordas gera uma imagem onde a forma dos o bjetos pode ser visualizada sem a interferência
de outras características.
A detecção de bordas é feita nesse módulo através do cálculo do operador de Sobel. O
que é borda será decidido pela determinação de um limiar onde os valores acima serão
considerados bordas (FAIRHURST, 1988). O limite é determinado pela média dos valores
calculados pelo operador de Sobel quando aplicado em todos os pixels da imagem menos
as primeiras e últimas linhas e colunas, pois utiliza uma ja nela de 3X3 pixels. A média foi
adotada como limite, pois a aplicação se comportou adequadamente com bordas extraídas
segundo este limite. Os valores dos pixels p ertencentes a uma borda são normalizados para
36
seu valor máximo ser 255. A normalização é feita dividindo o valor do operador de Sobel
para o pixel pelo maior valor encontrado e multiplicando este resultado por 255.
O operador de Sobel evita ruídos quando comparado com o operador de Robert, ou seja, a
detecção de bordas que não são realmente bordas (FAIRHURST, 1988). Devido ao uso de
uma janela pequena o operador de Sobel possibilita maior velocidade no processamento da
imagem em comparação com operadores que utilizam uma janela maior.
2. Binarização
Binarização é entendida como o processo de transformar uma imagem em tons de cinza em
uma imagem composta somente por pixels pretos ou brancos (FAIRHURST, 1988). Para
isso, um tom de cinza limite é escolhido e todos os valores acima dele serão considerados
branco e, abaixo, serão considerados preto. Para determinar um limite adequado, evitando
assim que os objetos na imagem fiquem deformados quando ocorre alguma variação de luz
no ambiente, foi adotado o cálculo do tom de cinza médio a cada nova imagem, que é então
usado como limite.
A Figura 3.8 mostra uma imagem do laboratório LACE (Laboratório de Automação e Com-
putação Evolutiva) onde a detecção de bordas e a binarização foi feita e a Figura 3 .7 é a
imagem panorâmica original. Estas duas figuras foram capturadas com dimensões maiores
para que fosse po ssível visualizar o ambiente adequadamente e comprovar que os algoritmos
fucionam corretamente.
Figura 3.7: Imagem panorâmica gerada pelo módulo de visão omnidirecional.
Figura 3.8: Imagem panorâmica resultante do pré-processamento pelo módulo de visão.
3.2 Estrutura do Sistema de Ma peamento
O sistema de mapeamento proposto para o robô móvel do LACE tem como objetivo construir
mapas topológicos de ambientes interiores estruturados, enquanto estes são explorados pelo robô.
Para executar tal tarefa o robô precisa ter a capacidade de interagir com seu ambiente, coletando
informações sobre o mesmo enquanto se locomove de um lugar a outro. Para isso, o robô usa seu
sistema sensorial descrito nas seções anteriores.
Como descrito na Seção 2.1 .3, as informações necessárias para a construção de um mapa
topológico dizem respeito apenas aos espaços livres por onde o robô pode se movimentar e às
relações de adjacência entre esses lugares. Tendo isso em mente, o objetivo do sistema propo sto
37
é mapear os espaç os livres do ambiente por onde o robô possa se movimentar ou mudar a direção
de seu percurso, bem como a relação de adjacência entre esses lugares.
O sistema de mapeamento é composto por três módulos: classificador, identificador/criador e
caracterizador de nós. A Figura 3.9 ilustra a estrutura funcional do sistema e as relações entre os
módulos
Figura 3.9: Esquema Funcional do Sistema de Mapeamento.
A função do módulo classificador é identificar cada lugar explorado pelo robô, classificando-os
dentre quatro classes pré-definidas: corredor, porta, intersecção e sala; e assim passar a informação
da respectiva classe ao módulo identificador/criador, o qual efetivamente cria um novo nó e o insere
dentro do mapa. Este módulo, contudo, necessita de outras informações processadas pelo módulo
caracterizador antes de armazenar a informação de um novo nó criado.
A tarefa de classificação é implementada através de uma rede neural artificial (RNAH) estru-
turada hierarquicamente em duas camadas: razão e intuição . A estrutura da RNAH bem como
o procedimento de classificaçã o adota do serão descrito na Seção 3.2.1.
Além de identificar e classificar os nós, é necessário caracterizá-los de modo a torná-los distintos
dos demais nós pertencentes a mesma classe. Isto é necessário pois cada nó do mapa precisa
ser identificado de maneira única a fim de permitir que o robô se localize precisamente em seu
ambiente. Esta tarefa é feita utilizando técnicas de navegação baseada em marcos.
Marcos podem ser definidos como objetos de uma cena que são encontrados de uma maneira
distintiva pelo robô, ou seja, objetos da cena que são selecionados pelo robô como um ponto
de referência de um local, identificando o mesmo. Em outras abordagens, marcos podem ser
definidos como atributos extraídos a partir de um conjunto de imagens das cenas e não apenas
por algum objeto da mesma. Neste trabalho são abordadas técnicas de extração de atributos
e reconhecimento de padrões invariantes com o objetivo de utilizá-las na definição dos marcos.
Desse modo, o módulo caracterizador de nós consiste num sistema de seleção e reconhecimento
de marcos visuais, o qual pode ser utilizado tanto para propóstios de mapeamento quanto para
localização do robô. As técnicas utilizadas para implemetar tal sistema, bem como o procedimento
adotado serão descritos nas próximas seções.
38
3.2.1 Módulo Classificador
A função do módulo classificador é classificar os lugares explorados pelo robô dentre quatro classes
pré-definidas: corredor, porta, intersecção e sala; e assim passar esta informação ao módulo cria-
dor, o qual efetivamente cria e insere um novo nó no mapa topológico. O objetivo de se seccionar
o ambiente em classes é permitir que o processo de decisão de navegação do robô seja facilitado
e baseado apenas nos parâmetros definidos para a classe atualmente ocupada por ele. Dessa
maneira, as decisões de navegação do robô podem ser definidas como uma máquina de estados,
onde cada estado (classe) está associado a um conjunto de possíveis ações. A Figura 3.10 ilustra
este procedimento.
Figura 3.10: Diagrama em máquina de estados das decisões de navegação do robô.
Analisando a Figura 3.10 pode-se constatar que uma vez que o mapa esteja disponível, basta
ao robô identificar a classe do local ocupado atualmente para então decidir quais decisões tomar.
Nesse caso, tendo um plano de percurso em mãos o robô pode então escolher o próximo nó do
mapa a ser ocupado a fim de alcançar seu objetivo. Dessa maneira, o sistema de classificação de
lugares pode então ser usado tanto para propósitos de mapeamento quanto para localização do
robô durante sua navegação.
Para implementar a tarefa de classificação foi utilizada uma Rede Neural Artificial Hierárquica
(RNAH) treinada para reconhecer as classes de luga res definidas. A estrutura da RNAH bem
como seu procedimento de classificaçã o são descritos na Seção 4.2.
Rede Neural Hierárquica - RNAH
Nesta seção nós descrevemos a estrutura da rede neural hierárquica utilizada para tarefas de
classificação dos lugares explorados pelo robô. A RNAH é formada por duas camadas, razão e
intuição, como ilustrado na Figura 3.11.
A rede recebe como entrada os dados lidos pelo sistema sensorial do robô: medidas de distância
e imagens do ambiente fornecidas pelos sonares e sistema de visão o mnidirecional, respectivamente.
39
Figura 3.11: Estrutura da Rede Neural Hierárquica - RNAH.
A rede razão receb e os dados lidos pelos sonares e com base neles é capaz de identificar a classe
corredor, quando o robô navega através deste, e a classe interseção, quando detecta o encontro
de dois ou mais corredores de modo que o robô possa eventualmente mudar a direção do seu
percurso. As informações de distância são suficientes para identificar as referidas classes sob
condições descritas. Quando os sonares do robô detectam a existência de uma a bertura lateral,
esta pode consistir de uma porta ou um corredor. Neste caso as informações de distância não
são suficientes para identificar a classe correta. É neste momento que a rede intuição é ativada,
utilizando como dados de entrada imagens do local a ser classificado.
Na situação descrita anteriormente um dos neurônios da saída da rede razão é ativado, o
qual consiste no neurônio excitador da rede intuição. Esta executa então seu procedimento de
classificação utilizando imagens do local com o objetivo de identificar a classe correta: porta ou
corredor. Para isso, a segunda camada da RNAH é treinada com imagens destas duas classes de
lugares para adquirir a capacidade de distingui-las.
O fato descrito no parágrafo anterior é o que justifica a criação de um rede neural hierárquica
para propósitos de classificação. O s testes envolvendo a RNAH são descritos no Capítulo 4.
Treinamento da RNAH - Classificação dos lugares
Para identificar as classes definidas, ambas as camadas da RNAH precisam ser treinadas para
adquirir tal capacidade. Foram definidos então parâmetros para cada classe, os quais as caracte-
rizam tornando-as diferentes das demais. Tais parâmetros são levados em consideração durante a
construção do conjunto de padrões de treinamento.
O conjunto de treinamento fornecido à camada razão da RNAH permite que a mesma classifique
com certo grau de certeza as classes cujos parâmetros que as caracterizam são bem definidos e
modelados com base nas distâncias lidas pelos sonares. As classes onde isso não acontece são
caracterizadas por suas imagens, e é respo nsabilidade da segunda rede identificá-las, a qual é
40
Figura 3.12: Estrutura da Rede Razão.
ativada sempre que houver qualquer dúvida no processo de reconhecimento da primeira camada.
Por exemplo, um corredor é definido como um luga r limitado continuamente por obstáculos em
ambos os lados do robô. Uma intersecção é um local onde dois ou mais corredores se interceptam,
de mo do que o robô possa eventualmente alterar a direção do seu percurso. Essas duas classes
são então modeladas levando-se em consideração tais características e as informações disponíveis
para a construção dos modelos: leitura das distâncias dos so nares. No caso da rede intuição, o
conjunto de treinamento é formado p or diferentes imagens de portas e corredores, com o objetivo
de capacitar a rede a distingui-las quando estes forem encontrados durante a etapa de mapeamento.
A arquitetura de rede neural adotada é a Perceptron Multi-Camadas, que são redes ade-
quadas para a tarefa de classificação . Determinar o número de camadas ocultas e a quantidade
de neurônios em cada uma delas é uma importante decisão de projeto que deve ser determinada
empiricamente durante a fase de testes, levando-se em consideração os resultados obtidos.
O número de neurônios da camada de entrada da rede razão deve ser igual ao número total
de leituras realizadas pelos três sonares: direito, esquerdo e dianteiro; seguindo o procedimento
descrito na Seção 3.1.1. Nes te caso, o número de leituras pode ser modificado, adequando-o as
necessidades do sistema de modo a torná-lo tanto confiável quanto eficiente. Sua camada de saída
é composta por quatro neurônios: os três primeiros correspondem às classes sala, intersecção e
corredor, enquanto o último consiste no neurônio excitador da rede intuição, como ilustrado na
Figura 3.12.
Como já citado, a rede intuição recebe como entrada imagens dos locais a serem classificados.
Dessa maneira, o número de neurônios de sua camada de entrada é igual a resolução das imagens,
ou seja, o número total de pixels utilizados para representar as imagens, como ilustrado na Figura
3.13. Este número deve ser "grande"o suficiente para permitir uma classificação e reconhecimento
confiável, e "pequeno" o suficiente para garantir eficiência durante as fases de treinamento e va-
lidação da rede, etapas estas que demandam o maior tempo de execução. Entretanto, um peso
maior deve ser dado as primeiras tarefas em detrimento das segundas, já que estas são executadas
apenas na fase de construção do sistema.
41
Figura 3.13: Estrutura da Rede Intuição.
3.2.2 Módulo Caracterizador
Neste seção apresenta-se a proposta para a implementação do sistema de seleção e reconhecimento
de marcos visuais - módulo caracterizador - criado tanto para tarefas de mapeamento de ambi-
entes quanto para localização do robô móvel do LACE. A função deste módulo é descrever os
nós identificados pelo módulo classificador, a fim de torná-los únicos e distintos dos demais nós
pertencentes à mesma classe. O objetivo é criar marcos naturais para os nós a partir de cenas de
um conjunto de imagens, as quais são usadas como marcos visuais ou a partir delas extraem-se um
conjunto de atributos que as caracterizam, o que difere da abordagem onde marcos são definidos
como objetos individuais da cena.
A proposta consiste em utilizar Transformada SIFT (LOWE, 1999), definida na Seção 2.3.1 ,
como ferramenta para se extrair características locais invariantes a partir das imagens coletadas
pelo sistema de visão do robô, utilizando tais características como marcos visuais definidos em
cada nó do mapa.
O objetivo é aproveitar a propriedade de invariância de tais características para criar marcos
visuais que sejam robustos a transformações sofridas pelas imagens, as quais são inerentes ao
processo de coleta. Dessa maneira, a proposta para o módulo caracterizador consiste em criar um
classificador para tais marcos, o qual consiga distinguir os diferentes nós do mapa com base nestas
informações.
Os testes envolvendo este módulo são apresentados no Capítulo 4.
42
Capítulo 4
Resultados Experimentais
Neste Capítulo são apresentados os resultados obtidos durante a fase de testes dos procedimentos
de seleção e reconhecimento de ma rcos do módulo caracterizador e de ambas as camadas da RNAH:
razão e intuição.
4.1 Módulo Classificador
Para criar as duas sub-redes, bem como a RNA do classificador de marcos, foi utilizado o simulador
de redes neurais SNNS (Stuttgart Neural Network Simulator) (ZELL et. al., 2000), o qual fornece
também suporte para etapas de treinamento, validação e teste.
A rede razão criada é uma perceptron de camada única com 35 neurônios em sua camada de
entrada, cada um dos quais recebe uma das posições do vetor e matriz de leitura dos sonares.
A saída desta camada tem quatro neurônios, os três primeiros relativos às classes intersecção,
sala e corredor, e o último é o neurônio excitador da segunda rede. A rede intuição foi testada
usando-se perceptrons de camada única e multicamadas. Os resultados obtidos no primeiro ca so
foram insatisfa tórios, apresentando uma baixa taxa de acertos na classificação. Este problema foi
resolvido com o uso de uma perceptron multicamadas, cujos resultados serão apresentados ainda
nesta seção.
A camada de entrada da rede intuição tem 300 neurônios, cada um dos quais recebe o valor
armazenado em um dos pixels da imagem de 50 X 6 de resolução. Sua camada de saída tem dois
neurônios relativos às classes corredor e porta.
Ambas as redes foram submetidas a diferentes fases de treinamento, de modo que em cada
fase um conjunto diferente de padrões eram utilizados. Após a fase de treino, elas foram sub-
metidas a uma fase de testes com o objetivo de se avaliar a fase anterior com base nos resultados
obtidos na classificação de padrões conhecidos e desconhecidos das redes. No primeiro grupo de
padrões encontra-se o conjunto de situações apresentadas à rede durante seu treinamento, vistas,
contudo, sob diferentes pontos-de vista do robô. Este teste tem por objetivo verificar a robustez
da classificação diante de transformações sofridas por estes padrões. O segundo grupo é formado
por situações nunca antes percebidas pelo robô, as quais testam a capacidade de generalização da
rede neural.
Na primeira etapa de testes, a rede razão foi treinada utilizando-se um conjunto formado por 95
padrões, o qual foi construído com o objetivo de capacitá-la para o reconhecimento de corredores
e intersecções, sendo estas classes modeladas com base na s leituras dos sonares. Já o conjunto
de treinamento da camada intuição tinha 65 imagens de portas e corredores. Durante os testes
foram apresentados 24 e 50 padrões à camada razão e intuição, respectivamente.
A Tabela 4.1 exemplifica alguns resultados obtidos durante a primeira fase de testes. Ela faz
43
referência a um local rotulado como Porta 1 - P1, o qual é mostrado sob três condições diferentes:
visão 1, visão 2 e visão 1 com baixa iluminação. Padrões deste local já haviam sido fornecidos à
RNAH-intuição durante seu treinamento. A Figura 4.1 mostra exemplos de imagens panorâmicas
de P1 fornecidas como padrão de entrada à rede intuição durante a fase de testes. A diferença
das situações é visível, o que também pode ser notado comparando-se as Figuras 4.2 a), b) e c).
O neurônio ativado é a quele que possuir o maior valor de ativação (va), e quanto mais próximo
do valor ótimo (1), mais precisa é a classificação. A rede intuição em todos os casos classificou
P1 corretamente e com um valor de ativação muito próximo do valor ótimo, 0.998, 0.995 e 0.992,
respectivamente.
Ta bela 4.1: Exemplos de locais classificados pela RNAH durante a etapa de testes
ID do local Descrição do local Imagem real Imagem Panorâmica
Porta 1 (P1) Conhecido, visão 1 Figura 4.2.a Figura 4.1.a
Porta 1 (P1) Conhecido, visão 2 Figura 4.2.b Figura 4.1.b
Porta 1 (P1) Conhecido, visão 1, baixa iluminação Figura 4.2.c Figura 4.1.c
Corredor 1 (C1) Desconhecido, visão 1 Figura 4.4.a Figura 4.3.a
Corredor 1 (C1) Desconhecido, visão 2 Figura 4.4.b Figura 4.3.b
Corredor 1 (C1) Desconhecido, visão 3 Figura 4.4.c Figura 4.3.c
Corredor 2 (C2) Desconhecida, visão 1 Figura 4.5.a -
Corredor 2 (C2) Desconhecida, visão 2 Figura 4.5.b -
Corredor 2 (C2) Desconhecida, visão 2, alta iluminação Figura 4.5.c -
Figura 4.1: Imagens Binárias Panorâmicas da Porta 1: a) Visão1; b) Visão 2; c) Visão 1 com
baixa iluminação.
Figura 4.2: Imagem Real da Porta 1 (P1)- a) Visão 1 b) Visão 2 c) Visão 1 com baixa iluminação.
44
O mesmo proces so de análise pode ser aplicado ao local Corredor 1 (C1), com três exemplos de
classificação referenciados na Tabela 4.1. O local C1 é desconhecido da RNAH - intuição e nesta
primeira etapa de testes foi classificado corretamente em todas as situações que o descrevem.
Figura 4.3: Imagens Binárias Panorâmicas do Corredor 1: a) Visão1; b) Visão 2; c) Visão 3.
Figura 4.4: Imagens Reais do Corredor 1 - C1: a) Visão 1, b) Visão 2, c) Visão 3.
O contrário acontece com o local Corredor 2 - C2. A cla ssificaçã o de C2, também desconhecido,
não obteve 100% de acertos. A Figura 4.5 ilustra, respectivamente, as duas situações classificadas
corretamente e uma incorretamente. Uma possível justificativa para o erro seria a diferença na
taxa de iluminação causada pela entrada de luz através de uma porta aberta no lado direito da
imagem.
A Tabela 4.2 descreve o resultado geral da classificação da RNAH-razão e RNAH-intuição
para os 24 e 50 padrões, respectivamente, testados durante a primeira fase de testes. Todos os
24 padrões testados pela rede razão consistem em situações familiares à rede, ou seja, corredores
e intersecções modelados segundo o mesmo padrão dos locais utilizados na fase de treinamento.
A diferença, entretanto, reside nas medidas de distância do robô em relação aos obstáculos, as
quais eram diferentes das utilizadas na fase anterior. À rede intuição foram apresentados 22
padrões desconhecidos e 28 imag ens de portas e corredores conhecidas da rede, vistas, contudo,
sob diferentes pontos-de-vista ou sob diferentes condições de iluminação. A coluna 2 desta tabela
indica a taxa geral de acertos. A coluna 3 mostra a taxa de acertos no processo de classificação
dos padrões desconhecidos. Já a última coluna, válida somente para a rede intuição, indica
a porcentagem de acertos na classificação daqueles padrões conhecidos da rede e que sofreram
algum tipo de modificação.
A Tabela 4.3 resume os resultados obtidos pela rede intuição no processo de classificação das
classes porta e corredor. Analisando-se esta tabela, verifica-se que a rede alcançou uma taxa de
acertos superior a 90 porcento. Além disso, somente 7% dos padrões corretamente classificados
obtiveram um baixo valor de ativação, os quais estão dentro do intervalo [0.65, 0.75], o que pode
ser considerado aceitável.
45
Figura 4.5: Imagem Real do Corredor 2 (C2) - a) Visão 1: classificada corretamente com va =
0.994; b) Visão 2: classificada corretamente com va=0.993; c) Visão 3: classificada incorretamente.
Ta bela 4.2: Porcentagem Geral da Classificação Correta das Camadas Razão e Intuição
Camada Classificação Geral Padrões Desconhecidos Padrões Alterados
Razão 100% - 100%
Intuição 94% 96 % 93%
Na segunda fase de testes, acrescentou-se ao conjunto de padrões da RNAH-razão, intersecções
modeladas seguindo um padrão diferente do utilizado na fase anterior. Tal diferença está na
modelagem de aberturas localizadas nas laterais do robô. Durante o treinamento forneceu-se à
rede padrões de aberturas estreitas com espaço livre à frente do robô, ou sej a, as leituras dos
sonares realizadas nos ângulos mais extremos detectavam algum obstáculo, ao mesmo tempo que
o sonar dianteiro não detectava qualquer obstáculo. Dessa forma, o segundo conjunto de testes
incluiu não apena s padrões que seguem este modelo, mas também padrões de aberturas laterais
mais largas, o pode resultar na não detecção de qualquer obstáculo pelo sonar lateral, bem como
instersecções com obstáculos localizados diante do robô, impedindo sua passagem.
Já no segundo conjunto de testes da RNAH-intuição incluiu-se 43 situações completamente
desconhecidas da rede. O objetivo é testar a capacidade de generalização da rede já treinada,
tendo em vista os bons resultados obtidos nos primeiros testes. As Tabelas 4.4 e 4.5 resumem os
resultados obtidos por ambas as camada s nesta etapa.
Uma terceira etapa de testes foi realizada com o objetivo de melhorar o desemp e nho obtido
na segunda etapa. Nesta fase busca-se um equilibrio entre a taxa de classificação geral e a taxa
de g eneralizaçã o da rede intuição, ou seja, atingir a melhor taxa de classificação, mantendo uma
boa taxa de generalização.
De acordo com a Tab ela 4.6, o desempenho geral da RNAH-razão manteve-se em 100% na
segunda etapa de testes, quando 30% dos padrõ es testados eram desconhecidos da rede. Já o
desempenho da RNAH-intuição caiu de 94% para 82% na segunda etapa quando a quantidade
testada de padrões desconhecidos aumentou de 44% para 77%, alcançando uma taxa de genera-
lização de 77%. Baseando-se nestes dados, a terceira fase de testes consistiu em acrescentar ao
conjunto de treinamento da RNAH-intuição alguns padrões desconhecidos, sendo ela retreinada
utilizando-se tal conjunto. Os resultados de tal teste estão resumidos na Tabela 4.7
Analisando-se os resultados conclui-se que o esperado aconteceu: o desempenho da classificação
sofreu uma leve melhora, proporcional a pequena quantidade de pa drões acrescentados ao conjunto
de treinamento da RNAH-intuição. Além disso , nota-se que a mesma continua sensível a mudanças
46
Ta bela 4.3: Classificação das Classes Corredor e Porta - Camada Intuição
Classe Correto Correto com um baixo valor de ativação
Porta 93 % 7 %
Corredor 95 % 0 %
Ta bela 4.4: Porcentagem Geral da Classificação Correta das Camadas Razão e Intuição - Teste 2
Camada Classificação Geral Padrões Desconhecidos Padrões Alterados
Razão 100% 100% 100%
Intuição 82% 77% 93%
de iluminação e pontos-de-vista das imagens coletadas. Dessa forma, a proposta para se melhorar
o desempenho desta camada da RNAH é aumentar a quantidade de imagens fornecidas como
entrada da rede em cada local a ser classificado, de modo que a decisão final da classificação vai
depender do resultado obtido na classificação das várias imagens do mesmo local coletadas sob
diferentes pontos-de-vista do robô.
Aumentando-se o espaço amostral espera-se alcançar melhores resultados, já que em to dos os
locais testados, a RNAH-intuição obteve uma taxa de acertos superior a 60%.
No caso da rede razã o, a terceira etapa de testes consistiu em apresentar à rede um conjunto
de padrões formado por medidas de distância reais. A Figura 4.6 ilustra o esquema de leitura dos
sonares, mostrando os ângulos definidos para cada leitura.
As leituras foram realizadas em nove lugares distintos, entre co rredores e portas localizadas
tanto à frente quanto nas laterais do robô. Os locais estão ilustrados na Figura 4.7.
A Figura 4.8 exemplifica um exemplo das distâncias calculadas para o local L1. As distâncias
foram calculadas em milímetros e estão realcionadas ao seu respectivo ângulo de leitura.
Os padrões que modelam os nove lugares testados foram construídos baseados nestas infor-
mações e no conhecimento prévio dos locais, supondo-se que:
• para os sonares laterais, distâncias superiores à 1000mm são consideradas aberturas laterais,
podendo consistir numa porta ou um corredor lateral
• para o sonar dianteiro, considerando-se que para locomoção do robô são necessários 200mm
de distância entre o robô e um obstáculo lateral, se a distância d calculada no ângulo de 90
◦
vertical/20
◦
horizontal e 90
◦
vetical/160
◦
horizontal satisfaz a equação 4.1.1, considera-se
que existe espaço livre à frente do robô.
d ≥
200 +
r
2
0.93
, onde r é a largura do chassi do robô (4.1.1)
O resultado geral obtido pela RNAH-razão considerando também esta fase está resumido na
Ta bela 4.8, sendo que na terceira etapa a rede alcançou uma taxa de classificação correta de
70%. Entretanto, vale a observação de que tal RNA foi treinada utilizando-se dados não reais que
modelavam situações ideais, diferentes daquelas encontradas nesta terceira fase de teste. Dessa
forma, tal camada deve então ser submetida a um outro processo de treinamento, onde o conjunto
de padrões deve ser construído utilizando-se medidas reais de distância.
4.2 Módulo Caracterizador
Para implementar o módulo caracterizador usou-se o algoritmo SIFT implementado por (ET-
TINGER, 2008). Os testes consistiram na extração de características SIFT a partir de imagens
47
Figura 4.6: Procedimento de leitura real dos sensores. Cinco posições de leitura para os sonares
laterais direito e esquerdo; vinte e cinco posições de leitura para o sonar dianteiro.
Figura 4.7: Locais onde os sonares coletaram medidas de distâncias do robô em relação a obstá-
culos: corredores e portas localizadas tanto à frente quanto nas laterais do robô.
48
Ta bela 4.5: Classificação das Classes Corredor e Porta: Camada Intuição - Abertura lateral:
Camada Razão
Classe Correto Correto com um baixo valor de ativação
Porta 87 % 3 %
Corredor 79 % 0 %
Porta ou Corredor lateral 100% 8%
Ta bela 4.6: Resultado Geral da Classificação da RNAH razão e intuição nas duas etapas de testes:
Tes te 1 e Teste 2
Camada Padrões desconhecidos Generalização Desempenho Etapa de Teste
Razão -% -% 100% Te ste 1
30% 100% 100% Te ste 2
Intuição 44% 96% 94% Teste 1
70% 77% 82% Teste 2
omnidirecional, utilizando estas características para treinar uma RNA com o objetivo de criar um
classificador de marcos visuais. Tais imagens não são submetidas a qualquer processo de retificação
ou pré-processamento.
O algoritmo detectou de 50 a 100 vetores de atributos para cada imagem. Cada vetor possui
7 atributos para cada característica: coordenada x da característica, c oordenada y, escala da
característica, tamanho, flag de aresta , flag de orientação e curvatura de resposta através do
espaço escala. O resultado é uma matriz mXn onde m é o número de características extraídas da
imagem e n é o número de atributos de cada característica.
A Figura 4.9 ilustra imagens omnidirecional do Corredor 3 - C3 visto sob três pontos de vista
diferentes. As marcações feitas sob as imagens representam as características SIFT extraídas pelo
algoritmo de (ETTINGER, 2008). Cada característica é representada p or um retângulo localizado
no local onde a mesma é encontrada. O tamanho do retângulo varia de acordo com o tamanho
da característica que ele representa.
Fa zendo-s e uma análise visual dessas imagens nota-se que as características extraídas nas três
cenas são similares em quantidade, tamanho e localizaçã o. O mesmo pode ser notado nas Figuras
4.10, 4.11 e 4.12.
Estas similaridades ilustram a inva riância das características SIFT, propriedade esta desejável
no contexto de seleção e reconhecimento de marcos visuais.
A abordagem adotada para criação de um classificador de marcos utilizando uma RNA foi
testada utilizando-se o SNNS. A rede criada é uma perceptron multi-camadas com 350 neurônios
na camada de entrada, cada um dos quais recebe o valor de um dos 7 atributos de um dos 50
vetores de características extraídos para cada imagem.
Os quatro locais referenciados nas Figuras 4.9, 4.10, 4.11 e 4.12 foram utilizados para treina-
mento e teste da RNA. A rede foi treinada com o algoritmo Backpropagation e o conjunto de
treinamento incluiu 48 padrões, os quais consistiam das características extraídas a partir das
imagens omni dos quatro locais já citados.
Os testes consistiram na variação do número de neurônios na camada oculta, bem como dos
parâmetros passados ao algoritmo de treinamento. Entretanto, os resultados obtidos foram simi-
lares, independentes das alterações realizadas. Em geral, a taxa de classificação correta alcançada
por todas RNAs treinadas foi de 30%. Tal valor deixa claro que a utilização de uma RNA para
tal aplicação não é adequada.
49
Ta bela 4.7: Porcentagem Geral da Classificação Correta da Camada Intuição - Teste 3
Camada Classificação Geral Padrões Desconhecidos Padrões Alterados
Intuição 84% 79% 95%
Ta bela 4.8: Porcentagem Geral da Classificação Correta da Camada Intuição - Teste 3
Camada Classificação Geral Padrões Desconhecidos Padrões Alterados
Razão 93% 84% 100%
Figura 4.8: Tabela das distâncias calculadas pelos sonares no local L1: corredor localizado à
direita do robô.
50
Figura 4.9: Características SIFT extraídas a partir de imagens omnidirecional do Corredor 3, visto
sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As características SIFT são
representadas por um retângulo localizado onde a característica foi encontrada. O tamanho da
característica é representado pelo número inteiro no interior do mesmo.
Figura 4.10: Características SIFT extraídas a partir de imagens omnidirecional do Corredor 4,
visto sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As características SIFT
são representadas por um retângulo localizado onde a característica foi encontrada. O tamanho
da característica é representado pelo número inteiro no interior do mesmo.
51
Figura 4.11: Características SIFT extraídas a partir de imagens omnidirecional do Porta 2, visto
sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As características SIFT são
representadas por um retângulo localizado onde a característica foi encontrada. O tamanho da
característica é representado pelo número inteiro no interior do mesmo.
Figura 4.12: Características SIFT extraídas a partir de imagens omnidirecional do Porta 3, visto
sob três pontos de vista diferentes: a) Visão 1 b) Visão 2 c) Visão 3. As características SIFT são
representadas por um retângulo localizado onde a característica foi encontrada. O tamanho da
característica é representado pelo número inteiro no interior do mesmo.
52
Capítulo 5
Conclusões
Este trabalho contempla uma técnica de modelagem de ambientes para navegação do robô móvel
do Laboratório de Automação e Controle Evolutivo - LACE, o qual usa seu sistema de visã o
omnidirecional e sensores de ultra-som para adquirir informações sobre o ambiente externo e
fornecê-las ao sistema de mapeamento. Neste trabalho apresenta-se dois módulos do sistema de
mapeamento: módulo classificado r de nós e módulo caracterizador de nós.
O modulo classificador utiliza como ferramenta de classificação uma rede neural hierárquica
estruturada em duas camadas: razão e intuição. O objetivo da criação de uma RNA estruturada
hierarquicamente é resolver possíveis conflitos no processo de cla ssificaçã o. Ou seja, quando a
primeira rede não conseguir distinguir o local a ser classificado utilizando informações dos sonares,
a segunda rede utiliza infomações extraídas a partir de imagens do local para classificar o mesmo.
A fase de testes, compos ta por três etapas, teve como o bjetivo validar o treinamento das
RNAs tendo como base os resultados obtidos. Dessa maneira, quando necessário as redes foram
retreinadas com diferentes alg oritmos de treinamento, parâmetros ou quantidade de neurônios na
camada oculta, a fim de se alcançar o melhor desempenho na classificação dos padrões testados.
O uso de uma perceptron de camada única nos testes da rede razão apresentou excelentes
resultados já que na etapa final dos testes utilizando dados simulados a classificação da mesma
alcançou 100% de acertos. Considerando também a terceira fase, pode-se concluir que, de modo
geral, o dese mpenho da rede foi satisfatório, tendo a mesma alcança do 93% de acertos. Sendo
assim, tal arquitetura de rede mostrou-se adequada para a implementação do sistema real do
sistema de mapeamento do robô.
A RNAH-intuição alcançou uma taxa de classificação correta de 84% na fase final de testes.
Ta l valor é considerado satisfatório, tendo em vista que a proposta para o método de classificação
é basear a decisão final num conjunto de resultados obtidos a partir da classificação de diferentes
situações do mesmo local, ou seja, basear a decisão de classe num espaço amostral maior, e não
somente um uma única situação de cada local.
Além disso, vale ressaltar a taxa de generalização alcançada pelas RNAH razão e intuição:
84% e 79%; valores estes considerados satisfatórios. Assim, a Rede Neural Artifial Hierárquica
alcançou o objetivo para a qual foi criada: resolver possíveis conflitos no processo de classificação
da primeira sub-rede.
Um outro fator importante consiste na baixa resolução das imagens panorâmicas utilizadas,
50 x 60 pixels, a qual foi suficiente para o propósito de classificação.
Sobre o módulo caracterizador, pode-se dizer que a RNA classificador de marcos treinada
com as características SIFT não obteve bons resultados. Entretanto, pode-se constatar que a
aplicação da transformada SIFT em imagens que sofreram algum tipo de transformação produz
características que visualmente são similares, considerando a variação no ponto-de vista durante
a coleta. Tal propriedade serve como motivação para o desenvolvimento de outra técnica para
53
implementar o selecionador e reconhecedor de marcos visuais utilizando tais características. Além
disso, resultados publicados na literatura da área mostram a robustez de tal método (TAMINI et.
al., 2006; LOWE, 2004; ANDREASSON e DUCKETT, 2004)
5.1 Proposta para Trabalhos Futuros
Com base nos resultados obtidos no processo de classificação das camadas razão e intuição conclui-
se que o objetivo inicial para a criação de uma rede neural hierárquica foi alcançado. Para se
concluir o módulo de mapeamento do robô móvel do LACE, propõem-se:
• Implementação do módulo classificador.
• Estudo e definição de um método para selecionar e reconhecer marcos visuais com o objetivo
de usá-lo no módulo caracterizador.
• Considerar diferentes técnicas de seleção e reconhecimento de marcos para os módulos ca-
racterizador e identificador de nós, comparando seus desempenhos.
• Considerar ambiguidades nas situações que descrevem os nós.
• Incluir no sistema informações de origem odométrica, as quais podem auxiliar a resolver as
ambiguidades.
54
Apêndice A
Testes - RNAH-Razão
Neste Apêndice descreve-se a terceira etapa de testes da camada razão, o qual consistiu na clas-
sificação de lugares modelados de acordo com distâncias reais. Vale ressaltar que no processo de
treinamento desta RNA utilizou-se apenas padrões construídos com base em modelos ideais de
distâncias.
1. Local 1 - L1
Descrição: co rredor localizado à direita do robô.
Classificação: Incorreta.
Imagem Real: Figura A.1
Tabela de distâncias: Figura A.2
Figura A.1: Imagem real de L1.
2. Local 2 - L2
Descrição: porta localizado à direita do robô.
Classificação: correta
Imagem Real: Figura A.3
Tabela de distâncias: Figura A.4
3. Local 3 - L3
Descrição: robô percorrendo um corredor.
Classificação: Incorreta
Imagem Real: Figura A.5
Tabela de distâncias: Figura A.6
4. Local 4 - L4
Descrição: co rredor localizado à direita do robô.
55
Figura A.2: Distâncias calculadas pelos sonares laterais e frontal para L1.
Classificação: Correta.
Imagem Real: Figura A.7
Tabela de distâncias: Figura A.8
5. Local 5 - L5
Descrição: co rredor localizado à esquerda e à frente do robô.
Classificação: Correta.
Imagem Real: Figura A.9
Tabela de distâncias: Figura A.10
6. Local 6 - L6
Descrição: co rredor localizado à frente do robô com abertura lateral à direita.
Classificação: Correta.
Imagem Real: Figura A.11
Tabela de distâncias: Figura A.12
7. Local 7 - L7
Descrição: porta localizado à esquerda do robô, com abertura lateral à direita.
56
Figura A.3: Imagem Real de L2.
Classificação: Correta.
Imagem Real: Figura A.13
Tabela de distâncias: Figura A.14
8. Local 8 - L8
Descrição: porta localizada em um corredor, à esquerda do robô.
Classificação: Incorreta.
Imagem Real: Figura A.15
Tabela de distâncias: Figura A.16
9. Local 9 - L9
Descrição: co rredor localizado à frente do robô com abertura lateral à esquerda.
Classificação: Correta.
Imagem Real: Figura A.17
Tabela de distâncias: Figura A.18
57
Figura A.4: Distâncias calculadas pelos sonares laterais e frontal para L2.
Figura A.5: Imagem Real de L3.
58
Figura A.6: Distâncias calculadas pelos sonares laterais e frontal para L3.
Figura A.7: Imagem Real de L4.
59
Figura A.8: Distâncias calculadas pelos sonares laterais e frontal para L4.
Figura A.9: Imagem Real de L5.
60
Figura A.10: Distâncias calculadas pelos sonares laterais e frontal para L5.
Figura A.11: Imagem Real de L6.
61
Figura A.12: Distâncias calculadas pelos sonares laterais e frontal para L6.
Figura A.13: Imagem Real de L7.
62
Figura A.14: Distâncias calculadas pelos sonares laterais e frontal para L7.
Figura A.15: Imagem Real de L8.
63
Figura A.16: Distâncias calculadas pelos sonares laterais e frontal para L8.
Figura A.17: Imagem Real de L9.
64
Figura A.18: Distâncias calculadas pelos sonares laterais e frontal para L9.
65
Apêndice B
Publicações
Fo ram publicados os seguintes artigos referentes a este trabalho:
• Silva, L.L.; Tronco, M.L.; Vian, H.A.;Porto, A.J.V.; "Classification a nd Characterization of
Places for Mapping o f Environment Using Hierarchical Neural Network and Omnivision",
15th International Conference on Systems, Signals and Image Processing, Bratislava, junho
de 2008.
• Silva, L.L.; Tronco, M.L.; Vian, H.A.; Souza, R . C. G.; Porto, A.J.V.; "Classification and
Characterization of Places for Mapping of Environment Using Hierarchical Neural Network
and Omnivision", IEEE World Congress on Computational Intelligence, Hong Kong, junho
de 2008.
• Silva, L.L.; Tronco, M.L.; Vian, H.A.; Souza, R. C. G.; Porto, A.J.V.; "MAPEAMENTO DE
AMBIENTES INTERIORES PARA ROBÔ MÓVEL BASEADO EM MARCOS VISUAIS
E REDE NEURAL HIERÁRQUICA"’, V Congresso Nacional de Engenharia Mecânica,
Salvador, agosto de 2008.
• Silva, L.L.; Tronco, M.L.; Vian, H.A.;Porto, A.J.V.; "CLASSIFICAÇÃO E CAR ACTER-
IZAÇÃO DE AMBIENTES PARA NAVEGAÇÃO DE ROBÔS MÓVEIS BASEADA EM
MAPAS", XVII Congresso Brasileiro de Automática, Juiz de Fora, setembro de 2008.
• Silva, L.L.; Tronco, M.L.; Vian, H.A.;Porto, A.J.V.; "NAVEGAÇÃO DE ROBÔS MÓVEIS
ATR AVÉS DE MODELAGEM DE AMBIENTES UTILIZANDO REDE NEURAL HI-
ERÁRQUICA", X Encontro de Modelagem Computacional, Instituto Politécnico/UERJ,
novembro de 2007.
• Silva, L.L.; Tronco, M.L.; Vian, H.A.;Porto, A.J.V.; "Modelagem de Ambientes para Robô
Móvel baseado em Rede Neural Hierárquica e Visão Omnidirecional", Workshop de Visão
Computacional, outubro de 2007.
66
Referências Bibliográficas
[1] Andreasson, H.; Duckett, T. "Topological localization for mobile robots using omnidirec-
tional vision and local features". In Proc. IAV 2 00 4, the 5th IFAC Symposium on Intelligent
Autonomous Vehicles, 200 4.
[2] Arleo, A., Gerstner, W. "Spatial cog nition and neuromimetic navigation: a model of hip-
pocampal place-cell activity". Biological Cybernetics , Special Issue on Navigation in Biolo-
gical and Artificial Systems, 83, 287-299, 2000.
[3] Atiya, S.; Hager, G. "Real-time Vision-based Robot Localization". IEEE Transactions on
Robotics and Automation, Vol. 9, No. 6, pp. 785-800, 1993.
[4] Ayache, N., Faugeras, O. "Maintaining representations of the environment of a mobile robot".
IEEE Transa ctions on Robotics and Automation, 5(6), 804-819, 1989.
[5] Bachelder, I. A., Waxman, A. M. "A view-based neurocomputational system for relational
map-making and navigation in visual environments". Robotics and Autonomous Systems, n
◦
16, pp. 267-298.
[6] Baczyk, R., Kasi´nski, A., Skrzypczy´nski, P. "Vision-based mobile robot localization with
simple artificial landmarks", 2003.
[7] Balakrishnan, K., Bousquet, O., Honavar, V. "Spatial learning and localization in rodents: a
computation mo del of the for hippocampus and its implications for mobile robots". Adaptive
Behavior, 7(2), 173-21 6, 199 9.
[8] Beale, R.; Jackson, T.; Neural Computing: An Introduction, Institute of Physics Publishing,
Lodon, 1992.
[9] Boreinstein, J.; Everett, H. R.; Feng, L. "’Where am I?’ Sensors and Methods for Mobile
Robot Positioning". University of Michigan, 1996.
[10] Braga , A.; Ludemir, T. B. and Carvalho, A.; Redes neurais artificiais, LTC, 2000.
[11] Burguess, N.; Donnett, J.; Jeffery, K.; O’Keefe, J. "Robotic and neuronal simulation of the
hippocampus and rat navigation". Philosophical Transactions of the Royal Society B 352,
1535-1543, 1997.
[12] Câmera omnidirecional com espelho hiperbólico. Altura 131 pi-
xels. Largura 140 pixels. 72 dpi. Formato JPEG. Disp o nível em:
<http://w3.sys.es.osa kau.ac.jp/projects/robot/images/hovi.jpg>. Acess ado em: 10 mai.
2008.
[13] Cavani, F. A., Sistema de Visão Omnidirecional para Robô Móvel, Projeto Final de Graduação
em Ciência da Computação, (2004).
67
[14] Chen, Z.; B irchfield, S. T. "Qualitative Vision-Based Mobile Robot Navigation". IEEE In-
ternational Conference on Robotics and Automation (ICRA), Orlando, Florida, 2006.
[15] Cox, I. J. "Blanche - an experiment in guidance and navigation of an autonomous robot
vehicle", IEEE Transactions on Robotics and Automation, 7(2), 193-204, 1991.
[16] Duda, R. O.; Hart, P. E."Pattern Classification and Scene Analysis". JohnWiley E Sons,
1973.
[17] Engelson, S. P., McDermott, D. V. "Error correction in mobile robot map-learning". In
Proceedings of the IEEE international conference on robotics and automation (ICRA- 92).
Press, pp. 2555-2560, 1992.
[18] Fairhurst, M. C.; Computer Vision for Robotic Systems An Introduction, Prentice Hall, 1988.
[19] Feder, H., Leonard, J., Smith, C. "Adaptive mobile robot navigation and mapping". Interna-
tional Journal of Robotics Research, 18(7), 650-668. 896-901, 1999.
[20] Filliat, D.; Meyer, J. A. "Map-based navigation in mobile robots: I. A review of localization
strategies". Journal of Cognitive Systems Research, vol 4, pp. 243 - 282, 2003.
[21] Flusser, J.; Suk, T. "Pattern recognition by affine moment invariants". Pattern Recognition,
Vo l 26, No 1, pp. 167-174 , 1993 .
[22] Franz, M., Scholkopf, B., Georg, P., Mallot, H., Bulthoff, H. "Learning view graphs for robot
navigation". Autonomous Robots, 5, 111-125, 1998.
[23] Goldberg, S. B.; Maimone, M. W.; Matthies, L. "Stereo vision and robb er navigation software
for planetary exploration". IEEE Aerospace Conference Proceedings, vol. 5, pp. 2025-2036,
2002.
[24] Gomes, J.; Velho, L.; Computação Gráfica: Imagem, Instituto de Matemática Pura e Apli-
cada, Sociedade Brasileira de Matemática, 1994.
[25] Gsós, J., Martin, A., "Mobile robot localization using fuzzy maps". In Martin, T., & Ralescu,
A. (Eds.), Fuzzy lo gic in AI - selected papers from the IJCAI ’95 workshop, n
◦
1188 in LNCS.
Spring-Verlag , pp. 207-22 4, 199 7.
[26] Guiachetti A.; Campani M.; Torre V. "The use of optical flow for road navigation. IEEE
Tra nsactions on Robotics and Automation", vol 14, n
o
1, pp. 34-48, 1998.
[27] Gutmann, J., Konolige, K. "‘Incremental mapping of large cyclic environments". In Pro-
ceedings of the IEEE international symposium on computational intelligence in robotics and
automation (CIRA- 2000). IEEE Press, 2000.
[28] Haykin, Simon. Redes Neurais : princípios e prática. Traduzido por Paulo Martins Engel. 2.
ed. Porto Alegre : Bookman, 2001. 900 p. il.
[29] Kortenkamp, D., Weymouth, T. "Topological mapping for mobile robots using a combina-
tion of sonar and vision sensing."Proceeding of the 12th National Conference on Artificial
Intelligence. Vol. 2, p. 979-84. MIT Press, 1994.
[30] Kuipers, B., Beeson, P. "Bootstrap learning for place recognition". In Proceedings of the 18th
national conference on artificial intelligence (AAAI- 02). AAAI/MIT Press, 2002.
68
[31] Kuipers, B. "The spa tial semantic hierarchy". Artificial Intelligence, vol. 119, pp. 191-233,
2000.
[32] Kuipers, B. J., Byun, Y. T. "A robot exploration and mapping strategy based on a semantic
hierarchy of spatial representations". Robotics and Autonomous Systems, 8, 47-63, 1991.
[33] Lente olho de peixe. Altura 294 pixels. Largura 296 pixels. 72 dpi. Formato JPEG. Disponível
em: <http://cmp.felk.cvut.cz/ bakstein/demo/fisheye/nikon2.jpg>.Acessado em: 10 maio
2008.
[34] Leonard, J. J., Durrant-Whyte, H. F., Cox, I. J. "Dynamic map building for an autonomous
mobile robot". International Journal of Robotics Research, 11(4), 89-96, 199 2.
[35] Levitt, T. S., Lawton, D. T. "Qualitative navigation for mobile robots". Artificial Intelligence,
44, 305-360. (SAB 02). MIT Press, 1990.
[36] Lin, S.; Bajcsy, R.; The single view point cone mirror omnidirectional catadioptric system.
ICCV01, vol 2, pp. 102-107.
[37] Lowe, D. G. "Object Recognition from Local Scale-Invariant Features". Proceedings of the
International Conference on Computer Vision, 1999.
[38] Lowe, D. G. "Distinctive Image Features from Scale-Invariant Keypoints", International Jour-
nal of Computer Vision, 2004.
[39] Lu, F., Milios, E. "Globally consistent range scan morpholoalignment for environment map-
ping". Autonomous Robots 4, 333-349, 1997.
[40] Martinez, V. O.; Costa, A. H. R. "Reconhecimento de marcos visuais como cenas para loca-
lização de robôs móvies", 2005.
[41] Mataric, M. J. "Integration of representation into goal- driven behaviour-based robots". IEEE
Tra nsactions on Robotics and Automation, 8(3), 304-312, 1992.
[42] Mecanismo para rotação da câmera. Altura 240 pixels. Largura 179 pixels. 72 dpi. Formato
JPEG. Disponível em: <http://www.cohucameras.com/products/ppix/3950med.jpg>. Aces-
sado em: 10 maio de 2008.
[43] Moravec, H., Elfes, A. "High resolution maps from wide angular sensors", In Proceedings of
the IEEE international conference on robotics and automation (ICRA- 85). IEEE Press, pp.
116-121, 1985.
[44] Prescott, T. J. "Spatial representation for navigation in animats". Adaptive Behavior, 4(2),
85-123, 1995.
[45] Rao , R. P. N.; Zelinsky, G. J.; Hayhoe M. M.; Ballard D. H. "Eye movements in iconic visual
search", Vision Research, 2002.
[46] Rekleitis, I. M.; Dujmovic, V. "Efficient topological exploration". Proceedings of the IEEE
International Conference on Robotics and Automation, Detroit, Michigan, pp. 676-681, 1999.
[47] Rencken, W.D. "Concurrent Localization and Map Building for Mobile Robots Using Ultra-
sonic Sensors". Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent
Robotics and Systems, pp. 2192-2197, 1993.
69
[48] Scharstein, D.; Brigg s, A. J. "Real-time recognition of s elf-similar landmarks". Image and
Vision Computing, vol 19, pp. 763-772, 2000.
[49] Se, S.; Lowe, D.; Little, J. "Local and global localization for mobile robots using visual
landmarks". In Proceedings of the IEEE/RSJ International Conference on Intelligent R obots
and Systems (IROS), pp. 414-420, 2001.
[50] S. Se, D. Lowe, and J. Little, "Mobile robot localiza tion and mapping with uncertainty using
scale-invariant visual landmarks", The International Journal of Robotics Research, vol. 21,
no. 8, pp. 735–758, 2002. http://citeseer.ist.psu.edu/se02mobile.html
[51] Spacek, L. Omnidirectional Catadioptric Vision Sensor with Conical Mirrors, Journal of
Robotics e Autonomous System, November, 2003.
[52] Tamimi, H.; Andreasson, H.; Treptowa, A.; Duckettc, T.; Zella, A. "Localization of mobile
robots with omnidirectional vision using Particle Filter and iterative SIFT". Robotics and
Autonomous Systems, vol. 54, pp. 758-765, 2006.
[53] Taylor, C., "Building Representations for the Environment of a Mobile Robot from Image
Data."Proceedings of the 1991 SPIE Conference on Mobile Robots, Boston, MA, Nov. 14-15,
pp. 331-339, 1991.
[54] Thrun, S., Burgard, W., Fox, D. "A real-time algorithm for mobile robot mapping with
applications to multi-robot and 3D mapping". In Proceedings of the IEEE international
conference on robotics and automation (ICRA- 2000). IEEE Press, pp. 321-328, 2000.
[55] Thrun, S. "Learning metric-topological maps for indoor mobile robot navigation". Artificial
Intelligence, 99(1), 21-71, 19 99 .
[56] Ulrich, I., Nourbakhsh, I. "Appearance-based place recognition for topological localization".
In Proceedings of the IEEE international conference on robotics and a utomation (ICR A-
2000), vol. 2. IEEE Press, pp. 1023-1029 , 2000 .
[57] Van Der Zwaan, S.; Santos-Victor, J. A. Real-time vision-based station keeping underwater
robots. MTS/IEEE Conference OCEANS, vol. 2, pp. 1058-10 65 , 2001 .
[58] Vassallo R. F.; Sheneebeli H. J.; Santos-Victor J. "Visual Navigation: Combining visual
servoing and appearance based methods". 6th International Symposium on Intelligent Robotic
Systems, SIS´s 98, Edinburg, Scotland, 1998.
[59] Vasudevan, S.; Gachter, S.; Nguyen, V.; Siegwart, R. "Cognitive maps for mobile robots - an
object based approach". Robotics and Autonomous Systems, vol. 55, pp. 359-371, 2007.
[60] Wichert, G. V. "Mobile robot localization using a self-organized visual environment repre-
sentation". Robotics and Autonomous Systems, 25, 185-194, 1998.
[61] Wahlgren, C.; Duckett, T. "Topological Map Building for Mobile Robots Using Omnidirec-
tional Vision". (extended abstract)Proc. SWAR’05, Third Swedish Workshop o n Autonomous
Robotics, pp. 1-2, 2005.
[62] Yamauchi, B. "A frontier-based approach for autonomous exploration" . In: Pro ceeding of
the 1997 IEEE International Symposium on Computacional Intelligence in Robotics and
Automation, pp. 146-151, 1997.
70
[63] Yamauchi, B., Beer, R. "Spatial learning for navigation in dynamic environments". IEEE
Tra nsactions on Systems ,Man, and Cybernetics-Part B .Special Issue on Learning Au-
tonomous Robots, 26(3), 496-505, 1996.
[64] Zell, A., Mamier, G., Vogt, M., Mache, N., Hubner, R., Doring, S., Herrmann, K., Soyez, T.,
Schmalzl, M., Sommer, T., Hatzigeorgiou, A., Posselt, D., Schreiner, T., Kett, B., Clemente,
G., Wieland, J.; SNNS Stuttgart neural network simulator user manual, Disponível em
http://www.ra.informatik.unituebingen.de/downloads/SNNS/ SNNSv4.2. Manual.pdf. Aces-
sado em: 7 de março de 2007.
[65] Zitovà, B.; Flusser, J. "Landmark recognition using invariant features". Pattern REcognition
20, 541-547, 1999.
71
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
