Estimao de movimentoa partir de imagens RGBD

usando homomorfismo entre grafos

David da Silva Pires

Tese apresentadaao

Instituto deMatematica e Estatisticada

Universidade de Sao Paulopara

obtencao do titulode

Doutor em Ciencias

Programa: ComputaoOrientador: Prof. Dr. Roberto M. Cesar-Jr

Coorientador: Prof. Dr. Luiz Velho

Durante a elaborao deste trabalho, o autor recebeu auxlio financeiro da CAPES

- So Paulo, 13 de maio de 2013 -

Estimao de movimentoa partir de imagens RGBD

usando homomorfismo entre grafos

Esta verso da tese contm as correes e alteraes sugeridaspela Comisso Julgadora durante a defesa da verso original do trabalho,

realizada em 14/12/2012. Uma cpia da verso original est disponvel noInstituto de Matemtica e Estatstica da Universidade de So Paulo.

Comisso Julgadora:

Prof. Dr. Roberto Marcondes Cesar-Jr. (orientador) - IME-USP

Prof. Dr. Carlos Hitoshi Morimoto - IME-USP

Prof. Dr. Roberto Hirata Jnior - IME-USP

Prof. Dr. Marcio Lobo Netto - EP-USP

Prof. Dr. Soraia Raupp Musse - PUC-RS

A meu amigo Jess P. Mena-Chalco,certamente culpado por mudar o curso de meu doutorado,eventualmente culpado por mudar o curso de minha vida.

A minha namorada Bartira,eventualmente culpada por mudar o curso de meu doutorado,

certamente culpada por mudar o curso de minha vida,sol que ilumina meus dias.

Resumo

Pires, D. S. Estimao de movimento a partir de imagens RGBD usando homomorfismo entre grafos.105 p. Tese - Instituto de Matemtica e Estatstica, Universidade de So Paulo, So Paulo, 2012.

Recentemente surgiram dispositivos sensores de profundidade capazes de capturar textura e geometriade uma cena em tempo real. Com isso, diversas tcnicas de Viso Computacional, que antes eram aplicadasapenas a texturas, agora so passveis de uma reformulao, visando o uso tambm da geometria. Ao mesmotempo em que tais algoritmos, tirando vantagem dessa nova tecnologia, podem ser acelerados ou tornarem-se mais robustos, surgem igualmente diversos novos desafios e problemas interessantes a serem enfrentados.Como exemplo desses dispositivos podemos citar o do Projeto Vdeo 4D, do IMPA, e o Kinect, da Mi-crosoft. Esses equipamentos fornecem imagens que vm sendo chamadas de RGBD, fazendo referncia aostrs canais de cores e ao canal adicional de profundidade (com a letra D vindo do termo depth , profundi-dade em ingls). A pesquisa descrita nesta tese apresenta uma nova abordagem no-supervisionada para aestimao de movimento a partir de vdeos compostos por imagens RGBD. Esse um passo intermedirionecessrio para a identificao de componentes rgidos de um objeto articulado. Nosso mtodo faz uso datcnica de casamento inexato (homomorfismo) entre grafos para encontrar grupos de pixels (blocos) que semovem para um mesmo sentido em quadros consecutivos de um vdeo. Com o intuito de escolher o melhorcasamento para cada bloco, minimizada uma funo custo que leva em conta distncias tanto no espaode cores RGB quanto no XYZ (espao tridimensional do mundo). A contribuio metodolgica consistejustamente na manipulao dos dados de profundidade fornecidos pelos novos dispositivos de captura, demodo que tais dados passem a integrar o vetor de caractersticas que representa cada bloco nos grafos a se-rem casados. Nosso mtodo no usa quadros de referncia para inicializao e aplicvel a qualquer vdeoque contenha movimento paramtrico por partes. Para blocos cujas dimenses causem uma relativa dimi-nuio na resoluo das imagens, nossa aplicao roda em tempo real. Para validar a metodologia proposta,so apresentados resultados envolvendo diversas classes de objetos com diferentes tipos de movimento, taiscomo vdeos de pessoas caminhando, os movimento de um brao e um casal de danarinos de samba degafieira. Tambm so apresentados os avanos obtidos na modelagem de um sistema de vdeo 4D orientadoa objetos, o qual norteia o desenvolvimento de diversas aplicaes a serem desenvolvidas na continuaodeste trabalho.

Palavras-chave: estimao de movimento, segmentao de movimento, casamento entre grafos, imagensRGBD.

Abstract

Pires, D. S. Motion estimation from RGBD images using graph homomorphism. 105 p. Ph. D. Thesis- Instituto de Matemtica e Estatstica, Universidade de So Paulo, So Paulo, 2012.

Depth-sensing devices have arised recently, allowing real-time scene texture and depth capture. As aresult, many computer vision techniques, primarily applied only to textures, now can be reformulated usingadditional properties like the geometry. At the same time that these algorithms, making use of this newtechnology, can be accelerated or be made more robust, new interesting challenges and problems to be con-fronted are appearing. Examples of such devices include the 4D Video Project, from IMPA, and Kinect,from Microsoft. These devices offer the so called RGBD images, being related to the three color channelsand to the additional depth channel. The research described on this thesis presents a new non-supervisedapproach to estimate motion from videos composed by RGBD images. This is an intermediary and nec-essary step to identify the rigid components of an articulated object. Our method uses the technique ofinexact graph matching (homomorphism) to find groups of pixels (patches) that move to the same direc-tion in subsequent video frames. In order to choose the best matching for each patch, we minimize a costfunction that accounts for distances on RGB color and XYZ (tridimensional world coordinates) spaces. Themethodological contribution consists on depth data manipulation given by the new capture devices, suchthat these data become components of the feature vector that represents each patch on graphs to be matched.Our method does not use reference frames in order to be initialized and it can be applied to any video thatcontains piecewise parametric motion. For patches which allow a relative decrease on images resolution,our application runs in real-time. In order to validate the proposed methodology, we present results in-volving object classes with different movement kinds, such as videos with walking people, the motions ofan arm and a couple of samba dancers. We also present the advances obtained on modeling an object ori-ented 4D video system, which guide a development of different applications to be developed as future work.

Keywords: motion estimation, motion segmentation, graph matching, RGBD images.

Sumrio

Resumo

Abstract

Lista de Figuras

Lista de Tabelas

1 IntroduoMotivao , 1 Comentrios preliminares, 2 Objetivos , 4 Contribuies, 4 Organizao do texto , 5.

7 Reviso bibliogrficaEstimao de movimento , 7 Mapa de profundidade , 9 Escaneamento 3D , 10 Vdeo 3D e vdeo 4D , 13.

17 MetodologiaPerspectiva geral, 17 Sequncia de etapas, 18 Dados de entrada, 18 Processamento da textura, 21 Processamento do mapa de profundidade, 22 Abordagem baseada em grafos, 25 Visualizao dosresultados, 28 Desempenho, 30.

33 Resultados experimentais

41 ConclusoDiscusso, 41 Trabalhos futuros, 41.

45 Detalhes tcnicos da implementaoPorte do vdeo 3D para o sistema operacional GNU/Linux, 45 Modelagem do sistema de vdeo 4D , 45 Equipamento e programa da estimao de movimento, 57.

xi

59 Manual de captura de vdeo 3DIncio rpido , 59 Detalhamento da captura , 60.

69 Pster SIBGRAPI 201271 Artigo 2013Referncias Bibliogrficas

Lista de Figuras

1.1 Dois dispositivos sensores de profundidade em uso atualmente . . . . . . . . . . . . . . . . . . 31.2 Dados de entrada tpicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Resultado tpico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1 Sequncia de passos do sistema do IMPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Etapas que constituram o trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1 Fluxo de dados atravs do mtodo implementado . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Imagem RGBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.3 Volume de visualizao ou frustum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4 Controlando os limiares do volume de visualizao . . . . . . . . . . . . . . . . . . . . . . . . 233.5 Exemplo de mapeamento de textura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.6 Construo e casamento de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.7 Exemplo de casamento entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.8 Opes de exibio dos blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.9 Rtulos que indicam a direo do movimento . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.10 Janela principal do aplicativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.11 Caixa de dilogo do desenho do grafo e do casamento . . . . . . . . . . . . . . . . . . . . . . . 32

4.1 Dados de entrada e sada tpicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.2 Imagem de profundidade capturada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.3 Imagem de textura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.4 Sequncia de vdeo com pessoa movendo seu brao . . . . . . . . . . . . . . . . . . . . . . . . 344.5 Visualizao dos casamentos como setas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6 Resultado refinado de segmentao de movimento usando blocos de 2 2 pixels . . . . . . . . 354.7 Teste dos valores extremos de : 0 e 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.8 Textura e mapa de profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.9 Comparao entre casamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.10 Teste de robustez da classificao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.1 Desempenho do Kinect na presena de luz solar . . . . . . . . . . . . . . . . . . . . . . . . . 425.2 Falha de captura na imagem de textura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

A.1 Casos de uso em alto nvel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46A.2 Edio de um vdeo 4D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48A.3 Salvamento e abertura de um vdeo 4D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49A.4 Exportao de um vdeo 4D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50A.5 Importao de textura e geometria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52A.6 Diagrama de implantao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53A.7 Sequncia de passos do sistema do IMPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

xiii

A.8 Diagrama de colaborao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55A.9 Diagrama de estados I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55A.10 Diagrama de estados II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56A.11 Diagrama de atividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

B.1 Cmera e projetor em um trip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61B.2 Cmera usada no sistema de captura de vdeo 3D . . . . . . . . . . . . . . . . . . . . . . . . . 62B.3 Enquadramento da cena na cmera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62B.4 Boto para fazer ajuste manual da ris da cmera . . . . . . . . . . . . . . . . . . . . . . . . . . 63B.5 Projetor usado no sistema de captura de vdeo 3D . . . . . . . . . . . . . . . . . . . . . . . . . 63B.6 Genlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64B.7 Monitores usados no sistema de captura de vdeo 3D . . . . . . . . . . . . . . . . . . . . . . . 65B.8 O programa v4dFaixas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65B.9 Ajuste dos objetos na cena a ser gravada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66B.10 Utenslios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Lista de Tabelas

B.1 Atalhos do programa v4dFaixas: quantidade de faixas exibidas . . . . . . . . . . . . . . . . . 66B.2 Atalhos do programa v4dFaixas: tipo de slides exibidos . . . . . . . . . . . . . . . . . . . . 66

xv

AgradecimentosDoze anos. Exatamente uma dzia de anos o tempo que se passou desde que minha amiga Ana Beatrizme apresentou, como um aluno interessado em fazer iniciao cientfica, ao professor que a tantosfascinava com seu jeito descontrado de dar as aulas de Viso Computacional e Processamento de Imagensdo IME-USP: o professor Roberto Cesar. Da iniciao cientfica veio o mestrado, do mestrado o doutoradoe, no de surpreender que, em meio a tanto tempo, a amizade. Sempre pronto a perdoar minhas falhas emquestes que sempre tive dificuldades e disposto a ajudar at em questes pessoais, vejo em voc, Roberto,uma pessoa muito humana, qual sou muito grato por todo o aprendizado. Sei que continuarei sempre sendoseu aluno.

Creio que tambm sou to grato quanto a meu amigo Jess P. Mena-Chalco, ao qual dedico esta obra.Assim como pude acompanhar a rpida evoluo acadmica do Roberto, tambm vi voc, Jess, galgandopasso-a-passo uma escalada de sucesso. Seus comentrios sempre pertinentes ao meu trabalho, as animadasdiscusses que tivemos sobre computao e, claro, sua interferncia direta em meu doutorado, quando meemprestou, sem data para devoluo, o Kinect que tinha acabado de comprar e com o qual s haviabrincado por um dia, desenham em minha memria lembranas agradveis que quero sempre manter. Agora,que cada um vai seguindo por seu caminho, hora de vivermos coisas diferentes, fortalecendo essa amizade.

Agradeo ao professor Luiz Velho, por sempre ter me recebido to bem quando fui ao IMPA e pelastimas orientaes que recebi nos poucos contatos (mea maxima culpa) que tivemos.

Tambm agradeo a todos os colegas do Laboratrio de Processamento de Imagens, Bioinfo I, com osquais convivi tantos anos estudando, trabalhando e me divertindo.

Nesta reta final do doutorado, pude contar com a ajuda de muitas pessoas que doaram seu tempo e suashabilidades para que eu pudesse concluir a minha tese. Agradeo especialmente ao Pedro Losco Takeciane ao Jess P. Mena-Chalco (de novo!) pelas timas revises que fizeram em meu texto final, aos meusprofessores de dana Camilla Varjo e Ricardo Oliveira por embelezarem o meu trabalho com sua arte dosamba de gafieira, e minha sobrinha Manuela (e a seus pais, minha irm Deise Pires Hala e meu cunhadoGeorge Roberto Hala) por ter sido a estrela em uma captura com o Kinect ao mostrar que j domina a artede andar.

Certamente essa tese no teria sido possvel sem todo o amor que recebi de meus pais, Antonio PiresEustquio e Dulcineia da Silva. Acho que s entenderei a razo de todos os sacrifcios que vocs fizeram, efazem, por mim quando tiver meus prprios filhos.

E claro, eu no poderia deixar de agradecer minha namorada Bartira Ferraz Martiniano, a quem tam-bm dedico esta tese e que, apesar de nem imaginar o qu o operador ++ faz em C, sempre me ouviu commuita ateno quando eu falava sobre as minhas dificuldades no doutorado, demonstrando toda sua paci-ncia. No houve um s dia que no tenhamos tratado desse assunto nessa reta final; voc se fez presentecomo ningum, em meu trabalho e em meus pensamentos.

David da Silva PiresSo Paulo, 17 de agosto de 2012.

xvii

Captulo 1

Introduo

Esta tese apresenta um mtodo para a estimao densa de movimento com base no formalismo de algo-ritmos em grafos, mais especificamente homomorfismo entre grafos. Tais algoritmos tm sido aplicados avrios problemas de processamento e anlise de imagens, incluindo filtragem e segmentao, classificao,representao e descrio de objetos.

A matemtica discreta fornece uma estrutura elegante para o processamento de imagens, sendo ricaem algoritmos eficientes, com provas de corretude. Como consequncia, muitos mtodos recentes de pro-cessamento de imagem tm sido modelados como problemas de busca e otimizao em grafos. Mtodostradicionais podem tambm ser reformulados com base em grafos, levando a implementaes mais efici-entes, e/ou favorecendo anlises tericas. Por outro lado, as peculiaridades do processamento de imagemexigem adaptaes especficas, o que gera novos desafios de pesquisa e oportunidades, visto a crescentequantidade de publicaes na rea [Lzoray & Grady, 2012].

1.1 Motivao

Ha diversos problemas a serem resolvidos e metodologias que vem sendo aplicadas com relao esti-mao de movimento 3D em vdeo. Em alguns casos, algumas solues tem sido adotadas e imple-mentadas e j h aplicaes sendo usadas em situaes reais, beneficiando-se da evoluo que a rea sofreunos ltimos anos. Muitas dessas aplicaes lidam apenas com o movimento que percebido a partir de umvdeo comum, com informao apenas da textura da cena. Outras usam marcadores nos objetos para inferiruma representao tridimensional dos mesmos.

Dado que o escaneamento 3D tradicional, envolvendo objetos rgidos e estticos, j foi resolvido paravariadas situaes prticas, muito se tem dado ateno presena de movimento nas cenas capturadas emum escaneamento 3D, tambm envolvendo objetos deformveis (maleveis).

Ao mesmo tempo em que essa necessidade verificada, tornou-se disponvel no mercado cmeras devdeo de profundidade, permitindo que, juntamente com a informao de intensidade, seja capturada tambma distncia de cada pixel at o dispositivo sensor. Essa disponibilidade permitiu que fossem desenvolvidosprodutos que realizam o reconhecimento de gestos para interao natural, usando estes como um meio decontrolar dispositivos eletrnicos, tais como televisores e vdeo-games.

Dentre as principais aplicaes que motivam este trabalho, podemos citar:

anlise de cenas de trfego de automveis;

anlise 3D do modo de caminhar humano;

estimao do esqueleto de uma pessoa;

rastreamento de pessoas;

1

2 INTRODUO

rastreamento de animais;

reconhecimento de gestos para interao natural [Suma et al., 2011];

escaneamento 3D de cenas dinmicas;

escaneamento completo 3D de objetos articulados;

mapeamento de texturas em superfcies;

identificao de componentes rgidos em objetos articulados [Kumar et al., 2005];

remoo de rudo e outros artefatos de vdeo;

estabilizao de imagem durante gravao de vdeo com cmera digital [Srinivasan et al., 2005];

desentrelaamento de vdeo;

interpolao de quadros em vdeo (cmera lenta);

compresso de vdeo [Gall, 1991; Lee et al., 1997];

morphing automatizado;

realidade aumentada;

vigilncia automatizada;

automao na conduo de automveis;

edio de vdeo.

1.2 Comentrios preliminares

O metodo desenvolvido durante o doutorado, apresentado neste documento, faz parte do desenvolvimentode uma plataforma de edio e integrao de dados, interao com usurio e visualizao de vdeo 3D.Trata-se do conceito que chamamos de vdeo 4D, o qual explicado nos captulos seguintes. Este trabalho uma continuao de uma parceria com o professor Luiz Velho, do Instituto Nacional de Matemtica Purae Aplicada (IMPA), dando sequncia a uma colaborao que se iniciou durante o mestrado.

Nesse contexto, fez-se uso do equipamento de captura de vdeo 3D desenvolvido no IMPA, o qual usauma tcnica baseada em luz estruturada para inferir a distncia dos objetos at a cmera. Com o acesso queobtivemos a esse hardware e com o posterior surgimento de dispositivos como o Kinect (da Microsoft) eo Xtion (da ASUS), que podem capturar imagens de textura e mapa de profundidade de uma cena, pude-mos iniciar os experimentos tomando estes dados como entrada e enfrentar os muitos desafios e problemasinteressantes que surgiram. A Figura 1.1 mostra os dois sensores de profundidade citados (as imagens noesto em escala).

O estudo de movimento em Viso Computacional um passo adiante em relao a problemas que en-volvem uma nica imagem ou duas imagens adquiridas ao mesmo tempo: para que o movimento possaser percebido, faz-se necessrio o processamento de imagens adquiridas no decorrer do tempo. O inte-resse passa a ser a informao visual que pode ser extrada a partir das mudanas espaciais e temporais queocorrem em uma sequncia de imagens.

Assumindo que as condies de iluminao no variam, mudanas nas imagens podem ser causadas porum movimento relativo entre a cmera e a cena: a cmera pode se mover em frente a uma cena esttica,partes da cena podem se mover em frente a uma cmera estacionria ou, em um caso mais geral, tantocmera quanto objetos podem se mover com diferentes movimentos.

Dada uma sequncia de vdeo, tal como a exibida na Figura 1.2, nosso mtodo constri um grafo para

COMENTRIOS PRELIMINARES 3

Figura 1.1: Dois dispositivos sensores de profundidade em uso atualmente.

Figura 1.2: Os dados de entrada tpicos constituem uma sequncia de vdeo com uma imagem de tex-tura e outra de profundidade para cada quadro. A imagem de textura fornece valores RGBenquanto que a do mapa de profundidade nos d triplas (x, y, z).

cada quadro e os compara, entre quadros consecutivos, encontrando um casamento baseado nas distnciasnos espaos RGB de cores e XYZ de coordenadas do mundo. Tais casamentos so codificados como rtuloscoloridos com o propsito de visualizao.

A principal aplicao de dados de entrada como os apresentados relativa a interao natural, seja paracontrolar um televisor ou no ramo do entretenimento, para interagir com jogos de vdeo-games. Alm dessetipo de aplicao, tambm podemos usar a informao adicional fornecida pela imagem de profundidadepara melhorar algoritmos que, at agora, eram aplicados apenas a imagens de textura. justamente nessesentido que desenvolvemos o mtodo de estimao de movimento aqui apresentado, conforme exibido na Fi-gura 1.3.

Nossa abordagem pode ser usada em situaes mais gerais que as que contm humanos fazendo gestosem frente ao dispositivo de captura. O mtodo apresentado pode lidar com ocluso e com continuidade es-

Figura 1.3: Deteco e segmentao de movimento ( direita) usando nosso mtodo aplicado s ima-gens de textura ( esquerda) e de profundidade (meio). As cores vermelho e azul indicammovimento para a direita e para a esquerda, respectivamente.

4 INTRODUO

pacial e independente de quadros que sejam usados para inicializao. O movimento deve ser paramtricopor partes, a fim de que seja possvel identificar componentes rgidos que estejam se movendo.

1.2.1 Divulgao cientficaO software encontra-se na pgina http://www.vision.ime.usp.br/~davidsp/4dvideoviewer/. Oprograma pode ser baixado e instalado em plataformas GNU/Linux e permite capturar, ler arquivos (videbase de dados abaixo), gravar arquivos, calcular o casamento e fazer a visualizao dos resultados.

Ns criamos uma base de dados para trabalhar e tornamos tal base pblica, acessvel a partir do endereo:http://www.vision.ime.usp.br/~davidsp/kinectdatabase/.

Todo material que documenta o desenvolvimento do software e o modo de us-lo encontra-se dispon-vel em http://www.vision.ime.usp.br/~davidsp/4dvideoviewer/v4dviewer/doc, incluindo do-cumentao gerada a partir do cdigo-fonte (com o Doxygen), diagramas UML sobre o sistema, manual deusurio e a verso final desta tese. Tambm so distribudos outros tipos de documentos, tais como psterese conjuntos de slides de apresentao, os quais foram usados em conferncias e seminrios dados sobre otrabalho desenvolvido, e o arquivo bibTeX usado nesta tese, o qual contm as principais referncias paraquem quiser se aprofundar nos detalhes, tericos e tcnicos, aqui descritos.

1.3 Objetivos

Este trabalho visa desenvolver um mtodo, baseado em modelos estruturais 3D dinmicos, representadospor casamentos entre grafos, que explore os benefcios ao se usar a informao adicional dada pelaimagem de profundidade registrada com a imagem de textura, apresentando um algoritmo que detecta adireo do movimento (fluxo ptico) a taxas de tempo real. O procedimento desenvolvido mostra, por meiode rtulos identificados por cores, para qual direo cada grupo de pixels (denominado bloco) est se mo-vendo. Dados de profundidade, quando usados em conjunto com os tradicionais valores RGB e coordenadasde textura, facilitam a delimitao de objetos de interesse e tornam os resultados substancialmente melho-res quando considerados como uma caracterstica descritiva para cada pixel. Esse fator uma vantagemsobre mtodos que dependem da presena de um padro de textura bem definido, como uma sequncia detabuleiros quadriculados [Tron & Vidal, 2007].

1.4 Contribuies

Ha tempos vem sendo desenvolvida uma metodologia no Grupo Creativision (Grupo de Viso Criativa doIME-USP, coordenado pelo professor Roberto Cesar), que vem pesquisando o uso da tcnica de ca-samento inexato entre grafos (homomorfismo). Cada vez mais essa tcnica tem se mostrado robusta egenrica, como pode ser verificado nas teses de doutorado de Noma [2010] e Graciano [2012]. Dentre asaplicaes, encontram-se segmentao interativa de imagem natural, colorizao assistida por computadore rastreamento de objetos.

A presente tese mais uma contribuio para essa linha de pesquisa. A metodologia desenvolvida aquigeneraliza os casos tratados em trabalhos anteriores (que baseavam-se apenas na textura) para casos 3D, quetambm fazem uso da informao de profundidade de uma cena. A inovao que trazida com o aumentode uma dimenso explorada de diversas formas no texto aqui apresentado. Seu emprego feito na tentativade resoluo de um problema muito desafiador: a estimao de movimento em cenas sem restries quanto iluminao ou quanto ao tipo de objetos se movimentando (que pode ser rgido ou malevel, articulado ouno).

O trabalho desenvolvido tambm contribuiu para a aquisio de know-how no grupo com relao a umanova proposta de uso de modelos de grafos com integrao (fuso) de atributos oriundos de diferentes fontes(textura, geometria e vdeo). Foi a primeira vez que tivemos acesso a dispositivos sensores de profundidadede ltima gerao, o que serviu de grande motivao para criar um mtodo que permitisse a comparaoentre os diferentes tipos de entrada.

ORGANIZAO DO TEXTO 5

No obstante, outro fruto resultante deste trabalho foi a implementao de um software que permite aexecuo, a experimentao e a anlise dos resultados de toda a pesquisa realizada.

1.5 Organizao do texto

O Capitulo 2 contm uma reviso bibliogrfica sobre estimao de movimento, mapas de profundidadee uma seo que explicita o estado da arte na rea de Computao Grfica em relao aos algoritmosj implementados para a reconstruo de objetos articulados, bem como dos problemas inerentes a essa ta-refa. Ainda no Captulo 2, a Seo 2.4 fornece uma breve viso sobre o sistema de captura de vdeo 3Ddesenvolvido no IMPA e tenta definir os principais tpicos que caracterizaro o vdeo 4D. Nesse sentido, apresentada a modelagem j existente para este. J no Captulo 3, descrita a metodologia que foi desenvol-vida para a estimao de movimento a partir de imagens RGBD. A fim de validar a metodologia proposta,no Captulo 4 so apresentados os resultados que obtivemos com a gravao de objetos mveis, resultadosestes que so discutidos no Captulo 5. O Apndice A apresenta a modelagem desenvolvida para o vdeo4D e detalhes tcnicos da implementao no uso do Kinect. O Apndice B, por sua vez, um manualde captura de vdeo 3D. Por fim, no Apndice C encontra-se o pster referente ao mtodo desenvolvidonesta tese que foi apresentado no Sibgrapi 2012 (Congress on Graphics, Patterns and Images), seguido, noApndice D, por um artigo que pretendemos submeter oportunamente.

Captulo 2

Reviso bibliogrfica

Este levantamento bibliografico sobre trabalhos relacionados ao tema da tese inicia com uma breve des-crio sobre pesquisas realizadas acerca da estimao de movimento na Seo 2.1. Procurou-se, deforma sucinta, dar uma ideia geral sobre fluxo ptico, listar aplicaes que faam uso dele e, na medida dopossvel, relacionar tais trabalhos com o mtodo desenvolvido.

Na Seo 2.2, so discutidas algumas aplicaes do mapa de profundidade, o formato de dados fornecidopor dispositivos como o Kinect. J na Seo 2.3, so apresentados diversos trabalhos que tratam de umassunto que se refere mais rea de Computao Grfica que de Viso Computacional: a reconstruotridimensional de objetos a partir de mapas de profundidade. Embora tal discusso parea se distanciardo tema principal da tese, deve-se lembrar que a estimao de movimento uma etapa necessria para aidentificao das articulaes de objetos rgidos articulados. Assim, este parece ser um caminho natural aser seguido em projetos futuros e exemplifica a forte conexo que pode haver entre assuntos que, de antemo,possam parecer to dspares.

Por fim, na Seo 2.4 so descritos o sistema de captura de vdeo 3D do IMPA e o conceito de vdeo 4Dque construdo sobre ele.

2.1 Estimao de movimento

Movimento um aspecto da viso tridimensional que ns, humanos, podemos interpretar com facilidade.O estudo de conceitos tericos bsicos envolvidos no seu entendimento permite tratar de problemasreais nos quais o movimento crucial. neste contexto que surge o conceito de fluxo ptico. Em oposio aorastreamento de caractersticas, a estimao densa de movimento baseada na intensidade, tambm chamadade fluxo ptico, um tpico que lida diretamente com os valores armazenados nos pixels de uma imagem.

A estimao de movimento pode ser usada em diversas aplicaes prticas tais como a estabilizao devdeos com a remoo de tremores causados durante a gravao [Hansen et al., 1994; Irani et al., 1997;Matsushita et al., 2006; Morimoto & Chellappa, 1997; Srinivasan et al., 2005], o monitoramento de trfegode veculos, o rastreamento de pessoas (e.g., em sistemas de vigilncia) ou a insero de figuras 2D oumodelos 3D em vdeos por meio do rastreamento automtico de pontos de referncia prximos.

A rea de estimao acurada de movimento vem sofrendo uma rpida evoluo, com significantesavanos no desempenho dos algoritmos ocorrendo a cada ano. A pgina de avaliao de fluxo ptico(http://vision.middlebury.edu/flow/) uma tima fonte de ponteiros para algoritmos de alto de-sempenho desenvolvidos recentemente.

Os modelos mais simples de movimento que existem so aqueles que modelam apenas movimentostranslacionais de toda a imagem [Wedel et al., 2009]. Tais modelos lidam com tpicos como estimaode movimento hierrquico (coarse-to-fine) [Anandan, 1989; Bergen et al., 1992; Quam, 1984], tcnicasbaseadas na transformada de Fourier [Fleet & Jepson, 1990] e refinamento iterativo.

7

8 REVISO BIBLIOGRFICA

Algumas abordagens [Baker & Matthews, 2004; Bergen et al., 1992; Fuh & Maragos, 1991; Lucas &Kanade, 1981; Rehg & Witkin, 1981; Shashua & Toelg, 1997; Shashua & Wexler, 2001] realizam umamodelagem do movimento por meio de parmetros globais vlidos tambm para toda a imagem, pormidentificando e compensando um nmero maior de alteraes tais como translao, rotao e aproximao(zoom), alm de movimento perspectivo planar. No entanto, enquanto modelos de movimento paramtricoso teis em uma variada gama de aplicaes (tais como estabilizao de vdeo e mapeamento em superfciesplanares), a maioria dos movimentos em imagens muito complicada para ser capturada por tais modelosde baixa dimenso.

Modelos de movimento baseados em splines comumente encontram largo uso no registro de imagensmdicas [Bajcsy & Kovacic, 1989; Christensen et al., 1997; Szeliski & Lavalle, 1996]. Tcnicas de registropodem ser usadas tanto para rastrear o desenvolvimento ou progresso de um paciente com o passar do tempoquanto para casar imagens de diferentes pacientes, a fim de encontrar partes comuns e detectar variaes oupatologias.

No outro extremo, tradicionalmente, algoritmos de fluxo ptico calculam uma estimativa de movimentoindependente para cada pixel, isto , o nmero de vetores de fluxo calculados igual ao nmero de pixelsde entrada.

Abordagens quantitativas Viso Computacional, tais como algoritmos de fluxo ptico baseados naintensidade das imagens, surgiram primeiramente no incio da dcada de 80 [Horn & Schunck, 1981; Huang,1981; Lucas & Kanade, 1981; Nagel, 1986]. O processamento de dados de profundidade tridimensionais(aquisio, casamento, modelagem e reconhecimento) tambm foi ativamente explorado desde ento [Agin& Binford, 1976; Banno et al., 2008; Besl & Jain, 1985; Curless & Levoy, 1996; Faugeras & Hebert,1987; Kanade, 1987; Montenegro et al., 2005; Pires, 2007; Pires et al., 2005; S et al., 2002; Velho et al.,2004; Vieira et al., 2005]. Algoritmos de rastreamento com tcnicas baseadas diretamente na intensidadedas imagens tambm foram desenvolvidos durante as dcadas de 80 e 90 [Lucas & Kanade, 1981; Rehg& Kanade, 1994; Shi & Tomasi, 1994], sendo frequentemente aplicados ao rastreamento de faces [Lanitiset al., 1997; Matthews & Baker, 2004; Matthews et al., 2007]. Outras abordagens que fazem uso de fluxoptico generalizado por pixel incluem modelos de movimento aprendido e em camadas. Aplicaes dessastcnicas incluem morphing automatizado, interpolao de quadros em vdeo (cmera lenta) e interfaces deusurio baseadas em movimento (gestos).

Os mtodos de fluxo ptico foram sendo melhorados com o passar do tempo [Anandan, 1989; Bakeret al., 2007; Barron et al., 1994; Bergen et al., 1992; Black & Anandan, 1996; Bolles et al., 1987; Bruhnet al., 2005; Horn & Weldon Jr., 1988; Nagel & Enkelmann, 1986; Papenberg et al., 2006].

Outra aplicao prtica que envolve a estimao de movimento e, portanto, faz parte da motivaodo desenvolvimento de mtodos que a calculem, o processo de remoo de rudo e outros artefatos devdeos [Kokaram, 2004]. Em contraste com removedores de rudo de uma nica imagem, nos quais somentea informao disponvel encontra-se na figura corrente, removedores de rudo em vdeo podem calcular amdia ou tomar emprestado informao de quadros adjacentes. No entanto, para realizar esta tarefa semintroduzir borramento ou jitter (movimento irregular), necessrio estimar um acurado movimento porpixel [Gai & Kang, 2009].

Algoritmos para alinhamento de imagens e estimao de movimento em sequncias de vdeo esto entreos mais amplamente usados em Viso Computacional. Como um exemplo, o alinhamento de imagens comcapturas a taxa de quadro ( 124 s, conhecida como frame rate na literatura) ou a taxa de campo (

130 s, do ingls

field rate) muito usado em filmadoras e cmeras digitais para implementar uma caracterstica chamadaestabilizao de imagem.

Tambm referente a uma aplicao que envolve a estimao de movimento por pixel que comumenteusada o desentrelaamento de vdeo, processo de converter um vdeo formado por campos de linhas parese mpares, que se alternam, em um sinal no entrelaado que contenha ambos os campos em cada qua-dro [de Haan & Bellers, 1998]. Duas tcnicas de desentrelaamento simples so a bob , que copia a linhaacima ou abaixo da linha ausente do mesmo campo, e a weave, que copia a linha correspondente do campoposterior ou anterior. Os nomes vm dos artefatos visuais gerados por estas duas tcnicas simples: o bobintroduz um movimento para cima e para baixo (conhecido como bobbing) ao longo de linhas horizontaisfortes; o weave pode levar a um efeito de zipeamento ao longo de arestas que se transladam horizontal-

MAPA DE PROFUNDIDADE 9

mente. Substituir esses operadores de cpia por valores mdios pode ajudar, mas no elimina completamentetais artefatos [Szeliski, 2011]. Uma grande variedade de tcnicas de aperfeioamento tem sido desenvolvi-das para este processo, o qual frequentemente vem embarcado em chips de processamento digital de sinaisencontrados em placas digitalizadoras de vdeo em computadores (j que vdeos com recepo via antenaso geralmente entrelaados, enquanto que os monitores de computadores no o so). Uma grande classedessas tcnicas estima movimentos locais por pixel e interpola os dados ausentes a partir de informaodisponvel em campos adjacentes no espao e no tempo [Dai et al., 2009].

O mtodo que desenvolvemos neste trabalho de doutorado pode ser usado em aplicaes mais geraisque aquelas que exigem que pessoas faam gestos em frente ao dispositivo de captura, permitindo lidar comreconstruo de cenas 3D e realidade aumentada. Naquela, pode-se atingir melhores registros de dados, umavez que parmetros do movimento de um objeto, tais como direo e velocidade, so conhecidos. Nesta,objetos artificiais da realidade aumentada podem responder melhor com relao ao movimento do usurio.

Neste trabalho, ns usamos a teoria de casamento entre grafos para encontrar a correspondncia entredois conjuntos de pontos. Esta abordagem tem sido usada para resolver muitos problemas de Viso Compu-tacional tais como segmentao interativa de imagem natural [Noma, 2012], casamento de formas [Belongieet al., 2002], colorizao assistida por computador [Noma, 2010], rastreamento de objetos [Graciano, 2007]e casamento de pontos para registro no-rgido [Chui & Rangarajan, 2003], dentre outros [Conte et al.,2004].

Nossa abordagem tambm um passo intermedirio na identificao de componentes rgidos de umobjeto articulado [Kumar et al., 2005; Torr & Zisserman, 1999]. Uma vez que saibamos, para cada bloco,a direo do movimento, ns podemos agrupar blocos similares em relao a esta caracterstica. Por meiodo acmulo de tais similaridades atravs de uma sequncia de vdeo, provvel que os componentes rgidostornem-se claramente identificveis e, por meio de comparao da proximidade entre tais componentes elevando em conta as diferenas nas direes de seus movimentos, poderia ser possvel identificar os pontosde articulao tambm.

Outra rea de pesquisa que poderia tirar vantagem da informao adicional fornecida pelo mapa deprofundidade o rastreamento 3D de movimento humano. Acreditamos que seja possvel melhorar bonstrabalhos desenvolvidos nesta rea [Zhao & Liu, 2008].

2.2 Mapa de profundidade

A envolvente tecnologia inerente aos atuais dispositivos sensores de profundidade foi inicialmente criadapara prover interao natural a consoles de vdeo-games. Porm, toda pesquisa que vem sendo feitaem reas como Computao Grfica e Viso Computacional tem mostrado muitos outros usos interessantes.Por isso vem sendo dada tanta importncia ao desenvolvimento de programas que facilitem o uso desseequipamento.

Embora essa tecnologia seja relativamente nova, no ser surpreendente se, em poucos anos, a mesmanovidade estiver presente tambm em clientes computacionais leves, tais como smart-phones e tablets. Como recente crescimento nas resolues de tela e no poder de processamento grfico desses pequenos disposi-tivos, tem sido possvel alavancar essas tendncias e implementar programas que lidam com dados estere-oscpicos 3D, mas ainda no sem um atraso nos dados processados [Olson et al., 2011]. Da a urgncia poralgoritmos eficientes e rpidos.

A principal aplicao de dados capturados por tais equipamentos geralmente referente a interao na-tural. Tais aplicaes usam algoritmos antropomtricos para estimar pose, esqueleto e o nmero de usuriosem frente ao dispositivo. Alguns sistemas possuem algoritmos especializados para reconhecer seus usurios,mesmo que haja gmeos idnticos entre eles [Leyvand et al., 2011]. O reconhecimento de gestos tem sidoaplicado para usar o Kinect para controlar outros dispositivos, objetivando uma interao mais fcil oumais natural e permitindo o uso de computadores por meio de grande acessibilidade. Exemplos de trabalhoscomo estes incluem interfaces para usar em apresentaes com slides [da Silveira, 2011] e a indstria dejogos [Microsoft, 2012].

Dentre as abordagens usadas para identificao de usurios desses dispositivos sensores de profundidade,

10 REVISO BIBLIOGRFICA

destaca-se a tecnologia chamada Kinect Identity [Leyvand et al., 2011], a qual seleciona um conjuntode trs tcnicas de identificao do usurio independentes: reconhecimento de faces, rastreamento da corda vestimenta e estimao da altura. Tais tcnicas foram selecionadas a partir de um conjunto maior edemonstraram ser as melhores que, ao mesmo tempo, eram robustas, sem exigir um processamento intensopor parte da CPU ou um consumo intenso de memria, e to independentes quanto possvel uma em relao outra. Tal escolha indica a importncia do desenvolvimento de algoritmos de treinamento que usam ambosos tipos de dados: textura e mapa de profundidade.

A necessidade de um melhor tratamento dos dados de profundidade em conjunto com os dados RGBe, consequentemente, o uso destes em algoritmos de segmentao de movimento sentido at mesmo pordesenvolvedores de programas especializados no reconhecimento de gestos, como o FAAST (sigla em inglsde Flexible Action and Articulated Skeleton Toolkit) [Suma et al., 2011]. Tais programadores demonstraraminteresse no desenvolvimento de rastreamento da cabea em tempo real e estimao da toro do brao deum usurio. Nenhum destes fornecido pela middleware OpenNI e as solues para estes problemascertamente exigem que tcnicas de Viso Computacional sejam aplicadas sobre ambos os dados de entrada.

2.3 Escaneamento 3D

Aplicacoes de escaneamento 3D tradicionais envolvem somente objetos estticos e o principal desafio emtais aplicaes a produo de um modelo digital preciso da geometria da cena. Na ltima dcada, umagama enorme de algoritmos tm sido proposta para tratar desse problema e atualmente pode-se considerarque ele esteja resolvido em variadas situaes prticas. Assim, a ateno tem mudado para a lide com cenasdinmicas, ou seja, aquelas nas quais os objetos esto se movendo.

Uma vez que a cena dinmica, primeira vista parece que o problema no est bem definido. O quesignifica escanear uma cena em que a geometria alterada constantemente? O que se espera como sadadesse processo? O problema torna-se mais complexo quando se leva em conta o fato de que, para capturarqualquer movimento de forma acurada, preciso capturar a cena a taxas em tempo real, o que, por si s, um desafio tecnolgico para o dispositivo de escaneamento.

Em relao a este ltimo desafio, o sensor mais comumente usado para cenas dinmicas a chamadacmera de vdeo de profundidade. Tal cmera fornece uma imagem da cena, na qual cada pixel contm nosomente a tradicional informao de intensidade como tambm a distncia geomtrica da cmera ao objetonaquele pixel. Algumas cmeras comerciais que geram esse tipo de informao a taxas de vdeo tm surgidonos ltimos anos [3DVSystems, 2009; Canesta, 2009; Primesense, 2009; Vialux, 2009] e o estado da artedas tecnologias envolvidas vem melhorando rapidamente. Os preos tambm caram e, com o surgimentodo Kinect, possvel adquirir atualmente uma cmera de vdeo de profundidade a um custo razovel.No nosso caso, em particular, temos acesso ao sistema de captura de vdeo 3D desenvolvido no IMPA peloprofessor Luiz Velho [Velho et al., 2004; Vieira et al., 2005] e tambm a um dispositivo Kinect.

A verso mais simples do escaneamento de uma cena dinmica a captura de movimento de um objeto3D rgido por partes (tal como uma pessoa). Isto significa que, como resultado, no se est interessadona geometria precisa do objeto, mas sim no movimento bruto de um esqueleto representando suas partesrgidas, as quais geralmente so poucas, atingindo no mximo a ordem de algumas dezenas. A capturade movimento vinha sendo realizada, at pouco tempo, por meio do uso de equipamentos elaborados, osquais envolviam marcadores situados no objeto, sendo til ter um dispositivo capaz de realizar a captura demovimento sem marcadores, baseado somente em cmeras de profundidade.

Uma verso mais desafiadora do problema o escaneamento completo 3D de objetos dinmicos tridi-mensionais rgidos por partes. A sada desejada no s um modelo esqueltico do objeto, mas tambmum modelo 3D completo da superfcie de cada um dos componentes rgidos e uma descrio do movimentode cada componente no tempo. Seria ideal se tudo isso pudesse ser calculado em tempo real. No entanto,mesmo uma computao em um ps-processamento poderia ser til para muitas aplicaes, principalmentenaquelas em que impossvel impedir que o objeto se mova durante o processo de escaneamento. Modelosde tais corpos articulados tm sido muito usados em Viso Computacional e em Computao Grfica, emaplicaes como deteco de pose e rastreamento de objetos em vdeo [Bregler & Malik, 1998; Hogg, 1983;

ESCANEAMENTO 3D 11

Sigal et al., 2003; Yu et al., 2002] e em dados 3D [Lin, 1999], alm de casos que incluem a estimaoe a renderizao de movimento 3D [Allen et al., 2002]. Na grande maioria das aplicaes, a estrutura eos parmetros do esqueleto articulado so especificados mo, embora algumas aplicaes otimizem osparmetros das juntas individuais [Allen et al., 2002; Gavrila & Davis, 1996; Mikic et al., 2001]. Um algo-ritmo que recupere, de um modo completamente no supervisionado, modelos articulados a partir de dados3D pode diminuir enormemente a dependncia, em muitas dessas aplicaes, de interferncia humana paradeterminao das articulaes do modelo.

Mais difcil ainda de ser resolvido o problema que envolve objetos na cena que se deformam com opassar do tempo de uma maneira no-rgida. Aqui, a descrio do movimento do objeto mais complicadae, em alguns casos, nem mesmo paramtrica.

Gool et al. [2002] ataca dois problemas que so de grande interesse. O primeiro deles o casamentode imagens obtidas a partir de pontos de vista muito diferentes, o que ocasiona pouca sobreposio deinformao. A soluo baseia-se em caractersticas locais invariantes ao ponto de vista no momento daaquisio da imagem. de grande interesse estender essa soluo para dados de entrada compostos porimagens RGBD, uma vez que, com isso, o registro da textura e da geometria poderia ser feito a partir dequadros do vdeo que estivessem bem distantes no tempo, acabando com a necessidade de pertencerema quadros consecutivos. O segundo problema tratado nesse artigo remete a como combinar modelos 3Dparciais, obtidos a partir de um sistema de luz estruturada, sem a necessidade de uma boa inicializaode suas posies relativas. Essa necessidade uma caracterstica intrnseca do algoritmo ICP (do inglsIterative Closest Point , ponto mais prximo iterativo), que largamente usado para realizar o registro entreduas nuvens de pontos.

Outro artigo que trata de escaneamento 3D e que descreve um mtodo que tambm poderia ser aplicadoaos mapas de profundidade que capturamos o de Wand et al. [2009], intitulado Efficient reconstructionof nonrigid shape and motion from real-time 3D scanner data. Nele, discutida uma nova tcnica paraa reconstruo de uma nica forma e seu movimento no-rgido a partir de dados de escaneamento 3D.O algoritmo descrito toma um conjunto de pontos no-estruturados amostrados com varincia no tempo,os quais capturam vises parciais de um objeto deformvel, e reconstri uma forma nica e um campo dedeformao que casa os dados. Tal representao gera correspondncias densas para a sequncia inteira,bem como uma forma 3D completa em cada quadro. No obstante, o algoritmo remove automaticamenteartefatos ruidosos, tanto espaciais quanto temporais, a partir dos dados de entrada brutos.

O livro Fotografia 3D, de Montenegro et al. [2005], apresenta as notas de um curso dado no 25o Col-quio Brasileiro de Matemtica. Ele descreve a rea de pesquisa conhecida como fotografia 3D, a qual integradiversos mtodos para a reconstruo de objetos tridimensionais a partir de imagens. Neste processo estoincludos a calibrao de cmera, a aquisio de informaes geomtricas e fotomtricas e o processamentodos modelos. O vdeo 3D uma evoluo obtida a partir da fotografia 3D.

O sistema descrito por Pekelny & Gotsman [2008] necessita de interveno manual na etapa de segmen-tao das partes articuladas de um objeto, etapa esta que poderia ser automatizada. O mtodo apresentadopelos autores o primeiro capaz de reconstruir um modelo 3D completo de um objeto articulado usandouma nica cmera de vdeo de profundidade. Este tambm o primeiro algoritmo de captura de movimentosem marcadores que no requer uma malha modelo para o objeto. Conforme a reviso bibliogrfica apre-sentada nesse artigo, h diversos algoritmos na literatura para a captura de movimento sem marcadores apartir de vdeo tradicional. Muitos deles [Cheung et al., 2003; Mndermann et al., 2006; Theobalt et al.,2004] recuperam o movimento de um objeto articulado a partir de sequncias de casco visual, adquiridas desilhuetas extradas deste. Tais algoritmos requerem mltiplas cmeras de vdeo sincronizadas observando oobjeto a partir de diferentes posies, o que acarreta complicaes relacionadas a calibrao multi-cmeratemporal e espacial.

H tambm diversas abordagens baseadas em modelos [Bray et al., 2004; Grest et al., 2005; Rodgerset al., 2006] capazes de recuperar a pose de um objeto articulado a partir de uma nica imagem de pro-fundidade por meio do casamento com um modelo. Isto, no entanto, requer um modelo muito detalhado ecalibrado a fim de que uma nica imagem de profundidade seja suficiente.

O algoritmo proposto por Anguelov et al. [2004] recupera o modelo 3D completo de um objeto junta-mente com a deteco da pose. Esse algoritmo tambm no exige marcadores, mas cada pose de entrada

12 REVISO BIBLIOGRFICA

deve ser uma malha completa da superfcie. Segue que esse algoritmo no se aplica a dados oriundos de umvdeo de profundidade.

Tambm almejamos, em trabalhos futuros, a reconstruo de um modelo 3D completo do objeto. Pararegistrar mltiplos componentes de um objeto articulado, assume-se uma estrutura esqueltica rgida porpartes. Uma abordagem diferente foi proposta por Mitra et al. [2007]. Nele, o problema do registro superado pela realizao de uma quebra dos dados de entrada em pequenos pedaos quase rgidos. Essealgoritmo assume amostragens espacial e temporal densas e faz o registro usando propriedades cinemticasda superfcie espao-tempo. Uma verso articulada desse algoritmo poderia ser possvel, de modo que talabordagem poder ser considerada por ns para a resoluo desse problema em tempo oportuno.

Diversos autores tm proposto algoritmos que recuperam tanto a geometria quanto o movimento doobjeto. Por exemplo, Ashbrook et al. [1999] propem um algoritmo para a reconstruo de um modeloarticulado. Contudo, o algoritmo usa uma abordagem de registro de quadros pareados, tornando-se, portanto,muito ineficiente quando aplicado a longas sequncias de dados de entrada. Os autores tambm admitemque o registro pareado, em oposio a uma abordagem mais global, leva a resultados sub-timos.

Os autores Knoop et al. [2006] propem um sistema, chamado VooDoo, de rastreamento de movimentodo corpo humano baseado em modelo. Este sistema modela o corpo humano como uma coleo de dezcilindros rgidos mveis (organizados hierarquicamente) e rastreia seu movimento no tempo usando o algo-ritmo de registro ICP. preciso redimensionar manualmente o modelo para diferentes pessoas. O VooDoono fornece bons resultados ao usar somente dados de profundidade como entrada e requer dados adicionaisa partir de sensores de rastreamento 2D para conseguir bons resultados.

Um outro trabalho [Wand et al., 2007] trata um problema similar, s que com um objeto deform-vel. Nele so realizadas reconstruo e otimizao iterativas da estrutura 4D assumindo suavidade espao-temporal. No entanto, o algoritmo computacionalmente pesado e no claro se ele capaz de reconstruirum modelo 3D completo de um objeto deformvel a partir de vdeo de profundidade.

Um dos algoritmos mais conhecidos para registro entre duas nuvens de pontos o ICP. Dentre as diversasimplementaes que esse algoritmo j recebeu, uma de destaque o chamado ICP dinmico, apresentadono artigo de Mitra et al. [2007]. O algoritmo apresentado realiza o registro de grandes conjuntos de nu-vens de pontos no estruturados, obtidos a partir de objetos mveis e maleveis, sem, no entanto, calcularas correspondncias. Dado como entrada um conjunto de quadros com uma densa amostragem espaciale temporal, como o caso dos dados adquiridos por um Kinect, o algoritmo apresentado nesse artigoexplora a coerncia temporal subjacente aos dados para calcular diretamente o movimento do objeto esca-neado e levar todos os quadros para um sistema de coordenadas comum. Em contraste com o mtodo usual,o qual realiza alinhamentos dois a dois entre quadros consecutivos, esse novo algoritmo calcula um mo-vimento consistente global considerando mltiplos quadros. adicionada, baseando-se na ordenao dosrespectivos quadros, uma coordenada de tempo a todos os pontos de entrada, de modo que o problema decalcular o movimento de cada quadro feito como sendo uma estimao de certas propriedades cinemticasda superfcie espao-tempo resultante. Executando essa estimao para cada quadro como um todo, pos-svel calcular movimentos rgidos inter-quadros e, adaptando o mtodo para realizar uma anlise local dasuperfcie espao-tempo, estende-se o algoritmo bsico para que ele trate tambm de objetos deformveis.

Em se tratando de escaneamento tridimensional, o estado da arte atualmente o projeto Kinect Fusion,da Microsoft Research [Izadi et al., 2011]. Trata-se de um sistema que permite que um usurio realize areconstruo tridimensional detalhada de uma cena em ambiente fechado bastando para isso mover um Ki-nect em torno dos objetos alvo. Somente os dados de profundidade capturados pelo Kinect so usadospara rastrear a pose 3D do sensor e para reconstruir, em tempo real, modelos 3D da cena. O rpido de-sempenho do sistema deve-se a uma nova sequncia de passos que baseada em processamentos realizadosem GPU. Os autores tambm descrevem o uso do sistema na segmentao de objetos (usada em realidadeextendida) e na interao de usurio, com este postando-se diretamente em frente ao sensor, permitindointeraes multi-toque em tempo real sobre qualquer tipo de superfcie.

Conforme comentado anteriormente, dispositivos sensores de profundidade so geralmente usados paraentretenimento e controle de outros dispositivos por meio de interface natural usando gestos. Algoritmosque fazem o reconhecimento de gestos primariamente necessitam de uma estimao e de um rastreamentodo esqueleto humano. Aqui, esqueleto entendido como um conjunto de juntas (pontos) e ossos (segmentos

VDEO 3D E VDEO 4D 13

de reta unindo juntas) que determinam os principais pontos de articulao de uma pessoa. Muitos programasbaseiam-se na implementao que fornecida pelo middleware OpenNI, que de cdigo fechado. Emborasejam frequentes questes da comunidade de programadores empresa Primesense, detentora do cdigo,sobre detalhes do algoritmo de rastreamento de esqueleto, a empresa sempre afirma que no h pretensesde public-lo. O que tem sido amplamente divulgado o conceito por trs do algoritmo de rastreamentooriginal da Microsoft, usado no Kinect [Shotton et al., 2011].

2.4 Vdeo 3D e vdeo 4D

O metodo que foi desenvolvido tambm aplica-se a dados oriundos de um sistema de vdeo 3D em temporeal proposto por Vieira et al. [2005]. Neste captulo dada apenas uma breve explicao sobre ofuncionamento do sistema de captura existente, uma vez que h um detalhamento completo que pode serconsultado na dissertao de mestrado [Pires, 2007]. Aps esta descrio sucinta, parte-se para a definiodo vdeo 4D e para a apresentao da modelagem que j foi feita at ento.

2.4.1 Vdeo 3D

O sistema de vdeo 3D [Montenegro et al., 2005; S et al., 2002; Velho et al., 2004], constitudo por projetore cmera, obtm imagens de profundidade de objetos por meio da projeo de slides com um padro defaixas coloridas. Tal procedimento permite a obteno, em tempo real, tanto do modelo 2 12 D dos objetosquanto da textura dos mesmos, segundo uma tcnica denominada luz estruturada. Os dados so capturadosa uma taxa de 30 quadros por segundo e possuem alta qualidade: resolues de 640 480 pixels para atextura e de 90 240 pontos (em mdia) para a geometria.

O trabalho desenvolvido no mestrado consistiu em um mtodo para deteco, rastreamento e casamentoespacial de componentes conexos presentes em um vdeo 3D. A informao de imagem do vdeo (textura)foi combinada com posies tridimensionais (geometria) a fim de alinhar partes de superfcies que so vistasem quadros subsequentes. A abordagem que adotamos consiste na deteco de caractersticas salientes noespao do mundo, provendo um alinhamento de geometria mais completo. O processo de registro feitosegundo a aplicao do algoritmo ICP, introduzido por Besl & McKay [1992]. Resultados experimentaisbem sucedidos [Pires et al., 2005] corroboraram nosso mtodo.

A Figura 2.1 fornece uma viso geral do pipeline do processamento 3D enquanto que as etapas queconstituram o trabalho desenvolvido no mestrado so ilustradas na Figura 2.2. O Apndice B detalha todoo processo de captura de vdeo 3D atualmente instalado no IMPA.

2.4.2 Vdeo 4D

O vdeo resultante do sistema de captura do IMPA pode ser, de certa forma, considerado um vdeo 3 12 D.Essa concluso vem do fato de cada quadro do vdeo fornecer um modelo 2 12 D da cena gravada, de modoque se tem a ordenada, a abscissa e a cota de cada ponto visvel pela cmera, mas no dos pontos oclusos.Pode-se tomar como exemplo de uma imagem 2 12 D a apresentada na Figura 2.1 (f). importante observarque no se tem dados sobre as partes sombreadas do coelho de pelcia, do cubo e da mo, uma vez que taispartes no esto no campo de viso da cmera. O tempo adiciona uma dimenso ao vdeo, totalizando 3dimenses e meia.

A evoluo para o conceito de vdeo 4D, portanto, almeja o aumento de meia dimenso a partir do vdeo3 12 D. Isso pode ser obtido segundo o casamento das diversas nuvens de pontos de um mesmo objeto, forne-cidas a cada quadro do vdeo. Conforme um objeto move-se diante da cmera ou, similarmente, conformea cmera movimenta-se em relao cena que gravada, novos detalhes, tanto referentes textura quanto geometria dos objetos, so capturados. Esses novos dados permitem que se v completando o modelo doobjeto em questo pouco a pouco, de acordo com um casamento realizado entre os dados que j faziam partedo modelo e os que so fornecidos a cada quadro do vdeo. Tal casamento fornecer um modelo tridimensi-

14

(a) (b)

(c) (d)

(e) (f)Figura 2.1: Sequncia de passos do sistema do IMPA. (a) Projeo de slides sobre objetos; (b) Padres

projetados; (c) Fronteiras das faixas identificadas; (d) Captura da textura; (e) Clculo daprofundidade; (f) Modelagem 3D.

VDEO 3D E VDEO 4D 15

captura segmentao rastreamento

registro integraoFigura 2.2: Etapas que constituram o trabalho do mestrado. As etapas consistiram na captura, seg-

mentao, rastreamento, registro e integrao.

onal do objeto, modelo esse que, em seguida, seria inserido novamente na cena, compondo o que chamamosde vdeo 4D reconstrudo.

De incio, portanto, deve-se estudar as diversas formas de se obter esse modelo 3D, composto por geo-metria e textura, a partir de conjuntos de nuvens de pontos ligeiramente diferentes entre si quando oriundasde quadros consecutivos do vdeo.

Com a insero do modelo tridimensional completo do objeto na cena e com a implementao de umainterface grfica, o usurio poder interagir com o vdeo, assistindo-o a partir de pontos de vista diferentesdaqueles em que se encontrava a cmera no momento da gravao da cena. importante enfatizar que nose trata apenas de uma mudana do ponto de vista em que o vdeo assistido: toda a geometria e a texturaque j foram reconstrudas baseando-se nos quadros gravados estar disponvel para visualizao.

H trs formas de se obter o vdeo 4D a partir de um vdeo 3 12 D:

Modo on-line: Tambm podendo ser chamado de modo em tempo real, a reconstruo do modelo feitaconcomitante captura. Conforme cada quadro do vdeo capturado pela cmera, o processamento j feito, permitindo que o usurio interaja com o vdeo 4D que est sendo construdo naquele mesmomomento.

Modo off-line: Semelhante ao modo on-line, com a diferena de que os quadros no esto sendo capturadosno mesmo momento. Em vez disso, o vdeo 4D construdo a partir dos quadros que vo sendo lidosa partir de um arquivo.

Modo em lote: Neste modo, todo o vdeo 4D reconstrudo e, somente depois, disponibilizado parainterao com o usurio, o qual usufruir de uma visualizao que contenha os dados obtidos de todosos quadros do vdeo.

H uma gradao na dificuldade dos problemas que podem ser enfrentados de acordo com os elementospresentes na captura de um vdeo 3D. Pode-se citar os seguintes exemplos:

Apenas o cenrio, sem objetos presentes. Este o caso mais simples. Um exemplo de aplicao seria odesenvolvimento de algoritmos que tentam inferir o caminho realizado pela cmera durante a grava-o.

16 REVISO BIBLIOGRFICA

Um objeto rgido. Envolve, como principal atividade, a reconstruo tridimensional completa de um mo-delo do objeto a partir de todas as imagens 2 12 D obtidas. Essa reconstruo exige que seja feitoo registro de nuvens de pontos de quadros subsequentes. Para a visualizao, pode-se aplicar umamalha sobre o volume.

Um objeto rgido mais o fundo da cena. Neste exemplo pode ser trabalhada a tarefa de segmentao eremoo do fundo, comum nos problemas de Viso Computacional.

Vrios objetos rgidos, com movimento relativo entre eles. Aqui, passa a ser interessante a identificaoe o rastreamento de cada objeto, incluindo casos de sobreposio e toque de um objeto no outro.

Um objeto rgido composto por partes articuladas. Principal caso que pode ser beneficiado com o avanodo mtodo de estimao de movimento desenvolvido.

Um objeto deformvel. H grande interesse em se trabalhar com faces, mos e corpo humano, os quaisconstituem um exemplo de objeto deformvel. Nesses casos, a adaptao e o casamento entre malhasde geometrias consecutivas no vdeo recebe um tratamento diferenciado, que j vem sendo tratado naliteratura.

A sequncia de etapas descrita possui diversos elementos em que se pode criar vontade. Pode-se, porexemplo, alterar o modelo (textura ou geometria) antes de inclu-lo na cena novamente.

Captulo 3

Metodologia

3.1 Perspectiva geral

Para o desenvolvimento do metodo apresentado, consideramos que as causas de mudanas em uma cenaso fruto do movimento de objetos presentes nesta. Outras opes seriam o movimento da cmera oumodificaes na iluminao [Klette et al., 1998].

Szeliski [2011] mostra que a complexidade do tipo de movimento a ser estimado pode variar considera-velmente. Uma vez que uma mtrica de erro tenha sido adotada, preciso escolher uma tcnica de buscaadequada. Pode-se, por exemplo, testar exaustivamente todos os possveis alinhamentos, ou seja, fazer umabusca completa. Na prtica, essa abordagem pode se mostrar muito lenta, de modo que tcnicas hierrquicasbaseadas em pirmides de imagens so normalmente usadas [Anandan, 1989; Bergen et al., 1992; Quam,1984]. Outra alternativa usar a transformada de Fourier para acelerar os clculos [Fleet & Jepson, 1990].Para movimentos mais complexos, modelos de movimento paramtrico por partes usando splines podem serusados [Kybic & Unser, 2003; Szeliski & Coughlan, 1997; Szeliski & Lavalle, 1996].

Segue que a verso mais geral (e desafiadora) de estimao de movimento a presena de movimentosmltiplos e independentes (e s vezes no-rgidos, como um tecido sendo balanado). Nesses casos, necessria a estimao do movimento independente de cada pixel, a qual conhecida como fluxo ptico.Isso normalmente envolve a minimizao da diferena entre o brilho ou a cor de pixels correspondentessomadas por toda a imagem [Szeliski, 2011]. Uma das abordagens clssicas para esse problema realizaro somatrio localmente sobre regies que se interceptam (abordagem baseada em blocos ou em janelas). justamente a busca por uma soluo para esse problema mais geral que motiva o mtodo que desenvolvemos.

Nem sempre o fluxo ptico pode ser identificado com deslocamentos locais. Como exemplo, considereuma esfera desprovida de textura em sua superfcie e que esteja rotacionando em torno de um eixo em frente cmera. Nenhum fluxo ptico poder ser observado, embora ocorra um movimento dos pontos do objeto.Por outro lado, para uma esfera esttica e mudanas nas condies de iluminao, um fluxo ptico poderser observado na superfcie da esfera, embora no haja movimento dos pontos em sua superfcie [Horn,1986; Klette et al., 1998].

Pode-se encarar a estimao de movimento como sendo um problema que envolve dois quadros, no qualo objetivo calcular o campo de movimento que alinha pixels de uma imagem com os de outra. Na prtica,a estimao de movimento usualmente aplicada a um vdeo, em que uma sequncia completa de quadrosest disponvel para realizar esta tarefa.

De acordo com Trucco & Verri [1998], podemos dividir o problema de movimento em dois subproble-mas:

Correspondncia: Quais elementos de um quadro correspondem a quais elementos do quadro seguinte deuma sequncia?

Reconstruo: Dado um nmero de elementos correspondentes e, possivelmente, o conhecimento dos pa-

17

18 METODOLOGIA

rmetros intrnsecos da cmera, o que ns podemos dizer sobre o movimento 3D e a estrutura domundo observado?

Para resolver o problema da correspondncia, pode-se usar duas estratgias:

Mtodos diferenciais: aplicam medidas densas, ou seja, calculadas em cada pixel da imagem. Tais mto-dos usam estimativas de derivadas no tempo e, portanto, requerem que as imagens da sequncia sejamamostradas bem prximas (no tempo) umas das outras.

Mtodos de casamento: aplicam medidas esparsas, ou seja, calculadas somente em um subconjunto dospontos das imagens. O filtro de Kalman exemplo de uma tcnica para casamento e rastreamento decaractersticas esparsas em imagens no decorrer do tempo.

O mtodo que desenvolvemos busca uma soluo para o problema da correspondncia e, apesar dacoincidncia no nome (o mtodo baseia-se no casamento entre grafos), trata-se de um mtodo diferencial(e no de casamento), pois calcula, para cada pixel, a diferena existente entre caractersticas que envolvemsua aparncia e sua posio no espao em relao aos outros pixels da imagem. Nossa abordagem usa comobase o reconhecimento estrutural de padres realizado por meio de casamento entre grafos.

3.2 Sequncia de etapas

O metodo proposto formado por uma sequncia de passos: aquisio de dados;

processamento da textura;

processamento do mapa de profundidade;

algoritmos de grafos;

visualizao dos dados.

O fluxo de dados esquematizado na Figura 3.1.

3.3 Dados de entrada

Nosso algoritmo recebe como entrada uma sequncia de pares de imagens registradas: textura colorida emapa de profundidade. A textura representada por trs canais (R, G e B) e o mapa de profundidade uma imagem em nveis de cinza, sendo tambm conhecido como canal D (do ingls depth , de profundi-dade). Assim, podemos dizer que a entrada de nosso algoritmo constitui-se de uma imagem de 4 canais, aqual vem sendo chamada na literatura como imagem RGBD. Uma vez que o mapa de profundidade captu-rado j est registrado com a imagem da textura, no h necessidade de conhecer os parmetros intrnsecose extrnsecos de calibrao entre o sensor de luz infra-vermelha e a cmera.

Alm de dados oriundos de um Kinect, o programa desenvolvido tambm aceita diversas outras fon-tes de entrada, tais como arquivos em formato de vdeo (AVI, MPEG, etc.), web-cam, arquivos de vdeo4D [Vieira et al., 2005] e sequncias de arquivos de imagens (BMP, JPEG, etc.). Isso pode facilitar a com-parao dos resultados (e eventualmente confirmar as vantagens) no uso da informao adicional do mapade profundidade com relao a abordagens que usam apenas a informao fornecida pela textura.

A opo de carregar sequncias de arquivos de imagens a partir do disco uma abordagem interessanteque ns adotamos para fazer processamento off-line. Isso pode ser necessrio em situaes nas quais osparmetros para os algoritmos implementados implicam em uma carga excessiva sobre a CPU, aumentandoassim o intervalo entre duas capturas consecutivas. Se o intervalo citado muito grande, a resoluo tempo-ral passa a ser muito pequena e uma grande gama de movimentos passa a ser despercebida. Para evitar que

19

Figura 3.1: Fluxo de dados atravs do mtodo implementado. A visualizao dos dados pode tanto serfeita nos resultados finais quanto a cada passo intermedirio.

20 METODOLOGIA

isso ocorra, ns podemos obter todos os dados desejados de uma s vez, gravando-os em disco sem realizarqualquer tipo de processamento, a fim de acelerar a etapa de aquisio; s ento que, numa fase posterior,podemos rodar o respectivo programa tendo essas imagens como entrada, carregando cada uma somentequando o seu processamento for necessrio no decorrer da execuo do mtodo.

Quando um dispositivo Kinect est disponvel, o mtodo desenvolvido tambm capaz de lidar com acaptura do mapa de disparidade, da textura em nveis de cinza, da imagem da cena iluminada com luz infra-vermelha e de uma mscara que indica onde o mapa de profundidade vlido. Uma vez que no usamosesses dados para processamento do mtodo desenvolvido, apenas a sua visualizao foi implementada.

O mapa de profundidade definido por um volume de visualizao, o qual, por sua vez, limitado pordois planos: um que mais prximo ao dispositivo de captura e outro que mais distante ao mesmo. Es-tes planos so conhecidos na literatura de Computao Grfica como plano prximo (znear) e plano distante(zfar). Se tomarmos znear = 1, zfar e invertermos o valor da cota dos pontos no mapa de profundidade,ento o terceiro canal desta nova imagem processada conter o inverso da profundidade, ou seja, a dispari-dade [Okutomi & Kanade, 1993]. Esta medida, tambm fornecida pelo Kinect e passvel de visualizao(como mapa de disparidade) no sistema desenvolvido, conveniente em diversos casos, uma vez que, paracmeras que se movem em cenas ao ar livre, o inverso da profundidade at a cmera frequentemente umaparametrizao mais estvel, em termos de aproximao numrica, que a distncia 3D.

3.3.1 Transformaes nos pixels

No decorrer de toda a sequncia de etapas que compem o mtodo desenvolvido, um operador didico (deduas entradas) representado por c (de custo) aplicado a cada par de pixels de um par de imagens RGBD.No domnio contnuo, isto pode ser denotado como:

c(pm, pi) = dRGB(pm, pi) + dXYZ(pm, pi), (3.1)

em que pm e pi so vetores que representam pixels em duas imagens RGBD consecutivas na captura dovdeo de entrada, e dRGB e dXYZ so funes que calculam distncias nos espaos RGB de cores e XYZ decoordenadas do mundo (no confundir com o espao XYZ de cores).

No caso das imagens com que trabalhamos, podemos considerar que o domnio d-dimensional da funoc d = 2, uma vez que as imagens so planares e cada pixel p pode ser identificado por suas coordenadas(x, y). Ainda, levando em conta que a imagem de profundidade registrada com a imagem de textura,temos que, para um pixel de coordenadas (x, y) na imagem de textura, podemos tanto obter o valor de suacor no espao RGB quando o valor de sua profundidade z na mesma coordenada (x, y), s que desta vezna imagem de profundidade. Assim, podemos considerar que, em vez de a entrada serem duas imagens,uma de textura e outra de profundidade, temos apenas uma imagem, porm com quatro canais. Nesta,alm dos trs canais RGB comuns, que representam sua cor, tambm teramos um quarto canal que, emvez de representar a transparncia, como normalmente usado na Computao Grfica, este canal passa arepresentar a profundidade (vide esquema na Figura 3.2).

Embora os valores sobre os quais o operador c atua sejam compostos pelos escalares R, G, B e D, todosos clculos so realizados em espaos vetoriais, sejam eles representativos de espaos de cores ou do espaofsico tridimensional.

Desta forma, o domnio e o contra-domnio do operador c que atua sobre cada pixel das imagens deentrada ficam bem definidos:

c : [0, 255]4 R (3.2)

3.3.2 Pr-processamento dos dados de entrada

O Kinect fornece um mapa de profundidade com 11 bits de preciso. Dessa forma, para que possamosvisualizar esse mapa como uma imagem em nveis de cinza, preciso normalizar os valores dos pixels parao intervalo [0, 255]. Empiricamente, encontrou-se o valor 0, 05 como um fator razovel.

PROCESSAMENTO DA TEXTURA 21

Figura 3.2: Imagem RGBD. O pixel p = (x, y) pertence a uma imagem com quatro canais. Com amesma coordenada (x, y) possvel acessar os valores dos canais R (red), G (green), B(blue) e D (depth).

3.4 Processamento da textura

Nosso metodo inclui a implementao de diversos processamentos da textura e dois deles so particular-mente importantes para obter os resultados desejados: reflexo na direo horizontal;

reduo da resoluo.

Ambos os processamentos so aplicados nas imagens da textura e do mapa de profundidade.A transformao de reflexo na direo horizontal usada por razes pragmticas: quando um usurio

interage com o sistema, mais fcil olhar para os resultados como se ele estivesse de frente para um espelho.Uma vez que o dispositivo de aquisio comumente posicionado em um local prximo tela do computa-dor, de frente para o usurio, uma reflexo na direo horizontal necessria para fazer com que interaesem tempo real tornem-se mais fceis.

O processamento de reduo da resoluo, alm de acelerar todos os clculos que so feitos, tambm muito relacionado a dois outros fatores:

a velocidade de cada objeto que se move;

a distncia, at o dispositivo de captura, de cada objeto que se move.

Essas duas quantidades interferem na preciso da deteco de movimento. Resolues baixas permitem ape-nas a deteco de movimentos que envolvem a modificao de muitos pixels nas imagens originais, uma vezque muitos pixels so representados por apenas um pixel na imagem de menor resoluo. Assim, o movi-mento ser percebido somente se o objeto localiza-se prximo ao dispositivo de captura ou se sua velocidade suficiente para envolver uma quantidade relativamente considervel de pixels em quadros consecutivos.

A reduo da resoluo da imagem foi implementada por meio da construo de blocos. Um bloco definido como sendo uma regio retangular na imagem, portanto permitindo blocos quadrados. Todos

22 METODOLOGIA

Figura 3.3: Volume de visualizao ou frustum: somente objetos presentes no interior do tronco depirmide (destacado na cor cinza e limitado pelos planos proximo e distante) que soprojetados no plano da imagem.

os pixels que pertencem a essa regio retangular tm seus valores (RGB ou de profundidade) alteradospara os respectivos valores do bloco, os quais sero explicados na prxima seo. A fim de simplificaresta converso, ns consideramos uma grade na qual a distncia entre linhas verticais definida comosendo o valor do comprimento do bloco e a distncia entre linhas horizontais o valor da altura do bloco.Ns no lidamos com multi-resoluo, de modo que os blocos possuem as mesmas dimenses por toda aimagem. Isto resulta em uma grade regular, igualmente espaada em cada direo. Por outro lado, o mtodoimplementado pode lidar perfeitamente com mudanas no tamanho dos blocos de um quadro a outro.

3.4.1 Clculo dos blocos mdiosComo pode ser inferido do ltimo pargrafo, h uma escolha importante a ser feita quando da construo deum bloco: seus valores RGB e de profundidade. Nosso mtodo permite duas opes:

1. os valores originais do pixel superior esquerdo de um bloco;

2. a mdia aritmtica dos valores de todos os pixels que compem o bloco.

Dentre os filtros usados, tambm encontra-se o da mediana, mas ele aplicado imagem que geradadepois de construir um grafo representativo do quadro; portanto, este filtro s ser comentado posterior-mente.

3.5 Processamento do mapa de profundidade

Processamentos realizados em mapas de profundidade so muito parecidos com os realizados em imagens detextura, uma vez que mapas de profundidade tambm so imagens. Assim, podemos explorar algumasvantagens pelo fato de que mapas de profundidade so imagens em nveis de cinza que podem ser vistascomo uma superfcie tridimensional.

Portanto, foi implementado um processamento do mapa de profundidade que permite escolher os dadosque esto cercados por dois limiares. Este processamento baseia-se somente na determinao destes doisparmetros, os quais determinam os planos prximo (corte frontal ou anterior) e o distante (corte traseiro ouposterior) do volume de visualizao (tambm conhecido como frustum, vide Figura 3.3). Com efeito, estesvalores controlam um ajuste fino na definio de um tronco de pirmide que restrito rea onde os objetosde interesse esto presentes. Na verdade, ns podemos precisamente remover o fundo e objetos que estomais prximos ao dispositivo de captura que os objetos-alvo. Com essa limiarizao de fundo e de frente,s so includos no grafo os pontos que fazem parte da geometria de interesse.

Na Figura 3.4 mostrada uma imagem da textura de uma cena que contm objetos em trs profundidadesdiferentes: o brao de uma pessoa segurando a moldura de um quadro frente, um beb no meio e a paredeao fundo. Podemos remover o fundo aproximando o plano distante (usamos o valor 93). Da mesma forma,

23

Figura 3.4: Controlando os limiares do volume de visualizao: a partir de uma imagem em que to-dos os elementos pictricos esto presentes dentro do frustum, possvel remover o fundo(aproximando o plano distante) ou remover objetos que se encontram mais prximos que ode interesse (afastando o plano prximo).

24 METODOLOGIA

Figura 3.5: Exemplo de mapeamento de textura sobre a disparidade colorizada. Cada imagem par-ticipa com 50% no valor RGB. Na imagem de disparidade, os valores das cores vo devermelho a azul, seguindo a ordem do espectro eletromagntico, conforme a distncia aodispositivo de captura aumenta.

o brao e a moldura podem ser removidos afastando o plano prximo (valor 47). Fazendo o mapeamentoda textura apenas nos pontos que pertencem ao volume de visualizao, conseguimos isolar o objeto deinteresse, causando uma melhora nos resultados e no desempenho de execuo. Note que, nas imagens debaixo na mesma figura, o valor 0 da profundidade, que visto como a cor preta, foi trocado por um padroquadriculado, comum em programas de processamento de imagens e que facilita a distino de reas emque no h contedo sendo exibido.

Tambm relacionado ao mapa de profundidade o mapeamento da textura. Este procedimento mapeia atextura no mapa de profundidade ou no mapa de disparidade, escolha esta que fica a critrio do usurio. Noteque, para que isso seja possvel, necessrio que uma das imagens esteja registrada com relao outra. Esteproblema foi resolvido e maiores detalhes tcnicos sobre a soluo adotada so descritos no Apndice A.

O resultado desse processamento da profundidade possui uma implicao muito importante na constru-o dos grafos, uma vez que, tendo sido o objeto de interesse bem delimitado pelos limiares comentados,elimina-se uma grande quantidade de dados que no so necessrios para a estimao do movimento. Nstambm podemos colorizar estas duas imagens em nveis de cinza a fim de obter uma melhor visualizaodos dados. O mapeamento da textura visa confirmar a acurcia do registro entre as imagens de textura eprofundidade ou entre as imagens de textura e disparidade. Embora ns no tenhamos desenvolvido umvisualizador que nos permita alterar o ponto de vista da cmera de modo que fosse possvel perceber facil-mente o correto alinhamento dos dados registrados, ns podemos confirmar esta caracterstica por meio damdia dos valores dos pixels das duas imagens, simulando uma transparncia, como um canal alfa (veja a Fi-gura 3.5). Com = 0, pixels do mapa de profundidade so totalmente transparentes (ou, equivalentemente,pixels da textura so totalmente opacos). J com = 1, ocorre o contrrio: so os pixels da textura (domapa de profundidade) que so totalmente transparentes (opacos). Com o controle fornecido pela interface

ABORDAGEM BASEADA EM GRAFOS 25

grfica, possvel variar suavemente entre os dois extremos.Alguns dos processamentos da textura e do mapa de profundidade podem ser aplicados em processos

paralelos, uma vez que so independentes entre si. Esta caracterstica pode acelerar o fluxo dos dados atravsda sequncia de etapas, principalmente porque uma grande variedade de mquinas modernas possui mais deuma CPU, CPUs com muitos ncleos ou at mesmo GPUs programveis com muitos ncleos. Apesar disso,ainda no paralelizamos nossos algoritmos e, portanto, atualmente, os dados seguem os passos apresentadoscomo uma sequncia serial de etapas.

3.6 Abordagem baseada em grafos

Com o objetivo de encontrar um casamento entre dois grafos, temos que levar em conta caractersticasrelevantes que descrevam os pontos e temos que ter um modo de comparar tais quantidades. Assim,cada quadro gera um grafo cujos vrtices so derivados de propriedades dos blocos. Ns usamos seis valorespara cada pixel nos dados de entrada: os dados RGB, extrados dos canais de cores, e os dados (x, y, z), comx e y sendo coordenadas da textura e z sendo a distncia do objeto ao dispositivo de captura. A representaodo quadro dada por um grafo de atributos relacionais (ARG, da sigla em ingls de Attributed RelationalGraph ), permitindo o armazenamento e a comparao de informao estrutural, temporal e quantitativa.O reconhecimento da direo do movimento feito atravs de um casamento inexato entre grafos. Estaabordagem permite diferenas entre o grafo modelo e o de entrada, tanto no conjunto de vrtices quanto noconjunto de arestas.

Um ARG um grafo cujos vrtices representam objetos enquanto suas arestas denotam relaes entreeles. Objetos podem ser caracterizados por um nmero finito de atributos (numricos ou simblicos), taiscomo rea, permetro, cor e forma. As relaes correspondem, na maioria das vezes, a uma medida dedistncia ou similaridade [Graciano, 2007]. Com o contedo de cada quadro sendo representado por umARG, a segmentao de movimento se resume a um casamento entre grafos, consistindo na determinaode um mapeamento de um conjunto de vrtices de um ARG no conjunto de vrtices de um outro.

Cada grafo tratado como um grafo completo, no sentido de que cada vrtice conectado com todosos outros vrtices. De fato, ns calculamos o valor de uma funo custo envolvendo a distncia entre osvalores RGBD de cada dois conjuntos de vrtices: (vm, vi), em que vm e vi so vrtices dos grafos modelo ede entrada, respectivamente. O par que minimiza o valor desta funo custo adicionado ao casamento.

Enquanto os vrtices de um grafo armazenam caractersticas de pontos, incluindo informaes sobre aposio destes pontos, por outro lado relaes estruturais so armazenadas nas arestas. No entanto, nestecaso, uma vez que tanto a informao estrutural quanto a de aparncia podem ser calculadas a partir dosdados armazenados em cada vrtice, as posies dos blocos na imagem so usadas para inferir o mdulo(tamanho) e a direo dos vetores nos espaos RGB e XYZ. Isso evita a necessidade de se armazenar dadosnas arestas da estrutura de dados que representa os grafos.

3.6.1 Construo dos grafos

Os grafos modelo e de entrada so construdos a partir de pares consecutivos de textura e de mapa deprofundidade dos quadros de entrada, conforme ilustrado na Figura 3.6. Logo, no incio do procedimentode aquisio, ns podemos construir apenas um grafo. Conforme os quadros seguintes so capturados, ografo de entrada relativo ao quadro imediatamente anterior atribudo ao grafo modelo e um novo grafo deentrada construdo a partir dos novos dados capturados.

Com o objetivo de construir o grafo, ns consideramos a representao das imagens de entrada (texturae mapa de profundidade) composta por blocos. Dados imagem e os parmetros dos blocos, ns podemoscalcular quantos blocos compem a nova representao, sendo suficiente para isso fazer a diviso entre onmero de linhas e colunas de cada um. Portanto, uma vez que a resoluo das imagens de entrada no sealtera, as dimenses dos blocos esto diretamente relacionadas com o tamanho dos grafos que so criados,influenciando fortemente no desempenho da aplicao.

26 METODOLOGIA

Figura 3.6: Construo e casamento de grafos a partir de quadros consecutivos. Cada grafo formadoa partir de uma imagem RGBD. O grafo que serviu de entrada no tempo t + 1 torna-se ografo modelo no tempo t + 2.

Cada bloco candidato a possuir um vrtice representativo no grafo, sendo eleito com base no valor desua profundidade (z). Somente se este valor pertence ao volume de visualizao definido anteriormente, naetapa de processamento do mapa de profundidade, um novo vrtice criado, tem seus campos preenchidoscom os dados do bloco e inserido no grafo. Uma consequncia desta abordagem que somente os pixelsque possuem valores de profundidade no-nulos so considerados. Assim, pixels que pertencem a reas desombra no mapa de profundidade ou que esto muito prximos ou muito longe do dispositivo de capturapara ter valores confiveis esto fora de escopo. Esta perspectiva trata o mapa de profundidade como umamscara de validao para os pixels da textura.

Uma vez que ns aplicamos a reduo da resoluo, os valores que compem os campos dos blocossempre podem ser obtidos a partir do pixel superior esquerdo, ainda que a opo de calcular os blocosmdios esteja ativada.

A estrutura de dados do grafo direcionado implementada por uma lista de adjacncia, na qual h umvetor de vrtices e, para cada vrtice, h uma lista de arestas de sada. Os dados armazenados nos vrticesincluem linha, coluna (ambos relacionados textura), cota (coordenada z, valor da imagem do mapa deprofundidade na mesma linha e coluna), valores dos canais vermelho, verde e azul da imagem de texturae um marcador de tempo, que indica o nmero de quadros capturados desde que o processo de captura foiiniciado.

3.6.2 Homomorfismo entre grafos

Com o intuito de se relacionar as imagens RGBD de dois quadros consecutivos e inferir o movimento reali-zado no intervalo entre as duas capturas, realiza-se o casamento entre dois grafos: o modelo e o de entrada.O grafo modelo representa o ltimo par de quadros (imagens de textura e de profundidade), capturados antesdos atuais, os quais so representados pelo grafo de entrada.

Um casamento um par ordenado de descritores de vrtices, com o primeiro se referindo a um vrticedo grafo modelo e o segundo relativo a um vrtice do grafo de entrada. Veja a Figura 3.7 para um exemplode casamento entre grafos.

ABORDAGEM BASEADA EM GRAFOS 27

Figura 3.7: Exemplo de casamento entre grafos. Note que este casamento um homomorfismo: todosos vrtices do grafo modelo so casados, h vrtices no grafo de entrada que no partici-pam de nenhum casamento e outros que participam mais de uma vez.

3.6.3 Casamento inexato entre grafos: Busca heurstica

A abordagem genrica, envolvendo grafos de deformaes, permite que o algoritmo adotado reduza ascomparaes estruturais a clculos de distncias entre pontos 3D [Noma et al., 2012].

Para cada vrtice pertencente ao grafo modelo, ns encontramos o vrtice no grafo de entrada que estejamais prximo de acordo com uma distncia medida por uma funo custo. Eventualmente, os vrticescasados possuem as mesmas coordenadas (x, y) de textura, indicando que no ocorreu movimento algumnaquele local entre os dois pares de quadros considerados.

3.6.4 Funo custo

A medida de erro escolhida uma funo custo c dada por uma mdia ponderada entre duas distncias: dRGBe dXYZ:

c = dRGB + (1 ) dXYZ, (3.3)com [0, 1]. O valor dRGB mede a distncia entre as cores dos blocos sendo comparados no espaoRGB, enquanto o valor dXYZ mede a distncia entre as coordenadas (x, y) da textura e entre os valores zde profundidade. Como pode ser visto, o parmetro controla o quanto cada distncia considerada novalor final da funo custo. Tomando valores de de 0 1, o valor de cada peso alterado de acordo.Este arranjo nos permite atribuir importncias diferentes para cada distncia calculada, enquanto a soma dospesos ainda permanece 1.

A funo custo c tambm pode ser vista como um operador didico de mistura linear de modo que,variando de 0 1, este operador realiza uma dissoluo cruzada temporal entre as duas imagens. Esteefeito muito visto em apresentaes de slides e em produes de filmes, ou como um componente dealgoritmos de morphing de imagens.

Ao calcular a funo custo, preciso decidir sobre qual funo de distncia usar. Foram implementadasduas delas: distncia do tipo quarteiro (city block ou Manhattan) e distncia Euclidiana. Aqui est afrmula da distn