Falsi positivi di tabella da testo giustificato in Delphi

La versione 3.117.0 di PDFium Component smette di segnalare i paragrafi giustificati come tabelle allineate su spaziature, richiedendo che ogni confine di colonna sia un corridoio verticale senza testo su nessuna riga che separa, saltando le parole già rivendicate da una griglia e assemblando il testo delle celle per sovrapposizione verticale invece che per distanza tra i centri dei box dei glifi. Tutte e tre le modifiche vivono dentro ExtractTables e ExtractDocumentTables e non richiedono alcuna opzione

La segnalazione da cui è partito tutto era poco glamour. Una pagina di comunicato stampa senza alcuna tabella tornava da ExtractTables con una tabella 5x4 da spaziature, con una confidence comodamente sopra il MinConfidence di default di 0.5, e le celle contenevano frammenti di normale testo di corpo. Un modulo di ammissione faceva lo stesso con i suoi paragrafi di tema e produceva una 3x4 e una 5x3. Entrambi i documenti erano giustificati. La risposta ovvia è ritoccare le soglie, e la lezione utile di questa release è che la taratura non può risolverlo, perché la regola che si stava tarando poneva la domanda sbagliata

uses
  PDFium;

// Controllo di regressione: elenca ogni tabella da spaziature di un documento così una pagina
// che sai essere solo prosa può essere confermata pulita
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;

Perché il testo giustificato sembra una tabella?

Un paragrafo giustificato sembra una tabella perché una riga giustificata è una riga di parole separate da spazi che il motore di impaginazione ha allungato, e una volta che uno spazio allungato raggiunge MinColumnGap il rilevatore non ha alcun modo, a livello di singola riga, di distinguerlo da un separatore di colonna. La strategia sulle spaziature in PDFium Component raggruppa i box delle parole in righe visive, spezza ogni riga in gruppi di parole ovunque la distanza orizzontale dalla parola precedente sia almeno MinColumnGap (12 punti per default), e accetta una tabella quando almeno due righe consecutive ripetono almeno MinColumns ancore di gruppo allineate a sinistra entro AlignmentTolerance, che è 3 punti. È la regola descritta nella panoramica sul rilevamento delle tabelle, e per una vera tabella allineata è esattamente giusta

Ora applicalo a venti righe di prosa giustificata da 10 punti. Ogni riga è allungata fino allo stesso margine destro, quindi una riga che finisce con una parola lunga apre gli spazi interni, e in un paragrafo con qualche riga corta alcuni di quegli spazi superano i 12 punti. A due righe consecutive basta uno spazio allungato ciascuna, che cada entro 3 punti dalla stessa posizione X, per formare un candidato a due righe e due colonne. Su abbastanza righe non è sfortuna; è una probabilità che tende alla certezza, e la 5x4 sul comunicato stampa era semplicemente la serie in cui quattro di quegli spazi si sono allineati su cinque righe

Ogni soglia baratta una classe di documenti contro un'altra. Alzare MinColumnGap a 20 punti fa perdere le colonne compatte dei report finanziari densi, che è esattamente il caso per cui il default era già stato abbassato. Alzare MinRows a 3 scarta vere tabelle a due righe e si limita ad abbassare le probabilità per i paragrafi lunghi. Stringere AlignmentTolerance sotto i 3 punti rompe i box delle parole derivati da OCR, i cui bordi sinistri oscillano più di così. Il segnale a livello di riga è genuinamente ambiguo, quindi la correzione deve venire da un segnale che le righe non portano da sole

Che cosa rende reale un confine di colonna?

Un vero confine di colonna è una striscia verticale della pagina che resta vuota su ogni riga che separa. Una tabella ne ha uno tra ogni coppia di colonne per costruzione, perché le celle sono state disposte su posizioni X condivise. Un paragrafo giustificato allunga i suoi spazi tra le parole in posizioni orizzontali diverse su ogni riga, quindi nessuna striscia sopravvive all'intersezione di più di una riga o due. PDFium Component ora testa esattamente questo: dopo che i gruppi di parole del candidato sono stati assegnati alle colonne ancora, per ogni coppia di colonne adiacenti prende, su ogni riga che abbia contenuto in entrambe le celle, l'intervallo dal bordo più a destra delle parole della cella sinistra al bordo più a sinistra delle parole della cella destra, interseca quegli intervalli tra le righe, e rifiuta l'intero candidato se l'intersezione è più stretta di MinColumnGap per 0.5, che con i default è 6 punti

Due dettagli contano. Le righe in cui una delle due celle è vuota non votano, quindi una tabella con una cella vuota, o con un'intestazione che copre meno colonne del corpo, passa comunque. E la larghezza del corridoio è derivata da MinColumnGap invece di essere esposta come opzione separata, perché le due cose descrivono lo stesso oggetto fisico: lo spazio che un designer lascia tra le colonne. La logica è abbastanza piccola da riprodurre se costruisci su box di parole grezzi invece che sull'API delle tabelle, e il campione qui sotto rispecchia il controllo dentro il componente:

uses
  Math, PDFium;

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

// Restituisce False quando una coppia di colonne adiacenti non ha un corridoio
// verticale libero da testo largo almeno MinColumnGap / 2 sulle righe che lo usano
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;                             // le celle vuote non votano
      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;

Perché le tabelle con griglia venivano estratte due volte?

Le tabelle con griglia venivano estratte due volte perché il passaggio sulle spaziature vedeva ogni parola della pagina, comprese le parole che il passaggio sulle griglie aveva già collocato in una griglia, e una tabella con griglia pulita è per costruzione anche una tabella da spaziature perfettamente allineata. Un controllo di sovrapposizione rifiutava già un candidato da spaziature i cui limiti coprissero più della metà di una tabella esistente, ma un candidato che univa le righe inferiori della tabella a qualche riga allineata di testo sotto di essa poteva stare sotto quel rapporto e sopravvivere come seconda tabella, leggermente più grande, che sconfinava nella vicina. Ora ExtractTables rimuove quelle parole prima che giri il passaggio sulle spaziature. Una parola viene scartata quando il suo punto centrale cade dentro i limiti di una qualsiasi tabella prodotta dal passaggio sulle griglie; si usa il centro invece della contenimento completo perché una parola che scavalca un bordo di una frazione di punto segua la tabella a cui appartiene visivamente. La strategia sulle spaziature lavora poi solo sulle parole libere, il che significa anche che una piccola tabella senza griglia che sta direttamente sotto una con griglia viene rilevata per meriti propri invece di essere fusa con la griglia sopra di essa

Perché "Purpose of Request:" usciva come "of Purpose Request:"?

Le parole uscivano riordinate perché i box delle parole che PDFium Component costruisce sono unioni dei bounding box dei glifi, e "of" non ha discendenti mentre "Purpose" e "Request:" sì. FPDFText_GetCharBox restituisce il box stretto dell'inchiostro del glifo in coordinate di pagina, non un box esteso fino all'ascendente e al discendente del font, e il box della parola è l'unione dei box dei suoi caratteri. Una parola senza discendenti è quindi più corta e il suo centro verticale sta più in alto, di 2 o 3 punti nel modulo in questione. La vecchia routine del testo delle celle ordinava le parole prima per centro Y, con una tolleranza di 1 punto per "stessa riga", e poi per bordo sinistro; "of" superava la tolleranza, si ordinava come riga a sé sopra le altre e veniva emessa per prima

Questa non è tanto una stranezza di PDFium quanto una conseguenza di come il PDF posiziona il testo. ISO 32000-1 §9.2.2 e §9.4.4 definiscono il posizionamento dei glifi come spostamento orizzontale lungo la baseline nello spazio del testo, e le uniche metriche verticali che il file porta sono per font: le voci Ascent, Descent e FontBBox del font descriptor in §9.8.1. Nulla nel file dice che due glifi condividono una riga; va dedotto dalla geometria, e i box stretti dei glifi che fanno apparire giusta l'evidenziazione della selezione, come descritto nella selezione delle righe di testo con i char box di PDFium, sono l'input sbagliato per un confronto tra distanze dei centri

La correzione nella versione 3.117.0 cambia la domanda da "quanto distano i centri" a "quanto si sovrappongono verticalmente i box". Il testo delle celle viene assemblato prima raggruppando le parole della cella in righe visive, dove una parola si unisce a una riga quando la sua sovrapposizione verticale con i limiti correnti della riga è almeno il 25 per cento della minore tra le due altezze, poi ordinando per inserimento ogni riga per bordo sinistro, e infine unendo le righe con un'interruzione di riga. "Purpose" e "of" si sovrappongono per tutta l'altezza della x, che è molto più del 25 per cento del box più corto, quindi finiscono sulla stessa riga e si ordinano per X come previsto

Raggruppa le righe di testo per sovrapposizione, non per distanza dei centri

La regola che vale la pena portarsi via da questo bug è generale: qualsiasi codice di layout del testo PDF che decida "stessa riga" confrontando i centri verticali con una tolleranza fissa fallirà sui font reali, e il fallimento è silenzioso: nulla va in errore, le parole escono semplicemente nell'ordine sbagliato. I discendenti misti sono il grilletto più blando. Un'etichetta in grassetto da 12 punti accanto a valori da 10 punti, un marcatore di nota in apice, un simbolo di valuta disegnato da un font di fallback e box di parole da OCR con rumore di altezza per parola spostano tutti i centri più di qualsiasi tolleranza che continui a separare righe adiacenti di testo da 10 punti con interlinea 12. Il rapporto di sovrapposizione è invariante rispetto alla dimensione: due box su una stessa baseline si sovrappongono per la loro x-height condivisa, qualunque cosa facciano ascendenti e discendenti, e due box su righe adiacenti non si sovrappongono per nulla

La stessa regola è facile da applicare fuori dall'estrazione delle tabelle. TPdf.PageWordBoxes restituisce ogni parola della pagina attiva con il suo rettangolo in coordinate di pagina, quindi raggruppare una pagina in righe visive è un ciclo breve:

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>;   // unione corrente per riga
  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;
  // ordina ogni riga per Rect.Left prima di leggerla; PageWordBoxes restituisce
  // le parole in ordine di content stream, che non è garantito essere visivo
end;

Che cosa cambia per chi già usa la libreria, e dove sono i limiti

Il punto di quel frammento è il predicato, non il ciclo; per qualsiasi cosa oltre a un dump veloce, parti dal modello di testo strutturato, che porta già blocchi, righe e una sorgente di ordine di lettura, come trattato in estrazione di testo strutturato PDF con ordine di lettura. Chi già chiama la parte tabelle ottiene tutte e tre le correzioni senza toccare le proprie opzioni. La soglia del corridoio è fissata a metà di MinColumnGap, la strategia sulle spaziature mantiene la sua soglia di due righe anche quando MinRows è impostato a 1 (che la strategia sulle griglie ora accetta), e il filtraggio delle parole già prese dalle griglie è incondizionato ogni volta che entrambe le strategie sono attive. Sul set di 13 documenti campione usato per la release, il passaggio sulle spaziature restituiva prima 34 frammenti e falsi positivi accanto a 9 tabelle con griglia; dopo la release non ne restituisce alcuno, e il conteggio delle tabelle con griglia è salito a 41, anche se gran parte di quell'aumento viene dalla stessa release che ha insegnato al rilevatore di griglie a leggere i bordi disegnati come rettangoli pieni, che è una storia a parte

I limiti dichiarati onestamente: il test del corridoio ha bisogno di almeno una riga con contenuto su entrambi i lati di un confine per rifiutare qualcosa, quindi un candidato a due righe i cui due spazi allungati cadano entro 6 punti l'uno dall'altro passa comunque. È una coincidenza stretta e non la quasi certezza di prima, ma documenti pieni di prosa senza vere tabelle a due righe possono chiudere la falla impostando MinRows a 3. Il testo allineato a sinistra con margine irregolare non è mai stato il problema e non è toccato. E il PDF non ha ancora un oggetto tabella; ISO 32000-1 §14.8.4.3 definisce un elemento di struttura Table, ma solo il Tagged PDF lo porta, quindi per tutto il resto la griglia resta un'inferenza dalla geometria, e il valore di confidence su ogni TPdfTable c'è perché un'inferenza merita un punteggio

L'estrazione delle tabelle, il testo strutturato e i box delle parole leggono tutti dallo stesso modello di pagina in Delphi, C++Builder e Lazarus; l'API completa, inclusi TPdfTableExtractionOptions e la demo TableExtractionLab che la accompagna, è descritta nella pagina di PDFium Component per Delphi