Deep learning-based reconstruction of shredded documents

Abstract

ABSTRACT: The reconstruction of shredded documents is a relevant task in various domains, such as forensic investigation and history reconstruction. As an alternative for the manual reconstruction, researchers have been investigating ways to perform (semi-)automatic digital reconstruction. Despite the several works on this topic, dealing with real-shredded data is a very sensitive issue in the current literature. Two research directions are addressed in this thesis to face this scenario: properly evaluating the fitting of shreds (the bulk of this work) and integrating the human into the reconstruction process. Regarding the fitting (compatibility) evaluation, it was verified that traditional pixel- based approaches are not robust to real shredding, while more sophisticated techniques compromise significantly time performance. This thesis presents two deep learning self- supervised approaches that have achieved state-of-the-art accuracy in more realistic/complex scenarios involving several real-shredded documents where the shreds are mixed (multi-page reconstruction or multi-reconstruction). The first approach models the compatibility evaluation as a two-class (valid or invalid) pattern recognition problem. The second approach, based on deep metric learning, proposes decoupling feature extraction from compatibility evaluation to improve scalability (time performance) for large reconstruction instances. Human interaction is explored to improve the accuracy of automatic methods. A critical issue regarding this topic is that the proposed methods do not scale well for large instances (real scenario), either because the user has the entire responsibility of arranging the shreds, or because he/she has to visualize the reconstruction and designate the shreds to be analyzed. In face of this challenge, we propose a human-in-the-loop framework that automatically selects potential mistakes (wrong pairings) in the solution for user analysis.

RESUMO: A reconstrução de documentos fragmentados é uma tarefa importante em diversas situações, tais como na investigação forense e na reconstrução de fatos históricos. Como alternativa ao processo manual, pesquisadores têm desenvolvido métodos para reconstruir documentos (semi-)automaticamente no domínio digital. Apesar dos diversos trabalhos na área, tratar adequadamente dados reais obtidos com uso de máquinas fragmentadoras é um problema crítico na literatura. Neste contexto, duas direções de pesquisa foram abordadas nesta tese: a avaliação robusta de compatibilidade entre os fragmentos, que é o foco do nosso trabalho, e a interação homem-máquina no processo de reconstrução. Com respeito à avaliação de compatibilidade, verificou-se que as técnicas tradicionais baseadas em análise de pixel não são robustas à fragmentação real, enquanto técnicas mais sofisticadas comprometem significativamente a eficiência (tempo de processamento). Esta tese propõe duas abordagens baseadas em deep learning para cenários mais complexos/realísticos envolvendo, além da fragmentação mecânica, a mistura de fragmentos provenientes de diversas páginas de documentos (multi-page reconstruction ou multireconstruction). A primeira abordagem modela a avaliação de compatibilidade como um problema de reconhecimento de padrões envolvendo duas classes (válida e inválida). A segunda abordagem, baseada no paradigma deep metric learning, propõe separar as etapas de extração de características e avaliação de compatibilidade para melhor eficiência na reconstrução de maiores instâncias de reconstrução. A interação humana é explorada num segundo momento para se obter maior acurácia comparada aos métodos automáticos. Em relação a este tema, um fator crítico é que os métodos propostos na literatura não escalam eficientemente com o aumento do número de fragmentos (cenário mais realístico). Isso se deve ao fato do usuário ser totalmente responsável pela organização dos fragmentos, e/ou porque ele precisa visualizar todo o documento reconstruído para designar fragmentos a serem analisados. Diante deste desafio, propusemos um framework que explora a interação homem-máquina e que automaticamente seleciona potenciais erros na solução (pareamentos incorretos) para serem analisados pelo usuário.