Oprava falešných pozitiv PDF tabulek ze zarovnaného textu

PDFium Component ve verzi 3.117.0 přestává hlásit zarovnané odstavce jako tabulky zarovnané whitespace tím, že vyžaduje, aby každá sloupcová hranice byla svislým koridorem bez textu na jakémkoli řádku, který odděluje, přeskakuje slova už zabraná ruled mřížkou a skládá text buněk podle vertikálního překryvu místo vzdálenosti středů glyph boxů. Všechny tři změny bydlí uvnitř ExtractTables a ExtractDocumentTables a nepotřebují žádnou volbu

Report, který to rozpoutal, byl nezajímavý. Stránka tiskové zprávy bez jediné tabulky se vrátila z ExtractTables s 5x4 whitespace tabulkou, confidence pohodlně nad defaultním MinConfidence 0,5 a buňky držely zlomky obyčejného tělového textu. Přihlašovací formulář udělal totéž se svými esejovými odstavci a produkoval 3x4 a 5x3. Oba dokumenty byly vysázené zarovnaně. Zjevná reakce je doladit prahy a užitečná lekce z tohohle vydání je, že doladění to neopraví, protože laděné pravidlo kladlo špatnou otázku

uses
  PDFium;

// Regresní kontrola: vyjmenuj každou whitespace tabulku v dokumentu, aby
// se potvrdila čistota stránky, o níž víte, že je jen próza
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;

Proč zarovnaný text vypadá jako tabulka?

Zarovnaný odstavec vypadá jako tabulka, protože zarovnaná řádka je řada slov oddělených mezerami, které layout engine roztáhl, a jakmile se roztáhlá mezera dosáhne MinColumnGap, detector nemá žádný row-local způsob, jak ji odlišit od sloupcového oddělovače. Strategie whitespace v PDFium Component seskupuje word boxy do vizuálních řádků, štěpí každý řádek na skupiny slov všude, kde horizontální vzdálenost k předchozímu slovu dosáhne aspoň MinColumnGap (12 bodů defaultně), a akceptuje tabulku, když aspoň dva po sobě jdoucí řádky zopakují aspoň MinColumns levým okrajem zarovnaných ukotvení skupin v rámci AlignmentTolerance, což je 3 body. To je pravidlo popsané v přehledu detekce tabulek a pro skutečnou zarovnanou tabulku je přesně správné

Teď to aplikujte na dvacet řádků zarovnané 10bodové prózy. Každá řádka je roztáhnutá na stejný pravý okraj, takže řádka končící dlouhým slovem rozevře své vnitřní mezery a v odstavci s pár krátkými řádkami některé z těch mezer překročí 12 bodů. Dvě po sobě jdoucí řádky potřebují jen jednu roztáhlou mezeru každá, přistávající do 3 bodů od stejné pozice X, aby vytvořily kandidáta dvou řádků a dvou sloupců. Přes dost řádků to není smůla; je to pravděpodobnost blížící se jistotě a 5x4 na tiskové zprávě byl prostě běh, kde se čtyři takové mezery zarovnaly na pěti řádcích

Každý prah obchází jednu třídu dokumentů proti jiné. Zvednutí MinColumnGap na 20 bodů přijde o kompaktní sloupce hustých finančních reportů, což je přesně případ, kvůli kterému už default byl snížený. Zvednutí MinRows na 3 zahodí skutečné dvouřádkové tabulky a jen sníží pravděpodobnost u dlouhých odstavců. Utžení AlignmentTolerance pod 3 body rozbije word boxy z OCR, jejichž levé hrany se třesou o víc. Signál na úrovni řádků je doopravdy víceznačný, takže oprava musí přijít ze signálu, který řádky samy o sobě nenosí

Co dělá sloupcovou hranici skutečnou?

Skutečná sloupcová hranice je svislý pruh stránky, který zůstává prázdný přes každý řádek, který odděluje. Tabulka jí má mezi každým párem sloupců konstrukcí, protože buňky se rozmísťovaly proti sdíleným pozicím X. Zarovnaný odstavec roztahuje své slovní mezery na jiných horizontálních pozicích na každé řádce, takže žádný pruh nepřežije průnik víc než řádky jedné či dvou. PDFium Component teď testuje přesně to: poté, co jsou kandidátovi skupiny slov přiřazené ke sloupcovým ukotvením, pro každý pár sousedních sloupců vezme, na každém řádku, který má obsah v obou buňkách, interval od pravé hrany slov levé buňky po levou hranu slov pravé buňky, protne ty intervaly napříč řádky a odmítne celého kandidáta, pokud je průnik užší než MinColumnGap krát 0,5, což je 6 bodů na defaultu

Dva detaily mají význam. Řádky, kde je kterákoliv buňka prázdná, nehlasují, takže tabulka s prázdnou buňkou nebo hlavička přesahující méně sloupců než tělo pořád projde. A šířka koridoru se odvozuje z MinColumnGap místo vystavení jako separátní volba, protože obojí popisuje tutéž fyzickou věc: mezeru, kterou návrhář nechává mezi sloupci. Logika je malá dost na to, abyste ji reprodukovali, stavíte-li na surových word boxech místo na tabulkovém API a vzorek níže zrcadlí kontrolu uvnitř komponenty:

uses
  Math, PDFium;

type
  TIndexList = array of Integer;
  TCellIndexes = array of TIndexList;   // Řádek * ColumnCount + Sloupec

// Vrací False, když libovolný pár sousedních sloupců postrádá svislý
// koridor bez textu široký aspoň MinColumnGap / 2 napříč řádky, které ho používají
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ázdné buňky 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;

Proč se ruled tabulky extrahovaly dvakrát?

Ruled tabulky se extrahovaly dvakrát, protože průchod whitespace viděl každé slovo na stránce, včetně slov, která ruled průchod už umístil do mřížky, a čistá ruled tabulka je konstrukcí zároveň dokonale zarovnaná whitespace tabulka. Kontrola překryvu už odmítala whitespace kandidáta, jehož meze pokrývaly víc než polovinu existující tabulky, ale kandidát, který spojil spodní řádky tabulky s pár zarovnanými řádky textu pod ní, mohl pod ten poměr spadnout a přežít jako druhá, o kousek větší tabulka, která krvácela do svého souseda. ExtractTables teď ty slova odstraní, než se pustí whitespace průchod. Slovo se zahodí, když leží jeho střední bod uvnitř mezí jakékoli tabulky, kterou ruled průchod vyprodukoval; používá se střed místo plného obsažení, aby slovo postrkající okraj o zlomek bodu následovalo tabulku, do níž vizuálně patří. Strategie whitespace pak pracuje jen na volných slovech, což taky znamená, že malá nečarovaná tabulka sedící přímo pod ruled se detekuje po svých zásluhách místo slijení s mřížkou nad ní

Proč „Purpose of Request:" vyšlo jako „of Purpose Request:"?

Slova vyšla přeřazená, protože word boxy, které staví PDFium Component, jsou sjednocení bounding boxů glyphů a „of" nemá descender, zatímco „Purpose" a „Request:" ano. FPDFText_GetCharBox vrací těsný box inkoustu glyphu v prostoru stránky, ne box vypodlážděný na ascent a descent fontu a word box je sjednocení boxů jeho znaků. Slovo bez descenderů je proto kratší a jeho vertikální střed sedí výš, o 2 až 3 body na dotyčném formuláři. Stará rutina textu buňky sortovala slova nejdřív podle středového Y, s 1bodovou tolerancí pro „stejnou řádku", a pak podle levého okraje; „of" toleranci přehodilo, sortovalo se jako vlastní řádka nad ostatními a emitovalo se první

Tohle není tak PDFium vrtoch jako důsledek toho, jak PDF pozicuje text. ISO 32000-1 §9.2.2 a §9.4.4 definují umístění glyphu jako horizontální posun podél baseline v textovém prostoru a jediné vertikální metriky, které soubor nese, jsou per-font: položky Ascent, Descent a FontBBox deskriptoru fontu v §9.8.1. Nic v souboru neříká, že dva glyphy sdílí řádku; to se musí odvodit z geometrie a těsné glyph boxy, díky nimž vypadá správně zvýraznění výběru, jak popisuje výběr textových řádků s PDFium char boxy, jsou špatný vstup pro srovnání vzdáleností středů

Oprava ve verzi 3.117.0 mění otázku z „jak daleko od sebe jsou středy" na „jak moc se boxy překrývají vertikálně". Text buňky se skládá tak, že se nejdřív seskupí slova buňky do vizuálních řádků, kde se slovo přidá k řádce, když je jeho vertikální překryv s běžícími mezemi řádku aspoň 25 procent z menší ze dvou výšek, pak se každá řádka insertion-sortuje podle levého okraje a pak se řádky spojí zalomením řádku. „Purpose" a „of" se překrývají přes celé x-height, což je daleko víc než 25 procent kratšího boxu, takže přistanou na téže řádce a sortují se podle X, jak bylo zamýšleno

Seskupujte textové řádky podle překryvu, ne podle vzdálenosti středů

Pravidlo, které z tohohle bugu stojí za odnést, je obecné: jakýkoli kód textového layoutu PDF, který rozhoduje „stejná řádka" srovnáváním vertikálních středů proti fixní toleranci, selže na reálných fontech a selhání je tiché: nic nehlásí chybu, slova prostě vycházejí ve špatném pořadí. Smíšené descender jsou nejjemnější spouštěč. Tučný 12bodový popisek vedle 10bodových hodnot, superskriptový odkaz poznámky, měnový symbol kreslený z fallback fontu a OCR word boxy s per-word šumem výšek všechny posunou středy o víc než jakákoli tolerance, která pořád odděluje sousední řádky 10bodového textu při 12bodovém proložení. Poměr překryvu je size-invariantní: dva boxy na jedné baseline se překrývají přes sdílené x-height bez ohledu na to, co dělají jejich ascender a descender, a dva boxy na sousedních řádcích se nepřekrývají ničím

Tutéž pravidlo jde snadno aplikovat mimo extrakci tabulek. TPdf.PageWordBoxes vrací každé slovo na aktivní stránce s jeho obdélníkem v prostoru stránky, takže seskupení stránky do vizuálních řádků je krátká smyč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>;   // běžné sjednocení na řádku
  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;
  // sortuj každou řádku podle Rect.Left před čtením; PageWordBoxes vrací
  // slova v pořadí content streamu, což nemusí být vizuální
end;

Co se mění pro stávající volající a kde jsou limity

Pointa toho ústřipku je predikát, ne smyčka; pro cokoli nad rámec rychlého dumpu začněte strukturálním textovým modelem, který už nese bloky, řádky a zdroj reading orderu, jak popisuje strukturovaná extrakce PDF textu s reading orderem. Stávající tabulkoví volající dostanou všechny tři opravy, aniž by sáhli ke svým volbám. Koridorový práh je fixní na polovině MinColumnGap, strategie whitespace drží svou dvouřádkovou podlahu, i když je MinRows nastavené na 1 (což ruled strategie teď akceptuje) a ruled-first filtrování slov je bezpodmínečné, kdykoli jsou zapnuté obě strategie. Na vzorkové sadě 13 dokumentů použité pro vydání vracela whitespace fáze dřív 34 fragmentů a falešných pozitiv po boku 9 ruled tabulek; po vydání nevrací nic a počet ruled tabulek vzrostl na 41, i když většina toho vzrůstu přichází z téhož vydání, které naučilo ruled detector číst okraje kreslené jako vyplněné obdélníky, což je separátní příběh

Poctivé limity: koridorový test potřebuje aspoň jeden řádek s obsahem po obou stranách hranice, aby cokoli odmítl, takže dvouřádkový kandidát, jehož dvě roztáhlé mezery náhodou spadnou do 6 bodů od sebe, pořád projde. To je úzká náhoda místo téměř jistoty, jaká to byla dřív, ale dokumenty těžké na prózu bez skutečných dvouřádkových tabulek to můžou zavřít nastavením MinRows na 3. Levým okrajem zarovnaný roztroušený text nebyl nikdy problém a není postižený. A PDF pořád nemá žádný objekt tabulky; ISO 32000-1 §14.8.4.3 definuje strukturní element Table, ale nese ho jen Tagged PDF, takže pro všechno ostatní zůstává mřížka inferencí z geometrie a hodnota confidence na každé TPdfTable je tam proto, že inference si zaslouží skóre

Extrakce tabulek, strukturovaný text i word boxy všechny čtou ze stejného modelu stránky v Delphi, C++Builderu a Lazarusu; kompletní API, včetně TPdfTableExtractionOptions a dema TableExtractionLab, které se dodává po boku, je popsáno na stránce PDFium Component for Delphi