AdelsonLL-DISSERT

Prévia do material em texto

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE TECNOLOGIA
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E
DE COMPUTAÇÃO
Uma aplicação do algoritmo QT clustering para
marcação colaborativa de pontos perigosos em
vias públicas
Adelson Luiz de Lima
Orientador: Prof. Dr. Agostinho de Medeiros Brito Júnior
Dissertação de Mestrado apresentada ao
Programa de Pós-Graduação em Engenharia
Elétrica e de Computação da UFRN como
parte dos requisitos para obtenção do título
de Mestre em Ciências.
Número de ordem PPgEE: M372
Natal, RN, dezembro de 2012
UFRN / Biblioteca Central Zila Mamede
Catalogação da Publicação na Fonte
Lima, Adelson Luiz de.
Uma aplicação do algoritmo QT clustering para marcação colaborativa de
pontos perigosos em vias públicas / Adelson Luiz de Lima. - Natal, RN, 2013.
45 f. : il.
Orientador: Prof. Dr. Agostinho de Medeiros Brito Júnior.
Dissertação (Mestrado) - Universidade Federal do Rio Grande do Norte.
Centro de Tecnologia. Programa de Pós-Graduação Engenharia Elétrica e da
Computação.
1. Algoritmo QT - Dissertação. 2. Acidentes de trâncito - Prevenção -
Dissertação. 3. Sistema de alerta - Dissertação. 4. Sistemas colaborativos
- Dissertação. 4. Aglomeração de dados - Dissertação. 5. Sistema de
Informação Geográfica - Dissertação. I. Brito Júnior, Agostinho de Medeitos. II.
Universidade Federal do Rio Grande do Norte. III. Uma aplicação do algoritmo
QT clustering para marcação colaborativa de pontos perigosos em vias públicas.
RN/UF/BCZM CDU 004.021
Uma aplicação do algoritmo QT clustering para
marcação colaborativa de pontos perigosos em
vias públicas
Adelson Luiz de Lima
Dissertação de Mestrado aprovada em 7 de dezembro de 2012 pela banca examinadora
composta pelos seguintes membros:
Prof. Dr. Agostinho de Medeiros Brito Júnior (orientador) . . . . . . . DCA/UFRN
Prof. Dr. Allan de Medeiros Martins . . . . . . . . . . . . . . . . . . . . . . . . . . . DEE/UFRN
Prof. Dr. Paulo Sérgio da Motta Pires . . . . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN
Prof. Dr. George Azevedo da Silva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IFRN
Dedico este trabalho à minha
família e amigos.
Agradecimentos
Ao meu orientador, professor Agostinho, sou grato pela orientação.
Ao professor Paulo Motta, pelos valiosos comentários que enriqueceram meu trabalho.
Aos meus colegas de pós-graduação, pelas críticas, sugestões e apoio.
À minha família e amigos pelo apoio durante esta jornada.
À CAPES, pelo apoio financeiro.
Resumo
O trabalho propõe um sistema colaborativo para marcação de pontos perigosos em
vias de transporte e geração de alertas para motoristas. Ele consistire de um sistema
de alerta de proximidade de um ponto de perigo, que será alimentado pelos próprios
motoristas através de um aparelho móvel equipado com GPS. O sistema deverá consolidar
dados fornecidos por vários motoristas diferentes e gerar um conjunto de pontos comuns
que serão usados no sistema de alerta. Embora a aplicação seja destinada à proteção
de motoristas, os dados gerados por ela poderão servir de insumos para os órgãos
responsáveis melhorarem a sinalização e recuperação de vias públicas.
Palavras-chave: Prevenção de acidentes de trânsito, sistema de alerta, sistemas
colaborativo, aglomeração de dados, sistemas de informação geográfica.
Abstract
This work proposes a collaborative system for marking dangerous points in the
transport routes and generation of alerts to drivers. It consisted of a proximity warning
system for a danger point that is fed by the driver via a mobile device equipped with
GPS. The system will consolidate data provided by several different drivers and generate
a set of points common to be used in the warning system. Although the application is
designed to protect drivers, the data generated by it can serve as inputs for the responsible
to improve signage and recovery of public roads.
Keywords: Prevention of traffic accidents, warning systems, collaborative systems,
data clustering, geographic information systems.
Sumário
Sumário i
Lista de Figuras iii
1 Introdução 1
1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Sistemas de Informação Geográfica 5
2.1 Foursquare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 WAZE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 WikiMapa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Wikimapia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Comob . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6 Avaliação das ferramentas pesquisadas no escopo do trabalho proposto . . 9
3 Aglomeração de dados 11
3.1 QT clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Trabalho proposto 16
4.1 Funcionamento do sistema . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Marcação de pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Processamentos dos dados . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.4 Remoção de pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.5 Alertas de perigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.6 Interface desktop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.7 Sincronização e expurgo de dados . . . . . . . . . . . . . . . . . . . . . 24
4.8 Modelo do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Resultados 29
i
6 Considerações finais 34
7 Agradecimentos 36
Referências bibliográficas 36
Lista de Figuras
4.1 Arquitetura do sistema proposto para marcação e aglomeração de pontos. 17
4.2 Interface de usuário para dispositivo móvel. . . . . . . . . . . . . . . . . 18
4.3 Exemplo de nuvens formada pela marcação de vários motoristas com seu
ponto representativo e os diferentes tipos de nuvens com pontos de perigo
que podem ser marcados nos cursos das vias. . . . . . . . . . . . . . . . 20
4.4 Protótipo da interface desktop para visualização de centros usando os
recursos do Google Maps. . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.5 Módulos do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.6 Módulos/Plataformas do sistema . . . . . . . . . . . . . . . . . . . . . . 26
4.7 Diagrama de classes do módulo móvel . . . . . . . . . . . . . . . . . . . 27
5.1 Experimento em zona urbana. . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 Experimento em zona rural. . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3 Experimento em zona urbana - marcação de falhas nas Avenidas Salgado
Filho e Hermes da Fonseca, Natal-RN . . . . . . . . . . . . . . . . . . . 33
iii
Capítulo 1
Introdução
A imperícia e a imprudência no trânsito são, sem dúvida, os principais responsáveis
pela maioria dos acidentes nas estradas brasileiras. De fato, a má formação de condutores
para o trânsito brasileiro, junto com a dificuldade de fiscalização e aplicação de penas mais
severas aos infratores, contribui para o estado em que se encontra o trânsito no nosso país.
É inegável a contribuição da formação humana para a quantidade, a gravidade
e o tipo dos acidentes presentes nas estatísticas oficiais do DNIT - Departamento
Nacional de Infraestrutura de Transporte [DNIT 2011]. Entretanto, boa parcela dos
acidentes de trânsito no Brasil são provocados por falhas nas vias de transporte estaduais
e federais, sejam essas falhas buracos, ondulações, pavimentos irregulares, valetas,
inclinações, depressões, lombadas e curvaturas mal planejadas. As próprias estatísticas
do DNIT relatam que, em 2010, havia aproximadamente 3.000 km de vias no país que
concentravam acidentes.
Informações fornecidas pela Polícia Rodoviária Federal demonstramque, embora
reduzidos, acidentes por defeito nas vias ainda são comuns. Os dados fornecidos são
apresentados na Tabela 1.11.
Ano do Acidente Quantidade. de Acidentes % do total de acidentes
2007 2349 1,83%
2008 2191 1,55%
2009 2611 1,65%
2010 2413 1,32%
Total geral 9564 1,56%
Tabela 1.1: Estatísticas de acidentes causados por falhas em vias públicas.
Danos físicos e até mortes são consequências comuns em acidentes causados por
falhas nas vias, principalmente relacionado a veículos com duas rodas. Ainda, os danos
1informações gentilmente cedidas pela Polícia Rodoviária Federal
CAPÍTULO 1. INTRODUÇÃO 2
não se resumem apenas em prejuízo à integridade física dos motoristas e passageiros.
Grande prejuízos financeiro são agregados frequentemente a essas falhas, sejam eles
representados por gastos com manutenções ou reparos causados por tais problemas. Dada
a quantidade de impostos pagos pelos contribuintes para criação e manutenção de vias,
geralmente entende-se de responsabilidade do estado os prejuízos causados aos veículos
e passageiros pela má conservação, má sinalização ou má manutenção das vias públicas.
Um caso exemplar de grande prejuízo pode-se imaginar no meio das empresas
transportadoras de cargas. A perda da carga no caso de um tombamento ocasionado
por uma falha nas rodovias não só representa o prejuízo, mas também danos ao veículo e
atraso ocasionado pelo reenvio da carga. Em outras palavras, o prejuízo direto será não
somente para a empresa transportadora mas também para a sua contratante.
Embora investimentos públicos sejam feitos constantemente para melhorar a
qualidade das estradas brasileiras, a presença de pontos perigosos são inevitáveis.
As origens geralmente são advindas do desgaste natural pelo uso constante, relevo e
topologia, e a própria intempéries da natureza.
Diversas soluções comerciais que já são capazes de orientar motoristas no trânsito, que
são os tradicionais sistemas guiados por GPS (Global Positioning System). Alguns deles,
por exemplo, oferecem alertas de proximidade para radares de velocidade, permitindo
que o motorista fique atento aos limites de velocidade e, é claro, às multas impostas
pela transgressão destes limites. A eficiência destas soluções dependem do esforço das
empresas em manter sempre atualizados seus bancos de dados e nos mecanismos de
repasse destes dados aos proprietários dos sistemas de navegação. Apesar do sucesso
destas ferramentas, nota-se a carência de uma funcionalidade simples que permita aos
próprios motoristas ajudarem uns aos outros a se proteger de falhas e pontos perigosos
nas vias públicas, principalmente durante períodos noturnos, quando a visibilidade da via
diminui.
É nesse contexto que o presente trabalho é inserido, oferecendo uma forma de atenuar
os problemas decorrentes dos danos causados pelas falhas e pontos perigosos presentes
nas vias de transporte. O trabalho propõe um sistema que alerta aos motoristas da
proximidade de algum ponto de perigo, permitindo a tomada de decisões capazes de evitar
danos à saúde ou ao patrimônio.
O sistema proposto consistirá de um programa para dispositivos móveis que poderá ser
instalado em celulares do tipo smartphones equipados com GPS. O sistema será dotado de
uma interface bastante simples, com botões para propor a inserção e remoção de pontos
perigosos, além de exibir alertas visuais e sonoros aos seus usuários. A proposta da
implementação em smartphones alia conveniência e custo, haja vista o barateamento de
CAPÍTULO 1. INTRODUÇÃO 3
tais dispositivos no mercado, o uso cada vez mais presente destes dispositivos como meio
de comunicação e a presença de módulos GPS em grande parte deles. Neste contexto,
a ferramenta proposta seria apenas mais um aplicativo a ser inserido no smartphone,
tornando os custos da solução bastante reduzidos.
Para que o sistema alerte ao usuário da proximidade de um ponto de perigo é preciso
saber a localização deste ponto. Para isto, os usuários do sistema ao trafegarem pelas
vias e identificarem esses pontos contribuirão com o sistema marcando-os na ferramenta
interativa, para que a coordenada geográfica desse ponto seja transmitida ao servidor para
um futuro processamento.
A fusão das informações fornecidas pelos usuários deverá ser feita através de um
servidor central que coletará, através da Internet, os pontos marcados pelos usuários
da ferramenta e realizará a consolidação destes dados através da catalogação de
aglomerados de pontos sugeridos para trechos comuns. O servidor processará os pontos
oferecidos pelos motoristas utilizando algoritmos inteligentes, repassando as informações
consolidadas aos módulos dos smartphones, por requisição dos próprios usuários.
Os dados gerados pelo sistema serão integrados com o sistema de informações
geográficas Google Maps (http://maps.google.com), acessível através da Internet, que
mostrará a localização dos pontos de perigo e poderá disponibilizar estatísticas para que
usuários e governantes possam utilizá-lo de forma a visualizar e colaborar na prevenção
de acidentes. Ainda, a base de dados do sistema poderá servir de insumo para integração
em sistemas de navegação que permitam traçados de rotas mais seguras, evitando assim
possíveis danos ao motorista e ao seu veículo.
1.1 Objetivos
O objetivo geral do trabalho é desenvolver um sistema de alerta que ajude aos
motoristas de transportes automotivos a ficarem atentos a falhas nas vias de transporte
ou trechos perigosos, ajudando a evitar acidentes e prejuízos materiais. Sua principal
contribuição é oferecer uma ferramenta voltada especificamente para a realidade
brasileira, preenchendo uma lacuna deixada pela maioria das ferramentas comerciais
encontradas.
1.1.1 Objetivos Específicos
Os objetivos específicos do presente trabalho de pesquisa consistem em:
• Fazer uma revisão dos trabalhos existentes que utilizam SIG;
CAPÍTULO 1. INTRODUÇÃO 4
• Realizar estudos sobre algoritmos de aglomeração de dados (clustering);
• Elicitar os requisitos do sistema a ser desenvolvido;
• Modelar a arquitetura do sistema;
• Implementar protótipo de ferramenta para funcionamento em algum modelo de
smartphone;
• Propor uma mecanismo de coleta, distribuição e processamento de dados de
usuários;
• Validar o sistema proposto.
1.2 Organização do texto
Este trabalho encontra-se dividido da seguinte forma. O Capítulo 2 descreve a
ideia geral do trabalho que se propõe desenvolver no contexto de aplicações correlatas
existentes. O Capítulo 3 oferece uma visão geral de algoritmos de aglomeração de
dados, fundamentando a escolha do algoritmo de aglomeração proposto para uso no
processamento dos dados fornecidos pelos usuários. O Capítulo 4 descreve o sistema
proposto, seu funcionamento e sua arquitetura. O Capítulo 5 mostra alguns resultados
obtidos com pontos coletados em zonas urbanas e rurais no estado do Rio Grande do
Norte. O Capítulo 6 finaliza o trabalho apresentando algumas considerações acerca do
desenvolvimento e traça proposta de tarefas futuras agregadas à temática apresentada.
Capítulo 2
Sistemas de Informação Geográfica
Sistemas de Informação Geográfica (SIG) são ferramentas que permitem sobrepor
informações espaciais (geográficas) com vários outros tipos de informações [Clarke
1986]. A sobreposição permite cruzar informações respeitando uma determinada
localização geográfica. Deste modo, é possível construir mapas onde aparecem
informações úteis para analisar diversos fenômenos. Esse cruzamento de informações
possibilita vários estudos de análise espacial com base nos parâmetros presentes no SIG.
Devido às suas potencialidades, os SIGs são atualmente utilizados em diversas
atividades profissionais, seja em planejamento, em investigação científica, em estudos
de impacto ambiental ou compartilhamento de informações genéricas. Os SIGs permitem
ainda realizar diferentes operações de análise, como calcular distâncias, identificar os
elementos que se encontram em determinados locais, ou que tenham determinadas
características.
Praticamente não há limitaçãoacerca dos tipos de dados que podem ser utilizados
em um SIG. Embora originalmente tenham sido desenvolvidos para fins de exibição de
informações naturais como relevo, clima e vegetação, a tecnologia atual permite inserir
os mais variados tipos de dados em um SIG. Exemplos de informações presentes em
SIGs atuais incluem imagens, vídeos e pontos de referência. No presente trabalho, o SIG
funcionaria utilizando uma base de dados com as informações geográficas de pontos de
perigo que podem ser mostrados em um mapa digital como a plataforma Google Maps.
Os modelos mais comuns em SIG são o raster (ou matricial) e o vetorial. O modelo de
SIG matricial utiliza um mapa de células de tamanho regular, geralmente quadradas, que
armazenam valores de informação para uma dada região do espaço real. Quanto maior
a dimensão da célula, menor é a quantidade de detalhes que se consegue representar no
espaço geográfico. Quanto menor o tamanho da célula, maior a quantidade de detalhes.
No caso do modelo de SIG vetorial, a representação é focada na precisão da localização
dos elementos no espaço. A ferramenta Google Maps, por exemplo, apresenta uma
CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 6
mistura destes dois modelos. Em um mesmo mapa, é possível visualizar de forma
superposta informações de terreno (modelo matricial com fotos de satélite) e desenhos
com ruas, avenidas e pontos de referência (modelo vetorial).
Os campos de aplicação dos Sistemas de Informação Geográfica, por serem muito
versáteis, são muito vastos, podendo-se utilizar na maioria das atividades com um
componente espacial, da cartografia a estudos de impacto ambiental ou vigilância
epidemiológica de doenças, de prospecção de recursos ao marketing, constituindo o que
poderá designar de Sistemas Espaciais de Apoio à Decisão.
Dada a versatilidade do georeferenciamento de informações, é possível encontrar
aplicações dos mais variados tipos à disposição dos usuários. O foco inicial dos SIGs
nas áreas de cartografia e vigilância ambiental está migrando, atualmente, para as áreas
de interação social, disseminação dos mais variados tipos de informação e, notadamente,
comércio, propaganda e logística.
Além da disseminação dos SIGs no comércio, eles estão migrando cada vez mais
do uso em computadores pessoais (desktop) para o uso em dispositivos móveis. Neste
sentido, o mercado vem investindo de forma significativa, dado o potencial associado à
capacidade de geolocalização. Algumas aplicações SIG, como as que serão apresentadas
nas seções seguintes, embora conceitualmente simples, são notáveis em utilidade e
funcionalidade, cada qual em sua área de interesse.
2.1 Foursquare
Foursquare é uma plataforma de localização móvel, uma rede social, e um micro blog,
baseada em geolocalização, que permite ao utilizador indicar onde se encontra e procurar
por contatos que estejam próximo desse local. [Foursquare 2011]. A aplicação móvel está
disponível para celulares, através de SMS, ou smartphones, com suporte à iOS, Android,
Windows Mobile, Blackberry e Symbian.
O serviço Foursquare recolhe dados pessoais dos utilizadores e partilha-os com
outros, por iniciativa e consentimento do utilizador do serviço. O serviço é baseado
na partilha e comunicação da localização, por vontade própria, dos seus utilizadores.
Segundo informações da própria Foursquare, havia passado de 100 milhões a quantidade
de atualizações de dados em diferentes locais no mês de julho de 2010. A taxa de
crescimento de entrada de usuários vêm de 1 milhão de atualizações, no ano de 2010,
para mais de 40 milhões nos últimos dois meses de 2010.
A utilização do serviço se dá através de um dispositivo móvel, como celular ou
smartphone. O usuário do serviço acessa o site, ativa seu perfil, identifica o local onde
CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 7
está via GPS, e informa a informação desejada já georeferenciada. O usuário pode ainda
compartilhar sua localização com outras pessoas, via Facebook ou Twitter.
2.2 WAZE
Geralmente chamado de GPS social, o Waze é um aplicativo que funciona em
smartphones dotados dos sistemas operacionais Android, iOS, Symbian e Windows
Mobile. A proposta do sistema é permitir que usuários compartilhem em tempo real
informações de trânsito e tráfego, podendo evitar problemas comuns como acidentes,
engarrafamentos e blitz. [Waze 2010]
O funcionamento do sistema é bem simples. Quando o motorista entra no carro,
deverá ativar o aplicativo do Waze em seu smartphone e deixá-lo em funcionamento.
Enquanto dirige, o aplicativo envia pela Internet informações sobre a velocidade de seu
veículo e, também, coleta informações da Internet acerca da velocidade da via e de outras
subjacentes. Se a velocidade da via estiver baixa, o aplicativo marca a via em cores
vibrantes, sugerindo que outros usuários evitem a região.
Outra funcionalidade oferecida pela ferramenta é a comunicação de acidentes. Se o
motorista usuário do Waze estiver preso em um engarrafamento motivado por acidente,
ele pode, tirar uma foto do local e enviá-la através do programa. Os outros usuários da
rede, denominado “wazers”, receberão essa informação na hora e visualizarão a foto.
No Brasil, o serviço ainda é bem limitado, dada a pequena quantidade de usuários.
Como a base de dados é mantida por voluntários, ainda faltam mapas das ruas nas
principais cidades. O serviço provido pela Waze, entretanto, é capaz de deduzir possíveis
ruas, melhorar a geometria de ruas existentes e corrigir sentido de ruas.
2.3 WikiMapa
O WikiMapa é um mapa virtual alimentado de forma colaborativa por diversos
participantes, por meio do telefone celular ou Internet. [WikiMapa 2011]. O projeto
foi lançado em 2009 pelo Programa Rede Jovem, da ONG Comunitas, que atua em
comunidades de baixa renda oferecendo à juventude oportunidades de interação com as
novas tecnologias.
Com o WikiMapa é possível inserir informações sobre diferentes lugares de interesse
público (hospitais, escolas, comércios, praças, quadras esportivas, restaurantes, bares,
entre outros) em quaisquer lugar do Brasil e do mundo, como também consultar e editar
CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 8
comentários e referências sobre os locais já mapeados.
Esse mapeamento pode ser feito por qualquer pessoa que tenha cadastro no site do
WikiMapa e/ou o programa instalado em um celular com GPS, permitindo a inserção
das informações, coleta da localização e também compartilhamento das experiências em
blogs dentro do site do projeto.
O diferencial do projeto é o mapeamento de ruas e vielas de comunidades de baixa
renda, que até então não tem sido realizados pelos serviços de pesquisa e visualização de
mapas na Internet, além do mapeamento dessas comunidades, realizado pelos próprios
moradores.
Em sua fase piloto, cinco comunidades cariocas foram mapeadas: Complexo do
Alemão, Complexo da Maré, Cidade de Deus, Santa Marta e Pavão-Pavãozinho. Em cada
uma tem um jovem morador, responsável por identificar caminhos e locais de interesse,
iniciando a construção do mapa georeferenciado de sua comunidade, tornando sua cultura
e geografia conhecidas por qualquer usuário do WikiMapa.
O Programa Rede Jovem recebeu em 2010 quatro grandes prêmios devido à
experiência adquirida com o projeto Wikimapa e foi, ainda, a única iniciativa da América
Latina indicada como finalista ao prêmio Mobile Monday Peer Awards, na categoria
Bottom of the Pyramids.
2.4 Wikimapia
Wikimapia é um sistema de busca e mapeamento na Internet que utiliza imagens de
satélite do planeta Terra para identificar os locais mostrados, desde pequenos comércios
até cidades inteiras. O serviço se baseia nas imagens de satélite como as providas pelo
Google Maps. O sistema wiki é aplicado na forma de localização de lugares, pois qualquer
pessoa tem a permissão (sendo registrado) de inserir um local no mapa até mesmo editar
os locais já criados. [Wikimapia 2011]
O WikiMapia foi apresentado em 2006 pelos russos Alexandre Koriakine e
Evgeniy Saveliev. A aplicação dispõe de várias funcionalidadesde edição de mapas,
principalmente através do uso de polígonos que permitem definir precisamente a área do
local marcado - e ferramentas lineares, como estradas, ferrovias e rios.
No princípio, todos os usuários editavam anonimamente e não havia mecanismos de
monitoramento de usuários problemáticos ou vândalos. Em outubro de 2006, criou-se
o sistema de registro de usuários. Apesar disso, o registro não se tornou obrigatório
e ainda hoje é permitida a colaboração como usuário não registrado. Posteriormente,
adotaram-se diferentes níveis de usuários, permitindo que usuários mais experientes que
CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 9
sejam considerados confiáveis (chamados de usuários nível 2, ou usuários avançados)
ganhassem maiores capacidades, como proteger regiões ou banir vândalos.
A marcação dos locais envolve basicamente a definição da área ocupada, título,
descrição, endereço, categorias. Um link para artigos da Wikipédia descrevendo o local, é
também incentivado, havendo campos específicos para este fim. Os usuários podem ainda
adicionar fotos dos locais. Na descrição é permitida a inserção de links para páginas da
web e vídeos do Youtube, por exemplo. As categorias são usadas para que se possa filtrar
a visualização, permitindo se ver apenas os locais marcados com certa categoria.
Os locais marcados podem ser descritos em 101 idiomas diferentes, enquanto a
interface do usuário já foi traduzida para 56 idiomas.
2.5 Comob
Comob é um projeto de arte digital que explora o potencial do mapeamento
colaborativo com a tecnologia GPS. Comob foi desenvolvido como uma ferramenta
de pesquisa para explorar as relações sociais e espaciais entre as pessoas em
movimento [Comob 2011]. Ele atualmente é suportado nas plataformas suporta
aplicações para iPhone e Nokia que explora mapeamento colaborativo com a tecnologia
GPS. O sistema permite que os membros de um grupo compartilhado vejam a posição e
a movimentação do outro em tempo real em seus telefones móveis. O grupo é interligado
por uma linha que mostra a sua distribuição espacial relativa.
2.6 Avaliação das ferramentas pesquisadas no escopo do
trabalho proposto
Aplicações como estas que foram descritas nas seções anteriores revelam um aspecto
interessante sobre interações sociais no mundo digital: muitos estão dispostos a colaborar
em prol do bem comum. De fato, quanto mais bem alimentados forem os bancos de dados
de cada ferramenta, mais bem informados estarão seus usuários.
Entretanto, dois aspectos importantes podem ser observado nestas e em outras
propostas de sistemas de georeferenciamento colaborativo existentes. Um deles é o fato
de as aplicações estarem cada vez mais voltadas para o mercado de dispositivos móveis.
O outro é que a grande maioria das aplicações são desenvolvida em países de primeiro
mundo, onde as malhas viárias geralmente são bem cuidadas e a educação no trânsito é
realmente levada à sério.
CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 10
No Brasil, não são raras as falhas em vias públicas e regiões de perigo. Entenda-se por
regiões de perigo os trechos de rodovia que, embora possam estar livres de falhas na via,
são palco de constantes acidentes de trânsito (ex: trechos com baixa visibilidade, curvas
acentuadas e locais de constantes transgressões de motoristas).
O uso de navegação automotiva assitida por GPS não se faz necessário para os
usuários quando as rotas de chegada ao destino são conhecidas. Exemplos típicos destes
usuários são motoristas de ônibus de linhas interestaduais e caminhoneiros. Para estes
usuários, a existência de uma ferramenta que os lembre de pontos de perigo oferecem
grande utilidade em suas viagens de transporte de passageiros e cargas. As ferramentas
comerciais disponíveis, embora sejam capazes de orientar motoristas sobre rotas de
viagem, são inúteis para realizar alertas de falhas e pontos de perigo.
Neste sentido, a proposta do trabalho vem preencher esta lacuna, oferecendo um
sistema que pode ser usado pelas mais variadas categorias de motoristas para melhorar
sua proteção durante seus deslocamentos entre localidades. Ademais, a ferramenta não
deverá demandar a presença constante de um canal de comunicação para que mapas e
pontos de interesse sejam carregados para o dispositivo móvel. A atualização dos dados
poderá ser feita pelo usuário apenas nos locais onde canais de comunicação estiverem
disponíveis. Tal funcionalidade é útil, tanto no sentido de que nem sempre sinais de
rádio estão presentes nas vias de transporte estadual ou interestadual, quanto no sentido
da redução de custos de comunicação, geralmente associados à transmissão de dados por
operadoras de telefonia móvel.
Para desenvolver a proposta do trabalho, que é a marcação de pontos de perigo
de forma colaborativa, é necessário considerar a marcação redundante de pontos pelos
usuários e, inclusive, a remoção de pontos de perigo, por exemplo, em falhas já
consertadas em vias danificadas. Para isso, o uso de algoritmos de aglomeração de dados
que reduzam esta redundância são necessários e valiosos para oferecer ao usuário mapas
condensados. Estes mapas deverão representar as informações de alerta de forma a exigir
o mínimo de recursos de memória para o dispositivo móvel e evitar aborrecer o usuário
com repetições (o que poderia desestimular o uso da ferramenta). A seleção do algoritmo
de aglomeração apropriado será discutida no capítulo seguinte.
Capítulo 3
Aglomeração de dados
Os algoritmos de aglomeração englobam uma categoria de algoritmos que buscam
reunir objetos em grupos homogêneos [Frei 2006]. Eles representam uma das principais
etapas de processos de análise de dados, denominada análise de clusters [Jain et al. 1999].
Aglomeração de dados é um processo de particionamento de uma quantidade de dados
em grupos, ou clusters e, por natureza, operam de forma não supervisionada. Em outras
palavras, algoritmos de aglomeração não requerem conhecimento prévio dos grupos de
dados para poderem agir sobre um conjunto de dados. O critério usado para aglomerar
os grupos é geralmente alguma medida de similaridade ou distância. Como resultado do
processo, elementos originalmente separados são organizados em conjuntos denominados
de clusters. Um exemplo de medida de similaridade é a distância euclidiana.
Os algoritmos de aglomeração colocam no mesmo cluster elementos que têm mais
semelhança entre eles, maximizando então as semelhanças entre elementos dentro do
cluster. De forma concomitante, elementos de diferentes clusters apresentam menor
similaridade entre si, minimizando, então, as similaridades entre grupos. Assegurar estas
características é uma importante etapa do processo de análise de dados, tradicionamente
conhecida de análise de clusters [Jain et al. 1999].
Algoritmos de aglomeração podem ser divididos em dois grupos principais:
algoritmos hierárquicos e não hierárquicos [Jain et al. 1999, Larose 2005].
Os algoritmos hierárquicos criam uma hierarquia de clusters, que podem ser
representados em uma estrutura de árvore chamada dendrograma. Eles podem ser
divididos em mais duas categorias: algoritmos aglomerativos e divisivos.
O algoritmo hierárquico aglomerativo têm uma abordagem bottom-up, ou seja, o
processo inicialmente assume cada elemento de dado como um cluster diferente. Então,
o algoritmo vai juntando de forma iterativa dois clusters, que têm maior semelhança e
prosseguindo neste processo até que no final exista apenas um cluster ou até que outro
critério de parada seja alcançado, como o limite no número de clusters, por exemplo.
CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 12
Diferente do aglomerativo, o algoritmo divisivo apresenta abordagem top-down.
Começa o processo com apenas um cluster contendo todo o conjunto de dados. A
cada passo do algoritmo, esse cluster é dividido recursivamente seguindo métricas de
comparação, até que cada elemento represente o seu próprio cluster. Ao fim do processo,
ou o número de clusters é igual à quantidade de dados ou até algum outro critério de
parada ser alcançado,tal como o número máximo de clusters alcançado.
Os algoritmos não-hierárquicos (ou particionados) normalmente particionam os dados
uma única vez em um determinado número de clusters especifico, ao invés de uma
estrutura interligada, como o dendrograma produzido pela técnica hierárquica. Métodos
particionados têm vantagens em aplicações que envolvam grandes conjuntos de dados
para os quais a construção de um dendrograma é computacionalmente custosa. Esta
característica coloca a escolha de algoritmos particionados como candidatos naturais para
aplicação no problema proposto neste trabalho. Uma das limitações que geralmente
acompanha o uso de um algoritmo divisivo é a escolha do número de clusters
desejado.[Jain et al. 1999]. Entretanto, existem soluções elegantes que conseguem
contornar esta limitação.
Dos algoritmos particionados, talvez o mais conhecido seja o algoritmo k-means
[MacQueen 1967]. O algoritmo surgiu em 1967 e sua proposta é processar um conjunto
de dados n-dimensionais agrupando os elementos em uma quantidade pré-determinada de
grupos.
Dado um conjunto n-dimensional, o algoritmo k-means visa particionar o conjunto de
dados em k clusters. Ao final do processamento, o algoritmo encontrará k centros, um para
cada cluster. Cada centro é representado por um elemento n-dimensional ci, i = 1 . . .k,
que é o ponto médio (ou centro) de cada cluster. Os centros obtidos pelo algoritmo k-
means podem ser usados para fazer a classificação de um elemento de prova em busca do
melhor grupo em que esse possa ser inserido. O algoritmo k-means funciona conforme
os seguintes passos:
1 - Dado o valor de k, número de clusters a serem gerados, são escolhidos
aleatoriamente k elementos para serem os centros dos clusters, geralmente do
próprio conjunto de entrada.
2 - Para cada elemento do conjunto de dados:
2.1 - Encontrar o cluster que tem a maior similaridade com o elemento, com base
na medida de distância.
2.2 - Definir este elemento como pertencente ao respectivo cluster.
3 - Para cada cluster:
CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 13
3.1 - Atualizar os valores dos centros como sendo a média dos elementos
pertencentes ao cluster.
4 - Repetir os passos 2 e 3 até que se atinja a convergência, por exemplo, quando a
distância entre o centro em um passo anterior e o passo atual for menor que um
limiar pré-estabelecido.
Como exemplo de aplicação do algoritmo, considere um sistema de classificação de
tumores de pele. O sistema recebe informações do tipo curvatura, tamanho, textura e
cor e deve ser capaz de orientar seu usuário acerca da melhor classificação do tumor sub
judice. Entretanto, o sistema precisa ser treinado com exemplos previamente rotulados
por especialistas, descrevendo a benignidade ou malignidade dos exemplos.
O algoritmo k-means pode ser usado neste problema para processar os exemplos e
agrupá-los em dois conjuntos (benignos e malignos), gerando centros correspondentes
para cada um. Rotulados os centros com base nas informações fornecidas pelos
especialistas, estes podem ser usados para classificar uma nova amostra, usando a mesma
medida de distância escolhida para o treinamento.
Embora seja aplicável a diversos tipos de problemas de aglomeração, o algoritmo
k-means possui uma limitação que o impede de ser usado no problema proposto. O
número de centros deve ser previamente definido. Sendo assim, alternativas que permitam
a aglomeração de pontos sem a prévia fixação da quantidade de centros precisam ser
consideradas.
Dos algoritmos pesquisados, um deles chama a atenção pela forma como realiza
o processo de aglomeração. A criação do centro se dá pela fixação do seu limite de
diâmetro, que é justamente o que se busca para o caso do sistema de alerta proposto. O
algoritmo é denominado QT clustering e será descrito na seção a seguir, bem como as
justificativas que embasam sua escolha.
3.1 QT clustering
O algoritmo de aglomeração Quality Threshold clustering (ou QT clustering) foi
desenvolvido por Heyer, Kruglyak e Yooseph para aglomeração genes de DNA [Heyer
et al. 1999].
O algoritmo requer um maior custo computacional que o algoritmo k-means, possui
custo exponencial, porém não exige a definição do número de clusters a priori, como no
k-means. Execuções distintas do QT clustering fornecem sempre o mesmo resultado.
CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 14
Ao invés do número de clusters, esse algoritmo recebe como entrada um valor limite
para o diâmetro do cluster. Sendo assim, o foco desse algoritmo é encontrar clusters cujos
diâmetros não ultrapassem o limiar fornecido.
O algoritmo segue os seguintes procedimentos:
1. O primeiro aglomerado candidato é formado começando pelo primeiro elemento
amostrado do conjunto de entradas;
2. Os demais elementos do conjunto são adicionados iterativamente, dado que cada
elemento escolhido minimiza o aumento do diâmetro do aglomerado candidato. O
processo continua até que o diâmetro do aglomerado candidato não ultrapasse o
limiar;
3. Um segundo aglomerado candidato é formado pelo segundo elemento do conjunto
e o mesmo processo de formação descrito na etapa anterior é repetido para todos os
dados do conjunto de entrada;
4. O processo é repetido para todos os elementos do conjunto, de sorte que o número
de aglomerados candidatos seja igual ao número de elementos no conjunto de
entrada;
5. O aglomerado candidato com maior número de dados é selecionado como um
aglomerado titular e os dados contidos nele são removidos dos outros aglomerados
candidatos;
6. O processo de seleção de titulares é repetido para todos os aglomerados candidatos
até o último aglomerado;
7. O centro de cada aglomerado é assumido como sendo posição do elemento que o
originou.
Um possível critério de parada é quando o cluster restante contiver menos que um
número de elementos especificado. O Algoritmo 1 mostra o funcionamento do QT
clustering.
A idéia do algoritmo, embora simples, possui aplicação direta no problema proposto.
Considere a situação onde o sistema de alerta precise avisar um motorista de um ponto de
perigo que se encontra adiante no curso da via. Emitido o alerta, o motorista deveria ser
capaz de reagir ao alerta, iniciar o processo de frenagem e parar, antes de atingir o ponto
de perigo, para se por em segurança.
A distância percorrida entre o início da reação e a parada do veículo é denominada
distância de parada e, usando cálculos simples, pode ser estimada conforme a velocidade
do veículo e tipo de pista. Para um veículo se deslocando a 110 km/h em pista seca,
a distância de parada pode ser estimada em aproximadamente 150m [Seguras 2011].
CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 15
Algoritmo 1 QT clustering(G,d). Recebe como dados de entrada o conjunto G e um
diâmetro d, e retorna um conjunto de clusters limitados em tamanho pelo diâmetro
fornecido. Fonte: [Heyer et al. 1999]
1: if |G| ≤ 0 then
2: return G
3: else
4: for all i ∈ G do
5: f lag← T RUE
6: Ai←{i}
7: while ( f lag = T RUE)&(Ai 6= G) do
8: Encontre j ∈ (G−Ai) em que o diâmetro de (Ai∪{ j}) é mínimo
9: if diâmetro de (Ai∪{ j})> d then
10: f lag← FALSE
11: else
12: Ai← Ai∪{ j}
13: end if
14: end while
15: end for
16: end if
17: Identifique o conjunto C ∈ {A1,A2, ...,A|G|} com a máxima cardinalidade
18: return C
19: QTclustering(G−C,d)
Criando clusters, por exemplo, com limite de diâmetro de 300m, seria possível marcar
pontos de perigo representativos de aglomerados que estejam a aproximadamente 150m
de distância de um motorista posicionado no limite do aglomerado. Assim, motoristas
se deslocando a 110 km/h se avisados quando estiverem a 150m de distância do ponto
representativo, poderiam reduzir a velocidade com segurança até atingir o obstáculo.
Embora possa ser estimado um valor mínimo para essa distância de alerta, esta
grandeza poderá também ser definida pelo próprio usuário da ferramenta, através do
estabelecimento de parâmetros em uma interface de usuário.
Estudos heurísticos podem ser realizados usando, por exemplo, opiniões e dados
coletados dos próprios usuários da ferramenta paradeterminar um diâmetro adequado
para os centros dos aglomerados e distância padrão para alertas, nem tão pequena que
irrite os motoristas com alertas excessivos, nem tão grande que instrua o sistema a realizar
alertas demasiadamente antecipados.
Capítulo 4
Trabalho proposto
O presente trabalho propõe o desenvolvimento de um Sistema Informação Geográfica
(SIG) colaborativo capaz de agregar tecnologias muito difundidas e de fácil acesso, como
as ferramentas localização geográfica, cartografia digital e interatividade com a Internet,
usando smartphones.
São agregados um sistema de geração de alertas, através de um dispositivo móvel,
que avisa da proximidade de pontos de perigo nas vias de transporte, e um sistema de
aglomeração de dados para coletar e processar informações dos seus diversos usuários.
Para funcionar, o sistema precisa ter a priori as coordenadas geográficas desses pontos
cadastradas em uma base de informações. Estas coordenadas deverão ser fornecidas pelos
usuários enquanto estiverem trafegando nas vias. Os pontos deverão ser enviados a um
servidor que irá processá-los e gerar uma lista representativa de pontos de perigo. Uma
vez recuperada esta lista, o usuário poderá utilizá-la durante a navegação em conjunto
com a lista dos pontos por ele marcados.
4.1 Funcionamento do sistema
Uma visão geral do sistema proposto é apresentada na Figura 4.1. Nesta figura, cada
número identifica uma fase do processo de armazenamento, tratamento e recuperação de
informações do servidor SIG. O processo de construção da base de informações tem início
pela iniciativa dos seus usuários, que alimentam o sistema marcando nos dispositivos
móveis os pontos de perigo e os enviam ao servidor SIG(1). O servidor armazena os pontos
fornecidos em um banco de dados(2), relacionando as marcações realizadas pelos usuários.
Os pontos presentes na base de dados de usuários são enviados para processamento e
geração periódica dos aglomerados através do algoritmo QT clustering(3). O resultado
do processamento é armazenado no banco de dados(4) para consultas(5) e atualização de
pontos de perigo (centros dos aglomerados) nos clientes móveis(6). Os dados presentes
CAPÍTULO 4. TRABALHO PROPOSTO 17
no servidor de banco de dados também podem ser acessíveis de forma integrada com
clientes desktop(6), no caso da necessidade de visualização ou manipulação dos pontos
superpostos com mapas digitais em um computador.
Banco de 
dados
1
6
4
3
5
EJEC
T
DVD-
RWDVD-
RW
USB
SATA
PH
O
N
E
M
IC
LI
N
E-
IN
AUDI
O
POW
ER
CARD
READ
ER
LCD-Pro
SELECT
MENU
- +
NumLock
CapsLock
ScrollLock
NumLock
7
4
1
/
8
5
2
*
9
6
3
0
-
+ScrollLock
ScrnPrin
t
SysRq
Pause Break
Home
End
PageDown
PageUp
Insert
Delete
Enter
End
Home
PgUp
PgDn
Del.
Ins
F1 F2
F3 F4
F5 F6
F7 F8
F9 F1
0 F11
F12
Esc
1 2
3 4
5 6
7 8
9 0(
)
*
&
^
%
$
#
@
!
`~
-_ =
+ \|
Ctrl
Ctrl
Alt
A S
D F
G H
J K
L
CapsLock
;: '
"
Z X
C V
B N
M
Shift
Shift
/?.>,< Alt Gr
Q W
E R
T Y
U I
O P
[{
]}
Tab
QT clustering/
Processamento
auxiliar
Servidor SIG
Cliente
desktop
Cliente
móvel
Internet
2 4
Figura 4.1: Arquitetura do sistema proposto para marcação e aglomeração de pontos.
4.2 Marcação de pontos
Em se tratando de um sistema de alerta colaborativo, o usuário deve ser capaz de
marcar de forma simples e rápida a presença de algum ponto de perigo na via em
que estiver trafegando. A marcação deverá ser feita no dispositivo móvel através de
CAPÍTULO 4. TRABALHO PROPOSTO 18
botões presentes na interface do aplicativo. Da mesma forma que a marcação de pontos
candidatos a inclusão na base de informações é permitida, também será permitida a
marcação de pontos candidatos a remoção da base de dados. Esta situação poderá ocorrer,
por exemplo, para falhas na via marcadas pelos usuários e já foram reparadas.
A interface de usuário proposta para o sistema é mostrada na Figura 4.2.
TRECHO
PERIGOSO
FALHA
NA VIA
ZONA
LIVRE
(10:30h) GPS ok! Iniciando navegação
(10:40h) Inserida falha na via
(10:42h) Trecho perigoso a 200m
(10:53h) Zona livre marcada
(10:55h) Inserida falha na via
(14:00h) Base de dados sincronizada
Figura 4.2: Interface de usuário para dispositivo móvel.
Na tela da interface do usuário são propostas quatro regiões principais: uma região
superior para apresentação de informações (distância para pontos de perigo, iterações
com o aplicativo, etc) e três regiões sensíveis ao toque, sendo dois botões centrais para
marcação de pontos de perigo e um botão inferior para a marcação de zonas livres.
Os pontos de perigo serão classificados em duas categorias: falhas na via
(caracterizadas pela associação a buracos e ondulações, por exemplo) e zonas de perigo
(associadas a curvas fechadas e pontos de ultrapassagem perigosos, por exemplo). Cada
categoria poderá gerar um alerta diferenciado para o usuário, bem como prover às
entidades govenamentais dados para melhorarem a sinalização e manuntenção das vias,
dadas as opiniões dos próprios motoristas acerca do que consideram trechos perigosos.
A marcação de zonas livre, associada à remoção de pontos, é feita pelo acionamento
do botão zona livre.
CAPÍTULO 4. TRABALHO PROPOSTO 19
A interface oferece alertas sonoros para não desviar a atenção visual do motorista
enquanto percorre o curso da rodovia. Com isso, a ferramenta desenvolvida não oferece
insumos que motivem os motoristas a desobedecer a legislação de trânsito, desviando o
foco da atenção. Dessa forma, a interação entre usuário e ferramenta funciona de forma
semelhante à do navegador GPS convencional, onde este vai ditando as informações ao
motorista.
A alimentação da plataforma móvel com as marcações se dá quando o usuário
acionar as regiões correspondentes no seu smartphone. Entenda-se como usuário, durante
procedimento de marcação, aquele que vai manipular a plataforma móvel (que pode ser
um dos passageiros que acompanham o motorista durante a viagem). Para cada ponto
marcado são armazenadas as suas coordenadas geográficas, latitude e longitude, data e
hora da marcação, bem como o tipo de ponto selecionado (falhas na via ou zonas de
perigo). O envio dos pontos da plataforma móvel para o servidor SIG não é imediata.
Parte-se do princípio que, em zonas rurais, normalmente sinais de rádio que permitiriam
conexões de dados estão indisponíveis. Portanto, os pontos podem ser enviados para o
servidor SIG para futuro processamento através de um processo de sincronização, quando
uma conexão com a Internet estiver disponível.
O envio das informações para o servidor SIG é feito em lote, quando então as
informações dos novos pontos presentes no smartphone são transferidos. Quando os
dados chegam ao servidor, estes são submetidos a técnicas de processamento inteligente
para escolher os pontos de alerta.
Pressupõe-se que a marcação do ponto de perigo na via não deva ser exatamente a
mesma para todos os motoristas. Quando um usuário passa por um ponto de perigo e
realiza a marcação no seu aparelho móvel, esta poderá ocorrer em pontos aproximados ao
ponto de perigo real, devido ao retardo ou antecipação associados à ação do usuário, ou
precisão do receptor GPS do dispositivo móvel. A falha pode ser marcada, portanto,
antes ou depois de o veículo passar pelo ponto. Além disso, vários usuários podem
marcar a mesma falha mais de uma vez, resultando em redundância de informações em
torno dos pontos de perigo. Sendo assim, ocorre a necessidade de consolidar estes vários
pontos marcados e selecionar um único ponto de perigo associado às marcações sugeridas.
Exemplos de nuvens de pontos que podem ser marcadas no processo colaborativo
são mostradas na Figura 4.3. Nesta figura, os pontos marcados pelos usuários são
representados com uma cruz e o ponto representativo de uma aglomerado gerado após
tratamento por técnicas inteligentes é destacado com um círculo.
CAPÍTULO 4. TRABALHO PROPOSTO 20
Curso da viaPontos de perigo
Ponto 
representativo
Cursos das vias
Trechos perigosos
Falhas nas vias
Figura 4.3: Exemplo denuvens formada pela marcação de vários motoristas com seu
ponto representativo e os diferentes tipos de nuvens com pontos de perigo que podem ser
marcados nos cursos das vias.
4.3 Processamentos dos dados
É no contexto da Figura 4.3 que o processamento dos pontos colhidos pelos usuários
do aplicativo torna-se necessário para produzir apenas pontos de perigo significativos.
Para problemas dessa natureza, algoritmos de aglomeração são candidatos naturais para
uso no sistema de marcações. A geração dos pontos representativos dos aglomerados
de marcações fornecidas pelos usuários deve ser feita de modo a remover as possíveis
redundâncias que porventura sejam fornecidas por diferentes usuários.
No caso desse trabalho, demanda-se um algoritmo de aglomeração que não exija a
determinação a priori da quantidade de aglomerados a serem formados, visto que não
existe a possibilidade de saber de antemão quantos pontos de perigo poderão existir em
uma via.
CAPÍTULO 4. TRABALHO PROPOSTO 21
Os aglomerados de pontos deverão ser formados nas proximidades dos pontos de
perigo, conforme as marcações dos usuários, devendo esta condição se repetir para cada
ponto de perigo real (ver Figura 4.3). Acredita-se que o diâmetro dessas nuvens tenda a
ser regular, devendo assumir forma geralmente elíptica. Tais conjecturas são baseadas no
tempo de observação e reação média dos usuários, promovendo a forma do eixo maior da
elipse, e na precisão do GPS, promovendo a expansão do eixo menor.
Diante das peculiaridades do sistema proposto, o algoritmo QT clustering apresentado
na seção 3.1 foi escolhido como candidato à criação dos centros que marcam os pontos de
perigo. O servidor SIG, em atividades escalonadas periodicamente, determina os centros
dos aglomerados via QT clustering, e torna estes centros disponíveis aos usuários para
atualização das bases de informação móveis.
O uso do algoritmo de aglomeração QT clustering possibilita amenizar a redundância
de marcações, oferecendo para um usuário apenas os pontos mais significativos de perigo,
de modo a orientá-lo sem excesso de informações. Neste trabalho, foi escolhida uma
distância de 300 metros como diâmetro máximo dos aglomerados, assumindo que, para
este diâmetro, é oferecido um limite mínimo para alertar o motorista com segurança.
4.4 Remoção de pontos
Para os aglomerados formados em torno dos ponto de perigo, centros correspondentes
serão determinados pelo próprio algoritmo de aglomeração. O processo de criação ou
atualização destes pontos de perigo deve prever, também, a situação onde a existência
de determinados pontos de perigo não seja mais necessária. Um exemplo típico dessa
situação é propiciada pelo reparo de um buraco na rodovia que fôra marcado como
ponto de perigo. Em casos como esses, os usuários da ferramenta poderão realizar uma
marcação do tipo zona livre (ver Figura 4.2), indicando a inexistência de fatores capazes
de gerar perigos na região marcada.
Os pontos marcados como zona livre também participam do processo de
aglomeração, influindo negativamente na inclusão ou manutenção de centros novos
ou existentes, respectivamente. O processamento desses pontos pelo algoritmo de
aglomeração leva em conta informações tais como o momento em que os pontos foram
inseridos na base de dados de pontos de perigo e a quantidade de marcações do tipo
zona livre. Os pontos marcados como zona livre não provocam a criação de novos
aglomerados. Eles servem apenas para decidir se os aglomerados dos quais participam
são ou não candidatos à remoção.
Para decidir a remoção de um aglomerado da base de dados foi utilizada uma
CAPÍTULO 4. TRABALHO PROPOSTO 22
heurística simples com base em um limiar K preestabelecido. Calcula-se a idade média
dos pontos de perigo mais recentes no aglomerado e dos pontos de zona livre mais
recentes no mesmo aglomerado e compara-se as duas médias. Caso a média de idade
dos pontos de zona livre supere a média de idades dos pontos de perigo e o número de
pontos de zona livre atinja o limiar K, todo o aglomerado é removido da base de dados.
No protótipo desenvolvido, escolheu-se um limiar K = 3 como parâmetro para controlar
a remoção de aglomerados.
A heurística proposta foi escolhida com base em algumas suposições acerca do uso
da plataforma móvel. Caso um usuário receba um alerta de ponto de perigo e o ponto
realmente exista, dificilmente ele marcará novamente este ponto na ferramenta como
sendo ponto de perigo, uma vez que foi avisado corretamente da presença do ponto.
Neste caso, as idades das marcações dos pontos de perigo tendem a ser mais antigas que
as idades das marcações de zona livre. Caso um usuário receba um alerta de ponto de
perigo e o ponto não exista, a realimentação natural será marcar aquele ponto como zona
livre, para evitar futuros alertas. O limiar para remoção de aglomerados mencionado no
parágrafo anterior visa impedir a remoção prematura de pontos de perigo, requerendo que
alguns usuários colaborem na confirmação da zona livre marcada. É importante observar
que o mesmo limiar inexiste para a marcação de um ponto de perigo, justamente para que
prevaleça o zelo na marcação de possíveis perigos presentes nas vias.
4.5 Alertas de perigo
O sistema de alerta para o dispositivo móvel oferece alerta sonoros, informando ao
motorista da proximidade de algum ponto de perigo na via em que ele estiver trafegando.
Para chamar atenção do motorista, o alerta sonoro pode sintetizar fala para informar
ao motorista a distância para o ponto de perigo e o tipo de perigo que está eminente.
A plataforma de testes na qual o protótipo da ferramenta foi criado, a plataforma
Android(http://www.android.com), já dispõe deste recurso para o desenvolvedor.
Para gerar os alertas, o programa em execução na plataforma móvel deverá
constantemente recuperar as coordenadas geográficas locais via GPS, calcular a distância
do usuário para o ponto de perigo mais próximo, e avisar o usuário conforme os alertas
programados na interface de usuário. Embora os aglomerados sejam gerados com
diâmetro fixo, a distância mínima de alerta poderá ser definida pelo próprio usuário.
CAPÍTULO 4. TRABALHO PROPOSTO 23
4.6 Interface desktop
A visualização das posições dos pontos pode ser feita na própria plataforma móvel
utilizando os recursos de apresentação de mapas disponibilizados pela Google. Apesar
desta comodidade, uma interface desktop é também disponibilizada para possibilitar a
exibição dos pontos de perigos juntamente com a ferramenta Google Maps. A interface
desktop é capaz de oferecer uma interação visual mais rica e poderá servir como fonte
de insumos para os órgãos responsáveis pela conservação e manutenção das vias de
transporte realizarem procedimentos de recuperação ou melhor sinalização das vias.
Cruzando informações fornecidas pelas marcações geradas pela ferramenta proposta com
informações do próprio DNIT, medidas colaborativas entre cidadãos e o Estado podem ser
tomadas para melhorar a qualidade das vias públicas e diminuir a quantidade de acidentes.
A exibição dos centros gerados pelo algoritmo pode ser feita diretamente através
de uma página web pela integração com a ferramenta Google Maps. Os recursos de
desenvolvimento disponibilizados pela Google permite que os pontos seja exibidos na
forma de uma camada (layer) integrada ao próprio navegador. Com isso, o usuário
poderá visualizar a representação dos pontos de perigo juntamente com fotos de satélite
contemplando a região onde são situados. O protótipo desenvolvido para este trabalho é
ilustrado na Figura 4.4.
Figura 4.4: Protótipo da interface desktop para visualização de centros usando os recursos
do Google Maps.
CAPÍTULO 4. TRABALHO PROPOSTO 24
4.7 Sincronização e expurgo de dados
A sincronização entre as marcações presentes na plataforma e as marcações fornecidas
a esta pelo servidor SIG é outro aspecto importante que precisou ser considerado. Ao
enviar ou receber informações, a ferramenta presente no dispositivo móvel precisa estar
alerta para não enviar dados repetidos oudesnecessários ao servidor SIG. Da mesma
forma, precisa ser capaz de evitar possíveis redundâncias oriundas dos dados recebidos
deste servidor.
Visando contornar tais problemas, estratégias de rotulação e processamento adicionais
foram também incorporadas à ferramenta móvel. Para fins de sincronização, os pontos de
perigo receberam os seguintes rótulos adicionais (além dos rótulos de trecho perigoso e
falha na via):
Novo: Ponto marcado pelo usuário, mas que ainda não foi comunicado ao servidor SIG.
Sincronizado: Ponto marcado pelo usuário e que já foi comunicado ao servidor SIG.
Centro: Ponto recebido pelo servidor SIG, resultado do processamento dos aglomerados
via algoritmo QT clustering.
Na interface da ferramenta móvel, são providas funcionalidades para permitir que o
usuário envie os pontos para o servidor remoto. Nesta etapa, os pontos dotados do rótulo
Novo têm seus rótulos substituídos por Sincronizado e são então enviados ao servidor
SIG, evitando assim o envio redundante de marcações ao servidor. A recuperação dos
centros gerados também é feita por intervenção do usuário na interface da ferramenta
móvel. Durante o processo, os pontos locais marcados como centro são substituídos pelos
novos centros recuperados.
O processo de marcação de zonas livres também sofre processamento adicional na
ferramenta móvel e possui processo de sincronização ligeiramente diferente dos pontos
de perigo. Cada marcação de zona livre realizada pelo usuário inicia duas ações a serem
tomadas. A primeira ação, realizada imediatamente, consiste em marcar para remoção
na base de dados local todos os pontos de perigo marcados dentro de um raio igual à
metade do diâmetro estipulado para o tamanho máximo dos aglomerados. A segunda
ação consiste em comunicar ao servidor SIG, durante a etapa de recuperação de centros,
os pontos marcados como zona livre. Uma vez enviados, eles são então removidos da
base de dados local, posto que sua presença torna-se inútil na ferramenta.
CAPÍTULO 4. TRABALHO PROPOSTO 25
4.8 Modelo do sistema
O sistema desenvolvido é composto principalmente por três módulos, são eles o
MÓVEL, o WEB e o CORE, como ilustrado na Figura 4.5.
Figura 4.5: Módulos do sistema
Cada módulo do sistema utiliza tecnologias adequadas as suas especificidades. A
Figura 4.6 mostra mais detalhes sobre cada um dos módulos, especificando as plataformas
utilizadas para desenvolvimento de cada um deles.
O módulo móvel foi desenvolvido utilizando a linguagem de programação Java,
dadas as exigências da plataforma/sistema operacional Android. Para o armazenamento
dos dados no módulo foi utilizado uma base de dados SQLite, provida pela plataforma
Android.
Na Figura 4.7 é ilustrado o diagrama de classes utilizado no módulo móvel. Ele se
difere do diagrama de classes dos outro módulos pela necessidade de armazenamento
dos senos e cossenos da latitude e longitude da coordenada geográfica para agilizar
o processamento, visto que o SQLite não provê funções nativas para executar sobre
CAPÍTULO 4. TRABALHO PROPOSTO 26
Figura 4.6: Módulos/Plataformas do sistema
comandos SQL, como também da classe Mapa que é utilizada para agrupar os conjuntos
de pontos marcados pelo usuário, permitindo assim ele escolher diferentes conjuntos,
mapas, e gerenciá-los.
O módulo WEB foi implementado principalmente em PHP. A integração com o
módulo móvel foi feita através de um web service utilizando o protocolo JSON-RPC. O
JSON-RPC é um protocolo que foi projetado para ser bastante simple e que utiliza menos
tráfego de dados do que os web services que utilizam XML. Um web service assim se
mostra adequado para a tranferêcia dos dados entre os módulos móvel e web, pois dessa
utiliza menos o plano de dados do smartphone.
O módelo de comunicação dos dados entre os módulos móvel e web via web service
é:
1 −−> { " method " : "NOME DA FUNÇÃO" , " params " : [ TIPO DE PONTO, STATUS DO
PONTO, LATITUDE , LONGITUDE] , " i d " : n u l l }
2 <−− { " r e s u l t " : "OK/ FAIL " , " e r r o r " : n u l l , " i d " : n u l l }
CAPÍTULO 4. TRABALHO PROPOSTO 27
Figura 4.7: Diagrama de classes do módulo móvel
Um exemplo de comunicação entre o módulo móvel e web:
1 −−> { " method " : " add_pon to " , " params " : [ 1 , 1 , 37 .422006 , −122.084095] ,
" i d " : n u l l }
2 <−− { " r e s u l t " : "OK" , " e r r o r " : n u l l , " i d " : n u l l }
Para a interação com usuário no módulo WEB além de PHP, foi utilizado também uma
biblioteca JavaScript disponibilizada pela plataforma Google Maps para visualização dos
mapas.
No módulo CORE se concentram a parte de acesso aos dados e também os
procedimentos para o processamento numérico do algoritmo QT clustering que foi
desenvolvido utilizando a linguagem C++, que é justificado pelo alto custo computacional
exigido pelo algoritmo de aglomeração. Além disso, esta linguagem permite que versões
futuras do algoritmo que executem em arquiteturas paralelas sejam mais facilmente
acopladas ao módulo servidor.
Por último, temos a base principal de dados, que foi projetada em cima do SGBD
CAPÍTULO 4. TRABALHO PROPOSTO 28
MySQL.
Capítulo 5
Resultados
Para testar a ferramenta proposta foram feitos experimentos utilizando um smartphone
Samsung Galaxy S II executando sistema operacional Android 4.0.3 (ice cream
sandwich). Nos experimentos realizados os usuários foram instruídos a marcarem
os pontos de perigo que lhes conviesse, sendo apenas informados o que poderia ser
caracterizado como trechos perigosos e falhas na via.
O primeiro experimento visava contemplar uma zona urbana. Vários deslocamentos
foram realizados na Avenida Senador Salgado Filho, na cidade de Natal, no Estado do
Grande do Norte, e foi pedido a diferentes usuários que marcassem todos as posições
dos 9 semáforos presentes em um trecho de 3km escolhido nesta avenida como sendo
do tipo trecho perigoso. Nesse experimento, 6 usuários marcaram um total de 61
pontos. Os pontos marcados pelos usuários são ilustrados na Figura 5.1a. Com a base
de dados abastecida com os pontos recolhidos da marcação, o algoritmo QT clustering
foi executado utilizando limite de diâmetro de 300 metros. Os centros gerados são
apresentados na Figura 5.1b. Para este experimento, constatou-se a formação de 10
centros, 9 dos quais marcando corretamente a posição real dos semáforos para fins de
navegação automotiva.
O segundo experimento visava contemplar uma zona rural. Para isso, 2 usuários
diferentes foram instruídos a marcar na ferramenta todos os ponto de perigo numa rodovia
de 15 km situada entre o centro da cidade de Nísia Floresta até a praia de Barra de
Tabatinga, no Estado do Rio Grande do Norte. Um dos usuários dirigiu-se da cidade
à praia e o outro da praia à cidade.
Realizadas as marcações em ambos os sentidos, os dados gerados pelos usuários
foram processados, gerando os centros para as zonas de perigo marcadas. De posse
destes centros, foi pedido a cada usuário que percorresse o mesmo trecho no sentido
contrário ao que haviam percorrido e que verificasse se a ferramenta gerava corretamente
os alertas. O resultado constatado pelos usuários foi o de que todos os alertas foram
CAPÍTULO 5. RESULTADOS 30
gerados corretamente, e contemplaram praticamente a totalidade de falhas na via que
haviam encontrado.
Um dos experimentos no trecho que liga o centro de Nísia Floresta à praia de Barra
de Tabatinga foi realizado à noite, para testar uma situação onde o usuário desconhece a
via onde trafega e a visibilidade é curta. A experiência relatada pelo usuário foi de que a
ferramenta tornou-se bastante útil no sentido de que pôde ficar mais alerta na proximidade
de pontos de perigo desconhecidos. Os alertas o ajudaram na navegação, permitindo
que tomasse decisões seguras com antecedência, sem ser supreendido por um obstáculo
no curso da rodovia. Uma das atitudes mais presenciadas durante o experimento foi a
redução de velocidade do motorista ao ser alertado.
Os 68 pontos marcados pelos dois usuários na zona rural e os 31 centros gerados
pelo QT clustering sãoilustrados nos mapas das Figuras 5.2a e 5.2b, respectivamente.
Observando-se os mapas, pode-se questionar o fato de os pontos encontrarem-se
ligeiramente desalinhados das marcações das rodovias fornecidas pelo Google Maps.
Entretanto, a inconsistência encontra-se no mapa gerado pela Google e não na posição dos
pontos marcados pelo usuários. Embora estas inconsistências possam ser inconvenientes,
a Google vem se esforçando para melhorar seus serviços de mapas e, para o motorista
usuário da ferramenta, o mais importante é ser alertado da presença de pontos de perigo.
Outro experimento foi realizado para marcar pontos de falha na via nas Avendidas
Salgado Filho e Hermes da Fonseca, em Natal, RN. A marcação foi realizada no dia
27 de setembro de 2012 com o objetivo de marcar as principais falhas da via em um
precurso de 5.400 metros que abrangem estas duas avenidas ao todo. Na época da escrita
desse documento, a sociedade natalense presenciou sérios problemas de desgaste nestas
duas vias (entre outras várias) e, neste experimento, procurou-se demonstrar a viabilidade
da ferramenta para mostrar (em números) problemas encontrados, servindo assim como
instrumento de cobrança de ações públicas. Foram marcados, nessa época, 38 pontos de
falha, que são ilustrados no mapa da Figura 5.3. Para esta situação, os centros gerados
poderiam ser usados como insumo logístico para os órgãos responsáveis determinarem
regiões de atuação.
CAPÍTULO 5. RESULTADOS 31
(a) Pontos marcados
(b) Centros gerados
Figura 5.1: Experimento em zona urbana.
CAPÍTULO 5. RESULTADOS 32
(a) Pontos marcados
(b) Centros gerados
Figura 5.2: Experimento em zona rural.
CAPÍTULO 5. RESULTADOS 33
(a) Pontos marcados
(b) Centros gerados
Figura 5.3: Experimento em zona urbana - marcação de falhas nas Avenidas Salgado
Filho e Hermes da Fonseca, Natal-RN
Capítulo 6
Considerações finais
O presente trabalho propôs a criação de uma ferramenta de geração de alertas para
proteção de motoristas em vias públicas. Os alertas gerados visam indicar ao motorista
pontos caracterizados como falhas e trechos perigosos na via. A marcação dos pontos
pode ser feita pelos usuários da ferramenta de forma colaborativa, sendo a escolha dos
melhores pontos candidatos realizada por um algoritmo de aglomeração.
O processo de aglomeração de pontos e escolha de centros para os aglomerados foi
realizada utilizando o algoritmo QT clustering, haja vista sua capacidade de gerar centros
com base na limitação de um diâmetro máximo para os centros. A imposição do limite
de diâmetro se ajusta perfeitamente à proposta da geração dos alertas, uma vez que é
necessário alertar os motoristas a uma distância razoável do perigo iminente.
Os experimentos realizados mostraram que a ferramenta embarcada em uma
plataforma móvel foi considerada satisfatória para os usuários em zonas urbanas e,
principalmente, em zonas rurais, atendendo às necessidades de cada situação. Uma
das principais utilidades constatadas para ferramenta são os alertas gerados durante o
período noturno. Verificou-se que, durante a noite, os alertas gerados pela plataforma
móvel tornaram o usuário mais atento e precavido na presença de pontos de perigo
desconhecidos.
Dada a carência de uma ferramenta de proteção a motoristas moldada nos aspectos
discutidos ao longo do texto, é razoável considerar que a ferramenta desenvolvida
pode ser aplicada à realidade nacional, onde boa parte das vias públicas de transporte,
principalmente de longa distância, acumulam regiões de perigo.
Alguns aspectos acerca do gerenciamento dos dados fornecidos pelos usuários e da
geração de aglomerados são objetos de estudo futuro:
• O diâmetro do aglomerado diferente do estabelecido em 300 metros pode ser
testado na medida em que mais pessoas puderem ter acesso à plataforma.
CAPÍTULO 6. CONSIDERAÇÕES FINAIS 35
• O valor do limiar K = 3 que regula a influência de pontos do tipo zona livre pode
ser melhor avaliado.
• Mecanismos que avaliem a qualidade dos pontos baseados na reputação dos
usuários da plataforma podem ser inseridos.
• Inserir na ferramenta móvel a possibilidade de usar mapas com centros gerados por
outros usuários.
• Estratégias baseadas no compartilhamento de mapas via Google Maps estão sendo
elaboradas, pois podem ser capazes de dispensar mecanismos mais complexos de
autenticação de usuários e prevenir eventuais envenenamentos das bases de dados
por usuários maliciosos.
• Mecanismos de geração de aglomerados apenas entre grupos de usuários também
podem ser considerados no futuro, visando a aplicação da ferramenta em
comunidades fechadas (por exemplo, usuários de empresas transportadoras de
cargas).
Por fim, acredita-se que a base de dados do sistema possa servir de insumo inclusive
para integração em sistemas de navegação que permitam traçados de rotas mais seguras,
evitando assim possíveis danos ao motorista e ao seu veículo.
Capítulo 7
Agradecimentos
O autor agradece à CAPES pelo suporte financeiro dispensado e ao Núcleo de
Estatísticas da PRF, pelos dados estatísticos que ajudaram a fundamentar este trabalho.
Referências Bibliográficas
Clarke, Keith C. (1986), ‘Advances in geographic information systems’, Computers,
Environment and Urban Systems 10(3-4), Pages 175–184.
Comob (2011), Comob’s homepage, Página na internet, acessado em junho de 2011.
URL: http://www.comob.org.uk/
DNIT (2011), ‘Estatísticas de acidentes’, Disponível em: <http://www.dnit.gov.br/
rodovias/operacoes-rodoviarias/estatisticas-de-acidentes >. Acesso
em julho de 2011.
Foursquare (2011), Foursquare’s homepage, Página na internet, acessado em junho de
2011.
URL: https://foursquare.com
Frei, Fernando (2006), Introdução à análise de agrupamentos: teoria e prátic, Editora
UNESP, São Paulo.
Heyer, Laurie J., Semyon Kruglyak & Shibu Yooseph (1999), ‘Exploring expression
data:identification and analysis of coexpressed genes’, Genome Research 9, 1106–
1115.
Jain, Anil Kumar, M Narasimha Murty & Patrick Joseph Flynn (1999), ‘Data clustering:
A review’, Acm Computing Surveys 31, 264–323.
Larose, Daniel T. (2005), DISCOVERING KNOWLEDGE IN DATA : An Introduction to
Data Mining, John Wiley and Sons, Hoboken.
MacQueen, J. B. (1967), Some methods for classification and analysis of multivariate
observations, em L. M. L.Cam & J.Neyman, eds., ‘Proc. of the fifth Berkeley
Symposium on Mathematical Statistics and Probability’, Vol. 1, University of
California Press, pp. 281–297.
Seguras, Associação Por Vias (2011), ‘Velocidade e distância de parada’, Disponível
em: <http://www.vias-seguras.com/publicacoes/aulas_de_educacao_
37
REFERÊNCIAS BIBLIOGRÁFICAS 38
no_transito/aula_09_velocidade_e_distancia_de_parada>. Acesso em
julho de 2011.
Waze (2010), Waze’s homepage, Página na internet, acessado em outubro de 2010.
URL: http://www.waze.com/
WikiMapa (2011), WikiMapa’s homepage, Página na internet, acessado em junho de
2011.
URL: http://wikimapa.org.br/
Wikimapia (2011), Wikimapia’s homepage, Página na internet, acessado em abril de
2011.
URL: http://wikimapia.org