Lažne tabele iz poravnatog teksta u PDF-u sa PDFium-om

PDFium Component verzija 3.117.0 prestaje da prijavljuje poravnate pasuse kao tabele poravnate prazninama tako što zahteva da svaka granica kolone bude vertikalni koridor bez teksta u svakom redu koji razdvaja, preskače reči koje je već prisvojio grid sa linijama, i sastavlja tekst ćelije po vertikalnom preklapanju umesto po rastojanju centara glyph box-ova. Sve tri izmene žive unutar ExtractTables i ExtractDocumentTables i ne traže nikakvu opciju

Izveštaj koji je ovo pokrenuo bio je neatraktivan. Stranica saopštenja za štampu na kojoj nema nikakve tabele vraćena je iz ExtractTables sa tabelom iz praznina 5x4, pouzdanosti udobno iznad podrazumevanog MinConfidence od 0,5, a ćelije su držale delove običnog teksta tela. Prijemni formular je uradio isto sa svojim esejskim pasusima i proizveo 3x4 i 5x3. Oba dokumenta bila su poravnata. Očigledan odgovor je doterati pragove, a korisna pouka ovog izdanja je da doterivanje ne može to da ispravi, jer je pravilo koje se doteruje postavljalo pogrešno pitanje

uses
  PDFium;

// Regresiona provera: ispiši svaku tabelu iz praznina u dokumentu da bi stranica
// za koju znate da je samo proza mogla da se potvrdi kao čista
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;

Zašto poravnat tekst izgleda kao tabela?

Poravnat pasus izgleda kao tabela jer je poravnata linija red reči razdvojenih razmacima koje je layout engine razvukao, a kada razvučeni razmak dostigne MinColumnGap, detektor nema način unutar reda da ga razlikuje od separatora kolone. Strategija praznina u PDFium Component-u grupiše box-ove reči u vizuelne redove, deli svaki red u grupe reči gde god je horizontalno rastojanje do prethodne reči najmanje MinColumnGap (podrazumevano 12 poena), i prihvata tabelu kada najmanje dva uzastopna reda ponove najmanje MinColumns levo poravnatih sidara grupa unutar AlignmentTolerance, što je 3 poena. To je pravilo opisano u pregledu detekcije tabela, i za pravu poravnatu tabelu ono je tačno onakvo kakvo treba da bude

Primenite ga sada na dvadeset linija poravnate proze od 10 poena. Svaka linija je razvučena do iste desne margine, pa linija koja se završava dugom reči otvara svoje unutrašnje razmake, a u pasusu sa nekoliko kratkih linija neki od tih razmaka prelaze 12 poena. Dvema uzastopnim linijama treba samo po jedan razvučeni razmak, koji sleće unutar 3 poena od iste X pozicije, da formiraju kandidata sa dva reda i dve kolone. Kroz dovoljno linija to nije loša sreća; to je verovatnoća koja se približava izvesnosti, a 5x4 na saopštenju za štampu bio je jednostavno niz u kojem su se četiri takva razmaka poravnala na pet linija

Svaki prag trguje jednom klasom dokumenata za drugu. Podizanje MinColumnGap na 20 poena gubi kompaktne kolone gustih finansijskih izveštaja, što je upravo slučaj zbog kojeg je podrazumevana vrednost već bila snižena. Podizanje MinRows na 3 odbacuje prave tabele sa dva reda i samo snižava verovatnoću za duge pasuse. Stezanje AlignmentTolerance ispod 3 poena lomi box-ove reči iz OCR-a, čije leve ivice podrhtavaju više od toga. Signal na nivou reda zaista je dvosmislen, pa ispravka mora doći iz signala koji redovi sami po sebi ne nose

Šta čini granicu kolone stvarnom?

Stvarna granica kolone je vertikalna traka stranice koja ostaje prazna u svakom redu koji razdvaja. Tabela je ima između svakog para kolona po konstrukciji, jer su ćelije postavljene prema zajedničkim X pozicijama. Poravnat pasus razvlači svoje razmake između reči na različitim horizontalnim pozicijama u svakoj liniji, pa nijedna traka ne preživi presek više od jedne ili dve linije. PDFium Component sada testira tačno to: pošto su grupe reči kandidata dodeljene sidrenim kolonama, za svaki par susednih kolona uzima, u svakom redu koji ima sadržaj u obe ćelije, interval od najdesnije ivice reči leve ćelije do najlevlje ivice reči desne ćelije, preseca te intervale kroz redove, i odbija ceo kandidat ako je presek uži od MinColumnGap puta 0,5, što je 6 poena pri podrazumevanoj vrednosti

Dva detalja su važna. Redovi u kojima je bilo koja ćelija prazna ne glasaju, pa tabela sa praznom ćelijom, ili zaglavlje koje pokriva manje kolona od tela, i dalje prolazi. A širina koridora izvodi se iz MinColumnGap umesto da bude izložena kao zasebna opcija, jer to dvoje opisuje istu fizičku stvar: razmak koji dizajner ostavlja između kolona. Logika je dovoljno mala da se reprodukuje ako gradite na sirovim box-ovima reči umesto na table API-ju, a primer ispod preslikava proveru unutar komponente:

uses
  Math, PDFium;

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

// Vraća False kada bilo kom paru susednih kolona nedostaje vertikalni
// koridor bez teksta širok najmanje MinColumnGap / 2 kroz redove koji ga koriste
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;                             // prazne ćelije ne glasaju
      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;

Zašto su tabele sa linijama izvlačene dvaput?

Tabele sa linijama izvlačene su dvaput jer je prolaz kroz praznine nekad video svaku reč na stranici, uključujući reči koje je prolaz za mreže već smestio u grid, a čista tabela sa linijama je po konstrukciji i savršeno poravnata tabela iz praznina. Provera preklapanja već je odbijala kandidata iz praznina čije su granice pokrivale više od polovine postojeće tabele, ali kandidat koji je spajao donje redove tabele sa nekoliko poravnatih linija teksta ispod nje mogao je pasti ispod tog odnosa i preživeti kao druga, malo veća tabela koja se prelivala u susednu. ExtractTables sada uklanja te reči pre nego što se prolaz kroz praznine pokrene. Reč se odbacuje kada njena centralna tačka leži unutar granica bilo koje tabele koju je prolaz za mreže proizveo; koristi se centar a ne potpuno sadržavanje, da bi reč koja premošćuje ivicu za delić poena sledila tabelu kojoj vizuelno pripada. Strategija praznina zatim radi samo na slobodnim rečima, što znači i da se mala tabela bez linija koja stoji direktno pod tabelom sa linijama detektuje po sopstvenim zaslugama umesto da se spoji sa gridom iznad sebe

Zašto je „Purpose of Request:" izašlo kao „of Purpose Request:"?

Reči su izašle preuređene jer su box-ovi reči koje PDFium Component gradi unije bounding box-ova glifova, a „of" nema descender dok „Purpose" i „Request:" imaju. FPDFText_GetCharBox vraća tesan box tinte glifa u prostoru stranice, a ne box dopunjen do ascent-a i descent-a fonta, i box reči je unija box-ova njenih znakova. Reč bez descender-a je zato kraća i njen vertikalni centar stoji više, za 2 do 3 poena na formularu u pitanju. Stara rutina za tekst ćelije sortirala je reči prvo po centru Y, sa tolerancijom od 1 poena za „isti red", a zatim po levoj ivici; „of" je prošlo toleranciju, sortiralo se kao sopstveni red iznad ostalih, i emitovano je prvo

To nije toliko PDFium-ov hir koliko posledica toga kako PDF pozicionira tekst. ISO 32000-1 §9.2.2 i §9.4.4 definišu postavljanje glifova kao horizontalno pomeranje duž baseline-a u prostoru teksta, a jedine vertikalne metrike koje fajl nosi su po fontu: unosi Ascent, Descent i FontBBox font descriptor-a u §9.8.1. Ništa u fajlu ne kaže da dva glifa dele liniju; to mora da se zaključi iz geometrije, a tesni box-ovi glifova zbog kojih isticanje selekcije izgleda ispravno, kako je opisano u selekciji tekstualnih linija pomoću PDFium char box-ova, pogrešan su ulaz za poređenje rastojanja centara

Ispravka u verziji 3.117.0 menja pitanje iz „koliko su centri udaljeni" u „koliko se box-ovi vertikalno preklapaju". Tekst ćelije sastavlja se tako što se reči ćelije prvo grupišu u vizuelne linije, gde se reč pridružuje liniji kada je njeno vertikalno preklapanje sa tekućim granicama linije najmanje 25 procenata manje od te dve visine, zatim se svaka linija sortira insertion sort-om po levoj ivici, i na kraju se linije spajaju prelomom reda. „Purpose" i „of" preklapaju se preko pune x-visine, što je daleko više od 25 procenata kraćeg box-a, pa sleću u istu liniju i sortiraju se po X kako je i zamišljeno

Grupisanje tekstualnih linija po preklapanju, ne po rastojanju centara

Pravilo koje vredi poneti iz ovog buga je opšte: svaki PDF kod za raspored teksta koji odlučuje o „istoj liniji" poredeći vertikalne centre sa fiksnom tolerancijom pašće na pravim fontovima, a otkaz je tih: ništa ne baca grešku, reči jednostavno izlaze u pogrešnom redu. Izmešani descender-i su najblaži okidač. Bold labela od 12 poena pored vrednosti od 10 poena, marker fusnote u superscript-u, simbol valute nacrtan iz fallback fonta, i OCR box-ovi reči sa šumom u visini po reči — svi pomeraju centre više od bilo koje tolerancije koja još razdvaja susedne linije teksta od 10 poena pri vodećem prostoru od 12 poena. Odnos preklapanja ne zavisi od veličine: dva box-a na istoj baseline-i preklapaju se preko zajedničke x-visine bez obzira na svoje ascent-e i descent-e, a dva box-a na susednim linijama ne preklapaju se ni malo

Isto pravilo je lako primeniti i van izvlačenja tabela. TPdf.PageWordBoxes vraća svaku reč na aktivnoj stranici sa njenim pravougaonikom u prostoru stranice, pa je grupisanje stranice u vizuelne linije kratka petlja:

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>;   // tekuća unija po liniji
  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;
  // sortiraj svaku liniju po Rect.Left pre čitanja; PageWordBoxes vraća
  // reči u redu content stream-a, što nije garantovano vizuelni red
end;

Šta se menja za postojeće pozivaoce, i gde su granice

Poenta tog isečka je predikat, ne petlja; za sve više od brzog dump-a pođite od modela strukturiranog teksta, koji već nosi blokove, linije i izvor redosleda čitanja, kako je obrađeno u izvlačenju strukturiranog PDF teksta sa redosledom čitanja. Postojeći pozivaoci izvlačenja tabela dobijaju sve tri ispravke bez diranja svojih opcija. Prag koridora fiksiran je na polovinu MinColumnGap, strategija praznina zadržava svoj pod od dva reda čak i kada je MinRows postavljen na 1 (što strategija mreža sada prihvata), a filtriranje reči pre mreža je bezuslovno kad god su obe strategije uključene. Na skupu od 13 uzoraka dokumenata korišćenom za izdanje, prolaz kroz praznine ranije je vraćao 34 fragmenta i lažne pozitive uz 9 tabela sa linijama; posle izdanja ne vraća nijedan, a broj tabela sa linijama porastao je na 41, mada većina tog rasta dolazi iz istog izdanja koje je detektor mreža naučilo da čita ivice nacrtane kao ispunjene pravougaonike, što je zasebna priča

Iskrene granice: test koridora traži najmanje jedan red sa sadržajem na obe strane granice da bi bilo šta odbio, pa kandidat sa dva reda čija dva razvučena razmaka slučajno padnu unutar 6 poena jedan od drugog i dalje prolazi. To je uska slučajnost a ne skoro izvesnost kakva je bila pre, ali dokumenti puni proze bez pravih tabela sa dva reda mogu to da zatvore postavljanjem MinRows na 3. Levo poravnat neravan tekst nikad nije bio problem i nije pogođen. A PDF i dalje nema objekat tabele; ISO 32000-1 §14.8.4.3 definiše strukturni element Table, ali ga nosi samo Tagged PDF, pa za sve ostalo grid ostaje zaključak iz geometrije, i vrednost pouzdanosti na svakom TPdfTable postoji zato što zaključivanje zaslužuje ocenu

Izvlačenje tabela, strukturirani tekst i box-ovi reči svi čitaju iz istog modela stranice u Delphiju, C++Builder-u i Lazarus-u; kompletan API, uključujući TPdfTableExtractionOptions i TableExtractionLab demo koji se isporučuje uz njega, opisan je na stranici PDFium Component za Delphi