Eder de Almeida Perez Descritor de movimento baseado em tensor e histograma de gradientes Dissertação apresentada ao Programa de PoÌs-graduação em Modelagem Computacional, da Universidade Federal de Juiz de Fora como requisito parcial aÌ€ obtenção do grau de Mestre em Modelagem Computacional. Orientador: Prof. D.Sc. Marcelo Bernardes Vieira Juiz de Fora 2012 Perez, Eder de Almeida. Descritor de movimento baseado em tensor e histograma de gradientes / Eder de Almeida Perez. – 2012. 61 f. : il. Dissertação (Mestrado em Modelagem Computacional)–Universidade Federal de Juiz de Fora, Juiz de Fora, 2012. 1.Ciência da computação. 2. Inteligência artificial. 3. Tensores. 4. Visão computacional. 4. Aprendizagem. I. TÃtulo. CDU 681.3 Eder de Almeida Perez Descritor de movimento baseado em tensor e histograma de gradientes Dissertação apresentada ao Programa de PoÌs-graduação em Modelagem Computacional, da Universidade Federal de Juiz de Fora como requisito parcial aÌ€ obtenção do grau de Mestre em Modelagem Computacional. Aprovada em 24 de Agosto de 2012. BANCA EXAMINADORA Prof. D.Sc. Marcelo Bernardes Vieira - Orientador Universidade Federal de Juiz de Fora Prof. D.Sc. Esteban Walter Gonzalez Clua Universidade Federal Fluminense Prof. D.Sc. Carlos Cristiano Hasenclever Borges Universidade Federal de Juiz de Fora Dedico este trabalho aÌ€ minha esposa NataÌlia, aos meus pais, irmã e amigos. AGRADECIMENTOS Agradeço primeiramente aÌ€ minha esposa NataÌlia pelo apoio incondicional durante todo mestrado e por ter sacrificado alguns finais de semana em prol da cieÌ‚ncia. Aos meus pais e aÌ€ minha irmã por estarem ao meu lado e permitirem que eu chegasse ateÌ aqui. AÌ€ minha sogra e meu sogro que sempre torceram pelo meu sucesso e sempre me incentivaram nos momentos difÌıceis. Aos meus grandes amigos Peçanha, TaÌssio, Thales e Scoralick que são verdadeiros irmãos com quem eu sempre posso contar. Ao meu orientador Marcelo Bernardes por todo ensinamento me dado durante esses longos anos de GCG. AÌ€ futura doutora VirgÌınia Mota pelo apoio nesse trabalho e nas publicações oriundas dele. AÌ€ ENSEA-UCP pelo ambiente RETIN SVM sem o qual esse trabalho não seria possÌıvel. AÌ€ UFJF e ao Grupo de Computação GraÌfica onde eu tive a oportunidade de adquirir grande conhecimento e foi responsaÌvel pela minha formação profissional. Agradeço tambeÌm ao Luiz MaurÌılio pela enorme ajuda nos testes experimentais e a todos os membros do GCG pelos momentos de trabalho e diversão. Aos membros da banca por terem aceitado o convite e por suas contribuições. Aos professores do Mestrado em Modelagem Computacional e aos companheiros de turma. AÌ€ CAPES pelo suporte financeiro. â€Ser eÌ ser percebido†George Berkeley RESUMO O reconhecimento de padrões de movimentos tem se tornado um campo de pesquisa muito atrativo nos uÌltimos anos devido, entre outros fatores, aÌ€ grande massificação de dados em vÌıdeos e a tendeÌ‚ncia na criação de interfaces homem-maÌquina que utilizam expressões faciais e corporais. Esse campo pode ser considerado um dos requisitos chave para anaÌlise e entendimento de vÌıdeos. Neste trabalho eÌ proposto um descritor de movimentos baseado em tensores de 2a ordem e histogramas de gradientes (HOG - Histogram of Oriented Gradients). O caÌlculo do descritor eÌ raÌpido, simples e eficaz. AleÌm disso, nenhum aprendizado preÌvio eÌ necessaÌrio sendo que a adição de novas classes de movimentos ou novos vÌıdeos não necessita de mudanças ou que se recalculem os descritores jaÌ existentes. Cada quadro do vÌıdeo eÌ particionado e em cada partição calcula-se o histograma de gradientes no espaço e no tempo. A partir daÌı calcula-se o tensor do quadro e o descritor final eÌ formado por uma seÌrie de tensores de cada quadro. O descritor criado eÌ avaliado classificando-se as bases de vÌıdeos KTH e Hollywood2, utilizadas na literatura atual, com um classificador MaÌquina Vetor Suporte (SVM). Os resultados obtidos na base KTH são proÌximos aos descritores do estado da arte que utili- zam informação local do vÌıdeo. Os resultados obtidos na base Hollywood2 não superam o estado da arte, mas são proÌximos o suficiente para concluirmos que o meÌtodo proposto eÌ eficaz. Apesar de a literatura apresentar descritores que possuem resultados superiores na classificação, suas abordagens são complexas e de alto custo computacional. Palavras-chave: Descritor de movimento. Tensor de 2a ordem. SeÌrie de tensores. SVM. Histograma de gradientes. Modelagem do movimento. ABSTRACT The motion pattern recognition has become a very attractive research field in recent years due to the large amount of video data and the creation of human-machine interfaces that use facial and body expressions. This field can be considered one of the key requirements for analysis and understanding in video. This thesis proposes a motion descriptor based on second order tensor and histograms of oriented gradients. The calculation of the descriptor is fast, simple and effective. Furthermore, no prior knowledge of data basis is required and the addition of new classes of motion and videos do not need to recalculate the existing descriptors. The frame of a video is divided into a grid and the histogram of oriented gradients is computed in each cell. After that, the frame tensor is computed and the final descriptor is built by a series of frame tensors. The descriptor is evaluated in both KTH and Hollywood2 data basis, used in the current literature, with a Support Vector Machine classifier (SVM). The results obtained on the basis KTH are very close to the descriptors of the state-of-the-art that use local information of the video. The results obtained on the basis Hollywood2 not outweigh the state-of-the-art but are close enough to conclude that the proposed method is effective. Although the literature presents descriptors that have superior results, their approaches are complex and with computational cost. Keywords: Motion descriptor. Second order tensor. Series of tensors. SVM. Histogram of oriented gradients. Motion modeling. SUMAÌRIO 1 INTRODUÇÃO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1 Definição do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Contribuições e Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 Descritores baseados em histogramas de gradientes . . . . . . . . . . . . . 14 1.4.2 Descritores baseados em tensores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.3 Descritores globais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 FUNDAMENTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1 MaÌquina Vetor Suporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 SIFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Histograma de gradientes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Tensor de 2a ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 DESCRITOR DE MOVIMENTO PROPOSTO. . . . . . . . . . . . . . . . . . . . . . . 26 3.1 Gradiente espaço-temporal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Particionamento do quadro e histograma de gradientes . . . . . . . . . . . . 28 3.3 Criação dos tensores de 2a ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.1 Tensor de um quadro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.2 Tensor final de um vÌıdeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.3 Reflexão do tensor para captura de simetrias. . . . . . . . . . . . . . . . . . . 31 3.4 Minimizando o efeito da variação de brilho . . . . . . . . . . . . . . . . . . . . . . . . 31 4 RESULTADOS E ANAÌLISE COMPARATIVA . . . . . . . . . . . . . . . . . . . . . . . 33 4.1 Base de vÌıdeos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Resultados na base KTH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.1 Reflexão do quadro para o caÌlculo do histograma . . . . . . . . . . . . . . . 38 4.2.2 Usando limiarização da norma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.3 Combinando limiarização e reflexão . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2.4 Efeito do uso da função gaussiana na ponderação dos gradientes das partições. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3 Resultados na base Hollywood2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3.1 Reflexão do quadro para o caÌlculo do histograma . . . . . . . . . . . . . . . 47 4.3.2 Efeito do uso da função gaussiana na ponderação dos gradientes das partições. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4 Comparação com descritores da literatura . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 REFEREÌ‚NCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 11 1 INTRODUÇÃO Um dos primeiros estudos sobre a natureza do movimento foi feito pelo cientista franceÌ‚s EÌtienne-Jules Marey no seÌculo XIX. Sua ideia original foi registrar as vaÌrias etapas do movimento em uma uÌnica fotografia (Figura 1.1). Essas fotografias eram tiradas em um instrumento conhecido como fuzil cronofotograÌfico, capaz de produzir 12 quadros consecutivos em uma uÌnica imagem. Esses estudos revelaram aspectos interessantes na locomoção de animais e seres humanos [1]. Na deÌcada de 70, o cientista Gunnar Johansson realizou um experimento que consistia na colocação de pontos refletores de luz dispostos nas juntas de um modelo humano cujos movimentos eram capturados por uma caÌ‚mera de vÌıdeo [2]. AtraveÌs desse experimento, conhecido como MLD (Moving Light Display), ele foi capaz de realizar estudos a respeito da percepção visual de padrões de movimentos. O trabalho de Johansson despertou grande interesse da neurocieÌ‚ncia no estudo e anaÌlise da percepção do movimento [1], abrindo caminho para a modelagem matemaÌtica de movimentos e reconhecimento automaÌtico que, naturalmente, envolve o campo da visão computacional e reconhecimento de padrões. Figura 1.1: Voo de um pelicano. Foto tirada por EÌtienne-Jules Marey por volta de 1882 (domıÌnio puÌblico). O avanço tecnoloÌgico nos dispositivos de captura de imagem e vÌıdeo e a popularização 12 de sites de compartilhamento deste tipo de mıÌdia na internet, fez com que a pesquisa em reconhecimento de movimentos crescesse muito nos uÌltimos anos. Algumas aÌreas de aplicação são [1]: • Biometria Comportamental: A biometria envolve o reconhecimento de pessoas atraveÌs de caracterÌısticas fisioloÌgicas como ıÌris e impressões digitais. Mais recentemente, ca- racterÌısticas comportamentais como o modo de agir e se movimentar tem atraÌıdo grande interesse nessa aÌrea. Diferentemente das caracterÌısticas fisioloÌgicas, eÌ possÌıvel capturar informações que identificam um indivÌıduo sem a necessidade de interação com o mesmo ou interrompendo suas atividades. Com isso, o reconhecimento de movimentos em vÌıdeos desempenha papel fundamental nessa tarefa. [3] • AnaÌlise de vÌıdeo baseada em conteuÌdo: Existem hoje inuÌmeros sites de compar- tilhamento de vÌıdeos na internet. A classificação e armazenagem dessas mıÌdias necessitam de meÌtodos eficientes para que seja possÌıvel fazer buscas raÌpidas e au- mentar a experieÌ‚ncia do usuaÌrio. Tudo isso requer o aprendizado de padrões em vÌıdeos classificando-os a partir de seu conteuÌdo. [4] [5] • Segurança e VigilaÌ‚ncia: Sistemas de segurança e vigilaÌ‚ncia geralmente contam com diversas caÌ‚meras espalhadas em locais estrateÌgicos e um ou mais operadores moni- torando cada uma delas em busca de ações suspeitas. Quanto mais caÌ‚meras, mais suscetÌıvel aÌ€s falhas humanas torna-se o sistema. Tais falhas podem ser minimiza- das atraveÌs de sistemas de visão capazes de reconhecer ações suspeitas de maneira automaÌtica. [6] [7] • Aplicações Interativas e Ambientes: A interação entre humanos e computadores atraveÌs de comunicação visual eÌ um grande desafio no projeto de interfaces homem- maÌquina. O reconhecimento eficiente de gestos e expressões faciais pode ajudar a criar computadores que interagem de forma faÌcil e raÌpida com pessoas. [8] • Animação e sÌıntese: A induÌstria de jogos e cinema faz uso intenso de sistemas de captura para sÌıntese realÌıstica de movimentos em modelos tridimensionais. O avanço dos algoritmos e hardware torna a sÌıntese de movimentos cada vez mais realista [9]. Antes de partirmos para definição do presente problema, faremos aqui algumas de- finições baÌsicas: 13 Definição 1.0.1 (Imagem). Uma imagem I pode ser definida como uma função (Gomes e Velho [10]): I : U ⊂ <2 → <n, onde U eÌ um conjunto suporte, ou seja, uma região onde a função toma valores e <n eÌ o espaço de cores associado a cada ponto da imagem. Definição 1.0.2 (VıÌdeo). Um vÌıdeo s nada mais eÌ do que uma sequeÌ‚ncia de imagens1: s : [U ⊂ <2]×< → <n, que representa uma imagem I em um determinado tempo t ∈ <. Cada imagem em um vÌıdeo eÌ chamada de quadro. 1.1 Definição do problema Dados vÌıdeos s1 e s2 em um espaço de vÌıdeos S, queremos encontrar uma função f f : S → <m, onde <m eÌ um espaço euclidiano de descritores, tal que, se s1 e s2 conteÌm movimentos similares, seus descritores são proÌximos segundo a norma euclidiana. 1.2 Objetivos O objetivo deste trabalho eÌ apresentar um descritor de movimentos em vÌıdeos sem que nenhuma informação preÌvia ou aprendizado de uma base seja necessaÌrio. EÌ primordial tambeÌm que se utilizem poucos paraÌ‚metros e haja alto desempenho no tempo de caÌlculo dos descritores. A abordagem escolhida combina tensores de 2a ordem e histogramas de gradientes na geração dos descritores utilizando informação de todo o quadro. Gradi- entes de imagens são bons estimadores de movimento. Eles representam a direção de maÌxima variação de brilho em um ponto da imagem, sendo usados, por exemplo, por 1Não estamos considerando aqui vÌıdeos com aÌudio 14 diversos meÌtodos para o caÌlculo do fluxo oÌptico [11]. Por outro lado, tensores são pode- rosas ferramentas matemaÌticas que vem sendo exploradas em diversas aÌreas da cieÌ‚ncia. Tensores derivados dos gradientes na vizinhança de um ponto de uma imagem sinteti- zam suas direções predominantes, podendo-se explorar essa caracterÌıstica na descrição de movimentos. Muitos trabalhos calculam pontos caracterÌısticos, entre outras informações locais da imagem, para geração dos descritores (abordagem local). Isso torna o problema mais complexo de ser resolvido e aumenta o custo computacional. Neste trabalho os descritores são gerados utilizando toda informação do quadro (abordagem global), sendo mais simples e menos custoso computacionalmente. AleÌm disso, a inserção de novos vÌıdeos ou categorias não requer que se recalcule ou modifique os descritores gerados previamente. 1.3 Contribuições e Publicações A principal contribuição deste trabalho estaÌ em combinar histogramas de gradientes com tensores de 2a ordem para gerar descritores de movimentos simples, poreÌm efetivos. O descritor eÌ simples devido aÌ€ baixa complexidade de tempo e espaço, necessitando de poucos paraÌ‚metros e gerando um descritor compacto que eÌ calculado de maneira raÌpida se comparado aÌ€ outros descritores. EÌ efetivo porque consegue resultados competitivos em relação aÌ€s abordagens locais da literatura. Este trabalho gerou uma publicação no International Conference on Pattern Recogni- tion 2012 entitulada Combining gradient histograms using orientation tensors for human action recognition [12]. 1.4 Trabalhos relacionados São apresentados aqui alguns trabalhos sobre descritores de movimentos utilizando ten- sores e/ou histogramas de gradientes, aleÌm de alguns trabalhos sobre descritores globais. 1.4.1 Descritores baseados em histogramas de gradientes Em [13], Lowe apresenta um novo meÌtodo de reconhecimento de objetos em imagens usando caracterÌısticas locais. Essas caracterÌısticas são invariaÌveis aÌ€ escala, translação, 15 rotação e, parcialmente invariaÌveis aÌ€s mudanças de brilho e projeções afins [13]. Chamado de Scale Invariante Feature Transform ou SIFT, esse meÌtodo transforma uma imagem em uma grande coleção de vetores de caracterÌısticas locais. Um dos estaÌgios na criação desses vetores eÌ a geração de descritores a partir do gradiente local da imagem. Esses descritores são gerados por histogramas de gradientes e são altamente distintivos, permitindo que um vetor de caracterÌısticas encontre, com alta probabilidade, seu correspondente em uma base de caracterÌısticas. Apesar de não ser um descritor de movimentos, o trabalho de Lowe inspirou diversos trabalhos voltados para descrever movimentos em vÌıdeos. PoreÌm, seu desempenho em vÌıdeos não eÌ muito bom, pois eÌ necessaÌrio a geração dos vetores de caracterÌısticas em cada quadro, exigindo alto custo computacional. Laptev [14] estende meÌtodos conhecidos de reconhecimento em imagens para o domıÌnio espaço-temporal a fim de classificar movimentos em vÌıdeos. Para caracterizar o movi- mento, ele calcula histogramas em volumes espaço-temporais na vizinhança de pontos de interesse. Cada volume eÌ subdividido em um conjunto de cuboides e para cada cu- boide calculam-se histogramas de gradientes (HOG) e de fluxo oÌptico (HOF - Histogram of Optical Flow). Os histogramas são normalizados e concatenados em um descritor similar ao usado no SIFT [13]. Dado um conjunto desses descritores, eÌ criado um bag-of- features (BoF) utilizado na posterior classificação. Bag-of-features podem ser utilizados na classificação de imagens. A ideia eÌ representar uma imagem atraveÌs de um conjunto de descritores locais que não possuem relação de ordem entre si. EÌ anaÌlogo ao bag-of- words (BoW) em que um documento de texto eÌ representado como um histograma das frequeÌ‚ncias de cada palavra (perdendo a relação de ordem entre as palavras - daÌı o termo “bagâ€). O uso de BoF requer a criação de um dicionaÌrio a partir de uma base de treino, tornando necessaÌrio um aprendizado preÌvio. Kläser et al. [15] apresenta um descritor espaço-temporal baseado em HOG em treÌ‚s dimensões. Em seu trabalho, os histogramas de orientação são quantizados em poliedros regulares onde cada face do poliedro representa um intervalo de classe do histograma. 1.4.2 Descritores baseados em tensores Kim et al. [16] introduzem um novo meÌtodo chamado Tensor Canonical Correlation Analysis (TCCA) que eÌ uma extensão do claÌssico Canonical Correlation Analysis (CCA2) 2Uma ferramenta padrão para inspeção de relações lineares entre dois conjuntos de vetores [17, 18] 16 para tensores e o aplicam para a classificação de ações/gestos em vÌıdeos. Nesse meÌtodo, caracterÌısticas de similaridade entre dois vÌıdeos são produzidas atraveÌs de relações line- ares e combinadas com um seletor discriminativo de caracterÌısticas e um classificador por “vizinho mais proÌximo†(nearest neighbor) para classificação de ações. PoreÌm, o meÌtodo exige alta demanda computacional caso movimentos similares entre dois vÌıdeos não estejam alinhados no espaço e no tempo. Krausz e Bauckhage [19] fazem o reconhecimento de ações baseado na ideia da fato- rização de tensores não-negativos. Eles consideram uma sequeÌ‚ncia de vÌıdeo como um ten- sor de terceira ordem e aplicam uma fatoração não negativa de tensores a essa sequeÌ‚ncia. Dessa fatoração são extraÌıdas imagens base cuja combinação linear geram os quadros da sequeÌ‚ncia. Dado um conjunto de vÌıdeos de teste, determina-se um conjunto de imagens base que representam diferentes partes da silhueta do objeto em movimento. Uma vez que diferentes combinações lineares dessas bases codificam diferentes poses, uma sequeÌ‚ncia particular de poses corresponde a uma sequeÌ‚ncia particular de coeficientes lineares. O re- conhecimento eÌ feito aplicando esse mecanismo a diferentes partes de um quadro. Como as imagens base são geradas previamente por uma base, eÌ necessaÌrio gerar novas imagens a cada vez que um novo padrão de movimentos eÌ inserido. Jia et al. [20] apresentam um meÌtodo de reconhecimento de ações usando anaÌlise ten- sorial e caracterÌısticas em multiescala. Nesse meÌtodo, uma seÌrie de silhuetas formam uma imagem chamada de Serials-Frame (SF). Assim, uma ação fica representada atraveÌs de poses contÌınuas em uma imagem. A imagem SF eÌ então associada a um auto-espaço de tensores chamado SF-Tensor (Serials-Frame Tensor). EÌ atraveÌs da anaÌlise desse espaço que são extraÌıdas informações para o reconhecimento de diferentes tipos de ações. As- sim como em [19], silhuetas representando um movimento são geradas previamente por uma base, resultando no mesmo problema quando necessaÌrio inserir novos padrões de movimento. Khadem et al. [21], assim como em [20], utiliza tensores de terceira ordem a partir de silhuetas de um conjunto de testes. O tensor formado compreende treÌ‚s modos que são: pixels, ações e pessoas. São encontrados os coeficientes no espaço de ações bem como o operador de projeção. A sequeÌ‚ncia a ser consultada eÌ projetada no espaço de ações e o vetor resultante eÌ comparado aos vetores aprendidos para encontrar a classe correspondente aÌ€ ação. 17 Kihl et al. [22] utiliza informação de movimento atraveÌs do fluxo oÌptico. O campo vetorial gerado pelo caÌlculo do fluxo eÌ projetado em uma base ortogonal de polinoÌ‚mios e uma medida de similaridade eÌ criada usando o maior autovalor do tensor da projeção dos valores dos campos vetoriais. O custo computacional para a projeção do fluxo oÌptico na base de polinoÌ‚mios tende a aumentar consideravelmente na medida em que se aumenta o nuÌmero de coeficientes da base. Mota [23] propõe um descritor global de movimento baseado em um tensor de ori- entação. Esse tensor, assim como em [22], tambeÌm eÌ extraÌıdo da projeção do fluxo oÌptico em uma base ortogonal de polinoÌ‚mios. 1.4.3 Descritores globais Zelnik-manor e Irani [24] desenvolvem um descritor global baseado em histogramas de gradientes. O descritor eÌ obtido extraindo-se escalas multitemporais atraveÌs da construção de uma piraÌ‚mide temporal. Para cada escala, o gradiente de cada pixel eÌ calculado. Então, um HOG eÌ criado para cada vÌıdeo e comparado com outros histogramas para classificar a base de dados. Assim, dois movimentos serão considerados similares se seus histogramas, em uma mesma escala, são similares. Os testes foram realizados na base Weizmann. Laptev et al [25] aplicam o descritor global de Zelnik-manor [24] na base KTH de duas maneiras: usando escalas multitemporais, como o original e usando escalas multitemporais e multiespaciais. 18 2 FUNDAMENTOS Neste capÌıtulo são apresentados os fundamentos os quais o descritor proposto se baseia. EÌ feita uma introdução aÌ€ MaÌquina Vetor Suporte, teÌcnica utilizada na classificação dos descritores gerados em cada base de vÌıdeos testada. Não nos aprofundaremos no estudo do SVM porque foge do escopo deste trabalho. A ideia eÌ apenas usaÌ-las para classificar os descritores gerados e testar a qualidade dos mesmos na discriminação de movimentos. Sendo assim, na seção 2.1 eÌ feita uma introdução desta ferramenta. Na seção 2.2 eÌ introduzido o meÌtodo SIFT, um algoritmo para detectar e descrever caracterÌısticas locais em imagens. Uma das etapas desse meÌtodo eÌ gerar um descritor baseado em histograma de gradientes. Os histogramas de gradientes usados na criação do descritor proposto nesta dissertação são baseados especificamente nessa etapa. Por fim, nas seções 2.3 e 2.4 são apresentados o histograma de gradientes (HOG) e tensores de 2a ordem. EÌ com base nessas duas ferramentas que o descritor proposto eÌ criado. 2.1 MaÌquina Vetor Suporte Uma maÌquina vetor suporte (SVM) eÌ uma teÌcnica de aprendizado supervisionado que utiliza algoritmos de aprendizado para analisar dados e reconhecer padrões. Basicamente, o SVM pega um conjunto de dados de entrada e preveÌ‚ a qual de duas possÌıveis classes cada um deles pertence. A partir de um conjunto de treino, onde um dado eÌ marcado como pertencente a uma de duas categorias distintas, a etapa de aprendizado do SVM constroÌi um modelo que associa cada dado a uma ou outra categoria. Um SVM pode classificar dados linearmente separaÌveis ou não linearmente separaÌveis. No caso linear, dado um conjunto de treino X de vetores de caracterÌısticas xi, com i = 1, 2, 3, . . . , N , que pertencem a uma de duas classes ω1 ou ω2 linearmente separaÌveis [26], o objetivo eÌ encontrar o hiperplano g(x) = wTx+w0 = 0 que classifica corretamente todos os vetores de X. A Figura 2.1 mostra um exemplo de uma solução para um dado conjunto de dados. Observe que o hiperplano h(x) tambeÌm consegue dividir as classes dos dados de treino de forma correta, poreÌm, o hiperplano g(x) consegue essa divisão com mais “folga†19 permitindo que um conjunto submetido aÌ€ classificação possa ter uma margem de variação maior sem que seja classificado de forma incorreta (Figura 2.2). h(x) g(x) Figura 2.1: Exemplo de duas classes separaÌveis linearmente e os hiperplanos g(x) e h(x) que as separam. h(x) g(x) Figura 2.2: Dados classificados utilizando os hiperplanos da Figura 2.1. Observe que o hiperplano h(x) permitiu que dois vetores fossem classificados incorretamente enquanto que g(x) permitiu uma correta classificação. Quando as classes não são separaÌveis linearmente (Figura 2.3), não eÌ possÌıvel encontrar 20 um hiperplano que divida os vetores em duas classes distintas. Neste caso, uma função não linear f eÌ usada para levar o conjunto de vetores a uma dimensão maior onde eÌ possÌıvel separaÌ-los por um hiperplano (Figura 2.4). Existem diversas funções que cumprem esse papel, chamadas nuÌcleo ou kernel, e o resultado da classificação pode variar de acordo com a escolha da função, como visto em [23]. Figura 2.3: Não existe um hiperplano que divida os vetores em duas classes distintas. f Figura 2.4: Os vetores são levados a uma dimensão maior por uma função f onde eÌ possÌıvel separaÌ-los linearmente. O SVM classifica os dados em duas classes distintas, mas pode-se fazer uma clas- sificação multiclasse considerando o problema, por exemplo, como um conjunto de M 21 classes dois a dois (abordagem conhecida como um contra todos) [26]. Nessa abordagem, para cada uma das classes, o objetivo eÌ conseguir uma função gi(x), i = 1, 2, . . . ,M tal que gi(x) > gj(x),∀j 6= i, se x ∈ ωi. Pode-se então projetar funções discriminantes tal que gi(x) = 0 eÌ o hiperplano otimal separando a classe ωi de todas as outras. Assim, cada classificador eÌ projetado para ter gi(x) > 0 para x ∈ ωi e gi(x) < 0 caso contraÌrio. A classificação eÌ então alcançada de acordo com a regra: i = arg max{gk(x)} ⇒ x ∈ ωi (2.1) k 2.2 SIFT SIFT (Scale-Invariant Feature Transform) eÌ um meÌtodo para extrair caracterÌısticas dis- tintas e invariantes em imagens, podendo ser usado para detecção de objetos ou cenas em diferentes imagens [27]. O vetor de caracterÌısticas calculado eÌ invariante aÌ€ mudança de escala e rotação e parcialmente invariante aÌ€ distorções afins, adição de ruÌıdo e mudanças de iluminação. Segundo Lowe, esse vetor possui certo nuÌmero de propriedades em comum com as respostas dos neuroÌ‚nios do coÌrtex inferior temporal dos primatas, responsaÌvel pelo reconhecimento de objetos no sistema de visão desses animais. O caÌlculo dos vetores de caracterÌısticas eÌ feito em etapas. Primeiramente, deseja- se encontrar pontos no espaço de escalas que sejam invariantes aÌ€ rotação, translação, escalamento e que sofram o mıÌnimo de influeÌ‚ncia de ruÌıdos e distorções. Isso eÌ feito identificando pontos chave atraveÌs de maÌximos e mıÌnimos encontrados em funções geradas por diferenças de gaussianas, que nada mais são do que uma subtração entre duas imagens com um filtro gaussiano aplicado com valores diferentes de σ para cada uma delas. Em seguida, eÌ feita uma varredura de informações na vizinhança dos pontos localiza- dos. Assim, pontos que tem baixo contraste (suscetÌıveis a ruÌıdos) ou mal localizados em bordas são rejeitados e os pontos mantidos são chamados pontos chave (keypoint). O proÌximo passo eÌ associar uma orientação aos pontos chave baseado nas propriedades locais da imagem, tornando-o assim, invariante aÌ€ rotação. Isso eÌ feito calculando-se os vetores gradientes numa vizinhança do ponto chave e acumulando-os num histograma de gradientes. O pico desse histograma indica a tendeÌ‚ncia de orientação dos gradientes e seraÌ a orientação do ponto. 22 Os passos anteriores tratam da invariaÌ‚ncia quanto aÌ€ localização, escala e rotação de um ponto chave. A uÌltima etapa calcula um descritor para cada ponto de modo que ele seja altamente distintivo e parcialmente invariante aÌ€ iluminação, mudanças de caÌ‚mera, etc. Primeiro um conjunto de histogramas de gradientes, com oito intervalos de classe cada, eÌ criado em uma vizinhança de 4 × 4 pixels. Esses histogramas são calculados a partir dos valores da magnitude e orientação de amostras de 16 × 16 regiões ao redor do ponto chave, de forma que cada histograma conteÌm amostras de uma sub-região de 4 × 4 pixels da vizinhança original da região. As magnitudes são ponderadas por uma função gaussiana com metade da largura da janela do descritor. O descritor então se torna um vetor com todos os valores dos histogramas. A Figura 2.5 exemplifica esse processo. O descritor eÌ então normalizado a fim de aumentar a invariaÌ‚ncia de mudanças lineares de iluminação. Para reduzir os efeitos de mudanças não lineares um limiar de 0, 2 eÌ aplicado ao vetor que eÌ novamente normalizado. Esse valor de 0, 2 foi determinado experimentalmente e o autor ([27]) não daÌ informações detalhadas de como foi obtido. Gradientes da imagem Descritor Figura 2.5: Exemplo de um descritor de um ponto no SIFT. Calcula-se o gradiente em cada ponto (imagem da esquerda) e pondera-se com uma janela gaussiana (indicada pelo cÌırculo). Os gradientes são então acumulados em histogramas (imagem da direita) onde o comprimento de cada vetor corresponde aÌ€ soma das magnitudes dos gradientes com orientação similar. O exemplo utiliza um descritor 2 × 2 calculado em uma janela 8 × 8 para melhor visualização. 23 2.3 Histograma de gradientes O gradiente do j -eÌsimo quadro de um vÌıdeo em um ponto p eÌ dado por, [ ] ∇ ≡ ∂Ij(p) ∂Ij(p) ∂Ij(p)Ij(p) , , , (2.2) ∂x ∂y ∂t ou, equivalentemente, em coordenadas esfeÌricas, ∇Ij(p) ≡ [Ïp, θp, Ï•p] , (2.3) onde θp ∈ [0, Ï€], Ï•p ∈ [0, 2Ï€] e Ïp = ‖∇Ij(p)‖. Este vetor aponta para a direção de maior variação de I no ponto p, o que pode indicar informação local de movimento. Um histograma de gradientes (HOG) eÌ uma distribuição das frequeÌ‚ncias de gradientes de um quadro ou imagem. Foi proposto por Dalal e Triggs [28], inicialmente utilizado para detecção de pessoas em imagens por ser um bom descritor de caracterÌısticas. A Figura 2.6 mostra um exemplo de um histograma de gradientes bidimensional subdi- vido em seis intervalos. Cada intervalo guarda a soma das magnitudes de todos os vetores pertencentes ao mesmo. Por exemplo, a frequeÌ‚ncia em [120o, 180o) eÌ a soma das magni- tudes dos dois vetores desse intervalo. De fato, um histograma bidimensional pode ser visto como uma aproximação de um cÌırculo por um polÌıgono, onde cada lado do polÌıgono corresponde a um intervalo de classe do histograma. Isso pode ser estendido para o caso tridimensional aproximando-se uma esfera por poliedros. Uma vez que estamos interes- sados em gradientes espaço-temporais, o histograma de gradientes tridimensionais hk,l com k ∈ [1, bθ] e l ∈ [1, bÏ•], sendo bθ e bÏ• o nuÌmero de intervalos de classe para θ e Ï• respectivamente, eÌ calculado como: ∑ hk,l = Ïp, (2.4) ⌊ ⌋ ⌊ p ⌋ onde {p ∈ I bθ·θp bϕ·ϕpj | k = 1 + , l = 1 + } são pontos cujos aÌ‚ngulos dos vetoresÏ€ 2Ï€ gradientes são mapeados no intervalo de classe (k, l). O campo de gradientes fica então representado por um vetor ~hj com bθ · bÏ• elementos. 24 120º 60º 180º 0º 240º 300º [0º, 60º) [60º - 120º) [120º - 180º) [180º - 240º) [240º - 300º) [300º - 360º) (a) (b) Figura 2.6: (a) representação das orientações de vetores gradientes na aproximação do cÌırculo por um hexaÌgono. Cada lado do polÌıgono corresponde a um intervalo de classe do histograma. (b) histograma gerado pelas magnitudes e orientações dos gradientes. 2.4 Tensor de 2a ordem Tensores são entidades matemaÌticas que generalizam o conceito de vetores e escalares. Ou seja, um vetor e um escalar são casos particulares de tensores sendo o vetor um tensor de primeira ordem e o escalar um tensor de ordem zero. Um tensor de 2a ordem eÌ uma matrizm×m real e simeÌtrica para sinais m-dimensionais. Podemos usaÌ-los para representar as orientações predominantes em um campo de gradi- entes. Nesse contexto, são geralmente utilizados em processamento de imagens e visão computacional sendo aplicados, por exemplo, aÌ€ detecção de pontos de interesse, anaÌlise de espaço de escalas [29] e no algoritmo para o caÌlculo do fluxo oÌptico de Lucas-Kanade [30]. Definimos o tensor de 2a ordem Tf como: Tf = ~v~v T , (2.5) onde ~v eÌ um vetor com m elementos. A fim de fornecer uma expressão do movimento meÌdio de quadros consecutivos de um vÌıdeo, podemos combinar os tensores em uma seÌrie dada por: ∑ St = Ti, (2.6) i 25 onde Ti eÌ o tensor calculado no i -eÌsimo quadro de um vÌıdeo. 26 3 DESCRITOR DE MOVIMENTO PROPOSTO Neste capÌıtulo eÌ apresentado o descritor proposto nesta dissertação. Sua criação envolve o caÌlculo de um tensor em cada quadro do vÌıdeo ou em um intervalo de quadros. O quadro eÌ divido em partições (Figura 3.2) e em cada uma delas eÌ calculado um histograma de gradientes. Um tensor intermediaÌrio eÌ criado a partir dos histogramas e são somados gerando o tensor do quadro. Por fim, esses tensores são somados gerando o descritor final do vÌıdeo. O diagrama da Figura 3.1 mostra as etapas do processo de obtenção do tensor de um quadro que seraÌ apresentado nas seções seguintes. i - 1 i Cálculo do i + 1 gradiente Gradientes Particionamento do quadro em sub-imagens Ponderação do gradiente por gaussiana Cálculo do HOG Tensor Tensor da Sub-imagem Tensor do quadro ... *Todos os cálculos são executados também Normalização do tensor com a imagem refletida na horizontal e os dois tensores somados Figura 3.1: Diagrama do caÌlculo do tensor de um quadro. O descritor final eÌ a soma dos tensores calculados num intervalo de quadros. 27 Abaixo eÌ mostrado o pseudo-coÌdigo do meÌtodo, os passos para o caÌlculo do descritor serão apresentados nas seções seguintes. Algorithm 1: PseudocoÌdigo do meÌtodo proposto. Entrada: VıÌdeo s; nuÌmero de partições nx e ny SaÌıda: Descritor Ts dos movimentos do vÌıdeo inÌıcio para cada quadro si de s faça sÌ‚i = si refletido horizontalmente; Calcula o gradiente de si e de sÌ‚i; Particiona si e sÌ‚i em nx × ny partições; para cada partição p de si e pÌ‚ de sÌ‚i faça // Ponderação do gradiente ∇p = w · ∇p; ∇pÌ‚ = w · ∇pÌ‚; // CaÌlculo do HOG Calcula o histograma ~hk,l de p; Calcula o histograma ~Ì‚hk,l de pÌ‚; // Calcula o tensor da sub-imagem Tp = ~h ~ T k,l · hk,l ; TÌ‚ = ~Ì‚p hk,l · ~Ì‚hTk,l ; fim p∑ara Ti = p Tp + TÌ‚p; Normaliza Ti; fim p∑ara Ts = i Ti; Normaliza Ts fim 28 3.1 Gradiente espaço-temporal A primeira etapa na criação do descritor eÌ o caÌlculo dos vetores gradientes em cada pixel do quadro. Dado um vÌıdeo s, o gradiente espaço-temporal de um quadro si ∈ s eÌ: [ ] ∇ ≡ ∂si ∂si ∂sisi , , , (3.1)( ) ∂x (∂y) ∂t onde ∂si , ∂si eÌ o gradiente espacial em si e ∂si eÌ a taxa de variação entre si e o quadro∂x ∂y ∂t consecutivo si+1. Esses vetores gradientes capturam variação tanto no espaço quanto no tempo permitindo obter informação de movimento. 3.2 Particionamento do quadro e histograma de gra- dientes Quando o histograma de gradientes eÌ calculado usando-se toda a imagem, perde-se qual- quer correlação existente entre vetores gradientes que estejam em uma mesma vizinhança na imagem. Como observado em [13] e comprovado nos resultados apresentados no capÌıtulo 4, o particionamento dos quadros do vÌıdeo aumenta a taxa de reconhecimento. O nuÌmero de partições não deve ser arbitraÌrio e devemos encontrar o valor que proporciona a melhor taxa de reconhecimento. AleÌm disso, essas partições devem se manter fixas em todos os quadros durante a geração dos descritores e um descritor deve ser comparado apenas com outro descritor gerado sob as mesmas configurações. A segunda etapa na criação do descritor consiste então em dividir o quadro em partições e calcular o histograma de gradientes em cada uma delas. Seja si um qua- dro uniformemente dividido em nx × ny partições não sobrepostas (Figura 3.2). Cada uma das partições pode ser vista como o quadro de um vÌıdeo distinto. Em cada um desses quadros eÌ calculado um histograma de gradientes ~ha,bk,l , onde a ∈ [1, nx] e b ∈ [1, ny]. Essa subdivisão permite obtermos uma melhor correlação de posição entre os gradientes da imagem. No entanto, dados dois quadros consecutivos si e si+1, alguns vetores gradi- entes pertencentes aÌ€ uma partição no primeiro quadro podem aparecer em uma partição vizinha no quadro seguinte. Isso pode acarretar em uma mudança brusca do histograma mesmo que o movimento seja suave. Para evitar isso, ponderamos cada vetor gradiente em uma partição com uma gaussiana cujo centro coincide com o centro da partição (Fi- 29 gura 3.3a). Isso faz com que vetores proÌximos aÌ€ fronteira tenham um peso menor e com isso influenciem menos, caso eles transitem de uma partição para outra. Essa ponderação mostrou-se eficaz, como seraÌ visto no capÌıtulo 4. Figura 3.2: Exemplo de um quadro com nove partições. Cada partição gera um HOG. 3.3 Criação dos tensores de 2a ordem ApoÌs a criação dos histogramas de gradientes, o descritor final eÌ criado a partir dos tensores formados em cada quadro do vÌıdeo. 3.3.1 Tensor de um quadro Primeiramente, cada histograma ~ha,bk,l de cada partição produz um tensor Ta,b referente aÌ€quela partição (Figura 3.3). Esse tensor carrega a informação de movimento obtida dos gradientes daquela região e eÌ dado por: T Ta,b = wp · ~ha,b ~ a,bk,l hk,l , (3.2) onde wp eÌ um fator de ponderação que eÌ uniforme quando os quadros não são particionados e gaussiano quando são. Individualmente, Ta,b conteÌm apenas informação referente aÌ€ partição a qual ele per- tence. Mas combinando os tensores de outras partições consegue-se obter covariaÌ‚ncia entre eles. Assim, criados todos os tensores das partições de um quadro si, calcula-se o 30 tensor final do quadro como: ∑ Ti = Ta,b (3.3) a,b Esse tensor captura a incerteza da direção dos vetores m-dimensionais ~ha,bk,l de si. AleÌm disso, a subdivisão da imagem não muda o tamanho do tensor, podendo-se então variar o nuÌmero de partições sem interferir no tamanho de Ti e, consequentemente, do descritor final. Tensor HOG Gradiente ( a ) ( b ) ( c ) Figura 3.3: (a) gradientes em uma partição. O cÌırculo tracejado representa a função gaus- siana centrada no centro da partição. (b) histograma de gradientes. (c) tensor calculado a partir do histograma de gradientes gerado. 3.3.2 Tensor final de um vÌıdeo Uma vez calculado todos os tensores de todos os quadros, o descritor final Ts de um vÌıdeo s eÌ dado por: ∑ Ts = Ti (3.4) i Esse descritor, representado por uma seÌrie de tensores, expressa a meÌdia de movimento dos quadros consecutivos de s. Podem-se usar todos os quadros do vÌıdeo ou algum intervalo de interesse. O tamanho do tensor final depende exclusivamente da dimensão do histograma de gradientes e eÌ dado por (b 2θ · bÏ•) . PoreÌm, o tensor eÌ uma matriz simeÌtrica e pode ser armazenado com m(m+1) elementos, onde m eÌ o nuÌmero de linhas ou colunas do 2 tensor. Por exemplo, um histograma com bθ = 8 e bÏ• = 16 geraria um tensor de tamanho 31 128× 128 com um total de (8 · 16)2 = 16384 elementos. PoreÌm, somente 8256 elementos precisariam ser armazenados. Por fim, o descritor final eÌ normalizado usando a norma L2. Essa normalização eÌ necessaÌria para que descritores gerados por um nuÌmero diferente de quadros ou por dife- rentes resoluções de imagem possam ser comparados. 3.3.3 Reflexão do tensor para captura de simetrias EÌ possÌıvel reforçar simetrias horizontais do gradiente que ocorrem no vÌıdeo, mesmo aquelas entre muÌltiplos frames, atraveÌs da reflexão horizontal do quadro. Com isso, calcula-se o tensor TÌ‚i do quadro refletido e acumula-se com o tensor Ti gerando o tensor final: ∑ TÌ‚s = (Ti + TÌ‚i) (3.5) i Essa mudança não interfere no processo de obtenção do tensor final que eÌ o mesmo descrito em 3.3.2. Ou seja, somam-se os tensores gerados em cada quadro, com a diferença de que o tensor de cada quadro i passa a ser a soma de Ti com TÌ‚i. No capÌıtulo 4 mostra-se que a adição desse tensor aumenta consideravelmente a taxa de classificação dos dados. 3.4 Minimizando o efeito da variação de brilho Variações na iluminação podem fazer com que dois descritores gerados para movimentos similares sejam bem diferentes jaÌ que a magnitude do vetor gradiente estaÌ diretamente ligada ao brilho da imagem. Para evitar os efeitos devido aÌ€ mudança de iluminação nos quadros, eÌ feita uma normalização usando a norma L2 em cada ~h a,b k,l . Como explicado em [27], uma mudança no contraste da imagem, no qual o valor de um pixel eÌ multiplicado por uma constante, iraÌ multiplicar o gradiente pela mesma constante, assim, a norma- lização iraÌ cancelar o efeito dessa mudança. PoreÌm, uma variação no brilho, na qual uma constante eÌ somada ao valor de um pixel não afetaraÌ os valores do gradiente porque eles são calculados a partir de diferenças entre pixels. Podem ocorrer tambeÌm, mudanças não lineares de iluminação devido aÌ€ saturação da caÌ‚mera ou variações de iluminação em superfÌıcies com diferentes orientações. Esses efei- tos podem causar uma grande mudança nas magnitudes de alguns gradientes, mas são 32 menos provaÌveis de afetar sua orientação [27]. Isso eÌ reduzido usando uma normalização igual a encontrada no SIFT, onde eÌ feita uma limiarização dos valores do vetor unitaÌrio, normalizando novamente em seguida. Isso significa que gradientes com altas magnitudes não são mais importantes do que a proÌpria distribuição de orientações. Na seção de resul- tados comprova-se que essa limiarização produz um aumento significativo na classificação dos movimentos. EÌ importante dizer que essa normalização torna o tensor possivelmente indefinido, podendo ter autovalores negativos. 33 4 RESULTADOS E ANAÌLISE COMPARATIVA Neste capÌıtulo eÌ apresentada a avaliação do descritor de movimentos em diversas confi- gurações e eÌ feita uma comparação dos melhores resultados com o que haÌ de mais recente na literatura. O descritor foi utilizado em um classificador MaÌquina de Vetor Suporte (SVM). Não eÌ objetivo deste trabalho aprofundar-se no estudo do SVM e sim de como montar o descritor de forma simples e eficiente. As configurações adotadas para o SVM, incluindo sua função nuÌcleo, são as mesmas utilizadas no trabalho de Mota [23]: função nuÌcleo triangular e norma L2. O descritor foi avaliado atraveÌs das bases KTH [31] e Hollywood2 [32], descritas na proÌxima seção. Ambas são amplamente utilizadas na literatura. A geração dos descritores e sua classificação foram feitos no sistema RETIN (RE- cherche et Traque INteractive d’images) do laboratoÌrio ETIS (Equipes Traitement de l’Information et SysteÌ€mes) da ENSEA (EÌcole Nationale SupeÌrieure de l’EÌlectronique et de ses Applications) [33]. 4.1 Base de vÌıdeos A base de vÌıdeos KTH eÌ composta por seis tipos de ações humanas: • Walking (Walk): movimento de pessoa caminhando; • Jogging (Jog): movimento entre uma corrida e uma caminhada; • Running (Run): movimento de pessoa correndo; • Boxing (Box): movimento de pessoa desferindo socos no ar; • Hand waving (HWav): movimento de pessoa agitando os braços; • Hand clapping (HClap): movimento de pessoa batendo palmas. 34 Estas ações são executadas diversas vezes por 25 pessoas e em quatro cenaÌrios dife- rentes (Figura 3.2): • ambiente externo (s1); • ambiente externo com variação de escala (s2); • ambiente externo com variação de velocidade (s3); • ambiente interno (s4). No total são 2391 sequeÌ‚ncias realizadas com fundo homogeÌ‚neo e uma caÌ‚mera estaÌtica de 25 quadros por segundo. As sequeÌ‚ncias tem resolução de 160x120 pixels e duram, em meÌdia, quatro segundos. Figura 4.1: Seis tipos de ações em quatro diferentes cenaÌrios na base de vÌıdeos KTH [31]. A base Hollywood2 eÌ composta por 12 classes de ações humanas que são: • AnswerPhone: pessoa atendendo o telefone; • DriveCar : pessoa dirigindo; • Eat : pessoa comendo; • FightPerson: cena de luta; 35 • GetOutCar : pessoa saindo do carro; • HandShake: aperto de mãos entre pessoas; • HugPerson: pessoas se abraçando; • Kiss : pessoas se beijando; • Run: pessoa correndo; • SitDown: pessoa sentando; • SitUp: pessoa se levantando; • StandUp: pessoa ficando em peÌ. E por 10 classes de cenas tanto externas quanto internas: EXT-House, EXT-Road, INT-Bedroom, INT-Car, INT-Hotel, INT-Kitchen, INT-LivingRoom, INT-Office, INT- Restaurant, INT-Shop. Tudo isso distribuÌıdos em 2669 vÌıdeos a partir de trechos de 69 filmes, totalizando aproximadamente 20.1 horas de gravação. O objetivo da Hollywood2 eÌ fornecer uma base de caÌlculo para o reconhecimento de ações humanas em um ambiente realÌıstico e desafiador [32]. (a) dirigindo (b) lutando (c) aperto de mão (d) sentando Figura 4.2: Exemplos de ações na base Hollywood2 [32]. 36 4.2 Resultados na base KTH Nesta seção são apresentados resultados classificando a base KTH com um classificador SVM. Para esta base, foi rodado um classificador multiclasse usando uma estrateÌgia um contra todos e um criteÌrio de Bayes para seleção do modelo. A Figura 4.3 mostra a taxa de reconhecimento encontrada para diversos nuÌmeros de partições diferentes do quadro e um HOG de 16 × 8 intervalos de classe. AleÌm disso, o histograma de cada partição eÌ normalizado segundo a norma L2. Na Tabela 4.1 são mostrados os valores exatos dessa classificação. Nota-se que o particionamento dos quadros aumenta consideravelmente a taxa de reconhecimento. Comparando-se o melhor resultado, obtido com o particiona- mento 10×10, com o resultado sem particionamento do quadro (1×1), obteÌm-se um ganho de 3, 59% na classificação. AleÌm disso, como fica faÌcil observar no graÌfico, o aumento do nuÌmero de partições não garante um aumento na classificação. Figura 4.3: Resultados da classificação da base KTH usando HOG 16× 8 com norma L2. 37 Partição Taxa de reconhecimento 1x1 83,7882% 2x2 82,5086% 4x4 86,9132% 8x8 87,3786% 10x10 87,6101% 12x12 86,2212% 14x14 86,6825% 16x16 87,2612% 18x18 86,1022% 19x19 86,5668% 20x20 85,2920% Tabela 4.1: Valores da classificação do graÌfico da Figura 4.3. Na Tabela 4.2 são mostrados alguns resultados para outras dimensões do histograma de gradientes. Dimensão do HOG Particionamento 4x2 6x3 8x4 4x4 78,231% 77,877% 79,732% 8x8 79,163% 78,696% 80,897% 16x16 79,045% 77,656% 81,937% Tabela 4.2: Resultados utilizando outras dimensões para o histograma de gradientes. Todas as outras configurações são as mesmas da tabela 4.1. O melhor resultado para as configurações apresentadas ateÌ aqui foi com um histo- grama de dimensão 16× 8, com 10× 10 partições, normalizado com a norma L2 em cada histograma gerado. A matriz de confusão para este resultado eÌ apresentada na Tabela 4.3. Ela mostra o percentual de ações classificadas corretamente e tambeÌm a porcentagem que foi classificada de forma errada. 38 Box HWav HClap Jog Run Walk Box 95,10% 7,64% 12,50% 0,0% 0,0% 0,0% HWav 0,0% 89,58% 2,08% 0,0% 0,0% 0,0% HClap 3,50% 0,69% 86,86% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 84,03% 19,44% 9,03% Run 0,0% 0,0% 0,0% 9,72% 80,55% 0,0% Walk 1,40% 2,08% 0,0% 6,25% 0,0% 90,97% Tabela 4.3: Matriz de confusão para o melhor resultado. Observa-se que no caso do running e do jogging, existe uma maior taxa de erros. Um vÌıdeo que deveria ter sido classificado como jogging eÌ classificado como running e vice-versa. Isso ocorre porque são movimentos muito similares, diferindo apenas por sua velocidade. 4.2.1 Reflexão do quadro para o caÌlculo do histograma O uso de reflexão do quadro aumentou a taxa de reconhecimento como mostra a Tabela 4.4. Com a reflexão, eÌ somado ao tensor gerado em uma partição o tensor gerado pela mesma partição, poreÌm refletida na horizontal. A reflexão na vertical e a reflexão na vertical e horizontal tambeÌm foram testadas, poreÌm os resultados ficaram piores do que sem o uso de nenhuma reflexão. Essa piora nos resultados usando reflexão na vertical eÌ possivelmente devido aÌ€ falta de simetria vertical dos movimentos, como o movimento de caminhar ou correr, por exemplo. Os valores de classificação do melhor resultado da Tabela 4.1 comparado a um teste com a mesma configuração mas sem usar reflexão mostra um ganho de quase 2%. A Tabela 4.6 mostra a matriz de confusão da classificação sem reflexão mostrada na Tabela 4.4. Percebe-se uma melhora na classificação dos movimentos jogging, running e walking quando se usa reflexão. 39 HOG 16x8 Partição Taxa de reconhecimento 8x8 sem reflexão 87,609% 8x8 com reflexão 89,578% Tabela 4.4: Ganho obtido com o uso de reflexão do quadro na geração do descritor. Box HWav HClap Jog Run Walk Box 94,40% 2,78% 12,50% 0,0% 0,0% 0,69% HWav 0,0% 96,53% 0,0% 0,0% 0,0% 0,0% HClap 3,49% 0,69% 87,50% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 77,78 18,75% 9,03% Run 0,0% 0,0% 0,0% 16,67% 79,17% 0,0% Walk 2,098% 0,0% 0,0% 5,56% 2,08% 90.28% Tabela 4.5: Matriz de confusão para o resultado sem reflexão da Tabela 4.4. Box HWav HClap Jog Run Walk Box 95,80% 2,08% 12,50% 0,0% 0,0% 1,39% HWav 0,0% 96,53% 0,69% 0,0% 0,0% 0,0% HClap 0,70% 1,39% 86,81% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 79,17 12,50% 4,86% Run 0,0% 0,0% 0,0% 15,97% 85,42% 0,0% Walk 3,50% 0,0% 0,0% 4,86% 2,08% 93.75% Tabela 4.6: Matriz de confusão para o resultado com reflexão da Tabela 4.4. 4.2.2 Usando limiarização da norma O uso de limiarização da norma como mostrado na seção 3.4 tambeÌm provou-se eficaz. Alguns valores para o limiar foram testados, mas o valor 0.2, que eÌ o mesmo utilizado por [27], foi o que obteve melhor resultado. A Tabela 4.7 mostra um comparativo do resultado com e sem limiarização do melhor resultado obtido na Tabela 4.4. 40 HOG 16x8 Partição Taxa de reconhecimento 8x8 sem limiarização 89,578% 8x8 com limiarização 92,123% Tabela 4.7: Ganho obtido com o uso de limiarização do tensor do quadro. A matriz de confusão para o resultado de 92, 123% da Tabela 4.7 eÌ mostrada na Tabela 4.9 e para o resultado de 89, 578% na Tabela 4.3. Comparando as duas tabelas, nota-se que o uso de limiarização melhorou significativamente os resultados para o movimento jogging (de 79, 17% para 86, 11%) e para o movimento hand clapping (de 86, 86% para 94, 44%). O alto ganho do movimento hand clapping se deu por conta da queda na taxa de classificação incorreta com o movimento boxing (de 12, 50% para 5, 56%). 4.2.3 Combinando limiarização e reflexão A Figura 4.4 compara os resultados obtidos com as diversas combinações de geração do descritor utilizando ou não reflexão e limiarização. Os valores dos resultados são mostrados na Tabela 4.8. A combinação de reflexão do quadro e limiarização do tensor proporcionou um aumento significativo na classificação. 41 Figura 4.4: Resultados obtidos com diversas configurações no uso ou não de reflexão e limiarização. Configuração Taxa de reconhecimento Sem reflexão e sem limiarização 87,61% Sem reflexão e com limiarização 89,35% Com reflexão e sem limiarização 89,58% Com reflexão e com limiarização 92,12% Tabela 4.8: Valores dos resultados do graÌfico da Figura 4.4. AtraveÌs dos valores da tabela e da observação do graÌfico verifica-se que o ganho na taxa de reconhecimento quando se utiliza apenas a reflexão do quadro ou apenas a limiarização do tensor são bem proÌximos, algo em torno de 1, 85%. PoreÌm, quando combinamos os dois, o ganho aumenta para 4, 51%. A Tabela 4.9 mostra a matriz de confusão para o resultado de 92, 12% que utiliza reflexão e limiarização. O grande problema continua sendo os movimentos jogging e running. A porcentagem de movimentos running classificados como jogging sofreu um aumento de 2, 78%, em contrapartida, a taxa de movimentos jogging classificados como running caiu 6, 94%. As tabelas 4.10 aÌ€ 4.12 mostram as matrizes de confusão para as 42 demais configurações da Tabela 4.8. Box HWav HClap Jog Run Walk Box 94,41% 0,0% 5,56% 0,69% 0,0% 0,0% HWav 0.70% 98,61% 0,0% 0,0% 0,0% 0,0% HClap 0.70% 1,39% 94,44% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 86,11% 15,28% 5,56% Run 0,0% 0,0% 0,0% 9,03% 84,72% 0,0% Walk 4,20% 0,0% 0,0% 4,17% 0,0% 94,44% Tabela 4.9: Matriz de confusão para o melhor resultado na base KTH (com reflexão e com limiarização). Box HWav HClap Jog Run Walk Box 94,41% 2,78% 12,50% 0,0% 0,0% 0,69% HWav 0,0% 96,53% 0,0% 0,0% 0,0% 0,0% HClap 3,50% 0,70% 87,50% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 77,78% 18,75% 9,03% Run 0,0% 0,0% 0,0% 16,67% 79,17% 0,0% Walk 2,10% 0,0% 0,0% 5,56% 2,08% 90,28% Tabela 4.10: Matriz de confusão para o caso sem reflexão e sem limiarização. Box HWav HClap Jog Run Walk Box 95,10% 0,0% 12,50% 0,0% 0,0% 0,0% HWav 0,0% 100,53% 0,0% 0,0% 0,0% 0,0% HClap 2,80% 0,0% 87,50% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 81,25% 20,14% 6,94% Run 0,0% 0,0% 0,0% 11,11% 77,78% 0,0% Walk 2,10% 0,0% 0,0% 7,64% 2,08% 93,06% Tabela 4.11: Matriz de confusão para o caso sem reflexão e com limiarização. 43 Box HWav HClap Jog Run Walk Box 95,80% 2,083% 12,50% 0,0% 0,0% 1,39% HWav 0,0% 96,53% 0,69% 0,0% 0,0% 0,0% HClap 0,70% 1,39% 86,86% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 79,17% 12,50% 4,86% Run 0,0% 0,0% 0,0% 15,97% 85,42% 0,0% Walk 3,50% 0,0% 0,0% 4,86% 2,08% 93,75% Tabela 4.12: Matriz de confusão para o caso com reflexão e sem limiarização. 4.2.4 Efeito do uso da função gaussiana na ponderação dos gradientes das partições Todos os testes efetuados a partir da seção 4.2.1 utilizam a ponderação dos vetores gradi- entes por uma gaussiana como explicado na seção 3.3. O melhor valor para σx e σy, obtido atraveÌs de testes, foi de 6.0 pixels. A Figura 4.5 mostra o resultado comparativo da clas- sificação com e sem o uso dessa ponderação e seus valores são mostrados na Tabela 4.13. A matriz de confusão para o caso sem ponderação eÌ visto na Tabela 4.14. Comparando-a com a matriz de confusão da Tabela 4.12, percebe-se que movimentos menos sutis, como o running, hand clapping e hand waving tiveram um aumento bastante significativo da taxa de reconhecimento quando usada a ponderação dos gradientes. No caso do movi- mento hand waving o salto na classificação foi de quase 8%. Esses movimentos teÌ‚m uma taxa de variação maior e, consequentemente, a mudança de posição de um ponto entre dois quadros consecutivos eÌ brusca. Com isso, o histograma de gradientes pode variar muito entre dois quadros. Dando-se menos peso aÌ€ fronteira de uma partição, como acon- tece com o uso da ponderação, consegue-se uma transição mais suave entre tensores de quadros consecutivos. 44 Figura 4.5: Resultados da melhor configuração com e sem ponderação dos vetores gradi- entes de uma partição. Ponderação Taxa de reconhecimento Sem ponderação 89,229% Com ponderação 92,123% Tabela 4.13: Valores da classificação do graÌfico da Figura 4.5. Box HWav HClap Jog Run Walk Box 94,41% 6,25% 7,64% 0,69% 0,0% 0,0% HWav 1,40% 90,97% 0,69% 0,0% 0,0% 0,0% HClap 0,0% 1,39% 91,67% 0,0% 0,0% 0,0% Jog 0,0% 0,0% 0,0% 84,03% 18,75% 6,25% Run 0,0% 0,0% 0,0% 11,11% 80,56% 0,0% Walk 4,20% 1,40% 0,0% 4,17% 0,69% 93,75% Tabela 4.14: Matriz de confusão para a configuração do melhor resultado sem ponderação dos vetores gradientes de uma partição. 45 4.3 Resultados na base Hollywood2 Nesta seção são apresentados resultados classificando a base Hollywood2 com um clas- sificador SVM. Para esta base, foi rodado um classificador monoclasse, um criteÌrio de precisão meÌdia para seleção do modelo e validação cruzada. A Figura 4.6 mostra a taxa de reconhecimento para diversas configurações de partição e histograma sem o uso de reflexão do quadro e com limiarização. Os valores exatos são mostrados na Tabela 4.15. Observa-se que o histograma com dimensões 16 × 8 eÌ o que gera os melhores resultados, assim como ocorreu com a base KTH. Nas tabelas 4.16 a 4.19 são mostradas as precisões meÌdias em cada classe de ação. As ações que tiveram os melhores resultados são, nessa ordem, DriveCar, Run, FightPerson e Kiss. Elas foram as uÌnicas em que se obteve classificação maior que 50%. As ações que tiveram os piores resultados foram SitUp, HandShake e AnswerPhone, respectivamente. Figura 4.6: Taxas de reconhecimento da base Hollywood2. 46 Configuração Taxa de reconhecimento Partição: 4x4, HOG: 8x4 31.52% Partição: 4x4, HOG: 16x8 33.98% Partição: 16x16, HOG: 8x4 31.15% Partição: 16x16, HOG: 16x8 34.28% Tabela 4.15: Valores da classificação do graÌfico da Figura 4.6. Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 13,80% DriveCar 67,30% Eat 20,69% FightPerson 55,13% GetOutCar 18,90% HandShake 12,87% HugPerson 19,33% Kiss 40,37% Run 59,09% SitDown 34,70% SitUp 7,82% StandUp 39,42% MeÌdia 31,52% Tabela 4.16: Precisão meÌdia para cada classe da base Hollywood2 usando partição 4× 4 e HOG 8× 4 sem reflexão. Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 13,73% DriveCar 69,76% Eat 23,78% FightPerson 53,64% GetOutCar 27,71% HandShake 9,27% HugPerson 22,46% Kiss 49,80% Run 56,68% SitDown 43,67% SitUp 9,12% StandUp 39,05% MeÌdia 33,98% Tabela 4.17: Precisão meÌdia para cada classe da base Hollywood2 usando partição 4× 4 e HOG 16× 8 sem reflexão. 47 Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 12,95% DriveCar 62,76% Eat 26,78% FightPerson 56,92% GetOutCar 20,31% HandShake 10,57% HugPerson 19,24% Kiss 40,76% Run 61,16% SitDown 30,65% SitUp 7,42% StandUp 35,11% MeÌdia 31,15% Tabela 4.18: Precisão meÌdia para cada classe da base Hollywood2 usando partição 16×16 e HOG 8× 4 sem reflexão. Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 14,68% DriveCar 69,99% Eat 27,69% FightPerson 56,19% GetOutCar 29,30% HandShake 10,55% HugPerson 18,66% Kiss 50,16% Run 57,94% SitDown 42,32% SitUp 11,30% StandUp 37,80% MeÌdia 34,28% Tabela 4.19: Precisão meÌdia para cada classe da base Hollywood2 usando partição 16×16 e HOG 16× 8 sem reflexão. 4.3.1 Reflexão do quadro para o caÌlculo do histograma A fim de melhorar o reconhecimento na base Hollywood2, inserimos a reflexão do quadro como feito para a base KTH. A Figura 4.7 mostra as taxas de reconhecimento usando as mesmas configurações dos testes sem reflexão (exceto pela proÌpria reflexão). A Tabela 4.20 mostra os valores exatos da classificação. Comparando com a Tabela 4.15, houve um aumento de 2, 24% entre os resultados com 4× 4 partições e HOG 16× 8 e um aumento de 1, 31% entre os resultados com 16× 16 e HOG 16× 8. Ou seja, a configuração com um nuÌmero maior de partições teve um aumento menor com a adição de reflexão do quadro no caÌlculo do histograma. 48 Como na base KTH, a Hollywood apresentou melhores resultados utilizando partições 4×4 e 8×8. O melhor resultado obtido com a base Hollywood foi com partição 8×8, HOG 16×8 e reflexão do quadro, alcançando 36, 34% de classificação. Apesar de esse resultado estar bem abaixo do que foi alcançado na KTH, deve-se levar em consideração o alto nÌıvel de complexidade da base Hollywood2. Todos os testes executados nessa subseção fizeram uso de normalização com limiarização e ponderação gaussiana nos gradientes. Figura 4.7: Taxas de reconhecimento da base Hollywood2. Configuração Taxa de reconhecimento Partição: 4x4, HOG: 8x4 32,29% Partição: 4x4, HOG: 16x8 36,22% Partição: 8x8, HOG: 16x8 36,34% Partição: 16x16, HOG: 8x4 31,07% Partição: 16x16, HOG: 16x8 35,59% Tabela 4.20: Valores da classificação do graÌfico da Figura 4.7. 49 Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 12,87% DriveCar 69,68% Eat 22,04% FightPerson 42,20% GetOutCar 26,55% HandShake 19,32% HugPerson 25,59% Kiss 42,15% Run 59,63% SitDown 34,87% SitUp 7,55% StandUp 40,88% MeÌdia 32,29% Tabela 4.21: Precisão meÌdia para cada classe da base Hollywood2 usando partição 4× 4 e HOG 8× 4 com reflexão. Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 19,30% DriveCar 70,49% Eat 22,23% FightPerson 50,80% GetOutCar 31,58% HandShake 16,67% HugPerson 27,53% Kiss 50,93% Run 58,57% SitDown 48,51% SitUp 10,61% StandUp 41,89% MeÌdia 36,22% Tabela 4.22: Precisão meÌdia para cada classe da base Hollywood2 usando partição 4× 4 e HOG 16× 8 com reflexão. 50 Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 18,59% DriveCar 70,51% Eat 24,09% FightPerson 52,80% GetOutCar 34,82% HandShake 14,72% HugPerson 26,59% Kiss 49,63% Run 57,94% SitDown 45,04% SitUp 11,84% StandUp 41,38% MeÌdia 36,34% Tabela 4.23: Precisão meÌdia para cada classe da base Hollywood2 usando partição 8× 8 e HOG 16× 8 com reflexão. Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 12,17% DriveCar 62,25% Eat 17,87% FightPerson 47,02% GetOutCar 25,90% HandShake 12,58% HugPerson 22,96% Kiss 41,48% Run 61,21% SitDown 32,67% SitUp 10,55% StandUp 39,20% MeÌdia 31,07% Tabela 4.24: Precisão meÌdia para cada classe da base Hollywood2 usando partição 16×16 e HOG 8× 4 com reflexão. 51 Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 15,05% DriveCar 70,48% Eat 23,50% FightPerson 51,22% GetOutCar 36,48% HandShake 12,46% HugPerson 24,26% Kiss 49,80% Run 58,19% SitDown 44,59% SitUp 10,92% StandUp 39,93% MeÌdia 35,59% Tabela 4.25: Precisão meÌdia para cada classe da base Hollywood2 usando partição 16×16 e HOG 16× 8 com reflexão. 4.3.2 Efeito do uso da função gaussiana na ponderação dos gradientes das partições O uso de ponderação gaussiana nos gradientes tambeÌm promoveu aumento na taxa de reconhecimento para a base Hollywood2. O graÌfico da Figura 4.8 mostra esse ganho. Os valores exatos são mostrados na Tabela 4.26. Pela tabela verifica-se que usando pon- deração gaussiana tem-se um ganho de 1, 18%, que eÌ um bom valor de aumento para essa base complexa. A precisão meÌdia para o caso sem ponderação eÌ mostrada na Tabela 4.27. Comparando-a com a Tabela 4.23 do caso com ponderação, observa-se que o uso de ponderação acarreta em ganho para algumas classes de ações e perda para outras. 52 Figura 4.8: Comparação entre a melhor configuração para Hollywood usando ou não a ponderação gaussiana. Configuração Taxa de reconhecimento Sem ponderação 35,16% Com ponderação 36,34% Tabela 4.26: Valores da classificação do graÌfico da Figura 4.8. Ação Precisão meÌdia Ação Precisão meÌdia AnswerPhone 15,43% DriveCar 70,03% Eat 19,81% FightPerson 54,22% GetOutCar 29,52% HandShake 13,00% HugPerson 26,27% Kiss 51,42% Run 55,94% SitDown 45,41% SitUp 13,57% StandUp 40,35% MeÌdia 35,16% Tabela 4.27: Precisão meÌdia para cada classe da base Hollywood2 usando partição 8× 8 e HOG 16× 8 com reflexão e sem ponderação gaussiana. 53 4.4 Comparação com descritores da literatura Nesta seção são comparados os melhores resultados obtidos com outros descritores da literatura. O desempenho do meÌtodo proposto para a base KTH eÌ mostrada na Tabela 4.28. A taxa de reconhecimento eÌ comparada com os outros resultados na literatura que utilizam histogramas de gradientes e tambeÌm com o trabalho de Mota [23] que utiliza tensores de orientação a partir de polinoÌ‚mios de Legendre. O meÌtodo proposto consegue superar o reconhecimento alcançado por outros meÌtodos. MeÌtodo Taxa de reconhecimento PiraÌ‚mides HOG [25] 72% PolinoÌ‚mios de Legendre + Tensor [23] 86,8% Harris3D + HOG3D [15] 91.4% Harris3D + HOG/HOF [14] 91.8% HOG3D + Tensor (este trabalho) 92.12% ISA [34] 93.9% TCCA [16] 95.33% Tabela 4.28: Comparação das taxas de reconhecimento na base KTH. Na base Hollywood2, este meÌtodo não consegue superar os melhores resultados. En- tretanto, ele consegue uma acuraÌcia competitiva atraveÌs de uma abordagem muito simples com poucos paraÌ‚metros. A Tabela 4.29 compara as taxas de reconhecimento do meÌtodo proposto com descritores locais de outros trabalhos. Percebe-se que a informação local desempenha um papel fundamental nessa base e que meÌtodos de aprendizado melhoram o reconhecimento de maneira geral. MeÌtodo Taxa de reconhecimento HOG3D + Tensor (estre trabalho) 36.34% Harris3D + HOG3D [15, 35] 43.7% Harris3D + HOG/HOF [14, 35] 45.2% ISA [34] 53.3% Tabela 4.29: Comparação das taxas de reconhecimento na base Hollywood2. A taxa de reconhecimento do meÌtodo proposto eÌ menor do que as abordagens locais para a base Hollywood2, poreÌm bastante competitiva. A abordagem apresentada neste texto eÌ raÌpida e novos vÌıdeos ou novas categorias de ações podem ser inseridas sem necessidade de recalcular os descritores jaÌ existentes. Quanto aÌ€ complexidade de tempo, 54 os descritores foram calculados com uma meÌdia de 23qps (quadros por segundo) para todos os vÌıdeos da base Hollywood2 em uma maÌquina Intel I7 2930MHz com 8Gb de memoÌria. A Tabela 4.30 mostra o tempo gasto em cada etapa do processo na geração dos descritores na base KTH para a melhor configuração. Percebe-se que o caÌlculo das derivadas e a normalização com limiarização de cada descritor de um quadro dominam a complexidade de tempo. No caso da normalização com limiarização, isso ocorre porque ela eÌ executada duas vezes em cada quadro. Para efeitos de comparação, somente a etapa de extração de caracterÌısticas no trabalho de [16] eÌ executada aÌ€ 1, 6qps para a base Hollywood2. Se comparado com [34], seu melhor resultado eÌ executado com 10qps, tambeÌm para Hollywood2, usando uma GPU GTX2701. Etapa Tempo total Tempo meÌdio por vÌıdeo CaÌlculo de todo o processo 9m e 50s 246ms Normalização do tensor de um quadro 2m e 56s 73ms CaÌlculo dos gradientes 2m e 35s 64ms Histograma de Gradientes 2m e 29s 62ms Normalização do descritor final 0m e 6s 2ms Tabela 4.30: Tempo gasto nas etapas de geração dos descritores na base KTH com a melhor configuração. O tempo total refere-se ao tempo gasto para calcular os descritores em toda a base. 1O artigo não fornece detalhes sobre o que foi implementado em GPU. 55 5 CONCLUSÃO Neste trabalho foi apresentado um meÌtodo para descrever movimentos baseado na com- binação de histogramas de gradientes com tensores de 2a ordem. Para validação da qualidade do descritor proposto foram classificadas as bases KTH e Hollywood2 e seus resultados comparados com outros trabalhos na literatura. A abordagem adotada eÌ simples, mas efetiva para classificação de vÌıdeos. Ela eÌ simples pois possui baixa complexidade espacial e temporal. Somente poucos paraÌ‚metros são necessaÌrios, resultando em um descritor compacto. A complexidade de tempo eÌ dominada pelo caÌlculo das derivadas, histograma e normalização dos tensores de um quadro (Tabela 4.30). Como esses caÌlculos dependem apenas dos quadros do vÌıdeo, o processo pode ser escalaÌvel e capaz de receber melhorias atraveÌs de paralelismo como instruções SIMD, processadores de muÌltiplos nuÌcleos e GPUs. EÌ tambeÌm uma abordagem efetiva porque alcança uma alta taxa de reconhecimento na base KTH (92, 12%), comparada com as melhores abordagens locais [34, 16] cujas complexidades são muito maiores. Para a base Hollywood, entretanto, foi percebido que a informação local possui papel importante e que meÌtodos de aprendizado melhoram o reconhecimento de maneira geral. A taxa de reconhecimento alcançada por este meÌtodo eÌ menor que a de abordagens locais, mas ainda assim, bastante competitiva. Um alto ıÌndice de erros pode ser aceitaÌvel quando a base de dados eÌ frequentemente atualizada ou o tempo de resposta eÌ crÌıtico. Este meÌtodo não requer que sejam feitas mudanças ou que descritores sejam recalculados devido aÌ€ adição de novos vÌıdeos e/ou novas categorias de ações. As melhorias propostas para o descritor se mostraram eficazes aumentando a taxa de reconhecimento tanto na base KTH quanto na Hollywood2. O uso de ponderação dos gradientes fez com que ocorresse um aumento significativo na classificação das bases (Tabela 5.1 e 5.2). Na base KTH, por exemplo, isso eÌ mais visÌıvel principalmente em ações com movimentos mais raÌpidos como o running, hand clapping e hand waving que obteve um aumento de quase 8%. 56 Ponderação Taxa de reconhecimento Sem ponderação 89,229% Com ponderação 92,123% Tabela 5.1: Comparação da taxa de classificação com e sem o uso de ponderação na base KTH. Configuração Taxa de reconhecimento Sem ponderação 35,16% Com ponderação 36,34% Tabela 5.2: Comparação da taxa de classificação com e sem o uso de ponderação na base Hollywood2. Outra melhoria proposta foi o caÌlculo do tensor do quadro refletido horizontalmente. Isso permitiu reforçar simetrias horizontais do gradiente aumentando a taxa de classi- ficação. O uso de reflexão na base KTH fez com que a classificação aumentasse de 89, 35% para 92, 12% para uma mesma configuração do descritor. No caso da Hollywood2 o au- mento foi de 33, 98% para 36, 22% em uma das configurações testadas. Uma terceira melhoria no descritor foi o uso da normalização usando um limiar. Essa limiarização, apresentada em [27] tem o objetivo de diminuir a influeÌ‚ncia que variações não lineares de iluminação. A Tabela 5.3 mostra o ganho obtido para a base KTH. HOG 16x8 Partição Taxa de reconhecimento 8x8 sem limiarização 89,578% 8x8 com limiarização 92,123% Tabela 5.3: Ganho obtido com o uso de limiarização. Um interessante estudo futuro seria a exploração de informação local para melhorar o descritor e como agregaÌ-la de maneira a aumentar as taxas de reconhecimento, princi- palmente na base Hollywood2 permitindo o uso do descritor em situações mais realistas. 57 AleÌm disso, em algumas situações o cenaÌrio possui diversos movimentos de diversos obje- tos no fundo que não são de interesse. Isso acaba comprometendo a qualidade do descritor ou mesmo tornando-o não discriminante do movimento. EÌ o que ocorre com frequeÌ‚ncia na base Hollywood2. Assim, a extração de objetos que não são de interesse tambeÌm necessita de um estudo futuro. Mas ainda assim, ele pode ser de grande valia em um cenaÌrio onde nenhum meÌtodo de classificação de ações humanas resolve todas as demandas de aplicação [35]. 58 REFEREÌ‚NCIAS [1] TURAGA, P., CHELLAPPA, R., SUBRAHMANIAN, V. S., UDREA, O., “Machine Recognition of Human Activities: A Surveyâ€, Circuits and Systems for Video Technology, IEEE Transactions on, v. 18, n. 11, pp. 1473–1488, Sept. 2008. [2] JOHANSSON, G., “Visual perception of biological motion and a model for its analy- sisâ€, Attention Perception Psychophysics , v. 14, n. 2, pp. 201–211, 1973. [3] SARKAR, S., PHILLIPS, P. J., LIU, Z., VEGA, I. R., GROTHER, P., BOWYER, K. W., “The humanID gait challenge problem: Data sets, performance, and analysisâ€, IEEE Transactions on Pattern Analysis and Machine Intelligence, v. 27, pp. 162–177, 2005. [4] RUI, Y., HUANG, T. S., “Image retrieval: Current techniques, promising directions and open issuesâ€, Journal of Visual Communication and Image Representation, v. 10, pp. 39–62, 1999. [5] CHANG, S.-F., “The holy grail of content-based media analysisâ€, IEEE Multimedia, v. 9, pp. 6–10, 2002. [6] ZHONG, H., SHI, J., VISONTAI, M., “Detecting Unusual Activity in Videoâ€, Com- puter Vision and Pattern Recognition, IEEE Computer Society Conference on, v. 2, pp. 819–826, 2004. [7] VASWANI, N., CHOWDHURY, A. R., CHELLAPPA, R., “â€Shape Activityâ€: A Con- tinuous State HMM for Moving/Deforming Shapes with Application to Abnor- mal Activity Detectionâ€, IEEE Trans. on Image Processing , v. 14, pp. 1603– 1616. [8] PENTLAND, A., “Smart rooms, smart clothesâ€. v. 2, pp. 949–953 vol.2, 1998. [9] FORSYTH, D. A., ARIKAN, O., RAMANAN, D., “Computational Studies of Human Motion: Part 1, Tracking and Motion Synthesisâ€. In: Foundations and Trends in Computer Graphics and Vision, p. 2006, Now Publishers Inc, 2006. [10] GOMES, J., VELHO, L., Fundamentos da Computação GraÌfica. 1st ed. Instituto Nacional de MatemaÌtica Pura e Aplicada: Rio de Janeiro, RJ, 2008. 59 [11] BEAUCHEMIN, S., BARRON, J., “The Computation of Optical Flowâ€, 1995. [12] PEREZ, E. A., MOTA, V. F., MACIEL, L. M., SAD, D., VIEIRA, M. B., “Com- bining gradient histograms using orientation tensors for human action recogni- tionâ€. In: ICPR, 2012. [13] LOWE, D. G., “Object Recognition from Local Scale-Invariant Featuresâ€. In: Proce- edings of the International Conference on Computer Vision-Volume 2 - Volume 2 , ICCV ’99 , pp. 1150–, IEEE Computer Society: Washington, DC, USA, 1999. [14] LAPTEV, I., MARSZAL EK, M., SCHMID, C., ROZENFELD, B., “Learning Re- alistic Human Actions from Moviesâ€. In: Conference on Computer Vision & Pattern Recognition, jun 2008. [15] KLÄSER, A., MARSZAL EK, M., SCHMID, C., “A Spatio-Temporal Descriptor Ba- sed on 3D-Gradientsâ€. In: British Machine Vision Conference, pp. 995–1004, sep 2008. [16] KYUN KIM, T., FAI WONG, S., CIPOLLA, R., “R.: Tensor Canonical Correlation Analysis for Action Classificationâ€. In: CVPR, 2007. [17] BACH, F. R., JORDAN, M. I., A probabilistic interpretation of canonical correlation analysis , Tech. rep., 2005. [18] HARDOON, D. R., SZEDMAK, S., SZEDMAK, O., SHAWE-TAYLOR, J., Cano- nical correlation analysis; An overview with application to learning methods , Tech. rep., 2007. [19] KRAUSZ, B., BAUCKHAGE, C., “Action Recognition in Videos Using Nonnegative Tensor Factorizationâ€. In: ICPR, pp. 1763–1766, 2010. [20] JIA, C., WANG, S., XU, X., ZHOU, C., ZHANG, L., “Tensor analysis and multi- scale features based multi-view human action recognitionâ€. In: International Conference on Computer Engineering and Technology , 2010. [21] KHADEM, B. S., RAJAN, D., “Appearance-based action recognition in the ten- sor frameworkâ€. In: Proceedings of the 8th IEEE international conference on 60 Computational intelligence in robotics and automation, CIRA’09 , pp. 398–403, IEEE Press: Piscataway, NJ, USA, 2009. [22] KIHL, O., TREMBLAIS, B., AUGEREAU, B., KHOUDEIR, M., “Human activities discrimination with motion approximation in polynomial bases.†In: ICIP , pp. 2469–2472, IEEE, 2010. [23] MOTA, V. F., Tensor baseado em fluxo oÌptico para descrição global de movimento em vÌıdeos , Mestrado, Universidade Federal de Juiz de Fora, Juiz de Fora, Brasil, 2011. [24] ZELNIK-MANOR, L., IRANI, M., “Event-based analysis of videoâ€. In: In Proc. CVPR, pp. 123–130, 2001. [25] LAPTEV, I., CAPUTO, B., SCHÜLDT, C., LINDEBERG, T., “Local velocity- adapted motion events for spatio-temporal recognitionâ€, Comput. Vis. Image Underst., v. 108, n. 3, pp. 207–229, Dec. 2007. [26] THEODORIDIS, S., KOUTROUMBAS, K., Pattern Recognition, Fourth Edition. 4th ed. Academic Press, 2008. [27] LOWE, D. G., “Distinctive Image Features from Scale-Invariant Keypointsâ€, Int. J. Comput. Vision, v. 60, n. 2, pp. 91–110, Nov. 2004. [28] DALAL, N., TRIGGS, B., “Histograms of Oriented Gradients for Human Detectionâ€. In: In CVPR, pp. 886–893, 2005. [29] LINDEBERG, T., “Scale-Space Theory in Computer Visionâ€, 1994. [30] LUCAS, B. D., KANADE, T., “An Iterative Image Registration Technique with an Application to Stereo Visionâ€. pp. 674–679, 1981. [31] SCHÜLDT, C., LAPTEV, I., CAPUTO, B., “Recognizing human actions: A local SVM approachâ€. In: In Proc. ICPR, pp. 32–36, 2004. [32] MARSZALEK, M., LAPTEV, I., SCHMID, C., “Actions in contextâ€, IEEE Conf. Computer Vision and Pattern Recog , 2009. 61 [33] FOURNIER, J., CORD, M., PHILIPP-FOLIGUET, S., PONTOISE CEDEX, F. C., “RETIN: A content-based image indexing and retrieval systemâ€, 2001. [34] LE, Q. V., ZOU, W. Y., YEUNG, S. Y., NG, A. Y., “Learning hierarchical invari- ant spatio-temporal features for action recognition with independent subspace analysisâ€. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’11 , pp. 3361–3368, IEEE Computer Society: Washington, DC, USA, 2011. [35] WANG, H., ULLAH, M. M., KLÄSER, A., LAPTEV, I., SCHMID, C., “Evaluation of local spatio-temporal features for action recognitionâ€. In: University of Central Florida, U.S.A, 2009.