PDF Column Detection Is a Graph Problem, Not a Signal Processing Problem

TLDR

Traditional document layout engines model column detection using 1D histogram valley scanning, a signal-processing framing that treats text elements as continuous noisy waveforms. Because text elements are discrete topological geometry, histogram scanning fails on bullet indents, ragged line endings, and financial headers. Reframing column detection as an interval graph separator problem replaces magic threshold tuning with topological predicates.

Problem statement: the signal processing misconception

Signal processing is optimized for continuous noisy waveforms (audio, imagery, sensor data).

PDF document text bands are not continuous waveforms. They are discrete geometric intervals $[X_{min}, X_{max}]$.

Projecting text intervals into 1D pixel histogram arrays introduces flawed assumptions:

1. Assumption 1: Low coverage indicates a column gutter (False: Bullet indents create low coverage without being gutters).
2. Assumption 2: Column gutters have uniform zero coverage (False: Ragged line ends create intermittent coverage).

Technical architecture: interval graph separator model

Model text bands as nodes in an interval graph. An edge exists between two text bands if their horizontal intervals overlap:

Interval Graph Node (Text Band A): [ minX_A ------------------ maxX_A ]
Interval Graph Node (Text Band B):            [ minX_B ------------------ maxX_B ]
                                              ^ Overlap creates edge ^

A column split candidate coordinate $X$ is a Graph Separator if removing coordinate $X$ partitions graph nodes into two independent subgraphs (Left-Only bands and Right-Only bands) with zero crossing edges:

// Graph Separator Predicate
export function isGraphSeparator(
  narrowBands,
  splitCoordinate,
  gutterHalfWidth,
) {
  const leftSubGraph = [];
  const rightSubGraph = [];
  const crossingEdges = [];
for (const band of narrowBands) {     if (band.maxX <= splitCoordinate - gutterHalfWidth) {       leftSubGraph.push(band);     } else if (band.minX >= splitCoordinate + gutterHalfWidth) {       rightSubGraph.push(band);     } else {       crossingEdges.push(band); // Edge crosses candidate separator X     }   }
// Topological Predicate: Valid separator requires sufficient partitions & minimal crossing edges   const coexistenceTotal =     leftSubGraph.length + rightSubGraph.length + crossingEdges.length;   const commitmentRatio =     (leftSubGraph.length + rightSubGraph.length) / (coexistenceTotal || 1);
return {     isValidSeparator:       commitmentRatio >= 0.4 &&       leftSubGraph.length >= 3 &&       rightSubGraph.length >= 3,     leftCount: leftSubGraph.length,     rightCount: rightSubGraph.length,   }; }

The upstream prevention cascade

Fixing upstream layout column detection prevents downstream classifier starvation:

• Failure Cascade: Incorrect column detection assigns text items to paragraph blocks prematurely.
• Downstream Result: Unclaimed text item arrays drop to 0, causing borderless table detectors to miss financial tables entirely.
• Graph Separator Result: Accurate column partitioning leaves table items unclaimed, enabling downstream stream-table detectors to execute successfully.

Rule of thumb: Treat PDF column detection as an interval graph separator problem rather than a 1D histogram signal processing problem.