Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
TÉCNICAS E ALGORITMOS PARA AGRUPAR
FOTOGRAFIAS DIGITAIS
RESUMO
Com a crescente popularidade das máquinas fotográficas digitais, a organização, gestão e
agrupamento de milhares de fotografias tornou-se um problema enfrentado por fotógrafos
profissionais e amadores. Neste documento serão abordadas diversas estratégias e
métodos utilizados na automatização desses processos, onde são consideradas as diversas
características das fotografias digitais: características semânticas, metadata, e
características de conteúdo ou características low-level (cor, textura, forma).
Serão analisadas as vantagens e lacunas dos estudos actualmente mais relevantes nesta
área. E por fim será proposta uma solução que tenta conciliar tais vantagens, tentando
também suprimir as deficiências de cada abordagem.
INTRODUÇÃO
O aparecimento de câmaras fotográficas digitais e a sua forte aceitação, permitiu aos
adeptos da fotografia despreocuparem-se com os custos de revelação e consequentemente
acumularem uma elevada quantidade de fotografias. Esta evolução tecnológica, ao
provocar a mudança da imagem em papel para a imagem digital, originou alterações nas
práticas dos utilizadores. Os reduzidos custos das fotografias digitais deixaram de limitar
a liberdade para fotografar desencadeando o crescimento das colecções fotográficas e
uma crescente tendência para o aparecimento de fotografias muito similares, por vezes
quase indiferenciáveis. Não só o utilizador passou a tirar mais fotografias como a partilha
das mesmas passou a estar mais facilitada, intensificando o aumento das imagens da sua
colecção.
Todas estas alterações na actividade fotográfica, em particular o aumento drástico do
número de fotografias, exigiram a necessidade de ferramentas que ajudassem o utilizador
na organização, gestão e procura automática de fotografias.
É neste sentido que pretendo desenvolver uma aplicação que facilite a organização de
qualquer colecção fotográfica e que por sua vez facilitará a gestão e procura de
fotografias.
Dispondo de colecções de milhares de fotografias os utilizadores deparam-se com a
dificuldade de organização dessas mesmas fotografias. De acordo com Frohlich e al.
[Frohlich 2002], são poucos os utilizadores que sistematicamente organizam as suas
colecções fotográficas. Dependendo dessa organização estão as futuras actividades de
gestão e pesquisa de fotos. O desenvolvimento de uma aplicação que agrupe essa
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
diversidade de fotos, de maneira a gerar colecções organizadas leva-nos à necessidade de
conhecer quais os factores de agrupamento a considerar.
Sendo que, automatizar o agrupamento efectuado manualmente pelos utilizadores, é o
principal objectivo deste tipo de sistemas, surge-nos a questão: quais as práticas mais
comuns na gestão e organização de fotografias? É na resposta a esta questão que
encontramos o fio condutor da realização do sistema [Kirk 2006] [Frohlich 2002]
[Rodden and Wood 2003].
Na tentativa de responder à questão anterior encontramos a primeira dificuldade. Cada
utilizador tem costumes próprios na organização das suas fotos e cada foto simboliza um
momento que poderá não ser descrito pela própria imagem ou informação a ela anexada.
Por vezes o contexto em que foi tirada a foto influência o método de organização da
mesma no respectivo álbum.
A dificuldade e o elevado consumo de tempo inerente à anotação de imagens a realizar
pelo utilizador, origina colecções fotográficas com pouca informação que contextualize o
conteúdo das imagens. A falta de informação contextual acerca do conteúdo da fotografia
ou do evento no qual a foto foi realizada torna mais subjectiva a interpretação das
fotografias, e dificulta a tarefa de organização e agrupamento das mesmas.
Não sendo possível o agrupamento e organização através de keywords que caracterizem
as fotos, teremos que focar outras abordagens que as contextualizem. Uma possibilidade
de extracção de contexto pode ser obtida através da correlação das imagens utilizando a
data e tempo das fotografias. Esta abordagem organiza as fotografias cronologicamente
de modo a identificar diferentes eventos. Mas até o próprio conceito de evento poderá ser
abordado de diferentes maneiras por diferentes utilizadores.
Mas será que o utilizador quer realmente agrupar as suas fotografias por eventos, ou
gostaria de agrupar as fotografias por similaridades ou outra métrica de relacionamento?
Um sistema que se adapte a diferentes categorias de utilizadores terá que considerar
informação díspar da informação contextual.
Juntamente com a informação contextual disponibilizada, podemos analisar as
características do conteúdo das imagens. Esta segunda perspectiva aproxima o nosso
problema às técnicas utilizadas nos sistemas de recuperação de imagens. Tal como nos
sistemas de recuperação de imagens, também nos focamos nas características da imagem
como conjunto de pixeis. O estudo das características low-level de uma imagem ajuda na
sua caracterização, e possibilita diversos géneros de agrupamento. Consequentemente,
novas questões surgem: quais as melhores características para descrever imagens, em
particular imagens fotográficas? Qual a utilidade de cada característica no agrupamento
de imagens vs recuperação de imagens? Como extrair tais características? Por fim, como
correlacionar os diferentes descritores extraídos da imagem?
Tendo obtido um conjunto de descritores que definam uma fotografia, passamos à
problemática da escolha da melhor métrica de definição de similaridade de contexto.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Existem diversas soluções desenvolvidas actualmente, sendo que a maioria dessas
soluções focam apenas o agrupamento de imagens baseado em eventos. Entenda-se por
evento uma actividade ou conjunto de actividades relacionadas entre si e realizadas num
intervalo de tempo contínuo.
No seguimento desta perspectiva, a maioria das soluções explora exaustivamente as
características temporais ignorando as características de conteúdo de imagem. Esta
lacuna na comparação de fotos limita os tipos de agrupamentos proporcionados pelas
soluções desenvolvidas.
Como solução dos problemas de organização de fotografias proponho um sistema que
tente abranger o máximo informação possível de cada fotografia. Nunca desprezando as
limitações computacionais impostas a qualquer aplicação end-user.
Dada a subjectividade na análise de fotografias, tentarei tornar o sistema bastante
parametrizável, dando a possibilidade do utilizador escolher os pesos de cada género de
agrupamento. Ao dispor do controlo de diversos parâmetros, o utilizador poderá adaptar o
sistema ao tipo de fotografias da sua colecção e às suas necessidades de agrupamento.
Para conseguir esta diversidade de agrupamentos, irei considerar técnicas de detecção de
eventos que analisam a informação contextual disponível. Irei também implementar
algumas soluções conhecidas da área de recuperação de imagens (CBIR), adaptando-as
ao agrupamento de fotografias baseado no conteúdo das imagens. Neste segundo género
de agrupamento tentarei abranger um elevado número de características low-level (cor,
textura, forma).
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Soluções existentes
Durante estes últimos anos tem-se observado um crescente interesse na área da análise de
imagem. Com o massivo crescimento das máquinas fotográficas digitais, esse interesse
especificou-se neste tipo de imagens. Desde então, os utilizadores têm exigido aplicações
que lhes ajudem a gerir e organizar as suas fotografias.
Entre as diferentes abordagens desenvolvidas para o agrupamento de imagens,
encontramos uma grande incidência na utilização da informação temporal como critério
base de organização. A complementar este critério são frequentemente utilizadas
abordagens utilizadas na área de recuperação de imagens baseada no conteúdo (ContentBase Image Retrieval - CBIR). A análise do conteúdo das imagens é efectuada através da
extracção de características descritoras das mesmas, denominadas por características lowlevel. No conjunto de características low-level encontramos 3 categorias: cor, textura e
forma.
Adquirido o conjunto de descritores de cada fotografia, procede-se ao agrupamento das
fotos. Esse agrupamento é frequentemente efectuado através de técnicas de clustering ou
por métricas de cálculo de similaridade de conteúdo e ou de contexto.
Girgensohn et al. propõem uma aplicação de organização de fotos baseada em eventos
[Girgensohn 03]. Nessa aplicação encontramos uma light table onde apresentam os
thumbnails das diferentes fotos. Complementando a light table ainda dispomos de uma
vista em árvore que suporta a navegação pela colecção. A divisão da colecção em
diferentes categorias é efectuada pela detecção automática de eventos, sendo possível
ajustar manualmente as fronteiras de cada evento.
Esta abordagem permite a organização em diversas categorias (ex.: pessoas, lugares,
eventos) através da filtragem de metadata associada às fotografias (informação GPS ou
reconhecimento de faces). Este género de filtragem é efectuado automaticamente quando
este tipo de informação se encontra disponível. O utilizador ainda dispõe de mecanismos
de criação de metadata através da associação manual das fotografias às categorias
desejadas ou aos eventos criados. Estes autores defendem que, na maioria das vezes, a
similaridade do conteúdo das imagens é menos significativa que a metadata para a
detecção de eventos. No seguimento dessa ideia, adaptam o algoritmo proposto em
[Cooper and Foote 2001] para realizar o clustering das fotografias com timestamps
semelhantes.
Neste estudo os autores demonstram a ideia inicial de [Graham 2002][Gargi 2003], que
defendem que a organização temporal das fotografias aumenta a performance em tarefas
de recuperação. Eu também estou de acordo com esta perspectiva, mas penso que
poderemos melhorar. Quantas vezes nos aconteceu tirar fotografias do mesmo evento
mas distanciadas por um intervalo de tempo considerável? Em contrapartida, quantas
vezes tiramos fotografias separadas por curto espaço de tempo mas que consideramos
como pertencentes a eventos diferentes? Outro problema ainda mais comum acontece
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
quando pretendemos juntar à nossa colecção, fotografias de um familiar ou amigo. Neste
caso a nossa colecção expande e provavelmente passa a conter fotografias de eventos
diferentes realizados em datas e tempos semelhantes. Se considerarmos eventos
diferentes, talvez queiramos que sejam organizados separadamente.
Outra impossibilidade deste sistema é a organização das fotografias por similaridade de
conteúdo. Ao considerarem apenas a metadata associada às fotografias limitam as
possibilidades de associação entre imagens, e como é referido por diferentes
investigadores, este tipo de informação não é muito frequente em fotografias e quando
existe é muito reduzida.
Cooper et al. apresentam-nos um método de clustering de colecções de fotos [Cooper
2005]. O método utilizado neste estudo já permite a divisão da colecção de fotos baseada
apenas na similaridade temporal ou conjugando as características temporais com as
características de conteúdo. Esta nova preocupação no conteúdo das imagens vem no
seguimento da tentativa de responder aos 3 maiores tipos de procuras efectuadas pelos
utilizadores e reportadas por [Rodden and Wood 2003]:
1. procurar fotografias pertencentes a um determinado evento;
2. procurar uma fotografia em particular;
3. procurar um conjunto de fotografias pertencentes a diferentes eventos mas que
partilhem atributos semelhantes (ex:. determinada pessoa).
Sem desprezar o conteúdo das imagens, o foco deste estudo localiza-se
fundamentalmente na organização temporal das colecções fotográficas em várias escalas.
Este método é automático não necessitando de qualquer parâmetro de threshold ou treino.
A similaridade é calculada entre todos os pares fotos numa vizinhança local e a avaliação
dessa similaridade é efectuada para diferentes escalas temporais.
A cada escala é calculado um valor de correlação para determinar novos pontos de
informação que eles designam por “novel scores”. As fronteiras de cada evento são
determinadas através da escolha da melhor escala para segmentação da colecção. Por fim
são apresentados alguns métodos para avaliação dos clusters associados às diferentes
fronteiras detectadas.
Uma das limitações deste algoritmo de detecção de eventos é a sua complexidade
quadrática no número de fotos. Para resolução desta restrição, são apresentadas duas
variações: uma baseada no critério de informação de Bayes (Bayes information criterion BIC) e outra baseada em programação dinâmica.
Apesar de não serem estudadas, a inserção da possibilidade de considerar semelhanças de
conteúdo de imagem melhoram as possibilidades de agrupamento. Outro aspecto positivo
desta abordagem é o facto de não utilizar thresholds ou outro género de assumpções,
permitindo generalizar o sistema a diferentes tipos de colecções de imagens.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Em [Platt 2003] é apresentado o PhotoTOC (Photo table of Contents), um sistema de
organização de fotografias. Este sistema efectua o agrupamento de fotos através do
clustering das datas de criação e das cores das fotografias. Neste paper são apresentados
dois algoritmos de clustering: o primeiro é time-based e portanto baseia-se no tempo de
criação da fotografia para efectuar o agrupamento. O segundo é content-based, utilizando
as cores da fotografia para detectar similaridades. Neste segundo algoritmo, o tempo de
criação é apenas utilizado para ordenação das fotos e é a cor que é utilizada para efectuar
o clustering. Os autores dão preferência à utilização do algoritmo time-based, utilizando
o segundo como algoritmo de backup, para quando a informação temporal não é credível.
No meu ponto de vista, esta abordagem torna-se bastante redutiva ao incentivar apenas a
informação temporal. Tal como já havia dito atrás, o automatismo da geração de
agrupamentos de fotografias não poderá basear-se apenas na data de criação das
fotografias. Caso assim seja, limitamos as possibilidades de formação de grupos, obtendo
apenas grupos com similaridade temporal. Outro aspecto onde penso já haver soluções
melhoradas é no modo como é feito o clustering. Neste sistema o algoritmo de clustering
necessita de threasholds calculados empiricamente e as fotos não são comparadas entre
todas. O algoritmo apenas ordena cronologicamente as fotos e efectua comparações ao
longo de uma janela de dimensão n, sendo n também calculado empiricamente (neste
estudo foi utilizado o valor 10).
[Platt 2003] vem no seguimento do estudo efectuado por Platt [Platt 2000], onde já era
apresentado um método de clustering através da data e hora em que as fotos foram
tiradas. O tipo de clustering usado em [Platt 2000] pode ser combinado com o clustering
de conteúdo das imagens. O AutoAlbum, o sistema proposto, utiliza agrupamento
probabilístico para obter uma melhor performance de clustering baseado no conteúdo das
imagens. O modelo probabilístico utilizado é o Left-Right Hidden Markov Model
(HMM).
Novamente são propostos dois métodos de clustering que poderão ser utilizados
simultaneamente e combinados de diversas maneiras. Essa combinação permitirá obter
diferentes perspectivas de agrupamento, dado que a noção de agrupamento é muito
subjectiva entre utilizadores.
Kechinsky et al. desenvolveram o FotoFile, um sistema para recuperação e organização
multimédia [Kuchinsky 1999]. Neste sistema, tal como eles referem, foi aplicada uma
abordagem híbrida. Foram desenvolvidas diversas técnicas que facilitam o utilizador a
efectuar anotações, que posteriormente serão utilizadas nas actividades de organização e
procura de elementos multimédia, incluindo fotografias. São também utilizadas várias
técnicas de indexação baseadas no conteúdo das imagens, aumentando as capacidades de
organização.
O sistema proposto tenta combinar as vantagens das anotações efectuadas manualmente
pelos utilizadores e as vantagens da extracção automática de características de conteúdo.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Tal como na maioria dos investigadores, também neste estudo é consensual a importância
e dificuldade inerente às anotações dos elementos multimédia. É nesse sentido que o
FotoFile dispõe de mecanismos de facilitam a realização dessas anotações. Mas mesmo
que tendo o trabalho facilitado, o utilizador terá que despender bastante atenção e tempo
à anotação das fotos. A necessidade de anotação tornam o sistema bastante dependente do
utilizador e o conceito de automatização fica bastante relaxado. É por isso que a
utilização de mecanismos de extracção de características, aumenta a automatização do
sistema e facilita a organização das fotos. Neste sentido, é de evidenciar o esforço
efectuado na análise de conteúdo efectuado através da detecção de faces disponibilizada
pelo sistema. Esta funcionalidade já permite uma organização específica de fotografias,
explorando bastante bem as potencialidades da análise de conteúdo.
Um aspecto ainda por analisar e fulcral para a análise do sucesso do sistema será o estudo
comportamental dos seus utilizadores. Visto que o processo de anotação é a actividade
que menos atrai os utilizadores na organização das suas colecções e sendo a razão para o
desenvolvimento destes sistemas, será importantíssimo saber se os mecanismos
implementados atraem os utilizadores para essa tarefa.
Em 2000 Liu et al apresentaram um sistema de gestão de fotografias familiares
denominado MiAlbum [Liu 2000a]. Este sistema é baseado na anotação semiautomática
das fotos. Liu Wenyin et al defendem que uma procura eficiente de imagens requer a
ajuda das anotações, de modo a efectuar uma procura baseada em keywords. Para tal é
utilizado o método de anotação de imagens proposto em [Liu 200b]. O processo de
anotação semiautomática encontra-se inserido nos processos de recuperação de imagens e
respectivo feedback. Quando um utilizador pesquisa uma determinada fotografia através
de um conjunto de keywords, poderá proporcionar um feedback ao sistema relativamente
à resposta que este lhe deu como resultado da pesquisa. Através deste feedback o sistema
actualiza as relações entre as imagens e as keywords utilizadas. Deste modo a anotação da
base de dados do sistema é aperfeiçoada com o aumento progressivo de pesquisas e
feedback.
Quando o utilizador importa novas fotografias, o sistema realiza uma pesquisa
automática, procurando as fotografias do álbum que mais se assemelhem visualmente às
imagens importadas. Essa pesquisa é efectuada utilizando as tradicionais técnicas de
recuperação de imagens baseada no conteúdo. Obtidas as imagens mais semelhantes, são
seleccionadas as keywords mais frequentes nesse grupo de imagens e associadas à nova
fotografia. Essa associação só será validada pelo utilizador através do feedback de uma
futura pesquisa.
A ideia traduzida neste sistema está direccionada à procura de imagens específicas. O
utilizador quando pretende visualizar um conjunto de fotografias já tem de ter
especificado um objectivo, que traduzirá numa keyword de pesquisa. No nosso caso
pretendemos gerar associações entre imagens para permitir ao utilizador observar a sua
colecção inteira através desse agrupamento de associações. No nosso estudo o objectivo
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
não será uma imagem específica mas permitir ao utilizador uma organização da sua
colecção fotográfica que vá de encontro aos seus objectivos.
Outro problema desta abordagem foca-se no facto do sistema necessitar de ser utilizado
bastantes vezes para produzir resultados aceitáveis. Com este sistema não conseguimos
ter uma organização da colecção imediatamente após importarmos as nossas fotos. Se
não tivermos o sistema treinado, não conseguiremos criar um álbum com as fotografias
que acabámos de descarregar dos nossos dispositivos fotográficos.
O ponto positivo a retirar deste sistema reflecte-se na possibilidade do utilizador dar
feedback às operações efectuadas automaticamente.
Loui e Savakis apresentam-nos um algoritmo que automatiza a criação de álbuns de
fotografias descrito em [Loui and Savakis 2003]. Neste estudo Loui e Savakis introduzem
dois algoritmos base: um de clustering de eventos e outro de detecção de imagens de
baixa qualidade. Nós vamo-nos focar no algoritmo de clustering de eventos.
A técnica de clustering desenvolvida, utiliza a data e tempo para a detecção de eventos e
conjuga a utilização da cor para agrupar as imagens de cada evento. Nesta abordagem os
eventos são obtidos através de um algoritmo de clustering k-means [Jain and Dubes
1988]. Na análise da cor é utilizada uma técnica de correlação de histogramas de cor
baseados em blocos da imagem.
O objectivo desta abordagem é a organização de fotografias em eventos e sub-eventos
através de dois tipos de informação: data e tempo de captura das fotos, reflectindo as
actividades implícitas nas fotos, e na similaridade de conteúdo.
O algoritmo utilizado demonstra ser útil na organização das nossas colecções quando
pretendemos uma organização por eventos, e considerarmos um evento como uma
actividade limitada por características temporais. A divisão dos eventos através da análise
de conteúdo de imagem já permite uma aproximação a outro género de agrupamento,
muitas vezes do interesse do utilizador, e efectivamente complementa a organização
temporal.
Um aspecto que poderá ser melhorado corresponde à melhoria das técnicas de análise de
conteúdo. Poderá ser vantajoso a combinação de diferentes técnicas de extracção de
semelhanças de conteúdo.
Este trabalho mostra-se limitado quando comparado com os objectivos de agrupamento
propostos no nosso estudo. Os resultados obtidos por Loui e Savakis mostram-se bastante
dependentes da característica temporal.
Gargi et al [Gargi 2003a] apresentam algumas técnicas de gestão e procura em colecções
de imagens digitais. Apesar de não se focar muito em métodos automáticos de
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
organização e agrupamento de imagens, este estudo explora bem a necessidade do
utilizador em obter diferentes formas de agrupar as fotos. A gestão de fotografias
proposta incide bastante na possibilidade de oferecer diferentes perspectivas da colecção.
O usual método de organização temporal é expandido a uma organização mais flexível,
de acordo com o propósito do utilizador. Neste paper é também abordado o problema de
gestão de álbuns criados. A ligação entre cada álbum e os ficheiros das imagens é
efectuada através de links que permitem a actualização dos álbuns quando uma foto é
movida ou removida. É introduzido o conceito de “álbum virtual”, que define o conjunto
de links que definem a perspectiva de cada álbum em relação à colecção.
Nos processos de procura disponibilizam técnicas de similaridade baseadas na metadata
disponibilizada pelas câmaras fotográficas, nas características low-level das imagens e na
detecção de faces. Sendo estas técnicas utilizadas na procura de imagens, será útil incluilas na automatização do agrupamento das mesmas.
Encontramos ainda muitos outros apologistas da utilização do tempo como característica
base à organização e browsing de fotos digitais pessoais. Todos estes estudos defendem a
ideia de que fotos semanticamente relacionadas têm também um relacionamento temporal
[Graham 2002][Huynh 2005][Gargi 2003b].
No trabalho de Lu et al apresentado em [Lu 2004], podemos observar uma das poucas
abordagens deste problema que não esteja estritamente dependente das características
temporais. Neste estudo são apresentadas técnicas de organização e clustering de fotos
utilizando o domínio da frequência DTC. Esta técnica utiliza os primeiros coeficientes
DCT diferentes de zero para calcular histogramas de energia no domínio da frequência. A
similaridade entre as fotos é obtida através da comparação desses histogramas.
Esta perspectiva permite a organização das fotos através do seu conteúdo, obtendo
resultados satisfatórios. Se combinarmos este método com os restantes métodos de
extracção de características, poderemos aperfeiçoar a detecção de similaridades e
consecutivamente melhorar esta técnica de agrupamento. Esta abordagem vem resolver
algumas lacunas de alguns dos estudos anteriores, evidenciando que a similaridade de
conteúdos de imagens é importante para utilizador na organização de colecções [Rodden
2001].
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Na tabela seguinte é resumida cada uma das abordagens descritas e analisadas
anteriormente. Para cada estudo são assinaladas as características em que se apoiam as
técnicas de agrupamento desenvolvidas (tempo, cor, textura, forma, detecção de faces,
metadata e informação semântica). Na última coluna da tabela é apresentado o foco de
estudo de cada abordagem, por exemplo: em [Cooper 2005] são utilizadas características
temporais e características de conteúdo de imagem, sendo que a ideia base de
agrupamento centra-se na informação temporal.
Tabela 1 – estudos mais relevantes de agrupamento de imagens.
Time
Features
[Girgensohn 03]
[Cooper 2005]
[Platt 2003]
[Platt 2000]
[Kuchinsky 1999]
[Liu 2000a]
[Loui and Savakis
2003]
[Gargi 2003a]
[Lu 2004]
(1)
(2)
(3)
Color
Features
Texture
Features
Shape
Features
Detecção
de faces
Metadata
Informação
Semântica
Foco
Detecção eventos
(time)
Detecção eventos
(1)
(time)
Detecção eventos
(time)
Detecção eventos
(time)
Utilização de anotações
(2)
Utilização de anotações
Detecção eventos
(time)
Detecção eventos
(3)
(time) e agrupamento
por conteúdo
Análise da cor através
de histogramas de
energia
o algoritmo possibilita a inserção de descritores de características low-level no calculo de
similaridades mas não é efectuado nenhuma abordagem a estas características.
Nesta abordagem apenas utilizam as tradicionais técnicas de content based retrieval durante a
importação de novas fotografias, para obterem informação metadata.
Este método utiliza informação específica disponibilizada pelas máquinas fotográficas: aperture e
SubjectDistance.
-
-
-
-
-
Discussão
Tal como é possível observar pela tabela 1, existem diversas formas de agrupamento de
fotografias. Através da última coluna da tabela, verificamos três grupos de abordagens:
baseadas no tempo, baseadas no conteúdo e baseadas nas anotações efectuadas às
fotografias. Cada um destes três grupos apresenta um tipo de agrupamento.
A maioria das abordagens aposta na importância da data/tempo na organização das
fotografias. Neste tipo de perspectiva conseguimos facilmente aproximar a organização
das fotografias digitais à organização normalmente efectuada com as fotografias em
papel. Mas será que a organização por eventos satisfaz suficientemente os utilizadores?
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Para além dos baixos custos da fotografia digital, a representação digital de imagens veio
proporcionar ao utilizador outro tipo de vantagens. [Gargi 2003a] defende a introdução
de um novo conceito de organização fotográfica denominado álbum virtual, que permite
melhorar a organização de fotografias. Em vez de continuarmos a utilizar apenas um tipo
de agrupamento, tal como acontecia com as fotografias em papel onde utilizávamos o
agrupamento por eventos, passamos a dispor de diversas maneiras agrupar e organizar as
fotos. É nesse sentido que será importante conciliar as técnicas utilizadas pelos 3 grupos
de agrupamento, originando um novo tipo de agrupamento. Esse novo tipo de
agrupamento permitirá qualquer um dos agrupamentos demonstrados nas abordagens
descritas, permitindo também a conjunção dos mesmos.
Se pegarmos nas ideias de anotação semântica de [Kuchinsky 1999][Liu 2000a] e nas
ideias de conteúdo de imagem de [Gargi 2003a][Lu 2004] e as inserirmos nas técnicas
utilizadas pelo grupo de detecção de eventos, acrescentamos valor a cada uma das
técnicas quando utilizadas de modo independente. Outra possibilidade de melhoramento
será ainda a introdução das técnicas de recuperação de imagem (CBIR), que possibilitam
o aumento de performance e eficácia na detecção de similaridades.
Sendo que o principal objectivo deste estudo é o desenvolvimento de diversas
possibilidades de agrupamento, teremos que considerar todas as abordagens para uma
possível integração. Obtendo uma integração eficaz das estratégias, conseguiremos um
sistema de geração de diferentes tipos de álbuns virtuais, onde cada um destes álbuns
reflecte uma perspectiva da colecção de fotografias. Assim o utilizador poderá
seleccionar o ou os que mais se enquadram com os seus objectivos.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
CBIR – Content Based Image Retrieval
Dado que a organização e gestão de colecções fotográficas são realizadas para facilitar as
futuras tarefas de pesquisa e procura de fotos, será interessante analisar os mecanismos
utilizados na área da recuperação de imagens (CBIR). O modo como são relacionadas as
imagens entre si na recuperação de imagens, também poderá ser utilizado na organização
das mesmas. Esta abordagem de cálculo de similaridade já é seguida por diversos autores,
alguns dos quais referidos anteriormente.
Dentro da análise de conteúdo de imagem existem 3 grandes categorias de descritores:
açor, a textura, e a forma geométrica. Através destes descritores são definidas métricas de
similaridade, a partir das quais geramos os grupos de fotos.
COR
Das 3 categorias de características low-level referidas, a cor é a característica mais trivial
de analisar, sendo portanto, a característica mais utilizada.
Os Histogramas são a técnica mais conhecida neste tipo de características. Mas a simples
utilização de histogramas não nos fornece informação suficiente. Diversos estudos têm
expandido a utilização dos histogramas a técnicas mais complexas e obtentoras de
descritores de imagem mais precisos. A combinação da cor com o espaço de imagem é
um desses exemplos: utilizar histogramas diferentes para segmentos de imagem
diferentes.
Outra técnica de extracção de descritores de imagem é apresentada em [Alghbari 2006].
Nesta abordagem é gerado o histograma da imagem, através do qual a imagem é
segmentada em regiões de cores diferentes. Através dessas regiões poderemos extrair as
cores representativas da imagem e utiliza-las na comparação das imagens.
Outro estudo [Huang 1997] analisa a similaridade das imagens através da correlação
entre as cores presentes na imagem. Este estudo utiliza a relação espacial entre cores para
caracterizar as imagens e posteriormente definir a similaridade das mesmas.
Wei e al abordam o problema da recuperação de imagens através da combinação das
características da cor e da textura [Wei 2005]. As imagens são segmentadas através da
cor e textura, obtendo regiões pertencentes a objectos e regiões de fundo.
A transformação da imagem do domínio espacial para o domínio da frequência também
tem vindo a ser explorada, obtendo resultados satisfatórios. No seguimento desta
abordagem, Biren N. Shah propõe uma descrição da imagem através da quantização da
cor [Shah 2004]. Biren N. Shah através da representação da frequência da imagem propõe
a selecção das cores representativas da imagem. No seu ponto de vista as cores não
uniformemente distribuídas são as que melhor representam as imagens. O autor utiliza a
variância de cada cor para definir a importância dessa cor na imagem.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Outra técnica que dá ênfase às cores menos dominantes, não desprezando as cores mais
dominantes, é proposta por Vishal Chitkara, Mario A. Nascimento, Curt Mastaller
[Chitkara 2000]. Esta técnica permite a obtenção de uma performance 50% superior à
obtida com o uso de histogramas de cor globais (GCH) e de 25% relativamente ao uso de
color coherence vectors (CCV). Para além da performance esta técnica permite poupar
75% de espaço de armazenamento quando comparado com GCH e 85.5% em relação a
CCV.
Por vezes também nos deparamos com questões de limitação recursos, para tal também
são abordadas técnicas que permitem contornar essas limitações mantendo as capacidades
de análise. Numa dessas abordagens [Smith and Chang 1995] o objectivo passa pela
redução da dimensão do espaço de cores e ao mesmo tempo adquirir a capacidade de
localizar informação de cor no espaço das imagens.
Textura
A textura é uma particularidade da organização das cores das imagens. Sendo uma
particularidade das cores, as texturas permitem obter resultados mais eficazes na
identificação de similaridades. Entre as técnicas de análise de texturas cito aqui algumas:
Em [Saha 2004] Saha et al utiliza a textura como característica descritora de uma
imagem. Através da imagem é construida uma matriz denominada texture co-occurance
matrix que reflecte os padrões de intensidade observados. Após obtida a matriz, poderão
ser calculadas medidas estatísticas como a entropia, energia e texture moments, e utiliar
essas medidas para definir níveis de semelhanças entre imagens.
Outra utilização da textura é apresentada em [Jalaja 2005], onde são descritos métodos
estruturais de análise da textura, visando aproximação à visão humana. São apresentadas
duas caracterizações de padrões locais: a primeira é uma extensão ao espectro de textura
de He e Wang [He and Wang 1990][He and Wang 1991] para uma janela de 5x5 com
novas características estruturais que permitem a captura de padrões locais tais como
faixas verticais e horizontais, alternância de pontos escuros e pontos brilhantes, etc.
A segunda é um método que caracteriza padrões como variações de contrastes em janelas
de 5x5.
No estudo efectuado por Rivaz e Kingsbury [Rivaz 1999], é exposta uma nova complex
wavelet transform que tem como objectivos a aproximação das características da técnica
de Gabor e a derivação de uma métrica de distâncias baseada em hipóteses estatísticas,
que obtenha melhor performance que as métricas usuais. Esta técnica combina velocidade
e precisão, sendo um bom método de extracção de características de texturas.
Formas
A detecção de formas geométricas em imagens é outra estratégia utilizada para a
detecção de objectos semelhantes em imagens diferentes. Esta estratégia é de grande
utilidade, visto que o agrupamento de fotografias é frequentemente efectuado pela
verificação de objectos comuns nas imagens.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Em 1999 Lu e Sajjanhar [Lu 1999] propõem um método de caracterização de imagens
através das formas geométricas dos objectos nelas contidos. Nesta solução, a
representação geométrica é invariante em relação à escala, translação e rotação. No
estudo também é comparada a solução com o método baseado no descritor de Fourrier,
obtendo melhor performance, maior precisão e custos computacionais idênticos.
Outro algoritmo de análise de formas geométricas numa imagem é apresentado em [Nabil
1996]. A estratégia explorada neste paper baseia-se nas relações espaciais entre os
objectos da imagem, utilizando métodos de representação interna de projecção 2D. A
ideia base deste método está no relacionamento das projecções dos diversos objectos da
imagem nos eixos dos x’s e y’s. Uma 2D-PIR (2D-Projection Internal Representation) é
definida como um conjunto de 3 elementos (a,b,c), em que ‘a’ define uma relação
topológica e ‘b’ e ‘c’ definem relações de intervalos nos eixos dos x’s e y’s
respectivamente.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Ideia para Solução
Com o objectivo de proporcionar diferentes métodos de agrupamento, tentarei abranger
técnicas que sejam capazes de identificar fotos tiradas nos mesmos contextos ou em
contextos muito próximos. Seguindo a ideia de [Rodden 2001], que refere a necessidade
de agrupamento de fotos por similaridade, e contrariamente a muitas das abordagens
efectuadas, também terei elevada preocupação com a análise de conteúdo das fotografias.
Enquanto a maioria dos estudos desenvolvidos focalizam o agrupamento das fotos num
determinado conjunto específico de características, neste trabalho tentarei abordar a
maior diversidade de características, para poder permitir ao utilizador parametrizar os
pesos que cada análise terá no processo de agrupamento.
Definido o meu objectivo, tentarei pegar nos benefícios de cada abordagem estudada
(tabela 1) e preencher as lacunas identificadas em cada uma. Tentarei conjugar a maioria
das técnicas implementadas nas diversas abordagens, de modo a originar um sistema que
considere as diferentes perspectivas de associação de imagens.
Após implementadas as técnicas de extracção de características implementarei
mecanismos que facultem ao utilizador a definição do tipo de agrupamento desejado.
Esta personalização dos métodos de agrupamento será efectuada através da atribuição de
pesos distintos para cada tipo de descritor extraído das imagens. Também serão
efectuadas avaliações experimentais que validem o sistema e permitam obter
parametrizações de omissão a atribuir aos tipos de agrupamentos mais comuns.
Sendo assim, a minha solução focará principalmente as características temporais, as
características low-level e a metadata disponível nas fotografias. Diversas técnicas de
CBIR serão consideradas na extracção de descritores de conteúdo das fotografias.
Posteriormente estudarei a detecção de faces para permitir o agrupamento de fotos
através das personagens nelas contidas. As características semânticas serão as
características mais desprezadas, dado que a sua existência requer que o utilizador realize
bastante trabalho contrariando o conceito de automatização de agrupamento.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
Referências
[Alghbari 2006] Zaher Al Aghbari, Ruba Al-Haj. Hill-Manipulation: An effective
algorithm for color image segmentation. Image and Vision Computing. 2006
[Chitkara 2000] Vishal Chitkara, Mario A. Nascimento, Curt Mastaller. Technical Report
TR 00-18, Department of Computing Scince, University of Alberta, Edmonton, Alberta,
Canada. September 2000
[Cooper 2005] Mtthew Cooper, Jonathan Foote, Andreas Girgensohn, and Lynn Wilcox.
Temporal Event Clustering for Digital Photo Collections. ACM Transactions on
Multimedia Computing, Communications and Applications, Vol. 1, No. 3, August 2005,
pages 269-288
[Cooper and Foote 2001] M. Cooper, and J. Foote. Scene Boundary Detection Via Video
Self-Similarity Analysis. Proc. IEEE Intl. Conf. on Image Processing, 2001, pp. 378-381
[Frohlich 2002] D. Frohlich, A. Kuchinsky, C. Pering, A. Don, and S. Ariss.
Requirements for photoware. In Proceedings of the ACM Conference on CSCW. ACM
Press, New York, NY, 166-175, 2002
[Gargi 2003a] Ullas Gargi, Yining Deng and Daniel R. Tretter. Managing and Searching
Personal Photo Collections. Proc. SPIE Storage and Retrieval for Media Databases,
2003, pp.13.21
[Gargi 2003b] Ullas Gargi. Consumer Media Capture: Time-based Analysis and Event
Clustering. Technical Report HPL-2003-165, HP Laboratories, August 2003.
[Girgensohn 2003] Andreas Girgensohn, John Adcock, Matthew Cooper, Jonathan Foot
& Lynn Wilcox. Simplifuing the Management of Large Photo Collections. HumanComputer Intereaction, INTERACT’03. Publicado pelo IOC Press, (c) IFIP, 2003, pp.
196-203
[Graham 2002] A. Graham, H. Garcia-Molina, A. Paepeke, and T. Wino-grad. Time as
the Essence for Photo Browsing Throught Personal Digital Libraries. Proc. Joint Conf. on
Digital Libraries, 2002, pp. 326-335
[He and Wang 1990] D. C. He and Li Wang. A new statistical approach for texture
analysis. Photogrammatic Engineering and Remote Sensing. 56(1):61-66, 1990.
[He and Wang 1991] D. C. He and Li Wang. Texture filters based on texture spectrum.
Pattern Recognition. 24(12): 1187-1195, 1991
[Huang 1997] J. Huang, S. Ravi Kumar, Mandar Mitra, Wei-Jing Zhu, Ramin Zabih.
Image indexing using color correlograms. in Proc. IEEE Computer Vision and Pattern
Recognition Conf., San Juan, PR, June 1997, pp. 762–768.
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
[Huynh 2005] David F. Huynh, Steven M. Drucker, Patrick Baudisch, Curtis Wong.
Time Quilt: Scaling up Zoomable Photo Browsers for Large, Unstructured Photo
Collections. CHI 2005, April 2-7, 2005, Portland, Oregon, USA
[Jain and Dubes 1988] A. Jain and R. Dubes. Algorithms for Clustering Data. Englewood
Cliffs, NJ: Prentice-Hall, 1988, pp. 96-101
[Jalaja 2005] K. Jalaja, Chakravarthy Bhagvati, B. L. Deekshatulu, Arun K. Pujari.
Texture Element Feature Characterizations for CBIR. Geoscience and Remote Sensing
Symposium, 2005. IGARSS '05. Proceedings. 2005 IEEE International. 25-29 July 2005
[Kirk 2006] David S. Kirk, Abigail J. Sellen, Carsten Rother and Kenneth R. Wood.
Understanding Photowork. CHI 2006 Procedings. Collecting and Editing Photos. April
22-27, 2006, Montréal, Québec, Canada.
[Kunchinsky 1999] Allan Kuchinsky, Celine Pering, Michael L. Creech, Dennis Freeze,
Bill Serra, Jacek Gwizdka. Hewlett Packard Laboratories. FotoFile: A Consumer
Multimedia Organization and Retrieval System. CHI’99, Pittsburg PA USA.
[Liu 2000a] Liu Wenyin, Yanfeng Sun, Hongjiang Zhang, Microsoft Research China.
MiAlbum – A System for Home Photo Management Using the Semi-Automatic Image
Annotation Approach. International Multimedia Conference. Proceedings of the eighth
ACM international conference on Multimedia, 2000, Los Angels CA USA
[Liu 2000b] LiuWenyin, Susan Dumais, Yanfeng Sun, HongJiang Zhang, Mary
Czerwinski and Brent Field. A Semi-Automatic image Annotation Strategy and its
Performance Evaluation. Microsoft Technical Report. 2000
[Loui and Savakis 2003] Alexander C. Loui and Andreas Savakis. Automated Event
Clustering and Quality Screening of Consumer Pictures for Digital Albuming. IEEE
Transactions on Multimedia, 2003, vol5, pp. 390- 402.
[Lu 1999] Guojun Lu, Atul Sajjanhar, Region-basedshape representation and similarity
measure suitable for content-basedimage retrieval, Multimedia Syst. 7 (2) (1999) 165–
174.
[Lu 2004] Yang Lu, Tien-Tsin Wong, and Pheng-Ann Heng. Digital Photo Similarity
Analysis in Frequency Domain and Photo Album Compression. ACM International
Conference Proceeding Series, Proceedings of the 3rd international conference on Mobile
and ubiquitous multimedia, 2004
[Nabil 1996] Mohammad Nabil, Anne H. H. Ngu, and John Shepherd. Picture Similarity
Retrieval Using the 2D Projection Internal Representation. IEEE Transactions on
Knowledge and Data Engineering, Vol.8, No.4, pp. 533-539. 1996
Introdução à Investigação
Instituto Superior Técnico - Lisboa, 2006
[Platt 2000] John C. Platt. AutoAlbum: Clustering Digital Photographs using
Probabilistic Model Merging. In Proc. IEEE Workshop on Content-Based Access of
Image and Video Libraries, 2000, pp.96-100
[Platt 2003] John C. Platt, Mary Czerwinski, Brent A. Field. PhotoTOC: Automatic
Clustering for Browsing Personal Photographs. Microsoft Research Technical Report
MSR-TR-2002-17, 2003
[Rodden 2001] K. Rodden, Wojciech Basalaj, David Sinclair, and Kenneth Wood. Does
Organization by Similarity Assist Image Browsing? In Proceedings of the SIGCHI
Conference on Human Factors in Computing Systems 2001, pp.190-197
[Rodden and Wood 2003] K. Rodden and K. Wood. How do people manage their digital
photographs? In Proceedings of the ACM Conference on Human factors in Computing
Systems (CHI). ACM Press, New York, NY, 409-416, 2003
[Saha 2004] Sanjoy Kumar Saha, Amit Kumar Das, and Bhabatosh Chanda. Cbir using
perception based texture and colour measures. 17th International Conference on Pattern
Recognition, pages 985–988, 2004.
[Shah 2004] Biren Shah, Praveen Dhatric, Vijay Raghavan. Using Inverse Image
Frequency for Perception-Based Color Image Quantization. Image Analysis and
Interpretation, 2004. 6th IEEE Southwest Symposium, 28-30 March 2004, pp. 71-75
[Smith and Chang 1995] John R. Smith and Shih-Fu Chang. Singe Color Extraction and
Image Query. Proc. IEEE Int'l Conf. Image Processing, pp. 528-531, 1995.
[Wei 2005] Shikui Wei, Yao Zhao, Zhenfeng Zhu. Meaningful Regions Segmentation in
CBIR. IEEE Int. Workshop VLSI Design & Video Tech, Suzhou, China, May, 28-10,
2005.