Corriger les faux positifs de table depuis du texte justifié

PDFium Component version 3.117.0 cesse de signaler les paragraphes justifiés comme des tables alignées par espaces blancs en exigeant que chaque frontière de colonne soit un corridor vertical sans texte sur chaque rangée qu'elle sépare, en sautant les mots déjà revendiqués par une grille réglée, et en assemblant le texte des cellules par chevauchement vertical plutôt que par distance entre centres de boîtes de glyphes. Les trois changements vivent à l'intérieur d'ExtractTables et d'ExtractDocumentTables et ne demandent aucune option

Le rapport qui a lancé tout cela n'avait rien de glamour. Une page de communiqué de presse sans aucune table revenait d'ExtractTables avec une table par espaces blancs 5x4, une confiance confortablement au-dessus du MinConfidence par défaut de 0,5, et les cellules contenaient des bouts de texte de corps ordinaire. Un formulaire d'admission faisait de même avec ses paragraphes de dissertation et produisait un 3x4 et un 5x3. Les deux documents étaient composés en justifié. La réaction évidente est d'ajuster les seuils, et la leçon utile de cette version est que l'ajustement ne peut pas corriger cela, parce que la règle qu'on ajustait posait la mauvaise question

uses
  PDFium;

// Vérification de non-régression : lister chaque table par espaces blancs d'un document
// pour confirmer qu'une page que vous savez purement textuelle est propre
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;

Pourquoi du texte justifié ressemble-t-il à une table ?

Un paragraphe justifié ressemble à une table parce qu'une ligne justifiée est une rangée de mots séparés par des blancs que le moteur de mise en page a étirés, et qu'une fois qu'un blanc étiré atteint MinColumnGap, le détecteur n'a aucun moyen local à la rangée de le distinguer d'un séparateur de colonne. La stratégie par espaces blancs de PDFium Component regroupe les boîtes de mots en rangées visuelles, découpe chaque rangée en groupes de mots partout où la distance horizontale au mot précédent atteint au moins MinColumnGap (12 points par défaut), et accepte une table quand au moins deux rangées consécutives répètent au moins MinColumns ancres de groupe alignées à gauche à AlignmentTolerance près, soit 3 points. C'est la règle décrite dans l'aperçu de la détection de tables, et pour une vraie table alignée elle est exactement juste

Appliquez-la maintenant à vingt lignes de prose justifiée en 10 points. Chaque ligne est étirée jusqu'à la même marge droite, donc une ligne qui se termine par un mot long ouvre ses espaces intérieurs, et dans un paragraphe comportant quelques lignes courtes certains de ces espaces franchissent 12 points. Deux lignes consécutives n'ont besoin que d'un blanc étiré chacune, tombant à 3 points près de la même position X, pour former un candidat de deux rangées et deux colonnes. Sur assez de lignes, ce n'est pas de la malchance ; c'est une probabilité qui tend vers la certitude, et le 5x4 du communiqué était simplement la série où quatre de ces blancs se sont alignés sur cinq lignes

Chaque seuil échange une classe de documents contre une autre. Monter MinColumnGap à 20 points fait perdre les colonnes compactes des rapports financiers denses, qui est exactement le cas pour lequel la valeur par défaut avait déjà été abaissée. Monter MinRows à 3 écarte de vraies tables à deux rangées et ne fait que réduire les probabilités pour les longs paragraphes. Resserrer AlignmentTolerance sous 3 points casse les boîtes de mots issues de l'OCR, dont les bords gauches tremblent de plus que cela. Le signal au niveau des rangées est réellement ambigu, donc le correctif doit venir d'un signal que les rangées ne portent pas d'elles-mêmes

Qu'est-ce qui rend une frontière de colonne réelle ?

Une vraie frontière de colonne est une bande verticale de la page qui reste vide sur chaque rangée qu'elle sépare. Une table en a une entre chaque paire de colonnes par construction, parce que les cellules ont été disposées contre des positions X partagées. Un paragraphe justifié étire ses espaces de mots à des positions horizontales différentes sur chaque ligne, donc aucune bande ne survit à l'intersection de plus d'une ou deux lignes. PDFium Component teste exactement cela désormais : après que les groupes de mots du candidat ont été affectés aux colonnes d'ancrage, pour chaque paire de colonnes adjacentes il prend, sur chaque rangée ayant du contenu dans les deux cellules, l'intervalle allant du bord droit des mots de la cellule gauche au bord gauche des mots de la cellule droite, intersecte ces intervalles sur toutes les rangées, et rejette tout le candidat si l'intersection est plus étroite que MinColumnGap fois 0,5, soit 6 points avec la valeur par défaut

Deux détails comptent. Les rangées où l'une des deux cellules est vide ne votent pas, donc une table avec une cellule vide, ou un en-tête qui couvre moins de colonnes que le corps, passe quand même. Et la largeur de corridor est dérivée de MinColumnGap plutôt qu'exposée comme option séparée, parce que les deux décrivent la même chose physique : le blanc qu'un concepteur laisse entre les colonnes. La logique est assez courte pour être reproduite si vous travaillez sur des boîtes de mots brutes plutôt que sur l'API de tables, et l'échantillon ci-dessous reflète la vérification à l'intérieur du composant :

uses
  Math, PDFium;

type
  TIndexList = array of Integer;
  TCellIndexes = array of TIndexList;   // 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;

Pourquoi les tables réglées étaient-elles extraites deux fois ?

Les tables réglées étaient extraites deux fois parce que la passe par espaces blancs voyait tous les mots de la page, y compris ceux que la passe réglée avait déjà placés dans une grille, et qu'une table réglée propre est par construction aussi une table par espaces blancs parfaitement alignée. Une vérification de chevauchement rejetait déjà un candidat par espaces blancs dont les limites couvraient plus de la moitié d'une table existante, mais un candidat qui combinait les rangées inférieures de la table avec quelques lignes de texte alignées en dessous pouvait tomber sous ce ratio et survivre comme seconde table légèrement plus grande débordant sur sa voisine. ExtractTables retire désormais ces mots avant que la passe par espaces blancs ne tourne. Un mot est écarté quand le centre de sa boîte se trouve à l'intérieur des limites d'une table produite par la passe réglée ; on utilise le centre plutôt que le confinement total pour qu'un mot à cheval sur une bordure d'une fraction de point suive la table à laquelle il appartient visuellement. La stratégie par espaces blancs ne travaille alors que sur les mots libres, ce qui signifie aussi qu'une petite table non réglée située juste sous une table réglée est détectée pour ses propres mérites au lieu d'être fusionnée avec la grille au-dessus

Pourquoi « Purpose of Request: » ressortait-il en « of Purpose Request: » ?

Les mots ressortaient réordonnés parce que les boîtes de mots que construit PDFium Component sont des unions de boîtes englobantes de glyphes, et que « of » n'a pas de descendante alors que « Purpose » et « Request: » en ont. FPDFText_GetCharBox renvoie la boîte serrée de l'encre du glyphe en espace de page, pas une boîte complétée jusqu'à l'ascendante et la descendante de la police, et la boîte du mot est l'union des boîtes de ses caractères. Un mot sans descendante est donc plus court et son centre vertical se situe plus haut, de 2 à 3 points sur le formulaire en question. L'ancienne routine de texte de cellule triait les mots par Y du centre d'abord, avec une tolérance de 1 point pour « même ligne », puis par bord gauche ; « of » passait la tolérance, se triait comme sa propre ligne au-dessus des autres, et était émis en premier

Ce n'est pas tant une bizarrerie de PDFium qu'une conséquence de la façon dont PDF positionne le texte. ISO 32000-1 §9.2.2 et §9.4.4 définissent le placement des glyphes comme un déplacement horizontal le long de la ligne de base en espace texte, et les seules métriques verticales que le fichier transporte sont par police : les entrées Ascent, Descent et FontBBox du descripteur de police en §9.8.1. Rien dans le fichier ne dit que deux glyphes partagent une ligne ; cela doit être inféré de la géométrie, et les boîtes de glyphes serrées qui font bien paraître la surbrillance de sélection, comme décrit dans la sélection de ligne de texte avec les boîtes de caractères PDFium, sont la mauvaise entrée pour une comparaison de distance entre centres

Le correctif de la version 3.117.0 change la question de « quelle distance sépare les centres » à « de combien les boîtes se chevauchent-elles verticalement ». Le texte des cellules est assemblé en regroupant d'abord les mots de la cellule en lignes visuelles, un mot rejoignant une ligne quand son chevauchement vertical avec les limites courantes de la ligne atteint au moins 25 pour cent de la plus petite des deux hauteurs, puis en triant par insertion chaque ligne par bord gauche, puis en joignant les lignes par un saut de ligne. « Purpose » et « of » se chevauchent sur toute la hauteur d'x, ce qui est bien plus que 25 pour cent de la boîte la plus courte, donc ils atterrissent sur la même ligne et se trient par X comme voulu

Grouper les lignes de texte par chevauchement, pas par distance entre centres

La règle à retenir de ce bug est générale : tout code de mise en page de texte PDF qui décide « même ligne » en comparant des centres verticaux à une tolérance fixe échouera sur de vraies polices, et l'échec est silencieux : rien ne lève d'erreur, les mots ressortent simplement dans le mauvais ordre. Des descendantes mélangées sont le déclencheur le plus bénin. Une étiquette en gras de 12 points à côté de valeurs de 10 points, un appel de note en exposant, un symbole monétaire dessiné depuis une police de repli et des boîtes de mots OCR avec du bruit de hauteur par mot déplacent tous les centres de plus que n'importe quelle tolérance qui sépare encore des lignes adjacentes de texte de 10 points à interligne de 12. Le ratio de chevauchement, lui, est invariant à la taille : deux boîtes sur une même ligne de base se chevauchent sur leur hauteur d'x partagée quoi que fassent leurs ascendantes et descendantes, et deux boîtes sur des lignes adjacentes ne se chevauchent pas du tout

La même règle est facile à appliquer en dehors de l'extraction de tables. TPdf.PageWordBoxes renvoie chaque mot de la page active avec son rectangle en espace de page, donc grouper une page en lignes visuelles tient en 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;

Ce qui change pour les appelants existants, et où sont les limites

L'intérêt de cet extrait est le prédicat, pas la boucle ; pour tout ce qui dépasse un vidage rapide, partez du modèle de texte structuré, qui porte déjà les blocs, les lignes et une source d'ordre de lecture, comme expliqué dans l'extraction de texte PDF structurée avec ordre de lecture. Les appelants existants de tables obtiennent les trois corrections sans toucher à leurs options. Le seuil de corridor est fixé à la moitié de MinColumnGap, la stratégie par espaces blancs garde son plancher de deux rangées même quand MinRows est mis à 1 (ce que la stratégie réglée accepte désormais), et le filtrage des mots déjà pris par les grilles réglées est inconditionnel dès que les deux stratégies sont activées. Sur le jeu de 13 documents utilisé pour la version, la passe par espaces blancs renvoyait auparavant 34 fragments et faux positifs à côté de 9 tables réglées ; après la version elle n'en renvoie aucun, et le compte des tables réglées est monté à 41, même si l'essentiel de cette hausse vient de la même version qui a appris au détecteur réglé à lire les bordures dessinées en rectangles remplis, ce qui est une autre histoire

Les limites honnêtes : le test de corridor a besoin d'au moins une rangée avec du contenu des deux côtés d'une frontière pour rejeter quoi que ce soit, donc un candidat de deux rangées dont les deux blancs étirés tombent par hasard à moins de 6 points l'un de l'autre passe encore. C'est une coïncidence étroite plutôt que la quasi-certitude d'avant, mais les documents riches en prose sans vraies tables à deux rangées peuvent la fermer en mettant MinRows à 3. Le texte en drapeau aligné à gauche n'a jamais été le problème et n'est pas affecté. Et PDF n'a toujours pas d'objet table ; ISO 32000-1 §14.8.4.3 définit un élément de structure Table, mais seul le PDF balisé le transporte, donc pour tout le reste la grille demeure une inférence à partir de la géométrie, et la valeur de confiance sur chaque TPdfTable est là parce qu'une inférence mérite un score

L'extraction de tables, le texte structuré et les boîtes de mots lisent tous le même modèle de page en Delphi, C++Builder et Lazarus ; l'API complète, y compris TPdfTableExtractionOptions et la démo TableExtractionLab livrée avec, est décrite sur la page PDFium Component pour Delphi