Orientador: Anderson de Rezende RochaDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Devido à grande quantidade de imagens compartilhadas na internet, rastrear a propagação e evolução de seu conteúdo se tornou um problema de crescente importância. Recentemente, diversos trabalhos têm se preocupado com a modelagem de relações de parentesco existentes entre duplicatas próximas em um conjunto de imagens. Duas imagens possuem uma relação de parentesco se uma delas pode ser obtida a partir da aplicação de transformações na outra. Entretanto, essa não é a única forma de parentesco que pode existir entre imagens. Uma imagem pode ser uma composição criada através da combinação de informação existente em duas ou mais imagens fonte, estabelecendo uma relação entre a composição e tais fontes. Chamamos de Filogenia de Múltiplos Pais o problema de identificar tais relações em um conjunto contendo subconjuntos de duplicatas próximas de composições e imagens fonte. Para lidar com esse problema, apresentamos nessa dissertação uma solução com três passos para o problema: (1) separação de grupos de duplicatas próximas; (2) classificação dos relacionamentos entre grupos; (3) identificação das imagens usadas na criação da composição original. Além disso, estendemos tal arcabouço introduzindo melhorias fundamentais, como, por exemplo, melhores formas de identificar quando duas imagens compartilham conteúdo, além de melhores maneiras de comparar tal conteúdo. Avaliamos as abordagens propostas em um cenário contendo três subconjuntos de duplicatas próximas: um pertencente à composição e dois pertencentes às imagens usadas para criá-la. Três bases de dados foram desenvolvidas para este trabalho, duas contendo composições criadas automaticamente e uma com composições realistas feitas por um artista profissional. Comparamos o arcabouço original com o estendido utilizando métricas quantitativas, estabelecidas com o intuito de avaliar a precisão na reconstrução das filogenias e na identificação das relações de múltiplo parentesco. Por fim, discutimos outras particularidades dos métodos propostos, como a importância de uma reconstrução precisa das filogenias, além de como composições mais complexas afetam negativamente a precisão do métodoAbstract: Due to the large amount of images shared on the web, tracking the spread and evolution of their content became an increasingly important problem. Recently, several works have been concerned with modeling the parenthood relationships between near duplicates in a set of images. Two images share a parenthood relationship if one is obtained by applying transformations to the other. However, this is not the only form of parenting that can exist among images. An image might be a composition created through the combination of the semantic information existent in two or more source images, establishing a relationship between the sources and the composite. We name as Multiple Parenting Phylogeny the problem of identifying such relationships in a set containing near-duplicate subsets of source and composition images. To tackle this problem, we present in this dissertation a three-step solution: (1) separation of near-duplicate groups; (2) classification of the relations between the groups; and (3) identification of the images used to create the original composition. Moreover, next we extend upon this framework by introducing key improvements, such as better identification of when two images share content, and improved ways to compare this content. We evaluate the proposed approaches in a scenario containing three subsets of near duplicates: one belonging to the composition image, and two to the source images used to create it. Three datasets were developed for this work, two with automatically created compositions and one of realistic, professionally-made compositions. The original and extended frameworks are compared by means of quantitative metrics established for evaluating the accuracy in reconstructing phylogenies and finding multiple parenting relationships. Finally, we discuss some particularities of the framework, such as the importance of an effective reconstruction of phylogenies and how more complex compositions can negatively affect the precision of the methodMestradoCiência da ComputaçãoMestre em Ciência da Computação