Valse PDF-tabellen uit uitgevulde tekst voorkomen in Delphi

PDFium Component versie 3.117.0 rapporteert uitgevulde alinea's niet langer als whitespace-uitgelijnde tabellen door te eisen dat elke kolomgrens een verticale corridor is zonder tekst op elke rij die hij scheidt, door woorden over te slaan die al door een gelijnd raster zijn opgeëist, en door celtekst samen te stellen op verticale overlap in plaats van op de afstand tussen glyph-boxcentra. Alle drie de wijzigingen zitten in ExtractTables en ExtractDocumentTables en vragen geen optie

Het rapport dat dit begon was weinig glamoureus. Een persberichtpagina zonder enige tabel kwam terug uit ExtractTables met een 5x4-whitespacetabel, de confidence ruim boven de standaard MinConfidence van 0.5, en de cellen bevatten fragmenten van gewone broodtekst. Een aanmeldingsformulier deed hetzelfde met zijn essay-alinea's en leverde een 3x4 en een 5x3 op. Beide documenten waren uitgevuld gezet. De voor de hand liggende reactie is de drempels bijstellen, en de nuttige les uit deze release is dat bijstellen het niet kan oplossen, omdat de regel die bijgesteld werd de verkeerde vraag stelde

uses
  PDFium;

// Regressiecontrole: som elke whitespacetabel in een document op zodat een pagina
// waarvan je weet dat hij alleen proza bevat als schoon bevestigd kan worden
procedure ReportWhitespaceTables(Pdf: TPdf);
var
  Options: TPdfTableExtractionOptions;
  Tables: TPdfTables;
  I: Integer;
begin
  Options := TPdfTableExtractionOptions.Default;   // MinColumnGap 12pt
  Tables := Pdf.ExtractDocumentTables(Options);
  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;

Waarom ziet uitgevulde tekst eruit als een tabel?

Een uitgevulde alinea ziet eruit als een tabel omdat een uitgevulde regel een rij woorden is, gescheiden door tussenruimtes die de layout-engine heeft opgerekt, en zodra een opgerekte tussenruimte MinColumnGap bereikt heeft de detector geen rij-lokale manier meer om hem van een kolomscheiding te onderscheiden. De whitespace-strategie in PDFium Component groepeert woordboxen tot visuele rijen, splitst elke rij in woordgroepen waar de horizontale afstand tot het vorige woord minstens MinColumnGap is (standaard 12 punten), en accepteert een tabel wanneer minstens twee opeenvolgende rijen minstens MinColumns links uitgelijnde groepankers binnen AlignmentTolerance herhalen, wat 3 punten is. Dat is de regel die in het overzicht van tabledetectie wordt beschreven, en voor een echt uitgelijnde tabel is hij precies goed

Pas hem nu toe op twintig regels uitgevuld proza van 10 punten. Elke regel wordt naar dezelfde rechtermarge opgerekt, dus een regel die met een lang woord eindigt trekt zijn binnenspaties open, en in een alinea met een paar korte regels kruisen sommige van die spaties de 12 punten. Twee opeenvolgende regels hebben elk maar één opgerekte tussenruimte nodig, binnen 3 punten van dezelfde X-positie, om een kandidaat van twee rijen en twee kolommen te vormen. Over genoeg regels is dat geen pech; het is een waarschijnlijkheid die naar zekerheid nadert, en de 5x4 op het persbericht was simpelweg de run waarin vier zulke tussenruimtes op vijf regels uitlijnden

Elke drempel ruilt de ene klasse documenten tegen de andere. MinColumnGap naar 20 punten verhogen verliest de compacte kolommen van dichte financiële rapporten, precies het geval waarvoor de standaard al was verlaagd. MinRows naar 3 verhogen gooit echte tabellen van twee rijen weg en verlaagt alleen de kansen voor lange alinea's. AlignmentTolerance onder 3 punten aanscherpen breekt woordboxen die uit OCR komen, waarvan de linkerranden meer dan dat trillen. Het signaal op rijniveau is werkelijk dubbelzinnig, dus de fix moet komen uit een signaal dat rijen niet op zichzelf dragen

Wat maakt een kolomgrens echt?

Een echte kolomgrens is een verticale strook van de pagina die leeg blijft op elke rij die hij scheidt. Een tabel heeft er per constructie een tussen elk paar kolommen, omdat de cellen tegen gedeelde X-posities zijn opgemaakt. Een uitgevulde alinea rekt zijn woordspaties op verschillende horizontale posities op elke regel op, dus geen enkele strook overleeft de doorsnijding van meer dan een regel of twee. PDFium Component test nu precies dat: nadat de woordgroepen van de kandidaat aan ankerkolommen zijn toegewezen, neemt het voor elk paar aangrenzende kolommen, op elke rij die inhoud heeft in beide cellen, het interval van de rechterrand van de woorden van de linkercel tot de linkerrand van de woorden van de rechtercel, doorsnijdt die intervallen over de rijen, en weigert de hele kandidaat wanneer de doorsnijding smaller is dan MinColumnGap maal 0.5, wat met de standaard 6 punten is

Twee details doen ertoe. Rijen waarin een van beide cellen leeg is stemmen niet mee, dus een tabel met een lege cel, of een kop die minder kolommen omspant dan de body, slaagt alsnog. En de corridorbreedte wordt afgeleid uit MinColumnGap in plaats van als aparte optie aangeboden, omdat de twee hetzelfde fysieke ding beschrijven: de tussenruimte die een ontwerper tussen kolommen laat. De logica is klein genoeg om te reproduceren als je op ruwe woordboxen bouwt in plaats van op de tabel-API, en het voorbeeld hieronder spiegelt de controle binnen de component:

uses
  Math, PDFium;

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

// Geeft False terug wanneer een paar aangrenzende kolommen een tekstvrije verticale
// corridor mist van minstens 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 mee
      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;

Waarom werden gelijnde tabellen twee keer geëxtraheerd?

Gelijnde tabellen werden twee keer geëxtraheerd omdat de whitespace-ronde vroeger elk woord op de pagina zag, inclusief de woorden die de gelijnde ronde al in een raster had geplaatst, en een schone gelijnde tabel is per constructie ook een perfect uitgelijnde whitespacetabel. Een overlapcontrole weigerde al een whitespace-kandidaat waarvan de grenzen meer dan de helft van een bestaande tabel dekten, maar een kandidaat die de onderste rijen van de tabel combineerde met een paar uitgelijnde tekstregels eronder kon onder die verhouding blijven en overleven als een tweede, iets grotere tabel die in zijn buurman bloedde. ExtractTables verwijdert die woorden nu voordat de whitespace-ronde loopt. Een woord wordt weggelaten wanneer zijn middelpunt binnen de grenzen van een tabel ligt die de gelijnde ronde heeft geproduceerd; het middelpunt wordt gebruikt in plaats van volledige insluiting, zodat een woord dat een rand met een fractie van een punt overschrijdt de tabel volgt waar het visueel bij hoort. De whitespace-strategie werkt daarna alleen op de vrije woorden, wat ook betekent dat een kleine ongelijnde tabel direct onder een gelijnde op zijn eigen merites wordt gevonden in plaats van met het raster erboven te versmelten

Waarom kwam "Purpose of Request:" eruit als "of Purpose Request:"?

De woorden kwamen in een andere orde eruit omdat de woordboxen die PDFium Component bouwt verenigingen zijn van glyph-begrenzingsboxen, en "of" heeft geen staartletter terwijl "Purpose" en "Request:" die wel hebben. FPDFText_GetCharBox geeft de strakke box van de inkt van de glyph in paginaruimte terug, niet een box die is opgevuld tot de ascender en descender van het font, en de woordbox is de vereniging van de boxen van zijn tekens. Een woord zonder staartletters is daardoor korter en zijn verticale midden ligt hoger, met 2 tot 3 punten op het formulier in kwestie. De oude routine voor celtekst sorteerde woorden eerst op center-Y, met een tolerantie van 1 punt voor "dezelfde regel", en daarna op linkerrand; "of" kwam buiten de tolerantie, sorteerde als zijn eigen regel boven de andere, en werd als eerste uitgeschreven

Dit is niet zozeer een PDFium-eigenaardigheid als een gevolg van hoe PDF tekst positioneert. ISO 32000-1 §9.2.2 en §9.4.4 definiëren glyph-plaatsing als horizontale verplaatsing langs de basislijn in tekstruimte, en de enige verticale metrieken die het bestand draagt zijn per font: de items Ascent, Descent en FontBBox van de fontdescriptor in §9.8.1. Niets in het bestand zegt dat twee glyphs een regel delen; dat moet uit geometrie worden afgeleid, en de strakke glyph-boxen die selectiemarkering er goed uit laten zien, zoals beschreven in tekstregelselectie met PDFium char boxes, zijn de verkeerde invoer voor een vergelijking op centerafstand

De fix in versie 3.117.0 verandert de vraag van "hoe ver liggen de centra uit elkaar" naar "hoeveel overlappen de boxen verticaal". Celtekst wordt nu samengesteld door eerst de woorden van de cel tot visuele regels te groeperen, waarbij een woord bij een regel komt wanneer zijn verticale overlap met de lopende grenzen van die regel minstens 25 procent is van de kleinste van de twee hoogtes, daarna elke regel met insertion sort op linkerrand te sorteren, en daarna de regels met een regeleinde aan elkaar te rijgen. "Purpose" en "of" overlappen over de volle x-hoogte, wat veel meer is dan 25 procent van de kortste box, dus ze komen op dezelfde regel en sorteren zoals bedoeld op X

Groepeer tekstregels op overlap, niet op centerafstand

De regel die je uit deze bug moet meenemen is algemeen: elke PDF-tekstlayoutcode die "dezelfde regel" bepaalt door verticale centra tegen een vaste tolerantie te vergelijken zal op echte fonts falen, en de fout is stil: niets geeft een error, woorden komen simpelweg in de verkeerde orde eruit. Gemengde staartletters zijn de mildste trigger. Een vet label van 12 punten naast waarden van 10 punten, een superscript-voetnootmarkering, een valutasymbool uit een fallback-font, en OCR-woordboxen met hoogteruis per woord verplaatsen alle centra met meer dan welke tolerantie dan ook die nog aangrenzende regels van 10-puntstekst op 12 punten interlinie scheidt. De overlapratio is maatvast: twee boxen op één basislijn overlappen over hun gedeelde x-hoogte wat hun ascenders en descenders ook doen, en twee boxen op aangrenzende regels overlappen helemaal niets

Dezelfde regel is makkelijk toe te passen buiten tabelextractie. TPdf.PageWordBoxes geeft elk woord op de actieve pagina met zijn rechthoek in paginaruimte, dus een pagina tot visuele regels groeperen is 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 vereniging per regel
  I, J, Found: Integer;
begin
  Words := Pdf.PageWordBoxes;
  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 voordat je hem leest; PageWordBoxes geeft
  // woorden in content-stream-volgorde, wat niet gegarandeerd visueel is
end;

Wat verandert er voor bestaande aanroepers, en waar de grenzen liggen

Het punt van dat stukje is het predicaat, niet de lus; begin voor alles meer dan een snelle dump bij het gestructureerde tekstmodel, dat al blokken, regels en een bron voor de leesorde draagt, zoals behandeld in gestructureerde PDF-tekstextractie met leesorde. Bestaande aanroepers van tabellen krijgen alle drie de correcties zonder hun opties aan te raken. De corridordrempel staat vast op de helft van MinColumnGap, de whitespace-strategie houdt haar ondergrens van twee rijen zelfs wanneer MinRows op 1 staat (wat de gelijnde strategie nu accepteert), en het eerst-wegfilteren van gelijnde woorden is onvoorwaardelijk wanneer beide strategieën aan staan. Op de voorbeeldset van 13 documenten die voor de release is gebruikt gaf de whitespace-ronde eerder 34 fragmenten en valse positieven naast 9 gelijnde tabellen; na de release geeft ze er geen, en steeg het aantal gelijnde tabellen naar 41, al komt het meeste van die stijging doordat dezelfde release de gelijnde detector leerde randen te lezen die als gevulde rechthoeken zijn getekend, wat een apart verhaal is

De eerlijke grenzen: de corridortest heeft minstens één rij nodig met inhoud aan beide zijden van een grens om iets te kunnen weigeren, dus een kandidaat van twee rijen waarvan de twee opgerekte tussenruimtes toevallig binnen 6 punten van elkaar vallen slaagt alsnog. Dat is een smalle samenloop in plaats van de bijna-zekerheid van voorheen, maar proza-zware documenten zonder echte tabellen van twee rijen kunnen dat dichten door MinRows op 3 te zetten. Links uitgelijnde rafelige tekst was nooit het probleem en wordt niet geraakt. En PDF heeft nog steeds geen tabelobject; ISO 32000-1 §14.8.4.3 definieert een structuurelement Table, maar alleen Tagged PDF draagt dat, dus voor al het andere blijft het raster een gevolgtrekking uit geometrie, en de confidence-waarde op elke TPdfTable staat er omdat een gevolgtrekking een score verdient

Tabelextractie, gestructureerde tekst en woordboxen lezen allemaal uit hetzelfde paginamodel in Delphi, C++Builder en Lazarus; de volledige API, inclusief TPdfTableExtractionOptions en de demo TableExtractionLab die ermee meekomt, staat beschreven op de PDFium Component for Delphi-pagina