Em bases de dados com um grande volume de dados, a pesquisa de imagens de rosto semelhantes a uma dada imagem de consulta pode tornar-se impraticável, principalmente se for realizada de forma exaustiva. Desta forma, é fundamental realizar um estudo das várias técnicas existentes que possibilitem melhorar a eficiência das pesquisas baseadas na similaridade/proximidade entre imagens de rosto.
De modo a tornar as pesquisas por semelhança mais eficientes, foram propostas várias estruturas de dados métricas que se baseiam no conceito matemático de espaço métrico, o qual é muito usado sempre que seja necessário medir a proximidade entre elementos. Estas estruturas de dados particionam o espaço em regiões baseadas na proximidade dos elementos de modo a minimizar o número de cálculos da função de distância entre objectos da base de dados aquando de uma pesquisa.
Neste trabalho pretende-se avaliar a aplicabilidade e eficiência de estruturas de dados métricas na pesquisa por alcance de imagens de rosto semelhantes a uma dada imagem de consulta.
- Aplicabilidade das Estruturas de Dados Métricas: Definição e Avaliação
de Espaços Métricos
Representação das imagens de rosto: Para a representação das imagens de rosto foi utilizado o método designado de Eigenfaces. Desta forma,com base num conjunto de imagens de treino, cada imagem de rosto é projectada num espaço de menor dimensão sendo representada por um vector que descreve a imagem.Medidas de semelhança: Foram usadas 4 métricas para medir a similaridade entre as várias representações de imagens de rosto: Euclidiana, Manhattan, Mahalanobis - L1 e Mahalanobis - L2.
Método de avaliação das medidas de semelhança: A avaliação de cada métrica foi realizada com base nos resultados obtidos de várias pesquisas dos k vizinhos mais próximos nas diferentes bases de dados. Desta forma, em cada base de dados de imagens de rosto foram seleccionados aleatoriamente vários elementos para serem usados como objectos de consulta. Para cada elemento de consulta foi realizada uma pesquisa dos k vizinhos mais próximos, onde k corresponde ao número de imagens de rosto associadas ao elemento de consulta que existem na base de dados. Neste caso, para cada consulta calculou-se a taxa de verdadeiros positivos e a taxa de falsos negativos e foi apresentado graficamente a média de cada taxa referente às várias consultas efectuadas e apresentaram-se estes resultados num gráfico ROC.
Seja B uma base de dados, q um elemento de pesquisa e X o conjunto de resultados obtidos da pesquisa tal que X
B . A taxa de verdadeiros
positivos pode ser vista como a percentagem do número total de elementos
relevantes (imagens que pertencem ao indíviduo associado a q) que é
obtida por uma pesquisa e é definida da seguinte forma:
A taxa de falsos positivos pode ser vista como a percentagem do número total de elementos irrelevantes que é obtido por uma pesquisa e é definido como:
Resultados da avaliação: A pesquisa por similaridade utilizando qualquer uma das métricas apresenta bons resultados pois os gráficos (ver abaixo) demonstram que em media a maioria dos elementos relevantes faz parte dos resultados das consultas e a maioria dos elementos irrelevantes não aparece nos resultados das consultas. As 4 métricas apresentaram performances muito semelhantes, no entanto uma análise mais detalhada mostra que a distância de Manhattan foi a que obteve o ponto mais próximo do ponto óptimo nas 4 bases de dados, seguindo-se a distância Euclidiana.A seguinte figura apresenta, para cada uma das métricas, a média das taxas de verdadeiros positivos e falsos positivos nas 4 bases de dados de imagens de rosto ( Faces94, JAFFE , AT&T e Yalefaces).
Média das Taxas de Verdadeiros Positivos e Falsos Positivos nas 4 bases de dados, para cada uma das métricas
- Eficiência da Pesquisa por Alcance com Estruturas de Dados Métricas
O objectivo consiste em estudar a eficiência das estruturas de dados na pesquisa por alcance das imagens de rosto semelhantes. No entanto, existem dois aspectos importantes na avaliação que podem influenciar os resultados obtidos. Estes aspectos são: a parametrização das diversas estruturas de dados, pois o comportamento das várias estruturas depende dos parâmetros escolhidos; e raio de pesquisa, o qual deveria ser um valor que permita obter resultados relevantes para as pesquisas em questão, ou seja, aplicáveis ao domínio do problema em causa. Assim sendo, estes aspectos foram analisados antes de proceder à avaliação da eficiência da pesquisa por alcance.Nota:
- Sempre que são realizadas pesquisas por alcance com as estruturas
de dados métricas numa dada base de dados, para cada estrutura de dados
são criadas 3 instâncias das mesma que foram construídas tendo como
base 3 ficheiros correspondentes a permutações aleatórias da base de
dados. Este aspecto está relacionado com o facto da organização das
estruturas de dados dependerem da ordem segundo a qual os objectos
ocorrem como parâmetro de entrada para o algoritmo de construção.
- O conjunto de elementos a pesquisar em todas as avaliações
realizadas, é um conjunto de objectos aleatórios da base de dados.
De modo a manter o mesmo número de indivíduos diferentes neste
conjunto, foram escolhidos 25% das imagens associadas a cada indivíduo.
Raio de Pesquisa: Para seleccionar o raio de pesquisa, associado a determinada métrica e base de dados, foi utilizado um conjunto de objectos de pesquisa que contém 25% das imagens de rosto associadas a cada indivíduo. Com base no conjunto de objectos de pesquisa, foram testados vários raios de pesquisa. Neste caso, para cada espaço métrico numa determinada base de dados foram testados 1000 raios no intervalo de 0 a M, onde M corresponde à distância máxima que existe entre os vários elementos. Desta forma, para cada raio foram realizadas várias pesquisas por alcance com o conjunto de objectos de pesquisa e com base nos resultados de cada pesquisa foi calculada a taxa de verdadeiros positivos, a taxa de falsos positivos e o número de elementos retornados da pesquisa. Assim sendo, para cada raio (r) foi calculada a média da taxa de verdadeiros positivos (denotada por VPr) e falsos positivos (denotada por FPr) e a média do número de resultados obtidos das várias pesquisas por alcance realizadas com esse raio (denotada por Rr).Com base nesta informação para cada base de dados sobre um dado espaço métrico, um raio r é candidato a ser escolhido se:
- FPr < 0.03;
- Rr <= 130% * k, sendo k a média do número de imagens associadas a cada indivíduo da base de dados;
- Não existe nenhum outro raio candidato x, tal que VPx >=VPr e FPx <= FPr.
Do conjunto de raios candidatos foi seleccionado o raio cuja mé dia da taxa de verdadeiros positivos e falsos positivos está mais próxima do ponto óptimo (que corresponde a uma taxa de verdadeiros positivos igual a 1 e uma taxa de falsos positivos igual a 0). A tabela seguinte apresenta o raio que foi seleccionado com este critério para cada métrica nas diferentes bases de dados.
Raios de pesquisa utilizados na parametrizaçãoDistância Euclidiana Distância de Manhattan Mahalanobis - L1 Mahalanobis - L2 Faces94 3338 12347 7,96 2,04 JAFFE 4649 15560 10,23 2,74 AT&T 1507 5447 10,46 2,71 Yalefaces 9400 33767 14,95 4,02 Os raios apresentados na tabela 1 foram utilizados na parametrização das estruturas de dados métricas. Para além disso, estes são os raios que aparecem por defeito cada vez que é seleccionada uma base de dados e uma métrica no protótipo que foi desenvolvido.
Parametrização das estruturas de dados métricas: De modo a garantir que as parametrizações usadas nas diferentes estruturas de dados métricas são aqueles que garantem os melhores resultados na nossa avaliação da eficiência na pesquisa por alcance, foi realizada uma avaliação das parametrizações das diversas estruturas de dados métricas nas diversas bases de dados. Esta parametrização depende do espaço métrico e da base de dados. Assim sendo, para analisar o comportamento de uma estrutura de dados métrica associada a um determinado espaço métrico numa determinada base de dados foram testadas várias parametrizações. Para cada parametrização duma dada estrutura de dados foram construídas três estruturas de dados métricas, resultantes de 3 permutações da base de dados, e foram realizadas várias pesquisas por alcance tendo como base o raio de pesquisa e o conjunto de elementos de pesquisa seleccionados anteriormente. Desta forma, para cada parametrização foi contabilizada a média do número de computações da métrica que foram efectuadas para realizar as diversas pesquisas. Os links seguintes apresentam os resultados obtidos e as parametrizações escolhidas nas várias estruturas de dados métricas: LAESA, GNAT,VPTree, DSAT , HDSAT1, HDSAT2, LC e RLC. A estrutura de dados VPTree é a única que não tem parametrizações.
Método de avaliação da pesquisa por alcance: A avaliação da pesquisa por alcance com as diferentes estruturas de dados métrica foi realizada tendo como base o número de cálculos de distância realizados para cada pesquisa. Para cada permutação das bases de dados e cada métrica foram realizadas 3 pesquisas por alcance com o conjunto de elementos de pesquisa e 3 raios de pesquisa, que correspondem, respectivamente, a 50%, 100% e 120% do raio seleccionado. Note que o segundo raio de pesquisa é o mesmo que foi utilizado na parametrização das estruturas de dados. Os 3 raios de pesquisa utilizados para cada métrica, nas diferentes bases de dados estão representados na seguinte tabela.
Distância Euclidiana Distância de Manhattan Mahalanobis - L1 Mahalanobis-L2 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio Faces94 1669 3338 4006 6174 12347 14816 3,98 7,96 9,55 1,02 2,04 2,45 JAFFE 2325 4649 5579 7780 15560 18672 5,12 10,23 12,28 1,37 2,74 3,29 AT&T 7,54 1507 1808 2724 5447 6536 5,23 10,46 12,55 1,36 2,71 3,25 Yalefaces 4700 9400 11280 16884 33767 40520 7,48 14,95 17,94 2,01 4,02 4,82 Raios de pesquisa utilizados na avaliação das pesquisas por alcance
.
Para cada pesquisa por alcance realizada no conjunto de elementos a pesquisar com um determinado raio, o número (em média) de elementos no conjunto resposta por cada elemento a pesquisar está presente na seguinte tabela:
Distância Euclidiana Distância de Manhattan Mahalanobis - L1 Mahalanobis-L2 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio Faces94 13,29 25,74 56,37 13,04 25,84 60,69 12,42 25,07 63,85 12,43 25,41 65,4 JAFFE 5,38 16,34 23,84 4,78 15,9 25,28 3,92 15,32 27,34 3,74 15,7 28,22 AT&T 2,38 12,89 30,3 2,23 12,73 32,6 1,99 12,96 37,95 2,01 12,98 38,05 Yalefaces 3,27 9,97 15,3 3,4 10,47 17,17 2,47 9,97 26,17 2,1 9,47 27,13 Média do nº de elementos obtidos com os diferentes raios associados a cada uma das métricas
Os resultados obtidos (número de distâncias calculadas) para cada base de dados dizem respeito à média dos valores obtidos em cada permutação da base de dados. Para uma dada permutação o valor é a média dos valores obtidos para cada elemento a pesquisar.
Protótipo para pesquisa por alcance: O protótipo foi implementado em Java, e permite realizar pesquisas por alcance de imagens de rosto. Ou seja, dada uma imagem de rosto de consulta e um raio de pesquisa, o sistema devolve o conjunto de imagens de rosto semelhantes/próximas que existem na base de dados seleccionada,de acordo com a pesquisa realizada. Note-se que é possível utilizar diferentes estruturas de dados métricas e diferentes medidas de semelhança. Para além disso, este protótipo permite utilizar 4 bases de dados (Faces94, JAFFE,AT&T, Yalefaces).
Para visualizar uma animação de demonstração do protótipo implementado clique aqui.
Resultados das avaliações: Em relação aos resultados da avaliação verificamos que a LAESA foi a estrutura de dados que obteve o melhor desempenho com as diferentes métricas nas várias bases de dados. A RLC foi a estrutura a seguir à LAESA que obteve os melhores esultados. Em relação às estruturas de dados métricas dinâmicas, a RLC foi a que obteve os melhores resultados na maioria dos casos. De seguida serão apresentados os links para os gráficos que validam estes factos e que são o resultado da nossa avaliação:
- Avaliação das estruturas de dados com a distância Euclidiana
- Avaliação das estruturas de dados com a distância de Manhattan
- Avaliação das estruturas de dados com a Mahalanobis - L1
- Avaliação das estruturas de dados com a Mahalanobis - L2
Os resultados desta experiência mostram que todas as estruturas de dados métricas reduziram o número de computações da métrica em relação ao tamanho da base de dados e, desta forma, são uma mais valia na pesquisa por alcance das imagens de rosto semelhantes. As tabelas seguintes apresentam a percentagem de cálculos de distância face ao número de elementos da base de dados, para cada base de dados, métrica e raio de pesquisa.
Faces94JAFFEAT&TYalefaces1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio VPtree 7,43%
20,98%
26,95%
18,99%
39,06%
45,9%
27,87%
60,79%
72,02%
28,93%
53,39%
61,37%
LC 5,97%
15,33%
21,16%
20,16%
36,03%
42,98%
22,71%
46,83%
56,48%
19,93%
40,07%
48,12%
HDSAT2 4,68%
10,67%
14,51%
17,72%
31,11%
37,5%
21,89%
45,61%
56,79%
19,05%
35,19%
43,62%
RLC 5,9%
11,38%
14,07%
17,9%
30,06%
34,46%
25,61%
43,67%
55,74%
19,7%
33,64%
42,51%
GNAT 4,56%
11,07%
15,2%
14,46%
30,04%
37,12%
22,48%
50,82%
62,43%
16,92%
37,91%
47,8%
LAESA 2,94%
14,14%
21,71%
12,95%
24,53%
30,96%
10,42%
32,36%
45,73%
13,76%
31,33%
40,30%
Percentagem da média do nº de computações em relação ao tamanho da basede dados com a distância Euclidiana
Faces94JAFFEAT&TYalefaces1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio VPtree 10,64%
28,86%
36,44%
27,86%
53,94%
63,34%
38,53%
78,48%
86,97%
45,14%
72,53%
80,92%
LC 6,69%
18,41%
25,83%
23,78%
40,67%
50,2%
26,67%
56,17%
69,9%
26,59%
48,45%
60,92%
HDSAT2 6,54%
14,54%
19,4%
22,56%
40,46%
48,74%
29,37%
58,64%
71,06%
24,55%
47,25%
58,32%
RLC 5,97%
12,14%
15,59%
20,24%
36,70%
45,69%
27,95%
53,79%
69,1%
22,24%
43,06%
56,54%
GNAT 7,12%
16,08%
21,2%
19,94%
41,37%
51%
33,62%
65,84%
76,68%
23,58%
51,2%
63,44%
LAESA 3,19%
17,08%
28,56%
12,23%
31,73%
43,01%
9,56%
38,28%
55,73%
15,36%
34,61%
46,63%
Percentagem da média do nº de computações em relação ao tamanho da basede dados com a distância de Manhattan
Faces94JAFFEAT&TYalefaces1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio VPtree 15,52%
39,64%
47,38%
41,36%
68,2%
77,7%
53,33%
88,64%
93,85%
64,71%
88,61%
94,1%
LC 7,54%
22,73%
31,35%
31,29%
53,38%
63,09%
33,91%
65,95%
78,51%
35,6%
68,3%
80,92%
HDSAT2 8,31%
18,14%
23,81%
30,31%
54,49%
64,5%
34,51%
70,46%
82,37%
36,38%
67,99%
79%
RLC 7,46%
14,02%
18,35%
28,32%
48,75%
61,88%
32,8%
65,11%
81,24%
32,03%
67,8%
81,65%
GNAT 10,31%
21,28%
27,18%
30,99%
55,58%
66,12%
45,46%
78,15%
87,15%
41,44%
76,88%
87,09%
LAESA 2,73%
23,82%
38,79%
19,03%
43,62%
53,13%
13,38%
50,69%
67,79%
24,57%
58,32%
72,66%
Percentagem da média do nº de computações em relação ao tamanho da base de dados com Mahalanobis - L1
Faces94JAFFEAT&TYalefaces1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio 1º raio 2º raio 3º raio VPtree 15,37%
38,8%
47,06%
38,86%
70,6%
79,09%
52,4%
88,39%
94,03%
67,1%
91,14%
94,89%
LC 7,3%
22,1%
31%
33,08%
57,2%
65,77%
34,48%
67,96%
79,97%
39,95%
70,06%
84,46%
HDSAT2 8,28%
17,75%
23,34%
32,75%
56,53%
67,2%
35,61%
70,34%
82,19%
37,14%
69,94%
80,63%
RLC 7,58%
14,15%
18,64%
30,61%
51,08%
65,24%
33,41%
65,22%
81,61%
36,7%
68,19%
82,54%
GNAT 9,16%
19,57%
25,46%
33,32%
59,21%
70,08%
44,49%
78,46%
87,03%
46,96%
79,63%
89,57%
LAESA 3,85%
32,08%
45,22%
20,32%
43,62%
53,52%
18,34%
58,82%
73,65%
23,74%
62,17%
75,88%
Percentagem da média do nº de computações em relação ao tamanho da basede dados com a Mahalanobis - L2
Em relação às estruturas de dados DSAT e variantes, apenas foi utilizada a HDSAT2 nesta avaliação pois, das 3, foi a que obteve sempre os melhores resultados (ver parametrização da DSAT e variantes).
- Sempre que são realizadas pesquisas por alcance com as estruturas
de dados métricas numa dada base de dados, para cada estrutura de dados
são criadas 3 instâncias das mesma que foram construídas tendo como
base 3 ficheiros correspondentes a permutações aleatórias da base de
dados. Este aspecto está relacionado com o facto da organização das
estruturas de dados dependerem da ordem segundo a qual os objectos
ocorrem como parâmetro de entrada para o algoritmo de construção.
Conclusão: Com base no estudo realizado
pode-se concluir que é possível utilizar estruturas
de dados métricas no domínio das imagens de rosto, obtendo
resultados nas pesquisas que se consideram “
satisfatórios” neste domínio de aplicação.
Os resultados obtidos na avaliação das várias estruturas
de dados métricas mostram que estas são uma mais valia na
pesquisa por alcance das imagens de rosto semelhantes. Em todos os casos
experimentais existiu uma redução do número de
computações da métrica face à pesquisa
exaustiva. A estrutura de dados métrica LAESA foi
a que obteve o melhor desempenho seguida da RLC.
Em relação às estruturas de dados métricas
dinâmicas a RLC foi a que obteve os melhores resultados.
Contributos: No que diz respeito aos contributos deste trabalho, é de salientar que:
- Face à pesquisa bibliográfica realizada, podemos concluir que este é o primeiro trabalho que usa estruturas de dados métricas para a pesquisa por alcance em imagens de rosto;
- Este trabalho mostra que é possível agilizar as pesquisas por alcance das imagens de rosto semelhantes;
- Foi realizada uma avaliação da eficiência da pesquisa por alcance com estruturas de dados métricas no domínio das imagens de rosto, usando 4 métricas em 4 bases de dados;
- Foi realizada uma avaliação para as 4 métricas (distância Euclidiana, distância de Manhattan, Mahalanobis - L1, Mahalanobis - L2), utilizando o método de Eigenfaces para a representação das imagens de rosto;
- Foi desenvolvido um pacote de estruturas de dados métricas genérico
composto pela LAESA,
GNAT, VPTree, DSAT, HDSAT1,
HDSAT2, LC e RLC. Este
poderá ser utilizado para a estudar aplicabilidade e
eficiência das estruturas noutros domínios
de aplicação.
Publicações: Este trabalho já deu origem a 2 publicações:
- F. Barbosa, F. Costa, P. Chambel, P. Paiva, ”Pesquisa aproximada em diferentes domínios de aplicação”, Proceedings of the Conferência Ibero-Americana WWW/Internet (CIAWI 2008), 2008
- P. Chambel, F. Barbosa, “Improving Similarity Search in Face-Images Data”, To appear in Proceedings of the Second Workshop on Very Large Digital Libraries (VLDL) of 13th European Conference on Research and Advanced Technologies on Digital Libraries (ECDL), 2009
O trabalho que se propõe, vir a ser desenvolvido no futuro, está inserido em 2 tópicos:
- Técnicas eficientes para a pesquisa por semelhança;
- Representação/semelhança de imagens de rosto.
No que diz respeito às estruturas de dados métricas aqui implementadas e avaliadas, é fundamental:
- Implementar a pesquisa dos k - vizinhos mais próximos;
- Avaliar esta pesquisa no que diz respeito à sua eficiência em diferentes domínios;
- Avaliar as pesquisas por semelhança considerando actualizações à base de dados (inserções e remoções);
- Avaliar as pesquisas por semelhança considerando também a complexidade espacial.
No que diz respeito ao domínio de aplicação (imagens de rosto) é fundamental:
- Identificar outros espaços métricos que utilizem outras formas de representação de imagens de rosto, como por exemplo com os descritores extraídos com a técnica SIFT;
- Avaliar esses espaços métricos face aos implementados neste trabalho;
- Avaliar a eficiência da pesquisa por alcance com as estruturas de dados métricas
nestes novos espaços métricos.
Em relação ao protótipo desenvolvido é fundamental que este permita a inserção/remoção de imagens de rosto. No que diz respeito à avaliação realizada nesta tese seria conveniente comparar outras técnicas, que não sejam baseadas em espaços métricos, com a avaliação aqui apresentada. Por último, seria muito interessante poder usar as estruturas de dados métricas numa aplicação concreta na área das imagens de rosto.