# Text Reading Order in Uncontrolled Conditions by Sparse Graph Segmentation

> A lightweight multi-task GCN on a beta-skeleton graph predicts column-wise vs. row-wise layout patterns and paragraph boundaries, then recovers global reading order via a hierarchical cluster-and-sort algorithm. Language-agnostic and small enough to run on mobile devices.

- Authors: Hunter Heidenreich
- Published: 2026-04-02
- Paper: Preprint (arXiv) <https://arxiv.org/abs/2305.02577>
- Source: Bevaya Labs, <https://labs.bevaya.ai/>

---


## TL;DR

Wang et al. (Google Research) reframe text reading order prediction as a graph segmentation task rather than sequence generation. A sparse, $\beta$-skeleton-based multi-task GCN predicts whether each text line belongs to a column-wise or row-wise reading pattern and whether neighboring lines share a paragraph. A deterministic hierarchical cluster-and-sort post-processing step then converts those local predictions into a global reading order. The resulting model has 267K parameters, is language-agnostic, and generalizes from English training data to seven other languages.

## What kind of paper is this?

**Dominant:** $\Psi\_{\text{Method}}$: The headline contribution is an algorithm combining a sparse-graph GCN with a deterministic cluster-and-sort post-processing stage. The paper introduces the architecture, the labeling scheme for deriving pattern labels from annotations, the hierarchical clustering algorithms, and ablations validating the design choices.

**Secondary:** none. The internal annotated dataset is not released and is used solely for validation.

## What is the motivation?

Reading order is a critical output of any OCR pipeline. Downstream tasks from text selection to structured document understanding with LayoutLM-family models depend on correctly ordered text. The difficulty is not uniform: a column of newsprint text is easily sorted by y-coordinate, but a restaurant menu photographed at an oblique angle with interleaved dish names and prices requires understanding two-dimensional relational structure.

Prior approaches fall into two failure modes:

- **Rule-based methods** such as XY-Cut and topological sort based on bidimensional relations work well within a narrow domain but fail out-of-distribution. They commit to a single layout pattern (column-wise or row-wise) globally and cannot handle mixed documents.
- **Sequence-learning methods** such as the graph encoder plus pointer-network decoder in Li et al. (ECCV 2020) or the LayoutLM-based LayoutReader suffer from $O(n^2)$ time complexity and accuracy degradation as input length grows, because the fully-connected attention conflates local layout signals with irrelevant global context.

The authors identify that most real-world reading order sequences follow one of two local patterns (column-wise or row-wise) and that deciding which pattern applies to any given text region is a local rather than global problem. This observation motivates reframing the task as node classification on a sparse neighborhood graph.

## What is the novelty?

### Sparse-graph formulation

Rather than building a fully connected graph over all text lines, the model uses a $\beta$-skeleton graph [Kirkpatrick and Radke, 1985] whose edges connect only spatially neighboring text-line boxes. This keeps graph-convolution complexity linear in the number of lines, $O(n)$, and provides a natural set of edge bounding boxes for RoI pooling.

### Multi-task GCN with edge RoI pooling

The GCN is an MPNN variant with weight-sharing convolutions. It has two output heads:

$$\hat{y}\_{\text{node}} \in \\{\text{col}, \text{row}\\}$$

for reading order pattern per line, and

$$\hat{y}\_{\text{edge}} \in \\{\text{same-para}, \text{different-para}\\}$$

for paragraph membership. Image features are extracted by a MobileNetV3-Small backbone (144K of the model's 267K parameters) at 512 $\times$ 512 resolution and pooled over *edge bounding boxes* (the minimum containing box of each connected pair of text-line boxes) rather than node boxes. An ablation (Table 2 in the paper) shows that node-box RoI pooling slightly degrades accuracy relative to using no image features at all, whereas edge-box RoI pooling provides a consistent improvement. The interpretation is that the discriminative visual signals (separator lines, color boundaries) live between text boxes rather than inside them.

Spatial node features encode $x, y$ corner coordinates multiplied by rotation coefficients $\cos \alpha$ and $\sin \alpha$, making the model rotation-aware from the input representation.

### Hierarchical cluster-and-sort post-processing

After the GCN outputs per-line pattern labels and per-edge paragraph membership, three deterministic algorithms convert local predictions into a global traversal order:

1. **Algorithm 1 (Hierarchical Clustering):** Lines are grouped into paragraphs via edge predictions; paragraphs inherit a pattern via majority vote; same-pattern clusters are merged along graph edges; clusters are nested by bounding box containment; and a single top-level cluster is created from all remaining children.
2. **Algorithm 2 (Sorting within a cluster):** Boxes are rotated to remove mean orientation, and then a topological sort applies column-wise or row-wise precedence constraints based on axis-overlap and center coordinates.
3. **Algorithm 3 (Pattern labeling from annotations):** Used at training time to derive ground-truth binary labels from human-annotated paragraph ordering sequences by comparing the geometric relation (vertical/horizontal/unknown) between each consecutive paragraph pair.

This design separates the machine learning component (local binary classification) from the combinatorial reasoning component (sorting), keeping the model small while enabling correct handling of mixed layouts, perspective distortion, and rotated text.

## What experiments were performed?

### Datasets

- **Internal annotated set:** 25K training images and a few hundred test images per language, annotated with paragraph polygons and partial reading order groups. Ground truths are partial (some subsets of paragraphs form ordered groups; order among groups is undefined). Languages tested: English, French, Italian, German, Spanish, Russian, Hindi, Thai.
- **PubLayNet:** 340K training + 12K validation images used to supplement training; "text" regions are treated as column-wise, "table"/"figure" containers as row-wise.

OCR bounding boxes are provided by Google Cloud Vision API.

### Evaluation metric

The authors use a **normalized Levenshtein distance** (lower is better) between the serialized predicted reading order and a ground-truth word sequence extracted from each annotated reading order group. This metric accommodates partially annotated ground truth, unlike BLEU or Kendall's Tau which require full permutation comparisons.

### Baselines

1. **All-column-wise topological sort:** Applies column-wise bidimensional sort rules globally. Chosen over all-row-wise because it scores better in practice.
2. **Fully-connected graph with direct edge-direction prediction:** A GCN on a complete graph predicting pairwise precedence relations, similar to Li et al. (ECCV 2020). Included to demonstrate scalability problems with dense graphs on receipt-style inputs.

### Ablations

- Image feature RoI source (none vs. node boxes vs. edge boxes): edge boxes are best; node boxes are no better than no image features (Table 2).
- Classification task scores on PubLayNet vs. the internal annotated set: PubLayNet scores near-perfect (F1 $\approx$ 0.997 for pattern, 0.995 for clustering), while the real-world annotated set reaches F1 0.819 / 0.902, reflecting the difficulty of in-the-wild images.

### Training setup

10M steps with random rotation and scaling augmentations, with image and OCR boxes transformed together. The image is scaled so all text boxes fit in a circle of diameter 512, then cropped or padded to 512 $\times$ 512; this ensures rotation augmentation never moves boxes out of bounds.

## What are the outcomes/conclusions?

On the multi-language evaluation set (Table 3), the 2-task GCN plus cluster-and-sort algorithm reduces normalized Levenshtein distance from 0.146 (all-column baseline) to 0.098 for English, and shows consistent improvements across all seven non-English languages despite training on English only. The fully-connected graph baseline shows intermediate results; on dense inputs (e.g., long receipts) it produces clearly worse output than the sparse approach (Figure 10).

The edge-box RoI ablation (Table 2) is the most informative experiment: node-box pooling does not help and can hurt, while edge-box pooling consistently improves both tasks. This supports the authors' hypothesis that useful visual signals (separator lines, color gradients) appear between text boxes.

The model is 267K parameters total, runs on mobile devices, and needs no text recognition (language features are omitted deliberately) to stay language-agnostic.

**Limitations acknowledged by the authors:**

- Complex layouts with multiple adjacent tabular sections can cause incorrect cross-section reading order because the two-task model lacks a higher-level section-parsing signal. A 3-task version trained on menu-specific section annotations partially addresses this but does not generalize reliably.
- Perspective-distorted tables (Figure 8, the menu from Figure 1) remain difficult: rotating boxes to cancel mean angle still leaves slanted individual boxes, so topological sort on axis-aligned containing boxes cannot guarantee row alignment.
- The model is not a table structure parser; for table-internal reading order, a dedicated structure recognition model will likely outperform it.
- Training data is English-only; while Latin-script generalization is strong, Cyrillic, Devanagari, and Thai still trail Latin languages in absolute score.

## Reproducibility

### Models

- MPNN-variant GCN: 10 weight-sharing graph convolution steps; node feature dimension 32; message-passing hidden dimension 128; edge-to-node pooling uses 4-head attention with 3 hidden layers of size 16 and dropout 0.5.
- MobileNetV3-Small image backbone: input resized so all text fits in a circle of diameter 512; output pooled via bilinear interpolation over $16 \times 3$ points per edge box; dropout 0.5.
- Total parameters: 267K (144K from MobileNetV3-Small, 123K from the GCN).
- No weights are released.

### Algorithms

- Optimizer and learning rate schedule: not reported.
- Training steps: 10M.
- Augmentations: random rotation and scaling with synchronized image and box transforms.
- TF-GNN used as the GCN implementation framework.
- No code repository released.

### Data

- Internal annotated dataset: 25K English training images with paragraph polygon and partial reading order annotations; a few hundred test images per language. Not publicly released.
- PubLayNet (340K train / 12K val): publicly available. Used to supplement training.
- OCR input: Google Cloud Vision API (not publicly reproducible at the same quality).
- No contamination analysis reported.

### Evaluation

- Metric: normalized Levenshtein distance. Exact word-level formulation described in Section 4.1.
- Baselines use the same OCR inputs from Google Cloud Vision API, so comparisons are fair within the paper but may not transfer to other OCR systems.
- No error bars, significance tests, or multi-run statistics reported.
- The PubLayNet reading order ground truth is constructed heuristically (text $\rightarrow$ column-wise, table/figure $\rightarrow$ row-wise), not from human annotation of actual reading order.

### Hardware

- No training hardware or compute budget reported.
- Inference is described as fast enough for mobile deployment, but no latency benchmarks or VRAM figures are provided.

## BibTeX

```bibtex
@inproceedings{wang2023sparse,
  title={Text Reading Order in Uncontrolled Conditions by Sparse Graph Segmentation},
  author={Wang, Renshen and Fujii, Yasuhisa and Bissacco, Alessandro},
  booktitle={Document Analysis and Recognition -- ICDAR 2023},
  year={2023},
  organization={Springer}
}
```