💻 computer science

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

This paper introduces Bag of Bags (BoB), an adaptive visual vocabulary method that replaces global codebooks with fragment-specific local vocabularies to significantly improve the retrieval of Cairo Genizah manuscript fragments by achieving a 6.1% relative increase in top-1 accuracy over state-of-the-art Bag of Words baselines.

Original authors: Sharva Gogawale, Gal Grudka, Daria Vasyutinsky-Shapira, Omer Ventura, Berat Kurar-Barakat, Nachum Dershowitz

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sharva Gogawale, Gal Grudka, Daria Vasyutinsky-Shapira, Omer Ventura, Berat Kurar-Barakat, Nachum Dershowitz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a massive, centuries-old puzzle. The pieces aren't cardboard; they are ancient, torn, stained, and scattered fragments of handwritten manuscripts from the Cairo Genizah (a historic storage room for Jewish texts).

Your job is Manuscript Join Retrieval: You pick up one torn piece of paper and ask, "Which other pieces in the world's libraries originally came from the same book?"

This is incredibly hard because:

The pieces are damaged: Some are missing corners, some are faded, and some are just smudges.
The handwriting is subtle: Two pieces might look similar because they are both old and yellowed, but they were written by different people. Conversely, two pieces from the same book might look different because one was written in bright light and the other in the dark, or because the ink faded differently.

The Old Way: The "Global Dictionary" (Bag of Words)

For a long time, computer scientists tried to solve this using a method called Bag of Words (BoW).

The Analogy: Imagine every manuscript fragment is a bag of marbles. In the old method, everyone agrees on one giant, global dictionary of marble colors (e.g., "Red," "Blue," "Green," "Speckled").

You dump your fragment's marbles into the bag.
You count how many "Red" marbles you have, how many "Blue," etc.
You compare your count to everyone else's.

The Problem: This is too blunt.

If two fragments have the same number of "Red" marbles, the computer thinks they are identical. But maybe one fragment has "Red" marbles arranged in a perfect circle, and the other has them scattered randomly. The pattern matters, not just the count.
If a fragment is damaged and missing its "Blue" marbles, the computer might think it's a totally different book, even if the remaining "Red" marbles match perfectly.
It forces every unique, messy manuscript to fit into the same rigid box, losing the specific "fingerprint" of the writer.

The New Way: "Bag of Bags" (BoB)

The authors of this paper propose a smarter, more flexible approach called Bag of Bags (BoB).

The Analogy: Instead of using one giant dictionary for everyone, every single fragment gets its own custom dictionary.

Here is how the system works, step-by-step:

The Microscope (Connected Components):
First, the computer zooms in on the fragment and cuts out every single letter or ink blot it can find. Think of these as individual "character patches."
The Translator (Sparse Autoencoder):
The computer looks at each patch and translates it into a mathematical "fingerprint" (an embedding). It's like turning a handwritten letter into a unique code that captures its shape, slant, and texture.
The Custom Dictionary (Local Vocabulary):
This is the magic step. Instead of forcing these fingerprints into a global list, the computer looks at just this one page and groups similar fingerprints together.
- Example: On this specific page, it might find that the writer has a unique way of writing the letter "A" that looks like a triangle, and another way that looks like a circle.
- It creates a mini-dictionary just for this page: "Triangle-A" and "Circle-A."
- It also counts how many of each there are (the "mass").
The Matchmaker (Set-to-Set Distance):
Now, to see if two fragments belong together, the computer doesn't just compare counts. It compares the custom dictionaries.
- It asks: "Does Fragment A's 'Triangle-A' match Fragment B's 'Triangle-A'?"
- It uses a clever math trick called Chamfer Distance. Think of it like a game of "closest match." If Fragment A has a "Triangle-A" and Fragment B has a "Triangle-A," they get a point. If Fragment A has a "Circle-A" but Fragment B is missing it (because it's torn), the computer doesn't punish them too hard. It just says, "Okay, we found a match for the triangle, that's good enough."

Why is this better?

It handles damage: If a piece is torn and missing half its letters, the old method panics. The new method says, "No problem, we still have the letters we do have, and they match perfectly."
It catches the "Hand": It focuses on the specific style of the writer on that specific page, rather than just generic features shared by all old papers.
It's efficient: The authors built a two-stage system. First, it quickly scans the whole library with the "old method" to find a shortlist of 30 candidates. Then, it uses the super-smart "Bag of Bags" method to rank those 30 and pick the winner. This makes it fast enough to use on huge collections.

The Results

When they tested this on the Cairo Genizah fragments:

The old method (BoW) got the right answer about 74% of the time.
The new method (BoB-Chamfer) got the right answer 78.4% of the time.

That might sound like a small number, but in the world of ancient manuscripts, where every piece is unique and damaged, that is a huge leap forward. It means scholars can now automatically reconnect fragments that were separated for centuries, helping to reconstruct lost history much faster than human experts could do alone.

In a nutshell: Instead of forcing every ancient page to speak the same language, the "Bag of Bags" method learns the unique dialect of each page and then finds the other pages that speak the same dialect.

1. Problem Statement

The paper addresses the challenge of manuscript join retrieval within the context of the Cairo Genizah, a vast collection of fragmented medieval manuscripts (11th–19th centuries) dispersed across global libraries.

The Goal: Given a query image of a manuscript fragment, the system must retrieve other fragments that originated from the same physical manuscript (a "join").
The Challenge:
- Fragmentation: Fragments are often damaged, incomplete, stained, or truncated.
- Subtle Signals: Fragments from the same manuscript share specific handwriting styles, while fragments from different manuscripts may look globally similar due to shared aging, background texture, or degradation.
- Limitations of Standard Methods: Traditional Bag of Words (BoW) approaches map all images to a single global visual codebook. This global quantization erases image-specific handwriting style signals. Two fragments with identical word frequencies but different geometric character distributions are treated as identical (distance zero), while fragments from the same manuscript with different lighting or layouts may be treated as distinct.

2. Methodology: Bag of Bags (BoB)

The authors propose Bag of Bags (BoB), a novel image-level representation that replaces the global codebook with fragment-specific vocabularies of local visual words.

A. Pipeline Overview

Character-Anchored Patch Extraction:
- Images are binarized (Otsu thresholding).
- Connected Component Analysis isolates individual character instances.
- Filtering: Components are filtered by area (300–3000 pixels) to remove noise and large merged blobs.
- Normalization: Components are scaled to a 64×64 patch while preserving aspect ratio (zero-padding), ensuring geometric integrity of Hebrew letterforms.
Sparse Convolutional Autoencoder:
- A sparse autoencoder ( $f_\theta$ ) encodes the normalized patches into a 128-dimensional latent space.
- Training Objective: Minimizes Mean Squared Error (reconstruction) + $L_1$ sparsity penalty ( $\lambda = 10^{-5}$ ). This forces the network to learn sparse, discriminative features for character strokes.
Page-Adaptive Vocabulary Construction:
- Instead of mapping all patches to a global dictionary, BoB performs $K$ -means clustering per page on the set of embeddings extracted from that specific fragment.
- This results in a "bag" of local prototypes (centroids) and their corresponding masses (cluster populations) unique to that fragment.
- Representation: $B(I) = \{(\mu_a, \pi_a)\}_{a=1}^K$ , where $\mu_a$ is the prototype and $\pi_a$ is the mass.

B. Distance Metrics (Set-to-Set Matching)

The similarity between two fragments is calculated as the distance between their local vocabularies:

BoB-Chamfer (Soft Matching):
- Computes the sum of nearest-neighbor distances in both directions.
- Advantage: Does not enforce a strict one-to-one mapping. It rewards partial overlap, which is crucial for damaged fragments where only a subset of character styles may be present in both.
- Performance: Empirically the strongest metric.
BoB-Hungarian (Strict Assignment):
- Enforces a strict one-to-one bipartite assignment using the Hungarian algorithm.
- Satisfies metric properties (triangle inequality) but is less robust to partial damage.
BoB-OT (Mass-Weighted Optimal Transport):
- Incorporates cluster population weights ( $\pi$ ) into the transport plan.
- Theoretical Guarantee: The authors prove that the deviation between BoB-OT and full component-level Optimal Transport is bounded by the sum of the $K$ -means quantization errors ( $\epsilon_I + \epsilon_J$ ). This provides a formal approximation guarantee.

C. Two-Stage Retrieval Pipeline

To handle large-scale collections where computing an $N \times N$ BoB distance matrix is expensive:

Stage 1 (Candidate Generation): Use a fast BoW-Cosine baseline to retrieve a shortlist (e.g., top 30 candidates).
Stage 2 (Reranking): Apply the computationally heavier BoB-OT only to the shortlist.

Complexity: Reduces online cost to $O(M \cdot K^3)$ , independent of the total gallery size $N$ .

3. Key Contributions

Bag of Bags (BoB) Representation: A shift from global quantization to page-adaptive local vocabularies, preserving specific handwriting styles that global codebooks lose.
Robust Distance Metrics: Introduction and evaluation of Chamfer, Hungarian, and Mass-Weighted OT distances for set-to-set matching, demonstrating that soft nearest-neighbor matching (Chamfer) is superior for partially damaged documents.
Theoretical Guarantee: A formal proof bounding the approximation error of the mass-weighted BoB-OT variant relative to full component-level Optimal Transport.
Efficient Scalability: A two-stage pipeline that balances high retrieval accuracy with computational feasibility for large archives.
Comprehensive Ablation: Detailed analysis showing that gains come from the adaptive vocabulary structure (clustering + set matching) rather than just the encoder quality.

4. Results

Evaluated on a benchmark of 287 Cairo Genizah fragments (100 join clusters):

Performance:
- BoB-Chamfer achieved Hit@1 = 0.784 and MRR = 0.841.
- This outperformed the strongest baseline, BoW-RawPatches-χ2 (Hit@1 = 0.739, MRR = 0.800), representing a 6.1% relative improvement in top-1 accuracy.
- BoB significantly outperformed pooling baselines (MeanPool/MaxPool) and global codebook variants (BoW-centroids), proving the value of page-specific clustering.
Ablation Insights:
- Vocabulary Size ( $K$ ): Performance peaked at $K=32$ (though $K=20$ was used for the main results to balance cost).
- Sparsity: Enabling $L_1$ sparsity in the autoencoder improved all metrics.
- Normalization: Preserving aspect ratios during patch extraction was critical; isotropic resizing degraded performance.
Computational Cost:
- Precomputed BoB lookup is effectively free (<0.01ms).
- The two-stage pipeline (BoW $\to$ BoB-OT) costs ~11ms per query and scales independently of gallery size.

5. Significance

Paleographic Analysis: The work demonstrates that for historical document retrieval, modeling how a page organizes its local visual modes is more effective than forcing all pages into a single shared vocabulary.
Handling Damage: The "Bag of Bags" approach, particularly with Chamfer distance, is uniquely suited for the partial-overlap nature of damaged manuscripts, where strict one-to-one matching fails.
Broader Applicability: The methodology extends beyond Genizah retrieval to any computer vision task involving fine-grained recognition where instances are globally similar but differ in subtle, local, or partial visual cues (e.g., biological specimens, material defects).
Practical Deployment: The proposed two-stage pipeline offers a viable path to applying advanced deep learning retrieval methods to massive, unstructured historical archives (250k+ fragments) without prohibitive computational costs.