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.