Bag of Bags: Adaptive Visual Vocabularies for Genizah Join Image Retrieval

1. O Problema: Recuperação de "Joins" em Manuscritos

O foco do trabalho é a recuperação de "joins" (junções) em fragmentos de manuscritos, especificamente da Genizá do Cairo.

• Contexto: A Genizá do Cairo contém milhares de fragmentos de manuscritos medievais (séculos XI-XIX) escritos em hebraico, aramaico e judeu-árabe, dispersos por dezenas de instituições.
• Desafio: O objetivo é identificar quais fragmentos pertenciam originalmente ao mesmo manuscrito físico (códice ou rolo), mesmo que estejam danificados, incompletos ou manchados.
• Dificuldade Computacional:
  • Fragmentos do mesmo manuscrito podem compartilhar apenas padrões visuais sutis de caligrafia.
  • Fragmentos de manuscritos diferentes podem parecer globalmente similares devido a texturas de fundo, envelhecimento ou degradação.
  • Métodos tradicionais de recuperação de imagens (como Bag of Words - BoW) falham porque utilizam um vocabulário visual global compartilhado. Isso perde informações específicas de cada página (estilo de escrita local) durante a quantização, tratando fragmentos com estilos geométricos diferentes como idênticos se tiverem frequências de palavras visuais similares.

2. Metodologia: Bag of Bags (BoB)

Os autores propõem uma nova representação chamada Bag of Bags (BoB), que substitui o código global por vocabulários visuais específicos para cada fragmento.

O pipeline funciona em três etapas principais:

1. Extração de Patches Ancorados em Caracteres:

   • As imagens são binarizadas e submetidas a análise de componentes conectados para isolar caracteres individuais.
   • Filtros de área removem ruído e blocos de texto massivos.
   • Cada componente é normalizado (mantendo a proporção de aspecto) para um patch de 64x64 pixels.

2. Codificação via Autoencoder Esparsa:

   • Um autoencoder convolucional esparsa é treinado para codificar esses patches em um espaço latente (vetores de 128 dimensões).
   • O treinamento utiliza uma função de perda que combina erro de reconstrução e uma penalidade de esparsidade ($L_1$) no espaço latente, garantindo que os recursos aprendidos sejam discriminativos e eficientes.

3. Criação de Vocabulário Local (O "Saco de Sacos"):

   • Em vez de agrupar todos os patches do dataset em um único dicionário global, o BoB agrupa os embeddings de cada página individualmente usando K-Means.
   • Isso gera um conjunto de protótipos locais (o "saco") para cada imagem, representando os estilos de escrita específicos daquela página.
   • Cada protótipo tem um "massa" (peso) baseada na frequência de componentes que o originaram.

4. Medidas de Distância (Set-to-Set):
   A similaridade entre dois fragmentos é calculada comparando seus vocabulários locais (conjuntos de protótipos) através de três abordagens:

   • BoB-Chamfer: Encontra o vizinho mais próximo para cada protótipo independentemente. É robusto a danos parciais (não penaliza protótipos sem correspondência).
   • BoB-Hungarian: Força uma atribuição um-para-um estrita (algoritmo húngaro). Garante propriedades métricas formais.
   • BoB-OT (Transporte Ótimo com Massa): Incorpora a frequência real dos componentes (massa) no cálculo de distância. Possui uma garantia teórica de aproximação em relação ao transporte ótimo de nível de componente completo.

3. Contribuições Principais

• Representação Bag of Bags (BoB): Uma abordagem que substitui o código global por vocabulários adaptativos por página, preservando a estrutura local da caligrafia.
• Análise de Distâncias: Demonstração empírica de que a correspondência de vizinhos mais próximos "suave" (Chamfer) é mais robusta para fragmentos danificados do que atribuições rígidas, embora o OT com massa ofereça garantias formais.
• Pipeline de Duas Etapas: Uma solução prática para grandes coleções onde o cálculo de matriz completa é caro. Usa um BoW rápido para gerar uma lista curta de candidatos e aplica o BoB-OT apenas para reclassificação (reranking). Isso reduz o custo online para $O(M \cdot K^3)$, independente do tamanho da galeria.
• Garantia Teórica: Prova formal de que a distância BoB-OT aproxima o transporte ótimo de nível de componente com um erro limitado pela qualidade da quantização K-Means dentro da página.

4. Resultados Experimentais

O método foi avaliado em um conjunto de dados de benchmark da Genizá do Cairo (287 imagens, 100 clusters de junção).

• Desempenho Superior: A variante BoB-Chamfer alcançou os melhores resultados:
  • Hit@1: 0.784 (vs. 0.739 do melhor baseline BoW).
  • MRR (Mean Reciprocal Rank): 0.841 (vs. 0.800 do baseline).
  • Isso representa uma melhoria relativa de 6.1% na precisão top-1 em relação ao baseline mais forte (BoW-RawPatches-χ2).
• Ablação:
  • O uso de esparsidade no autoencoder e a normalização que preserva a proporção de aspecto foram cruciais para o desempenho.
  • O tamanho do vocabulário local ($K$) mostrou sensibilidade, com $K=32$ sendo ótimo no subset de teste, embora $K=20$ tenha sido usado para o pipeline principal.
• Custo Computacional: O pipeline de duas etapas (BoW + BoB-OT) oferece um compromisso prático, mantendo alta precisão com custo computacional viável para grandes coleções.

5. Significado e Impacto

Este trabalho é significativo para a paleografia digital e a recuperação de documentos históricos por várias razões:

1. Superação do BoW Global: Demonstra que forçar todos os manuscritos em um único vocabulário visual é prejudicial para a análise fina de estilos de escrita. A adaptação por página captura nuances que métodos globais perdem.
2. Robustez a Danos: A abordagem baseada em conjuntos (set-to-set) com correspondência parcial (Chamfer) lida naturalmente com a realidade física dos fragmentos da Genizá, onde partes do texto podem estar faltando.
3. Escalabilidade: A proposta de reclassificação em duas etapas permite que a tecnologia seja aplicada a coleções massivas (centenas de milhares de fragmentos), superando a barreira do custo computacional de métodos de transporte ótimo.
4. Generalização: A ideia de "vocabulários adaptativos por imagem" e correspondência de conjuntos pode ser aplicada a outros problemas de visão computacional que envolvem evidências visuais parciais, ruidosas e heterogêneas, como reconhecimento fino de granulação.

Em resumo, o Bag of Bags oferece um avanço metodológico ao tratar a recuperação de manuscritos como um problema de correspondência de estruturas locais adaptativas, em vez de apenas contagem global de características, resultando em uma recuperação de junções significativamente mais precisa.