Gefüllte Rechtecke als Tabellenlinien im PDFium Delphi

Eine aus Word oder Google Docs exportierte Tabelle kann Hunderte von Umrandungsstücken auf einer Seite tragen und keine einzige Stroke-Linie. Dekomprimiert man die Seite mit qpdf --qdf, liest sich der Content-Stream wie eine Spalte von re f-Paaren, jeder beschreibt eine Box von einem halben Punkt Höhe. Ein Tabellen-Detektor, der nur nach Segmenten mit Stroke sucht, findet nichts, fällt auf das Ausrichten von Wörtern anhand des Weißraums zurück und liefert eine Streuung von Zwei- und Drei-Zeilen-Fragmenten zurück, wo der Autor ein sauberes Gitter gezeichnet hat. Die Umrandungen sind alle da. Sie sind mit einer Füllung gemalt, also muss der Detektor gefüllte Rechtecke als Tabellenlinien lesen und dann fast berührende Kanten auf gemeinsame Gitterlinien ziehen

Warum eine Word-Tabelle keine Stroke-Linien hat

Eine Textverarbeitung denkt sich eine Zellumrandung als Box mit einer Breite und malt diese Box mit dem Fill-Operator. ISO 32000-1 §8.5.2.1 definiert re als Anfügen eines geschlossenen Rechteck-Subpfads, und §8.5.3 trennt die Zeichenoperatoren: S zieht den Pfad mit der aktuellen Linienbreite nach, f füllt sein Inneres. Eine 0,5-Punkt-Umrandung kommt als x y w 0.5 re f heraus, und die Stroke-Maschinerie (Linienbreite, Joins, Dash-Muster) läuft nie. Zellschattierung ist dieselbe Konstruktion mit einer größeren Box. Die Stroke-Form, die ein linienorientierter Detektor erwartet – m, l, S –, ist die, die Office-Exporte selten benutzen:

% eine Zellumrandung aus einem Textverarbeitungs-Export: eine 0.5 pt hohe gefüllte Box
72 700 468 0.5 re f
% Zellschattierung: eine gefüllte Box in Zellgröße
72 676 117 24 re f
% die Stroke-Gitterlinie, nach der ein Stroke-only-Detektor sucht
72 700 m 540 700 l S

Wer einen eigenen Detektor auf der rohen PDFium-API schreibt, ruft im ersten Entwurf gewöhnlich FPDFPath_GetDrawMode auf, behält den Pfad, wenn das Stroke-Flag gesetzt ist, und geht weiter. Beide gefüllten Boxen oben fallen durch diesen Test. Die Wörter in den Zellen erreichen die Whitespace-Erkennung, und bei einem kompakten Export liegen die Spalten vielleicht 6 Punkte auseinander. In PDFium Component beträgt das Default-MinColumnGap 12 Punkte, also registrieren diese Spalten nicht. MinColumnGap so weit zu senken, dass sie es tun, lässt auch die gestreckten Wortabstände von Blocksatz-Absätzen registrieren, und das Gitter, das der Autor gezeichnet hat, kommt trotzdem nie zurück, denn die Information, die es definiert, lebt in den gefüllten Boxen

Wie PDFium Component eine gefüllte Box als Tabellenlinie liest

PDFium Component liest Tabellengeometrie aus jedem Pfadobjekt auf der Seite, einen Subpfad nach dem anderen, und weil TPdfTableExtractionOptions.DetectFilledRulings auf True defaultet, wird ein Pfad, dessen Fill-Mode nicht none ist, neben den Stroke-Pfaden auf Tabellenlinien untersucht. Der Filter dahinter ist absichtlich streng. Ein gefüllter Subpfad qualifiziert sich nur, wenn er zwischen vier und acht Punkten hat, kein Kurvensegment enthält und jeder Punkt innerhalb von 0.05 Punkt auf einer Ecke der Bounding Box des Subpfads sitzt. Ein mit re gezeichnetes Rechteck passiert, und eines, das als fünf explizite Punkte mit wiederholter Ecke gezeichnet ist, ebenso. Ein Dreieck, ein Chevron, eine L-förmige Umrandung oder ein abgerundeter Tab fällt durch den Test und trägt nichts bei

Das überlebende Rechteck wird über seine Bounding Box gegen MaxRulingThickness klassifiziert, das mit 3 Punkten defaultet. Breite auf oder unter dem Schwellenwert mit Höhe darüber ergibt eine vertikale Linie im horizontalen Zentrum, die die volle Höhe der Box läuft; der Spiegelfall ergibt eine horizontale Linie. Übersteigen beide Dimensionen den Schwellenwert, gilt die Box als schattierte Zelle und trägt vier Linien bei, eine pro Kante. Liegen beide auf oder unter ihm, trägt die Box nichts bei, also wird ein 2-Punkt-quadratisches Aufzählungszeichen nie zu einem Stummel des Tabellengitters. Die Füllfarbe spielt bei all dem keine Rolle. Eine weiße Box auf weißer Seite produziert dieselben Linien wie eine schwarze, weshalb ein Hintergrund-Panel in der Größe der Tabelle als äußerer Rahmen auftauchen kann

Stroke-Pfade behalten ihre eigene Route. Jedes gerade Segment, dessen Endpunkte sich auf einer Achse um nicht mehr als RulingTolerance (1 Punkt als Default) unterscheiden, wird eine Linie entlang der anderen, Kurvensegmente werden übersprungen, und das Schlusssegment eines geschlossenen Subpfads zählt mit. Ein Pfad, der mit Fill und Stroke zugleich gemalt wird, trägt über beide Routen bei, und die überlappenden Stücke kollabiert später der Merge-Schritt. Ein mit Stroke gezogenes Rundrechteck liefert weiterhin Linien für seine geraden Seiten; nur die Bögen an den Ecken fallen weg. Der Extraktionsaufruf selbst braucht keine besondere Einrichtung:

uses
  System.SysUtils, PDFium;

var
  Pdf: TPdf;
  Options: TPdfTableExtractionOptions;
  Tables: TPdfTables;
  Mode: string;
  I, J, WithText: Integer;
begin
  Pdf := TPdf.Create(nil);
  try
    Pdf.FileName := 'itinerary-from-word.pdf';
    Pdf.LoadDocument;
    Pdf.PageNumber := 1;                     // 1-basiert

    Options := TPdfTableExtractionOptions.Default;
    // die Filled-Ruling-Felder, ausgeschrieben mit ihren Default-Werten
    Options.DetectFilledRulings := True;
    Options.MaxRulingThickness := 3.0;       // Punkte; muss größer als 0 sein
    Options.RulingSnapTolerance := 4.0;      // Punkte; 0 schaltet das Einrasten ab
    Options.IncludeFormXObjects := True;

    Tables := Pdf.ExtractTables(Options);
    for I := 0 to High(Tables) do
    begin
      if Tables[I].DetectionMode = ptdmRuled then
        Mode := 'ruled'
      else
        Mode := 'whitespace';
      WithText := 0;
      for J := 0 to High(Tables[I].Cells) do
        if Tables[I].Cells[J].Text <> '' then
          Inc(WithText);
      Writeln(Format('%dx%d %s, confidence %.2f, %d of %d cells hold text',
        [Tables[I].RowCount, Tables[I].ColumnCount, Mode,
         Tables[I].Confidence, WithText, Length(Tables[I].Cells)]));
    end;
  finally
    Pdf.Free;
  end;
end;

MaxRulingThickness auf 0 zu setzen schaltet das Feature nicht ab. ExtractTables validiert die Geometrie-Optionen vorab und wirft EPdfError mit „Table extraction geometry options are invalid“ für einen Schwellenwert von null oder darunter. Für das Stroke-only-Verhalten DetectFilledRulings auf False setzen. Für alles, was aus einer Office-Suite oder einem Browser-Druckdialog kommt, lässt man es an; der strenge Rechteckfilter hält die Kosten niedrig, denn dekorative Füllungen passieren ihn fast nie

Was bewirkt RulingSnapTolerance bei Tabellen aus schattierten Zellen?

RulingSnapTolerance ist das, was eine Tabelle, die nur aus Schattierung gebaut ist, zu einem Gitter verbindet. Manche Exporte zeichnen gar keine Umrandung: Jede Zelle ist eine gefüllte Box, getrennt von ihren Nachbarn durch einen weißen Zwischenraum von 1 bis 3 Punkten. Jede Box liefert ihre vier Kantenlinien, aber die rechte Kante einer Zelle und die linke Kante der nächsten liegen, sagen wir, 2 Punkte auseinander, und der Test, der entscheidet, ob zwei Linien zum selben Gitter gehören, erlaubt nur RulingTolerance, 1 Punkt. Ohne Einrasten ist jede Zelle eine Insel aus vier Linien, die ein 1x1-Gitter beschreiben, nichts erreicht MinColumns oder MinRows (beide 2 als Default), und der Linien-Durchgang meldet keine Tabelle auf einer Seite, die offensichtlich eine hat

Der Einrast-Schritt sammelt jede im Spiel befindliche X-Koordinate, also die Position jeder vertikalen Linie plus Start und Ende jeder horizontalen, und jede Y-Koordinate ebenso. Jede Liste wird sortiert und in Cluster geteilt, wo immer zwei Nachbarn um mehr als die Toleranz abweichen; jedes Cluster wird durch seinen Mittelwert ersetzt, und jede Position, jeder Start und jedes Ende rückt dann zum nächsten Zentrum. Kanten bei 230.0 und 232.0 werden beide 231.0, die zwei Zellen teilen eine Linie, und die horizontalen Linien dehnen sich mit, damit die Ecken sich treffen

Kollineare Teilstücke, die sich innerhalb von RulingTolerance berühren oder überlappen, werden zu einzelnen Linien zusammengefasst. Erst danach läuft der Gitterdetektor und vergleicht die Linien paarweise; eine 30-Zeilen-Tabelle, die als 720 Umrandungsstücke ankam, erreicht diesen Vergleich als ein paar Dutzend Linien

Auf einem Stroke-Gitter ändert der Schritt nichts, denn Koordinaten, die schon übereinstimmen, rasten in sich selbst ein. Der Haken: Verkettung hat keine eigene Breitengrenze. Eine Folge von Werten im Abstand von je 3 Punkten, bei 100, 103, 106 und 109, kollabiert zu einem Zentrum bei 104.5, obwohl die äußeren Werte 9 Punkte auseinander liegen. Beim 4-Punkt-Default beißt das nur bei Spalten, die schmaler als ein Zeichen sind, also können Office-Ausgaben beim 4-Punkt-Default bleiben. In Richtung 1 oder 2 senken, wenn ein Formular absichtlich schmale Spalten hat (Kontrollkästchen, einstellig-pro-Zelle Kontonummernfelder), und auf 0 setzen, um das Einrasten abzuschalten. Die Linien-Strategie allein unter drei Einstellungen zu fahren zeigt, von welchem Mechanismus eine Seite abhängt:

// Nur die Linien-Strategie, damit die Whitespace-Erkennung das Ergebnis nicht überdeckt
function CountRuledTables(Pdf: TPdf; FilledRulings: Boolean;
  SnapTolerance: Double): Integer;
var
  Options: TPdfTableExtractionOptions;
begin
  Options := TPdfTableExtractionOptions.Default;
  Options.DetectWhitespaceTables := False;
  Options.DetectFilledRulings := FilledRulings;
  Options.RulingSnapTolerance := SnapTolerance;
  Result := Length(Pdf.ExtractTables(Options));
end;

// Erwartung für eine Tabelle, die nur als schattierte Zellen mit 2 pt Zwischenräumen gezeichnet ist:
//   nur Stroke             -> 0  (überhaupt keine Stroke-Geometrie)
//   gefüllte Boxen, Snap 4 -> 1  (Kanten des Zwischenraums teilen eine Linie)
//   gefüllte Boxen, Snap 0 -> 0  (jede Zelle bleibt eine 1x1-Insel)
Writeln('stroke only:          ', CountRuledTables(Pdf, False, 4.0));
Writeln('filled boxes, snap 4: ', CountRuledTables(Pdf, True, 4.0));
Writeln('filled boxes, snap 0: ', CountRuledTables(Pdf, True, 0.0));

Sinkt der dritte Zähler unter den zweiten, verlässt sich die Seite auf das Einrasten, und das ist die Seite, die man vor dem Senken der Toleranz per Auge prüft

Tabellenlinien in Form-XObjects

Layout-Tools packen eine Tabelle oder den ganzen Seitenkörper häufig in ein Form-XObject und malen es mit Do. ISO 32000-1 §8.10.1 sagt, dass die Form-Matrix beim Malen der Form mit der aktuellen Transformationsmatrix konkateniert wird, also ist ein Rechteck in der Form im Form-Raum geschrieben und erreicht den Seitenraum erst nach zwei oder mehr Transformationen. Mit gesetztem IncludeFormXObjects, dem Default, steigt PDFium Component in jedes Form-Objekt hinab, kombiniert die Objekt-Matrix mit der Matrix des Elters und reicht die kombinierte Matrix an jedes Kind weiter, also landet eine als 72 700 468 0.5 re f in einer verschobenen Form gezeichnete Umrandung dort, wo der Viewer sie zeigt. Der Abstieg stoppt bei acht Ebenen verschachtelter Formen

Die Reihenfolge dieser Kombination zählt. Ein Punkt in der Form läuft zuerst durch die Objekt-Matrix und dann durch die Eltern-Matrix; vertauscht man die Operanden, wird der Translationsterm im falschen Raum angewandt, also landet eine Linie, die oben auf der Seite hingehört, nahe am Ursprung oder außerhalb der Seite. Dieselbe Falle stellt sich immer, wenn man Matrizen selbst baut, und der Artikel zu Matrix-Prepend versus Append geht sie mit einem Rotations-Pivot durch

Warum ist das Default-Linienbudget 16384?

Das Default-MaxRulingSegments von 16384 spiegelt, wie viele Stücke ein Umrandungs-Export pro Zelle produziert. Eine mit Stroke gezogene 30-Zeilen-, 6-Spalten-Tabelle braucht 38 Liniensegmente: 31 horizontale und 7 vertikale. Dieselbe Tabelle als gefüllte Boxen exportiert kann vier Umrandungsstücke pro Zelle tragen, 720 vor dem Mergen, und jede Zelle zu schattieren legt vier weitere Kantenlinien pro Zelle oben drauf, 1440 insgesamt. Zwei solche Tabellen auf einer Seite brauchen schon nahe 3000

Das Budget zu überschreiten ist ein Fehler, und er zeigt sich auch als einer. ExtractTables wirft EPdfError mit der Meldung „Table ruling-segment budget exceeded“, liefert kein partielles Gitter, und der Whitespace-Durchgang für diese Seite läuft ebenfalls nicht. Ein knappes Budget ist für nicht vertrauenswürdigen Input vernünftig, wo eine gezüchtete Seite Millionen winziger Boxen halten könnte, aber dann muss der Aufrufer „zu komplex für dieses Budget“ von „keine Tabellen auf dieser Seite“ unterscheiden können:

function TryExtractTables(Pdf: TPdf; Budget: Integer;
  out Tables: TPdfTables): Boolean;
var
  Options: TPdfTableExtractionOptions;
begin
  Options := TPdfTableExtractionOptions.Default;
  Options.MaxRulingSegments := Budget;     // 16384 als Default
  try
    Tables := Pdf.ExtractTables(Options);
    Result := True;
  except
    on E: EPdfError do
    begin
      // LogWarning ist Ihre eigene Logging-Routine, nicht Teil der Bibliothek
      LogWarning(Format('Page %d: %s', [Pdf.PageNumber, E.Message]));
      Tables := nil;
      Result := False;                     // Budget überschritten oder ungültige Optionen
    end;
  end;
end;

// Ein False-Ergebnis heißt „nicht entschieden“, was sich von einem leeren Array unterscheidet
if not TryExtractTables(Pdf, 4096, Tables) then
  QueueForReview(Pdf.FileName, Pdf.PageNumber);  // ebenfalls Ihre eigene Routine

Derselbe Exception-Typ deckt auch das Wort-Budget und ungültige Optionen ab, also sagt die protokollierte Meldung, was davon in einer Review-Queue vorliegt

Wo der Linien-Pfad übergibt

Die Linienerkennung läuft zuerst, die Whitespace-Erkennung zweite, und zwei Regeln halten sie davon ab, sich gegenseitig zu treten. Wörter, deren Zentren in einem Gitter liegen, das der Linien-Durchgang bereits gemeldet hat, werden entfernt, bevor die Whitespace-Erkennung startet, also wird eine Tabelle nie doppelt gemeldet. Eine Whitespace-Spaltengrenze muss außerdem ein textfreier vertikaler Korridor über jede Zeile sein, die sie trennt, was Blocksatz-Absätze davon abhält, als Tabellen zu punkten; der Artikel zu Whitespace-Tabellen-Fehlalarmen behandelt diese Regel. Gefüllte Rechtecke zu lesen verschiebt Tabellen aus Office-Exporten aus dem Whitespace-Pfad in den Linien-Pfad

Weil Linien aus Pfadobjekten kommen und Text von der Textseite, produziert eine Seite ohne Textebene weiterhin das Gitterskelett mit jeder Zelle leer. Die Konfidenz eines Liniengitters ist 0.88 plus 0.12 mal dem Anteil der Zellen mit Text, also meldet ein leeres Skelett exakt 0.88, und die Zellzählung im ersten Listing zeigt 0 Zellen mit Text. Diese Kombination ist das Signal, zuerst OCR laufen zu lassen, wie in Hinzufügen einer durchsuchbaren Textebene mit OCR beschrieben. Gefüllte Formen mit Kurven oder nicht-rechteckigen Umrandungen tragen nichts bei, also fällt eine Tabelle, deren Zellen als gefüllte Rundrechtecke gezeichnet sind, an die Whitespace-Erkennung. Eine Tabelle ohne Umrandungen und ohne Schattierung gehört zur Whitespace-Strategie, die im Artikel zur Tabellenerkennung und -extraktion beschrieben wird, und wenn selbst das nicht reicht, sind die Wortboxen und Blöcke aus strukturiertem Text und Lesereihenfolge das Rohmaterial für einen Reader, der für eine Dokumentfamilie geschrieben wird

Die TableExtractionLab-Demo, die mit der Komponente kommt, hat ein Kontrollkästchen für DetectFilledRulings, also kann man einen Export laden und das Gitter ohne eine Zeile Code erscheinen und verschwinden sehen. Optionen, Record-Typen und der Rest der Extraktions-API sind auf der PDFium Component for Delphi-Produktseite gelistet