Fałszywe tabele w PDF z tekstu wyjustowanego w Delphi

PDFium Component w wersji 3.117.0 przestaje raportować wyjustowane akapity jako tabele wyrównane po białych znakach: wymaga teraz, by każda granica kolumny była pionowym korytarzem bez tekstu w żadnym wierszu, który rozdziela, pomija słowa zajęte już przez siatkę i składa tekst komórek po pionowym nakładaniu, a nie po odległości środków ramek glifów. Wszystkie trzy zmiany żyją w ExtractTables i ExtractDocumentTables i nie wymagają żadnej opcji

Zgłoszenie, które to zapoczątkowało, było mało spektakularne. Strona komunikatu prasowego, na której nie ma żadnej tabeli, wracała z ExtractTables z tabelą 5x4 po białych znakach, z pewnością wygodnie powyżej domyślnego MinConfidence równego 0,5, a komórki trzymały fragmenty zwykłego tekstu głównego. Formularz zgłoszeniowy zrobił to samo ze swoimi akapitami eseju i wyprodukował tabelę 3x4 oraz 5x3. Oba dokumenty były wyjustowane. Oczywistą reakcją jest strojenie progów, a pożyteczny wniosek z tego wydania jest taki, że strojenie tego nie naprawi, bo reguła, którą się stroiło, zadawała niewłaściwe pytanie

uses
  PDFium;

// Sprawdzenie regresyjne: wypisz każdą tabelę po białych znakach, żeby stronę
// o której wiesz, że to sama proza, dało się potwierdzić jako czystą
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;

Dlaczego wyjustowany tekst wygląda jak tabela?

Wyjustowany akapit wygląda jak tabela, bo wyjustowany wiersz to rząd słów rozdzielonych odstępami, które silnik składu rozciągnął, a gdy rozciągnięty odstęp osiągnie MinColumnGap, detektor nie ma w obrębie wiersza sposobu, by odróżnić go od separatora kolumn. Strategia białych znaków w PDFium Component grupuje ramki słów w wiersze wizualne, dzieli każdy wiersz na grupy słów wszędzie tam, gdzie odległość pozioma od poprzedniego słowa wynosi co najmniej MinColumnGap (domyślnie 12 punktów), i przyjmuje tabelę, gdy co najmniej dwa kolejne wiersze powtarzają co najmniej MinColumns lewostronnie wyrównanych punktów odniesienia grup w granicach AlignmentTolerance, czyli 3 punktów. To ta reguła, którą opisuje przegląd wykrywania tabel, i dla prawdziwej wyrównanej tabeli jest dokładnie słuszna

Zastosuj ją teraz do dwudziestu wierszy wyjustowanej prozy o stopniu 10. Każdy wiersz jest rozciągany do tego samego prawego marginesu, więc wiersz kończący się długim słowem otwiera swoje wewnętrzne odstępy, a w akapicie z kilkoma krótkimi wierszami część tych odstępów przekracza 12 punktów. Dwa kolejne wiersze potrzebują tylko po jednym rozciągniętym odstępie, trafiającym w granicach 3 punktów w tę samą pozycję X, by powstał kandydat na dwuwierszową, dwukolumnową tabelę. Przy odpowiedniej liczbie wierszy to nie pech; to prawdopodobieństwo zmierzające do pewności, a tabela 5x4 na komunikacie prasowym była po prostu tym przebiegiem, w którym cztery takie odstępy ustawiły się w pięciu wierszach

Każdy próg wymienia jedną klasę dokumentów na inną. Podniesienie MinColumnGap do 20 punktów gubi zwarte kolumny gęstych raportów finansowych, czyli dokładnie ten przypadek, dla którego wartość domyślną już obniżono. Podniesienie MinRows do 3 odrzuca prawdziwe dwuwierszowe tabele i tylko zmniejsza szanse przy długich akapitach. Zacieśnienie AlignmentTolerance poniżej 3 punktów psuje ramki słów pochodzące z OCR, których lewe krawędzie drgają bardziej. Sygnał na poziomie wiersza jest naprawdę niejednoznaczny, więc poprawka musi przyjść z sygnału, którego pojedyncze wiersze same nie niosą

Co czyni granicę kolumny prawdziwą?

Prawdziwa granica kolumny to pionowy pas strony, który pozostaje pusty we wszystkich wierszach, które rozdziela. Tabela ma taki pas między każdą parą kolumn z założenia, bo komórki układano względem wspólnych pozycji X. Wyjustowany akapit rozciąga swoje odstępy między słowami w różnych miejscach poziomych w każdym wierszu, więc żaden pas nie przetrwa przecięcia więcej niż jednego czy dwóch wierszy. PDFium Component sprawdza teraz dokładnie to: gdy grupy słów kandydata zostaną przypisane do kolumn odniesienia, dla każdej pary sąsiednich kolumn bierze w każdym wierszu, który ma treść w obu komórkach, przedział od najbardziej prawej krawędzi słów lewej komórki do najbardziej lewej krawędzi słów prawej komórki, przecina te przedziały przez wiersze i odrzuca całego kandydata, jeśli przecięcie jest węższe niż MinColumnGap razy 0,5, czyli 6 punktów przy wartościach domyślnych

Znaczące są dwa szczegóły. Wiersze, w których którakolwiek komórka jest pusta, nie głosują, więc tabela z pustą komórką albo nagłówek obejmujący mniej kolumn niż ciało tabeli nadal przechodzi. A szerokość korytarza jest wyprowadzana z MinColumnGap, a nie wystawiona jako osobna opcja, bo obie rzeczy opisują to samo fizyczne zjawisko: odstęp, który projektant zostawia między kolumnami. Ta logika jest dość mała, by ją odtworzyć, jeśli budujesz na surowych ramkach słów, a nie na API tabel, a próbka poniżej odwzorowuje to sprawdzenie z wnętrza komponentu:

uses
  Math, PDFium;

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

// Zwraca False, gdy dowolna para sąsiednich kolumn nie ma pionowego
// korytarza wolnego od tekstu o szerokości co najmniej MinColumnGap / 2
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;                             // puste komórki nie głosują
      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;

Dlaczego tabele siatkowe były wyciągane dwa razy?

Tabele siatkowe były wyciągane dwa razy, bo przebieg po białych znakach widział kiedyś każde słowo na stronie, w tym słowa, które przebieg siatkowy umieścił już w siatce — a czysta tabela siatkowa jest z założenia także doskonale wyrównaną tabelą po białych znakach. Sprawdzenie nakładania odrzucało już kandydata po białych znakach, którego granice obejmowały więcej niż połowę istniejącej tabeli, ale kandydat łączący dolne wiersze tabeli z kilkoma wyrównanymi liniami tekstu pod nią mógł spaść poniżej tego stosunku i przetrwać jako druga, nieco większa tabela nachodząca na sąsiada. ExtractTables usuwa teraz te słowa, zanim ruszy przebieg po białych znakach. Słowo jest wyrzucane, gdy jego punkt środkowy leży wewnątrz granic którejkolwiek tabeli wyprodukowanej przez przebieg siatkowy; używany jest środek, a nie pełne zawieranie, żeby słowo wystające poza obramowanie o ułamek punktu poszło za tabelą, do której wizualnie należy. Strategia białych znaków pracuje potem tylko na wolnych słowach, co oznacza też, że mała tabela bez obramowań leżąca bezpośrednio pod siatkową jest wykrywana na własnych prawach, zamiast zlewać się z siatką nad sobą

Dlaczego „Purpose of Request:” wyszło jako „of Purpose Request:”?

Słowa wyszły w zmienionej kolejności, bo ramki słów, które buduje PDFium Component, są sumami prostokątów otaczających glify, a „of” nie ma wydłużenia dolnego, podczas gdy „Purpose” i „Request:” mają. FPDFText_GetCharBox zwraca ciasny prostokąt tuszu glifu w przestrzeni strony, a nie prostokąt dopełniony do wyniesienia i wydłużenia czcionki, a ramka słowa to suma prostokątów jego znaków. Słowo bez wydłużeń dolnych jest więc krótsze, a jego pionowy środek siedzi wyżej — o 2 do 3 punktów w tym formularzu. Stara procedura tekstu komórki sortowała słowa najpierw po środku Y, z 1-punktową tolerancją na „ten sam wiersz”, a potem po lewej krawędzi; „of” przechodziło tę tolerancję, sortowało się jako własny wiersz nad pozostałymi i było emitowane pierwsze

To nie tyle kaprys PDFium, ile konsekwencja tego, jak PDF pozycjonuje tekst. ISO 32000-1 §9.2.2 i §9.4.4 definiują umieszczanie glifów jako przesunięcie poziome wzdłuż linii bazowej w przestrzeni tekstu, a jedyne metryki pionowe, jakie niesie plik, są przypisane do czcionki: wpisy Ascent, Descent i FontBBox deskryptora czcionki z §9.8.1. Nic w pliku nie mówi, że dwa glify dzielą wiersz; trzeba to wywnioskować z geometrii, a ciasne prostokąty glifów, które sprawiają, że podświetlanie zaznaczenia wygląda dobrze — jak opisuje zaznaczanie wierszy tekstu ramkami znaków w PDFium — są niewłaściwym wejściem dla porównywania odległości środków

Poprawka w wersji 3.117.0 zmienia pytanie z „jak daleko są od siebie środki” na „jak bardzo prostokąty nakładają się pionowo”. Tekst komórki jest składany tak: najpierw słowa komórki grupuje się w wiersze wizualne, gdzie słowo dołącza do wiersza, gdy jego pionowe nakładanie z bieżącymi granicami wiersza wynosi co najmniej 25 procent mniejszej z dwóch wysokości, potem każdy wiersz sortuje się wstawianiem po lewej krawędzi, a na końcu wiersze łączy się znakiem przejścia do nowego wiersza. „Purpose” i „of” nakładają się na całej wysokości x, a to znacznie więcej niż 25 procent krótszego prostokąta, więc lądują w tym samym wierszu i sortują się po X, jak powinny

Grupuj wiersze tekstu po nakładaniu, nie po odległości środków

Reguła, którą warto wynieść z tego błędu, jest ogólna: każdy kod składu tekstu PDF, który rozstrzyga „ten sam wiersz”, porównując pionowe środki z ustaloną tolerancją, polegnie na prawdziwych czcionkach, i to po cichu: nic nie zgłasza błędu, słowa po prostu wychodzą w złej kolejności. Wymieszane wydłużenia dolne to najłagodniejszy wyzwalacz. Pogrubiona etykieta o stopniu 12 obok wartości o stopniu 10, znacznik przypisu w indeksie górnym, symbol waluty rysowany z czcionki zastępczej i ramki słów z OCR z szumem wysokości na słowo — wszystko to przesuwa środki bardziej niż jakakolwiek tolerancja, która wciąż rozdziela sąsiednie wiersze tekstu o stopniu 10 przy interlinii 12. Stosunek nakładania nie zależy od rozmiaru: dwa prostokąty na jednej linii bazowej nakładają się na wspólnej wysokości x niezależnie od swoich wyniesień i wydłużeń dolnych, a dwa prostokąty w sąsiednich wierszach nie nakładają się wcale

Tę samą regułę łatwo zastosować poza wyciąganiem tabel. TPdf.PageWordBoxes zwraca każde słowo na aktywnej stronie wraz z jego prostokątem w przestrzeni strony, więc zgrupowanie strony w wiersze wizualne to krótka pętla:

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>;   // suma bieżąca na wiersz
  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;
  // posortuj każdy wiersz po Rect.Left przed czytaniem; PageWordBoxes zwraca
  // słowa w kolejności strumienia treści, która nie musi być wizualna
end;

Co się zmienia dla istniejących wywołań i gdzie są granice

W tym fragmencie kodu chodzi o predykat, a nie o pętlę; do czegokolwiek więcej niż szybki zrzut zacznij od modelu tekstu strukturalnego, który niesie już bloki, wiersze i źródło kolejności czytania, jak opisuje strukturalne wyciąganie tekstu PDF z kolejnością czytania. Istniejące wywołania tabel dostają wszystkie trzy poprawki bez dotykania swoich opcji. Próg korytarza jest ustalony na połowę MinColumnGap, strategia białych znaków zachowuje swój próg dwóch wierszy nawet przy MinRows ustawionym na 1 (co strategia siatkowa teraz przyjmuje), a filtrowanie słów zajętych przez siatkę działa bezwarunkowo, gdy obie strategie są włączone. Na zestawie 13 dokumentów użytym do wydania przebieg po białych znakach zwracał wcześniej 34 fragmenty i fałszywe trafienia obok 9 tabel siatkowych; po wydaniu nie zwraca żadnego, a liczba tabel siatkowych wzrosła do 41, choć większość tego wzrostu pochodzi z tego samego wydania, które nauczyło detektor siatek czytać obramowania rysowane jako wypełnione prostokąty — a to osobna historia

Uczciwe granice: test korytarza potrzebuje co najmniej jednego wiersza z treścią po obu stronach granicy, żeby cokolwiek odrzucić, więc dwuwierszowy kandydat, którego dwa rozciągnięte odstępy przypadkiem wypadną w granicach 6 punktów od siebie, wciąż przechodzi. To wąski zbieg okoliczności, a nie prawie pewność jak wcześniej, ale dokumenty pełne prozy, w których nie ma prawdziwych dwuwierszowych tabel, mogą tę lukę zamknąć, ustawiając MinRows na 3. Tekst wyrównany do lewej z poszarpanym prawym brzegiem nigdy nie był problemem i nie jest tym dotknięty. A PDF wciąż nie ma obiektu tabeli; ISO 32000-1 §14.8.4.3 definiuje element struktury Table, ale niesie go tylko Tagged PDF, więc dla całej reszty siatka pozostaje wnioskiem z geometrii, a wartość pewności na każdym TPdfTable jest tam dlatego, że wnioskowanie zasługuje na ocenę

Wyciąganie tabel, tekst strukturalny i ramki słów czytają z tego samego modelu strony w Delphi, C++Builderze i Lazarusie; pełne API, wraz z TPdfTableExtractionOptions i dostarczanym obok demem TableExtractionLab, jest opisane na stronie PDFium Component dla Delphi