Falska PDF-tabeller från marginaljusterad text i Delphi

PDFium Component version 3.117.0 slutar rapportera marginaljusterade stycken som whitespace-linjerade tabeller genom att kräva att varje kolumngräns är en vertikal korridor utan text på någon rad den skiljer åt, genom att hoppa över ord som redan tagits i anspråk av ett linjerat rutnät, och genom att sätta ihop celltext efter vertikal överlappning i stället för avstånd mellan glyfboxars mittpunkter. Alla tre ändringarna ligger inuti ExtractTables och ExtractDocumentTables och kräver ingen inställning

Rapporten som startade det här var oglamorös. En pressmeddelandesida utan tabell kom tillbaka från ExtractTables med en 5x4-whitespace-tabell, konfidensvärde bekvämt över standardvärdet MinConfidence på 0,5, och cellerna innehöll fragment av vanlig brödtext. Ett ansökningsformulär gjorde samma sak med sina essäistycken och gav en 3x4 och en 5x3. Båda dokumenten var marginaljusterade. Den uppenbara reaktionen är att trimma tröskelvärdena, och den användbara lärdomen från den här releasen är att trimning inte kan fixa det, för regeln som trimmades ställde fel fråga

uses
  PDFium;

// Regressionskontroll: lista varje whitespace-tabell i ett dokument så att en sida
// du vet bara innehåller prosa kan bekräftas ren
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;

Varför ser marginaljusterad text ut som en tabell?

Ett marginaljusterat stycke ser ut som en tabell för att en justerad rad är en rad ord åtskilda av luckor som layoutmotorn töjde ut, och så fort en uttöjd lucka når MinColumnGap har detektorn inget radlokalt sätt att skilja den från en kolumnavskiljare. Whitespace-strategin i PDFium Component grupperar ordboxar i visuella rader, delar varje rad i ordgrupper varhelst det horisontella avståndet till föregående ord är minst MinColumnGap (12 punkter som standard), och accepterar en tabell när minst två på varandra följande rader upprepar minst MinColumns vänsterjusterade gruppankare inom AlignmentTolerance, vilket är 3 punkter. Det är regeln som beskrivs i översikten över tabelldetektering, och för en äkta justerad tabell är den precis rätt

Tillämpa den nu på tjugo rader marginaljusterad prosa i 10 punkter. Varje rad töjs till samma högermarginal, så en rad som slutar med ett långt ord drar upp sina inre mellanslag, och i ett stycke med några korta rader passerar en del av de mellanslagen 12 punkter. Två på varandra följande rader behöver bara en uttöjd lucka var, som landar inom 3 punkter från samma X-position, för att bilda en kandidat med två rader och två kolumner. Över tillräckligt många rader är det här inte otur; det är en sannolikhet som närmar sig visshet, och 5x4:an på pressmeddelandet var helt enkelt den följd där fyra sådana luckor linjerade in sig på fem rader

Varje tröskelväxlar en klass av dokument mot en annan. Att höja MinColumnGap till 20 punkter tappar de kompakta kolumnerna i täta ekonomirapporter, vilket är precis det fall standardvärdet redan sänktes för. Att höja MinRows till 3 kastar bort riktiga tvåradstabeller och sänker bara oddsen för långa stycken. Att strama åt AlignmentTolerance under 3 punkter bryter ordfyrkanter från OCR, vars vänsterkanter vacklar mer än så. Radnivåsignalen är genuint tvetydig, så fixen måste komma från en signal som raderna inte bär på egen hand

Vad gör en kolumngräns verklig?

En verklig kolumngräns är en vertikal remsa av sidan som förblir tom över varje rad den skiljer åt. En tabell har en mellan varje kolumnpar genom konstruktion, eftersom cellerna lades ut mot delade X-positioner. Ett marginaljusterat stycke töjer sina ordmellanslag vid olika horisontella positioner på varje rad, så ingen remsa överlever skärningen av mer än en rad eller två. PDFium Component testar nu precis det: efter att kandidatens ordgrupper tilldelats ankarkolumner tar den, för varje par av intilliggande kolumner, på varje rad som har innehåll i båda cellerna, intervallet från den vänstra cellens ords högerkant till den högra cellens ords vänsterkant, skär dessa intervall över raderna, och avvisar hela kandidaten om skärningen är smalare än MinColumnGap gånger 0,5, vilket är 6 punkter med standardvärdet

Två detaljer spelar roll. Rader där någon av cellerna är tom röstar inte, så en tabell med en tom cell, eller en rubrik som spänner över färre kolumner än kroppen, passerar ändå. Och korridorbredden härleds från MinColumnGap i stället för att exponeras som en separat inställning, eftersom de två beskriver samma fysiska sak: luckan en formgivare lämnar mellan kolumner. Logiken är liten nog att återskapa om du bygger på råa ordfyrkanter i stället för tabell-API:et, och exemplet nedan speglar kontrollen inuti komponenten:

uses
  Math, PDFium;

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

// Returnerar False när något intilliggande kolumnpar saknar en textfri vertikal
// korridor minst MinColumnGap / 2 bred över de rader som använder den
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;                             // tomma celler röstar inte
      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;

Varför extraherades linjerade tabeller två gånger?

Linjerade tabeller extraherades två gånger för att whitespace-passet brukade se varje ord på sidan, inklusive de ord som det linjerade passet redan placerat i ett rutnät, och en ren linjerad tabell är genom konstruktion också en perfekt justerad whitespace-tabell. En överlappningskontroll avvisade redan en whitespace-kandidat vars gränser täckte mer än halva en befintlig tabell, men en kandidat som kombinerade tabellens nedre rader med några justerade textrader under den kunde falla under den kvoten och överleva som en andra, något större tabell som blödde in i sin granne. ExtractTables tar nu bort de orden innan whitespace-passet kör. Ett ord tas bort när dess mittpunkt ligger innanför gränserna för någon tabell som det linjerade passet producerade; mittpunkten används i stället för fullständig inneslutning så att ett ord som korsar en ram med en bråkdel av en punkt följer den tabell det visuellt tillhör. Whitespace-strategin arbetar sedan bara på de fria orden, vilket också betyder att en liten olinjerad tabell direkt under en linjerad upptäcks på sina egna meriter i stället för att smältas samman med rutnätet ovanför

Varför blev "Purpose of Request:" till "of Purpose Request:"?

Orden kom ut i fel ordning för att ordfyrkanterna PDFium Component bygger är unioner av glyfers avgränsningsboxar, och "of" saknar underlängd medan "Purpose" och "Request:" har det. FPDFText_GetCharBox ger den täta boxen runt glyfens bläck i sidrymden, inte en box utfylld till typsnittets ascent och descent, och ordfyrkanterna är unionen av dess teckens boxar. Ett ord utan underlängder är därför kortare och dess vertikala mittpunkt sitter högre, med 2 till 3 punkter på formuläret i fråga. Den gamla celltextrutinen sorterade ord efter mittpunktens Y först, med en tolerans på 1 punkt för "samma rad", och sedan efter vänsterkant; "of" klarade toleransen, sorterades som sin egen rad ovanför de andra och emitterades först

Det här är inte så mycket en PDFium-egenhet som en följd av hur PDF placerar text. ISO 32000-1 §9.2.2 och §9.4.4 definierar glyfplacering som horisontell förskjutning längs baslinjen i textrymden, och de enda vertikala mått filen bär är per typsnitt: posterna Ascent, Descent och FontBBox i typsnittsbeskrivningen i §9.8.1. Inget i filen säger att två glyfer delar en rad; det måste härledas ur geometrin, och de täta glyfboxarna som får markeringshighlighten att se rätt ut, som beskrivs i textradsmarkering med PDFium char boxes, är fel indata för en jämförelse av mittpunktsavstånd

Fixen i version 3.117.0 ändrar frågan från "hur långt ifrån varandra ligger mittpunkterna" till "hur mycket överlappar boxarna vertikalt". Celltexten sätts ihop genom att först gruppera cellens ord i visuella rader, där ett ord ansluter till en rad när dess vertikala överlappning med radens löpande gränser är minst 25 procent av den mindre av de två höjderna, sedan insättningssortera varje rad efter vänsterkant och därefter foga samman raderna med en radbrytning. "Purpose" och "of" överlappar över hela x-höjden, vilket är långt mer än 25 procent av den kortare boxen, så de hamnar på samma rad och sorteras efter X som avsett

Gruppera textrader efter överlappning, inte efter mittpunktsavstånd

Regeln som är värd att ta med sig från den här buggen är allmän: varje PDF-textlayoutkod som avgör "samma rad" genom att jämföra vertikala mittpunkter mot en fast tolerans kommer att fallera på riktiga typsnitt, och felet är tyst: inget felar, orden kommer bara ut i fel ordning. Blandade underlängder är den mildaste utlösaren. En fet etikett i 12 punkter bredvid värden i 10 punkter, en upphöjd fotnotsmarkör, en valutasymbol ritad ur ett reservtypsnitt och OCR-ordfyrkanter med höjdbrus per ord flyttar alla mittpunkter mer än någon tolerans som fortfarande skiljer intilliggande rader av 10-punktstext med 12 punkters radavstånd. Överlappningskvoten är storleksoberoende: två boxar på samma baslinje överlappar över sin delade x-höjd oavsett vad deras över- och underlängder gör, och två boxar på intilliggande rader överlappar inte alls

Samma regel är enkel att tillämpa utanför tabellutvinningen. TPdf.PageWordBoxes ger varje ord på den aktiva sidan med sin rektangel i sidrymden, så att gruppera en sida i visuella rader är en kort loop:

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>;   // löpande union per rad
  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;
  // sortera varje rad efter Rect.Left innan du läser den; PageWordBoxes ger
  // orden i content stream-ordning, vilket inte garanterat är visuell ordning
end;

Vad ändras för befintliga anropare, och var gränserna går

Poängen med det utdraget är predikatet, inte loopen; för allt bortom en snabb dump, utgå från den strukturerade textmodellen, som redan bär block, rader och en källa för läsordning, så som tas upp i strukturerad PDF-textutvinning med läsordning. Befintliga tabellanropare får alla tre rättelserna utan att röra sina inställningar. Korridortröskeln är fast vid halva MinColumnGap, whitespace-strategin behåller sitt tvåradsgolv även när MinRows sätts till 1 (vilket den linjerade strategin nu accepterar), och filtreringen av ord före whitespace-passet är ovillkorlig närhelst båda strategierna är aktiverade. På de 13 dokument som användes som urval för releasen hade whitespace-passet tidigare gett 34 fragment och falska positiva vid sidan av 9 linjerade tabeller; efter releasen ger det inga, och antalet linjerade tabeller steg till 41, även om det mesta av den ökningen kommer från att samma release lärde den linjerade detektorn att läsa ramar ritade som fyllda rektanglar, vilket är en separat historia

De ärliga gränserna: korridortestet behöver minst en rad med innehåll på båda sidor om en gräns för att avvisa något, så en tvåradskandidat vars två uttöjda luckor råkar falla inom 6 punkter från varandra passerar ändå. Det är ett snävt sammanträffande snarare än den nära visshet det var förut, men prosatunga dokument utan äkta tvåradstabeller kan stänga det genom att sätta MinRows till 3. Vänsterjusterad ojämn text var aldrig problemet och påverkas inte. Och PDF har fortfarande inget tabellobjekt; ISO 32000-1 §14.8.4.3 definierar ett Table-strukturelement, men bara Tagged PDF bär det, så för allt annat förblir rutnätet en slutledning ur geometrin, och konfidensvärdet på varje TPdfTable finns där för att slutledning förtjänar en poäng

Tabellutvinning, strukturerad text och ordfyrkanter läser alla från samma sidmodell i Delphi, C++Builder och Lazarus; hela API:et, inklusive TPdfTableExtractionOptions och demon TableExtractionLab som följer med, beskrivs på sidan för PDFium Component for Delphi