Proposta: Algoritmo paralelo para estimação de movimento a partir de imagens RGBD
Departamento de Computação
IME/USP
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 nas subsequentes 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 casamento entre grafos.
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 desenvolveu um algoritmo que utiliza esta tecnologia para criar uma representação tridimensional da realidade através das imagens RGBD obtidas pelo Kinetic(TM) [Pires, D. 2012. Estimação de movimento a partir de imagens RGBD usando homomorfismo entre grafos.]. 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.
formato para referências: [Pires, D. 2012. Estimação de movimento a partir de imagens RGBD usando homomorfismo entre grafos.] No meio do texto ou como "footnote"(site diz que footnotes nao sao recomendados...)??Objetivos
ITEMIZE ISTO(?)::
- 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 [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.].
- 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 2 trabalhos
Tarefas:
* 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
REMOVER IDENTAĆAO!!!! ESTA ESTRAGANDO O FORMATO DO ITEMIZE!!!
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