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

> Discover how pdf-inspector detects columns using horizontal projection histograms and valley detection. Analyze page layouts efficiently with this technical approach.

- Repository: [Firecrawl/pdf-inspector](https://github.com/firecrawl/pdf-inspector)
- Tags: internals
- Published: 2026-08-14

---

**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`](https://github.com/firecrawl/pdf-inspector/blob/main/src/extractor/layout.rs), the `build_histogram` function scans all `TextItem` objects on a page and bins them by horizontal position.

```rust
// 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`](https://github.com/firecrawl/pdf-inspector/blob/main/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)

```rust
// 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`](https://github.com/firecrawl/pdf-inspector/blob/main/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

```bash

# 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:

```json
{
  "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`](https://github.com/firecrawl/pdf-inspector/blob/main/src/extractor/layout.rs) can be accessed before Markdown conversion. The [`src/markdown/preprocess.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/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`](https://github.com/firecrawl/pdf-inspector/blob/main/src/extractor/layout.rs) | Histogram construction, smoothing, valley detection, column slicing |
| [`src/extractor/reading_order.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/src/extractor/reading_order.rs) | Orders content within detected columns, handles sidebars |
| [`src/markdown/preprocess.rs`](https://github.com/firecrawl/pdf-inspector/blob/main/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`](https://github.com/firecrawl/pdf-inspector/blob/main/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.