How pdf-inspector Uses Horizontal Projection Histograms and Valley Detection for Column Detection

pdf-inspector analyzes page layouts by building an occupancy histogram across the horizontal axis, smoothing the data, and identifying valleys as candidate column separators.

Column detection is a core challenge in PDF extraction. Unlike HTML, PDFs encode characters as positioned glyphs without semantic structure. The pdf-inspector project solves this by treating horizontal whitespace patterns as signals for column boundaries. This article explains the histogram-based algorithm implemented in the Rust codebase.

The Core Algorithm: From Glyphs to Valleys

The column detection pipeline runs automatically during extraction. It transforms raw text positions into structural column boundaries through four stages.

Stage 1: Build the Occupancy Histogram

In src/extractor/layout.rs, the build_histogram function scans all TextItem objects on a page and bins them by horizontal position.

// Conceptual flow based on the source implementation
// See src/extractor/layout.rs, line 18 comment:
// "Builds an occupancy histogram across the page width and finds empty valleys"

The histogram uses a fixed maximum number of bins to handle arbitrarily wide pages. Each bin represents a slice of the page width. When a text item's x-coordinate falls within a bin's range, that bin's count increments.

Key properties of this histogram:

• Bin count is capped to prevent memory explosion on poster-sized PDFs
• Only horizontal position matters — vertical position is ignored at this stage
• All text items contribute equally regardless of font size or weight

Stage 2: Smooth and Normalize

Raw histograms are noisy. Isolated characters, page numbers, and margin notes create spikes that could be mistaken for column content. The algorithm applies a 5-bin moving average to smooth these fluctuations.

After smoothing, the histogram is normalized against the maximum bin count. This produces values between 0 and 1, making threshold parameters independent of document-specific text density.

Stage 3: Detect Valleys as Column Separators

The find_valleys helper (documented at line 585 in src/extractor/layout.rs) identifies local minima in the smoothed histogram:

"Find relative valleys (local minima) in the histogram"

A valley qualifies as a column separator when:

• Its normalized count falls below neighboring bins by a configurable margin
• The valley is sufficiently wide to represent meaningful whitespace
• It is not inside a detected table region (handled separately by the table pipeline)

// Valley detection parameters in the actual implementation
// - margin_threshold: minimum depth relative to neighbors
// - min_valley_width: minimum consecutive low bins to qualify

Each valid valley becomes a column boundary. The regions between valleys form column slices.

Stage 4: Handle Edge Cases and Fallbacks

The algorithm includes specialized handling for layouts that histograms alone cannot capture:

Edge Case	Handling
No valleys found	Falls back to XY-cut style gap detection (line 312)
Asymmetric layouts	Special sidebar detection (line 330 comment: "Handles asymmetric layouts (sidebars) that the histogram misses")
Spanning elements	Full-width captions and headings are preserved across columns
Table regions	Valley detection is suppressed inside table boundaries

These refinements ensure the histogram method works for newspapers, academic papers, and mixed layouts alike.

Why Horizontal Projection Works

The histogram approach offers three advantages over alternatives like connected component analysis or machine learning:

• Computational efficiency — O(N) where N is glyph count; no neural network overhead
• Deterministic output — Same PDF produces identical columns across runs
• Parameter interpretability — Bin width, smoothing window, and valley thresholds map directly to visual whitespace concepts

Vertical projection histograms are not used for column detection because columns are defined by horizontal gaps in text flow. The algorithm does analyze vertical relationships later in src/extractor/reading_order.rs to determine final reading order within detected columns.

Working with Column Detection Output

The column boundaries are exposed through both CLI and programmatic interfaces.

Command Line Inspection

# Standard extraction with automatic column detection

pdf2md document.pdf > output.md

# Extract raw layout data including column boundaries

pdf2md --json document.pdf | jq '.pages[].layout.columns'

The JSON output structure:

{
  "pages": [
    {
      "layout": {
        "columns": [
          {"left": 0.0, "right": 0.33},
          {"left": 0.35, "right": 0.68},
          {"left": 0.70, "right": 1.0}
        ]
      }
    }
  ]
}

Coordinates are normalized to page width (0.0–1.0).

Programmatic Access

For custom processing, the ColumnSlice structs from src/extractor/layout.rs can be accessed before Markdown conversion. The src/markdown/preprocess.rs module demonstrates merging lines that cross column gaps — useful for handling drop-caps and ornamental initials.

Key Source Files

File	Function
src/extractor/layout.rs	Histogram construction, smoothing, valley detection, column slicing
src/extractor/reading_order.rs	Orders content within detected columns, handles sidebars
src/markdown/preprocess.rs	Post-processing of column-spanning elements before output

Summary

• Horizontal projection histograms transform glyph positions into whitespace density maps in src/extractor/layout.rs
• Valley detection identifies relative minima as column separators, with configurable depth and width thresholds
• Smoothing and normalization make the algorithm robust to noise and document-specific density variations
• Fallback mechanisms handle edge cases: XY-cut when no valleys exist, special logic for sidebars and tables
• Output is available as normalized column boundaries via --json or automatically processed into correct reading order

Frequently Asked Questions

What parameters control valley detection sensitivity?

Three parameters configure the behavior: bin count (horizontal resolution), smoothing window width (default 5 bins), and valley margin threshold (relative depth required vs. neighbors). These are compile-time constants in the current codebase; runtime configuration is not exposed through the CLI.

Why does column detection sometimes fail on complex magazine layouts?

Highly irregular layouts with text flowing around images, or pages with dozens of micro-columns in advertisements, may produce histograms without clear valley structure. The algorithm falls back to XY-cut gap detection, but this cannot capture all reading-order semantics. Such documents may require manual post-processing.

How does pdf-inspector distinguish between column valleys and intra-paragraph spacing?

The valley width threshold filters narrow gaps. Additionally, the table detection pipeline runs before column analysis; table cells often contain narrow internal spacing that would create false valleys. Detected table regions are excluded from histogram analysis to prevent this interference.

Can column detection be disabled if I know my documents are single-column?

No explicit flag exists. However, the histogram for a truly single-column document will typically show no qualifying valleys, causing the algorithm to fall back to single-column mode automatically. The performance overhead is negligible — histogram construction remains O(N) regardless of column count.

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