README

Structure from Repeating Documents (SfRD) discovers and/or exploits structure in repeating series of documents to facilitate automated creation of research databases in a semi-supervised (and potentially fully unsupervised) manner, even in the presence of degradations and nuisance features. SfRD is inspired by Structure from motion (SfM) methods for reconstructing 3D structures from 2D images.

Usage

Install this package and the nafrec library (e.g. pip install nafrec[gpu] or nafrec[cpu]), then run the structuralizer command for help. User documentation will be added as the project matures.

Text line detection and recognition is done by nafrec. Any command line option that structuralizer does not recognize is passed on to nafrec, so for example

structuralizer --input_directory ... --output_directory ... --annotation_directory ... \
    --detection_model_path det.pth \
    --recognition_model_path trocr --processor_path trocr \
    --cyrillic_recognition_model_path cyr --cyrillic_processor_path cyr \
    --script_classification_model_path script.pt \
    --device cuda --gpu_ids 0 1 --tile_size 768

uses a script classifier to send each line to the latin or the cyrillic recognition model. The cyrillic model is optional: with only one recognition model configured, all lines go to it. See nafrec --help for all options. The --disregard_regions/--disregard_lines options of SfRD itself are unchanged, and with both of them no detection model is needed. --print_recognized prints each recognized text line while processing. --cpu_processes sets the number of SfRD CPU workers; nafrec starts and manages the model (GPU) workers.

If you don't know what the templates are in your collection, consider trying the --suggest_templates feature. The default (or a similarly strict) config is recommended for template finding.

Motivation

Traditional image registration methods can be used to align digitized forms and index cards onto a single annotated template. However, image registration sometimes fails when the features are not sufficiently invariant to changing imaging conditions or there are too many nuisance features relative to template features, such as written content, degradations or minor template revisions in the documents. Additionally, traditional descriptor-based feature matching often cannot reliably output paired keypoints for fitting more complex transformations or deformations than a homography/perspective transformation and requires robust estimation methods such as RANSAC and small degrees of freedom when the feature matching is unreliable. In archives, utilizing the full series of repeating documents enables us to reliably separate stable template features from the per-page variable content.

Viewing the collection of documents as a graph allows us to produce a chain (track) of inlier features and the resulting transformations between document pairs from less degraded to more degraded, as long as intermediate stages of degradation exist along the way that can still be aligned pairwise. We use the graph of alignment relationships to combine evidence for more reliable keypoint locations (step 5) and to transform keypoint locations into virtual locations in the template even when they are not visually present in the annotated copy, for example in the case of templates which had later revisions to add sections. In the case of multiple possible templates, we select the best matching template for each document by finding the shortest paths in the graph.

Theoretical outline

1. Feature detection: We use a feature detector (SIFT) to detect visual features (keypoint, descriptor) on each page.

2. Prefiltering: We use a very cheap method to select the k=12 nearest neighbors (including possibly the template images) for each page, based on principal components or perceptual image hashes.

3. Pairwise alignment: For each page and its k nearest neighbors, we try to align them (solve for the transformation matrix between the pairs) using a FLANN matcher and the RANSAC method. The result is a graph with edges (transformations) between neighboring pages, where the edge weight is defined using the inlier ratio as $$-\ln(\frac{\text{inliers}}{\text{matches}})+0.05$$ (0.05 is a small hop penalty).

4. Shortest path to root: We traverse the shortest paths of the graph with Dijkstra's algorithm considering every possible root (template page) as a starting point, chaining each alignment transformation along the way. If we disregard the hop penalty and consider the inlier ratio as a proxy for the probability of the transformation being correct, this is approximately maximizing for the joint probability of the chain of transformations being correct, because additions in path length on the log scale are multiplicative on the original probability scale. This also simultaneously selects which root the page tentatively belongs to among all the competing roots (the owner). The result is a dictionary {pageid: transform_to_nearest_root} and {pageid: owner_root_id}.

5. Feature tracking: For each root, we use a union-find data structure to build tracks (sets) out of features. This combines features that are inliers with each other into one track (across pages). Then, we transform all of the feature keypoints with an available transformation into the current root frame (from the dictionary from the previous step), and compute a canonical keypoint location in the root frame by taking the median. The canonical keypoint location should have higher accuracy since it combines location estimates from multiple pages. To increase reliability, we use a minimum support threshold to select only tracks with at least a certain number of features/pages that have a transformation to the root.

Importantly, to be transformed into the root frame and become a canonical keypoint, we do not actually need to be able to detect the feature on the root page itself using SIFT. Even features only detected on other pages will be propagated to the root! This means we greatly expand the number of keypoints that are able to be matched between the root and other pages. Increasing the minimum support threshold will tend to select for reliable features that are inliers across several pages (temporally/serially stable features), removing nuisance features such as written markings that change per page.

6. Final alignment and root selection: We align all (possible) pages to each root with RANSAC, using the previously detected keypoints on the page and the calculated canonical keypoints in the root. The matching is done with the tracksets found in the previous step instead of FLANN. The resulting transformation should be higher quality than simply chaining multiple transformations, because we recalculate the transformation between actual SIFT keypoint detections on the page and the refined canonical keypoints on the root. We select the root with the most inliers as the final alignment target, in the case of a tie we choose the root with the lower mean residual between aligned keypoints.
7. Fallback: For any pages where the previous step failed, we fall back to using the chained transformations from the paths to the nearest roots in step 4. Chaining will propagate errors from multiple alignments. It is still possible that some pages are left unaligned (these are usually noise pages that we can discard)
8. Optional: Correct deformation: With the stable visual features identified in steps 1-6, it is optionally supported to fit a thin plate spline mapping from the template to each aligned page. This will deform the annotated example to more closely match complex deformations on the page that could not be corrected by the affine transformation alone. When using this feature, it is recommended to relax certain alignment parameters (see tolerant_config.toml).
9. Optional: Refine boundaries: Convert results into axis-aligned bounding boxes and use an exact or heuristic solver to shift the bounding box edges away from Canny edge pixels in the image. The objective function penalizes box contraction more than it does box expansion while ensuring no overlaps in the final result.

FAQ

Isn't SIFT outdated, why not use neural networks?

SIFT is probably close to state of the art for feature detection in the case of 2D documents with small transformations (digitized with copy stands), which is our case. RANSAC is state of the art for finding the transformation, because we have small degrees of freedom for the camera so directly solving for the transformation matrix should converge to the optimal mathematical solution. Most neural methods are built to handle more complex 6DOF transformations (moving and rotating freely), and we don't need that extra capability in return for much higher computational cost.

Rather than doing zero-shot form field detection with neural networks, we choose to take advantage of the repeating structure in an archived series. By choosing the older but faster methods for feature detection and alignment, we can afford to explore the graph of multiple chained transformations instead of just the direct transformation between the root and another page. Also, SIFT has optimized C++ implementations for CPU.

By analogy, most structure from motion libraries use mathematical optimization/solve for transformations; neural methods do not provide meaningful improvement even on 3D benchmarks in that case. The magic is in how the detected features are processed rather than in the detector itself.

MST vs. shortest paths

Using e.g. Prim's algorithm for traversing the MST from the root would give the highest quality paths to the root as defined by inlier count, with no regard for the number of transformations chained in the process, apart from being part of the MST (no cycles allowed). With Dijkstra's algorithm for finding shortest paths, the tradeoff between path length and edge quality can be managed with an appropriate edge weighting scheme. When we view the inlier ratio as a proxy for the probability of the transformation being correct, we are trying to find the path with maximum probability (relevant leetcode problem).

Prefiltering tradeoffs

Prefiltering may be sensitive to the chosen PCA parameters and image size or the hash length in the case of pHash, and the value of k. Some more sophisticated methods could be explored. However, the default PCA-based method seems to work fairly well at balancing between having a little but not too much rotational/translational invariance. Even though SIFT features are invariant to many transformations, they are not perfect and thus pairwise alignment will benefit from a prefiltering approach which is somewhat sensitive to transformations. The k parameter can be increased to reduce the impact of prefiltering.

TODO

A fully unsupervised mode is planned, where pages are clustered using a more accurate page embedding, then pages are aligned to the centroid of each page cluster, and finally field embeddings are calculated and clustered to link the same field across pages. Output will be a table with a generic unnamed header such as (field1, field2, field3).