How Rect‑Based Table Detection Works in pdf‑inspector: A Deep Dive into PDF Rectangle Operators

pdf‑inspector detects tables by clustering explicit rectangle (re) drawing operators from PDF content streams through a multi‑stage pipeline involving spatial indexing, union‑find clustering, and grid‑based table reconstruction.

The pdf-inspector Rust library implements a sophisticated rect‑based table detection system in src/tables/detect_rects.rs. This approach targets PDFs where table cells are explicitly drawn as rectangular borders—a common pattern in generated PDFs from spreadsheets, reports, and data exports. The system processes raw PDF geometry operators, filters noise, clusters related rectangles, and attempts multiple table reconstruction strategies before falling back to heuristic hints.

Overview of the Detection Pipeline

The entry point detect_tables_from_rects orchestrates nine distinct processing stages. Each stage progressively refines rectangle data toward structured table output or diagnostic hints for downstream detectors.

Stage 1: Normalize and Filter Raw Rectangles

PDF content streams often contain malformed or decorative rectangle operators. The first pass corrects negative widths and heights, removes tiny decorations below a size threshold, and strips obvious page‑spanning backgrounds via without_page_backgrounds.

// From detect_tables_from_rects, lines 36-49
let rects: Vec<_> = rects
    .into_iter()
    .map(|r| r.normalize())  // Fixes negative dimensions
    .filter(|r| r.area() > MIN_RECT_AREA)  // Drop decorations
    .collect();

Lines 52‑66 implement additional filtering, while lines 70‑84 handle background removal. This normalization ensures downstream clustering operates on geometrically valid, semantically meaningful rectangles.

Stage 2: Remove Oversized Background Fills

Large filled rectangles often represent section backgrounds rather than cell borders. The code computes the median cell width from all remaining rects, then discards any rectangle exceeding 10× that median.

// Lines 77-84: Median-based size filtering
let median_width = compute_median_width(&rects);
let max_allowed_width = median_width * 10.0;
let rects: Vec<_> = rects
    .into_iter()
    .filter(|r| r.width() <= max_allowed_width)
    .collect();

This statistical approach adapts to document scale without hardcoded thresholds.

Stage 3: Deduplicate Sub‑Rectangles

Nested or overlapping rectangles from adjacent drawing commands produce spurious edge detections. The algorithm identifies small rectangles fully contained within slightly larger ones (height ratio < 4) and drops the smaller copy. Lines 95‑126 implement this containment check with tolerance‑aware geometry.

Spatial Clustering with Union‑Find

The core grouping algorithm uses disjoint‑set (union‑find) data structures combined with spatial hashing for near‑linear performance.

Grid Bucketing for Scalable Overlap Detection

Rather than testing all rectangle pairs (O(n²)), cluster_rects assigns rectangles to a uniform 64‑point grid. Overlap tests occur only within shared grid cells, with a per‑cell pair limit (MAX_CLUSTER_PAIRS_PER_CELL) preventing pathological cases.

// Lines 81-95: Grid coordinate utilities
fn grid_coord(x: f32, cell_size: f32) -> i32 {
    (x / cell_size).floor() as i32
}

fn grid_span(min: f32, max: f32, cell_size: f32) -> RangeInclusive<i32> {
    // Returns inclusive cell indices for a coordinate range
    grid_coord(min, cell_size)..=grid_coord(max, cell_size)
}

Handling Large Rectangles

Rectangles spanning more than 64 grid cells bypass the standard bucketing to avoid memory explosion. These "large" rectangles route through auxiliary maps (large_x, large_y, large_coarse_y) and merge in linear‑time passes (lines 65‑73, 124‑170).

Union‑Find Implementation

The UnionFind struct (lines 14‑55) manages component merging with path compression:

pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<u8>,
    size: Vec<usize>,
}

impl UnionFind {
    pub fn find(&mut self, x: usize) -> usize {
        // Path compression for amortized O(α(n)) lookup
    }
    
    pub fn union(&mut self, x: usize, y: usize) {
        // Union by rank, with size tracking
    }
}

Two rectangles union when rects_overlap (lines 63‑79) returns true—an AABB test with tolerance scaling (tolerance * 4.0).

Component Formation

After all unions complete, lines 332‑347 gather root nodes and filter components below min_size (default 6 rectangles). This eliminates isolated drawing artifacts from genuine table structures.

Table Construction Strategies

Each surviving rect cluster feeds into progressive table detectors:

Direct Rectangle Table Detection

detect_direct_rect_table (lines 576‑584) attempts three strategies in order:

1. Full grid: Requires consistent row and column alignment across all rectangles
2. Row stripe: Horizontal cell bands with varying column counts per row
3. Stacked boxes: Independent rectangular regions treated as sub‑tables

Wide‑Cluster Splitting

When direct detection fails on broad clusters, split_wide_cluster (lines 49‑112, invoked at lines 588‑610) finds the largest X‑axis gap and recursively detects tables in each partition:

// Conceptual flow from lines 588-610
if let Some(split_point) = find_largest_x_gap(&cluster) {
    let (left, right) = split_at_gap(cluster, split_point);
    detect_tables_from_rects_on(left);
    detect_tables_from_rects_on(right);
}

Fallback Merge

If individual clusters yield only narrow tables (≤ 3 columns) or no tables, the algorithm merges all clusters and runs a row‑stripe detector on the combined geometry (lines 686‑724). This handles fragmented table borders that survive initial clustering as separate components.

Hint Generation for Heuristic Detection

Clusters that resist all table construction become RectHintRegion outputs (lines 740‑815, 836‑876). These bounding boxes guide the later heuristic detector—a separate subsystem analyzing text alignment and spacing rather than explicit graphics.

// Output types from detect_tables_from_rects
pub struct RectHintRegion {
    pub bbox: Rect,
    pub confidence: f32,
    pub source_cluster_size: usize,
}

This cooperation between explicit‑geometry and heuristic detection maximizes recall across diverse PDF generation patterns.

Public API and Usage

The rustdoc‑friendly interface exposes detection through pdf_inspector::extractor:

use pdf_inspector::extractor::detect_tables_from_rects;

// Items: extracted text positions from the PDF
// Rects: PdfRect objects from `re` operators in content stream
// page: 0-based page index
let (tables, hint_regions) = detect_tables_from_rects(
    &page_text_items,
    &page_rects,
    page_number,
);

Return values:

• tables: Complete Table structures with column/row indexing and cell text assignment
• hint_regions: Localized search regions for downstream heuristic processing

Integration in the pdf2md Binary

The production pdf2md tool orchestrates three detection strategies:

// From src/extractor/mod.rs conceptual flow
let (rect_tables, hints) = detect_tables_from_rects(&items, &rects, page);
if !rect_tables.is_empty() {
    return rect_tables;  // Prefer explicit geometry
}

let line_tables = detect_tables_from_lines(&items, &lines);
let heuristic_tables = detect_tables_heuristic(&items, hints);

// Merge or select best results...

This cascading approach prioritizes high‑precision rect‑based results while maintaining coverage through alternative methods.

Key Implementation Limits

Parameter	Default	Purpose
CLUSTER_GRID_CELL	64 pt	Spatial hashing resolution
MAX_CLUSTER_PAIRS_PER_CELL	—	Prevents quadratic blow‑up within cells
MAX_CLUSTER_RECTS	2000	Caps union‑find component size
min_size	6 rects	Minimum cluster size for table consideration

These safeguards ensure robust performance on vector‑heavy PDFs with thousands of drawing operators.

Summary

• Rect‑based detection in pdf‑inspector operates on explicit PDF re operators, making it highly precise for bordered tables
• The nine‑stage pipeline progressively filters noise, clusters spatially related rectangles, and attempts multiple reconstruction strategies
• Union‑find with 64‑pt grid bucketing achieves near‑linear clustering performance while handling pathological inputs through size limits and large‑rect special cases
• Three table construction strategies (full grid, row stripe, stacked boxes) accommodate diverse table layouts, with recursive splitting for wide clusters
• Hint generation bridges to heuristic detection when explicit geometry proves insufficient
• The public API at detect_tables_from_rects returns both completed tables and diagnostic regions, supporting flexible downstream processing

Frequently Asked Questions

What types of PDFs work best with rect‑based table detection?

PDFs generated from structured data sources—spreadsheets, database reports, and document generators—typically draw explicit cell borders with re operators. Scanned documents, HTML‑to‑PDF conversions with CSS borders, and presentation exports may lack these operators entirely, requiring the heuristic or line‑based detectors instead.

How does pdf‑inspector handle overlapping or nested tables?

The deduplication stage (lines 95‑126) removes contained sub‑rectangles, while the wide‑cluster splitting mechanism partitions horizontally separated tables that share vertical overlap. Tables stacked vertically typically separate during grid bucketing due to Y‑axis cell boundaries. The fallback merge (lines 686‑724) can recombine erroneously split fragments when both halves produce weak results.

Why does the union‑find cluster cap at 2000 rectangles?

MAX_CLUSTER_RECTS = 2000 prevents runaway memory and CPU consumption on decorative vector graphics or complex illustrations misinterpreted as rectangle operators. According to the source in src/tables/detect_rects.rs, this limit has proven sufficient for production tables while excluding pathological PDFs that would otherwise stall processing.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}