Gefüllte Rechtecke als Tabellenlinien im PDFium Delphi

Die Tabellenextraktion des PDFium Component behandelt ab Version 3.117.0 ein dünnes gefülltes Rechteck als Tabellenlinie. Mit aktiviertem DetectFilledRulings, was die Voreinstellung ist, wird eine gefüllte achsenparallele Box, die nicht dicker als MaxRulingThickness (3 Punkte) ist, zu einer Linie entlang ihrer Längsachse, eine größere gefüllte Box liefert ihre vier Kanten, und jede Linienkoordinate wird innerhalb von RulingSnapTolerance (4 Punkte) eingerastet, bevor das Gitter zusammengebaut wird. Tabellen aus Word, Google Docs und Browsern erreichen den Linien-Detektor deshalb als vollständige Gitter, statt als Fragmente in die Whitespace-Erkennung durchzurutschen

Der frühere Artikel zur Tabellenerkennung und -extraktion stellte fest, dass die Linien-Erkennung die gezeichneten Linien benutzt und dass jedes mit Stroke gezeichnete Pfadsegment in Seitenkoordinaten transformiert wird. Dieser Satz war wahr und unvollständig. Das Zählen der Pfadobjekte über einen Satz von 13 realen Beispieldokumenten zeigte, dass 9 von ihnen überhaupt keinen Stroke-Pfad enthalten, während jede ihrer Seiten Hunderte von gefüllten Rechtecken mit 0,5 bis 1 Punkt Dicke trägt. Der Stroke-only-Detektor sah nichts, jede Seite fiel an die Whitespace-Erkennung, und die Ausgabe war eine Streuung kleiner Fragmente statt Tabellen. Das in 3.116.4 ergänzte Compact-Columns-Preset milderte das auf Fragmentebene; die Wurzelursache war, dass der Detektor den falschen Zeichenoperator las

Warum hat eine aus Word exportierte Tabelle keine Stroke-Linien?

Eine Textverarbeitung denkt sich eine Umrandung nicht als Linie; sie denkt sie sich als Box mit einer Breite und malt diese Box mit einer Füllung. ISO 32000-1 §8.5.2.1 definiert den re-Operator als Anfügen eines 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-Zellumrandung kommt als x y w 0.5 re f heraus, und die Stroke-Maschinerie – Linienbreite, Joins und Dash-Muster eingeschlossen – läuft nie. Zellschattierung ist dieselbe Konstruktion mit einer größeren Box. Ein mit m, l und S gezogenes Liniengitter ist, was der ursprüngliche Detektor erwartete, und es ist das, was fast nichts aus einer Office-Anwendung exportiert erzeugt:

% 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, für die der ursprüngliche Detektor geschrieben war
72 700 m 540 700 l S

Für einen Detektor, der FPDFPath_GetDrawMode nur fragt, ob das Stroke-Flag gesetzt ist, sind beide gefüllten Boxen unsichtbar. Die Wörter in den Zellen erreichen dann die Whitespace-Erkennung, wo Spalten mit einem 6-Punkt-Zwischenraum unter der Voreinstellung MinColumnGap von 12 Punkten liegen, und zurück kommt, welche Teilmenge von Zeilen gerade gut genug ausgerichtet ist, um MinRows zu bestehen. Das ist das Fragment-Verhalten, und noch so viel Parameterjustage macht daraus nicht das Gitter, das der Autor gezeichnet hat

Wie macht PDFium Component aus einer gefüllten Box eine Tabellenlinie?

TableCollectObjectRulings inspiziert jedes Pfadobjekt, einen Subpfad nach dem anderen. Der Draw-Mode kommt von FPDFPath_GetDrawMode; ein Pfad zählt als gefüllt, wenn DetectFilledRulings an ist und der Fill-Mode nicht none ist. Jeder Punkt wird durch die Objekt-Matrix transformiert und gesammelt, bis zu MaxSubpathPoints (8) pro Subpfad, und jedes Kurvensegment markiert den Subpfad als gekrümmt. Schließt sich der Subpfad oder beginnt ein neues MoveTo, entscheidet FlushSubpath, was er war: Ein gekrümmter Subpfad wird verworfen, ebenso jedes geschlossene Polygon, dessen Punkte nicht alle auf mindestens einer Achse innerhalb von PointTolerance (0,05 Punkte) an den Kanten der Bounding Box sitzen. Ein Dreieck, ein Chevron oder ein abgerundeter Tab wird nie zur Tabellenlinie, was Deko-Grafik aus dem Gitter fernhält

Was überlebt, ist ein achsenparalleles Rechteck, klassifiziert über seine Bounding Box. Breite auf oder unter MaxRulingThickness mit Höhe darüber ergibt eine vertikale Linie im horizontalen Zentrum, die die Box von unten nach oben überspannt; der Spiegelfall ergibt eine horizontale Linie. Beide Dimensionen über dem Schwellenwert heißt schattierte Zelle, und die Box liefert vier Linien, eine pro Kante. Beide Dimensionen auf oder unter dem Schwellenwert liefern nichts, also wird ein 2-Punkt-quadratisches Aufzählungszeichen nicht für eine Linie gehalten. Ein mit Stroke gezogener Pfad nimmt den älteren Weg über AddLine, eine Linie pro achsenparallelem Segment, also wird ein mit S gezogenes Gitter genau wie vorher behandelt, und ein Pfad, der mit Fill und Stroke zugleich gemalt wird, produziert überlappende Stücke, die der Merge-Durchgang kollabiert:

uses
  PDFium;

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

    Options := TPdfTableExtractionOptions.Default;
    // das sind die 3.117.0-Voreinstellungen, der Deutlichkeit halber ausgeschrieben
    Options.DetectFilledRulings := True;     // dünne gefüllte Boxen werden zu Tabellenlinien
    Options.MaxRulingThickness := 3.0;       // Punkte; dickere Boxen zählen als Schattierung
    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';
      Writeln(Format('%dx%d %s, confidence %.2f',
        [Tables[I].RowCount, Tables[I].ColumnCount, Mode,
         Tables[I].Confidence]));
    end;
  finally
    Pdf.Free;
  end;
end;

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 in eigener Farbe, und benachbarte Boxen sind durch einen 1 bis 3 Punkt breiten weißen Zwischenraum getrennt. Jede Box liefert vier Kantenlinien, aber die rechte Kante einer Zelle und die linke Kante der nächsten liegen 2 Punkte auseinander, und der Konnektivitätstest benutzt RulingTolerance, das standardmäßig auf 1 Punkt steht. Ohne Einrasten bildet jede Zelle ihre eigene Zusammenhangskomponente aus vier Linien, keine Komponente erreicht MinRows, und die Seite meldet nichts. TableSnapRulings sammelt jede im Spiel befindliche X-Koordinate (die Position jeder vertikalen Linie plus Start und Ende jeder horizontalen) und ebenso jede Y-Koordinate, sortiert jede Liste, clustert sie, indem es Werte verkettet, deren Nachbar um nicht mehr als die Toleranz abweicht, ersetzt jedes Cluster durch seinen Mittelwert und verschiebt dann jede Position, jeden Start und jedes Ende zum nächsten Cluster-Zentrum. Die beiden Seiten eines Zwischenraums werden dieselbe Linie, und die Konnektivität hält

Das Einrasten läuft vor TableMergeRulings, das die Linien sortiert und kollineare Stücke, die innerhalb von RulingTolerance berühren oder überlappen, zusammenfügt, und beide laufen, bevor TableDetectRuled die Daten überhaupt sieht, also skaliert die paarweise Konnektivitätsprüfung mit der Zahl der Gitterlinien statt mit der Zahl der Zellfragmente. Auf einem mit Stroke gezogenen Gitter sind die Durchgänge harmlos, denn Koordinaten, die schon identisch waren, rasten in sich selbst ein. Das eine, was man im Kopf behalten sollte: Chain-Clustering hat keine eigene Breitengrenze, eine Folge von Koordinaten im Abstand von je 3 Punkten kollabiert zu einem einzigen Zentrum. Beim 4-Punkt-Default betrifft das nur Spalten, die schmaler als ein Zeichen sind, aber wenn ein Dokument echte 3-Punkt-Zwischenräume hat, die getrennt bleiben müssen, senken Sie die Toleranz oder setzen Sie sie auf 0, um das Einrasten abzuschalten:

// Linien-Strategie isolieren und vergleichen, was jede Einstellung auf einer Seite sieht
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;

// Ein Word-Export meldet typischerweise 0, N und danach weniger als N:
// Stroke-only sieht nichts, das Einrasten verbindet die schattierten Zellen,
// und deaktiviertes Einrasten lässt jede schattierte Zelle als eigene Insel zurück
Writeln(CountRuledTables(Pdf, False, 4.0));
Writeln(CountRuledTables(Pdf, True, 4.0));
Writeln(CountRuledTables(Pdf, True, 0.0));

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 legt fest, dass die Form-Matrix beim Malen der Form mit der aktuellen Transformationsmatrix konkateniert wird, also lebt ein Rechteck in der Form im Form-Raum und landet erst nach zwei oder mehr Transformationen auf der Seite. TableCollectObjectRulings steigt in Form-Objekte hinab, wenn IncludeFormXObjects gesetzt ist: Er liest die Objekt-Matrix, kombiniert sie über TableMultiplyMatrix mit der Eltern-Matrix, deren Argumentreihenfolge heißt „durch die erste Matrix mappen, dann durch die zweite“, und zählt die Kinder mit FPDFFormObj_CountObjects und FPDFFormObj_GetObject auf, wobei er die kombinierte Matrix weiterreicht. Nesting tiefer als MaxFormDepth (8) wird stillschweigend übersprungen, was eine Absicherung gegen pathologische Dateien ist und keine Grenze, die ein realer Export auch nur erreicht. Warum die Multiplikationsreihenfolge zählt, ist derselbe Grund wie im Artikel zu Matrix-Prepend versus Append: Die Operanden zu tauschen verschiebt den Translationsterm, und eine Linie, die oben auf der Seite landen sollte, landet stattdessen im Ursprung

Warum hat sich das Linien-Budget vervierfacht?

Das voreingestellte MaxRulingSegments stieg in 3.117.0 von 4096 auf 16384, weil Umrandungen pro Zelle in weit größerer Zahl ankommen als mit Stroke gezogene Gitterlinien. Eine 30-zeilige, 6-spaltige Tabelle aus Stroke-Linien besteht aus 38 Liniensegmenten. Dieselbe als gefüllte Boxen exportierte Tabelle zählt bis zu vier Umrandungen pro Zelle, 720 Stücke vor dem Mergen, und ein Formular mit schattierten Zellen verdoppelt das. Zwei solche Tabellen auf einer Seite hätten das alte Budget erschöpft. Das Budget wird in TableAppendRuling über Check erzwungen, das eine EPdfError mit der Meldung „Table ruling-segment budget exceeded“ wirft; es gibt kein degradiertes Ergebnis, kein partielles Gitter, und der Whitespace-Durchgang läuft ebenfalls nicht. Wer für nicht vertrauenswürdigen Input ein eigenes, engeres Budget setzt, fängt die Exception und entscheidet selbst, statt ein leeres Ergebnis als „keine Tabellen“ zu lesen:

Options := TPdfTableExtractionOptions.Default;
Options.MaxRulingSegments := 2048;        // absichtlich eng für nicht vertrauenswürdigen Input
try
  Tables := Pdf.ExtractTables(Options);
except
  on E: EPdfError do
  begin
    Log(E.Message);                       // 'Table ruling-segment budget exceeded'
    Options.MaxRulingSegments := 16384;   // der 3.117.0-Default
    Tables := Pdf.ExtractTables(Options);
  end;
end;

Gemessene Ergebnisse und wo der Ansatz endet

Auf denselben 13 Beispieldokumenten ging die Extraktion von 43 Tabellen, 9 davon als Liniengitter und 34 als Whitespace-Fragmente oder Fehlalarme, auf 41 Liniengitter-Tabellen und null Whitespace-Fehlalarme. Ein Teil dieser Bereinigung gehört zu zwei Begleitänderungen in 3.117.0: Wörter, die bereits von einem Liniengitter beansprucht wurden, werden entfernt, bevor die Whitespace-Erkennung läuft, also wird eine Tabelle nie doppelt gemeldet, und eine Whitespace-Spaltengrenze muss jetzt ein textfreier Korridor über jede Zeile sein, die sie trennt – das hat Blocksatz-Absätze davon abgehalten, als 5x4-Tabellen zu punkten. Der gefüllte-Rechtecke-Reader ist das, was die Tabellen selbst aus der Fragment-Spalte in die Linien-Spalte verschoben hat

Die Grenzen sollte man klar benennen. Eine Seite ohne Textebene liefert weiterhin das Gitterskelett, jede Zelle leer, denn Tabellenlinien kommen aus der Geometrie und Text von der Textseite; gescannte Seiten brauchen zuerst OCR. Gefüllte Formen mit Kurven, abgerundeten Ecken oder nicht-rechteckigen Umrandungen fallen komplett weg, also braucht eine Tabelle, deren Umrandungen als Rundrechteck-Konturen gezeichnet sind, weiterhin die Whitespace-Erkennung. Eine Tabelle ohne Umrandungen und ohne Schattierung bleibt von all dem unberührt und bleibt die Domäne der Whitespace-Strategie, die im Artikel zur Tabellenextraktion beschrieben wird; wenn selbst das nicht reicht, sind die Wortboxen und Blöcke aus strukturiertem Text und Lesereihenfolge das Rohmaterial für einen domänenspezifischen Reader. Die TableExtractionLab-Demo, die mit der Komponente kommt, legt DetectFilledRulings in ihrem Optionspanel offen – der schnellste Weg zu sehen, wie ein gegebener Export mit und ohne es aussieht; die vollständige API ist auf der PDFium Component for Delphi-Seite beschrieben