How pdf-inspector Uses Horizontal Projection Histograms for Robust Column Detection

pdf‑inspector detects columns by building a horizontal projection histogram that counts text items across horizontal slices of the page, then identifies empty vertical strips (valleys) and validates them as gutters to split the page into logical columns.

The pdf-inspector project implements a fast, layout-aware column detection system that works across diverse PDF formats—academic papers, magazines, and mixed-content documents. Rather than relying on heuristics alone, its core algorithm leverages horizontal projection histograms to find the actual gaps between columns, even when text is justified or asymmetric layouts obscure visual boundaries.

Understanding Horizontal Projection Histograms

A horizontal projection histogram (also called an occupancy profile) is a one-dimensional signal where each bin represents a horizontal slice of the page and its value indicates how many text items occupy that slice. Dense text regions create peaks; empty gutters between columns create valleys. This approach gives pdf-inspector a page-wide, quantitative view of layout structure.

The histogram method is implemented in src/extractor/layout.rs and operates in three distinct stages: construction, valley detection, and validation.

Stage 1: Building the Occupancy Histogram

The algorithm begins by gathering all layout-relevant TextItems for the current page, excluding image placeholders【/src/extractor/layout.rs#L34-L38】.

Determining Histogram Parameters

The code computes the page's usable width (x_min to x_max) and selects a bin width that limits resolution to 65,536 bins maximum:

// From src/extractor/layout.rs#L44-L62 and L145-L161
let page_width = x_max - x_min;
let bin_width = BIN_WIDTH.max(page_width / 65_536.0);
let num_bins = (page_width / bin_width).ceil() as usize;
let mut histogram = vec![0u32; num_bins];

This cap ensures memory efficiency regardless of page dimensions.

Filtering Spanning Elements

Items wider than 60% of the page width are excluded from histogram construction. These spanning elements—full-width titles, headers, or dividers—would otherwise fill every bin and mask legitimate column gutters:

// From src/extractor/layout.rs#L162-L166
if item_width > page_width * 0.60 {
    continue; // Skip spanning items that would obscure gutters
}

Populating the Histogram

For each remaining text item, every bin it spans receives a count increment:

// From src/extractor/layout.rs#L170-L182
let left = ((item.x - x_min) / bin_width).floor() as usize;
let right = (((item.x + item.width) - x_min) / bin_width).ceil() as usize;

for count in histogram.iter_mut().take(right).skip(left) {
    *count += 1;
}

This yields a density profile where column boundaries appear as sustained low-count regions.

Stage 2: Identifying Candidate Gutters (Valleys)

Once the histogram exists, the algorithm extracts potential column boundaries by finding vertical gaps in the text distribution.

Absolute Threshold Method

First, a noise threshold is calculated as 15% of the maximum bin count (NOISE_FRACTION = 0.15). Bins at or below this threshold are considered empty【/src/extractor/layout.rs#L185-L188】:

// From src/extractor/layout.rs#L185-L188
let max_count = *histogram.iter().max().unwrap_or(&0);
let threshold = (max_count as f32 * NOISE_FRACTION) as u32;

Consecutive empty bins form valleys. These candidate gutters undergo geometric filtering:

• Minimum gutter width: 8 points (MIN_GUTTER_WIDTH = 8.0)
• Edge margin exclusion: 5% of page width to avoid false positives at page boundaries【/src/extractor/layout.rs#L209-L222】

Relative-Valley Fallback for Justified Text

When text is tightly justified, gutters may not reach the absolute noise threshold. For pages with ≥30 items, pdf-inspector invokes find_relative_valleys as a fallback【/src/extractor/layout.rs#L240-L272】.

This function applies smoothing to the histogram, then identifies local minima that are at most 60% of neighboring peaks, keeping only the deepest candidate:

// From src/extractor/layout.rs#L418-L487 (simplified concept)
fn find_relative_valleys(histogram: &[f32], min_prominence: f32) -> Vec<usize> {
    let smoothed = smooth_histogram(histogram);
    find_local_minima(&smoothed)
        .into_iter()
        .filter(|&idx| relative_depth(idx, &smoothed) <= 0.60)
        .max_by_key(|&idx| depth_at(idx, &smoothed)) // Deepest only
        .into_iter()
        .collect()
}

This relative approach recovers gutters that absolute thresholding misses.

Stage 3: Validation and Column Region Construction

Raw valleys require validation to distinguish true column boundaries from artifacts. The validate_and_build_columns function enforces structural constraints【/src/extractor/layout.rs#L522-L556】:

Criterion	Purpose	Constant
Minimum item count per side	Ensures both columns contain substantial content	Implicit in caller logic
Vertical span overlap ratio	Confirms columns coexist on same vertical extent	MIN_VERTICAL_SPAN_RATIO = 0.30
List-marker exclusion	Prevents narrow bullet columns from being treated as full columns	Heuristic detection

Item-to-Column Assignment

Validated gutters become boundaries. Items are assigned to columns by center point when justified text is detected, or by right edge for legacy compatibility【/src/extractor/layout.rs#L668-L682】:

// From src/extractor/layout.rs#L668-L682 (conceptual)
let use_center_point = has_justified_text(items);
let boundary = gutter_center_x;

let left_items: Vec<_> = items.iter()
    .filter(|i| {
        let ref_x = if use_center_point {
            i.x + effective_width(i) / 2.0
        } else {
            i.x + effective_width(i) // right edge
        };
        ref_x <= boundary
    })
    .collect();

Each validated region produces a ColumnRegion struct capturing the column's spatial extent【/src/extractor/layout.rs#L886-L904】.

XY-Cut Fallback for Asymmetric Layouts

When histogram analysis fails to find robust valleys—as with sidebars or asymmetric magazine layouts—pdf-inspector falls back to an XY-cut approach【/src/extractor/layout.rs#L386-L420】. This alternative examines the largest horizontal gap between item edges directly, catching structures that projection histograms may obscure.

Complete Implementation Reference

The following consolidated example demonstrates the three-stage pipeline:

use pdf_inspector::types::TextItem;

/// Three-stage column detection using horizontal projection histograms
pub fn detect_columns(items: &[TextItem], page_bounds: (f32, f32, f32, f32)) -> Vec<ColumnRegion> {
    let (x_min, _, x_max, _) = page_bounds;
    
    // Stage 1: Build histogram
    let histogram = build_histogram(items, x_min, x_max);
    
    // Stage 2: Find valleys with dual strategy
    let mut valleys = find_absolute_valleys(&histogram);
    if valleys.is_empty() && items.len() >= 30 {
        valleys = find_relative_valleys(&histogram);
    }
    
    // Stage 3: Validate and build regions
    valleys.iter()
        .filter_map(|&v| validate_and_build_columns(v, &histogram, items, x_min))
        .collect()
}

fn build_histogram(items: &[TextItem], x_min: f32, x_max: f32) -> Vec<u32> {
    const MAX_BINS: usize = 65_536;
    const SPANNING_THRESHOLD: f32 = 0.60;
    const BIN_WIDTH: f32 = 2.0; // Default, adjusted per page
    
    let page_width = x_max - x_min;
    let bin_width = BIN_WIDTH.max(page_width / MAX_BINS as f32);
    let mut hist = vec![0u32; (page_width / bin_width).ceil() as usize];
    
    for item in items {
        let w = effective_width(item);
        if w > page_width * SPANNING_THRESHOLD { continue; }
        
        let left = ((item.x - x_min) / bin_width).floor() as usize;
        let right = (((item.x + w) - x_min) / bin_width).ceil() as usize;
        
        for count in hist.iter_mut().take(right).skip(left) {
            *count += 1;
        }
    }
    hist
}

Performance Characteristics and Design Considerations

Aspect	Implementation Detail	Rationale
Bin limit	65,536 maximum	Memory bounds, cache efficiency
Spanning exclusion	60% width threshold	Preserve gutter visibility
Noise floor	15% of peak	Adapt to variable text density
Minimum gutter	8 points	Physical printing constraints
Vertical overlap	30% minimum	Ensure parallel column existence

The histogram approach provides O(n × bins) complexity where n is the text item count, making it suitable for real-time PDF processing. The fallback to XY-cut ensures graceful degradation when projection analysis is insufficient.

Summary

• pdf-inspector constructs horizontal projection histograms to quantify text density across page width, creating a signal where valleys indicate potential column gutters.
• The algorithm applies dual valley detection: absolute thresholding for clear gaps, and relative minima analysis for justified text layouts.
• Geometric constraints—including minimum width, edge margins, and vertical overlap—validate candidate gutters before committing to column boundaries.
• A fallback XY-cut method handles asymmetric layouts that resist histogram analysis.
• All core logic resides in src/extractor/layout.rs with supporting utilities in src/types.rs and src/text_utils.rs.

Frequently Asked Questions

What is a horizontal projection histogram in PDF processing?

A horizontal projection histogram is a one-dimensional density profile where each bin counts how many text elements occupy a particular horizontal slice of a page. In pdf-inspector, this profile reveals where text clusters into columns and where empty gutters separate them. The tool uses this signal rather than visual rendering to achieve layout analysis that works across different PDF generation methods.

Why does pdf-inspector ignore items wider than 60% of the page?

Spanning elements like full-width titles, section headers, and horizontal rules would increment every histogram bin they touch, effectively flattening the profile and masking legitimate column gutters. By excluding items exceeding 60% of page width, pdf-inspector preserves the valley structure that indicates actual column boundaries. This threshold is implemented in src/extractor/layout.rs near line 162.

How does relative-valley detection differ from absolute thresholding?

Absolute thresholding marks bins as empty when their count falls below 15% of the maximum histogram value. Relative-valley detection instead smooths the histogram and finds local minima whose depth is at most 60% of surrounding peaks. This secondary method activates when justified text creates gutters that never drop to the absolute noise floor, ensuring robust detection across diverse typographic layouts.

When does pdf-inspector fall back to XY-cut analysis?

The XY-cut fallback triggers when histogram-based valley detection returns no valid gutters, typically in asymmetric layouts like magazine sidebars or documents with irregular margin structures. Rather than forcing a histogram interpretation, the algorithm examines direct horizontal gaps between item edges in src/extractor/layout.rs lines 386-420. This dual-strategy approach maximizes layout coverage without overfitting to projection assumptions.

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