Resumo
Seja em câmeras de segurança, jogos eletrônicos ou carros que se guiam sem motorista, a elaboração de algoritmos capazes de reconhecer movimento em uma sequência de imagens há algum tempo é requisito para concretizar muitas das ambições humanas para a tecnologia futura.
A estimação de movimento pode ser feita através da representação da imagem como um grafo completo, cada pixel correspondendo a um nó. Com esta representação, a estimação de movimento é obtida a partir do casamento dos grafos obtidos na sequência de imagens que compõe um vídeo. No entanto, este casamento de grafos é sabidamente um problema NP-difícil, e o maior gargalo de processamento que impossibilita que a estimação de movimento seja realizada em tempo real.
Neste trabalho procuraremos contribuir para o problema de visão de estimação de movimento através do estudo da paralelização do problema de estimação de movimento.
Contexto científico
O problema de estimação de movimento já tem sido estudado há algumas décadas e o resultado desses estudos já vê uso em aplicações modernas. Porém, até recentemente as metodologias utilizavam apenas texturas (imagens RGB) de câmeras convencionais, às vezes juntamente a identificadores visuais nítidos (tags), para a estimação de movimento.
Desenvolvimentos tecnológicos recentes apresentaram e difundiram dispositivos capazes de fornecer o campo de profundidade em adição à textura convencional (imagens RGBD) e abrem espaço para o desenvolvimento de novas metodologias de estimação de movimento que aproveitam esta nova informação. Um destes é o Kinetic (TM) desenvolvido pela Microsoft.
Pires [1] desenvolveu um algoritmo que utiliza esta tecnologia para criar uma representação tridimensional da realidade através das imagens RGBD obtidas pelo Kinetic(TM). Cada pixel da textura RGB é representado como um nó em um grafo completo, e o movimento é estimado calculando as distâncias entre pixeis de uma sequência de imagens.
Porém, Pires afirma que o algoritmo proposto não pode ser executado em tempo real se as imagens gerarem representações em grafos com muitos vértices.
Objetivos
- Propor uma estratégia de paralelização para a parte do problema que é intrinsecamente difícil do ponto de vista computacional, que é o casamento entre grafos. O problema de casamento entre grafos é sabidamente um problema NP-Difícil [2].
- Neste trabalho, estudaremos um método eficaz de paralelização para o problema e realizaremos uma avaliação experimental da implementação proposta.
- Inicialmente, estudaremos a aplicabilidade de uma estratégia de paralelização utilizando a biblioteca OpenMP e/ou utilizando placas de aceleração gráfica com processadores do tipo GPGPU.
Atividades já realizadas
- Estudo da tese de doutorado do David - A compreensão do algoritmo a ser paralelizado é fundamental, além da tese ser uma fonte de referências sobre outros estudos de Visão.
- Estudo do código-fonte da ferramenta desenvolvida durante seu doutorado
- Reuniões preliminares para discussão da estratégia de paralelização
- Criação de conta e integração ao Grupo de Visão - Isto é importante para possibilitar acesso a hardware necessário para o desenvolvimento de um algoritmo que utilize aceleração gráfica.
- Estudo das bibliotecas necessárias para acessar o Kinect e OpenCV
- Criação do blog
- Resenha de dois trabalhos anteriores
Tarefas e cronograma de atividades
- * Estudo do algoritmo e código
- * Estudo do hardware necessário (Kinect) - Junho
- * Estudo do estado da arte da área de paralelização - Junho/Agosto
- * Escolha do(s) método(s) de paralelização para o algoritmo - Agosto
- * Implementação do algoritmo paralelo -Agosto/Setembro
- * Versão Preliminar da Monografia - Setembro
- * Avaliação de corretude do programa -Setembro/Outubro
- * Comparação com o desempenho da versão sequencial -Outubro
- * Poster - Novembro
- * Redação da monografia -Novembro
Estrutura esperada da monografia
- Título
- Resumo
- Introdução
- Contexto científico
- Objetivos
- Trabalhos relacionados
- Estimação de movimento
- Baseado somente na textura (RGB)
- Estimação de movimento usando RGBD
- Avaliação de técnicas de paralelização
- OpenMP
- GPGPU
- Work-stealing
- Estratégia de paralelização
- Análise experimental
- Descrição das instâncias e ambiente de experimentação
- Análise de desempenho
- Conclusão
- Trabalhos futuros
- Referências
Referências
[1] Pires, D. 2012. Estimação de movimento a partir de imagens RGBD usando homomorfismo entre grafos.[2] Michael R. Garey and David S. Johnson. Computers and Intractability:A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, Jan. 1979. ISBN : 0-716-71045-5.