How to Detect PDF Columns Without Lying to Yourself

TLDR

Traditional PDF column detection uses 1D X-axis histogram valley scanning to find spatial gutters. This signal-processing approach misinterprets bullet indents, wide margins, and financial headers as column splits. Modeling column detection as a graph-theoretic separator, finding an X coordinate that partitions text bands into two populations with zero crossing intervals, eliminates heuristic magic numbers and functions reliably across arbitrary layouts.

Detection Strategy	Core Mechanism	Vulnerability	Layout Adaptability
Histogram Valley Scan	Counts per-pixel X coverage	Fails on bullet indents & wide margins	Low (Requires page-specific thresholds)
Bipartite Graph Separator	Interval-merge + 3-gate validation	None (Pure topological partition)	High (100% Scale & Font Agnostic)

---

Problem statement: the limits of histogram valley scanning

Standard PDF column extractors project text bounding boxes onto a 1D horizontal histogram array:

// NAIVE HISTOGRAM APPROACH: Counting pixel coverage
const histogram = new Float32Array(pageWidth);
textBands.forEach(band => {
  for (let x = Math.floor(band.minX); x <= Math.ceil(band.maxX); x++) {
    histogram[x]++;
  }
});
// Find gutters where histogram[x] < threshold...

Histogram scanning asks a magnitude question: "Is text coverage low at coordinate X?"

This fails on:

• Bullet Indents: Lone bullet characters (•) create low coverage regions on the left margin.
• Financial Headers: Short right-aligned header text creates low coverage regions on top right margins.
• Mixed Layouts: Pages featuring single-column headers followed by 2-column body text.

---

Technical architecture: bipartite band partitioning

Model text bands as horizontal intervals $[X_{min}, X_{max}]$. A vertical split candidate at coordinate $X$ with inward gutter tolerance $tol$ partitions text bands into three sets:

$$\text{LeftOnly} = \{ b \mid b.maxX \le X - tol \}$$ $$\text{RightOnly} = \{ b \mid b.minX \ge X + tol \}$$ $$\text{CrossBands} = \{ b \mid \text{otherwise} \}$$

    [----- Left Band 1 -----]         |         [----- Right Band 1 -----]
           [--- Left Band 2 ---]      |      [------- Right Band 2 -------]
                                      |
                                  Split (X)
                                 <--tol|tol-->

A split candidate $X$ is valid if it satisfies three structural gates:

Gate 1: population count threshold

Both sides must contain at least 3 committed text bands:

if (leftOnly.length < 3 || rightOnly.length < 3) return false;

Gate 2: coexistence zone commitment ratio

Evaluate commitment ratio within the Y-range intersection of left and right populations (the Coexistence Zone):

const coexistTop = Math.max(
  Math.min(...leftOnly.map(b => b.y)),
  Math.min(...rightOnly.map(b => b.y))
);
const coexistBottom = Math.min(
  Math.max(...leftOnly.map(b => b.y)),
  Math.max(...rightOnly.map(b => b.y))
);
if (coexistBottom < coexistTop) return false; // Populations do not overlap vertically!
const localBands = narrowBands.filter(b => b.y >= coexistTop && b.y <= coexistBottom); const commitmentRatio = (leftOnly.length + rightOnly.length) / localBands.length;
if (commitmentRatio < 0.40) return false; // Less than 40% commitment in coexistence zone

Gate 3: vertical persistence relative to content span

Ensure populations are not confined strictly to header zones:

const contentTop = Math.min(...narrowBands.map(b => b.y));
const contentBottom = Math.max(...narrowBands.map(b => b.y));
const contentHeight = contentBottom - contentTop || 1;
const persistenceThreshold = contentTop + contentHeight * 0.20;
const leftConfined = leftOnly.every(b => b.y <= persistenceThreshold); const rightConfined = rightOnly.every(b => b.y <= persistenceThreshold);
if (leftConfined && rightConfined) return false; // Confined strictly to header area

---

Candidate generation via interval merging

To generate split candidates $X$ in $O(N \log N)$ time, merge overlapping text band intervals into disjoint spans and extract gap midpoints:

export function generateSplitCandidates(narrowBands, minGapPx, viewportWidth) {
  // Sort bands by minimum X coordinate
  const sorted = [...narrowBands].sort((a, b) => a.minX - b.minX);
  const mergedSpans = [];
// Merge overlapping intervals   for (const band of sorted) {     if (mergedSpans.length && band.minX <= mergedSpans.at(-1).hi) {       mergedSpans.at(-1).hi = Math.max(mergedSpans.at(-1).hi, band.maxX);     } else {       mergedSpans.push({ lo: band.minX, hi: band.maxX });     }   }
// Extract gap midpoints between disjoint spans   const candidates = [];   for (let i = 0; i < mergedSpans.length - 1; i++) {     const gapWidth = mergedSpans[i + 1].lo - mergedSpans[i].hi;     if (gapWidth >= minGapPx) {       const midpoint = (mergedSpans[i].hi + mergedSpans[i + 1].lo) / 2;       // Restrict candidates to page interior (10% to 90% viewport width)       if (midpoint >= viewportWidth  0.10 && midpoint <= viewportWidth  0.90) {         candidates.push(midpoint);       }     }   }
return candidates; }

Rule of thumb: Model multi-column layout detection as an interval graph partition problem. Use interval merging and multi-gate commitment ratios to reject false gutters.