Falsos positivos de tabela em texto justificado no Delphi

Uma página de texto corrido justificado pode voltar de um detector de tabelas por whitespace como uma grade de várias colunas, cada célula guardando meia frase cortada e o score de confiança bem acima de qualquer threshold que você pensaria em definir. Não há tabela nessa página. O detector encontrou espaços entre palavras largos o bastante para passar por separadores de coluna e umas quantas linhas consecutivas em que esses espaços caíram quase no mesmo X, e só pelo alinhamento isso é exatamente o que uma tabela parece. A resposta é parar de julgar um limite de coluna uma linha por vez e perguntar se uma faixa de papel em branco desce a página entre as colunas

Por que texto justificado passa num teste de tabela por whitespace?

Texto justificado passa porque uma linha justificada é uma fila de palavras separadas por espaços que o motor de layout esticou, e quando um espaço esticado cruza o threshold de coluna, nada naquela única linha o distingue de um canalete. A estratégia de whitespace no PDFium Component funciona como a maioria dos detectores de whitespace. TPdf.ExtractTables agrupa boxes de palavras em linhas visuais, divide cada linha onde quer que a distância horizontal de uma palavra à próxima seja de ao menos MinColumnGap (12 pontos em TPdfTableExtractionOptions.Default), e agrupa as bordas esquerdas dos grupos de palavras resultantes em âncoras de coluna dentro de AlignmentTolerance, que tem padrão 3 pontos. Uma âncora sobrevive só se se repete em ao menos MinRows linhas, e toda linha da candidata precisa acertar ao menos MinColumns âncoras distintas. Para uma tabela alinhada genuína essa regra está correta, e é a regra descrita em o overview de detecção e extração de tabelas

A aritmética do lado da prosa é menos generosa do que parece. Suponha uma linha de 10 pontos numa coluna de newsletter de 180 pontos que termina 30 pontos antes da margem direita porque a próxima palavra não caberia, e a linha tem só três espaços entre palavras porque as palavras são compridas. Um motor de justificação distribui esses 30 pontos pelos três espaços, então cada um cresce de cerca de 2,5 pontos para 12,5 pontos e cruza o MinColumnGap padrão. Uma segunda linha só precisa de um espaço esticado cuja palavra seguinte comece a até 3 pontos da da primeira linha, e o detector tem uma candidata de duas linhas por duas colunas

Como o esticamento é codificado não importa. A ISO 32000-1 §9.3.3 aplica word spacing (Tw) só ao código de caractere de byte único 32, então produtores que usam fontes multibyte em geral posicionam palavras com ajustes numéricos num array TJ (§9.4.3); de qualquer jeito os boxes de palavra saem idênticos. A última linha de cada parágrafo é composta ragged e carrega espaços comuns, e é por isso que falsos positivos tendem a cobrir o corpo de um parágrafo e parar uma linha antes do fim dele

Um jeito rápido de conferir o seu corpus é rodar o detector sobre documentos que você sabe serem só prosa, como cartas ou comunicados de imprensa, e imprimir toda tabela em modo whitespace que ele reportar. A saída esperada nesses é nada

uses
  SysUtils, PDFium;

// Lista toda tabela alinhada por whitespace no documento carregado para que
// páginas que você sabe conterem só prosa possam ser checadas rápido
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);   // restaura a página ativa
  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;

O que cada threshold custa

Todo threshold no nível de linha troca uma classe de documento por outra, e essa é a razão para deixá-los em paz neste problema. Subir MinColumnGap para 20 pontos derruba as colunas compactas de demonstrações financeiras densas, em que o canalete entre uma coluna de rótulos e os valores dela costuma ser mal mais largo que o padrão. Subir MinRows para 3 descarta tabelas genuínas de duas linhas e só diminui as chances para parágrafos longos, já que uma página de prosa oferece muitas chances de três linhas se alinharem. Apertar AlignmentTolerance para abaixo de 3 pontos começa a rachar colunas reais cujas bordas esquerdas derivam um pouco, como acontece em páginas escaneadas com uma camada de texto OCR

MinConfidence parece o filtro natural e é o mais fraco dos quatro. Uma tabela por whitespace no PDFium Component pontua 0,58 mais 0,30 vezes a fatia de células não vazias, com teto de 0,88, então o score mede quão cheia a grade está. Um fragmento de parágrafo enche toda célula, o que significa que um falso positivo de prosa pontua perto do topo da faixa enquanto uma tabela real com células em branco pontua mais baixo

Duas linhas de prosa justificada e duas linhas de uma tabela de duas colunas podem produzir grupos de palavras idênticos nas mesmas âncoras. A evidência que os separa fica entre as linhas

Um limite de coluna real é um corredor vertical

Um limite de coluna real é uma faixa vertical da página que fica livre de texto em toda linha que ele separa. Uma tabela tem um entre cada par de colunas por construção, porque as células dela foram dispostas contra posições X compartilhadas. Um parágrafo justificado estica os espaços dele numa posição horizontal diferente a cada linha, então nenhuma faixa sobrevive mais que uma ou duas linhas. O PDFium Component testa exatamente isto depois que os grupos de palavras de uma candidata são atribuídos às colunas de âncora. Para cada par de colunas adjacentes, toda linha com conteúdo nas duas células contribui com o intervalo da borda mais à direita das palavras da célula da esquerda até a borda mais à esquerda das palavras da célula da direita; os intervalos são intersectados entre as linhas, e a candidata inteira é rejeitada quando a interseção é mais estreita que metade de MinColumnGap — 6 pontos no padrão

Dois detalhes importam em tabelas reais espinhosas. Linhas em que qualquer célula está vazia não votam, então uma tabela com células em branco, ou uma linha de cabeçalho que cobre menos colunas que o corpo, ainda passa. E a largura do corredor é derivada de MinColumnGap em vez de ser uma opção separada, porque os dois valores descrevem a mesma coisa física: o espaço que um designer deixa entre colunas. Reduzi-lo à metade deixa espaço para a linha em que uma entrada comprida na coluna da esquerda corre perto da próxima

A conferência é pequena o bastante para reproduzir no seu próprio código de layout; as listas de células abaixo são a sua estrutura, um array de índices de palavra por célula em ordem linha-por-coluna

uses
  Math, PDFium;

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

// Devolve False quando um par de colunas adjacentes não tem um corredor
// vertical livre de texto de ao menos MinColumnGap / 2 nas linhas que o usam
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;                             // células vazias não votam
      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;

Mantendo tabelas com linhas fora da passada de whitespace

Uma tabela com linhas de grade seria achada duas vezes se a passada de whitespace visse toda palavra da página, porque uma tabela com linhas de grade limpa é, por construção, também uma tabela por whitespace perfeitamente alinhada. Por si só, uma regra de sobreposição maior que metade deixaria uma candidata que combina as linhas de baixo de uma tabela com grade e umas quantas linhas de texto alinhado sob ela ficar sob a razão e sair como uma segunda tabela maior que sangra na vizinha

Quando DetectRuledTables e DetectWhitespaceTables estão ambos ligados, que é o padrão, ExtractTables portanto roda a passada com linhas de grade primeiro e remove toda palavra cujo ponto central está dentro dos limites de uma tabela com linhas de grade antes de a passada de whitespace começar. O centro é usado em vez de contenção total para que uma palavra que cavalga uma borda por uma fração de ponto siga a tabela a que visualmente pertence. A estratégia de whitespace então só vê palavras livres, e uma tabela pequena sem grade parada diretamente sob uma grade com linhas é julgada pelas linhas dela próprias

Por que "Purpose of Request:" pode sair como "of Purpose Request:"?

Palavras dentro de uma célula saem na ordem errada quando o código que decide "mesma linha" compara centros verticais, porque boxes de palavras construídos a partir de boxes de glifos não dividem um centro mesmo quando dividem uma baseline. FPDFText_GetCharBox devolve o box apertado da tinta de cada glifo no espaço da página, não um box estendido até o ascent e o descent da fonte, e um box de palavra é a união dos boxes dos caracteres dele. Num rótulo de formulário como "Purpose of Request:", as palavras "Purpose" e "Request:" carregam descendentes e "of" não, então o box de "of" é mais curto e o centro dele fica uns dois pontos mais alto. Uma rotina que ordena pelo Y do centro com tolerância de mesma linha de 1 ponto e depois pela borda esquerda põe "of" numa linha própria acima das outras duas e o emite primeiro

O PDF não oferece atalho. A ISO 32000-1 §9.4.4 posiciona glifos por deslocamento ao longo da baseline, e as únicas métricas verticais no arquivo são por fonte: Ascent, Descent e FontBBox no descritor de fonte (§9.8.1). Nada diz que dois glifos dividem uma linha. Os boxes apertados que fazem o destaque de seleção parecer certo, como coberto em seleção de linhas de texto com char boxes do PDFium, são entrada ruim para uma comparação de distância de centros

O PDFium Component constrói o texto de célula por sobreposição em vez disso. Uma palavra entra numa linha visual quando a sobreposição vertical dela com os limites correntes da linha é de ao menos 25 por cento do menor das duas alturas, ou quando os dois centros estão a um ponto um do outro; cada linha é então ordenada pela borda esquerda, e as linhas são unidas com um par CR LF. "Purpose" e "of" se sobrepõem pelo x-height inteiro, muito mais que um quarto do box menor, então caem numa linha e leem em ordem

Agrupe linhas de texto por sobreposição no seu próprio código

A mesma armadilha espera em qualquer código de layout de PDF que decide "mesma linha" comparando centros contra uma tolerância fixa. Descendentes são o gatilho mais leve. Rótulos em negrito ao lado de valores menores, marcadores de nota de rodapé em sobrescrito e boxes de OCR barulhentos movem centros por mais que qualquer tolerância que ainda separe linhas adjacentes de texto de 10 pontos em entrelinha de 12 pontos. A razão de sobreposição não se importa com tamanho: dois boxes numa mesma baseline se sobrepõem pelo x-height compartilhado, e dois boxes em linhas adjacentes não se sobrepõem em nada

TPdf.PageWordBoxes devolve toda palavra da página ativa com o retângulo dela no espaço da página em Rect, então agrupar uma página em linhas visuais leva um predicado e um loop curto

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>;   // união corrente por linha
  I, J, Found: Integer;
begin
  Words := Pdf.PageWordBoxes;            // precisa de página ativa (Pdf.PageNumber)
  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;
  // ordene cada linha por Rect.Left antes de lê-la: PageWordBoxes devolve
  // palavras em ordem de content stream, que não precisa casar com a ordem visual
end;

O predicado é a parte que vale copiar. Para qualquer coisa além de um dump rápido, parta do modelo de texto estruturado, que já carrega blocos, linhas e uma fonte de ordem de leitura, como descrito em extração de texto PDF estruturado com ordem de leitura

O que quem chama tabelas ainda controla

Quem chama extração de tabelas ganha o teste de corredor, o filtro de palavras com linhas de grade primeiro e o texto de célula por sobreposição sem tocar nas opções. O threshold do corredor é fixado em metade de MinColumnGap, então o único valor que você ajusta para largura de canalete governa ambos. A estratégia de whitespace mantém um piso de duas linhas mesmo quando MinRows é definido como 1; só a estratégia com linhas de grade aceita grades de linha única, que ExtractDocumentTables usa para fragmentos de tabela continuados no topo de uma página. O mesmo record de opções viaja para TPdfReflowOptions.TableOptions, então a saída de reflow herda as mesmas decisões quando DetectTables está ligado

O teste de corredor decide sobre linhas que têm conteúdo nos dois lados de um limite, então uma candidata de duas linhas é julgada em só duas dessas linhas. Para arquivos que são maiormente prosa e raramente contêm tabelas genuínas de duas linhas — contratos, correspondência, ensaios — defina MinRows como 3 e aceite as tabelas de duas linhas perdidas. Para documentos financeiros e cheios de formulários mantenha o padrão de 2, porque tabelas reais curtas são comuns ali. Texto alinhado à esquerda mantém espaços únicos comuns e raramente produz um espaço perto de 12 pontos

O PDF não tem um objeto de tabela geral. A ISO 32000-1 §14.8.4.3.4 define um elemento de estrutura Table, mas só PDF Tagged o carrega, então para todo o resto a grade é uma inferência da geometria, e o Confidence de uma tabela por whitespace nunca passa de 0,88

As opções de detecção, a serialização TPdfTable.ToCsv e ToJson, e a demo TableExtractionLab para Delphi, C++Builder e Lazarus estão cobertas na página de produto do PDFium Component for Delphi