Valse PDF-tabellen uit uitgevulde tekst voorkomen in Delphi

Een pagina uitgevulde lopende tekst kan uit een whitespace-tabeldetector terugkomen als een raster van meerdere kolommen, elke cel met een afgebroken halfzinnen en een confidencescore ver boven elke drempel waar je aan zou denken te draaien. Er staat geen tabel op die pagina. De detector vond woordgaten breed genoeg om als kolomscheiders door te gaan en een paar opeenvolgende regels waar die gaten op vrijwel dezelfde X-positie landden, en op uitlijning alleen ziet dat er precies zo uit als een tabel. Het antwoord is stoppen met het beoordelen van een kolomgrens per rij en je afvragen of er een strook leeg papier de pagina tussen de kolommen doorloopt

Waarom slaagt uitgevulde tekst voor een whitespace-tabeltest?

Uitgevulde tekst slaagt omdat een uitgevulde regel een rij woorden is, gescheiden door gaten die de layoutengine oprekte, en zodra een opgerekt gat de kolomdrempel passeert, onderscheidt niets op die ene regel hem van een gutter. De whitespace-strategie in PDFium Component werkt zoals de meeste whitespace-detectors. TPdf.ExtractTables groepeert word boxes in visuele rijen, splitst elke rij waar de horizontale afstand van het ene woord naar het volgende ten minste MinColumnGap is (12 points in TPdfTableExtractionOptions.Default), en clustert de linker randen van de ontstane woordgroepen tot kolomankers binnen AlignmentTolerance, dat op 3 points defaultt. Een anker overleeft alleen als hij op ten minste MinRows rijen terugkomt, en elke rij van de kandidaat moet ten minste MinColumns verschillende ankers raken. Voor een echte uitgelijnde tabel is die regel correct, en het is de regel die in het overzicht van tabeldetectie staat beschreven

De rekenkunde aan de prozekant is minder toegeeflijk dan hij eruitziet. Stel dat een regel van 10 points in een nieuwsbriefkolom van 180 points 30 points voor de rechtermarge eindigt omdat het volgende woord niet meer paste, en de regel maar drie woorden tussen spaties telt omdat zijn woorden lang zijn. Een uitvulengine verdeelt die 30 points over de drie spaties, zodat elk groeit van ruwweg 2,5 points naar 12,5 points en de default MinColumnGap passeert. Een tweede regel heeft maar een opgerekt gat nodig waarvan het volgende woord binnen 3 points van dat van de eerste regel begint, en de detector heeft een kandidaat van twee rijen en twee kolommen

Hoe de uitrekking is gecodeerd, doet er niet toe. ISO 32000-1 §9.3.3 past word spacing (Tw) alleen toe op de single-byte character code 32, dus producers met multi-byte fonts positioneren woorden meestal met numerieke aanpassingen in een TJ-array (§9.4.3); hoe dan ook komen de word boxes identiek uit de bus. De laatste regel van elke alinea wordt aan de marge gezet en draagt gewone spaties, en daarom dekken false positives meestal de romp van een alinea en stoppen ze een regel voor het einde

Een snelle manier om je eigen corpus te controleren is de detector draaien over documenten waarvan je weet dat ze alleen proze zijn, zoals brieven of persberichten, en elke whitespace-tabel printen die hij meldt. De verwachte uitvoer daarop is niets

uses
  SysUtils, PDFium;

// Zet elke whitespace-uitgelijnde tabel in het geladen document op een lijst, zodat
// pagina's waarvan je weet dat ze alleen lopende tekst bevatten snel gecontroleerd kunnen worden
procedure ReportWhitespaceTables(Pdf: TPdf; MinRows: Integer = 2);
var
  Options: TPdfTableExtractionOptions;
  Tables: TPdfTables;
  I: Integer;
begin
  Options := TPdfTableExtractionOptions.Default;  // MinColumnGap 12, AlignmentTolerance 3
  Options.MinRows := MinRows;
  Tables := Pdf.ExtractDocumentTables(Options);   // herstelt de actieve pagina
  for I := 0 to High(Tables) do
    if Tables[I].DetectionMode = ptdmWhitespace then
      Writeln(Format('page %d: %dx%d whitespace table, confidence %.2f, ' +
        'first cell "%s"',
        [Tables[I].PageNumber, Tables[I].RowCount, Tables[I].ColumnCount,
         Tables[I].Confidence, Tables[I].Cells[0].Text]));
end;

Wat elke drempel kost

Elke drempel op rijniveau ruilt een klasse documenten tegen een andere, en dat is de reden om ze voor dit probleem met rust te laten. MinColumnGap op 20 points zetten schrapt de compacte kolommen van dichte financiele overzichten, waar de gutter tussen een labelkolom en zijn waarden vaak nauwelijks breder is dan de default. MinRows op 3 zetten gooit echte tabellen van twee rijen weg en verlaagt alleen de kans voor lange alinea's, want een pagina proze biedt vele kansen voor drie regels die uitlijnen. AlignmentTolerance onder 3 points aanscherpen begint echte kolommen te splitsen waarvan de linker randen licht afdwalen, zoals op gescande pagina's met een OCR-tekstlaag gebeurt

MinConfidence oogt als het natuurlijke filter en is de zwakste van de vier. Een whitespace-tabel scoort in PDFium Component 0,58 plus 0,30 keer het aandeel niet-lege cellen, begrensd op 0,88, dus de score meet hoe vol het raster is. Een alineafragment vult elke cel, wat betekent dat een proze-false positive bij de top van het bereik scoort terwijl een echte tabel met lege cellen lager uitkomt

Twee regels uitgevulde proze en twee rijen van een tabel met twee kolommen kunnen identieke woordgroepen op identieke ankers opleveren. Het bewijs dat ze scheidt, zit tussen de rijen

Een echte kolomgrens is een verticale corridor

Een echte kolomgrens is een verticale strook van de pagina die op elke rij die hij scheidt, vrij van tekst blijft. Een tabel heeft er vanzelf een tussen elk kolompaar, want zijn cellen zijn tegen gedeelde X-posities gezet. Een uitgevulde alinea rekt zijn spaties op elke regel op een andere horizontale positie, dus geen strook overleeft meer dan een regel of twee. PDFium Component test precies dit nadat de woordgroepen van een kandidaat aan ankerkolommen zijn toegekend. Per paar aangrenzende kolommen levert elke rij met inhoud in beide cellen het interval van de rechterrand van de woorden van de linkercel tot de linkerrand van de woorden van de rechtercel; de intervallen worden over rijen doorsneden, en de hele kandidaat wordt verworpen wanneer de doorsnede smaller is dan de helft van MinColumnGap — 6 points bij de default

Op lastige echte tabellen doen twee details ertoe. Rijen waarvan een van beide cellen leeg is, stemmen niet, dus een tabel met lege cellen, of een koprij die over minder kolommen loopt dan de romp, komt er nog doorheen. En de corridorbreedte is afgeleid van MinColumnGap in plaats van een eigen optie te zijn, want beide waarden beschrijven dezelfde fysieke zaak: de ruimte die een ontwerper tussen kolommen laat. Het halveren laat ruimte voor de rij waarin een lange entry in de linkerkolom dicht bij de volgende komt

De controle is klein genoeg om in je eigen layoutcode na te bouwen; de cellijsten hieronder zijn je eigen structuur, een array van woordindices per cel in row-major volgorde

uses
  Math, PDFium;

type
  TIndexList = array of Integer;
  TCellIndexes = array of TIndexList;   // eigen structuur: Row * ColumnCount + Column

// Geeft False terug wanneer een aangrenzend kolompaar geen tekstvrije verticale
// corridor heeft, ten minste MinColumnGap / 2 breed over de rijen die hem gebruiken
function HasTextFreeCorridors(const Words: TPdfWordBoxes;
  const Cells: TCellIndexes; RowCount, ColumnCount: Integer;
  MinColumnGap: Double): Boolean;
var
  Col, Row, I, LeftCell, RightCell, Supported: Integer;
  CorridorLeft, CorridorRight, RowLeft, RowRight: Double;
begin
  for Col := 0 to ColumnCount - 2 do
  begin
    CorridorLeft := -MaxDouble;
    CorridorRight := MaxDouble;
    Supported := 0;
    for Row := 0 to RowCount - 1 do
    begin
      LeftCell := Row * ColumnCount + Col;
      RightCell := LeftCell + 1;
      if (Length(Cells[LeftCell]) = 0) or (Length(Cells[RightCell]) = 0) then
        Continue;                             // lege cellen stemmen niet
      RowLeft := -MaxDouble;
      RowRight := MaxDouble;
      for I in Cells[LeftCell] do
        RowLeft := Max(RowLeft, Words[I].Rect.Right);
      for I in Cells[RightCell] do
        RowRight := Min(RowRight, Words[I].Rect.Left);
      CorridorLeft := Max(CorridorLeft, RowLeft);
      CorridorRight := Min(CorridorRight, RowRight);
      Inc(Supported);
    end;
    if (Supported > 0) and
       (CorridorRight - CorridorLeft < MinColumnGap * 0.5) then
      Exit(False);
  end;
  Result := True;
end;

Gelijnde tabellen buiten de whitespace-ronde houden

Een gelijnde tabel zou twee keer worden gevonden als de whitespace-ronde elk woord op de pagina zag, want een schone gelijnde tabel is vanzelf ook een perfect uitgelijnde whitespace-tabel. Op zichzelf zou een meer-dan-de-helft-overlappingsregel een kandidaat die de onderste rijen van een gelijnde tabel combineert met een paar uitgelijnde tekstregels eronder door de verhouding laten komen en als tweede, grotere tabel naar buiten laten komen die in zijn buurman bloedt

Als zowel DetectRuledTables als DetectWhitespaceTables aan staan, wat de default is, draait ExtractTables daarom eerst de gelijnde ronde en verwijdert elk woord waarvan het middelpunt binnen de grenzen van een gelijnde tabel ligt voordat de whitespace-ronde begint. Het middelpunt wordt gebruikt in plaats van volledige insluiting zodat een woord dat met een fractie van een point over een rand struikelt, de tabel volgt waar hij visueel bij hoort. De whitespace-strategie ziet daarna alleen vrije woorden, en een kleine tabel zonder lijnen die direct onder een gelijnd raster staat, wordt op zijn eigen rijen beoordeeld

Waarom kan "Purpose of Request:" eruit komen als "of Purpose Request:"?

Woorden in een cel komen in de verkeerde volgorde uit wanneer de code die "zelfde regel" beslist verticale middens vergelijkt, want word boxes opgebouwd uit glyph boxes delen geen midden, zelfs als ze een basislijn delen. FPDFText_GetCharBox geeft de strakke box van de inkt van elke glyph in paginaruimte, geen box opgevuld tot de ascent en descent van het font, en een word box is de unie van de boxes van zijn tekens. In een formulierlabel als "Purpose of Request:" dragen de woorden "Purpose" en "Request:" descenders en "of" niet, dus de box voor "of" is korter en zijn midden zit een paar points hoger. Een routine die op midden-Y sorteert met een tolerantie van 1 point voor zelfde-regel en daarna op linkerrand, zet "of" op een eigen regel boven de andere twee en emitteert hem eerst

PDF biedt geen shortcut. ISO 32000-1 §9.4.4 zet glyphs neer op verplaatsing langs de basislijn, en de enige verticale metrieken in het bestand zijn per font: Ascent, Descent en FontBBox in de fontdescriptor (§9.8.1). Niets zegt dat twee glyphs een regel delen. De strakke boxes die selectieaccenten goed laten ogen, behandeld in tekstregelselectie met PDFium char boxes, zijn slechte invoer voor een middenafstandsvergelijking

PDFium Component bouwt celtekst in plaats daarvan op overlap. Een woord sluit zich aan bij een visuele regel als zijn verticale overlap met de lopende grenzen van de regel ten minste 25 procent van de kleinste van de twee hoogten is, of als de twee middens binnen een point van elkaar zitten; elke regel wordt daarna op linkerrand gesorteerd, en regels worden met een CR LF-paar samengevoegd. "Purpose" en "of" overlappen over de hele x-hoogte, ruim meer dan een kwart van de kortere box, dus ze belanden op een regel en lezen in volgorde

Tekstregels op overlap groeperen in je eigen code

Dezelfde valkuil loert in elke PDF-layoutcode die "zelfde regel" beslist door middens te vergelijken tegen een vaste tolerantie. Descenders zijn de mildste aanleiding. Vette labels naast kleinere waarden, superscript-voetnootmarkeringen en ruisige OCR-boxes verschuiven middens allemaal met meer dan elke tolerantie die naastgelegen regels van 10-point tekst op 12-point leading nog scheidt. Overlapverhouding kijkt niet naar grootte: twee boxes op een basislijn overlappen over hun gedeelde x-hoogte, en twee boxes op naburige regels overlappen met niets

TPdf.PageWordBoxes geeft elk woord op de actieve pagina met zijn paginaruimte-rechthoek in Rect terug, dus een pagina in visuele regels groeperen kost een predicate en een kort lusje

uses
  Math, PDFium;

function SameVisualLine(const A, B: TPdfRectangle): Boolean;
var
  Overlap, MinHeight: Double;
begin
  Overlap := Min(A.Top, B.Top) - Max(A.Bottom, B.Bottom);
  MinHeight := Min(A.Top - A.Bottom, B.Top - B.Bottom);
  Result := (MinHeight > 0) and (Overlap >= MinHeight * 0.25);
end;

procedure GroupPageIntoLines(Pdf: TPdf; out Lines: TArray<TPdfWordBoxes>);
var
  Words: TPdfWordBoxes;
  Bounds: TArray<TPdfRectangle>;   // lopende unie per regel
  I, J, Found: Integer;
begin
  Words := Pdf.PageWordBoxes;            // heeft een actieve pagina nodig (Pdf.PageNumber)
  Lines := nil;
  Bounds := nil;
  for I := 0 to High(Words) do
  begin
    Found := -1;
    for J := High(Lines) downto 0 do
      if SameVisualLine(Bounds[J], Words[I].Rect) then
      begin
        Found := J;
        Break;
      end;
    if Found < 0 then
    begin
      SetLength(Lines, Length(Lines) + 1);
      SetLength(Bounds, Length(Bounds) + 1);
      Found := High(Lines);
      Bounds[Found] := Words[I].Rect;
    end;
    SetLength(Lines[Found], Length(Lines[Found]) + 1);
    Lines[Found][High(Lines[Found])] := Words[I];
    Bounds[Found].Left := Min(Bounds[Found].Left, Words[I].Rect.Left);
    Bounds[Found].Right := Max(Bounds[Found].Right, Words[I].Rect.Right);
    Bounds[Found].Top := Max(Bounds[Found].Top, Words[I].Rect.Top);
    Bounds[Found].Bottom := Min(Bounds[Found].Bottom, Words[I].Rect.Bottom);
  end;
  // sorteer elke regel op Rect.Left voor je hem leest: PageWordBoxes geeft
  // woorden in content-stream-volgorde, wat niet de visuele volgorde hoeft te zijn
end;

Het predicate is het deel dat het kopieren waard is. Voor alles boven een snelle dump, begin bij het gestructureerde tekstmodel, dat al blocks, regels en een leesvolgordebron draagt, zoals beschreven in gestructureerde PDF-tekstextractie met leesvolgorde

Wat tabel-aanroepers nog zelf bepalen

Tabel-aanroepers krijgen de corridortest, het gelijnd-eerst-woordfilter en overlapgebaseerde celtekst zonder aan hun opties te zitten. De drempel voor de corridor staat vast op de helft van MinColumnGap, dus de ene waarde waar je aan draait voor gutterbreedte regeert beide. De whitespace-strategie houdt een ondergrens van twee rijen zelfs als MinRows op 1 staat; alleen de gelijnde strategie accepteert rasters van een rij, die ExtractDocumentTables gebruikt voor tabelfragmenten die bovenaan een pagina verderlopen. Hetzelfde optierecord reist door naar TPdfReflowOptions.TableOptions, dus reflow-uitvoer erft dezelfde beslissingen als DetectTables aan staat

De corridortest oordeelt over rijen die aan beide kanten van een grens inhoud hebben, dus een kandidaat van twee rijen wordt beoordeeld op precies twee zulke rijen. Voor archieven die grotendeels proze zijn en zelden echte tabellen van twee rijen bevatten — contracten, correspondentie, essays — zet MinRows op 3 en accepteer de verloren tabellen van twee rijen. Voor financiele en formulierrijke documenten houd je de default van 2 aan, want korte echte tabellen zijn daar gewoon. Links uitgelijnde tekst houdt gewone enkele spaties aan en produceert zelden een gat ergens in de buurt van 12 points

PDF heeft geen algemeen tabelobject. ISO 32000-1 §14.8.4.3.4 definieert wel een Table-structuurelement, maar alleen Tagged PDF draagt hem, dus voor al het overige is het raster een gevolgtrekking uit geometrie, en de Confidence van een whitespace-tabel komt nooit boven 0,88

De detectieopties, de TPdfTable.ToCsv- en ToJson-serialisatie en de TableExtractionLab-demo voor Delphi, C++Builder en Lazarus staan op de PDFium Component for Delphi-productpagina