Falošné tabuľky z zarovnaného textu v PDFium

PDFium Component vo verzii 3.117.0 prestáva hlásiť zarovnané odseky ako whitespace tabuľky tým, že vyžaduje, aby každá hranica stĺpca bola zvislý koridor bez textu na každom riadku, ktorý oddeľuje, preskakuje slová, ktoré už zabrala ruled mriežka, a skladá text buniek podľa zvislého presahu namiesto vzdialenosti stredov glyph boxov. Všetky tri zmeny žijú vnútri ExtractTables a ExtractDocumentTables a nepotrebujú žiadnu voľbu

Report, ktorý to spustil, bol neokázalý. Stránka s tlačovou správou, na ktorej nie je žiadna tabuľka, sa z ExtractTables vrátila ako whitespace tabuľka 5x4 s confidence pohodlne nad defaultným MinConfidence 0,5, a bunky držali fragmenty obyčajného telového textu. Prijímací formulár spravil to isté so svojimi odsekmi a vyprodukoval 3x4 a 5x3. Oba dokumenty boli zarovnané do bloku. Očividná reakcia je ladiť prahy, a užitočná lekcia z tohto vydania je, že ladenie to nedokáže opraviť, pretože pravidlo, ktoré sa ladí, sa pýtalo nesprávnu otázku

uses
  PDFium;

// Regresná kontrola: vypíš všetky whitespace tabuľky v dokumente, aby sa
// stránka, o ktorej vieš, že je len próza, dala potvrdiť ako čistá
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;

Prečo zarovnaný text vyzerá ako tabuľka?

Zarovnaný odsek vyzerá ako tabuľka preto, že zarovnaný riadok je rad slov oddelených medzerami, ktoré layout engine roztiahol, a keď roztiahnutá medzera dosiahne MinColumnGap, detektor nemá žiadny row-lokálny spôsob, ako ju odlíšiť od oddeľovača stĺpcov. Whitespace stratégia v PDFium Component zoskupuje word boxy do vizuálnych riadkov, delí každý riadok na skupiny slov všade tam, kde je horizontálna vzdialenosť od predchádzajúceho slova aspoň MinColumnGap (defaultne 12 bodov), a tabuľku prijme, keď aspoň dva po sebe idúce riadky zopakujú aspoň MinColumns naľavo zarovnaných anchorov skupín v rámci AlignmentTolerance, čo sú 3 body. To je pravidlo opísané v prehľade detekcie tabuliek, a pre skutočnú zarovnanú tabuľku je presne správne

Teraz to aplikujte na dvadsať riadkov zarovnanej desaťbodovej prózy. Každý riadok je roztiahnutý na ten istý pravý okraj, takže riadok, ktorý končí dlhým slovom, si otvorí vnútorné medzery, a v odseku s niekoľkými krátkymi riadkami niektoré z tých medzier prekročia 12 bodov. Dvom po sebe idúcim riadkom stačí jedna roztiahnutá medzera v každom, ktorá padne do 3 bodov od tej istej X pozície, na vznik kandidáta s dvoma riadkami a dvoma stĺpcami. Na dosť dlhom texte to nie je smola; je to pravdepodobnosť blížiaca sa istote, a to 5x4 v tlačovej správe bol jednoducho úsek, kde sa štyri také medzery zoradili na piatich riadkoch

Každý prah mení jednu triedu dokumentov za druhú. Zvýšenie MinColumnGap na 20 bodov stratí kompaktné stĺpce hustých finančných reportov, čo je presne ten prípad, kvôli ktorému sa default už raz znižoval. Zvýšenie MinRows na 3 zahodí skutočné dvojriadkové tabuľky a len zníži šance pri dlhých odsekoch. Stiahnutie AlignmentTolerance pod 3 body rozbije word boxy z OCR, ktorých ľavé okraje kmitajú o viac. Signál na úrovni riadkov je naozaj nejednoznačný, takže oprava musí prísť zo signálu, ktorý riadky samy o sebe nenesú

Čo robí hranicu stĺpca skutočnou?

Skutočná hranica stĺpca je zvislý pruh stránky, ktorý zostáva prázdny naprieč každým riadkom, ktorý oddeľuje. Tabuľka ho má medzi každou dvojicou stĺpcov už z konštrukcie, pretože bunky boli rozložené proti zdieľaným X pozíciám. Zarovnaný odsek roztiahne svoje slovné medzery na každom riadku na iných horizontálnych pozíciách, takže žiadny pruh neprežije prienik dlhší než riadok alebo dva. PDFium Component teraz testuje presne toto: keď sú skupiny slov kandidáta priradené k anchor stĺpcom, pre každú dvojicu susedných stĺpcov vezme na každom riadku, ktorý má obsah v oboch bunkách, interval od pravého okraja slov ľavej bunky po ľavý okraj slov pravej bunky, tie intervaly naprieč riadkami pretne a celého kandidáta odmietne, ak je prienik užší než MinColumnGap krát 0,5, čo je pri defaulte 6 bodov

Dva detaily sú dôležité. Riadky, v ktorých je niektorá bunka prázdna, nehlasujú, takže tabuľka s prázdnou bunkou alebo hlavičkou, ktorá zaberá menej stĺpcov než telo, stále prejde. A šírka koridoru sa odvodzuje z MinColumnGap a nie je vystavená ako samostatná voľba, pretože obe opisujú tú istú fyzickú vec: medzeru, ktorú dizajnér necháva medzi stĺpcami. Tá logika je dosť malá na to, aby sa reprodukovala, ak staviate na surových word boxoch a nie na table API, a vzorka nižšie zrkadlí kontrolu vnútri komponentu:

uses
  Math, PDFium;

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

// Vráti False, keď ktorejkoľvek dvojici susedných stĺpcov chýba zvislý
// koridor bez textu široký aspoň MinColumnGap / 2 na riadkoch, ktoré ho použijú
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;                             // prázdne bunky nehlasujú
      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;

Prečo sa ruled tabuľky extrahovali dvakrát?

Ruled tabuľky sa extrahovali dvakrát, pretože whitespace prechod predtým videl každé slovo na stránke, vrátane slov, ktoré ruled prechod už umiestnil do mriežky, a čistá ruled tabuľka je už z konštrukcie aj dokonale zarovnanou whitespace tabuľkou. Kontrola prekrytia už odmietala whitespace kandidáta, ktorého hranice pokrývali viac než polovicu existujúcej tabuľky, ale kandidát, ktorý skombinoval spodné riadky tabuľky s niekoľkými zarovnanými riadkami textu pod ňou, mohol pod ten pomer spadnúť a prežiť ako druhá, o niečo väčšia tabuľka, ktorá sa vyliala do svojho suseda. ExtractTables teraz tie slová odstráni pred spustením whitespace prechodu. Slovo sa zahodí, keď jeho stredový bod leží vnútri hraníc ktorejkoľvek tabuľky, ktorú ruled prechod vyprodukoval; používa sa stred a nie úplné obsiahnutie, aby slovo prečnievajúce cez hranicu o zlomok bodu nasledovalo tabuľku, ku ktorej vizuálne patrí. Whitespace stratégia potom pracuje len na voľných slovách, čo tiež znamená, že malá neohraničená tabuľka sedia priamo pod ohraničenou sa detekuje na základe svojich vlastných kvalít a nie tak, že sa zleje s mriežkou nad sebou

Prečo vyšlo „Purpose of Request:“ ako „of Purpose Request:“?

Slová vyšli preusporiadané preto, že word boxy, ktoré PDFium Component stavia, sú zjednotenia glyph bounding boxov, a „of“ nemá descender, kým „Purpose“ a „Request:“ áno. FPDFText_GetCharBox vracia tesný box atramentu glyfu v page space, nie box doplnený na ascent a descent fontu, a word box je zjednotením boxov jeho znakov. Slovo bez descenderov je preto kratšie a jeho zvislý stred sedí vyššie, na danom formulári o 2 až 3 body. Stará rutina pre text bunky triedila slová najprv podľa stredu Y s 1-bodovou toleranciou pre „ten istý riadok“ a potom podľa ľavého okraja; „of“ tú toleranciu prekročilo, zoradilo sa ako vlastný riadok nad ostatnými a bolo emitované prvé

Nie je to ani tak zvláštnosť PDFia ako dôsledok toho, ako PDF umiestňuje text. ISO 32000-1 §9.2.2 a §9.4.4 definujú umiestnenie glyfu ako horizontálny posun pozdĺž baseline v text space, a jediné zvislé metriky, ktoré súbor nesie, sú per-font: položky Ascent, Descent a FontBBox font descriptoru v §9.8.1. Nič v súbore nehovorí, že dva glyfy zdieľajú riadok; to sa musí odvodiť z geometrie, a tesné glyph boxy, vďaka ktorým výber a zvýrazňovanie vyzerajú dobre, ako opisuje výber textových riadkov cez PDFium char boxy, sú pre porovnávanie vzdialeností stredov nesprávnym vstupom

Oprava vo verzii 3.117.0 mení otázku z „ako ďaleko sú od seba stredy“ na „o koľko sa boxy zvisle prekrývajú“. Text bunky sa skladá tak, že sa najprv slová bunky zoskupia do vizuálnych riadkov, pričom slovo sa pridá do riadku, keď jeho zvislý presah s priebežnými hranicami riadku je aspoň 25 percent menšej z tých dvoch výšok, potom sa každý riadok insertion-sortom zoradí podľa ľavého okraja a nakoniec sa riadky spoja zlomom riadka. „Purpose“ a „of“ sa prekrývajú po celej x-height, čo je oveľa viac než 25 percent kratšieho boxu, takže pristanú na tom istom riadku a zoradia sa podľa X, ako sa má

Zoskupujte textové riadky podľa presahu, nie podľa vzdialenosti stredov

Pravidlo, ktoré sa z tohto bugu oplatí odniesť, je všeobecné: každý PDF kód na rozloženie textu, ktorý rozhoduje „ten istý riadok“ porovnávaním zvislých stredov proti pevnej tolerancii, zlyhá na skutočných fontoch, a to zlyhanie je tiché — nič nevyhodí chybu, slová jednoducho vyjdú v nesprávnom poradí. Zmiešané descendery sú ten najmiernejší spúšťač. Tučný 12-bodový label vedľa 10-bodových hodnôt, marker poznámky pod čiarou v superscripte, symbol meny kreslený z fallback fontu a OCR word boxy so šumom vo výške jednotlivých slov — to všetko posúva stredy o viac, než je akákoľvek tolerancia, ktorá ešte oddeľuje susedné riadky 10-bodového textu pri 12-bodovom leadingu. Pomer presahu je nezávislý od veľkosti: dva boxy na jednej baseline sa prekrývajú po spoločnej x-height bez ohľadu na svoje ascendery a descendery a dva boxy na susedných riadkoch sa neprekrývajú vôbec

To isté pravidlo sa dá ľahko použiť aj mimo extrakcie tabuliek. TPdf.PageWordBoxes vracia každé slovo na aktívnej stránke s jeho obdĺžnikom v page space, takže zoskupenie stránky do vizuálnych riadkov je krátka slučka:

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>;   // priebežné zjednotenie na riadok
  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;
  // každý riadok pred čítaním zoraď podľa Rect.Left; PageWordBoxes vracia
  // slová v poradí content streamu, ktoré nemusí byť vizuálne
end;

Čo sa mení pre existujúcich volajúcich a kde sú hranice

Zmyslom toho útržku je predikát a nie slučka; na čokoľvek nad rýchly dump začnite zo structured text modelu, ktorý už nesie bloky, riadky a zdroj reading orderu, ako pokrýva štruktúrovaná extrakcia PDF textu s reading orderom. Existujúci volajúci extrakcie tabuliek dostanú všetky tri opravy bez toho, aby sa dotkli svojich volieb. Prah koridoru je pevne na polovici MinColumnGap, whitespace stratégia si drží dvojriadkovú hranicu aj keď je MinRows nastavené na 1 (čo ruled stratégia teraz prijíma), a filtrovanie slov pred whitespace prechodom je bezpodmienečné vždy, keď sú zapnuté obe stratégie. Na 13-dokumentovej vzorke použitej pre toto vydanie whitespace prechod predtým vracal 34 fragmentov a false positives vedľa 9 ruled tabuliek; po vydaní nevracia nič a počet ruled tabuliek stúpol na 41, hoci väčšina toho rastu pochádza z toho istého vydania, ktoré naučilo ruled detektor čítať okraje kreslené ako vyplnené obdĺžniky, čo je samostatný príbeh

Poctivé hranice: test koridoru potrebuje aspoň jeden riadok s obsahom na oboch stranách hranice, aby vôbec niečo odmietol, takže dvojriadkový kandidát, ktorého dve roztiahnuté medzery náhodou padnú do 6 bodov od seba, stále prejde. To je úzka náhoda a nie takmer istota ako predtým, ale dokumenty plné prózy bez skutočných dvojriadkových tabuliek to môžu zavrieť nastavením MinRows na 3. Nezarovnaný text s rovnou ľavicou nikdy nebol problém a nie je zasiahnutý. A PDF stále nemá tabuľkový objekt; ISO 32000-1 §14.8.4.3 definuje štruktúrny element Table, ale nosí ho len Tagged PDF, takže pre všetko ostatné mriežka zostáva odvodením z geometrie, a hodnota confidence na každej TPdfTable je tam preto, že odvodenie si zaslúži skóre

Extrakcia tabuliek, structured text aj word boxy čítajú z toho istého page modelu v Delphi, C++Builderi a Lazare; kompletné API vrátane TPdfTableExtractionOptions a dema TableExtractionLab, ktoré vychádza spolu s ním, opisuje stránka PDFium Component pre Delphi