Ret PDF-tabel falske positiver fra justreret tekst i Delphi

PDFium Component version 3.117.0 holder op med at rapportere justerede afsnit som whitespace-alignede tabeller ved at kræve, at hver kolonnegrænse er en vertikal korridor uden tekst på nogen af de rækker, den adskiller, ved at springe ord over, der allerede er claimet af et linjeret gitter, og ved at samle celletekst efter vertikal overlap i stedet for glyf-boks-center-afstand. Alle tre ændringer bor inde i ExtractTables og ExtractDocumentTables og behøver ingen option

Rapporten, der startede dette, var uglamorøs. En pressemeddelelsesside uden nogen tabel på kom tilbage fra ExtractTables med en 5x4 whitespace-tabel, confidence komfortabelt over default-MinConfidence på 0,5, og cellerne holdt fragmenter af almindelig brødtekst. En adgangsformular gjorde det samme med sine essay-afsnit og producerede en 3x4 og en 5x3. Begge dokumenter var sat justeret. Det oplagte svar er at tune tærsklerne, og den nyttige lektie fra denne udgivelse er, at tuning ikke kan fikse det, for den regel, der blev tunet, stillede det forkerte spørgsmål

uses
  PDFium;

// Regressionstjek: List hver whitespace-tabel i et dokument, så en side,
// du ved kun er prosa, kan bekræftes ren
procedure ReportWhitespaceTables(Pdf: TPdf);
var
  Options: TPdfTableExtractionOptions;
  Tables: TPdfTables;
  I: Integer;
begin
  Options := TPdfTableExtractionOptions.Default;   // MinColumnGap 12 pt
  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;

Hvorfor ligner justreret tekst en tabel?

Et justeret afsnit ligner en tabel, fordi en justeret linje er en række ord adskilt af mellemrum, som layout-enginen har strakt, og når et strakt mellemrum først når MinColumnGap, har detektoren ingen række-lokal måde at skelne det fra en kolonneseparator. Whitespace-strategien i PDFium Component grupperer ord-bokse i visuelle rækker, splitter hver række i ordgrupper, hvor den horisontale afstand til det forrige ord er mindst MinColumnGap (12 point som default), og accepterer en tabel, når mindst to konsekutive rækker gentager mindst MinColumns venstrealignerede gruppe-ankre inden for AlignmentTolerance, som er 3 point. Det er reglen, der er beskrevet i oversigten over tabeldetektering, og for en ægte alignet tabel er den præcis rigtig

Anvend den nu på tyve linjer justeret 10-point prosa. Hver linje strækkes til samme højre margin, så en linje, der slutter med et langt ord, trækker sine indre mellemrum op, og i et afsnit med et par korte linjer krydser nogle af de mellemrum 12 point. To konsekutive linjer behøver kun ét strakt mellemrum hver, landende inden for 3 point af samme X-position, for at danne en to-rækkers, to-kolonners kandidat. Over nok linjer er det ikke uheld; det er en sandsynlighed, der nærmer sig sikkerhed, og 5x4'en på pressemeddelelsen var simpelthen den kørsel, hvor fire sådanne mellemrum stillede sig op på fem linjer

Hver tærskel afvejer én klasse af dokumenter mod en anden. At hæve MinColumnGap til 20 point mister de kompakte kolonner i tætte finansielle rapporter, hvilket er præcis den case, defaulten allerede var sænket for. At hæve MinRows til 3 kasserer rigtige to-rækkers tabeller og sænker blot oddsene for lange afsnit. At stramme AlignmentTolerance under 3 point knækker OCR-afledte ord-bokse, hvis venstre kanter jitter mere end det. Række-niveau-signalet er reelt tvetydigt, så fixet må komme fra et signal, rækker ikke bærer på egen hånd

Hvad gør en kolonnegrænse ægte?

En ægte kolonnegrænse er en vertikal stribe af siden, der forbliver tom hen over hver række, den adskiller. En tabel har én mellem hvert par af kolonner ved konstruktion, fordi cellerne blev lagt op ad delte X-positioner. Et justeret afsnit strækker sine ordmellemrum ved forskellige horisontale positioner på hver linje, så ingen stribe overlever skæringen af mere end en linje eller to. PDFium Component tester nu præcis det: Efter kandidatens ordgrupper er tildelt ankerkolonner tager den, for hvert par af nabokolonner, på hver række med indhold i begge celler, intervallet fra den højeste kant af venstre celles ord til den venstre kant af højre celles ord, skærer de intervaller sammen hen over rækkerne og afviser hele kandidaten, hvis skæringen er smallere end MinColumnGap ganget med 0,5, hvilket er 6 point ved default

To detaljer tæller. Rækker, hvor den ene celle er tom, stemmer ikke, så en tabel med en tom celle, eller et header, der spænder over færre kolonner end kroppen, består stadig. Og korridorens bredde er udledt af MinColumnGap frem for eksponeret som en separat option, fordi de to beskriver samme fysiske ting: Det mellemrum, en designer efterlader mellem kolonner. Logikken er lille nok til at reproducere, hvis du bygger på rå ord-bokse frem for tabel-API'en, og eksemplet nedenfor spejler tjekket inde i komponenten:

uses
  Math, PDFium;

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

// Returnerer False, når et nabokolonne-par mangler en tekstfri vertikal
// korridor på mindst MinColumnGap / 2 hen over de rækker, der bruger 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;                             // tomme celler stemmer ikke
      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;

Hvorfor blev linjerede tabeller ekstraheret to gange?

Linjerede tabeller blev ekstraheret to gange, fordi whitespace-passet plejede at se hvert ord på siden, inklusive de ord, det linjerede pass allerede havde placeret i et gitter, og et rent linjeret gitter er ved konstruktion også en perfekt alignet whitespace-tabel. Et overlap-tjek afviste allerede en whitespace-kandidat, hvis grænser dækkede mere end halvdelen af en eksisterende tabel, men en kandidat, der kombinerede tabellens nederste rækker med et par alignede tekstlinjer under den, kunne falde under den ratio og overleve som en anden, let større tabel, der blødte ind i sin nabo. ExtractTables fjerner nu de ord, før whitespace-passet kører. Et ord droppes, når dets centerpunkt ligger inde i grænserne af enhver tabel, det linjerede pass producerede; centeret bruges frem for fuld indeslutning, så et ord, der sidder på grænsen med en brøkdel af et point, følger den tabel, det visuelt tilhører. Whitespace-strategien arbejder derefter kun på de frie ord, hvilket også betyder, at en lille ulinjeret tabel direkte under en linjeret detekteres på egne meritter i stedet for at smelte sammen med gitteret over den

Hvorfor kom "Purpose of Request:" ud som "of Purpose Request:"?

Ordene kom ud i forkert rækkefølge, fordi de ord-bokse, PDFium Component bygger, er unioner af glyf-bounding boxes, og "of" har ingen descender, mens "Purpose" og "Request:" har. FPDFText_GetCharBox returnerer den tætte boks af glyfens blæk i side-rum, ikke en boks polstret til fontens ascent og descent, og ord-boksen er unionen af dens tegns bokse. Et ord uden descenders er derfor kortere, og dets vertikale center sidder højere, med 2 til 3 point på formularen i spørgsmål. Den gamle celletekst-rutine sorterede ord efter center Y først, med en 1-point-tolerance for "samme linje", og derefter efter venstre kant; "of" klarede tolerancen, sorteredes som sin egen linje over de andre og blev emitteret først

Dette er ikke så meget en PDFium-quirk som en konsekvens af, hvordan PDF placerer tekst. ISO 32000-1 §9.2.2 og §9.4.4 definerer glyfplacering som horisontal forskydning langs baselinjen i tekst-rum, og de eneste vertikale målinger, filen bærer, er pr. font: Ascent-, Descent- og FontBBox-posterne i font-deskriptoren i §9.8.1. Intet i filen siger, at to glyffer deler en linje; det skal udledes af geometrien, og de tætte glyf-bokse, der får selections-fremhævning til at se rigtig ud, som beskrevet i tekstlinje-selektion med PDFium char boxes, er det forkerte input til en center-afstand-sammenligning

Fixet i version 3.117.0 ændrer spørgsmålet fra "hvor langt fra hinanden er centrene" til "hvor meget overlapper bokserne vertikalt". Celletekst samles ved først at gruppere cellens ord i visuelle linjer, hvor et ord tilslutter sig en linje, når dets vertikale overlap med linjens løbende grænser er mindst 25 procent af det mindste af de to højder, derefter insertion-sortere hver linje efter venstre kant og derefter forene linjerne med et linjeskift. "Purpose" og "of" overlapper over hele x-højden, hvilket er langt mere end 25 procent af den kortere boks, så de lander på samme linje og sorteres efter X som tænkt

Gruppér tekstlinjer efter overlap, ikke efter center-afstand

Reglen, der er det værd at tage med fra denne bug, er generel: Enhver PDF tekst-layout-kode, der afgør "samme linje" ved at sammenligne vertikale centre mod en fast tolerance, vil fejle på rigtige fonts, og fejlen er lydløs: Intet raiser, ordene kommer simpelthen ud i forkert rækkefølge. Blandede descenders er den mildeste trigger. Et fedt 12-point label ved siden af 10-point værdier, et hævet fodnote-tegn, et valutasymbol tegnet fra en fallback-font og OCR-ord-bokse med per-ord højdestøj flytter alle centre mere end nogen tolerance, der stadig adskiller nabolinjer af 10-point tekst ved 12-point leading. Overlap-ratio er størrelses-invariant: To bokse på én baseline overlapper over deres delte x-højde, uanset hvad deres ascenders og descenders gør, og to bokse på nabolinjer overlapper med ingenting

Samme regel er let at anvende uden for tabel-ekstraktion. TPdf.PageWordBoxes returnerer hvert ord på den aktive side med dets side-rum-rektangel, så at gruppere en side i visuelle linjer er en kort løkke:

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øbende union pr. linje
  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;
  // Sortér hver linje efter Rect.Left, før den læses; PageWordBoxes returnerer
  // ord i content-stream-orden, som ikke er garanteret visuel
end;

Hvad ændrer sig for eksisterende callers, og hvor grænserne er

Pointen med det snippet er prædikatet, ikke løkken; til noget ud over et hurtigt dump, så start fra den strukturerede tekstmodel, som allerede bærer blokke, linjer og en læseretningskilde, som dækket i struktureret PDF-tekstekstraktion med læseretning. Eksisterende tabel-callers får alle tre rettelser uden at røre deres options. Korridor-tærsklen er fastsat til halvdelen af MinColumnGap, whitespace-strategien beholder sit to-række-gulv, selv når MinRows er sat til 1 (hvilket den linjerede strategi nu accepterer), og den linjeret-første ord-filtrering er ubetinget, når begge strategier er slået til. På det 13-dokumenters eksempelsæt, der blev brugt til udgivelsen, havde whitespace-passet tidligere returneret 34 fragmenter og falske positiver ved siden af 9 linjerede tabeller; efter udgivelsen returnerer den ingen, og antallet af linjerede tabeller steg til 41, selv om mesteparten af det spring kommer fra samme udgivelse, der lærte den linjerede detektor at læse kanter tegnet som udfyldte rektangler, hvilket er en separat historie

De ærlige grænser: Korridor-testen behøver mindst én række med indhold på begge sider af en grænse for at afvise noget, så en to-rækkers kandidat, hvis to strakte mellemrum tilfældigvis falder inden for 6 point af hinanden, består stadig. Det er en snæver tilfældighed frem for den nær-sikkerhed, det var før, men prosatunge dokumenter uden ægte to-rækkers tabeller kan lukke den ved at sætte MinRows til 3. Venstrealigneret takket tekst var aldrig problemet og påvirkes ikke. Og PDF har stadig intet tabel-objekt; ISO 32000-1 §14.8.4.3 definerer et Table-strukturelement, men kun Tagged PDF bærer det, så for alt andet forbliver gitteret en udledning fra geometrien, og confidence-værdien på hver TPdfTable er der, fordi en udledning fortjener en score

Tabel-ekstraktion, struktureret tekst og ord-bokse læser alle fra samme sidemodel i Delphi, C++Builder og Lazarus; den komplette API, inklusive TPdfTableExtractionOptions og TableExtractionLab-demoen, der ships ved siden af, er beskrevet på siden PDFium Component til Delphi