Sorkizárt szöveg téves táblatalálatai: javítás Delphiben

A PDFium Component 3.117.0 verziója abbahagyja, hogy a sorkizárt bekezdéseket whitespace-hez igazított táblákként jelentse: megköveteli, hogy minden oszlophathatár olyan függőleges folyosó legyen, amelyen az általa elválasztott egyetlen sorban sincs szöveg, kihagyja a vonalazott rács által már igénybe vett szavakat, a cellaszöveget pedig függőleges átfedés alapján állítja össze a glifadoboz-középpontok távolsága helyett. Mindhárom változtatás az ExtractTables és az ExtractDocumentTables belsejében él, és egyik sem igényel opciót

A bejelentés, amelyből mindez kiindult, cseppet sem volt látványos. Egy táblát nem tartalmazó sajtóközlemény-oldal úgy jött vissza az ExtractTables hívásából, hogy van rajta egy 5x4-es whitespace-tábla, a bizonyossági érték kényelmesen a 0,5-ös MinConfidence alapérték felett, a cellákban pedig hétköznapi törzsszöveg-töredékek. Egy felvételi űrlap ugyanezt tette az esszébekezdéseivel, és előállított egy 3x4-est meg egy 5x3-ast. Mindkét dokumentum sorkizárt volt. A kézenfekvő válasz a küszöbök hangolása, és a kiadás hasznos tanulsága az, hogy a hangolás ezt nem tudja megjavítani, mert a hangolt szabály rossz kérdést tett fel

uses
  PDFium;

// Regressziós ellenőrzés: soroljuk fel a dokumentum minden whitespace-tábláját, hogy a
// bizonyítottan csak prózát tartalmazó oldal tisztasága igazolható legyen
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;

Miért látszik táblának a sorkizárt szöveg?

A sorkizárt bekezdés azért látszik táblának, mert egy sorkizárt sor olyan szavak sora, amelyeket az elrendezésmotor által megnyújtott közök választanak el, és amint egy megnyújtott köz eléri a MinColumnGap értéket, a detektornak soron belül nincs módja megkülönböztetni az oszlopelválasztótól. A PDFium Component whitespace-stratégiája a szódobozokat látható sorokba csoportosítja, minden sort szócsoportokra bont ott, ahol a vízszintes távolság az előző szótól legalább MinColumnGap (alapértelmezésben 12 pont), és akkor fogad el egy táblát, ha legalább két egymást követő sor legalább MinColumns balra igazított csoport-horgonypontot ismétel az AlignmentTolerance értéken belül, ami 3 pont. Ez az a szabály, amelyet a táblázatdetektálás áttekintése leír, és egy valódi, igazított tábla esetében pontosan helyes

Alkalmazzuk most ezt húsz sor sorkizárt, 10 pontos prózára. Minden sor ugyanahhoz a jobb margóhoz nyúlik ki, így az a sor, amely hosszú szóval végződik, kifeszíti a belső közöket, és egy kevés rövid sort tartalmazó bekezdésben e közök némelyike átlépi a 12 pontot. Két egymást követő sornak csak egy-egy megnyújtott közre van szüksége, amelyek ugyanazon X pozíció 3 pontján belülre esnek, hogy kialakuljon egy kétsoros, kétoszlopos jelölt. Elég sok soron át ez nem balszerencse, hanem a bizonyossághoz közelítő valószínűség, és a sajtóközleményen lévő 5x4 egyszerűen az a sorozat volt, ahol négy ilyen köz öt soron összeállt

Minden küszöb az egyik dokumentumosztályt a másik ellenében váltja fel. A MinColumnGap 20 pontra emelése elveszíti a sűrű pénzügyi jelentések kompakt oszlopait — pontosan azt az esetet, amely miatt az alapértéket már le is csökkentették. A MinRows 3-ra emelése elveti a valódi kétsoros táblákat, és csupán csökkenti a hosszú bekezdések esélyeit. Az AlignmentTolerance 3 pont alá szigorítása eltöri az OCR-ből származó szódobozokat, amelyeknek a bal éle ennél nagyobbat rezeg. A sor szintű jel valóban kétértelmű, így a javításnak olyan jeltől kell jönnie, amelyet a sorok önmagukban nem hordoznak

Mitől válik valódivá egy oszlophathatár?

Egy valódi oszlophathatár az oldal azon függőleges sávja, amely üresen marad az általa elválasztott minden sorban. Egy táblában minden oszloppár között van ilyen, felépítésénél fogva, mert a cellák közös X pozíciókhoz igazodva rendeződtek el. A sorkizárt bekezdés minden sorban más vízszintes pozícióknál nyújtja meg a szóközeit, így egyetlen sáv sem éli túl egynél-kettőnél több sor metszetét. A PDFium Component mostantól pontosan ezt vizsgálja: miután a jelölt szócsoportjai horgonyoszlopokhoz rendelődtek, minden szomszédos oszloppárra, minden olyan soron, amelynek mindkét cellájában van tartalom, veszi a bal cella szavainak jobb szélétől a jobb cella szavainak bal széléig tartó intervallumot, ezeket az intervallumokat sorokon át metszetbe hozza, és az egész jelöltet visszautasítja, ha a metszet keskenyebb, mint a MinColumnGap szorozva 0,5-tel, ami az alapértéknél 6 pont

Két részlet számít. Azok a sorok, amelyekben valamelyik cella üres, nem szavaznak, így az a tábla, amelyben van üres cella, vagy amelynek a fejléce kevesebb oszlopra terjed ki, mint a törzs, továbbra is átmegy. A folyosó szélessége pedig a MinColumnGap értékéből származik, nem önálló opcióként van kitéve, mert a kettő ugyanazt a fizikai dolgot írja le: az oszlopok között hagyott rést. A logika elég kicsi ahhoz, hogy reprodukáljuk, ha nyers szódobozokra építünk a tábla-API helyett, és az alábbi minta a komponensen belüli ellenőrzést tükrözi:

uses
  Math, PDFium;

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

// False-t ad vissza, ha bármely szomszédos oszloppárból hiányzik a szövegmentes függőleges
// folyosó, amely legalább MinColumnGap / 2 széles az őt használó sorokon át
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;                             // az üres cellák nem szavaznak
      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;

Miért nyerődtek ki kétszer a vonalazott táblák?

A vonalazott táblák azért nyerődtek ki kétszer, mert a whitespace-menet korábban az oldal minden szavát látta, beleértve azokat is, amelyeket a vonalazott menet már rácsba helyezett, egy tiszta vonalazott tábla pedig felépítésénél fogva tökéletesen igazított whitespace-tábla is egyben. Egy átfedésvizsgálat már eddig is visszautasította azt a whitespace-jelöltet, amelynek a határai egy meglévő tábla több mint felét lefedték, de az a jelölt, amely a tábla alsó sorait összevonta alatta néhány igazított szövegsorral, e küszöb alá eshetett, és túlélhetett második, valamivel nagyobb táblaként, amely belefolyt a szomszédjába. Az ExtractTables mostantól eltávolítja ezeket a szavakat, mielőtt a whitespace-menet lefut. Egy szó akkor esik ki, ha a középpontja a vonalazott menet bármelyik táblájának a határain belül van; a középpontot használjuk teljes tartalmazás helyett, hogy az a szó, amely egy pont tört részével átnyúlik egy szegélyen, ahhoz a táblához kerüljön, amelyhez vizuálisan tartozik. A whitespace-stratégia így már csak a szabad szavakon dolgozik, ami azt is jelenti, hogy egy közvetlenül a vonalazott tábla alatt ülő kis, vonalazatlan tábla a saját érdemei szerint ismerődik fel, ahelyett hogy összeolvadna a felette lévő ráccsal

Miért lett a „Purpose of Request:" szövegből „of Purpose Request:"?

A szavak azért jöttek ki átrendezve, mert a PDFium Component által épített szódobozok glifák befoglaló dobozainak uniói, az „of" szónak pedig nincs leszálló szála, míg a „Purpose" és a „Request:" szavaknak van. A FPDFText_GetCharBox a glifa festékének szoros dobozát adja vissza oldaltérben, nem a font ascenderéhez és descenderéhez kitöltött dobozt, a szódoboz pedig a karakterei dobozainak uniója. A leszálló szál nélküli szó ezért rövidebb, függőleges középpontja pedig feljebb ül, a szóban forgó űrlapon 2-3 ponttal. A régi cellaszöveg-rutin a szavakat először középpont-Y szerint rendezte, 1 pontos toleranciával az „ugyanaz a sor" esetére, majd bal él szerint; az „of" túljutott a tolerancián, a többi fölött saját sorként rendeződött, és elsőként került ki

Ez nem is annyira PDFium-sajátosság, mint inkább annak a következménye, ahogyan a PDF elhelyezi a szöveget. Az ISO 32000-1 §9.2.2 és §9.4.4 a glifák elhelyezését a szövegtérbeli alapvonal menti vízszintes elmozdulásként definiálja, és a fájl egyetlen függőleges metrikája is fontonkénti: a fontdescriptor Ascent, Descent és FontBBox bejegyzései a §9.8.1-ben. A fájlban semmi nem mondja meg, hogy két glifa egy sorban van; ezt a geometriából kell kikövetkeztetni, és azok a szoros glifadobozok, amelyektől a kijelöléskiemelés jól néz ki — ahogy a szövegsor-kijelölés PDFium char boxokkal leírja —, rossz bemenetet jelentenek egy középponttávolság-összehasonlításhoz

A 3.117.0 verzió javítása átfogalmazza a kérdést abból, hogy „milyen messze vannak a középpontok", abba, hogy „mennyire fedik egymást függőlegesen a dobozok". A cellaszöveg úgy áll össze, hogy először a cella szavait látható sorokba csoportosítjuk, ahol egy szó akkor csatlakozik egy sorhoz, ha a függőleges átfedése a sor futó határaival legalább a két magasság közül a kisebbnek a 25 százaléka, majd minden sort bal él szerint beszúró rendezéssel rendezünk, végül a sorokat sortöréssel fűzzük össze. A „Purpose" és az „of" a teljes x-magasságon átfedésben van, ami jóval több, mint a rövidebb doboz 25 százaléka, így ugyanabba a sorba kerülnek, és X szerint rendeződnek, ahogy kell

A szövegsorokat átfedés szerint csoportosítsuk, ne középponttávolság szerint

Az általános szabály, amelyet érdemes elvinni ebből a hibából: minden olyan PDF-szövegelrendező kód, amely a függőleges középpontok rögzített toleranciához való összehasonlításával dönti el, hogy „ugyanaz a sor", valódi fontoknál el fog bukni, méghozzá csendben: semmi nem jelez hibát, a szavak egyszerűen rossz sorrendben jönnek ki. A vegyes leszálló szálak a legenyhébb kiváltó ok. Egy félkövér, 12 pontos címke 10 pontos értékek mellett, egy felső indexbe tett lábjegyzetjelölő, egy tartalék fontból rajzolt pénznemszimbólum, és a szavankénti magasságzajjal rendelkező OCR-szódobozok mind nagyobbat mozdítanak a középpontokon, mint bármely tolerancia, amely még elválasztja a szomszédos sorokat 10 pontos szöveg 12 pontos sorközénél. Az átfedési arány méretfüggetlen: két egy alapvonalon lévő doboz a közös x-magasságon átfedésben van, bármit tesznek az ascendereik és descendereik, két szomszédos sorban lévő doboz pedig egyáltalán nem fedi egymást

Ugyanez a szabály könnyen alkalmazható a táblakinyerésen kívül is. A TPdf.PageWordBoxes visszaadja az aktív oldal minden szavát az oldaltérbeli téglalapjával együtt, így egy oldal látható sorokba csoportosítása rövid ciklus:

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>;   // soronkénti futó unió
  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;
  // a sorokat Rect.Left szerint rendezzük, mielőtt kiolvassuk őket; a PageWordBoxes
  // a szavakat tartalomfolyam-sorrendben adja vissza, ami nem feltétlenül vizuális
end;

Mi változik a meglévő hívóknál, és hol vannak a határok

A részlet lényege a predikátum, nem a ciklus; bármi többre, mint egy gyors listázás, a strukturált szövegmodellből induljon, amely már hordoz blokkokat, sorokat és olvasási sorrend forrását, ahogy a strukturált PDF-szövegkinyerés olvasási sorrenddel tárgyalja. A meglévő táblahívók mindhárom javítást megkapják anélkül, hogy az opcióikhoz hozzányúlnának. A folyosó küszöbe a MinColumnGap felében rögzített, a whitespace-stratégia megtartja a kétsoros alsó korlátját akkor is, ha a MinRows 1-re van állítva (amit a vonalazott stratégia mostantól elfogad), a vonalazottat előnyben részesítő szószűrés pedig feltétel nélküli, valahányszor mindkét stratégia be van kapcsolva. A kiadáshoz használt tizenhárom dokumentumból álló mintahalmazon a whitespace-menet korábban 34 töredéket és téves találatot adott vissza 9 vonalazott tábla mellett; a kiadás után egyet sem, a vonalazott táblák száma pedig 41-re nőtt, bár a növekedés nagy része ugyanabból a kiadásból származik, amely megtanította a vonalazott detektort a kitöltött téglalapokként rajzolt szegélyek olvasására — az viszont külön történet

Az őszinte határok: a folyosóvizsgálatnak legalább egy olyan sor kell, amelynek egy határ mindkét oldalán van tartalma, hogy egyáltalán visszautasíthasson valamit, így az a kétsoros jelölt, amelynek két megnyújtott köze épp 6 ponton belülre esik egymáshoz, továbbra is átmegy. Ez szűk véletlen egybeesés, nem pedig az a majdnem bizonyosság, ami korábban volt, a prózában gazdag, valódi kétsoros táblákat nem tartalmazó dokumentumok viszont bezárhatják a MinRows 3-ra állításával. A balra igazított, foghíjas szöveg soha nem volt probléma, és nem is érinti semmi. A PDF-nek pedig továbbra sincs táblaobjektuma; az ISO 32000-1 §14.8.4.3 definiál egy Table struktúraelem, de csak a Tagged PDF hordozza, így minden más esetben a rács a geometriából levont következtetés marad, és az egyes TPdfTable példányokon lévő bizonyossági érték azért van ott, mert a következtetés megérdemel egy pontszámot

A táblakinyerés, a strukturált szöveg és a szódobozok mind ugyanabból az oldalmodellből olvasnak Delphi, C++Builder és Lazarus alatt; a teljes API, benne a TPdfTableExtractionOptions és a mellette érkező TableExtractionLab demó, a PDFium Component for Delphi oldalán van leírva