Dissertação
DISSERTAÇÃO_Samuel Rocha Silva - 2017.pdf
Documento PDF (6.5MB)
Documento PDF (6.5MB)
UNIVERSIDADE FEDERAL DE ALAGOAS
INSTITUTO DE MATEMÁTICA
PROGRAMA DE PÓS GRADUAÇÃO EM MATEMÁTICA
SAMUEL ROCHA SILVA
RECONHECIMENTO DE GESTOS CUSTOMIZADOS DA MÃO EM TEMPO REAL
USANDO APRENDIZADO DE MÉTRICAS E GRAFOS DE AÇÃO
MACEIÓ - AL
SETEMBRO DE 2017
SAMUEL ROCHA SILVA
RECONHECIMENTO DE GESTOS CUSTOMIZADOS DA MÃO EM TEMPO REAL
USANDO APRENDIZADO DE MÉTRICAS E GRAFOS DE AÇÃO
Dissertação de Mestrado submetida em Setembro de 2017 à Banca Examinadora, designada pelo Colegiado do Programa de PósGraduação em Matemática da Universidade
Federal de Alagoas, como parte dos requisitos necessários à obtenção do grau de Mestre em Matemática.
Orientador: Prof. Dr. Thales Miranda de
Almeida Vieira
MACEIÓ - AL
SETEMBRO DE 2017
Catalogação na fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecária Responsável: Helena Cristina Pimentel do Vale
S586r
Silva, Samuel Rocha.
Reconhecimento de gestos customizados da mão em tempo real usando
aprendizado de métrica e grafos de ação / Samuel Rocha Silva. – 2017.
111 f.
Orientador: Thales Miranda de Almeida Vieira.
Dissertação (mestrado em Matemática) – Universidade Federal de Alagoas.
Instituto de Matemática. Maceió, 2017.
Bibliografia: f. 108-111.
1. Língua brasileira de sinais. 2. Leap motion. 3. Aprendizagem de máquina.
4. Reconhecimento de gestos. 5. Aprendizagem de métrica. I. Título.
CDU: 51:004.9
À minha mãe, irmãos e a toda minha família que, com muito carinho e apoio, não
mediram esforços para que eu chegasse até esta etapa de minha vida.
Agradecimentos
Primeiramente à Deus, por me conceder saúde e disposição para vencer mais um
desafio em minha vida.
À minha mãe, que através de sua simplicidade e imensa bondade me ensinou os
verdadeiros valores da vida. Aos meus irmãos, cunhados e demais familiares, que sempre
me apoiaram durante essa jornada. À minha namorada, por seu amor, carinho e incentivo,
que sempre renovavam minhas energias nos momentos de maiores difilculdades.
Ao meu orientador, Prof. Dr. Thales Vieira, pelo seu apoio, comprometimento
e pelas várias reuniões que foram de suma importância para o desenvolvimento deste
trabalho.
Aos Profs. Dr. Adelailson Peixoto, Dr. Dimas Martinez e Dr. Tiago Vieira por
aceitarem compor a banca examinadora deste trabalho. Em especial ao Prof. Dr. Tiago
pelas diversas correções e sugestões.
Ao Prof. Adriano Valeriano pelo constante apoio e incentivo ao meu crescimento
científico e intelectual durante nossos mais de 10 anos de convivência.
À todos que fizeram e fazem parte do Laboratório de Computação Gráfica, pelos
momentos de descontração e aprendizado.
Aos amigos do Instituto de Matemática e CPMAT, em especial ao Diego, Matheus,
Robson e Vinícius, que através de nossos diversos momentos de descontração tornaram
esta jornada mais leve.
Aos docentes do Instituto de Matemática que tanto contribuíram na minha formação
acadêmica e à todos que fazem a coordenação do programa, que me ajudaram com
esclarecimentos e com o acompanhamento de minha vida acadêmica junto ao departamento.
Por fim, agradeço à Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
(CAPES) pelo suporte financeiro durante estes 2 anos que estive com bolsa de mestrado
PICME.
Resumo
Devido à recente popularização dos sensores de profundidade e de movimento, o reconhecimento eficiente de gestos humanos tem se apresentado como uma alternativa para
interação homem-máquina. Nesta dissertação tratamos, em particular, do reconhecimento
de gestos da mão em tempo real utilizando o sensor Leap Motion. Consideramos que um
gesto dinâmico, em geral, pode ser representado por uma pequena sequência finita de
poses estáticas, as quais são treinadas e reconhecidas por um novo classificador baseado
em aprendizagem de métricas denominado Classificador de Distâncias Médias Mínimas
(DMM). Para aprender métricas no espaço de poses, experimentamos o algoritmo Large
Margin Nearest Neighbor (LMNN) nas versões linear e não-linear. Para reconhecer gestos
dinâmicos, apresentamos um classificador baseado nos Modelos ocultos de Markov (HMM)
e em grafos de ação. Com esta abordagem probabilística, mostramos que gestos dinâmicos
da mão podem ser reconhecidos em tempo real e online, ou seja, sem a necessidade
de pausas ou segmentações extras por parte do usuário. Finalmente, experimentamos o
método proposto em quatro aplicações, onde destacamos o reconhecimento de sinais da
Língua Brasileira de Sinais (LIBRAS). Os resultados apresentados mostram a robustez de
todas as variações do método proposto.
Palavras-chaves: língua brasileira de sinais, leap motion, aprendizagem de máquina,
reconhecimento de gestos, aprendizagem de métrica.
Abstract
The recent popularization of depth and motion sensors, human gestures recognition has
become an alternative for human-computer interaction. In this Masters dissertation we
focus on hand gesture recognition in real time using the Leap Motion sensor. We consider
that a dynamic gesture can be represented by a small finite sequence of static poses, which
are trained and recognized by a novel classifier based on metric learning called Minimal
Mean Distances Classifier (MMD). To learn metrics in the pose space, we experimented
the Large Margin Nearest Neighbor (LMNN) algorithm in both linear and non-linear
variants. To recognize dynamic gestures, we present a classifier based on the Hidden
Markov Model (HMM) and action graphs. Using this probabilistic approach, we show that
dynamic hand gestures can be recognized in real-time and online (not requiring pauses or
segmentation information to the user). Finally, we experimented the proposed method in
four applications, highlighting the recognition of signals of the Brazilian Sign Language
(LIBRAS). The presented results show the robustness of all variations of the proposed
method.
Keywords: brazilian sign language, leap motion, machine learning, hand gesture, metric
learning.
Lista de ilustrações
Figura 1 – Ilustração de uso do sensor Leap Motion para rastreamento de movimentos das mãos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Figura 2 – Criação do conjunto de treinamento de poses da mão e aprendizagem
da métrica linear (quadro 2, abaixo) ou não linear (quadro 2, acima). . 24
Figura 3 – Etapas do método usado no reconhecimento de poses. . . . . . . . . . . 25
Figura 4 – Etapas do treinamento dos gestos com a codificação em grafos de ação.
26
Figura 5 – Etapas do método de reconhecimento de gestos. . . . . . . . . . . . . . 26
Figura 6 – Sistema de coordenadas Leap Motion. . . . . . . . . . . . . . . . . . . 29
Figura 7 – Modelo da mão para o sistema Leap Motion. . . . . . . . . . . . . . . . 30
Figura 8 – Cinco principais características de algoritmos de aprendizagem de métricas. 37
Figura 9 – Ilustração esquemática da vizinhança de um exemplo antes da otimização da métrica dM (à esquerda) e após a otimização (à direita). A
métrica é otimizada de modo que os k = 3 vizinhos alvos de xi fiquem
dentro de uma bola de raio menor após o treinamento; ao mesmo tempo
que exemplos de classes diferentes (impostores) fiquem fora desta bola
com uma margem relativamente grande. . . . . . . . . . . . . . . . . . 42
Figura 10 – Em (a) é ilustrado um caso onde os exemplos da classe 1 cercam
os exemplos da classe 2, impossibilitando a aprendizagem de uma
métrica linear que diferencie bem as duas classes. Já em (b) temos
um caso onde os exemplos das classe 1 e 2 são compostos por dois
aglomerados diametralmente opostos, impossibilitando a aprendizagem
de uma métrica linear que aproxime exemplos da mesma classe e afaste
de classes distintas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Figura 11 – Direções principais (em vermelho) de um conjunto de pontos no plano
obtidas através do PCA. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Figura 12 – Ilustração de um caso onde duas classes de exemplos não são separáveis
linearmente, à esquerda; e o efeito produzido pelo KPCA, à direita. Os
pontos em formato de asterisco (∗) representam os centros das classes
antes e após a aplicação do KPCA. . . . . . . . . . . . . . . . . . . . . 50
Figura 13 – Representação de uma Cadeia de Markov como um grafo orientado. Os
vértices são os estados da cadeia e as arestas reprensentam a transição
de um estado si para sj com uma probabilidade pij . . . . . . . . . . . . 53
Figura 14 – Representação de um HMM como um grafo orientado. Os vértices
azuis são os estados e os vermelhos as observações. Já as arestas azuis
reprensentam as transições entre estados com probabilidades pij e as
vermelhas indicam quais os possíveis observáveis gerados a partir de
um estado si com probabilidade qik . . . . . . . . . . . . . . . . . . . . . 55
Figura 15 – (a) Juntas da mão utilizadas para visualização da pose. (b) Juntas
utilizadas para extração de descritores da mão. . . . . . . . . . . . . . 57
Figura 16 – Ilustração dos ângulos, em amarelo, utilizados como descritores de
poses invariantes a rotação e translação. Na Figura (a), os vetores, que
indicam a direção das falanges proximais, estão deslocados para obter
uma melhor visualização dos ângulos entre os mesmos. . . . . . . . . . 58
Figura 17 – Ilustração dos vetores normal e direcional da palma da mão. Note que
estes vetores definem a rotação da palma da mão. . . . . . . . . . . . . 59
Figura 18 – Ilustração da projeção do centro da palma da mão no plano XZ. Esta
projeção define a translação horizontal da mão em relação ao sensor
Leap Motion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Figura 19 – Criação dos conjuntos de treinamento e validação. . . . . . . . . . . . .
61
Figura 20 – Ilustração de limiares de fronteiras para 4 classes de exemplos no espaço
de características R2 , e de como 3 novos exemplos (marcados com um X)
deveriam ser classificados de acordo a condição imposta pelos limiares
de fronteira na função de classificação. . . . . . . . . . . . . . . . . . . 66
Figura 21 – Ilustração da intuição por trás do cálculo do limiar de fronteira εc . . . . 68
Figura 22 – Ilustração das etapas de simplificação dos gestos do conjunto de treinamento TG̃ em pequenas sequências de key poses para a criação de um
novo conjunto de treinamento de gestos simplificados TG . . . . . . . . .
71
Figura 23 – Ilustração da etapa de codificação das classes de gestos treinadas em
grafos de ação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Figura 24 – Grafo de ação com probabilidades de transições entre 4 key poses da mão. 73
Figura 25 – Ilustração das etapas do reconhecimento de gestos offline. . . . . . . . 75
Figura 26 – Ilustração das etapas do reconhecimento de gestos online. . . . . . . . . 77
Figura 27 – Conjunto de classes de poses estáticas variantes a translação utilizados
para realizar comandos gestuais em NUIs. . . . . . . . . . . . . . . . . 79
Figura 28 – Linhas do tempo de execução e reconhecimento de gestos da biblioteca
de gestos dinâmicos para comandos gestuais em NUIs segmentados manualmente (linha do tempo inferior) e segmentados de forma automática
pelo algoritmo (linha do tempo superior). . . . . . . . . . . . . . . . . 82
Figura 29 – Classes de poses estáticas para o reconhecimento dos números em
LIBRAS e gestos personalizados para as operações matemáticas básicas. 84
Figura 30 – Linhas do tempo de execução e reconhecimento de gestos utilizados para
representar os números em LIBRAS e as operações matemáticas básicas
segmentados manualmente (linha do tempo inferior) e segmentados de
forma automática pelo algoritmo (linha do tempo superior). . . . . . . 89
Figura 31 – Classes de poses estáticas para o reconhecimento de sinais estáticos do
alfabeto manual em LIBRAS e palavras como gestos dinâmicos. . . . . 90
Figura 32 – Linhas do tempo de execução e reconhecimento das palavras da frase
“A MÉTRICA LINEAR” segmentada manualmente (linha do tempo
inferior) e segmentada de forma automática pelo algoritmo utilizando
diferentes distâncias (linhas do tempo superiores). . . . . . . . . . . . . 97
Figura 33 – Linhas do tempo de execução e reconhecimento das palavras da frase
“AS POSES DO GESTO DINÂMICO” segmentada manualmente (linha
do tempo inferior) e segmentada de forma automática pelo algoritmo
utilizando diferentes distâncias (linhas do tempo superiores). . . . . . . 98
Figura 34 – Classes de poses estáticas utilizadas para o reconhecimento dos sinais
dinâmicos do alfabeto manual em LIBRAS. . . . . . . . . . . . . . . . 99
Figura 35 – Linhas do tempo de execução e reconhecimento de sinais dinâmicos
do alfabeto manual em LIBRAS segmentados manualmente (linha do
tempo inferior) e segmentados de forma automática pelo algoritmo
(linha do tempo superior). . . . . . . . . . . . . . . . . . . . . . . . . . 103
Lista de tabelas
Tabela 1 – Descrição do conjunto de gestos dinâmicos da mão para utilização de
comandos gestuais em NUIs. . . . . . . . . . . . . . . . . . . . . . . . . 79
Tabela 2 – Gestos dinâmicos da mão para reconhecimento de comandos gestuais
em NUIs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Tabela 3 – Matriz de confusão do reconhecimento de poses estáticas da biblioteca
de gestos dinâmicos utilizando as distâncias euclidiana, mahalanobis
linear e mahalanobis não linear. . . . . . . . . . . . . . . . . . . . . . .
81
Tabela 4 – Desempenho do reconhecimento das classes de gestos da biblioteca de
gestos dinâmicos para comandos gestuais em NUIs. . . . . . . . . . . . 82
Tabela 5 – Latência do reconhecimento de gestos da biblioteca de gestos dinâmicos
para comandos gestuais em NUIs em três abordagens: por quadros, por
segundo e por porcentagem de execução do gesto. . . . . . . . . . . . . 83
Tabela 6 – Gestos dinâmicos da mão para representação dos números em LIBRAS
e as operações matemáticas básicas. . . . . . . . . . . . . . . . . . . . 85
Tabela 7 – Matriz de confusão do reconhecimento de exemplos de poses estáticas
dos sinais dos números em LIBRAS e de poses estáticas dos gestos personalizados para as operações matemáticas básicas utilizando distância
euclidiana. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Tabela 8 – Matriz de confusão do reconhecimento de exemplos de poses estáticas
dos sinais dos números em LIBRAS e de poses estáticas dos gestos personalizados para as operações matemáticas básicas utilizando distância
de mahalanobis linear. . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Tabela 9 – Matriz de confusão do reconhecimento de exemplos de poses estáticas
dos sinais dos números em LIBRAS e de poses estáticas dos gestos personalizados para as operações matemáticas básicas utilizando distância
de mahalanobis não linear. . . . . . . . . . . . . . . . . . . . . . . . . . 87
Tabela 10 – Desempenho do reconhecimento das classes de gestos que representam
os números em LIBRAS e as operações matemáticas básicas. . . . . . . 88
Tabela 11 – Latência do reconhecimento dos gestos utilizados para representar os
números em LIBRAS e as operações matemáticas básicas em três
abordagens: por quadros, por segundo e por porcentagem de execução
do gesto.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Tabela 12 – Gestos dinâmicos da mão para reconhecimento de palavras utilizando o
alfabeto manual em LIBRAS. . . . . . . . . . . . . . . . . . . . . . . . 92
Tabela 13 – Matriz de confusão do reconhecimento de exemplos de poses estáticas do
conjunto de testes de poses dos sinais estáticos em LIBRAS utilizando
distância euclidiana. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Tabela 14 – Matriz de confusão do reconhecimento de exemplos de poses estáticas
do conjunto de testes de poses de sinais estáticos em LIBRAS utilizando
distância de mahalanobis linear. . . . . . . . . . . . . . . . . . . . . . . 94
Tabela 15 – Matriz de confusão do reconhecimento de exemplos de poses estáticas
do conjunto de testes de poses de sinais estáticos em LIBRAS utilizando
distância de mahalanobis não linear. . . . . . . . . . . . . . . . . . . . 94
Tabela 16 – Desempenho do reconhecimento das classes de gestos que representam
as palavras treinadas como gestos dinâmicos. . . . . . . . . . . . . . . 95
Tabela 17 – Latência do reconhecimento dos gestos utilizados para representar
palavras da frase “A MÉTRICA LINEAR” como gestos dinâmicos
em LIBRAS utilizando a distância de mahalanobis não linear em três
abordagens: por quadros, por segundo e por porcentagem de execução
do gesto.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Tabela 18 – Latência do reconhecimento dos gestos utilizados para representar
palavras da frase “AS POSES DO GESTO DINÂMICO” como gestos
dinâmicos em LIBRAS utilizando a distância de mahalanobis não linear
em três abordagens: por quadros, por segundo e por porcentagem de
execução do gesto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Tabela 19 – Gestos dinâmicos da mão para representação dos sinais dinâmicos do
alfabeto manual em LIBRAS. . . . . . . . . . . . . . . . . . . . . . . . 100
Tabela 20 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais dinâmicos do alfabeto manual em LIBRAS utilizando
distância euclidiana. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Tabela 21 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais dinâmicos do alfabeto manual em LIBRAS utilizando
distância de mahalanobis linear. . . . . . . . . . . . . . . . . . . . . . . 101
Tabela 22 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais dinâmicos do alfabeto manual em LIBRAS utilizando
distância de mahalanobis não linear. . . . . . . . . . . . . . . . . . . . 102
Tabela 23 – Desempenho do reconhecimento das classes de gestos que representam
os sinais dinâmicos do alfabeto manual em LIBRAS. . . . . . . . . . . 102
Tabela 24 – Latência do reconhecimento dos sinais dinâmicos do alfabeto manual
em LIBRAS utilizando três abordagens: por quadros, por segundo e
por porcentagem de execução do gesto. . . . . . . . . . . . . . . . . . . 104
Sumário
Página
INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
1.1
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2
Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.1
Reconhecimento de Gestos da Mão . . . . . . . . . . . . . . . . . .
2 VISÃO GERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
22
2.1
Treinamento de Poses da Mão com Aprendizagem de Métrica . . . . . . . . 23
2.2
Reconhecimento de poses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3
Treinamento de Gestos Dinâmicos da Mão usando Grafos de Ação . . . . . 25
2.4
Reconhecimento de Gestos Dinâmicos . . . . . . . . . . . . . . . . . . . . . 25
3 PRELIMINARES
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.1
Sensores de Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2
Leap Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3
Aprendizagem de Máquina . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1
3.4
3.5
4.2
Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Aprendizagem de Métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.1
Definições Matemáticas . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.2
Formulação Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.3
Método Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.4
Large Margin Nearest Neighbor (LMNN) . . . . . . . . . . . . . . .
3.4.5
Método Não Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.6
Kernel Large Margin Nearest Neighbor (KLMNN) . . . . . . . . . .
41
51
Modelo Oculto de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.1
Cadeia de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.2
Modelo Oculto de Markov (HMM) . . . . . . . . . . . . . . . . . . . 54
4 MÉTODO
4.1
31
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
Treinamento de Poses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1
Extração de Descritores . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.2
Conjuntos de Treinamento e Validação . . . . . . . . . . . . . . . . 60
Aprendizagem da Métrica . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3
4.4
4.5
4.2.1
Caso Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2.2
Caso Não Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Reconhecimento de Poses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.1
Classificador de Distâncias Médias Mínimas (DMM) . . . . . . . . 65
4.3.2
Estimativa de Limiar de Fronteira de Classes de Poses . . . . . . . 66
Treinamento de Gestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4.1
Conjuntos de Treinamento de Gestos . . . . . . . . . . . . . . . . . 69
4.4.2
Extração de Key Poses de Gestos . . . . . . . . . . . . . . . . . . . 69
4.4.3
Codificação em Grafos de Ação . . . . . . . . . . . . . . . . . . . . 70
Reconhecimento de Gestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.1
Cenário de Reconhecimento Offline . . . . . . . . . . . . . . . . . . 73
4.5.2
Cenário de Reconhecimento Online . . . . . . . . . . . . . . . . . . 74
5 RESULTADOS E APLICAÇÕES
5.1
. . . . . . . . . . . . . . . . . . . . . .
76
Reconhecimento de Gestos Dinâmicos Para Interfaces Naturais de Usuário
(NUIs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.2
5.1.1
Análise do Reconhecimento de Poses Estáticas . . . . . . . . . . . . 80
5.1.2
Análise do Reconhecimento de Gestos Dinâmicos Offline . . . . . .
81
5.1.3
Análise do Reconhecimento de Gestos Dinâmicos Online . . . . . .
81
Reconhecimento de Sinais dos Números em LIBRAS e Gestos Personalizados
Para as Operações Matemáticas Básicas . . . . . . . . . . . . . . . . . . . 83
5.3
5.2.1
Análise do Reconhecimento de Poses Estáticas . . . . . . . . . . . . 85
5.2.2
Análise do Reconhecimento de Gestos Dinâmicos Offline . . . . . . 86
5.2.3
Análise do Reconhecimento de Gestos Dinâmicos Online . . . . . . 88
Reconhecimento de Sinais Estáticos do Alfabeto Manual em LIBRAS e de
Palavras como Gestos Dinâmicos . . . . . . . . . . . . . . . . . . . . . . . 90
5.4
5.3.1
Análise do Reconhecimento de Poses Estáticas . . . . . . . . . . . .
91
5.3.2
Análise do Reconhecimento do Gestos Dinâmicos Offline . . . . . . 93
5.3.3
Análise do Reconhecimento de Gestos Dinâmicos Online . . . . . . 96
Reconhecimento de Sinais Dinâmicos do Alfabeto Manual em LIBRAS . . 98
5.4.1
Análise do Reconhecimento de Poses Estáticas . . . . . . . . . . . . 100
5.4.2
Análise do Reconhecimento de Gestos Dinâmicos Offline . . . . . . 102
5.4.3
Análise do Reconhecimento de Gestos Dinâmicos Online . . . . . . 103
CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
6.1
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
18
INTRODUÇÃO
O reconhecimento de gestos vem se apresentando como uma nova altenativa para
a interação homem-máquina, possibilitando o desenvolvimento de novas aplicações em
realidade virtual, interfaces naturais de usuário, jogos imersivos e reconhecimento de
línguas de sinais. Graças à recente popularização de sensores, tais como Microsoft Kinect
[1], Intel RealSense 3D [2] ou Leap Motion [3] (Figura 1), por exemplo, ocorreram muitos
avanços nesta área. Estes sensores são capazes de detectar e rastrear diferentes partes do
corpo humano. No entanto, o reconhecimento de gestos humanos ainda é uma tarefa difícil
e subjetiva, pois um mesmo gesto pode ser realizado por diferentes usuários com diversas
variações.
Embora muitos avanços tenham sido alcançados no que diz respeito ao reconhecimento de gestos corporais utilizando sensores ópticos [4], o reconhecimento robusto de
gestos da mão utilizando estes sensores ainda é um problema pouco explorado. Em geral,
sensores ópticos tendem a ter dificuldade em rastrear a mão devido à oclusões de dedos.
Estas oclusões ocorrem devido à complexidade das juntas da mão, dependendo da pose
realizada. Por estes motivos, algoritmos de reconhecimento de gestos da mão utilizando
sensores ópticos ainda não apresentam alto grau de acurácia.
Figura 1 – Ilustração de uso do sensor Leap Motion para rastreamento de movimentos das
mãos.
Fonte – Community, 2016.
19
1.1 Objetivos
Neste trabalho abordamos o problema de reconhecimento de gestos dinâmicos da
mão utilizando o sensor Leap Motion. Consideramos que um gesto dinâmico pode ser
codificado como uma sequência de poses chave (key poses [6]), e buscamos desenvolver
classificadores para poses estáticas da mão, os quais são incorporados em um classificador
de gestos dinâmicos da mão.
Para o problema de reconhecimento de poses estáticas da mão, utilizamos aprendizado de máquina. Mais especificamente, nosso método procurará aprender métricas que
melhorem o desempenho do classificador de Distâncias Médias Mínimas (DMM) proposto.
Para isto, criamos conjuntos de treinamento de poses estáticas e passamos estes conjuntos
como entrada para algoritmos de aprendizagem de métricas linear e não linear. As métricas
calculadas são usadas no lugar da distância euclidiana padrão.
Já para o reconhecimento de gestos dinâmicos da mão, treinamos gestos dinâmicos
usando uma abordagem probabilística baseada nos Modelos Ocultos de Markov (HMM),
onde supomos que as transições entre poses estáticas de um gesto dependem unicamente
da pose estática corrente do gesto, ou seja, não depende de um passado distante. Na etapa
de treinamento de gestos dinâmicos, são realizados diversos exemplos de gestos de cada
classe, a fim de generalizar todas as possíveis transições entre poses estáticas que podem
ocorrer na classe. As informações de probabilidades de transições entre poses estáticas de
cada classe de gestos são então codificadas em estruturas denominadas grafos de ação. Por
fim, estes grafos são utilizados para possibilitar o reconhecimento de gestos dinâmicos da
mão em tempo real e possivelmente online, ou seja, em tempo real sem a necessidade de
pausas ou quaisquer tipos de segmentações extras, deixando o usuário livre para realizar
os gestos da forma como bem entender.
1.2 Trabalhos Relacionados
De modo geral os trabalhos relacionados ao reconhecimento de gestos podem ter até
duas etapas: reconhecimento de poses estáticas e reconhecimento de gestos dinâmicos. Sendo
a primeira etapa geralmente um passo intermediário necessário para o reconhecimento
de gestos dinâmicos realizado na segunda etapa. Isto ocorre pois muitos dos métodos
de reconhecimento de gestos dinâmicos trabalham com o modelo de gestos sequencial
20
temporal de poses estáticas. Logo, o desenvolvimento de algoritmos de reconhecimento de
poses estáticos torna-se indispensável.
A literatura de reconhecimento de gestos utilizando aprendizagem de métrica é
escassa. Destacamos o trabalho de Berlemont[7], uma tese de doutorado desenvolvida no
Instituto Nacional de Ciências Aplicadas (INSA) de Lyon, França. Uma das aplicações foi
o desenvolvimento de um método para reconhecimento de gestos inerciais 3D relizados
com smartphones. Para isto foi utilizada uma abordagem de aprendizagem de métrica
não linear obtida através de um tipo de rede neural denominada Rede Neural Siamesa
(SNN) [8], que é uma classe de rede neural popular entre tarefas que envolvem encontrar
semelhança entre dois objetos comparáveis.
A literatura em reconhecimento de gestos é bastante diversa, abrangendo diferentes
técnicas e com inúmeras aplicações. Focamos aqui nos mais relacionados ao tema de
pesquisa deste trabalho, no entanto, recomendamos ao leitor [9, 10, 11, 12] para uma
apresentação mais abrangente dos trabalhos relacionados.
Mais relacionado com nossa abordagem é o trabalho de Miranda et al.[6], que
propõe um modelo de reconhecimento de gestos corporais utilizando o sensor Kinect como
dispositivo de extração de recursos. Cada pose estática foi descrita com uma representação
angular adaptada das articulações do esqueleto fornecido pelo sensor Kinect. Para detecção
e classificações de poses estáticas, foi utilizado um classificador multi-classe derivado
das Máquinas de Vetores de Suporte (SVM). Enquanto para o reconhecimento de gestos
dinâmicos foi proposto um esquema de florestas de decisão, onde cada raíz da floresta
é uma key pose do gesto, as folhas representam classes de gestos e caminhos da raíz às
folhas representam sequências de key poses dos respectivos gestos das folhas. Com esta
abordagem foi possível efetuar o reconhecimento de gestos dinâmicos corporais de forma
online (em tempo real). No entanto, este método possui o problema de latência alta, uma
vez que a identificação dos gestos só ocorre após o término da execução dos mesmos.
Para corrigir o problema de latência observado em [6], Vieira et al.[13] propôs a
utilização de um método de reconhecimento de gestos mais adequado que possibilita o
reconhecimento de ações humanas com baixa latência. Para isto, substituiu o método de
florestas de decisão pela abordagem probabilística de grafos de ação [14]. Além disso, foram
desenvolvidas outras melhorias, como por exemplo: a possibilidade de reconhecimento de
21
gestos que diferem apenas pela velocidade de execução.
1.2.1 Reconhecimento de Gestos da Mão
No que diz respeito ao reconhecimento de gestos da mão, diferentes abordagens
surgiram fazendo uso de diferentes tecnologias, tais como: webcams [15], luvas coloridas
[16], luvas de dados [17] e, mais recentemente, os sensores de profundidade (como o Kinect)
[18] e de movimento (como o Leap Motion). Abaixo destacamos alguns trabalhos que
utilizaram estas duas últimas tecnologias.
Em Marin et al.[19] é proposto um esquema de reconhecimento de gestos da mão
que utiliza uma combinação de recursos extraídos de ambos os sensores Leap Motion e
Kinect. Do Leap Motion foram utilizados recursos como informações de distâncias das
pontas dos dedos ao centro da palma, ângulos de aberturas das pontas dos dedos com o
centro da palma e elevação das pontas dos dedos. Enquanto do Kinect foram utilizados
recursos como curvatura e correlação.
Em Hu et al.[20], o reconhecimento de gestos dinâmicos é feito através da análise de
imagens estáticas de trajetória do gesto utilizando Redes Neurais Convolucionais (CNN).
Cada imagem de trajetória utiliza como recursos as posições 3D das pontas dos dedos
obtidos através do sensor Leap Motion. Com esta abordagem foram reconhecidos os dígitos
de 0 a 9 “desenhados no ar” de forma segmentada, com acurácia de 98.8%.
Já Schmidt et al.[21] propõe uma abordagem de reconhecimento de gestos estáticos
da mão com o sensor Leap Motion onde foi utilizado como recursos: os ângulos entre os
dedos, ângulos entre os vetores direcionais dos dedos com o vetor normal da palma e a
distância das pontas dos dedos para o centro da palma. Foram utilizados dois classificadores,
o primeiro utilizando SVM e o segundo baseado em florestas aleatórias [22]. Em sequência
foram comparados os desempenhos de ambos os métodos na tarefa de reconhecimento de
poses de um conjunto de testes com classes de poses estáticos relativamente simples, isto
é, classes de poses estáticas que não possuem grandes oclusões de juntas e dedos da mão.
Alguns outros trabalhos recentes que utilizam técnicas híbridas, bem como outras
não abordadas nesta dissertação, são Lu et al.[23], Guo et al.[24] e John et al.[25].
Como podemos ver, a literatura em reconhecimento de gestos da mão com sensores
ópticos ainda é um campo pouco explorado, com abordagens por vezes simplistas que
22
são insatisfatórias para o desenvolvimento de aplicações reais robustas, em tempo real e
online. Em Cheng et al.[4] são discutidas algumas destas limitações, como por exemplo: os
desafios encontrados para desenvolver aplicações robustas que realizem reconhecimento
online de gestos dinâmicos da mão sem a necessidade de quaisquer tipos de pausas ou
segmentações manuais por parte do usuário.
Como contribuição para a literatura, nosso método de reconhecimento online de
gestos dinâmicos da mão, com o sensor Leap Motion, introduz no campo de reconhecimento
de gestos manuais um método, inspirado no trabalho de Vieira et al.[13], capaz de
reconhecer gestos dinâmicos da mão em tempo real com baixa latência (ou seja, de forma
antecipada), ao mesmo tempo que deixa o usuário livre para executar os gestos da forma
que bem entender. Com este trabalho contribuímos também com o desenvolvimento de
uma literatura básica em língua portuguesa a respeito do problema de aprendizagem de
métricas.
23
2 VISÃO GERAL
Tratamos neste trabalho do problema de reconhecimento de gestos estáticos (poses)
e dinâmicos da mão usando o sensor Leap Motion. No entanto, para o reconhecimento de
gestos dinâmicos, ou seja, movimentos da mão, também será necessário reconhecer poses.
Abordamos o problema de classificação e reconhecimento de poses da mão usando
aprendizado de máquina. Mais especificamente, procuramos aprender métricas que melhorem o desempenho de um classificador simples de poses da mão. Essa classificação é então
utilizada para possibilitar o reconhecimento online e offline de gestos da mão.
Para melhor esclarecimento, dividimos o método de reconhecimento de poses e
gestos em quatro etapas: treinamento de poses; reconhecimento de poses; treinamento de
gestos dinâmicos; e reconhecimento de gestos dinâmicos.
2.1 Treinamento de Poses da Mão com Aprendizagem de Métrica
Aqui é abordada a aprendizagem de métricas que melhor se adaptem aos tipos
de dados trabalhados. Inicialmente, é necessário criar um conjunto de treinamento para
distintas classes de poses da mão, onde o usuário deve fornecer exemplos de cada uma das
classes que deseje reconhecer em sua aplicação.
De acordo com a Figura 2, para cada exemplo dado, o sensor Leap Motion é
utilizado para extrair informações relevantes da pose da mão, tais como a posição das
juntas em relação ao sensor e o vetor normal da palma. Com estas informações, extraímos
inicialmente características da mão que descrevem poses estáticas de forma invariante
a rotação e translação. Posteriormente são consideradas outras características, como os
vetores normal e direcional da mão (Figura 17), e o centro da palma (Figura 18), a fim de
obter as variações de rotação e translação da mão que muitos gestos dinâmicos possuem.
Após a aquisição dos exemplos, o conjunto de treinamento obtido com informações
supervisionadas (rótulos das classes) será usado para aprender uma métrica. Caso a métrica
desejada seja linear, o algoritmo Large Margin Nearest Neighbor (LMNN) recebe como
entrada o conjunto de treinamento e calcula uma matriz que representa uma métrica de
Mahalanobis, que aproxima exemplos de uma mesma classe e distancia exemplos de classes
distintas (Figura 2, quadro 2, abaixo). Caso a métrica desejada seja não linear, o conjunto
24
de treinamento é passado como entrada para o algoritmo Kernel Principal Component
Analysis (KPCA), que mapeia os dados de maneira não linear e retorna um novo conjunto
de treinamento em um espaço de alta dimensão (Figura 2, quadro 2, acima). Este novo
conjunto de treinamento é então passado como entrada para o algoritmo LMNN, onde
uma métrica pode ser aprendida mais eficientemente.
Figura 2 – Criação do conjunto de treinamento de poses da mão e aprendizagem da métrica
linear (quadro 2, abaixo) ou não linear (quadro 2, acima).
1. extração dos descritores
𝜃𝑖 ∈ ℝ
Leap Motion
2. aprendizagem da métrica
𝑝1 , … , 𝑝𝑝 , 𝑥𝑖 ∈ ℝ3
KPCA
NOVO CONJUNTO
DE TREINAMENTO
LMNN
MÉTRICA
não linear
(𝜃1 , … , 𝜃𝑑 ) ∈ ℝ𝑑
CONJUNTO
DE
TREINAMENTO
linear
Fonte – Autor, 2017.
2.2 Reconhecimento de poses
Uma vez obtida a melhor métrica associada a um determinado conjunto de treinamento, vem a tarefa de reconhecimento de novas poses reali zadas pelo usuário em tempo
real. Para tanto, utilizamos o sensor Leap Motion e realizamos a pose a ser reconhecida.
Como na etapa anterior, o sensor extrai as características da pose executada e essas
informações são passadas para o classificador de poses. O classificador leva em conta
as distâncias entre a pose executada e representantes das classes de poses do conjunto
de treinamento, segundo a métrica aprendida anteriormente, para decidir a que classe
pertence a amostra. Um exemplo de um classificador deste tipo é o kNN. A Figura 3
ilustra este processo.
25
Figura 3 – Etapas do método usado no reconhecimento de poses.
1. execução de uma pose
𝜃𝑖 ∈ ℝ
Leap Motion
CONJUNTO
DE
TREINAMENTO
MÉTRICA
𝑝1 , … , 𝑝𝑝 , 𝑥𝑖 ∈ ℝ3
CLASSIFICADOR
(𝜃1 , … , 𝜃𝑑 ) ∈ ℝ𝑑
POSE
2. reconhecimento da pose
Fonte – Autor, 2017.
2.3 Treinamento de Gestos Dinâmicos da Mão usando Grafos de Ação
Nesta etapa é feito o treinamento de gestos dinâmicos. O usuário deve fornecer
exemplos de cada classe de gestos dinâmicos que deseja que a máquina reconheça. Estes
exemplos serão compostos por sequências de poses da mão que serão representadas pelos
descritores de poses da mão. Utilizando o classificador de poses decodificamos essas
sequências em sequências de key poses. Finalmente, utilizando uma abordagem chamada
grafos de ação, é feita uma codificação das sequências de key poses dos gestos em matrizes
de transições de probabilidades de key poses, baseadas em modelos de Markov. Desse
modo, cada classe de gesto dinâmico corresponde a um modelo codificado como um grafo
de ação. A Figura 4 ilustra este processo.
2.4 Reconhecimento de Gestos Dinâmicos
Nesta etapa o usuário poderá realizar gestos dinâmicos treinados previamente e a
máquina deve ser capaz de reconhecer o gesto realizado, de forma offline ou online (em
tempo real). Para decodificar estes gestos, será utilizado um decodificador baseado nos
Modelo Oculto de Markov (HMM) para calcular a probabilidade de cada gesto realizado
ter sido gerado a partir de cada modelo de classe de gesto treinado previamente. Estas
probabilidades serão utilizadas para inferir o gesto realizado. No reconhecimento online
este decodificador de gestos funciona em paralelo ao classificador de poses. A Figura 5
ilustra este processo.
26
Figura 4 – Etapas do treinamento dos gestos com a codificação em grafos de ação.
1. treinamento dos gestos
CONJUNTO
DE
TREINAMENTO
𝜃𝑖 ∈ ℝ
MÉTRICA
𝑝1 , … , 𝑝𝑝 , 𝑥𝑖 ∈ ℝ3
Leap Motion
CLASSIFICADOR
(𝜃1 , … , 𝜃𝑑 ) ∈ ℝ𝑑
POSE
2. reconhecimento de poses
3. codificação em grafos de ação
GRAFO DE AÇÃO
gesto para codificação
𝐾1
p13
p21
(𝐾1 , 𝑡1 )
(𝐾2 , 𝑡2 )
⋯
(𝐾𝑞 , 𝑡𝑞 )
p31
buffer
𝐾2
𝐾3
p32
Fonte – Autor, 2017.
Figura 5 – Etapas do método de reconhecimento de gestos.
1. execução de um gesto
CONJUNTO
DE
TREINAMENTO
𝜃𝑖 ∈ ℝ
MÉTRICA
𝑝1 , … , 𝑝𝑝 , 𝑥𝑖 ∈ ℝ3
Leap Motion
CLASSIFICADOR
(𝜃1 , … , 𝜃𝑑 ) ∈ ℝ𝑑
2. reconhecimento de poses
3. reconhecimento do gesto
CONJUNTO DE
GRAFOS DE AÇÃO
𝐾1
p13
gesto executado
p21
p31
(𝐾1 , 𝑡1 )
𝐾2
𝐾3
p32
GESTO
DECODIFICADOR
Fonte – Autor, 2017.
(𝐾2 , 𝑡2 )
⋯
(𝐾𝑞 , 𝑡𝑞 )
buffer
POSE
27
3 PRELIMINARES
3.1 Sensores de Profundidade
Sensores de profundidade são dispositivos capazes de capturar, em tempo real,
nuvens de pontos 3D representando a geometria de superfícies que estão em seu campo de
visão. Dessa forma, estes sensores podem ser utilizados em diversas aplicações, incluindo:
reconhecimento de gestos para o controle de dispositivos de entretenimento e utilitários domésticos, tais como televisores e consoles de jogos; realidade virtual; captura de movimento
para geração de modelos em animações, e; reconstrução de geometria 3D.
Mas para entendermos como esse mapeamento é feito é preciso dar uma descrição
geral do funcionamento de tais sensores. Em geral, existem dois componentes que sempre
estão presentes nos sensores de profundidade: projetores de luz infravermelha e câmeras
infravermelhas. O projetor serve para lançar luz infravermelha (com ou sem um padrão
definido) sobre as superfícies em seu campo de visão. Vale ressaltar que o ser humano
não é capaz de ver a luz projetada porque ela tem comprimentos de onda do intervalo
de luz não visível pelo olho humano, porém as câmeras destes sensores são capazes de
capturar luz com estas características. Uma câmera infravermelha é essencialmente a
mesma que uma câmera RGB regular, exceto que os pixels das imagens capturadas
representam comprimentos de onda no intervalo de luz infravermelha. Quando a luz é
projetada (com ou sem padrão), a câmera envia essas imagens para o processador do
sensor, que as decodifica, retornando uma imagem de profundidade do campo de visão
do sensor naquele dado instante. Matematicamente, uma imagem de profundidade é uma
função f : I × J → R, com I, J ⊂ N, tal que para cada par de pontos (x, y) do retângulo
I × J, f (x, y) = d representa a distância do sensor ao ponto correspondente na superfície
mapeada.
Normalmente os fabricantes de sensores de profundidade, como o Kinect por
exemplo [26], não disponibilizam qual padrão de luz o projetor de seus sensores utilizam,
mas vale destacar que a qualidade desse padrão implica diretamente na qualidade da
geometria capturada pelo sensor.
Outra classe de sensores, projeta luz sem utilizar padrões, se baseando em estereoscopia para reconstruir a geometria. Nestes sensores, é necessário capturar simultaneamente
28
duas imagens de posições distintas. Esta é a tecnologia utilizada, por exemplo, no sensor
Leap Motion [27]. Na próxima seção descrevemos um pouco sobre seu o funcionamento.
3.2 Leap Motion
O sensor Leap Motion, criado pela empresa homônima e apresentado ao mercado
em 2013, é uma tecnologia que consiste em um pequeno dispositivo dotado de sensores
ópticos e luz infravermelha, que faz o reconhecimento e rastreamento de mãos e dedos do
usuário em tempo real [27].
Este pequeno sensor pode ser posicionado em cima de uma mesa e, segundo o
fabricante, os sensores ópticos incorporados no dispositivo têm um campo de visão de 150
graus com um alcance que varia de 25 a 600 milímetros acima do dispositivo.
No estudo de Weichert et al.[28] foi mostrado que a precisão global média do
dispositivo é de 0,7 milímetros. Entretanto, assim como todos os sensores de profundidade
disponíveis no mercado, o Leap Motion também sofre com problemas de oclusão do alvo a
ser rastreado. Dessa forma, poderão ocorrer alguns erros grosseiros na hora do rastreamento
de alguns dedos da mão que não estejam visíveis ao sensor. Para tentar contornar esse
problema, o software Leap Motion combina os dados de seus sensores com um modelo
interno da mão humana, para assim tentar prever posições de dedos em situações de
rastreamento difíceis.
O Leap Motion utiliza um sistema de coordenadas interno, onde a origem é centrada
no topo do dispositivo. O eixo Y está na posição vertical, com valores positivos aumentando
para cima. O eixo X é paralelo a borda mais longa do dispositivo, com valores positivos
crescentes para a direita. Por fim, o eixo Z tem valores positivos na direção do usuário,
como mostra a Figura 6.
A API (Application Programming Interface) do Leap Motion fornece uma vasta
quantidade de informações de quaisquer mãos detectadas pelo dispositivo, como por
exemplo, vetor normal e direcional da palma, velocidade de deslocamento, posição das
juntas dos dedos, etc. Todas essas informações são calculadas em tempo real e fornecidas
para o usuário a cada quadro. Para isto, o Leap Motion adquire duas imagens infravermelhas
(uma de cada câmera), e usando uma tecnologia não divulgada pela empresa, extrai o
esquelo 3D da mão comparando as imagens 2D geradas por cada câmera. A taxa de
29
Figura 6 – Sistema de coordenadas Leap Motion.
Fonte – Motion, 2015.
atualização de quadros é bastande elevada, chegando a cerca de 200 quadros por segundo
[3].
A API está estruturada hierarquicamente nas classes: Frame, Hands, Arms, Fingers
e Bones. A classe Frame é essencialmente a raíz do modelo de dados do Leap Motion.
A classe Hands fornece informações sobre, por exemplo, a posição do braço a que
a mão está ligada e as listas de dedos das mãos. Métodos como Hand::palmNormal() e
Hands::direction() retornam vetores que definem a orientação da mão detectada.
A classe Arms serve para fornecer a orientação, comprimento, largura e extremidades
do braço. Quando o cotovelo não está em vista o sistema faz uma previsão baseada nas
proporções médias do comprimento do braço humano.
Já a classe Fingers fornece informações sobre cada dedo. Dedos são identificados
pelos tipos, ou seja, por polegar, indicador, médio, anular ou mindinho. Um objeto Finger
fornece um objeto Bone que descreve a posição e orientação de cada osso do dedo. Para o
Leap Motion, todos os dedos contêm 4 ossos ordenados da base a ponta, como mostra a
Figura 7.
Os ossos são identificados como:
• Metacarpo - o osso interno da mão que liga o dedo ao pulso (exceto para o polegar).
• Falange proximal - o osso da base do dedo, ligado à palma.
• Falange intermédia - o osso do meio do dedo, entre a ponta e a base.
• Falange distal - o osso da extremidade do dedo.
30
Figura 7 – Modelo da mão para o sistema Leap Motion.
Fonte – adaptado de Motion, 2015.
Uma observação importante é que o modelo para o polegar não está totalmente
de acordo com o sistema de nomenclatura anatômica padrão. Um polegar real tem um
osso a menos que os outros dedos, mas para facilidades de programação, o sistema foi
implementado com um osso metacárpio de comprimento zero, para que o polegar tenha o
mesmo número de ossos nos mesmos índices que os outros dedos. Dessa forma, no sistema
do Leap Motion, o osso metacarpo foi rotulado como falange proximal e o falange proximal
real como falange intermédia.
Como mencionado anteriormente, o software Leap Motion utiliza um modelo interno
da mão humana para fornecer um rastreamento previsível, mesmo quando os dedos de
uma mão não estão totalmente visíveis. Dessa forma, movimentos sutis de dedos, que estão
fora do campo de visão dos sensores do dipositivo, podem não ser rastreados corretamente.
A API do dispositivo é capaz de fornecer uma medida de confiabilidade do modelo da
mão rastreado, assumindo valores entre 0 e 1, que indicam o quão bem os dados rastreados
se encaixam no modelo interno da mão, sendo 0 quando os dados de rastreamento diferem
totalmente do modelo interno; 1 quando os dados rastreados se encaixam totalmente no
modelo; e valores intermediários para indicar oclusões parciais de partes da mão.
31
3.3 Aprendizagem de Máquina
Segundo Mohri et al.[29] a aprendizagem de máquina pode ser definida de forma
geral como o ramo da Ciência da Computação que estuda métodos computacionais que
usam experiência para aprender e fazer previsões sobre dados. A experiência nesse sentindo
refere-se a informações passadas para a máquina, tais informações constituem o chamado
conjunto de treinamento do problema.
A aprendizagem de máquina se preocupa em projetar algoritmos de previsão
eficientes e precisos. Tais algoritmos operam construindo um modelo a partir de amostras
de dados (conjunto de treinamento) a fim de fazer previsões ou decisões guiadas pelos
dados ao invés de seguir instruções inflexíveis e estáticas pré-programadas. Desse modo, o
tamanho e a qualidade dessa amostra de dados são cruciais para o sucesso das previsões e
decisões feitas pela máquina.
Uma vez que a qualidade de um algoritmo de aprendizagem depende dos dados
utilizados, a aprendizagem de máquina está intimamente relacionada com a análise de
dados. De uma forma geral, as técnicas de aprendizagem de máquina são métodos de
manipulação de dados que combinam conceitos fundamentais da informática com ideias
da estatística, da probabilidade e da otimização matemática.
A aprendizagem de máquina é utilizada em uma variedade de tarefas computacionais onde programar algoritmos explícitos é inviável. Exemplos de aplicações incluem a
classificação de documentos, detecção de spams, reconhecimento de voz, reconhecimento
ótico de caracteres (OCR) e reconhecimento de gestos (objetivo de pesquisa deste trabalho); além de aplicações em motores de busca, como o do Google [30], e em sistemas de
recomendação inteligentes, como o sistema de recomendação de filmes e séries da Netflix
[31].
Os problemas de aprendizagem de máquina podem diferir de acordo com diferentes
critérios, como por exemplo: o tipo de problema, a abordagem da solução e o cenário de
aprendizagem. Nesse contexto, o tipo de problema refere-se, em geral, a saída do algoritmo
de aprendizagem utilizado. A abordagem refere-se aos tipos de técnicas e algoritmos
utilizados. Enquanto o cenário de aprendizagem refere-se, em geral, ao tipo de conjunto
de treinamento do problema.
Entre os principais problemas de aprendizagem de máquina, podemos citar: classi-
32
ficação, ordenação, regressão e clusterização.
Nos problemas de classificação o objetivo é atribuir uma categoria a cada item,
como por exemplo na classificação de documentos, onde podem ser atribuídas categorias
como negócios, esportes, política ou tempo. O número de categorias nesse problema é
muitas vezes relativamente pequeno, mas pode ser exremamente grande em problemas
difíceis como no reconhecimento ótico de caracteres (OCR) ou reconhecimento de voz.
Neste trabalho, tratamos do problema de classificação de poses e gestos da mão.
Por outro lado em ordenação o objetivo é ordenar itens de acordo com algum
critério. A busca de sítios na internet, por exemplo, é um problema clássico de ordenação.
Já nos problemas de regressão o objetivo é prever um valor real para cada item.
Exemplos de regressão incluem a previsão de valores de estoque ou variações de variáveis
econômicas. Neste problema é dada uma penalidade para uma previsão incorreta baseada
na diferença de magnitude dos valores verdadeiro e previsto, ao contrário do problema de
classificação que não há uma noção de proximidade entre categorias.
Em clusterização o objetivo é particionar itens em regiões homogêneas. Esse tipo
de problema aparece geralmente quando é preciso analisar conjuntos muito grandes de
dados. Por exemplo, no contexto da análise de redes sociais, os algoritmos de clusterização
tentam encontrar grupos de usuários específicos dentre grandes grupos de pessoas.
Quanto a abordagem da solução dos problemas de aprendizagem, podemos destacar:
aprendizagem por similaridade e métrica, e aprendizagem por representação.
Na aprendizagem por similaridade e métrica são analisados pares de amostras
consideradas similares e pares de amostras consideradas menos similares. A máquina
precisa então aprender uma função de similaridade (ou uma função de distância métrica)
que possa predizer se novas amostras são similares ou não. Neste trabalho, realizamos
aprendizagem de métricas para avaliar distâncias entre poses da mão.
Já a aprendizagem por representação é utilizada quando se quer preservar a
informação das amostras, mas transformando-a de forma que a torne útil. Frenquentemente
aplicada como um passo de pré-processamento antes da máquina aprender de fato a fazer
classificações ou previsões.
Podemos ainda classificar a aprendizagem de máquina quanto aos cenários de
33
aprendizagem. Esses cenários diferem nos tipos de dados de treinamento disponíveis,
na ordem e no método pelo qual os dados de treinamento são recebidos pela máquina.
Os tipos mais comuns de aprendizagem incluídos nessa classificação são: aprendizagem
supervisionada, aprendizagem não supervisionada e aprendizagem semi-supervisionada.
Na aprendizagem supervisionada a máquina recebe um conjunto de amostras
rotuladas com categorias e o objetivo é fazer a previsão de a qual categoria novas amostras
pertencem. Este é o cenário de aprendizagem mais comum associado aos problemas de
classificação, regressão e ordenação.
Já na aprendizagem não supervisionada a máquina recebe um conjunto de amostras
sem rótulos de categorias e o objetivo é predizer a qual categoria novas amostras pertencem.
Uma vez que, em geral, não há nenhuma amostra disponível rotulada nessa configuração,
pode ser difícil avaliar quantitativamente o desempenho de uma máquina de aprendizagem
não supervisionada. Exemplos de problemas que utilizam este cenário são clusterização e
redução de dimensionalidade.
Por outro lado, na aprendizagem semi-supervisionada a máquina recebe um conjunto
de amostras composto por dados rotulados e não rotulados, e assim como nos cenários
anteriores, o objetivo é fazer a previsão de qual categoria novas amostras se encaixam.
Esse tipo de aprendizado é comum em ambientes onde os dados sem rótulos são facilmente
acessíveis, mas os rótulos são difíceis de serem obtidos. A análise das condições sob as quais
isso pode realmente ser realizado é o tema de muitas pesquisas teóricas sobre aprendizagem
de máquina. Exemplos de problemas que se enquadram nesse cenário de aprendizagem
incluem problemas de classificação, regressão e ordenação.
3.3.1 Terminologia
Agora descreveremos a terminologia utilizada em problemas de aprendizagem de
máquina. Para isto, utilizaremos o problema de reconhecimento de sinais em LIBRAS
para ilustrar melhor cada conceito. O reconhecimento de sinais em LIBRAS consiste no
problema de classificar a que classe de sinais treinadas uma nova pose pertence. Dito isto,
vamos a terminologia básica:
• Exemplos: são as amostras de dados utilizados para treinamento e avaliação. No
problema de reconhecimento de sinais, esses exemplos correspondem à coleção de po-
34
ses da mão, representando os sinais de LIBRAS, que será usada para a aprendizagem
e teste.
• Descritores: é o conjunto de atributos mais relevantes, normalmente representado
como um vetor, associado a um exemplo. No caso de poses da mão, alguns descritores
relevantes podem incluir os ângulos de abertura entre os dedos, os ângulos dos vetores
das articulações com o vetor normal da palma, a posição de algumas articulações, o
centro da palma, e assim por diante.
• Rótulos: são os valores ou classes atribuídos a exemplos. Nos problemas de classificação, os exemplos recebem rótulos representando uma classe de exemplos específica,
tais rótulos são normalmente representados com números naturais. No problema de
reconhecimento de poses da mão, as poses poderiam receber rótulos de diferentes
classes de acordo com as poses que o usuário deseje que a máquina reconheça. Por
exemplo, no problema de reconhecimento de sinais em LIBRAS, os rótulos poderiam
ser 0 para a letra A, 1 para a B, 2 para a C, e assim por diante. Já nos problemas
de regressão, os exemplos são normalmente rotulados com valores reais.
• Conjunto de treinamento: são os exemplos usados para treinar um algoritmo
de aprendizagem. No problema de reconhecimento de sinais, o conjunto de treinamento consiste em exemplos de sinais rotulados como 0, 1, 2, 3, . . . , 25, indicando
respectivamente as classes de sinais A, B, C, D, . . . , Z. No entanto, o conjunto de
treinamento pode variar bastante para os diferentes cenários de aprendizagem vistos
anteriormente.
• Conjunto de validação: são os exemplos usados para ajustar os parâmetros de
um algoritmo de aprendizagem. Pois tais algoritmos normalmente têm um ou mais
parâmetros livres, e o conjunto de validação é usado para selecionar valores apropriados para esses parâmetros do modelo. Normalmente necessário ao se trabalhar no
cenário de aprendizagem supervisionado.
• Conjunto de teste: são os exemplos utilizados para avaliar o desempenho de um
algoritmo de aprendizagem. Esse conjunto é separado dos conjuntos de treinamento
e validação e não é disponibilizado à máquina na faze de aprendizagem. No problema
de reconhecimento de sinais, o conjunto de teste consiste em uma coleção de exemplos
de poses da mão representando sinais feitos pelo usuário, para os quais o algoritmo
35
de aprendizagem deve prever o rótulo com base nos seus descritores. Estas previsões
são então comparadas com os rótulos verdadeiros afim de medir o desempenho do
algoritmo.
• Validação cruzada: é uma técnica usada para calibrar parâmetros em algoritmos de
aprendizagem de máquina, e assim melhorar o desempenho de previsão da máquina.
Normalmente busca-se tais parâmetros ótimos pelo cruzamento de dados de exemplos
do conjunto de validação e observa-se qual destes fornece o menor erro segundo
alguma função de custo pré-estabelecida.
• Espaço de características: é o espaço onde estão os descritores do conjunto de
treinamento. Normalmente um espaço vetorial Rd de dimensão d, onde d é quantidade
de descritores dos exemplos do conjunto de treinamento.
Definidos estes conceitos, podemos agora descrever com maior precisão o modelo
genérico de treinamento de uma máquina de aprendizagem. Pois em geral, algoritmos
de aprendizagem seguem um roteiro de treinamento pré-estabelecido, sendo dividido em
algumas fases.
Na primeira fase fazemos uma análise de quais descritores são mais relevantes
para os exemplos do problema, isto é, quais atributos caracterizam melhor os exemplos.
Essa fase inicial é de grande importância no desenvolvimento da solução do problema de
aprendizagem, pois descritores úteis podem efetivamente guiar algoritmos de aprendizagem
para serem robustos e precisos, enquanto que descritores mais pobres podem ser enganosos,
podendo levar a efeitos desastrosos sobre o desempenho de previsão da máquina.
Na segunda fase são coletados os exemplos, que são particionados aleatoriamente
nos conjuntos de treinamento, validação e teste. O tamanho de cada um desses conjuntos
depende de várias considerações diferentes. Por exemplo, a quantidade de dados reservados
para validação depende do número de parâmetros livres do algoritmo. Além disso, quando
a quantidade de exemplos rotulados é relativamente pequena, o conjunto de treinamento
é frequentemente escolhido para ser maior do que o conjunto de teste, uma vez que o
desempenho de aprendizagem depende diretamente do conjunto de treinamento.
Na terceira fase são usados os conjuntos de treinamento e validação pra treinar o
algoritmo de aprendizagem através da fixação de diferentes valores de seus parâmetros
36
livres. Para cada valor desses parâmetros, o algoritmo seleciona uma hipótese diferente,
escolhendo dentre elas a hipótese que resulta no melhor desempenho no conjunto de
validação.
Por fim, temos a fase de teste, que tem como objetivo fazer a análise do desempenho
do algoritmo aprendido. Aqui a máquina tenta prever os rótulos dos exemplos do conjunto
de teste. O desempenho do algoritmo é analisado usando a função de perda associada ao
problema. Por exemplo, no problema de detecção de spams, a função de perda zero-um
pode ser utilizada para comparar os rótulos previstos pelo algoritmo e os verdadeiros.
Na próxima seção, descreveremos o funcionamento geral do algoritmo de aprendizagem de métricas LMNN, que será a base do método de aprendizagem proposto para
resolver o problema de reconhecimento de poses e gestos da mão estudado neste trabalho.
3.4 Aprendizagem de Métricas
Nesta seção falaremos de um tipo especial de aprendizagem de máquina: a aprendizagem de métricas. Este problema de aprendizagem está relacionado com a aprendizagem
de uma função de distância ótimo para um problema específico; isto torna-se necessário
pelo fato de muitas vezes o problema de aprendizagem tratado exigir que certos atributos
tenham mais relevância que outros para serem corretamente classificados, ou para resolver
problemas de ordenação de instâncias por similaridade.
Os métodos e algoritmos de aprendizagem de métricas podem diferir de acordo
com muitas características, como por exemplo: cenário de aprendizagem, tipo de métrica,
escalabilidade, otimalidade da solução e redução de dimensionalidade. O diagrama da
Figura 8 mostra as principais características de algoritmos de aprendizagem de métricas.
Na característica de cenário de aprendizagem daremos enfoque a formulação totalmente supervisionada. No que diz respeito a forma da métrica, detalharemos nas próximas
subseções os casos: linear e não linear. Sobre a otimalidade da solução, focaremos no
modelo de aprendizagem de métrica global. Quanto as demais características, os detalhes
podem ser encontrados no estudo de Bellet et al.[32].
Porém, antes de prosseguirmos com a teoria básica de aprendizagem de métrica,
precisamos definir precisamente alguns conceitos matemáticos que serão utilizados com
frequência de agora em diante.
37
Figura 8 – Cinco principais características de algoritmos de aprendizagem de métricas.
Aprendizagem de métrica
Cenário de
aprendizagem
Forma da
métrica
Escalabilidade
Otimalizadade
da solução
Redução de
dimensionalidade
Totalmente
supervisionado
Linear
Com respeito
aos dados
Local
Sim
Fracamente
supervisionado
Não linear
Com respeito
as dimensões
Global
Não
Semisupervisionado
Local
Fonte – adaptado de Bellet et al., 2013.
3.4.1 Denições Matemáticas
Definição 3.1. Uma métrica num conjunto X é uma função d : X × X → R, que associa
a cada par ordenado de elementos x, y ∈ X, um número real d(x, y), chamado distância
de x a y, de modo que sejam satisfeitas as seguintes condições para quaisquer x, y ∈ X:
(a) d(x, x) = 0;
(b) Se x 6= y então d(x, x) > 0;
(c) d(x, y) = d(y, x);
(d) d(x, z) ≤ d(x, y) + d(y, z);
As condições (a) e (b) dizem que d(x, y) ≥ 0 para todo x, y ∈ X, e que d(x, y) = 0
se, e somente se, x = y. A condição (c) afirma que a distância d(x, y) é uma função
simétrica das variáveis x e y. Já (d) diz que uma métrica satisfaz a desigualdade triangular.
Quando uma função satisfaz todas as condições de uma métrica, exceto a condição (a),
chamamos essa função de pseudométrica. O par (X, d), onde X é um conjunto e d é uma
métrica em X, é chamado de espaço métrico.
Definição 3.2. Um conjunto K é chamado de cone se para todo x ∈ K tem-se ainda que
αx ∈ K para todo α ≥ 0.
38
Definição 3.3. Um cone K é dito convexo se para todos x, y ∈ K tem-se que α1 x+α2 y ∈ K
para todos α1 , α2 ≥ 0; isto é, se combinações lineares de elementos de K ainda estão em
K.
Definição 3.4. Uma matriz simétrica M ∈ SRn×n é chamada de positiva semidefinida se
xT M x ≥ 0 para todo x ∈ Rn não nulo.
O conjunto das matrizes positivas semidefinidas será representado como S+n e
usaremos a notação M 0 para dizer que M ∈ S+n , isto é, para afirmar que M é positiva
semidefinida.
Teorema 3.4.1 (Caracterização das matrizes positivas semidefinidas). Seja M
0. Então, valem as seguintes afirmações:
(a) Todos os autovalores de M são não negativos.
(b) Existe uma matriz G tal que M = GT G.
Proposição 3.4.1. O conjunto das matrizes positivas semidefinidas S+n é um cone convexo.
Demonstração. Primeiramente, temos que provar que S+n é de fato um cone. Mas isto é
simples, basta observar que se M ∈ S+n , então por definição xT M x ≥ 0, logo para todo
α ≥ 0 temos que xT (αM )x = α(xT M x) ≥ 0, o que implica que αM ∈ S+n . Para provar a
segunda parte, isto é, que S+n é convexo, basta observar que se M, N ∈ S+n , então para
todos α, β ≥ 0 temos que xT (αM + βN )x = α(xT M x) + β(xT N x) ≥ 0, o que implica que
αM + βN ∈ S+n e portanto S+n é um cone convexo.
Definição 3.5. Um kernel positivo semi-definido k(·, ·), em um conjunto não vazio X ,
é uma função k : X × X → R tal que para todo n ∈ N e todo x1 , . . . , xn ∈ X a matriz
K = (kij )n×n , kij = k(xi , xj ), é positiva semidefinida.
3.4.2 Formulação Inicial
Descreveremos agora uma formulação inicial que servirá de base para os modelos
de aprendizagem de métrica, tanto linear quanto não linear estudados neste trabalho.
Segundo Kulis[33] é proposta a seguinte formulação: dada uma função de distância
de entrada d(x, y) entre elementos x e y (a distância euclidiana, por exemplo), juntamente
39
com informações supervisionadas, isto é, com dados de treinamento rotulados, construa
˜ y) que é “melhor” do que a função de distância original.
uma nova função de distância d(x,
˜ y) = d(f (x), f (y)) para alguma função f , ou seja,
Essa função é geralmente do tipo d(x,
a máquina deve aprender algum mapeamento f e utilizar a função de distância original
sobre os dados mapeados por f .
Esta formulação pode ser classificada como global, uma vez que é aprendido um
único mapeamento f para ser aplicado a todos os dados. Outras formulações com métodos
de aprendizagem de métricas locais podem ser encontradas nos trabalhos de Wang et
al.[34] e Noh et al.[35].
Dividimos a formulação de aprendizagem de métrica global, com respeito ao
mapeamento f , em duas subclasses: linear e não linear. Em ambos os casos, tomamos
como distância de entrada a distância Euclidiana, isto é, d(x, y) = kx − yk.
No caso linear, a função f será uma transformação linear, logo poderá ser represen˜ y) = kGx − Gyk.
tada como uma matriz G, donde a distância aprendida será da forma d(x,
Mostraremos detalhadamente este caso na próxima seção.
No caso não linear, uma das técnicas mais eficazes para aprender tais mapeamentos
é transformar o problema em linear utilizando uma técnica chamada truque do kernel.
A ideia básica para este caso é aprender um mapeamento linear em um novo espaço de
características induzido por uma função não linear φ, donde a distância aprendida terá a
˜ y) = kGφ(x) − Gφ(y)k. Explicaremos detalhadamente este procedimento na
forma d(x,
Seção 3.4.5.
3.4.3 Método Linear
Introduzida pelo matemático indiano Mahalanobis[36] em 1936, a distância de
Mahalanobis refere-se originalmente a uma medida que se baseia nas correlações entre
variáveis com as quais diferentes padrões podem ser identificados e analisados. Formulada
originalmente como
dmaha (x, x0 ) =
q
(x − x0 )T Ω−1 (x − x0 ),
(3.1)
onde x e x0 são vetores aleatórios da mesma distrituição de probabilidade com matriz de
covariância Ω.
No entanto, por um abuso de terminologia comum na literatura de aprendizagem
40
de métrica, vamos o usar o termo distância de Mahalanobis entre vetores x e y para se
referir a distância quadrática
dM (x, y) =
q
(x − y)T M (x − y),
(3.2)
onde M é uma matriz positiva semidefinida. Observe que quando M é a matriz identidade,
a equação acima se torna a distância Euclidiana.
Como M é positiva semidefinida, pelo teorema 3.4.1 podemos escrevê-la como
M = GT G para alguma matriz G. Substituindo em 3.2 teremos
dM (x, y) =
q
(x − y)T GT G(x − y)
=
q
(G(x − y))T G(x − y)
=
q
(Gx − Gy)T (Gx − Gy),
ou seja, dM (x, y) = kGx − Gyk.
Assim, uma distância de Mahalanobis como formulada acima, corresponde implicitamente ao cálculo da distância Eulidiana após a projeção linear dos dados pela
transformação linear definida pela matriz G, o que coincide exatamene com a nossa
formulação inicial de aprender uma transformação linear global para ser aplicada aos
dados.
Vale lembrar que, computacionalmente, é mais vantajoso usar o quadrado da
distância do que apenas a distância Euclidiana ou de Mahalanobis comum. Dessa forma, a
partir de agora, quando nos referirmos a distância Euclidiana ou de Mahalanobis entre
dois vetores x e y estaremos nos referindo ao quadrado das suas distâncias, isto é, à
d(x, y) = (x − y)T (x − y)
(3.3)
dM (x, y) = (x − y)T M (x − y)
(3.4)
e
De modo geral, as técnicas de aprendizagem de métrica de Mahalanobis são
formuladas como um problema de otimização convexa [37]; onde o objetivos é minimizar
uma função de custo sujeita a restrições.
A seguir, descreveremos um método que tenta encontrar uma distância de Mahalanobis ótima a partir de dados de treinamento chamado Large Margin Nearest Neighbor
(LMNN), desenvolvido por Weinberger e Saul[38].
41
3.4.4 Large Margin Nearest Neighbor (LMNN)
O algoritmo LMNN foi originalmente proposto para melhorar o desempenho do
algoritmo de classificação kNN através da aprendizagem de uma distância melhor que a
distância Euclidiana [38]. No entanto, nos limitaremos por enquanto ao uso do LMNN apenas para a aprendizagem da distância de Mahalanobis, deixando o método de classificação
para ser discutido na Seção 4.3.
O objetivo principal por trás do LMNN é aprender uma pseudométrica sob a qual
todos os exemplos no conjunto de treinamento estejam mais próximos de pelo menos k
exemplos que compartilham o mesmo rótulo de classe, ao mesmo tempo que exemplos que
compartilham rótulos diferentes sejam afastados por uma distância superior.
Primeiramente, denotemos nosso conjunto de treinamento supervisionado como
T = {(x1 , y1 ), . . . , (xn , yn )} ⊂ Rd × C, onde Rd é o espaço de características de dimensão d
e C = {0, 1, . . . , c} é o conjunto de rótulos de classes. Com essa notação cada par ordenado
(xi , yi ) representa o i-ésimo exemplo do conjunto de treinamento, onde xi é vetor de
descritores e yi é o rótulo de classe exemplo.
Consideremos agora os conjuntos de pares ordenados S = {(i, j); yi = yj } e
D = {(i, j); yi 6= yj } com i, j = 1, . . . , n, onde n é a cardinalidade do cojunto de treinamento
T . Note que S contém todos os pares de índices de exemplos que compartilham o mesmo
rótulo de classe, já D contém todos os pares de índices de exemplos que têm rótulos
diferentes.
Considere ainda o conjunto de triplas ordenadas R = {(i, j, k); yi = yj =
6
yk , dM (xi , xj ) < dM (xi , xk )} com i, j, k = 1, . . . , n. Observe que R é definido para conter triplas de índices de dois exemplos da mesma classe e um terceiro de outra classe, que possuem
a característica de distância relativa satisfeita pela desigualdade dM (xi , xj ) < dM (xi , xk ),
onde dM é a distância de Mahalanobis definida por 3.4.
Denotemos ainda por vizinho alvo de um exemplo xi os exemplos pertencentes a
mesma classe de xi e que desejamos que virem vizinhos mais próximos de xi segundo a
distância aprendida dM . E por impostor aqueles exemplos que são vizinhos mais próximos
de xi mas que pertencem a uma classe diferente da de xi .
O algoritmo LMNN tentará aprender uma métrica de Mahalanobis dM que faz
com que pelo menos k vizinhos alvos de um exemplo xi se tornem de fato vizinhos mais
42
próximos, ao mesmo tempo que exemplos impostores sejam afastados de xi por uma
margem de distância relativamente grande. A Figura 9 ilustra o efeito provocado pela
distância de Mahalanobis buscada pelo algoritmo LMNN.
Figura 9 – Ilustração esquemática da vizinhança de um exemplo antes da otimização da
métrica dM (à esquerda) e após a otimização (à direita). A métrica é otimizada
de modo que os k = 3 vizinhos alvos de xi fiquem dentro de uma bola de raio
menor após o treinamento; ao mesmo tempo que exemplos de classes diferentes
(impostores) fiquem fora desta bola com uma margem relativamente grande.
Fonte – adaptado de Weinberger e Saul, 2009.
Para isto, o algoritmo LMNN busca minimizar a função de custo
L(M ) =
X
(i,j)∈S
dM (xi , yj ) + λ
X
[1 + dM (xi , xj ) − dM (xi , xk )]+
(3.5)
(i,j,k)∈R
sujeita a condição de a matriz M ser positiva semidefinida (M 0).
A minimização dessa função implica na minimização dos dois somatórios. No
primeiro somatório busca-se minimizar as distâncias entre exemplos da mesma classe, o
que faz com que vizinhos alvos de um exemplo se tornem de fato vizinhos mais próximos.
Já no segundo somatório busca-se minimizar cada termo [1 + dM (xi , xj ) − dM (xi , xk )]+ =
max(1 + dM (xi , xj ) − dM (xi , xk ), 0), o que faz com que exemplos impostores xk sejam
distanciados da classe de exempos de rótulo yi por pelo menos 1 unidade de distância. A
constante λ ∈ R serve para alterar o peso do segundo somatório, isto é, para dizermos ao
algoritmo se queremos forçar mais ou menos o distanciamento de exemplos impostores.
43
Como o LMNN busca minimizar a função L(M ) sujeita a condição M 0, temos
que o LMNN pode ser reformulado como um problema de programação semidefinida, uma
classe particular de problemas otimização convexa, da seguinte forma:
minimizar
M
sujeito a
X
dM (xi , yj ) +
(i,j)∈S
X
ξijk
(i,j,k)∈R
dM (xi , xj ) + 1 ≤ dM (xi , xk ) + ξijk
(3.6)
ξijk ≥ 0
M 0,
onde a variável de folga ξjk absorve a restrição colocada sobre os exemplos impostores e a
soma total de tais variáveis deve ser minimizada. A última condição assegura que M é
positiva semidefinida.
Embora problemas de programação semidefinida tendam a sofrer de alta complexidade computacional, este problema particular pode ser resolvido muito eficientemente
porque, na maioria dos casos, as restrições já são satisfeitas naturalmente e não precisam ser
aplicadas em tempo de execução. Para mais detalhes sobre o método de otimização, ver [38].
Vale a pena mencionar que o próprio autor do método disponibiliza uma implementação
eficiente em Matlab, disponível em [39].
3.4.5 Método Não Linear
Como vimos na seção anterior, a aprendizagem de uma distância de Mahalanobis
ótima pode ser encontrada na maioria das vezes através da formulação do problema
como um problema de otimização convexa. No entanto, visto que esta distância é uma
transformação linear, nem sempre será possível satisfazer as restrições do problema de
minimização dado pela Equação 3.6 para um conjunto de treinamento qualquer. Pois, uma
vez que transformações lineares se limitam a escalas, rotações e cisalhamentos dos dados,
muitas vezes tais operações não são capazes de lidar com certos conjuntos de dados não
separáveis linearmente. Para ilustrar melhor este fato, observe a Figura 10.
Para trabalhar com casos desse tipo é melhor aprender uma transformação não
linear. No entanto, aprender tais transformações é uma tarefa difícil, pois ao contrário
das transformações lineares que podem ser expressas como matrizes de parâmetros, o
conjunto de transformações não lineares não é prontamente parametrizado. Para aprender
44
Figura 10 – Em (a) é ilustrado um caso onde os exemplos da classe 1 cercam os exemplos da
classe 2, impossibilitando a aprendizagem de uma métrica linear que diferencie
bem as duas classes. Já em (b) temos um caso onde os exemplos das classe 1 e 2
são compostos por dois aglomerados diametralmente opostos, impossibilitando
a aprendizagem de uma métrica linear que aproxime exemplos da mesma
classe e afaste de classes distintas.
(a)
(b)
Fonte – Autor, 2017.
uma transformação do tipo, retringiremos a forma do mapeamento não linear a uma
classe particular de transformações não lineares de tal forma que os parâmetros possam
ser aprendidos eficientemente. A esta classe daremos o nome de transformações lineares
kernelizadas.
Abaixo mostraremos dois métodos de kernelização, o método padrão e um método
que utiliza Análise de Componentes Principais (PCA).
Truque do Kernel Padrão
Dado um kernel positivo semi-definido k(x, y) = φ(x)T φ(x), onde φ : Rd → H é não
linear, com H um espaço de Hilbert de dimensão possivelmente infinito; sejam φ = φ(x),
φ0 = φ(x)0 e φi = φ(xi ) exemplos mapeados em um novo espaço de características H. A
distância de Mahalanobis sobre M 0 entre dois exemplos φi e φj é
dM (φi , φj ) = (φi − φj )T M (φi − φj ) = (φi − φj )T GT G(φi − φj ).
(3.7)
Para fixar as ideias, suponha que GT = (a1 , . . . , ad ), onde cada ai é um vetor coluna,
e seja Φ = (φ1 , . . . , φn ) a matriz dos exemplos do conjunto de treinamento mapeados no
45
espaço H. A ideia principal do truque do kernel é utilizar a seguinte parametrização
GT = ΦU T
(3.8)
onde U T = (u1 , . . . , ud ), com cada ui sendo uma vetor coluna de dimensão n. Substituindo
GT = ΦU T e G = U ΦT na Equação 3.7 temos que
dM (φi , φj ) = (φi − φj )T ΦU T U ΦT (φi − φj )
= (ΦT (φi − φj ))T U T U ΦT (φi − φj )
= (ΦT φi − ΦT φj )T U T U (ΦT φi − ΦT φj ),
ou seja, dM (φi , φj ) = (ki − kj )U T U (ki − kj ), onde ki = ΦT φi = (hφ1 , φi i, . . . , hφn , φi i)T .
Nossa fórmula agora depende apenas de produtos internos hφi , φj i, e podemos, portanto,
fazer a substituição kij = hφi , φj i, exigindo que a matriz de kernels K = (kij ) seja positiva
semidefinida.
Portanto, o problema de encontrar a melhor distância de Mahalanobis no espaço
de características inicial é agora reduzido a encontrar a melhor transformação linear U .
No entanto, muitas vezes encontar U é muito mais problemático do que encontrar G no
espaço inicial como é mostrado no estudo de Chatpatanasiri et al.[40].
Uma vez encontrada a matriz U , a distância de Mahalanobis entre um novo
exemplo de teste x0 e um exemplo xi do conjunto de treinamento no novo espaço H pode
ser calculado como
dM (φi , φj ) = (k 0 − ki )T U T U (k 0 − ki ),
(3.9)
onde k 0 = (k(x0 , x1 ), . . . , k(x0 , xn ))T .
Kernel Principal Component Analysis (KPCA)
Como enfatizamos acima, embora o truque do kernel padrão possa ser aplicado
para resolver o problema da aprendizagem de métrica não linear, muitas vezes encontrar
U torna-se muito mais difícil do que encontrar G no espaço de características inicial. Para
resolver este problema, desenvolveu-se um método chamado Kernel Principal Component
Analysis (KPCA) que pode ser aplicado eficientemente para a aprendizagem de uma
métrica não linear.
Porém, antes de explicarmos a formulação do KPCA, vale a pena comentar a
formulação linear da Análise de Componentes Principais (PCA) [41]. Dado um conjunto de
46
n pontos xk ∈ Rd centrados na origem (
Pn
i=1 xi = 0), o objetivo do PCA é a diagonalização
da matriz de covariância
n
1X
C=
xk xTk .
n k=1
(3.10)
Para isto, é preciso resolver a equação de autovalores
λv = Cv
(3.11)
para autovalores λ ≥ 0 e autovetores v ∈ Rd \ {0}. É possível mostrar que a matriz de
covariância sempre é positiva semidefinida, portanto a Equação 3.11 sempre tem solução
com λ ≥ 0. Como
λv = Cv
= ( n1
=
=
1
n
1
n
n
P
k=1
n
P
k=1
n
P
xk xTk )v
xk (xTk v)
xk hv, xk i
k=1
então
v=
n
X
1
hxk , vixk .
k=1 λn
(3.12)
Portanto, os autovetores v pertecem ao subespaço dos pontos xk , k = 1, . . . , n.
Ordenando os autovalores em ordem crescente é possível mostrar que as direções
dos autovetores, correspondentes aos autovalores de maior valor, correspondem às direções
ortogonais nas quais o conjunto {xk }nk=1 tem maiores variâncias nos dados. A Figura 11
ilustra as direções principais de um conjunto de pontos no plano.
O KPCA nada mais é do que uma formulação não linear do PCA tradicional. A
motivação inicial surge pela busca de componentes principais em um espaço de característica
de dimensão mais alta.
Considere então um mapeamento não linear φ : Rd → H do conjunto de características inicial Rd em um espaço de características H de dimensão mais alta, e sejam k(·, ·),
φ = φ(x), φ0 = φ(x)0 e φi = φ(xi ) como definidos na seção anterior.
Motivados pela Equação 3.10, definimos a matriz de covariância dos exemplos φk ,
mapeados por φ, como
Ce =
n
1X
φk φTk ,
n k=1
(3.13)
47
Figura 11 – Direções principais (em vermelho) de um conjunto de pontos no plano obtidas
através do PCA.
Fonte – Autor, 2017.
e procuramos por autovalores λ ≥ 0 e autovetores ψ ∈ H \ {0} resolvendo a equação de
autovalores
e
λψ = Cψ.
(3.14)
Assim como anteriormente, podemos mostrar que cada autovetor ψ pertence ao
subespaço dos pontos φj , j = 1, . . . , n, e que existem coeficientes αj , j = 1, . . . , n, tais que
ψ=
n
X
(3.15)
αj φj
j=1
Dessa forma, faz sentindo tomar produtos internos por φi em ambos os lados da
Equação 3.11. Fazendo isto, obtemos o sistema de equações
e
λhφi , ψi = hφi , Cψi,
i = 1, . . . , n.
(3.16)
Substituindo 3.13 e 3.15 no sistema acima, e considerando as entradas kij := hφi , φj i
da matriz de kernels K, temos que
n
P
λhφi ,
j=1
λn
n
P
αj φj i = hφi , ( n1
hφi , φj iαj = hφi ,
j=1
=
λn
n
P
j=1
kij αj =
n
P
p=1
n P
n
P
φp φTp )(
n
P
αj φj )i
j=1
φp φTp αj φj i
j=1 p=1
n
P
αj
hφi , φp ihφp , φj i
p=1
j=1
n
n
P
P
αj
kip kpj .
p=1
j=1
n
P
48
Quando i varia de 1 até n podemos escrever o sistema de n equações do tipo acima
como a equação matricial
λnKα = K 2 α
(3.17)
onde α denota o vetor coluna com entradas α1 , . . . , αn . Como K é simétrica, para encontrar
as soluções de 3.17 basta resolver a equação de autovalores
λnα = Kα
(3.18)
pois, obviamente, todas as soluções de 3.18 satisfazem 3.17, e vice-versa.
Além disso, é possível mostrar que K é positiva semidefinida, portanto 3.18 possui
autovalores não-negativos como solução. Assim como no caso do PCA linear, ordenamos
os autovalores em ordem crescente. No entanto, o que nos interessa são as projeções dos
e do
pontos φi nas componentes principais (autovetores ψ da matriz de covariância C)
conjunto de pontos {φi }ni=1 contido no espaço de característica H. Para isto, encontraremos
uma representação implícita dessas projeções em função apenas dos autovetores α da
matriz de kernels K.
Sejam λ1 ≤ λ2 ≤ . . . ≤ λn os autovalores soluções de 3.18 ordenados em ordem
crescente e α1 , α2 , . . . , αn os autovetores correspondentes, e seja λp o primeiro autovalor
não nulo. Para calcular as projeções de φi em {ψ r }nr=p , o conjunto de autovetores {ψ r }nr=p
deve formar uma base ortonormal do subespaço gerado pelos pontos {φi }ni=1 . Como
cada autovetor ψ r pode ser escrito como em 3.15 e o conjunto de autovetores {αr }nr=p
é linearmente independente, então é possível mostrar que o conjunto {ψ r }nr=p também
é linearmente independente, portanto é uma base do subespaço gerado pelo conjunto
{φi }ni=1 .
Além disso, como
hψ r , ψ s i = h
=
=
n
P
αir φi ,
i=1
n P
n
P
n
P
j=1
αjs φj i
αir αjs hφi , φj i
i=1 j=1
n
n
P
P
(αjr
αjs kij )
i=1
j=1
= hαr , Kαs i,
então hψ r , ψ s i = nλs hαr , αs i. Logo, hψ r , ψ s i = 0, para r 6= s, pois os autovetores αr e αs
são ortogonais. E para que tenhamos hψ r , ψ s i = 1 quando r = s, basta normalizar os
autovetores αr de tal forma que nλr hαr , αr i = 1.
49
Feito isso, teremos uma base ortonormal {ψ r }nr=p do subespaço dos pontos {φi }ni=1 .
Donde, cada ponto φi é representado por sua projeção
ϕi = (hφi , ψ p i, . . . , hφi , ψ n i), 1 ≤ p ≤ n
(3.19)
e cada coordenada pode ser calculada implicitamente por
hφi , ψ r i = hφi ,
n
P
j=1
=
n
P
j=1
αjr φj i
αjr hφi , φj i,
ou seja,
r
hφi , ψ i =
n
X
αjr kij .
(3.20)
j=1
Já as coordenadas de um novo exemplo x ∈ Rd , do espaço de características inicial, podem
ser calculadas como a projeção ϕ = (hφ(x), ψ p i, . . . , hφ(x), ψ n i) de φ(x) nos autovetores
ψ r , onde
hφ(x), ψ r i =
n
X
αjr k(x, xj ).
(3.21)
j=1
Note que na formulação acima, estamos projetando os pontos φi nos n − p + 1
autovetores ψr correspondentes aos λp ≤ . . . ≤ n não nulos. Porém, na maioria das vezes,
muitos destes autovalores são próximos de zero, indicando que na direção do autovetor
correspondente há pouca variância nos dados. Este fato pode ser levado em conta no
momento de calcular as projeções segundo a Equação 3.19, pois pode reduzir drasticamente
a dimensão dos vetores ϕi com pouca ou nenhuma perda de informação, em troca de um
custo computacional menor.
A Figura 12 mostra o efeito do KPCA sobre um conjunto de treinamento não
separável linearmente. Os pontos foram mapeados em um espaço de características de
dimensão alta utilizando um kernel gaussiano e depois projetados em duas componentes
principais.
Centralização dos Pontos em Espaço de Alta Dimensão
Para aplicar o método do PCA ao conjunto de pontos {φi }ni=1 supomos que os dados
estavam centrados na origem, isto é, que
Pn
i=1 φi = 0. No entanto, como não conhecemos
φ : Rd → H explicitamente, então não é possível fazer essa operação diretamente sobre
os pontos φi . Além disso, centralizar os pontos xi no espaço de características inicial não
50
Figura 12 – Ilustração de um caso onde duas classes de exemplos não são separáveis
linearmente, à esquerda; e o efeito produzido pelo KPCA, à direita. Os pontos
em formato de asterisco (∗) representam os centros das classes antes e após a
aplicação do KPCA.
KPCA
Fonte – Autor, 2017.
garante que as imagens φi serão centralizadas em um espaço de características de dimensão
mais alta.
Para resolver este problema, observe que dado o conjunto {φi }ni=1 de n pontos
φi ∈ H, então o novo conjunto {φei }ni=1 , onde
1
φe := φ −
i
está centrado na origem, isto é,
Pn
i
n
X
n i=1
φi ,
(3.22)
i=1 φi = 0.
e
f representados explicitamente, não podemos calcular
Como não temos os pontos φ
i
e = hφ
e ,φ
e i diretamente. No entanto
f dos kernels k
a matriz K
ij
i
j
keij = hφei , φej i
= hφi − n1
=
=
=
n
P
φr , φj − n1
n
P
φs i
r=1
s=1
n
n
n
P
P
P
hφi , φj i − n1
hφi , φs i − n1
hφr , φj i + n12
hφr , φs i
s=1
r=1
r,s=1
n
n
n
P
P
P
kij − n1
kis − n1
krj + n12
krs
s=1
r=1
r,s=1
n
n
n
P
P
P
kij −
kis (1n )sj − (1n )ir krj +
(1n )ir krs (1n )sj , (1n )ij := 1/n.
r=1
r,s=1
j=1
Logo
f = K − 1 K − K1 + 1 K1 ,
K
n
n
n
n
(3.23)
51
onde 1n é uma matriz com entradas (1n )ij := 1/n.
Assim, antes de resolver o problema de autovalores dado na Equação 3.18 da matriz
de kernels K, deve-se executar um passo de pré-processamento recalculando as entradas
f definida pela Equação 3.23.
de K como sendo iguais as entradas da matriz K
Vale a pena também mencionar que nesta subseção supomos de forma implícita a
existência de uma função não linear φ : Rd → H que mapeia cada xi ∈ Rd para φi = φ(x)
em um espaço H de dimensão possivelmente infinito, onde o produto interno hφ(x), φ(y)i =
φ(y)T φ(x) é dado por uma função de kernel k(·, ·) no espaço de características inicial
Rd . No entanto, surge a pergunta: dada uma função de kernel positiva semidefinida
k : Rd × Rd → R, existe realmente uma função não linear φ : Rd → H tal que k(x, y) =
hφ(x), φ(y)i = φ(y)T φ(x)? A resposta para esta questão é positiva, e pode ser provada
devido a um resultado conhecido como Teorema de Mercer [42].
3.4.6 Kernel Large Margin Nearest Neighbor (KLMNN)
Na Seção 3.4.4 explicamos o funcionamento do algoritmo LMNN passando como
entrada o conjunto de treinamento supervisionado T = {(x1 , y1 ), . . . , (xn , yn )} ⊂ Rd × C.
No entanto, o algoritmo se tornava ineficiente ao se deparar com casos dos tipos mostrados
na Figura 10. Isto motivou o uso do KPCA, que nada mais é do que uma forma de
reorganizar os pontos em um espaço de dimensão alta de forma que os mesmos possam ser
separados linearmente, como mostra a Figura 12.
A partir do conjunto de treinamento inicial T calculamos um novo conjunto de
treinamento supervisionado Te = {(ϕ1 , y1 ), . . . , (ϕn , yn )} ⊂ Rm × C, onde cada ϕi ∈ Rm é
obtido através da Equação 3.19 e Rm é o subespaço dos m autovetores ψ r mais relevantes
do conjunto {φi }ni=1 , e C = {0, 1, . . . , c} é o conjunto de rótulos de classes inicial.
Tirando proveito do efeito que o KPCA provoca nos pontos, aplicamos o algoritmo
LMNN ao novo conjunto de treinamento supervisionado Te e procuramos por uma métrica
ótima no espaço de características Rm . A este processo de aplicar o LMNN com os pontos
de saída do KPCA juntamente com as informações de supervisão iniciais chamaremos
de Kernel Large Margin Nearest Neighbor (KLMNN). Para fins de classificação de um
novo exemplo x0 ∈ Rd , devemos recalcular suas coordenadas no espaço Rm através da
Equação 3.21. Isto é feito para calcular as distâncias entre x0 e os exemplos xi com a
52
métrica encontrada pelo KLMNN.
Um fato importante a saber, no contexto de aprendizagem de métrica, é a validade
da representação de um ponto φi de dimensão infinita como um vetor ϕi de dimensão
finita. Pois como o problema de aprendizagem de métrica é formulado como um problema
de otimização, então dada uma função de custo L(·) como definida pela Equação 3.5, é
necessário saber se o valor ótimo de L(·) baseado nos pontos φi é igual ao valor ótimo
de L(·) baseado nos pontos ϕi . Este fato é garantido pelo Teorema de Representação,
enunciado e demonstrado com detalhes no estudo de Chatpatanasiri et al.[40].
3.5 Modelo Oculto de Markov
Nesta seção descrevemos de forma breve o Modelo Oculto de Markov, uma ferramenta que vem sendo amplamente utilizada pela comunidade de aprendizagem de máquina
para modelagem de problemas nas quais os dados são representados como uma sequência
de observações ao longo do tempo.
Começaremos definindo Cadeia de Markov, uma ferramenta mais simples que o
Modelo Oculto de Markov generaliza, na qual as observações são os próprios estados do
modelo.
3.5.1 Cadeia de Markov
Seja S = {s1 , s2 , ..., sn } um conjunto de estados e X : Ω → S uma variável aleatória
de Ω = {t : t ≥ 0} a assumir valores do conjunto de estados S em diferentes instantes de
tempo t.
Definimos Cadeias de Markov como uma sequência de estados Xt , Xt+1 , . . . , Xt+p
que satisfaça a propriedade de que o estado da cadeia no instante de tempo seguinte
dependa apenas do estado da cadeia no tempo atual, ou seja:
P (Xt+1 = s | Xt , Xt−1 , . . . , X1 , X0 ) = P (Xt+1 = s | Xt ).
(3.24)
Esta propriedade é conhecida como propriedade de Markov e é o que caracteriza as
Cadeias de Markov.
A cadeia inicia em um dos estados com uma probabilidade preestabelecida e movese aleatoriamente de um estado para outro de acordo com probabilidades de transições
53
entre estados. Denotaremos a probabilidade de transição do estado si para o estado sj
por pij . Vale a pena comentar que essa probabilidade é independe do instante de tempo t
considerado, ou seja, pij = P (Xt+1 = sj | Xt = si ) para todo t ≥ 0. A Figura 13 exibe um
grafo orientado que ilustra um exemplo de Cadeia de Markov de três estados.
Figura 13 – Representação de uma Cadeia de Markov como um grafo orientado. Os vértices
são os estados da cadeia e as arestas reprensentam a transição de um estado
si para sj com uma probabilidade pij .
s1
p12
p31
p21
s3
s2
p33
p23
Fonte – Autor, 2017.
Normalmente essas informações de probabilidades de transições entre estados são
representadas como uma matriz P = (pij )n×n , chamada de matriz de transição de
probabilidade, onde a ij-ésima entrada representa a probabilidade pij de transição do
estado si para o estado sj . Quando não se sabe ao certo em qual estado uma Cadeia
de Markov deve iniciar, costuma-se considerar um vetor de probabilidades inicial p =
(p1 , p2 , . . . , pn ) para representar que a cadeia inicia no estado si com probabilidade pi .
Como cada transição entre estados depende apenas do estado atual na qual a cadeia
se encontra, então a probabilidade de ocorrer uma sequência de estados Xt , Xt+1 , . . . , Xt+p
é dada por
P (Xt , Xt+1 , . . . , Xt+p ) =
p−1
Y
P (Xt+k+1 | Xt+k ), t ≥ 0.
(3.25)
k=0
Desse modo, Cadeias de Markov podem ser utilizadas para classificação de padrões
que têm natureza sequencial. Considere que cada classe de um determinado problema de
classificação é representada por uma cadeia de Markov. Dada uma sequência de estados
a ser classificada, o modelo mais provável que gerou tal sequência pode ser encontrado
calculando-se as probabilidades segundo a Equação 3.25.
54
Definiremos agora o Modelo Oculto de Markov, explicitando as semelhanças e
diferenças existentes para uma Cadeia de Markov.
3.5.2 Modelo Oculto de Markov (HMM)
Um Modelo Oculto de Markov (HMM) é um modelo probabilístico composto de
um conjunto W = {w1 , w2 , . . . , wm } chamado de conjunto de observações; uma variável
aleatória Y : Ω → W , a assumir observações do conjunto W ao longo do tempo; e, assim
como no caso das Cadeias de Markov, também é composto por um conjunto de estados
S = {s1 , s2 , . . . , sn } e uma variável aleatória X : Ω → S, a assumir estados do conjunto S
ao longo do tempo. A diferença é que em um HMM não temos certeza sobre os estados
do modelo e nem sobre qual o estado no tempo t, ou seja, Xt é oculto. Além disso, em
um HMM assume-se que a variável aleatória Y depende única e exclusivamente do estado
na qual a variável aleatória X encontra-se. Dessa forma, se qik é a probabilidade de uma
observação wk ocorrer, dado que ocorreu o estado si no instante de tempo t, então
qik = P (Yt = wk | Xt = si ), t ≥ 0.
(3.26)
Assim como as Cadeias de Markov, um HMM também pode ser representado
visualmente como um grafo orientado. A Figura 14 ilustra um HMM de três estados e
quarto observações.
Normalmente essas informações de probabilidades qik são armazenadas como entradas de uma matriz de probabilidades Q, de ordem n × m, onde n é a quantidade de
estados e m a quantidade de observáveis de um HMM. E assim como no caso das Cadeias
de Markov, as probabilidades de transições pij entre estados também são armazenadas
como entradas de uma matriz de transição P , de ordem n × n.
Como cada observação gerada Yt depende apenas do estado atual Xt , então a
probabilidade de ocorrer uma sequência de observações Y = {Yt , Yt+1 , . . . , Yt+p } é dada
por
P (Y) =
X
P (Y | X ) · P (X ), t ≥ 0,
(3.27)
X
onde o somatório varia sobre todas as sequências de estados X = {Xt , Xt+1 , . . . , Xt+p }
possíveis.
55
Figura 14 – Representação de um HMM como um grafo orientado. Os vértices azuis são
os estados e os vermelhos as observações. Já as arestas azuis reprensentam as
transições entre estados com probabilidades pij e as vermelhas indicam quais
os possíveis observáveis gerados a partir de um estado si com probabilidade
qik .
q12
q11
s1
w2
w1
p31
p12
q22
p21
q31
q14
s3
s2
p33
p23
q23
q34
q33
w3
w4
Fonte – Autor, 2017.
A grande explosão combinatória de possíveis sequências torna o cálculo desta
probabilidade impraticável. Algoritmos eficientes para o cálculo de probabilidades em
HMMs podem ser encontrados em Rabiner[43].
56
4 MÉTODO
Neste capítulo explicamos detalhadamente o método de reconhecimento de poses e
gestos da mão proposto no trabalho.
4.1 Treinamento de Poses
Em qualquer sistema de aprendizagem de máquina temos uma fase inicial chamada
de fase de treinamento, que é a fase de captura de dados que servirão de base para a
máquina aprender a tomar decisões sobre novas instâncias.
Esta fase consiste na captura de exemplos de classes de poses que servirão de base
para o algoritmo de reconhecimento classificar novas poses. Quando a aprendizagem é
supervisionada, cria-se um conjunto de treinamento composto por vetores de descritores de
poses de mão, associado com informações de qual classe de poses cada vetor de descritores
representa (rótulos de classes). Explicamos detalhadamente este processo nas próximas
seções.
4.1.1 Extração de Descritores
Como definimos na Seção 3.3.1, os descritores compõem um conjunto de atributos
relevantes para descrever um objeto de entrada em um problema de aprendizagem de
máquina. Dessa forma, a escolha dos descritores apropriados para determinada aplicação
é uma tarefa que exige bastante atenção, pois uma escolha de descritores errada pode
comprometer a capacidade de generalização do modelo de aprendizagem pretendido.
Para o problema de reconhecimento de gestos do qual se refere este trabalho,
procuramos fazer a escolha de descritores de mão que mais se ajusta as necessidades de
distinção de diferentes tipos de poses estásticas. Para isto, optamos por separar a escolha
dos descritores de mão em quatro categorias de poses estáticas: invariantes, variantes
por rotação, variantes por translação e variantes por rotação e translação.
Para a visualização de poses estáticas utilizamos um modelo do esqueleto da mão
composto pela posição espacial de 21 juntas detectadas pelo sensor Leap Motion, ilustradas
na Figura 15 (a). Todavia, para a extração dos descritores escolhidos nem todas essas
juntas são relevantes. Assim, optamos por desconsiderar as posições das pontas dos dedos
57
(exceto do polegar), e a posição da junta do polegar que faz a ligação dos ossos falange
proximal e falange intermédia, como ilustra a Figura 15 (b). Para relembrar a nomenclatura
dos ossos da mão utilizada pela API do Leap Motion consultar a Figura 7. As posições das
pontas dos dedos são irrelevantes para nosso modelo pelo fato de os ângulos entre os ossos
falange intermédia e distal serem irrelevantes, visto que é inerente da própria anatomia da
mão humana este ângulo depender do ângulo de abertura entre os ossos falange proximal
e intermédia. Tente por exemplo dobrar a junta de ligação dos ossos falange proximal e
intermédia sem dobrar a junta de ligação dos ossos intermédia e distal. Esta limitação, no
entanto, não é válida para o dedo polegar, onde a limitação de movimento ocorre agora na
junta de ligação dos ossos falange proximal e falange intermédia. Neste caso optamos por
desconsiderar tal junta e considerar os ossos falange proximal e intermédia como se fossem
um único osso, ver Figura 15 (b) abaixo.
Figura 15 – (a) Juntas da mão utilizadas para visualização da pose. (b) Juntas utilizadas
para extração de descritores da mão.
(a)
(b)
Fonte – Autor, 2017.
Na categoria de poses invariantes todas as poses estáticas são representadas com
um conjunto de descritores invariantes por rotação e translação. Para isto, foram escolhidos
como descritores um conjunto de 14 ângulos: os 4 ângulos entre as falanges proximais,
Figura 16 (a); os 5 ângulos entre o vetor normal da palma e as falanges proximais, Figura
16 (b); e os 5 ângulos entre os ossos falanges intermédias e falanges proximais de cada
um dos cinco dedos da mão, Figura 16 (c). Como cada exemplo de pose estática da mão
nesta categoria é representada com 14 atributos de ângulos (todos medidos em radianos),
58
então passamos a representar uma pose estática invariante como um vetor de descritores
x ∈ R14 .
Figura 16 – Ilustração dos ângulos, em amarelo, utilizados como descritores de poses
invariantes a rotação e translação. Na Figura (a), os vetores, que indicam
a direção das falanges proximais, estão deslocados para obter uma melhor
visualização dos ângulos entre os mesmos.
(a)
(b)
(c)
Fonte – Autor, 2017.
Já na categoria de poses variantes por rotação todas as poses estáticas são
representadas com um conjunto de descritores variantes por rotação, porém, que ainda
sejam invariantes por translação. Ou seja, nesta categoria diferentes exemplos de poses
estáticas que na categoria de poses invariantes pertenceriam a mesma classe, aqui podem
pertencer a classes de poses distintas dependendo da rotação da mão definida pelos vetores
normal e direcional da palma destacados na Figura 17. Para isto, foram escolhidos todos os
14 descritores de ângulos da categoria de poses invariantes, acrescentada das 3 coordenadas
do vetor normal da palma e também das 3 coordenadas do vetor direcional da palma da
mão, totalizando assim 20 descritores. Logo, cada exemplo de pose estática nesta categoria
passa agora a ser representada como um vetor de descritores x ∈ R20 .
Na categoria de poses variantes por translação todas as poses estáticas são
representadas com um conjunto de descritores variantes por tranlação, porém, que ainda
sejam invariantes por rotação. Desta forma, nesta categoria as diferentes poses estáticas
que na categoria de poses invariantes pertenceriam a mesma classe, aqui podem pertencer a
classes de poses distintas dependendo da posição espacial da mão em relação ao sensor Leap
59
Figura 17 – Ilustração dos vetores normal e direcional da palma da mão. Note que estes
vetores definem a rotação da palma da mão.
Fonte – Autor, 2017.
Motion. Isto é importante quando se deseja que a máquina reconheça poses que dependam
da posição na qual foram realizadas, e também para reconhecer gestos caracterizados
apenas por translações de uma mesma pose da mão. Para isto, foram escolhidos todos os
14 descritores de ângulos da categoria de poses invariantes, acrescentada das coordenadas
horizontais do centro da palma da mão (eixos X e Z de acordo com o sistema de
coordenadas do sensor Leap Motion mostrado na Figura 6), totalizando assim 16 descritores.
Optamos por não utilizar a coordenada vertical (eixo Y ) para dar ao usuário a liberdade
de optar por realizar as poses mais próximas ou mais distantes do sensor, sem que o
desempenho de reconhecimento seja afetado. Além disso, como no sistema de coordenadas
do sensor os valores das coordenadas espaciais do centro da palma assumem valores altos
quando comparados com os valores dos ângulos em radianos, optamos por normalizar as
coordenadas do centro da palma por um fator de 1/300. Finalmente, cada exemplo de
pose estática fica sendo representada como um vetor de descritores x ∈ R16 .
Já na categoria de poses invariantes por rotação e translação todas as poses
estáticas são representadas com um conjunto de descritores variantes simultaneamente
por translação e rotação. Isto significa que poses estáticas que nas três classes anteriores
pertenceriam a mesma classe de poses, aqui podem pertencer a classes de poses distintas
dependendo da orientação e posição espacial da mão com relação ao sensor. Para esta
categoria, foram concatenados todos os descritores das categorias anteriores, ou seja, os 14
descritores de ângulos da categoria invariante, os 6 da categoria variantes por rotação e
60
Figura 18 – Ilustração da projeção do centro da palma da mão no plano XZ. Esta projeção
define a translação horizontal da mão em relação ao sensor Leap Motion.
centro da
palma
eixo X
eixo Z
Fonte – Autor, 2017.
os 2 da categoria variantes por translação, totalizando assim 22 descritores. Desta forma,
cada exemplo de pose estática percente a esta categoria passa agora a ser representada
como um vetor de descritores x ∈ R22 .
4.1.2 Conjuntos de Treinamento e Validação
Definidas as 4 categorias de poses estáticas e seus respectivos descritores, vamos
agora a etapa de criação dos conjuntos de treinamento de cada categoria de poses estáticas.
Para melhor esclarecimento de cada etapa, acompanhar a Figura 19.
Escolhemos primeiramente qual o tipo de categoria de poses estásticas que desejamos
criar o conjunto de treinamento, de acordo com o quadro 1 da Figura 19, e definimos
as classes de poses estáticas que serão treinadas, quadro 2 da Figura 19. Cada classe
de poses passa então a ser identificada por um rótulo de classe. Para nossos objetivos
utilizaremos o conjunto de rótulos de classes como o subconjunto dos números naturais:
C = {1, 2, . . . , m}.
Definidas as classes de poses estáticas e seus respectivos rótulos, o usuário posiciona
a mão acima do sensor e realiza exemplos de poses daquela classe, pressionando uma tecla
específica para gravação de cada exemplo, como ilustra o quadro 3 da Figura 19. Mesmo
que estes exemplos definam a mesma pose, é importante que o usuário realize os exemplos
da mesma classe de formas variadas, afim de generalizar possíveis variações de atributos
de uma classe de poses.
A cada exemplo de pose realizada, é feito a gravação do exemplo na forma de um
61
par ordenado (xi , yi ) ∈ Rd × C, onde xi ∈ Rd é o vetor de descritores que representa o
i-ésimo exemplo de pose realizada e yi é o rótulo de classe da qual o exemplo realizado
pertence, d é quantidade de descitores utilizados na categoria de poses em questão. Por
exemplo, na categoria de poses invariantes, temos que d = 14, isto implica que o vetor de
descritores das poses dessa categoria pertencem ao espaço euclidiano de dimensão 14.
Em nossos experimentos, o usuário forneceu em média 12 exemplos de poses por
classe. Destes, 8 foram armazenados no conjunto de treinamento (quadro 4.1 da Figura
19) e os outros 4 foram separados para serem utilizados no conjunto de validação (quadro
4.2 da Figura 19).
Figura 19 – Criação dos conjuntos de treinamento e validação.
1. escolha do tipo de
conjunto de treinamento
2. definição das classes de poses
Invariante
Variante por rotação
classe m
classe 0
Variante por translação
classe 1
Variante por rotação e translação
Conjunto de rótulos: 𝐶 = 0,1, … , 𝑚
4.2. conjunto de validação
3. treinamento de poses (extração de descritores)
𝜃𝑖 ∈ ℝ
Leap Motion
𝑝1 , … , 𝑝𝑝 , 𝑥𝑖 ∈ ℝ3
𝑥𝑖 = (𝜃1 , … , 𝜃𝑑 ) ∈ ℝ𝑑
𝑉=
𝑥𝑗 , 𝑐 ∈ ℝ𝑑 × 𝐶; 𝑗 = 1, … , 𝑟
4.1. conjunto de treinamento
𝑇=
𝑥𝑖 , 𝑐 ∈ ℝ𝑑 × 𝐶; 𝑖 = 1, … , 𝑛
Fonte – Autor, 2017.
Ambos os conjuntos de treinamento e validação são utilizados na fase de aprendizagem de métrica, com a diferença de que o conjunto de treinamento é utilizado diretamente
como entrada do algoritmo de aprendizagem de métrica, enquanto o conjunto de validação
é utilizado apenas para estimar os parâmetros ótimos do algoritmo.
Os conjuntos de treinamento e validação têm os seguintes formatos: T = {(xi , yi ) ∈
Rd × C; i = 1, . . . , n}, V = {(xj , yj ) ∈ Rd × C; j = 1, . . . , r}, respectivamente.
62
4.2 Aprendizagem da Métrica
Na Seção 3.4, vimos que algoritmos de aprendizagem de máquina são mais eficientes
quando utilizada internamente uma função de distância específica para o problema. Levando
isto em conta, nesta etapa, utilizamos o conjunto de treinamento criado na seção anterior
para aprender uma métrica global no espaço de descritores de poses da mão. Esta métrica
é então utilizada com o objetivo de melhorar o desempenho de classificação automática de
novas poses.
Para a aprendizagem de métrica neste trabalho, utilizamos o algoritmo LMNN
com uma implementação em Matlab desenvolvida pelo próprio autor do método. Esta
implementação pode pode ser encontrada em [39].
4.2.1 Caso Linear
Para aprender uma métrica linear no espaço de características de poses da mão,
primeiramente determinamos alguns parâmetros do algoritmo LMNN necessários para
aprendizagem da métrica, tais como: quantidade de vizinhos alvo (como definido na
Subseção 3.4.4), dimensão de saída do espaço de características e número de iterações do
algoritmo.
O parâmetro quantidade de vizinhos alvo foi escolhido como sendo o menor valor
dentre as quantidades de exemplos de cada classe do conjunto de treinamento. A dimensão
de saída do espaço de características é definida como sendo igual a dimensão de entrada;
e o número máximo de iterações do algoritmo foi escolhido empiricamente. Este último
parâmetro tem a ver com a quantidade máxima de iterações que o algoritmo LMNN deverá
executar para encontrar a métrica ótima.
Finalmente, passamos o conjunto de treinamento T = {(xi , yi ) ∈ Rd × C; i =
1, . . . , n}, juntamente com os parâmetros escolhidos, como entrada do algoritmo LMNN,
que executa um processo de otimização convexa, e retorna uma matriz G ∈ Rd×d que
determina a melhor distância de Mahalanobis
dG (x, y) = (x − y)T GT G(x − y) = kGx − Gyk2
(4.28)
entre dois vetores de descritores de exemplos de poses x e y ∈ Rd quaisquer.
O problema dessa formulação linear é que nem sempre os dados de treinamento são
63
linearmente separáveis, e portanto, a métrica aprendida pode não ser tão eficiente. Isto
nos motiva a utilizar o caso de aprendizagem de métrica não linear, descrito na Subseção
3.4.5.
4.2.2 Caso Não Linear
Para a aprendizagem de uma métrica não linear, foi utilizado o método Kernel
Principal Component Analysis (KPCA), que possibilita a projeção não linear dos exemplos
de treinamento para um espaço de dimensão mais alta, onde uma métrica pode ser
aprendida com mais eficiência. Uma implementação (em Matlab) deste método pode ser
encontrada em [44].
Primeiramente, definimos manualmente alguns parâmetros do algoritmo KPCA,
tais como: tipo de kernel, argumento do kernel e nova dimensão do espaço de
características.
O tipo de kernel se refere ao kernel PSD (ver Definição 3.5) que será utilizado
para o cálculo da projeção não linear dos exemplos de treinamento em um novo espaço de
características. Este é o parâmetro mais importante do algoritmo, pois a escolha do tipo
de kernel pode mudar consideravelmente a forma como os exemplos são projetados no
novo espaço. Os kernels implementados e suportados pelo algoritmo são: linear, polinomial,
gaussiano e sigmoidal. Cada um destes kernels tem suas particularidades. Neste trabalho,
optamos por utilizar o kernel gaussiano, definido como:
kx − x0 k2
k(x, x0 ) = exp −
,
2σ 2
!
(4.29)
onde σ é o parâmetro argumento do kernel que também deve ser passado para o
algoritmo. Optamos por este kernel uma vez que o mesmo tém se mostrado ser um dos
mais eficientes em trabalhos de pesquisa na área de aprendizagem de máquina.
O parâmetro argumento do kernel é definido por padrão como σ = 1. No
entanto, optamos por fazer a calibração do parâmetro do kernel manualmente, levando
em conta o desempenho de classificação.
Já o parâmetro nova dimensão se refere à dimensão do novo espaço de características para onde os exemplos de treinamento são mapeados não linearmente. Normalmente,
o KPCA projeta os exemplos em um espaço euclideano de dimensão no máximo igual a
quantidade de exemplos do conjunto de treinamento. No entanto, como vimos na Subseção
64
3.4.5, a dimensão desse espaço pode ser reduzida pela projeção dos exemplos de treinamento
nos autovetores mais relevantesda matriz de covariância definida pela Equação 3.13. Dessa
forma, a dimensão do espaço onde os exemplos são projetados pode ser reduzida com
nenhuma perda de informação. No nosso modelo, podemos escolher manter a dimensão do
espaço igual a quantidade de exemplos ou executar a redução de dimensão automática
optando por não projetar os exemplos em autovetores correspondentes a autovalores
próximos de zero.
Definidos estes parâmetros, passamos o conjunto de treinamento T = {(xi , yi ) ∈
Rd × C; i = 1, . . . , n}, juntamente com os parâmetros citados acima, como entrada do
algoritmo KPCA, que executa uma transformação não linear dos exemplos de treinamento
para um espaço de dimensão maior, e retorna um novo conjunto de treinamento T 0 =
{(ϕi , yi ) ∈ RD × C; i = 1, . . . , n}, mantendo a correspondência xi 7→ ϕi e com ϕi herdando
o rótulo de classe yi de xi , para todo i = 1, . . . , n.
Finalmente, passamos este novo conjunto de treinamento T 0 , com os devidos pâmetros, como entrada do algoritmo LMNN. E, assim como no caso linear, o algoritmo executa
um processo de otimização convexa e retorna uma matriz Q ∈ RD×D que corresponde a
melhor distância de Mahalanobis
dQ (ϕ, ϕ0 ) = (ϕ − ϕ0 )T QT Q(ϕ − ϕ0 ) = kQϕ − Qϕ0 k2
(4.30)
entre dois exemplos ϕ e ϕ0 quaisquer do novo espaço de características RD .
Note que como LMNN retorna uma matriz, então a métrica aprendida nesse novo
espaço de características RD é linear. No entanto, como a correspondência xi 7→ ϕi é não
linear, então a métrica linear aprendida no espaço RD corresponde a uma métrica não
linear aprendida no espaço de características inicial Rd .
4.3 Reconhecimento de Poses
Após a fase de aprendizagem da melhor métrica para o conjunto de treinamento
T = {(xi , yi ) ∈ Rd × C; i = 1, . . . , n}, passamos a etapa de reconhecimento automático de
novos exemplos de poses.
Nesta etapa, utiliza-se um classificador de poses que recebe como entrada um novo
exemplo de pose estática x ∈ Rd e, baseado em uma regra de classificação, retorna a
classe y ∈ C que mais se assemelha ao exemplo realizado. No entanto, em aprendizagem de
65
máquina, nem sempre uma nova entrada se assemelha a alguma das classes de exemplos
treinadas, ou seja, nem toda pose deve ser classificada como alguma das classes de poses
treinadas. Dessa forma, em geral, algoritmos de classificação automática necessitam saber
quando um exemplo não deve ser classificado como alguma das classes treinadas.
Explicamos abaixo como resolver este problema para o caso específico de classificação
automática de novos exemplos de poses.
4.3.1 Classicador de Distâncias Médias Mínimas (DMM)
Primeiramente, sejam TX = {x1 , . . . , xn } o conjunto dos n exemplos de poses
treinadas, Xc = {x1 , . . . , x|Xc | } ⊂ TX o subconjunto de exemplos rotulados com a classe c
e XC = {X1 , . . . , Xm }.
Definimos a função de distância média δ : Rd × X → R+ , entre um novo exemplo
de pose x ∈ Rd e a classe de poses c, por
δ(x, Xc ) =
1 X
dG (x, xi ),
|Xc | xi ∈Xc
(4.31)
onde dG : Rd × Rd → R+ é a distância de Mahalanobis ótima entre dois exemplos de poses
do espaço de características Rd , definida pela Equação 4.28.
O classificador proposto, que denominamos por Classificador de Distâncias
Médias Mínimas (DMM), é a função ρ : Rd → C ∪ {−1} definida por
c = argmin δ(x, Xy )
se δ(x, Xc ) < εc ,
−1
caso contrário
ρ(x) =
y∈C
(4.32)
onde εc é o limiar de fronteira da classe de poses c mais semelhante ao novo exemplo.
Este classificador recebe um novo exemplo de pose x ∈ Rd de rótulo de classe
desconhecido, e utilizando a função de distância média definida pela Equação 4.31, classifica
o exemplo com o rótulo da classe que o exemplo mais se assemelha. Caso o exemplo não
satisfaça a condição do limiar de fronteira da classe, o classificador retorna −1 para o
exemplo. A condição de classificação imposta no classificador pelo uso do limiar de fronteira
εc garante que o exemplo de pose realizado seja classificado como a classe c apenas caso o
exemplo esteja o suficientemente próximo da classe mais semelhante.
Na Figura 20, por exemplo, cada limiar de fronteira estipula a distância média
máxima permitida para que um novo exemplo de pose seja classificado como pertencentes a
66
classe. Isto significa que exemplos de poses que não pertençam ao interior de nenhuma das
regiões definidas pelos limiares das classes não devem ser classificadas como pertencentes
à nenhuma das classes treinadas.
Figura 20 – Ilustração de limiares de fronteiras para 4 classes de exemplos no espaço
de características R2 , e de como 3 novos exemplos (marcados com um X)
deveriam ser classificados de acordo a condição imposta pelos limiares de
fronteira na função de classificação.
1,2
1
deve ser classificado
como a classe 2
Classe 1
não deve ser classificado
como nenhuma das classes
Classe 2
𝜀1
0,8
Classe 3
𝜀2
0,6
Classe 4
x
0,4
x
0,2
0
x
deve ser classificado
como a classe 1
𝜀4
-0,2
𝜀3
-0,4
-0,6
-0,8
-1
-1,2
-1,2
-1
-0,8
-0,6
-0,4
-0,2
0
0,2
0,4
0,6
0,8
1
1,2
Fonte – Autor, 2017.
4.3.2 Estimativa de Limiar de Fronteira de Classes de Poses
Seja VX = {x1 , . . . , xr } o conjunto de poses de validação. Para cada classe de poses
c, definimos o subconjunto de poses de validação Vc ⊂ VX cujos elementos têm rótulo c.
Com estes subconjuntos estimamos um limiar de fronteira ótimo εc > 0 para cada
classe de poses. Para isto, consideramos primeiramente as funções de custo
Lc (ε) =
X
[ε − δ(xj , Xc )]+ [δ(xj , Xc0 ) − ε]+ , c = 1, . . . , m
(4.33)
xj ∈Vc
onde [∗]+ = max(∗, 0), c = argmin e c0 = argmin é o rótulo da segunda classe de poses
y∈C
y ∈ C\{c}
mais próxima de xj . Em seguida, resolvemos os problemas de otimização correspondentes:
maximizar
ε
sujeito a
X
[ε − δ(xj , Xc )]+ [δ(xj , Xc0 ) − ε]+
xj ∈Vc
ε > 0,
(4.34)
67
para c = 1, . . . , m.
Cada limiar ótimo (aquele que maximiza a função de custo correspondente), servirá
para estimar a distância média máxima permitida para que novos exemplos de poses
venham a ser classificadas como pertencentes a uma classe.
Observe que
Lc (ε) =
P
se ε ∈ (δmin , δmax ),
0
caso contrário.
xj ∈Vc [ε − δ(xj , Xc )][δ(xj , Xc0 ) − ε]
(4.35)
Dessa forma, vemos que a função de custo Lc assume seu ponto de máximo no intervalo
(δmin , δmax ). Além disso, Lc é diferenciável neste intervalo, pois, expandido o produto na
função de custo, notamos que Lc é o polinômio
Lc (ε) = −
X
ε2 +
xj ∈Vc
X
[δ(xj , Xc ) + δ(xj , Xc0 )]ε −
xj ∈Vc
X
δ(xj , Xc )δ(xj , Xc0 ).
(4.36)
xj ∈Vc
Logo, sua derivada é
L0 c (ε) = −2
X
ε+
xj ∈Vc
X
[δ(xj , Xc ) + δ(xj , Xc0 )].
(4.37)
xj ∈Vc
Sabemos que uma função diferenciável possui máximos ou mínimos locais nos
pontos onde sua derivada se anula. Portanto, a função de custo Lc assume valor máximo
no intervalo (δmin , δmax ) no ponto εc onde L0c (εc ) = 0, ou seja, em
P
εc =
xj ∈Vc [δ(xj , Xc ) + δ(xj , Xc0 )]
2|Vc |
.
(4.38)
Intuitivamente, encontrar o limiar que maximiza a função de custo Lc , equivale a
encontrar um valor εc que maximize o somátório das parcelas [ε − δ(xj , Xc )][δ(xj , Xc0 ) − ε]
para cada xj ∈ Vc . Se |Vc | = 1, então o limiar ótimo ocorre quando ε − δ(xj , Xc ) =
δ(xj , Xc0 ) − ε. Logo, o limiar de fronteira seria simplesmente o valor médio das distâncias
δ(xj , Xc ) δ(xj , Xc0 ), ou seja,
εc =
δ(xj , Xc ) + δ(xj , Xc0 )
.
2
(4.39)
Quando |Vc | > 1, então o limiar de fronteira ótimo é o valor médio das distâncias médias
δmed,c =
1 X
δ(xj , Xc )
|Vc | xj ∈Vc
(4.40)
68
e
δmed,c0 =
1 X
δ(xj , Xc0 ),
|Vc | xj ∈Vc
(4.41)
das poses de validação xj ∈ Vc para as classes de poses mais próxima (classe c) e segunda
mais próxima (classe c0 ), respectivamente. Ou seja,
εc =
δmed,c + δmed,c0
,
2
(4.42)
como ilustra a Figura 21. Observe que a equação acima é apenas uma outra forma de
reescrever o valor de εc , descrito na Equação 4.38, utilizando os valores δmed,c e δmed,c0 .
Figura 21 – Ilustração da intuição por trás do cálculo do limiar de fronteira εc .
distância para a classe de poses mais
próxima
2,5
Distância para classes de poses
𝛿 𝑥4 , 𝑋𝑐′
2
distância para a segunda classe de
poses mais próxima
𝛿𝑚𝑒𝑑,𝑐′
𝛿 𝑥1 , 𝑋𝑐′
1,5
𝛿 𝑥3 , 𝑋𝑐′
limiar de fronteira
𝛿 𝑥2 , 𝑋𝑐′
1
𝜀𝑐 =
0,5
𝛿 𝑥1 , 𝑋𝑐
0
1
𝛿𝑚𝑒𝑑,𝑐
𝛿 𝑥3 , 𝑋𝑐
𝛿 𝑥2 , 𝑋𝑐
0
2
3
Poses de validação
𝛿𝑚𝑒𝑑,𝑐 + 𝛿𝑚𝑒𝑑,𝑐′
2
𝛿 𝑥4 , 𝑋𝑐
4
5
Fonte – Autor, 2017.
4.4 Treinamento de Gestos
Passamos agora à etapa de treinamento de gestos dinâmicos da mão. Assim como
na etapa de treinamento de poses, aqui também é passado para a máquina um conjunto
de treinamento supervisionado. A diferença é que ao invés de serem passados vetores
de descritores de poses, agora são passadas para a máquina sequências de vetores de
descritores de poses, correspondentes à execução de gestos pré-estabelecidos, juntamente
com a informação de rótulo de classe de cada gesto.
Definimos um gesto g̃i como a sequência de vetores de descritores
g̃i = (x1 , x2 , . . . , xpi ),
(4.43)
69
onde cada vetor de descritor de pose xt ∈ Rd corresponde aos descritores de pose de mão
extraídos através do sensor Leap Motion no quadro de rastreamento t.
4.4.1 Conjuntos de Treinamento de Gestos
Para a criação do conjunto de treinamento de gestos, o usuário define o conjunto
de classes de gestos F = (1, 2, . . . , mg ) a serem treinados de acordo com o tipo de
categoria de poses estáticas treinada: invariantes, variantes por rotação, variantes
por translação e variantes por rotação e translação. A categoria de poses treinadas
implica diretamente nos tipos de gestos que a máquina poderá reconhecer. Feito isso, o
usuário posiciona a mão acima do sensor e realiza diversos exemplos de cada classe de
gestos dinâmicos do conjunto F.
Cria-se então o conjunto de treinamento de gestos supervisionados TG̃ = {(g̃i , hi ) ∈
G̃ × F; i = 1, . . . , ng }, onde G̃ é o conjunto dos gestos g̃i treinados, hi ∈ F é o rótulo de
classe do gesto g̃i e ng é quantidade de exemplos treinados.
4.4.2 Extração de Key Poses de Gestos
Cada elemento do conjunto de treinamento de gestos, criado na etapa anterior, é
uma sequência de vetores de descritores de poses que descrevem o gesto treinado a cada
quadro rastreado pelo sensor Leap Motion (Figura 22, quadro 1). No entanto, visto que
um gesto dinâmico, em geral, pode ser perfeitamente caracterizado por uma pequena
quantidade de poses estáticas, chamadas de key poses, então, utilizando o método de
reconhecimento de poses proposto neste trabalho, extraimos de cada gesto dinâmico da mão
uma pequena sequência de key poses que melhor caracterizam o gesto treinado. Observe,
no entanto, que tais poses devem ser treinadas previamente para possibilitar a extração
das mesmas de cada gesto. Dessa forma, é necessário que o usuário defina previamente um
conjunto de key poses que seja capaz de representar os gestos que o usuário deseja treinar
de maneira compacta e garantindo que gestos distintos serão representados por sequências
distintas. Em seguida, o usuário deve realizar o treinamento destas utilizando o método
proposto neste trabalho.
Seja K = {1, 2, . . . , |K|} o conjunto de classes de key poses treinadas. Para uma
melhor compreensão de como é feita a extração de key poses, considere o gesto
g̃i = (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 , x10 ), xj ∈ Rd .
(4.44)
70
Primeiramente, realizamos o reconhecimento de pose em cada vetor de descritor xj ∈ Rd
do gesto g̃i , obtendo uma sequência de key poses kj ∈ K (Figura 22, quadro 2). Digamos
que esta sequência seja (k1 , k1 , −1, −1, k2 , k3 , k3 , k4 , k5 , k5 ), os −1’s presentes indicam
que os vetores de descritores x3 e x4 não correspondem a nenhuma das classes de key poses
treinadas. O segundo passo é fazer a simplificação desta sequência (Figura 22, quadro
3). Para isto, removemos os −1’s que aparecem; depois, removemos blocos de key poses
repetidas com menos de M poses, pois estes podem corresponder a ruídos do sensor (M
é um parâmetro calibrado manualmente); e, por último, removemos o excesso de key
poses dos blocos de key poses repetidas sucessivamente e que possuem mais de M poses,
deixando apenas uma key pose representante por bloco. Por exemplo, com M = 2, após esta
simplificação, a sequência obtida anteriormente passa a ser apenas gi = (k1 , k3 , k5 ), kj ∈ K.
Esta filtragem também será realizada na etapa de reconhecimento de gestos.
Finalizada a extração de key poses para todos os gestos treinados, cria-se um novo
conjunto de treinamento de gestos simplificados TG = {(gi , hi ) ∈ G × F; i = 1, . . . , ng },
onde G é o conjunto dos gestos simplificados, hi ∈ F é o rótulo de classe do gesto gi e ng
é quantidade de gestos treinados (Figura 22, quadro 4).
Na próxima seção veremos como funcionam os grafos de ação e como codificar o
conjunto de treinamento de gestos TG nessas estruturas.
4.4.3 Codicação em Grafos de Ação
Um grafo de ação é uma estrutura utilizada para armazenar informações de
probabilidades de transições entre key poses referentes a uma classe de gestos. Cada grafo
de ação Ah pode ser visto como um grafo orientado ponderado, onde: os nós correspondem
às key poses do conjunto K; as arestas orientadas eij indicam a transição entre as key poses
ki e kj ; e os pesos são as probabilidades de transições ph (kj |ki ), que mede a probabilidade
de ocorrer a transição da key pose ki para kj em cada classe de gestos h.
Para codificar o conjunto de treinamento de gestos simplificados TG = {(gi , hi ) ∈
G × F; i = 1, . . . , ng }, é criado um grafo de ação para cada classe de gestos treinada.
Cada grafo é então utilizado para codificar as probabilidades de transições ph (kj |ki ) entre
as key poses que ocorrem na classe de gestos correspondente. De acordo com trabalhos
71
Figura 22 – Ilustração das etapas de simplificação dos gestos do conjunto de treinamento
TG̃ em pequenas sequências de key poses para a criação de um novo conjunto
de treinamento de gestos simplificados TG .
1. conjunto de treinamento inicial
𝒯𝐺෨ =
𝑔𝑖 , ℎ𝑖 ∈ 𝐺෨ × ℱ; 𝑖 = 1, … , 𝑛𝑔
4. novo conjunto de treinamento
𝒯𝐺 =
3. simplificação dos gestos
em pequenas sequências
de key poses
para 𝑔𝑖 = (𝑥1 , … , 𝑥𝑛𝑔 )
para 𝑥𝑖 = (𝜃1 , … , 𝜃𝑑 )
𝑔𝑖 , ℎ𝑖 ∈ 𝐺 × ℱ; 𝑖 = 1, … , 𝑛𝑔
𝑔𝑖 = (𝑘1 , … , 𝑘𝑝 )
SIMPLIFICAÇÃO
próximo gesto 𝑔𝑖
𝑔𝑖 = (𝑘1 , … , 𝑘𝑛𝑔 )
CLASSIFICADOR
classe 𝑘𝑖
próximo vetor de descritores de pose 𝑥𝑖
2. extração de classes de poses dos gestos
Fonte – Autor, 2017.
anteriores [13, 45] estas probabilidades podem ser
ph (kj |ki ) =
Nijh
,
Nih
(4.45)
onde Nijh é quantidade de vezes que ocorre a transição da key pose ki para kj na classe
de gestos h e Nih é a quantidade total de transições da key pose ki para quaisquer outras
key poses que ocorrem nos exemplos da classe de gestos h do conjunto de treinamento
de gestos simplificados. Fazendo isto para todas as classes de gestos, teremos o conjunto
de treinamento de gestos inicial TG̃ codificado como o conjunto de grafos de ação A =
{Ah ; h ∈ F}. A Figura 23 ilusta o processo de codificação das classes de gestos do conjunto
de treinamento TG no conjunto de grafos de ação A.
Para uma melhor compreensão, suponha, por exemplo, que um certo conjunto de
treinamento tenha uma classe de gestos h que, após a etapa de extração de key poses,
retornou as seguintes sequências para cada exemplo de gesto da classe: gh1 = (k1 , k3 , k1 ),
gh2 = (k1 , k2 , k3 , k1 ), gh3 = (k1 , k3 , k4 , k1 ), gh4 = (k1 , k3 , k1 ) e gh5 = (k1 , k3 , k4 , k1 ). Suponha
também que o conjunto de classes de poses estáticas treinadas seja C = {k1 , k2 , k3 , k4 }.
72
Figura 23 – Ilustração da etapa de codificação das classes de gestos treinadas em grafos
de ação.
1. novo conjunto de treinamento
𝒯𝐺 =
3. conjunto de grafos de ação
𝑔𝑖 , ℎ𝑖 ∈ 𝐺 × ℱ; 𝑖 = 1, … , 𝑛𝑔
para a classe ℎ
para a transição 𝑘𝑖 → 𝑘𝑗
𝒜 = 𝐴ℎ ; ℎ ∈ ℱ
𝐴ℎ
próxima classe ℎ
conte 𝑁𝑖𝑗ℎ e 𝑁𝑖ℎ
𝑝ℎ 𝑘𝑗 𝑘𝑖 =
𝑁𝑖𝑗ℎ
𝑁𝑖ℎ
próxima transição 𝑘𝑖 → 𝑘𝑗
2. codificação das classes de gestos em grafos de ação
Fonte – Autor, 2017.
Para criar o grafo de ação corresponde a classe de gestos h, calculamos as probabilidades
de transições entre key poses considerando todas as transições presentes nestas sequências.
h
Para a transição entre k1 e k2 , por exemplo, temos que N12
= 1, pois entre
as sequências gh1 , gh2 , gh3 , gh4 e gh5 , a transição k1 para k2 aparece apenas 1 vezes; e
N1h = 5, pois, existem 5 transições entre key poses começando em k1 . Logo, ph (k2 |k1 ) =
1/5. Analogamente, podemos ver que: ph (k3 |k1 ) = 4/5, ph (k3 |k2 ) = 1, ph (k1 |k3 ) =
3/5, ph (k4 |k3 ) = 2/5 e ph (k1 |k4 ) = 1. Todas as demais probabilidades de transições entre
key poses da classe de gesto h são nulas. A Figura 24 ilustra o grafo de ação para este
exemplo em particular.
Na próxima seção veremos como é feito o reconhecimento de novos exemplos de
gestos utilizando estes grafos de ação e de como esse tipo de codificação possibilita o
reconhecimento offline e online de gestos.
4.5 Reconhecimento de Gestos
Tendo em vista que um gesto dinâmico da mão é caracterizado como uma sequência
de vetores de descritores de pose observada ao longo do tempo, utilizamos o HMM (Seção
3.5), para realizar o reconhecimento de gestos dinâmicos da mão.
Nesta formulação, as observações correspondem aos vetores de descritores de pose
73
Figura 24 – Grafo de ação com probabilidades de transições entre 4 key poses da mão.
𝑘1
1.0
0.8
0.2
0.6
𝑘4
𝑘2
1.0
0.4
𝑘3
Fonte – Autor, 2017.
da mão (extraídos do sensor Leap Motion a cada quadro), e os estados ocultos do sistema
correspondem às key poses pela qual um gesto executado transita ao longo de sua realização.
No entanto, uma vez que temos um classificador de poses estáticas, podemos utilizá-lo para
descobrir os estados ocultos do modelo, isto é, as key poses pela qual um gesto realizado
transita ao longo do tempo. A partir desta observação, uma HMM que governa a realização
de um gesto passa a ser praticamente uma Cadeia de Markov, onde os estados são as key
poses do modelo.
Com esta formulação é possível efetuar o reconhecimento de gestos dinâmicos em
dois cenários de reconhecimento bem distintos: o offline, onde os exemplos de gestos são
realizados de forma segmentada e o reconhecimento só é ativado quando a realização do
gesto é concluída; e o online, onde o reconhecimento é feito em tempo real, isto é, durante
a realização do gesto, e o usuário não precisa segmentar cada exemplo.
4.5.1 Cenário de Reconhecimento Oine
Assim como na fase de treinamento, para o reconhecimento de gestos offline, o
usuário realiza os exemplos de gestos dinâmicos de forma bem segmentada, isto é, com
início e fim bem determinados. Em seguida, os gestos realizados passam pela etapa de
74
extração de key poses, exatamente como descrito na Seção 4.1.1. Finalizada a extração,
cada exemplo é passado para a etapa de decodificação de sua sequência de key poses
correspondente. Nesta etapa de decodificação é feita a classificação final do exemplo como
uma das classes de gestos treinadas previamente.
Para isto, é utilizado um decodificador de gestos baseado na probabilidade de
ocorrer uma sequência de estados na Cadeia de Markov de uma determinada classe de
gestos. Este decodificador utiliza os grafos de ação de cada classe de gesto treinada para
calcular a probabilidade da sequência de key poses extraídas ter sido gerada a partir de
cada classe de gesto treinada previamente. Fazendo um paralelo com Cadeias de Markov,
observe que cada grafo de ação seria o equivalente a uma estimativa da matriz de transição
de probabilidades da Cadeia de Markov que governa as propriedades de transições entre
key poses da classe de gesto correspondente.
É válido utilizar esta formulação de Cadeias de Markov porque de acordo com os
grafos de ação criados na etapa de treinamento, a key pose corrente de um gesto que está
sendo realizado depende apenas da key pose que ocorre anteriormente no gesto, ou seja,
a realização de um gesto dinâmico satisfaz a propriedade de Markov. Dessa forma,
podemos utilizar a Equação 3.25 para calcular a probabilidade da sequência de key poses
ter sido gerada por cada classe de gestos treinada.
Portanto, se um gesto g̃ realizado gerou uma sequência de key poses {k1 , k2 , . . . , kp },
então a classe de gestos treinada que mais se assemelha ao gesto g̃ é
g 0 = argmax
i∈F
p
Y
pi (kt |kt−1 ),
(4.46)
t=2
onde pi (kt |kt−1 ) é a probabilidade de um gesto da classe de gestos i realizar a transição de
key poses kt−1 para kt .
4.5.2 Cenário de Reconhecimento Online
Diferentemente do cenário de reconhecimento de gestos offline, aqui o usuário é
livre para executar os exemplos sem a necessidade de pausa entre gestos ou qualquer tipo
de segmentação inicial e final dos exemplos, sendo ideal para interfaces naturais de usuário,
por exemplo. Neste cenário, o reconhecimento de gestos dinâmicos é feito em tempo real,
isto é, de forma simultânea à realização dos exemplos.
75
Figura 25 – Ilustração das etapas do reconhecimento de gestos offline.
1. captura do gesto
gesto offline
Leap Motion
2. extraçao de poses por quadro do gesto
sequência de vetores de
descritores de poses 𝑥𝑖
CLASSIFICADOR
𝑔 = (𝑥1 , … , 𝑥𝑛𝑔 )
para 𝑥𝑖 = (𝜃1 , … , 𝜃𝑑 )
conjunto de grafos de ação
𝐴2
𝐴1
próximo 𝑥𝑖
3. simplificação do gesto
SIMPLIFICAÇÃO
𝐴0
classe 𝑘𝑖
𝑔𝑖 = (𝑘1 , … , 𝑘𝑛𝑔 )
𝑔𝑖 = (𝑘1 , … , 𝑘𝑃 )
DECODIFICADOR
OFFLINE
GESTO
4. reconhecimento do gesto
Fonte – Autor, 2017.
Para isto, vamos utilizar uma estratégia apresentada em [13], na qual o reconhecimento é ativado a cada nova key pose detectada durante a realização do gesto. Este
processo funciona da seguinte forma: para cada vetor de descritores de pose estática x ∈ Rd
obtidos do sensor Leap Motion (Figura 26, quadro 1), o classificador de poses reconhece a
classe de pose estática correspondente (Figura 26, quadro 2) e insere-a em um buffer de
key poses (Figura 26, quadro 3), obedecendo os mesmos critérios de geração das sequências
de key poses visto na Seção 4.1.1, ou seja, este buffer deve conter as poses estáticas mais
relevantes detectadas na realização do gesto até o instante corrente, sem que hajam key
poses sequenciais repetidas. A cada key pose inserida no buffer, é ativado o decodificador
de gestos (Figura 26, quadro 4), que calcula as probabilidades de cada classe de gestos ter
gerado as sequências das últimas key poses inseridas no buffer.
Para esclarecer melhor as ideias, suponha que num dado instante de tempo
foi inserido no buffer a key pose kr e o buffer tornou-se a sequência de key poses
{k1 , k2 , . . . , kr−1 , kr }. Ao ser inserida esta key pose, o decodificador de gestos é ativado. Este
decodificador analisa as probabilidades das subsequências {kr−q−1 , . . . , kr−1 , kr } de key
poses do buffer, terem sido geradas a partir de cada classe de gestos treinadas, iniciando-se
76
de q = 0, e incrementando-o se necessário. A análise é interrompida quando é encontrado
um q tal que a sequência de key poses corresponde tenha sido gerada por uma classe de
gestos com probabilidade suficientemente maior do que a probabilidade da segunda classe
de gestos mais provável. Isto significa que a subsequência {kr−q−1 , . . . , kr−1 , kr } é suficiente
para distinguir o gesto que foi executado por último.
Formalmente, suponha que em um determinado momento da realização de um
gesto o buffer de key poses seja {k1 , k2 , . . . , kr−1 , kr }, e sejam
Li (q) =
r
Y
pi (kt |kt−1 ), i ∈ F,
(4.47)
t=r−q
as probabilidades da subsequência {kr−q−1 , . . . , kr−1 , kr }, das últimas key poses inseridas
no buffer, ter sido gerada a partir de cada uma das classes de gestos treinadas i ∈ F. O
reconhecimento do gesto corrente é iniciado em q = 0 e para se
Lg0 (q) > 0 e Lg00 (q) = 0
(4.48)
Lg0 (q)
> T, Lg00 (q) 6= 0,
Lg00 (q)
(4.49)
ou
onde g 0 e g 00 ∈ F são a primeira e segunda classes de gestos treinadas mais prováveis de
que o gesto atual pertença, respectivamente; o parâmetro T é calibrado empiricamente.
Se uma destas condições de parada for satisfeita, o gesto atualmente sendo realizado
é classificado como pertencente a classe de gestos g 0 , mesmo que a realização do gesto não
tenha sido ainda concluída. Caso nenhuma das condições de parada seja satisfeita para
quaisquer dos valores q, com q ≤ r − 2 e q ≤ max; então, o decodificador de gestos aguarda
uma nova key pose ser inserida no buffer e repete o mesmo processo com o buffer de key
poses atualizado. O parâmetro max é utilizado para limitar a profundidade de busca por
key poses, uma vez que na maioria das aplicações os gestos online são determinados por
pequenas sequências de key poses, o que torna desnecessária a busca por key poses muito
antigas do buffer. O quadro 4 da Figura 26 ilustra o funcionamento deste algoritmo.
Todo este processo é feito em tempo real, permitindo a previsão antecipada de
gestos; além disso, deixa o usuário livre para realizar os gestos sem a necessidade de pausas
ou qualquer outro tipo de segmentação para que a máquina seja capaz de reconhecê-los
eficientemente.
77
Figura 26 – Ilustração das etapas do reconhecimento de gestos online.
1. captura do gesto
vetor de descritores de pose
𝑥𝑖 da pose de mão corrente
execução em tempo real
(gesto online)
Leap Motion
⋯
CLASSIFICADOR
𝑥 = (𝜃1 , … , 𝜃𝑑 )
conjunto de grafos de ação
𝐴0
2. reconhecimento da classe de pose do vetor de
descritores corrente do gesto
3. armazenamento da classe de pose corrente
em um buffer de key poses
𝑘1
𝐴2
𝐴1
⋯
𝑘𝑟−2
4. decodificação do gesto em execução
esperar próxima
key pose
classe 𝑘𝑟
𝑘𝑟
𝑘𝑟−1
q=0
𝑟
F
V
𝐿𝑖 𝑞 = ෑ 𝑝𝑖 𝑘𝑡 𝑘𝑡−1 ,
𝑖∈ ℱ
𝑡=𝑟−𝑞
Se
q ≤ 𝑟−2
e
q ≤ 𝑚𝑎𝑥
q++
F
GESTO
V
Fonte – Autor, 2017.
Se
𝐿𝑔′ 𝑞 > 0 e 𝐿𝑔′ 𝑞 = 0
ou
𝐿𝑔′ 𝑞
> 𝑇, 𝐿𝑔′′ 𝑞 ≠ 0
𝐿𝑔′′ 𝑞
78
5 RESULTADOS E APLICAÇÕES
Para gerar os experimentos deste capítulo, foi desenvolvido um software na linguagem de programação C++ com a biblioteca OpenGL para visualização do esqueleto da
mão rastreado pelo sensor Leap Motion. Foi utilizado ainda, a parte, o software Matlab
para a etapa de aprendizagem das métricas, tanto no caso linear quanto no não linear.
Foram criadas 4 aplicações distintas, uma para cada categoria de poses estáticas
consideradas (ver Subseção 4.1.1). Em cada uma delas foi feita a análise de acurácia nas
tarefas: reconhecimento de poses estáticas, reconhecimento de gestos dinâmicos de forma
offline e reconhecimento de gestos dinâmicos de forma online.
Estas aplicações englobaram: reconhecimento de gestos dinâmicos para interfaces
naturais de usuário; reconhecimento de sinais dos números em LIBRAS e operações
aritméticas; e reconhecimento de sinais do alfabeto manual em LIBRAS de forma estática
ou dinâmica. Descrevemos os resultados obtidos nas próximas seções.
5.1 Reconhecimento de Gestos Dinâmicos Para Interfaces Naturais de Usuário (NUIs)
Em computação, Interface Natural de Usuário (NUI) é um paradigma de interação
humano-máquina onde as interações são realizadas a partir de ações naturais dos seres
humanos, sem a necessidade de periféricos intermediários para interagir com a máquina,
ou caso existam, que estes estejam em segundo plano. Pode-se interagir com as NUIs
de diferentes formas, como por exemplo, utilizando toques, comandos de voz, comandos
gestuais, entre outros. E é nesta última modadidade citada que propomos uma biblioteca
de gestos dinâmicos simples para controle de uma NUI por comandos gestuais da mão
utilizando o sensor Leap Motion.
Para isto, capturamos uma base de dados composta por um total de 7 classes de
gestos dinâmicos da mão (Tabela 1). Para possibilitar o reconhecimento destes gestos,
nossa base de dados contém um conjunto de poses estáticas variantes por translação
composto de 8 poses estáticas bem definidas (Figura 27).
Classes marcadas com letra e sinal indicam a localização espacial das poses da
classe em relação ao sensor Leap Motion (ver sistema de coordenadas do Leap Motion na
Figura 6). Por exemplo, Z + indica que a classe está localizada no semi-espaço z > 0 (à
79
Tabela 1 – Descrição do conjunto de gestos dinâmicos da mão para utilização de comandos
gestuais em NUIs.
Classe
Gesto
Descrição
g0
SELECIONAR
Gesto utilizado para selecionar itens em um determinado contexto ou inicializar determinadas tarefas. Ação análoga ao
clique simples do botão esquerdo do mouse.
g1
EXECUTAR
Gesto utilizado para abrir ou executar itens selecionados em
um determinado contexto ou inicializar determinadas tarefas.
Ação análoga ao clique duplo do botão esquerdo do mouse.
g2
OPÇÕES
Gesto utilizado para visualizar opções em um determinado
contexto. Ação análoga ao clique simples do botão direito do
mouse.
g3
ESQUERDA
Gesto utilizado para alternar entre itens a esquerda em um determinado contexto. Análogo a seta para esquerda do teclado.
g4
DIREITA
Gesto utilizado para alternar entre itens a direita em um
determinado contexto. Análogo a seta para direita do teclado.
g5
CIMA
Gesto utilizado para alternar entre itens a cima em um determinado contexto. Análogo a seta para cima do teclado.
g6
BAIXO
Gesto utilizado para alternar entre itens a baixo em um determinado contexto. Análogo a seta para baixo do teclado.
Fonte – Autor, 2017.
Figura 27 – Conjunto de classes de poses estáticas variantes a translação utilizados para
realizar comandos gestuais em NUIs.
c0
c2
c4
c6
c1
c3
c5
c7
Fonte – Autor, 2017.
frente do sensor); analogamente, Z − indica que a classe está localizada no semi-espaço
z < 0 (atrás do sensor), X + no semi-espaço x > 0 (à direita do sensor) e X − no x < 0
(à esquerda do sensor). Finalmente, definimos os gestos da nossa biblioteca de gestos
dinâmicos como mostra a Tabela 2.
Para esta aplicação, criamos:
1. um conjunto de treinamento de classes de poses estáticas composto de 110 exemplos
80
Tabela 2 – Gestos dinâmicos da mão para reconhecimento de comandos gestuais em NUIs.
Classe
Key Poses
g0
c0 c1
g1
c2 c3
g2
c4 c5
g3
c6 c7
g4
c6 c7
g5
c5 c1 ou c5 c0
g6
c2 c5 ou c3 c5
Representação Visual
ou
ou
Fonte – Autor, 2017.
distribuídos entre as 8 classes de poses, sendo 67 para treinamento e 43 para validação;
2. um conjunto de treinamento de gestos dinâmicos composto de 99 exemplos de gestos
distribuídos entre as 7 classes de gestos consideradas.
O conjunto de treinamento de poses estáticas foi então passado como entrada dos
algoritmos LMNN e KLMNN para obter as melhores distâncias de mahalanobis linear e
não linear, respectivamente, para a aplicação.
5.1.1 Análise do Reconhecimento de Poses Estáticas
Para análise de acurácia das classes de poses estáticas, criamos um conjuntos de
testes com 80 exemplos de poses (10 por classe). Para o reconhecimento destas poses
utilizamos o Classificador DMM (Seção 4.3.1), com dG igual as 3 distâncias: euclidiana,
mahalanobis linear, e mahalanobis não linear. Para a aprendizagem da distância de
mahalanobis não linear foi utilizado o parâmetro argumento do kernel gaussiano σ = 0.5,
calibrado manualmente.
Para as 3 distâncias utilizadas, o algoritmo classificou corretamente todas as
70 poses do conjunto de testes (acurácia de 100.0%). Tais índices altíssimos devem-se
principalmente ao conjunto de classes de poses ser relativamente simples, não existindo
81
classes de poses com sobreposições de dedos ou oclusões que impossibilitem o sensor Leap
Motion de fazer um rastreamento de juntas com alta precisão. A Tabela 3 exibe a matriz de
confusão correspondente as informações de classifcação para as classes de poses estáticas.
Tabela 3 – Matriz de confusão do reconhecimento de poses estáticas da biblioteca de gestos
dinâmicos utilizando as distâncias euclidiana, mahalanobis linear e mahalanobis
não linear.
classe
c0
c1
c2
c3
c4
c5
c6
c7
c0
c1
c2
c3
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
c7
cD
(%)
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0
0
0
0
0
0
0
0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
c4
c5
c6
Fonte – Autor, 2017.
Cada elemento aij representa a quantidade de exemplos da classe de poses i que
foram classificados como pertencentes à classe de poses j. A coluna cD representa as
quantidades de exemplos de cada classe i que não foram classificados com pertencentes a
nenhuma das classes j. Enquanto a coluna (%) exibe a acurácia de cada classe de poses.
5.1.2 Análise do Reconhecimento de Gestos Dinâmicos Oine
Para análise de acurácia das classes de gestos dinâmicos, criamos um conjunto de
treinamento de gestos composto de 70 exemplos de gestos (10 exemplos por classe). Na
etapa de extração de key poses dos gestos foi utilizado o parâmetro comprimento de blocos
de key poses sucessivas, descrito na Seção 4.4.2, como M = 5. A Tabela 4 exibe os detalhes
de reconhecimento por classe de gestos dinâmicos. As taxas de reconhecimento novamente
foram máximas utilizando ambas as distâncias.
5.1.3 Análise do Reconhecimento de Gestos Dinâmicos Online
No reconhecimento online foram criados diversos conjuntos com execuções de gestos
online. Em todos estes conjuntos o classificador de gestos online foi capaz de reconhecer de
forma robusta e antecipada todos os gestos realizados, com uma latência de reconhecimento
82
Tabela 4 – Desempenho do reconhecimento das classes de gestos da biblioteca de gestos
dinâmicos para comandos gestuais em NUIs.
Euclidiana
Mahalanobis Linear
Mahalanobis Não Linear
Classe
Quantidade
Acertos
Acurácia (%)
Acertos
Acurácia (%)
Acertos
Acurácia (%)
g0
g1
g2
g3
g4
g5
g6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
100.0
100.0
100.0
100.0
100.0
100.0
100.0
10
10
10
10
10
10
10
100.0
100.0
100.0
100.0
100.0
100.0
100.0
10
10
10
10
10
10
10
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Geral
70
70
100.0
70
100.0
70
100.0
Fonte – Autor, 2017.
inferior a 50% da execução do gesto para maioria das classes, ou seja, o gesto é reconhecido
antes de sua execução completa.
A Figura 28 ilustra um destes conjuntos, composto pela realização de todas as 7
classes de gestos treinadas, onde foi utilizada a distância de mahalanobis não linear
para detecção das key poses. Faixas pretas indicam que no período correspondente não foi
detectado nenhum gesto sendo executado.
Figura 28 – Linhas do tempo de execução e reconhecimento de gestos da biblioteca de
gestos dinâmicos para comandos gestuais em NUIs segmentados manualmente
(linha do tempo inferior) e segmentados de forma automática pelo algoritmo
(linha do tempo superior).
𝑔0
𝑔0
0
32
𝑔1
𝑔2
𝑔3
𝑔1
𝑔2
𝑔3
150 186
300 330
440 476
530
𝑔4
𝑔5
𝑔6
𝑔4
𝑔5
𝑔6
569
680 712
840 868
quadros
Fonte – Autor, 2017.
Utilizando as outras distâncias: euclidiana e mahalanobis linear, o reconhecimento
e segmentação automática dos gestos se deram de forma bastante parecida. A Tabela 5
mostra as taxas de latência do reconhecimento dos gestos do conjunto analisado na Figura
28.
83
Tabela 5 – Latência do reconhecimento de gestos da biblioteca de gestos dinâmicos para
comandos gestuais em NUIs em três abordagens: por quadros, por segundo e
por porcentagem de execução do gesto.
Classe Latência (quadros)
g0
g1
g2
g3
g4
g5
g6
Latência (segundos) Latência (%)
32
36
30
36
39
32
28
0.80
0.90
0.75
0.90
0.97
0.80
0.70
40.0
40.0
37.5
40.0
43.3
40.0
35.0
Fonte – Autor, 2017.
Observamos de modo geral com esta aplicação, que o desempenho do Classificador
DMM apenas com a distância euclidiana já foi suficiente para um reconhecimento eficaz
tanto de poses estáticas quanto de gestos dinâmicos executados de forma offline e online.
5.2 Reconhecimento de Sinais dos Números em LIBRAS e Gestos Personalizados Para
as Operações Matemáticas Básicas
Nesta segunda aplicação, utilizamos nosso método de reconhecimento de gestos
dinâmicos para o reconhecimento dos 10 números na Língua Brasileira de Sinais (LIBRAS)
e de mais um conjunto de 5 gestos personalizados para representar as 4 operações matemáticas básicas e o operador de igualdade. Para possibilitar um reconhecimento preciso,
treinamos o conjunto de key poses da Figura 29, composto de 15 poses estáticas variantes
por rotação; onde: as poses das classe de c0 a c9 são os sinais estáticos em LIBRAS
que representam os números de 0 a 9; as classes de c11 a c14 representam as operações
matemáticas básicas: adição, subtração, multiplicação e divisão; as classes c15 e c16 são
utilizadas para representar o gesto do operador de igualdade e a classe c10 é utilizada para
facilitar o reconhecimento online dos gestos.
Vale a pena mencionar que durante a confecção desta base inserimos variações
propositais nos exemplos de treinamento de cada classe de poses. Fazemos isto para agregar
à máquina maior potencial de generalização sobre novas amostras desconhecidas de poses
da mão.
84
Figura 29 – Classes de poses estáticas para o reconhecimento dos números em LIBRAS e
gestos personalizados para as operações matemáticas básicas.
c0
c3
c6
c9
c12
c15
c1
c4
c7
c10
c13
c16
c2
c5
c8
c11
c14
Fonte – Autor, 2017.
Finalmente, treinamos os números de 0 a 9, as operações matemáticas básicas e
operador de igualdade como as classes de gestos dinâmicos mostrados na Tabela 6.
Utilizamos gestos dinâmicos terminados com a classe c10 para representar os
números ao invés apenas da representação de cada número como uma pose estática, para
possibilitar um reconhecimento online eficaz, pois desejamos evitar segmentações manuais,
deixando o usuário livre para realizar os gestos. Esta estratégia garante também que
números indesejados (fruto de ruídos do sensor ou de transições entre classes de poses)
sejam reconhecidos pela máquina acidentalmente.
Com esta estratégia podemos realizar facilmente operações matemáticas básicas
utilizando apenas gestos da mão. Por exemplo, se um usuário deseja efetuar a operação
2017 − 1995, basta que ele realize de forma online a seguinte sequência de classes de poses:
c| 2 {zc10} |c0 {zc10} c| 1 {zc10} c| 7 {zc10} c| 12 {zc10} c| 1 {zc10} c| 9 {zc10} c| 9 {zc10} c| 5 {zc10} c| 15 {zc16}
g2
g0
g1
g7
g11
g1
g9
g9
g5
g14
2
0
1
7
−
1
9
9
5
=
Para possibilitar o reconhecimento eficaz de poses e gestos para esta aplicação,
criamos:
1. um conjunto de treinamento de classes de poses estáticas composto de 306 exemplos
distribuídos entre as 17 classes de poses, sendo 185 para treinamento e 121 para
validação;
2. um conjunto de treinamento de gestos dinâmicos composto de 99 exemplos de gestos
85
Tabela 6 – Gestos dinâmicos da mão para representação dos números em LIBRAS e as
operações matemáticas básicas.
Classe
Gesto
Key Poses
g0
0
c0 c10
g1
1
c1 c10
g2
2
c2 c10
g3
3
c3 c10
g4
4
c4 c10
g5
5
c5 c10
g6
6
c6 c10
g7
7
c7 c10
g8
8
c8 c10
g9
9
c9 c10
g10
+
c11 c10
g11
−
c12 c10
g12
×
c13 c10
g13
÷
c14 c10
g14
=
c15 c16
Representação Visual
Fonte – Autor, 2017.
distribuídos entre as 15 classes de gestos consideradas.
O conjunto de treinamento de poses estáticas foi então passado como entrada dos
algoritmos LMNN e KLMNN para obter as melhores distâncias de mahalanobis linear e
não linear, respectivamente, para a aplicação.
5.2.1 Análise do Reconhecimento de Poses Estáticas
Para análise de acurária das classes de poses estáticas, criamos um conjunto de
testes de poses estáticas com 170 exemplos de poses (10 por classe). Abaixo exibimos os
86
resultados de classificação utilizando as 3 distâncias consideradas no Classificador DMM:
euclidiana, mahalanobis linear e mahalanobis não linear.
No geral foram obtidos os seguintes resultados:
• com a distância euclidiana o reconhecimento foi de 94.7% (161 exemplos dos 170);
• com a distância de mahalanobis linear o reconhecimento foi de 98.2% (167 exemplos
dos 170);
• com a distância de mahalanobis não linear o reconhecimento foi de 99.4% (169 exemplos dos 170), utilizando como argumento do kernel σ = 0.8, calibrado manualmente.
As Tabelas 7, 8 e 9 contêm as matrizes de confusões com as informações de
reconhecimento por classe de poses utilizando as 3 distâncias consideradas.
Tabela 7 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais
dos números em LIBRAS e de poses estáticas dos gestos personalizados para
as operações matemáticas básicas utilizando distância euclidiana.
classe
c0
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
cD
(%)
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
3 0
10 0
0 10
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
10
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
100.0
100.0
100.0
100.0
90.0
90.0
100.0
60.0
100.0
100.0
100.0
100.0
100.0
90.0
80.0
100.0
100.0
c1
c2
Fonte – Autor, 2017.
5.2.2 Análise do Reconhecimento de Gestos Dinâmicos Oine
Para análise de acurácia das classes de gestos dinâmicos, criamos um conjunto de
treinamento de gestos composto de 150 exemplos de gestos (10 exemplos por classe). Na
etapa de extração de key poses dos gestos foi utilizado o parâmetro comprimento de blocos
87
Tabela 8 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais
dos números em LIBRAS e de poses estáticas dos gestos personalizados para
as operações matemáticas básicas utilizando distância de mahalanobis linear.
classe
c0
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
cD
(%)
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
10 0
0 10
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
10
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100.0
100.0
100.0
100.0
100.0
90.0
100.0
90.0
100.0
100.0
100.0
100.0
100.0
90.0
100.0
100.0
100.0
c1
c2
Fonte – Autor, 2017.
Tabela 9 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais
dos números em LIBRAS e de poses estáticas dos gestos personalizados para as
operações matemáticas básicas utilizando distância de mahalanobis não linear.
classe
c0
c1
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 0 0 0
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
c2
c3
c4
c9
c10
c11
c12
c13
c14
c15
c16
cD
(%)
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
10 0 0 0 0
0 10 0 0 0
0 0 10 0 0
0 0 0 10 0
0 0 0 0 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
90.0
100.0
100.0
100.0
c5
c6
c7
c8
Fonte – Autor, 2017.
de key poses sucessivas como M = 8. A Tabela 10 exibe os detalhes de reconhecimento
por classe de gestos dinâmicos.
Observe que houve uma melhora razoável nos resultados utilizando as distâncias
88
Tabela 10 – Desempenho do reconhecimento das classes de gestos que representam os
números em LIBRAS e as operações matemáticas básicas.
Euclidiana
Mahalanobis Linear
Mahalanobis Não Linear
Classe
Quantidade
Acertos
Acurácia (%)
Acertos
Acurácia (%)
Acertos
Acurácia (%)
g0
g1
g2
g3
g4
g5
g6
g7
g8
g9
g10
g11
g12
g13
g14
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
9
10
10
9
9
10
9
8
10
10
10
9
10
10
100.0
90.0
100.0
100.0
90.0
90.0
100.0
90.0
80.0
100.0
100.0
100.0
90.0
100.0
100.0
10
9
10
10
10
9
10
10
9
10
10
10
10
10
10
100.0
90.0
100.0
100.0
100.0
90.0
100.0
100.0
90.0
100.0
100.0
100.0
100.0
100.0
100.0
10
9
10
10
10
10
10
10
9
10
10
10
10
10
10
100.0
90.0
100.0
100.0
100.0
100.0
100.0
100.0
90.0
100.0
100.0
100.0
100.0
100.0
100.0
Geral
150
143
95.3
147
98.0
148
98.6
Fonte – Autor, 2017
de mahalanobis linear e não linear quando comparados com a utilização da distância
euclidiana. No entanto, vale destacar novamente que a utilização do Classificador DMM
já ofereceu bons resultados apenas com a distância euclidiana. Isto pode ser explicado,
de certa forma, por conta do conjunto de poses estáticas treinadas não oferecer grandes
dificuldades de rastreamento para o sensor Leap Motion, que fornece um rastreamento
bom para a maioria das classes de poses estáticas desta aplicação.
5.2.3 Análise do Reconhecimento de Gestos Dinâmicos Online
No reconhecimento online foram criados diversos conjuntos com execuções de gestos
online. Na maioria deles o classificador de gestos online foi capaz de reconhecer de forma
robusta e antecipada todos os gestos realizados, com uma latência de reconhecimento
inferior a 50% da execução do gesto para todas as classes, isto já era esperado uma vez
que cada classe de gestos é treinada como uma sequência de 2 key poses apenas.
A Figura 28 ilustra a linha do tempo de um destes conjuntos correspondente a
execução da expressão “ 2017 − 1993 = ”, composto pelas execuções de 8 das 15 classes de
gestos treinadas e segmentado utilizando a distância de mahalanobis não linear como
base para a extração de key poses.
89
Figura 30 – Linhas do tempo de execução e reconhecimento de gestos utilizados para
representar os números em LIBRAS e as operações matemáticas básicas
segmentados manualmente (linha do tempo inferior) e segmentados de forma
automática pelo algoritmo (linha do tempo superior).
2
2
0 30
0
1
7
−
1
9
9
0
1
7
−
1
9
9
130 157
270 306
390 429
530 563
670 702
800 835
920 951
3
3
=
=
1040 1070 1150 1182
quadros
Fonte – Autor, 2017.
Vale ressaltar que para ambas as distâncias euclidiana e mahalanobis linear, utilizadas no Classificador DMM, o resultado da segmentação automática dos gestos também
foi satisfatória. A Tabela 11 apresenta as taxas de latência do reconhecimento dos gestos
do conjunto analisado na Figura 30.
Tabela 11 – Latência do reconhecimento dos gestos utilizados para representar os números
em LIBRAS e as operações matemáticas básicas em três abordagens: por
quadros, por segundo e por porcentagem de execução do gesto.
Classe Latência (quadros)
g2
g0
g1
g7
g11
g1
g9
g9
g3
g14
30
27
36
39
33
32
35
31
30
32
Latência (segundos) Latência (%)
0.75
0.67
0.90
0.97
0.82
0.80
0.87
0.77
0.75
0.80
Fonte – Autor, 2017.
37.5
30.0
45.0
43.3
36.6
40.0
43.7
38.7
37.7
35.5
90
5.3 Reconhecimento de Sinais Estáticos do Alfabeto Manual em LIBRAS e de Palavras
como Gestos Dinâmicos
Nesta terceira aplicação, utilizamos o método de reconhecimento de gestos para
realizar o reconhecimento de palavras treinadas como gestos dinâmicos. Neste contexto,
cada palavra é tratada como um gesto onde as poses são os sinais estáticos do alfabeto
manual em Lingua Brasileira de Sinais (LIBRAS).
Iniciamos treinamos o conjunto de poses da mão descrito na Figura 31, composto
de 20 classes de poses estáticas invariantes por rotação e translação. As classes de c0
a c18 são os sinais estáticos do alfabeto manual em LIBRAS e c19 , representada como “”,
é uma classe de poses auxiliar utilizada para evitar que palavras menores sejam treinadas
como subgestos de palavras maiores. Abaixo explicamos com mais detalhes este processo.
Figura 31 – Classes de poses estáticas para o reconhecimento de sinais estáticos do alfabeto
manual em LIBRAS e palavras como gestos dinâmicos.
c0 : A
c4 : E
c8 : L
c12 : P
c16 : T
c1 : B
c5 : F
c9 : M
c13 : Q
c17 : U
c2 : C
c6 : G
c10 : N
c14 : R
c18 : V
c3 : D
c7 : I
c11 : O
c15 : S
c19 :
Fonte – Autor, 2017.
Para esta aplicação, consideramos o conjunto de palavras da Tabela 12 e treinamos
cada palavra como sendo um gesto dinâmico periódico (de período 2), obtido pela realização
dos sinais estáticos correspondentes as suas letras, seguida da pose correspondente a classe
c19 . Isto é feito para possibilitar o reconhecimento de palavras que são subpalavras de
outras, uma vez que a abordagem de reconhecimento de gestos online utilizando grafos de
ação não detecta gestos que são subgestos de algum outro gesto do conjunto.
Por exemplo, para reconhecer palavras como “DA” e “OS”, que são subpalavras de “APLICADA” e “GESTOS”, respectivamente; treinamo-las como os gestos
91
DADA e OSOS. De forma análoga, treinamos os gestos APLICADAAPLICADA
e GESTOSGESTOS para as palavras “APLICADA” e “GESTOS”, respectivamente.
Finalmente, para que a máquina reconheça essas palavras, o usuário deve executar
o respectivo gesto com período igual a 2 para palavras que sejam subpalavras de outras,
enquanto para as demais, o usuário precisa em geral realizar apenas 1 período do respectivo
gesto. Dessa forma, para que a máquina reconheça a palavra “OS”, por exemplo, o usuário
deve realizá-la exatamente como foi treinada, isto é, como OSOS. Enquanto para o
reconhecimento da palavra “GESTOS”, basta realizar o gesto GESTOS, ao invés de
GESTOSGESTOS como treinada.
A inclusão da classe de pose c19 () no fim do gesto correspondente a cada palavra
é útil também para possibilitar o reconhecimento online de letras, quando consideradas
como palavras. O motivo disto é o mesmo pelo qual foi utilizada uma segunda pose no
reconhecimento dos números em LIBRAS, quando considerados como gestos dinâmicos.
Para possibilitar o reconhecimento de poses e gestos para esta aplicação, criamos:
1. um conjunto de treinamento de classes de poses estáticas, composto de 381 exemplos
distribuídos entre as 20 classes de poses estáticas, sendo 230 para treinamento e 151
para validação;
2. um conjunto de treinamento de gestos dinâmicos, composto de 368 exemplos de
gestos distribuídos entre as 20 classes de gestos consideradas.
O conjunto de treinamento de poses estáticas foi então passado como entrada dos
algoritmos LMNN e KLMNN para obter as melhores distâncias de mahalanobis linear e
não linear, respectivamente, para a aplicação.
5.3.1 Análise do Reconhecimento de Poses Estáticas
Para análise de acurácia dos sinais estáticos, criamos um conjunto de testes de
poses com 200 exemplos de poses (10 por classe). Abaixo exibimos os resultados utilizando
as 3 distâncias consideradas no Classificador DMM: euclidiana, mahalanobis linear e
mahalanobis não linear.
No geral foram obtidos os seguintes resultados:
92
Tabela 12 – Gestos dinâmicos da mão para reconhecimento de palavras utilizando o
alfabeto manual em LIBRAS.
Classe
Gesto
Key Poses
g0
A
c0 c19 c0 c19
g1
E
c4 c19 c4 c19
g2
O
c11 c19 c11 c19
g3
AS
c0 c15 c19 c0 c15 c19
g4
OS
c11 c15 c19 c11 c15 c19
g5
DA
c3 c0 c19 c3 c0 c19
g6
DO
c3 c11 c19 c3 c11 c19
g7
DE
c3 c4 c19 c3 c4 c19
g8
UM
c17 c9 c19 c17 c9 c19
g9
UMA
c17 c9 c0 c19 c17 c9 c0 c19
g10
EM
c4 c9 c19 c17 c9 c19
g11
NÃO
c10 c0 c11 c19 c10 c0 c11 c19
g12
LINEAR
c8 c7 c10 c4 c0 c14 c19
g13
APLICADA
c0 c12 c8 c7 c2 c0 c3 c0 c19
g14
POSE
c12 c11 c15 c4 c19
g15
POSES
c12 c11 c15 c4 c15 c19
g16
ESTÁTICA
c4 c15 c16 c0 c16 c7 c2 c0 c19
g17
ESTÁTICAS
c4 c15 c16 c0 c16 c7 c2 c0 c15 c19
g18
GESTO
c6 c4 c15 c16 c11 c19
g19
GESTOS
c6 c4 c15 c16 c11 c15 c19
g20
DINÂMICO
c3 c7 c10 c0 c9 c7 c2 c11 c19
g21
DINÂMICOS
c3 c7 c10 c0 c9 c7 c2 c11 c15 c19
g22
MESTRADO
c9 c4 c15 c16 c14 c0 c3 c11 c19
g23
COMPUTAÇÃO
c2 c11 c9 c12 c17 c16 c0 c2 c0 c11 c19
g24
GRÁFICA
c6 c14 c0 c5 c7 c7 c2 c0 c19
g25
MATEMÁTICA
c9 c0 c16 c4 c9 c0 c16 c7 c2 c0 c19
g26
OLIMPÍADA
c11 c8 c7 c9 c12 c7 c0 c3 c0 c19
g27
MÉTRICA
c9 c4 c16 c14 c7 c2 c0 c19
Fonte – Autor, 2017.
Representação Visual
93
• com a distância euclidiana o reconhecimento foi de 72.5% (145 exemplos dos 200);
• com a distância de mahalanobis linear o reconhecimento foi de 82.0% (164 exemplos
dos 200);
• com a distância de mahalanobis não linear o reconhecimento foi de 84.5% (169 exemplos dos 200), utilizando como argumento do kernel σ = 0.33 calibrado manualmente.
As Tabelas 13, 14 e 15 contêm as matrizes de confusão com as informações de
reconhecimento por classe de poses utilizando as 3 distâncias consideradas.
Tabela 13 – Matriz de confusão do reconhecimento de exemplos de poses estáticas do
conjunto de testes de poses dos sinais estáticos em LIBRAS utilizando distância
euclidiana.
classe c0
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
c17
c18
c19
7
0
0
0
0
0
0
0
0
0
2
0
0
0
0
6
0
0
0
0
c2
c3
c4
c5
c6
c8
c9
c10
c11
c12
c13
c14
c15
c16
c17
c18
c19
cD
(%)
0 0
10 0
0 10
0 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0 0 0
0 0 0
0 0 0
2 0 0
0 0 0
0 0 0
10 0 0
0 10 0
0 0 10
0 0 0
0 0 0
0 0 0
5 0 0
0 0 0
2 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0
0
0
0
0
0
0
0
0
7
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
2
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
10
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
3
0
0
0
0
1
0
0
0
3
3
0
1
0
4
1
0
0
1
0
70.0
100.0
100.0
80.0
80.0
90.0
100.0
100.0
100.0
70.0
10.0
100.0
40.0
80.0
0.0
30.0
30.0
100.0
70.0
100.0
c1
c7
Fonte – Autor, 2017.
5.3.2 Análise do Reconhecimento do Gestos Dinâmicos Oine
Para análise de acurácia das palavras da Tabela 12, criamos um conjunto de
treinamento de gestos composto de 280 exemplos, 10 exemplos por classe de palavra. Na
etapa de extração de key poses dos gestos foi utilizado o parâmetro comprimento de blocos
de key poses sucessivas como M = 15. A Tabela 16 exibe os detalhes de reconhecimento
por palavra treinada.
94
Tabela 14 – Matriz de confusão do reconhecimento de exemplos de poses estáticas do
conjunto de testes de poses de sinais estáticos em LIBRAS utilizando distância
de mahalanobis linear.
classe c0
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
c17
c18
c19
7
0
0
0
0
0
0
0
0
0
2
0
0
2
0
3
0
0
0
0
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
c17
c18
c19
cD
(%)
0 0
10 0
0 10
0 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
10 0
0 10
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
0
0
0
0
0
0
9
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
10
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
1
0
0
0
0
0
1
0
0
0
0
0
0
1
3
0
0
0
2
0
70.0
100.0
100.0
100.0
80.0
90.0
90.0
100.0
100.0
90.0
50.0
100.0
100.0
60.0
0.0
70.0
80.0
100.0
60.0
100.0
c1
Fonte – Autor, 2017.
Tabela 15 – Matriz de confusão do reconhecimento de exemplos de poses estáticas do
conjunto de testes de poses de sinais estáticos em LIBRAS utilizando distância
de mahalanobis não linear.
classe c0
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
c17
c18
c19
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
c2
c3
c4
c5
c6
c8
c9
c10
c11
c12
c13
c14
c15
c16
c17
c18
c19
cD
(%)
0 0
10 0
0 10
0 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
10 0 0
0 10 0
0 0 10
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
2
6
0
0
1
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
9
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
6
0
0
0
2
0
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
1
0
0
0
0
0
0
0
0
1
2
0
1
0
1
0
0
0
1
0
30.0
100.0
100.0
90.0
70.0
100.0
100.0
100.0
100.0
70.0
60.0
100.0
90.0
90.0
60.0
90.0
70.0
100.0
70.0
100.0
c1
c7
0
9
0
0
0
0
0
0
0
Fonte – Autor, 2017.
95
Tabela 16 – Desempenho do reconhecimento das classes de gestos que representam as
palavras treinadas como gestos dinâmicos.
Euclidiana
Mahalanobis Linear
Mahalanobis Não Linear
Classe
Quantidade
Acertos
Acurácia (%)
Acertos
Acurácia (%)
Acertos
Acurácia (%)
g0
g1
g2
g3
g4
g5
g6
g7
g8
g9
g10
g11
g12
g13
g14
g15
g16
g17
g18
g19
g20
g21
g22
g23
g24
g25
g26
g27
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
8
9
10
10
9
7
9
7
8
10
9
8
9
10
10
9
10
7
6
9
7
6
7
8
6
8
10
100.0
80.0
90.0
100.0
100.0
90.0
70.0
90.0
70.0
80.0
100.0
90.0
80.0
90.0
100.0
100.0
90.0
100.0
70.0
60.0
90.0
70.0
60.0
70.0
80.0
60.0
80.0
100.0
10
8
10
9
10
9
9
10
8
8
10
7
10
8
10
10
9
9
10
8
9
6
7
8
9
9
10
10
90.0
70.0
100.0
100.0
70.0
100.0
100.0
100.0
80.0
80.0
100.0
70.0
100.0
80.0
100.0
100.0
90.0
90.0
100.0
80.0
90.0
60.0
70.0
80.0
90.0
90.0
100.0
100.0
9
8
10
9
10
8
7
10
8
7
10
7
6
7
9
9
7
9
8
9
9
7
8
7
7
9
8
10
90.0
80.0
100.0
90.0
100.0
80.0
70.0
100.0
80.0
70.0
100.0
70.0
60.0
70.0
90.0
90.0
70.0
90.0
80.0
90.0
90.0
70.0
80.0
70.0
70.0
90.0
80.0
100.0
Geral
280
236
84.3
250
89.3
231
82.5
Fonte – Autor, 2017.
Em nossos testes obtivemos uma melhoria razoável na classificação de palavras
utilizando a distância de mahalanobis linear. No entanto, houve uma queda de desempenho
utilizando a distância de mahalanobis não linear, isto provavelmente se deve ao fato de
a calibração manual do parâmetro do kernel σ não ter sido o parâmetro ótimo para
o conjunto de palavras considerado. Isto pode ser corrigido em trabalhos futuros pela
implementação de uma calibração automática. Observamos, no entanto, que utilizando-se o
mesmo parâmetro na classificação dos sinais descritos na seção anterior, o reconhecimento
com a distância de mahalanobis não linear foi muito superior ao reconhecimento utilizando
a distância euclidiana, e ainda relativamente superior a distancia de mahalanobis. Este
fato nos leva a crer que o parâmetro escolhido se adequa relativamente bem ao conjunto de
sinais estáticos treinado, porém é insuficiente para uma boa generalização de cada classe
96
de sinais, uma vez que durante o reconhecimento de gestos existem diversas variações dos
sinais treinados que talvez não estejam presentes no conjunto de testes de sinais estáticos
criado.
5.3.3 Análise do Reconhecimento de Gestos Dinâmicos Online
No reconhecimento online foram criados diversos conjuntos com execuções de
gestos correspondentes à frases elaboradas a partir do conjunto de palavras treinadas.
Na maioria destes conjuntos houveram erros de classificação e segmentação das palavras
que cumpunham os conjuntos para ambas as 3 distâncias consideradas. Isto se deve
principalmente a imprecisão de ratreamento do sensor Leap Motion para algumas classes
de sinais da Figura 31, sinais estes que posssuem oclusões parciais ou totais de dedos da
mão, fazendo com que o sensor não rastrei corretamente dedos importantes para diferenciar
algumas classes de sinais que são parecidos. Abaixo exibimos o resultado de reconhecimento
e segmentação para dois destes conjuntos onlines.
Primeiro conjunto: “A MÉTRICA LINEAR”
Para este conjunto o reconhecimento e segmentação das palavras se deu de forma
parecida para cada distância utilizada. As únicas diferenças notáveis se deram no reconhecimento da palavra “MÉTRICA”, onde em dados instantes de sua realização o
classificador reconheceu sinais equivocadamente, o que induziu a uma quebra no fluxo de
reconhecimento da palavra. Com a distância de mahalanobis, por exemplo, no quadro 321
o algoritmo confundiu o gesto corrente com o gesto da palavra “MATEMÁTICA” (classe
g25 ).
A Figura 32 ilustra as linhas do tempo de execução e de como se deu o reconhecimento e segmentação das palvras do conjunto. As faixas pretas indicam que no período
correspondente o algoritmo não reconheceu nenhuma palavra. A Tabela 17 apresenta as
taxas de latência do reconhecimento das palavras para este conjunto.
Observe que a latência do reconhecimento da palavra “A” foi alta em relação as
demais palavras do conjunto. Isto se deu por conta do fato já comentado no início desta
seção, o de que subpalavras precisam de uma segunda execução para serem reconhecidos
adequadamente; enquanto as palavras “MÉTRICA” e “LINEAR” com poucos sinais
estáticos realizados já são facilmente detectadas pelo algoritmo.
97
Figura 32 – Linhas do tempo de execução e reconhecimento das palavras da frase “A
MÉTRICA LINEAR” segmentada manualmente (linha do tempo inferior) e
segmentada de forma automática pelo algoritmo utilizando diferentes distâncias (linhas do tempo superiores).
Segmentação automática de gestos utilizando distância euclidiana:
0
𝑔27
𝑔27
𝑔0
75
202
525
𝑔12
591
quadros
Segmentação automática de gestos utilizando distância de mahalanobis linear:
𝑔27
𝑔0
0
75
202
𝑔25
321
𝑔27
400
𝑔12
590
quadros
Segmentação automática de gestos utilizando distância de mahalanobis não linear:
𝑔27
𝑔0
0
𝑔12
201
75
590
quadros
Segmentação manual de gestos:
𝑔27
𝑔0
0
𝑔12
170
570
quadros
Fonte – Autor, 2017.
Tabela 17 – Latência do reconhecimento dos gestos utilizados para representar palavras da
frase “A MÉTRICA LINEAR” como gestos dinâmicos em LIBRAS utilizando
a distância de mahalanobis não linear em três abordagens: por quadros, por
segundo e por porcentagem de execução do gesto.
Classe Latência (quadros)
g0
g27
g12
75
31
20
Latência (segundos) Latência (%)
1.87
0.77
0.50
44.1
7.7
5.7
Fonte – Autor, 2017.
Segundo conjunto: “AS POSES DO GESTO DINÂMICO”
O reconhecimento e segmentação das palavras deste segundo conjunto também se
deu de forma parecida para cada distância utilizada. No entanto, desta vez o algortimo
cometeu erros de segmentação e classificação com todas as 3 distâncias utilizadas. A
palavra “DINÂMICO” (classe g20 ) se mostrou a de reconhecimento mais difícil, sendo
segmentada equivocadamente com todas as distâncias. Isto se deve provavelmente ao fato
98
da palavra conter as letras M (classe c9 ) e N (classe c10 ), que possuem sinais em LIBRAS
difíceis de o sensor Leap Motion rastrear com precisão.
A Figura 33 ilustra as linhas do tempo de execução e de como se deu o reconhecimento e segmentação das palvras do conjunto. As faixas pretas indicam que no período
correspondente o algoritmo não reconheceu nenhuma palavra. A Tabela 18 apresenta as
taxas de latência do reconhecimento das palavras para este conjunto.
Figura 33 – Linhas do tempo de execução e reconhecimento das palavras da frase “AS
POSES DO GESTO DINÂMICO” segmentada manualmente (linha do tempo
inferior) e segmentada de forma automática pelo algoritmo utilizando diferentes
distâncias (linhas do tempo superiores).
Segmentação automática de gestos utilizando distância euclidiana:
𝑔15
𝑔3
0
179
𝑔6
𝑔15
427 505 571
768
894
𝑔20 𝑔26
𝑔18
𝑔18
1063
𝑔20
1304 1387
1620 quadros
Segmentação automática de gestos utilizando distância de mahalanobis linear:
𝑔3
0
179
𝑔15
𝑔6
𝑔15
360
570
723
𝑔18
893
𝑔20
𝑔21
1307
1475
𝑔20
1621 quadros
Segmentação automática de gestos utilizando distância de mahalanobis não linear:
𝑔15
𝑔3
0
178
𝑔6
𝑔15
360
571
728
𝑔18
𝑔18
890
1137
𝑔20 𝑔26
1308 1385
𝑔20
1621 quadros
Segmentação manual de gestos:
0
𝑔6
𝑔15
𝑔3
320
650
𝑔18
850
𝑔20
1230
quadros
Fonte – Autor, 2017.
5.4 Reconhecimento de Sinais Dinâmicos do Alfabeto Manual em LIBRAS
Nesta última aplicação, utilizamos o método de reconhecimento de gestos dinâmicos
para efetuar o reconhecimento dos sinais dinâmicos do alfabeto manual na Lingua Brasileira
de Sinais (LIBRAS). Para isto, definimos primeiramente o conjunto de key poses da Figura
34; composto de 15 poses estáticas variantes por rotação e translação.
A partir destas key poses treinamos os sinais dinâmicos do alfabeto manual em
LIBRAS como os gestos dinâmicos da Tabela 19.
99
Tabela 18 – Latência do reconhecimento dos gestos utilizados para representar palavras
da frase “AS POSES DO GESTO DINÂMICO” como gestos dinâmicos em
LIBRAS utilizando a distância de mahalanobis não linear em três abordagens:
por quadros, por segundo e por porcentagem de execução do gesto.
Classe Latência (quadros)
Latência (segundos) Latência (%)
138
40
78
40
78
g3
g15
g6
g18
g20
3.45
1.00
1.95
1.00
1.95
43.1
12.1
39.0
10.5
16.6
Fonte – Autor, 2017.
Figura 34 – Classes de poses estáticas utilizadas para o reconhecimento dos sinais dinâmicos
do alfabeto manual em LIBRAS.
c0
c3
c6
c9
c12
c15
c1
c4
c7
c10
c13
c16
c2
c5
c8
c11
c14
Fonte – Autor, 2017.
Para possibilitar o reconhecimento eficaz destes gestos, criamos:
1. o conjunto de treinamento de classes de poses estáticas, composto por 215 exemplos
distribuídos entre as 17 classes de poses, sendo 128 para treinamento e 87 para
validação;
2. o conjunto de treinamento dos sinais dinâmicos, composto por 88 exemplos de gestos
distribuídos entre os 8 sinais dinâmicos consideradas.
Passamos então o conjunto de key poses como entrada dos algoritmos LMNN e
KLMNN para obter as melhores distâncias de mahalanobis linear e não linear, respectivamente, para a aplicação.
100
Tabela 19 – Gestos dinâmicos da mão para representação dos sinais dinâmicos do alfabeto
manual em LIBRAS.
Classe
Gesto
Key Poses
g0
Ç
c0 c1
g1
H
c 2 c3
g2
J
c4 c5
g3
K
c6 c3
g4
W
c7 c8
g5
X
c9 c10
g6
Y
c11 c12
g7
Z
c13 c14 c15 c16
Representação Visual
Fonte – Auto, 2017.
5.4.1 Análise do Reconhecimento de Poses Estáticas
Para análise de acurária das classes de poses estáticas, criamos um conjunto de
testes de poses estáticas com 170 exemplos de poses (10 por classe). Abaixo exibimos
os resultados utilizando as 3 distâncias consideradas no Classificador DMM: euclidiana,
mahalanobis linear e mahalanobis não linear.
No geral foram obtidos os seguintes resultados:
• com a distância euclidiana o reconhecimento foi de 85.9% (146 exemplos dos 170);
• com a distância de mahalanobis linear o reconhecimento foi de 93.5% (159 exemplos
dos 170);
• com a distância de mahalanobis não linear o reconhecimento foi de 98.2% (167 exemplos dos 170), utilizando como argumento do kernel σ = 0.8 calibrado manualmente.
Note como a utilização da distância de mahalanobis proporcionou um desempenho
de classificação muito superior ao quando utilizado a distância euclidiana comum.
101
As Tabelas 20, 21 e 22 contém as matrizes de confusões com as informações de
reconhecimento por classe de poses utilizando as 3 distâncias consideradas.
Tabela 20 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos sinais
dinâmicos do alfabeto manual em LIBRAS utilizando distância euclidiana.
classe
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
cD
(%)
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
10 0
0 10
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
10 0
0 10
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
2
2
2
2
3
0
0
6
0
1
0
5
0
0
1
100.0
100.0
80.0
80.0
80.0
80.0
70.0
100.0
100.0
40.0
100.0
90.0
100.0
50.0
100.0
100.0
90.0
Fonte – Autor, 2017.
Tabela 21 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos
sinais dinâmicos do alfabeto manual em LIBRAS utilizando distância de
mahalanobis linear.
classe c0
c1
c2
c3
c4
c5
c8
c9
c10
c11
c12
c13
c14
c15
c16
cD
(%)
9
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
1
1
0
1
0
0
0
0
0
1
0
1
0
2
0
0
1
90.0
80.0
100.0
80.0
100.0
100.0
100.0
100.0
100.0
90.0
100.0
90.0
100.0
80.0
90.0
100.0
90.0
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
c6
c7
Fonte – Autor, 2017.
102
Tabela 22 – Matriz de confusão do reconhecimento de exemplos de poses estáticas dos
sinais dinâmicos do alfabeto manual em LIBRAS utilizando distância de
mahalanobis não linear.
classe
c0
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
c1
c2
c3
c7
c8
c9
c10
c11
c12
c13
c14
c15
c16
cD
(%)
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 10
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
10
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
90.0
90.0
100.0
100.0
100.0
100.0
100.0
100.0
90.0
c4
c5
c6
Fonte – Autor, 2017.
5.4.2 Análise do Reconhecimento de Gestos Dinâmicos Oine
Para análise de acurácia das classes de sinais dinâmicos, criamos um conjunto de
treinamento de gestos composto de 80 exemplos de gestos (10 exemplos por classe). Na
etapa de extração de key poses dos gestos foi utilizado o parâmetro comprimento de blocos
de key poses sucessivas como M = 8. A Tabela 23 exibe os detalhes de reconhecimento
por classe de sinais dinâmicos.
Tabela 23 – Desempenho do reconhecimento das classes de gestos que representam os
sinais dinâmicos do alfabeto manual em LIBRAS.
Euclidiana
Mahalanobis Linear
ahalanobis não linear
Classe
Quantidade
Acertos
Acurácia (%)
Acertos
Acurácia (%)
Acertos
Acurácia (%)
g0
g1
g2
g3
g4
g5
g6
g7
10
10
10
10
10
10
10
10
10
9
10
7
10
10
10
10
100.0
90.0
100.0
70.0
100.0
100.0
100.0
100.0
9
10
10
10
10
10
10
10
90.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
10
10
10
10
10
10
10
10
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
Geral
80
76
95.0
79
98.7
80
100.0
Fonte – Autor, 2017.
103
Observe que houve uma melhoria razoável nos resultados utilizando as distâncias
de mahalanobis Linear e não linear se comparados com a utilização da distância euclidiana.
No entanto, vale destacar novamente que a utilização do Classificador DMM já ofereceu
boms resultados apenas com a utilização da distância euclidiana, mesmo com a acurácia
de reconhecimento de poses estáticas ter sido bastante inferior.
5.4.3 Análise do Reconhecimento de Gestos Dinâmicos Online
No reconhecimento online foram criados diversos conjuntos com execuções de gestos
online. Em todos estes conjuntos o classificador de gestos online conseguiu reconhecer de
forma robusta e antecipada todos os gestos realizados, com uma latência de reconhecimento
inferior a 50% da execução do gestos para todas as classes de gestos.
A Figura 35 ilustra um destes conjuntos, composto pela execução de todas as 8
classes de gestos treinadas, onde foi utilizada a distância de mahalanobis não linear para
detecção das key poses.
Figura 35 – Linhas do tempo de execução e reconhecimento de sinais dinâmicos do alfabeto
manual em LIBRAS segmentados manualmente (linha do tempo inferior) e
segmentados de forma automática pelo algoritmo (linha do tempo superior).
𝑔0
𝑔0
0 25
𝑔1
𝑔1
170 196
𝑔2
𝑔4
𝑔3
𝑔2
𝑔3
310 350
450 474
𝑔5
𝑔5
𝑔4
600 621
750 787
𝑔7
𝑔6
𝑔6
880 895
𝑔7
1010 1027
quadros
Fonte – Autor, 2017.
Utilizando as outras distâncias: euclidiana e mahalanobis linear, o reconhecimento
e segmentação automática dos gestos se deram de forma bastante parecida. A Tabela 5
mostra as taxas de latência do reconhecimento dos gestos do conjunto analisado na Figura
28.
104
Tabela 24 – Latência do reconhecimento dos sinais dinâmicos do alfabeto manual em LIBRAS utilizando três abordagens: por quadros, por segundo e por porcentagem
de execução do gesto.
Classe Latência (quadros)
g0
g1
g2
g3
g4
g5
g6
g7
25
26
40
24
21
37
15
17
Latência (segundos) Latência (%)
0.62
0.65
1.00
0.60
0.52
0.92
0.37
0.42
Fonte – Autor, 2017.
19.2
26.0
44.4
26.6
19.1
41.1
16.6
12.1
105
CONCLUSÃO
Este trabalho apresentou um método de reconhecimento de poses estáticas e
gestos dinâmicos da mão de forma offline e online. Para isto utilizamos aprendizado
supervisionado para ambas as tarefas. No reconhecimento de poses estáticas foi utilizado
mais especificamente aprendizagem de métrica para melhorar um classificador de poses
estáticas simples. No reconhecimento de gestos foi utilizado a abordagem probabilística de
grafos de ação.
Nosso método foi divido em 4 etapas globais. A primeira foi o treinamento das
classes de poses estáticas e a aprendizagem das métricas linear e não linear que melhor se
adaptavam aos exemplos de poses estáticas treinados. Para encontrar estas métricas foi
utilizado o algoritmo LMNN nas versões linear e não linear. A segunda etapa foi a utilização
do Classificador DMM com as métricas aprendidas. Estas duas etapas constituíram o
método de reconhecimento de poses estáticas. A terceira etapa foi o treinamento das classes
de gestos dinâmicos, onde cada classe de gestos foi codificada em um grafo de ação que
continha as probabilidades de transições entre poses estáticas que ocorreram nos exemplos
de gestos treinados da classe. Na quarta etapa foram utilizados os grafos de ação gerados
na etapa anterior para deduzir os rótulos de classes de novos gestos realizados. Esta última
etapa de reconhecimento foi realizada de forma offline e online.
Para avaliar o método de reconhecimento foram criadas 4 aplicações. Em cada uma
delas foi analisada a acurácia do método nas seguintes tarefas: reconhecimento de poses
estáticas, reconhecimento de gestos dinâmicos offline e reconhecimento de gestos dinâmicos
realizados de forma online. Na primeira aplicação (Seção 5.1), tanto o desempenho do
reconhecimento de poses estáticas quanto o de gestos dinâmicos offline foram máximos
para todas as 3 distâncias utilizadas. Esta aplicação demonstrou que nos casos em que
o sensor Leap Motion consegue rastrear todas as classes de poses com precisão então
nosso método pode obter índices de acurácia máximos. Na segunda e quarta aplicação
(Seção 5.2 e Seção 5.4, respectivamente), que foram um pouco mais desafiadoras que a
primeira, podemos notar como a utilização das métricas aprendidas tornaram o método
mais robusto com relação a a utilização do método apenas com a distância euclidiana.
Já na terceira aplicação (Seção 5.3), a mais desafiadora dentre as quatro, foi observado
um índice de acurácia menor com a métrica não linear na tarefa de reconhecimento de
106
gestos dinâmicos offline. Isto ocorreu pelo fato de nesta aplicação muitas classes de poses
diferenciarem pouquíssimo uma das outras, diferenciando-se muitas vezes apenas pela
posição de um dedo. Além disso, muitas vezes estes dedos ficavam escondidos do sensor, o
que acabou prejudicando bastante a classificação das poses correspondentes. Este foi o
caso, por exemplo, dos sinais que representam as letras “R” e “U” em LIBRAS.
O baixo desempenho com a utilização da métrica não linear na terceira aplicação
evidenciou também a necessidade de desenvolvimento de um algoritmo de calibração
automática do parâmetro do kernel no algoritmo KPCA utilizado na fase de aprendizagem
da métrica não linear; pois, como foi observado, a utilização de um parâmetro do kernel
ruim pode não só prejudicar parcialmente o desempenho do reconhecimento das poses
estáticas, como pode também tornar o método totalmente ineficaz.
Para a tarefa de reconhecimento de gestos dinâmicos da mão de forma online,
observamos excelentes resultados nas aplicações 5.1, 5.2 e 5.4. Em todos os conjuntos de
testes online destas aplicações, nosso método reconheceu corretamente todos os gestos
executados com latência média inferior a 40% da execução para a maioria dos gestos. No
entanto, para a aplicação 5.3 os resultados não foram totalmente satisfatórios. Na maioria
dos conjuntos online criados para esta aplicação, nosso método reconheceu erroneamente
ao menos 1 gesto de cada conjunto.
De um modo geral, nosso trabalho obteve excelentes resultados, principalmente
para aplicações onde não existiam muitas oclusões de dedos da mão, pois nestes casos o
sensor Leap Motion fornecia um esqueleto sensível que não correspondia totalmente a pose
de mão realizada.
6.1 Trabalhos Futuros
Para trabalhos futuros, podemos incluir:
1. Calibração automática do parâmetro do kernel no algoritmo KPCA utilizado na
etapa de aprendizagem da métrica não linear.
2. Utilização das duas imagens fornecidas pelas câmeras do sensor Leap Motion como
recurso extra, a fim de melhorar o reconhecimento de poses da mão com muita
oclusão.
107
3. Desenvolvimento de um sistema de aprendizagem profunda (Deep Learning) sobre
os recursos fornecidos pelo sensor Leap Motion, a fim de aprender as características
que melhor descrevam poses da mão.
108
Referências
1 CORPORATION, M. Meet Kinect for Windows. 2017. Disponível em:
<https://developer.microsoft.com/en-us/windows/kinect>. Citado na página 18.
2 CORPORATION, I. Intel RealSense Technology. 2017. Disponível em: <https:
//www.intel.com/content/www/us/en/architecture-and-technology/realsense-overview.
html>. Citado na página 18.
3 MOTION, I. L. Leap Motion For Mac and PC. 2015. Disponível em:
<https://www.leapmotion.com/product/desktop>. Citado 2 vezes nas páginas 18 e 29.
4 CHENG, H.; YANG, L.; LIU, Z. Survey on 3D Hand Gesture Recognition. IEEE
Transactions on Circuits and Systems for Video Technology, IEEE, v. 26, n. 9,
p. 1659–1673, 2016. Citado 2 vezes nas páginas 18 e 22.
5 COMMUNITY, B. for the E. U. Elon Student Creates Interactive
Games for Children. 2016. Disponível em: <http://blogs.elon.edu/technology/
elon-student-creates-interactive-games-for-children/>. Citado na página 18.
6 MIRANDA, L. et al. Real-Time Gesture Recognition from Depth Data Through Key
Poses Learning and Decision Forests. In: Proceedings of the 2012 25th SIBGRAPI
Conference on Graphics, Patterns and Images. Washington, DC, USA: IEEE
Computer Society, 2012. (SIBGRAPI ’12), p. 268–275. ISBN 978-0-7695-4829-6. Disponível
em: <http://dx.doi.org/10.1109/SIBGRAPI.2012.44>. Citado 2 vezes nas páginas 19
e 20.
7 BERLEMONT, S. C. Automatic non Linear Metric Learning - Application
to Gesture Recognition. Tese (Thesis) — Université de Lyon 1, 2016. Disponível em:
<https://tel.archives-ouvertes.fr/tel-01379579>. Citado na página 20.
8 BROMLEY, J. et al. Signature Verification Using a Siamese Time Delay Neural
Network. In: Advances in Neural Information Processing Systems. [S.l.: s.n.],
1994. p. 737–744. Citado na página 20.
9 LAVIOLA, J. J. 3D Gestural Interaction: The State of the Field. International
Scholarly Research Notices, Hindawi Publishing Corporation, 2013. Citado na
página 20.
10 PRESTI, L. L.; CASCIA, M. L. 3D Skeleton-Based Human Action Classification: A
Survey. Pattern Recognition, Elsevier, v. 53, p. 130–147, 2016. Citado na página 20.
11 POPPE, R. A Survey on Vision-based Human Action Recognition. Image and
Vision Computing, v. 28, n. 6, p. 976–990, 2010. ISSN 0262-8856. Disponível em:
<http://www.sciencedirect.com/science/article/pii/S0262885609002704>. Citado na
página 20.
12 PADILLA-LÓPEZ, J. R.; CHAARAOUI, A. A.; FLÓREZ-REVUELTA, F. A
Discussion on the Validation Tests Employed to Compare Human Action Recognition
Methods Using The MSR Action3D Dataset. CoRR, abs/1407.7390, 2014. Disponível em:
<http://arxiv.org/abs/1407.7390>. Citado na página 20.
109
13 VIEIRA, T. et al. Online Human Moves Recognition Through Discriminative Key
Poses and Speed-Aware Action Graphs. Machine Vision and Applications, v. 28,
n. 1, p. 185–200, 2017. Citado 4 vezes nas páginas 20, 22, 71 e 75.
14 LI, W.; ZHANG, Z.; LIU, Z. Expandable Data-Driven Graphical Modeling of Human
Actions Based on Salient Postures. IEEE Transactions on Circuits and Systems
for Video Technology, v. 18, n. 11, p. 1499–1510, 2008. ISSN 1051-8215. Citado na
página 20.
15 CHEN, Q. et al. Interacting with Digital Signage Using Hand Gestures. In:
SPRINGER. International Conference Image Analysis and Recognition. [S.l.],
2009. p. 347–358. Citado na página 21.
16 WANG, R. Y.; POPOVIĆ, J. Real-time Hand-tracking with a Color Glove. Citado
na página 21.
17 KUMAR, P.; VERMA, J.; PRASAD, S. Hand Data Glove: A Wearable Real-time
Device for Human-computer Interaction. International Journal of Advanced Science
and Technology, v. 43, 2012. Citado na página 21.
18 REN, Z. et al. Robust Part-based Hand Gesture Recognition Using Kinect Sensor.
IEEE Transactions on Multimedia, IEEE, v. 15, n. 5, p. 1110–1120, 2013. Citado
na página 21.
19 MARIN, G.; DOMINIO, F.; ZANUTTIGH, P. Hand Gesture Recognition with Leap
Motion and Kinect Devices. In: IEEE. 2014 IEEE International Conference on
Image Processing (ICIP). [S.l.], 2014. p. 1565–1569. Citado na página 21.
20 HU, J.-T.; FAN, C.-X.; MING, Y. Trajectory Image Based Dynamic Gesture
Recognition with Convolutional Neural Networks. In: IEEE. Automation and Systems
(ICCAS), 2015 15th International Conference on Control. [S.l.], 2015. p.
1885–1889. Citado na página 21.
21 SCHMIDT, T. et al. Real-time Hand Gesture Recognition Based on Sparse Positional
Data. In: Proceedings of WVC 2014, Brazilian Workshop on Computer Vision.
[S.l.: s.n.], 2014. p. 243–248. Citado na página 21.
22 BREIMAN, L. Random Forests. Machine learning, Springer, v. 45, n. 1, p. 5–32,
2001. Citado na página 21.
23 LU, W.; TONG, Z.; CHU, J. Dynamic Hand Gesture Recognition with Leap Motion
Controller. IEEE Signal Processing Letters, IEEE, v. 23, n. 9, p. 1188–1192, 2016.
Citado na página 21.
24 GUO, D. et al. Sign Language Recognition Based on Adaptive HMMS with Data
Augmentation. In: IEEE. Image Processing (ICIP), 2016 IEEE International
’Conference on’. [S.l.], 2016. p. 2876–2880. Citado na página 21.
25 JOHN, V. et al. Real-time Hand Posture and Gesture-based Touchless Automotive
User Interface Using Deep Learning. In: IEEE. Intelligent Vehicles Symposium (IV),
2017 IEEE. [S.l.], 2017. p. 869–874. Citado na página 21.
26 SHOTTON, J. et al. Real-time Human Pose Recognition in Parts from Single Depth
Images. In: CVPR. [S.l.: s.n.], 2011. p. 1297–1304. Citado na página 27.
110
27 MOTION, I. L. API Overview. 2015. Disponível em: <https://developer.leapmotion.
com/documentation/cpp/devguide/Leap_Overview.html>. Citado 3 vezes nas páginas
28, 29 e 30.
28 WEICHERT, F. et al. Analysis of the Accuracy and Robustness of the Leap Motion
Controller. Sensors (Basel, Switzerland), 2013. Citado na página 28.
29 MOHRI, M.; ROSTAMIZADEH, A.; TALWALKAR, A. Foundations of Machine
Learning. [S.l.]: The MIT Press, 2012. Citado na página 31.
30 TSOI, A. C.; YONG, S. L.; HAGENBUCHNER, M. Ranking Web Pages Using
Machine Learning Approaches. IEEE/WIC/ACM International Conference on
Web Intelligence and Intelligent Agent Technology, 2008. Citado na página 31.
31 GOMEZ-URIBE, C. A.; HUNT, N. The Netflix Recommender System: Algorithms,
Business Value, and Innovation. ACM Transactions on Management Information
Systems (TMIS), 2015. Citado na página 31.
32 BELLET, A.; HABRARD, A.; SEBBAN, M. A Survey and Data, Structured on
Metric Learning for Feature Vectors. CoRR, abs/1306.6709, 2013. Disponível em:
<http://arxiv.org/abs/1306.6709>. Citado 2 vezes nas páginas 36 e 37.
33 KULIS, B. Metric Learning: A Survey. Foundations and Trends in
Machine Learning, v. 5, n. 4, p. 287–364, 2013. ISSN 1935-8237. Disponível em:
<http://dx.doi.org/10.1561/2200000019>. Citado na página 38.
34 WANG, J.; WOZNICA, A.; KALOUSIS, A. Parametric Local Metric Learning for
Nearest Neighbor Classification. ArXiv e-prints, set. 2012. Citado na página 39.
35 NOH, Y.-K.; ZHANG, B.-t.; LEE, D. D. Classification, Generative Local
Metric Learning for Nearest Neighbor. In: LAFFERTY, J. D. et al. (Ed.).
Advances in Neural Information Processing Systems 23. Curran Associates, Inc., 2010. p. 1822–1830. Disponível em: <http://papers.nips.cc/paper/
4040-generative-local-metric-learning-for-nearest-neighbor-classification.pdf>. Citado na
página 39.
36 MAHALANOBIS, P. C. On the Generalised Distance in Statistics. In: Proceedings
National Institute of Science, India. [s.n.], 1936. v. 2, n. 1, p. 49–55. Disponível em:
<http://ir.isical.ac.in/dspace/handle/1/1268>. Citado na página 39.
37 DATTORRO, J. Convex Optimization and Euclidean Distance Geometry.
[S.l.]: Meboo Publishing USA, 2005. Citado na página 40.
38 WEINBERGER, K.; SAUL, L. Distance Metric Learning for Large Margin Nearest
Neighbor Classification. The Journal of Machine Learning Research, MIT Press,
v. 10, p. 207–244, 2009. Citado 4 vezes nas páginas 40, 41, 42 e 43.
39 WEINBERGER, K. Large Margin Nearest Neighbors. 2015. Disponível em:
<http://www.cs.cornell.edu/~kilian/code/lmnn/lmnn.html>. Citado 2 vezes nas páginas
43 e 62.
40 CHATPATANASIRI, R. et al. On Kernelization of Supervised Mahalanobis Distance
Learners. CoRR, abs/0804.1441, 2008. Disponível em: <http://arxiv.org/abs/0804.1441>.
Citado 2 vezes nas páginas 45 e 52.
111
41 SHLENS, J. A Tutorial on Principal Component Analysis. In: Systems
Neurobiology Laboratory, Salk Institute for Biological Studies. [S.l.: s.n.], 2005.
Citado na página 45.
42 MERCER, J. Functions of Positive and Negative Type, and their Connection
with the Theory of Integral Equations. Philosophical Transactions of the Royal
Society of London A: Mathematical, Physical and Engineering Sciences, The
Royal Society, v. 209, n. 441-458, p. 415–446, 1909. ISSN 0264-3952. Disponível em:
<http://rsta.royalsocietypublishing.org/content/209/441-458/415>. Citado na página 51.
43 RABINER, L. R. A Tutorial on Hidden Markov Models and Selected Applications
in Speech Recognition. In: Proceedings of the IEEE. [S.l.: s.n.], 1989. p. 257–286.
Citado na página 55.
44 FRANC, V. Statistical Pattern Recognition Toolbox. 2008. Disponível em:
<https://cmp.felk.cvut.cz/cmp/software/stprtool/>. Citado na página 63.
45 VIEIRA, A. W. et al. On the Improvement of Human Action Recognition from Depth
Map Sequences Using Space-time Occupancy Patterns. Pattern Recognition Letters,
v. 36, p. 221–227, 2014. Disponível em: <http://www.sciencedirect.com/science/article/
pii/S0167865513002778>. Citado na página 71.
