Corriger les faux positifs de table depuis du texte justifié

Une page de texte courant justifié peut ressortir d'un détecteur de tables par espaces blancs comme une grille de plusieurs colonnes, chaque cellule portant une demi-phrase cassée et le score de confiance bien au-dessus de tout seuil auquel vous penseriez à régler. Il n'y a pas de table sur cette page. Le détecteur a trouvé des écarts entre mots assez larges pour passer pour des séparateurs de colonnes et quelques lignes consécutives où ces écarts tombaient à presque la même position X, et rien que sur l'alignement c'est exactement à quoi ressemble une table. La réponse est d'arrêter de juger une frontière de colonne une rangée à la fois et de demander si une bande de papier blanc court sur la page entre les colonnes

Pourquoi le texte justifié passe-t-il un test de table par espaces blancs ?

Le texte justifié passe parce qu'une ligne justifiée est une rangée de mots séparés par des écarts que le moteur de mise en page a étirés, et dès qu'un écart étiré franchit le seuil de colonne, rien sur cette seule ligne le distingue d'une gouttière. La stratégie par espaces blancs de PDFium Component fonctionne comme la plupart des détecteurs par espaces. TPdf.ExtractTables regroupe les boîtes de mots en lignes visuelles, coupe chaque ligne partout où la distance horizontale d'un mot au suivant vaut au moins MinColumnGap (12 points dans TPdfTableExtractionOptions.Default), et regroupe les bords gauches des groupes de mots obtenus en ancres de colonnes à AlignmentTolerance près, qui vaut 3 points par défaut. Une ancre survit seulement si elle se répète sur au moins MinRows lignes, et chaque ligne de la candidate doit toucher au moins MinColumns ancres distinctes. Pour une vraie table alignée cette règle est correcte, et c'est la règle décrite dans la vue d'ensemble de la détection de tables

L'arithmétique côté prose est moins indulgente qu'il n'y paraît. Supposez une ligne de 10 points dans une colonne de gazette de 180 points qui s'arrête 30 points avant la marge droite parce que le mot suivant ne rentrait pas, et la ligne ne porte que trois espaces entre mots parce que ses mots sont longs. Un moteur de justification répartit ces 30 points sur les trois espaces, si bien que chacun passe d'environ 2,5 points à 12,5 points et franchit le MinColumnGap par défaut. Une seconde ligne n'a besoin que d'un écart étiré dont le mot suivant démarre à 3 points ou moins de celui de la première ligne, et le détecteur a une candidate de deux lignes sur deux colonnes

La façon dont l'étirement est encodé n'importe pas. ISO 32000-1 §9.3.3 n'applique l'espacement des mots (Tw) qu'au code de caractère mono-octet 32, si bien que les producteurs qui emploient des polices multi-octets positionnent d'ordinaire les mots avec des ajustements numériques dans un tableau TJ (§9.4.3) ; dans les deux cas les boîtes de mots ressortent identiques. La dernière ligne de chaque paragraphe est composée en drapeau et porte des espaces ordinaires, voilà pourquoi les faux positifs couvrent en général le corps d'un paragraphe et s'arrêtent une ligne avant sa fin

Un moyen rapide de contrôler votre propre corpus est de faire tourner le détecteur sur des documents que vous savez être uniquement de la prose, tels que des lettres ou des communiqués de presse, et d'afficher chaque table en mode espaces blancs qu'il rapporte. La sortie attendue sur ceux-ci est rien

uses
  SysUtils, PDFium;

// Liste chaque table alignée par espaces blancs du document chargé pour que
// les pages que vous savez ne contenir que de la prose puissent être vérifiées vite
procedure ReportWhitespaceTables(Pdf: TPdf; MinRows: Integer = 2);
var
  Options: TPdfTableExtractionOptions;
  Tables: TPdfTables;
  I: Integer;
begin
  Options := TPdfTableExtractionOptions.Default;  // MinColumnGap 12, AlignmentTolerance 3
  Options.MinRows := MinRows;
  Tables := Pdf.ExtractDocumentTables(Options);   // restaure la page active
  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;

Ce que coûte chaque seuil

Chaque seuil au niveau des lignes échange une classe de documents contre une autre, et c'est la raison de ne pas y toucher pour ce problème. Monter MinColumnGap à 20 points fait tomber les colonnes compactes des états financiers denses, où la gouttière entre une colonne d'étiquettes et ses valeurs est souvent à peine plus large que le défaut. Monter MinRows à 3 jette les vraies tables de deux lignes et ne fait que baisser les chances pour les longs paragraphes, puisqu'une page de prose offre bien des chances que trois lignes s'alignent. Serrer AlignmentTolerance sous 3 points commence à scinder de vraies colonnes dont les bords gauches dérivent légèrement, comme cela arrive sur des pages scannées avec une couche texte OCR

MinConfidence ressemble au filtre naturel et est le plus faible des quatre. Une table par espaces blancs dans PDFium Component marque 0,58 plus 0,30 fois la part de cellules non vides, plafonné à 0,88, si bien que le score mesure le remplissage de la grille. Un fragment de paragraphe remplit chaque cellule, ce qui fait qu'un faux positif de prose marque près du haut de la plage tandis qu'une vraie table avec des cellules vides marque plus bas

Deux lignes de prose justifiée et deux rangées d'une table à deux colonnes peuvent produire des groupes de mots identiques aux mêmes ancres. La preuve qui les sépare se trouve entre les lignes

Une vraie frontière de colonne est un corridor vertical

Une vraie frontière de colonne est une bande verticale de la page qui reste libre de texte sur chaque ligne qu'elle sépare. Une table en a une entre chaque paire de colonnes par construction, parce que ses cellules ont été posées contre des positions X partagées. Un paragraphe justifié étire ses espaces à une position horizontale différente à chaque ligne, si bien qu'aucune bande ne survit plus d'une ligne ou deux. PDFium Component teste exactement cela après que les groupes de mots d'une candidate ont été affectés aux colonnes d'ancres. Pour chaque paire de colonnes adjacentes, chaque ligne avec du contenu dans les deux cellules apporte l'intervalle allant du bord le plus à droite des mots de la cellule de gauche au bord le plus à gauche des mots de la cellule de droite ; les intervalles sont intersectés à travers les lignes, et toute la candidate est rejetée quand l'intersection est plus étroite que la moitié de MinColumnGap — 6 points au défaut

Deux détails comptent sur les vraies tables mal commodes. Les lignes où l'une des cellules est vide ne votent pas, si bien qu'une table avec des cellules vides, ou une ligne d'en-tête qui couvre moins de colonnes que le corps, passe quand même. Et la largeur de corridor se dérive de MinColumnGap au lieu d'être une option séparée, parce que les deux valeurs décrivent la même chose physique : l'espace qu'un designer laisse entre les colonnes. La moitié laisse de la place pour la ligne où une longue entrée de la colonne de gauche approche la suivante

Le contrôle est assez petit pour être reproduit dans votre propre code de mise en page ; les listes de cellules ci-dessous sont votre propre structure, un tableau d'indices de mots par cellule en ordre ligne-majeur

uses
  Math, PDFium;

type
  TIndexList = array of Integer;
  TCellIndexes = array of TIndexList;   // votre propre structure : Row * ColumnCount + Column

// Renvoie False quand une paire de colonnes adjacentes manque d'un corridor
// vertical sans texte d'au moins MinColumnGap / 2 sur les rangées qui l'utilisent
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;                             // les cellules vides ne votent pas
      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;

Garder les tables à filets hors de la passe par espaces blancs

Une table à filets serait trouvée deux fois si la passe par espaces blancs voyait chaque mot de la page, parce qu'une table à filets propre est par construction aussi une table par espaces blancs parfaitement alignée. À elle seule, une règle de chevauchement supérieur à la moitié laisserait une candidate qui combine les lignes basses d'une table à filets avec quelques lignes de texte alignées sous elle rester sous le ratio et ressortir comme une seconde table plus grande qui déborde sur sa voisine

Quand DetectRuledTables et DetectWhitespaceTables sont tous deux actifs, ce qui est le défaut, ExtractTables fait donc tourner la passe à filets en premier et retire chaque mot dont le point central se trouve à l'intérieur des bornes d'une table à filets avant que la passe par espaces blancs ne démarre. Le centre est employé au lieu du containment complet pour qu'un mot qui chevauche un filet d'une fraction de point suive la table à laquelle il appartient visuellement. La stratégie par espaces blancs ne voit alors que les mots libres, et une petite table sans filets posée directement sous une grille à filets est jugée sur ses propres lignes

Pourquoi « Purpose of Request: » peut-il ressortir en « of Purpose Request: » ?

Les mots d'une cellule ressortent dans le mauvais ordre quand le code qui décide de « même ligne » compare les centres verticaux, parce que des boîtes de mots construites depuis des boîtes de glyphes ne partagent pas un centre même quand elles partagent une ligne de base. FPDFText_GetCharBox renvoie la boîte stricte de l'encre de chaque glyphe en espace page, pas une boîte rembourrée jusqu'à l'ascendente et la descendante de la police, et une boîte de mot est l'union des boîtes de ses caractères. Dans une étiquette de formulaire telle que « Purpose of Request: », les mots « Purpose » et « Request: » portent des descendantes et « of » n'en porte pas, si bien que la boîte de « of » est plus courte et son centre se situe quelques points plus haut. Une routine qui trie par Y du centre avec une tolérance de même ligne d'un point puis par bord gauche met « of » sur sa propre ligne au-dessus des deux autres et l'émet en premier

Le PDF n'offre aucun raccourci. ISO 32000-1 §9.4.4 place les glyphes par déplacement le long de la ligne de base, et les seules métriques verticales du fichier sont par police : Ascent, Descent et FontBBox dans le descripteur de police (§9.8.1). Rien ne dit que deux glyphes partagent une ligne. Les boîtes strictes qui font que la surbrillance de sélection a l'air juste, traitées dans la sélection de lignes de texte avec les char boxes de PDFium, sont une mauvaise entrée pour une comparaison de distance de centres

PDFium Component construit le texte des cellules par chevauchement à la place. Un mot rejoint une ligne visuelle quand son chevauchement vertical avec les bornes courantes de la ligne vaut au moins 25 pour cent de la plus petite des deux hauteurs, ou quand les deux centres sont à un point l'un de l'autre ; chaque ligne est ensuite triée par bord gauche, et les lignes sont jointes par une paire CR LF. « Purpose » et « of » se chevauchent sur toute la hauteur d'x, bien plus qu'un quart de la boîte la plus courte, si bien qu'ils atterrissent sur une ligne et se lisent dans l'ordre

Regrouper les lignes de texte par chevauchement dans votre propre code

Le même piège attend tout code de mise en page PDF qui décide de « même ligne » en comparant des centres contre une tolérance fixe. Les descendantes sont le déclencheur le plus doux. Des étiquettes en gras à côté de valeurs plus petites, des appels de note en exposant et des boîtes OCR bruitées déplacent tous les centres de plus que toute tolérance qui sépare encore des lignes adjacentes de texte de 10 points sur un interlignage de 12 points. Le ratio de chevauchement se moque de la taille : deux boîtes sur une même ligne de base se chevauchent sur leur hauteur d'x partagée, et deux boîtes sur des lignes adjacentes ne se chevauchent de rien

TPdf.PageWordBoxes renvoie chaque mot de la page active avec son rectangle en espace page dans Rect, si bien que regrouper une page en lignes visuelles demande un prédicat et une courte boucle

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>;   // union courante par ligne
  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;
  // trier chaque ligne par Rect.Left avant de la lire ; PageWordBoxes renvoie
  // les mots dans l'ordre du flux de contenu, qui n'est pas forcément visuel
end;

Le prédicat est la partie qui vaut d'être copiée. Pour quoi que ce soit au-delà d'un dump rapide, partez du modèle de texte structuré, qui porte déjà des blocs, des lignes et une source d'ordre de lecture, comme décrit dans l'extraction de texte PDF structuré avec ordre de lecture

Ce que les appelants de tables contrôlent encore

Les appelants de tables obtiennent le test de corridor, le filtre mots filets-d'abord et le texte de cellules par chevauchement sans toucher à leurs options. Le seuil de corridor est fixé à la moitié de MinColumnGap, si bien que l'unique valeur que vous réglez pour la largeur de gouttière gouverne les deux. La stratégie par espaces blancs garde un plancher de deux lignes même quand MinRows vaut 1 ; seule la stratégie à filets accepte les grilles d'une ligne, que ExtractDocumentTables emploie pour des fragments de table poursuivis en haut d'une page. Le même enregistrement d'options voyage dans TPdfReflowOptions.TableOptions, si bien que la sortie de reflow hérite des mêmes décisions quand DetectTables est actif

Le test de corridor se décide sur les lignes qui ont du contenu des deux côtés d'une frontière, si bien qu'une candidate de deux lignes est jugée sur seulement deux telles lignes. Pour des archives qui sont surtout de la prose et contiennent rarement de vraies tables de deux lignes — contrats, correspondances, essais — mettez MinRows à 3 et acceptez les tables de deux lignes perdues. Pour des documents financiers et à forte teneur de formulaires gardez le défaut de 2, parce que les courtes vraies tables y sont courantes. Un texte au fer à gauche garde des espaces simples ordinaires et produit rarement un écart approchant 12 points

Le PDF n'a pas d'objet table général. ISO 32000-1 §14.8.4.3.4 définit un élément de structure Table, mais seul le PDF balisé le porte, si bien que pour tout le reste la grille est une inférence depuis la géométrie, et le Confidence d'une table par espaces blancs ne dépasse jamais 0,88

Les options de détection, la sérialisation TPdfTable.ToCsv et ToJson, et la démo TableExtractionLab pour Delphi, C++Builder et Lazarus sont couvertes sur la page produit de PDFium Component for Delphi