Ложные таблицы в PDF из-за выключенного текста в Delphi

PDFium Component версии 3.117.0 перестаёт выдавать выключенные по формату абзацы за таблицы, выровненные по пробелам: теперь каждая граница столбца обязана быть вертикальным коридором без текста на всех строках, которые она разделяет; слова, уже занятые сеткой по линейкам, пропускаются; а текст ячейки собирается по вертикальному перекрытию, а не по расстоянию между центрами глифовых боксов. Все три изменения живут внутри ExtractTables и ExtractDocumentTables и не требуют никаких опций

Отчёт, с которого всё началось, был прозаичен. Страница пресс-релиза, на которой нет никакой таблицы, возвращалась из ExtractTables с таблицей 5x4 по пробелам, уверенность комфортно выше MinConfidence по умолчанию в 0.5, а в ячейках лежали обрывки обычного основного текста. Форма приёма сделала то же самое со своими абзацами-эссе и выдала 3x4 и 5x3. Оба документа были выключены по формату. Очевидная реакция — крутить пороги, и полезный урок этого релиза в том, что кручение тут не поможет, потому что правило, которое крутят, задавало неверный вопрос

uses
  PDFium;

// Регрессионная проверка: перечислить все таблицы по пробелам в документе, чтобы страницу,
// о которой известно, что на ней только проза, можно подтвердить как чистую
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;

Почему выключенный по формату текст выглядит как таблица?

Выключенный по формату абзац выглядит как таблица потому, что выключенная строка — это ряд слов, разделённых промежутками, которые растянул движок вёрстки, и как только растянутый промежуток достигает MinColumnGap, у детектора нет способа отличить его от разделителя столбцов, оставаясь в пределах строки. Стратегия по пробелам в PDFium Component группирует рамки слов в визуальные строки, расщепляет каждую строку на группы слов всюду, где горизонтальное расстояние до предыдущего слова не меньше MinColumnGap (12 пунктов по умолчанию), и принимает таблицу, когда хотя бы две подряд идущие строки повторяют как минимум MinColumns левых якорей групп в пределах AlignmentTolerance, то есть 3 пунктов. Это правило, описанное в обзоре обнаружения таблиц, и для настоящей выровненной таблицы оно абсолютно верно

А теперь примените его к двадцати строкам выключенной прозы кеглем 10 пунктов. Каждая строка растянута до одного и того же правого поля, поэтому строка, заканчивающаяся длинным словом, распирает свои внутренние пробелы, и в абзаце с несколькими короткими строками часть этих пробелов переваливает за 12 пунктов. Двум подряд идущим строкам нужно всего по одному растянутому промежутку, попавшему в пределах 3 пунктов к той же позиции X, чтобы образовать кандидата на две строки и два столбца. На достаточном числе строк это уже не невезение, а вероятность, стремящаяся к единице, и 5x4 в пресс-релизе была просто тем случаем, когда четыре таких промежутка выстроились на пяти строках

Каждый порог обменивает один класс документов на другой. Подъём MinColumnGap до 20 пунктов теряет компактные столбцы плотных финансовых отчётов — ровно тот случай, ради которого значение по умолчанию и опускали. Подъём MinRows до 3 выбрасывает настоящие таблицы из двух строк и лишь понижает шансы для длинных абзацев. Затягивание AlignmentTolerance ниже 3 пунктов ломает рамки слов, полученные из OCR, чьи левые края дрожат сильнее этого. Сигнал уровня строки по-настоящему двусмыслен, так что фикс обязан прийти от сигнала, которого у строки самой по себе нет

Что делает границу столбца настоящей?

Настоящая граница столбца — это вертикальная полоса страницы, остающаяся пустой на всех строках, которые она разделяет. У таблицы такая есть между каждой парой столбцов по построению, потому что ячейки раскладывались по общим позициям X. Выключенный по формату абзац растягивает пробелы между словами в разных горизонтальных позициях на каждой строке, так что никакая полоса не переживает пересечение больше одной-двух строк. PDFium Component теперь проверяет ровно это: после того как группы слов кандидата назначены якорным столбцам, для каждой пары соседних столбцов он берёт на каждой строке, где содержимое есть в обеих ячейках, интервал от самого правого края слов левой ячейки до самого левого края слов правой ячейки, пересекает эти интервалы по строкам и отвергает всего кандидата, если пересечение уже, чем MinColumnGap, умноженный на 0.5, то есть 6 пунктов при значении по умолчанию

Две детали важны. Строки, где пуста хотя бы одна из ячеек, не голосуют, так что таблица с пустой ячейкой или заголовок, охватывающий меньше столбцов, чем тело, всё равно проходят. А ширина коридора выводится из MinColumnGap, а не выставляется отдельной опцией, потому что эти двое описывают одну физическую вещь: зазор, который дизайнер оставляет между столбцами. Логика достаточно мала, чтобы воспроизвести её, если вы строите на голых рамках слов, а не на API таблиц, и пример ниже повторяет проверку внутри компонента:

uses
  Math, PDFium;

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

// Возвращает False, когда любой паре соседних столбцов не хватает свободного
// от текста вертикального коридора шириной хотя бы 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;                             // пустые ячейки не голосуют
      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;

Почему таблицы по линейкам извлекались дважды?

Таблицы по линейкам извлекались дважды потому, что проход по пробелам видел каждое слово на странице, включая слова, которые проход по линейкам уже расставил в сетку, а чистая таблица по линейкам по построению является ещё и идеально выровненной таблицей по пробелам. Проверка перекрытия уже отвергала кандидата по пробелам, чьи границы покрывали больше половины существующей таблицы, но кандидат, соединивший нижние строки таблицы с несколькими выровненными строками текста под ней, мог не дотянуть до этой доли и выжить как вторая, чуть более крупная таблица, залезающая на соседа. Теперь ExtractTables удаляет эти слова до запуска прохода по пробелам. Слово отбрасывается, когда его центральная точка лежит внутри границ любой таблицы, которую произвёл проход по линейкам; берётся именно центр, а не полное вхождение, чтобы слово, перевалившее за рамку на доли пункта, последовало за таблицей, к которой визуально принадлежит. После этого стратегия по пробелам работает только со свободными словами, а значит маленькая таблица без линеек прямо под таблицей с линейками обнаруживается сама по себе, а не сращивается с сеткой над ней

Почему «Purpose of Request:» выходило как «of Purpose Request:»?

Слова выходили переставленными потому, что рамки слов, которые строит PDFium Component, — это объединения ограничивающих боксов глифов, а у «of» нет нижнего выносного элемента, тогда как у «Purpose» и «Request:» он есть. FPDFText_GetCharBox возвращает плотный бокс чернил глифа в пространстве страницы, а не бокс, добитый до ascent и descent шрифта, и рамка слова — это объединение боксов его символов. Поэтому слово без нижних выносных элементов короче, и его вертикальный центр сидит выше — на 2–3 пункта в той самой форме. Старая процедура текста ячейки сортировала слова сначала по центру Y с допуском в 1 пункт на «ту же строку», а затем по левому краю; «of» выходило за пределы допуска, сортировалось как отдельная строка над остальными и выдавалось первым

Это не столько причуда PDFium, сколько следствие того, как PDF размещает текст. ISO 32000-1 §9.2.2 и §9.4.4 определяют размещение глифа как горизонтальное смещение вдоль базовой линии в пространстве текста, а единственные вертикальные метрики, которые несёт файл, заданы по шрифту: записи Ascent, Descent и FontBBox дескриптора шрифта из §9.8.1. Ничто в файле не говорит, что два глифа делят строку; это приходится выводить из геометрии, а плотные боксы глифов, из-за которых подсветка выделения выглядит правильно, как описано в материале про выделение строк текста по char-боксам PDFium, — неверный вход для сравнения по расстоянию между центрами

Фикс в версии 3.117.0 меняет вопрос с «насколько далеко разнесены центры» на «насколько сильно боксы перекрываются по вертикали». Текст ячейки собирается так: сначала слова ячейки группируются в визуальные строки, причём слово присоединяется к строке, когда его вертикальное перекрытие с текущими границами строки составляет не меньше 25 процентов от меньшей из двух высот; затем каждая строка сортируется вставками по левому краю; затем строки соединяются переводом строки. «Purpose» и «of» перекрываются по всей высоте строчных, что куда больше 25 процентов от более короткого бокса, так что они попадают в одну строку и сортируются по X, как и задумано

Группируйте строки текста по перекрытию, а не по расстоянию между центрами

Правило, которое стоит вынести из этого бага, общее: любой код раскладки текста в PDF, решающий «та же строка» сравнением вертикальных центров с фиксированным допуском, сломается на настоящих шрифтах, и отказ будет тихим: ничего не возбуждается, слова просто выходят в неверном порядке. Разные нижние выносные элементы — самый мягкий триггер. Жирная метка кеглем 12 рядом со значениями кегля 10, надстрочный маркер сноски, символ валюты, нарисованный запасным шрифтом, и рамки слов из OCR с пошумной разницей высот — всё это сдвигает центры сильнее, чем любой допуск, который ещё разделяет соседние строки текста кегля 10 при интерлиньяже 12. Доля перекрытия инвариантна к размеру: два бокса на одной базовой линии перекрываются по общей высоте строчных независимо от того, что делают их верхние и нижние выносные элементы, а два бокса на соседних строках не перекрываются ничем

То же правило легко применить и вне извлечения таблиц. TPdf.PageWordBoxes возвращает каждое слово активной страницы с его прямоугольником в пространстве страницы, так что группировка страницы в визуальные строки — короткий цикл:

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>;   // текущее объединение по строке
  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;
  // перед чтением сортируйте каждую строку по Rect.Left; PageWordBoxes возвращает
  // слова в порядке потока содержимого, который не обязан быть визуальным
end;

Что меняется для существующих вызывающих и где границы

Смысл этого фрагмента — в предикате, а не в цикле; для всего, что серьёзнее быстрого дампа, начинайте со структурной модели текста, которая уже несёт блоки, строки и источник порядка чтения, как рассказано в материале про структурированное извлечение текста PDF с порядком чтения. Существующие вызывающие извлечения таблиц получают все три исправления, не трогая своих опций. Порог коридора зафиксирован на половине MinColumnGap, стратегия по пробелам сохраняет свой порог в две строки даже когда MinRows выставлен в 1 (что теперь принимает стратегия по линейкам), а фильтрация слов, уже занятых линейками, работает безусловно, когда включены обе стратегии. На наборе из 13 документов, использованном для релиза, проход по пробелам раньше возвращал 34 фрагмента и ложных срабатывания рядом с 9 таблицами по линейкам; после релиза он не возвращает ничего, а число таблиц по линейкам выросло до 41, хотя большая часть этого роста приходится на тот же релиз, научивший детектор линеек читать рамки, нарисованные залитыми прямоугольниками, — а это отдельная история

Честные границы: проверке коридора нужна хотя бы одна строка с содержимым по обе стороны границы, чтобы что-то отвергнуть, так что кандидат из двух строк, чьи два растянутых промежутка случайно попали в пределах 6 пунктов друг от друга, всё равно пройдёт. Это узкое совпадение, а не почти неизбежность, как было раньше, но документы, переполненные прозой без настоящих таблиц из двух строк, могут закрыть и это, выставив MinRows в 3. Текст с рваным левым краем проблемой никогда не был и не затронут. И в PDF по-прежнему нет объекта таблицы; ISO 32000-1 §14.8.4.3 определяет структурный элемент Table, но его несёт только Tagged PDF, так что для всего остального сетка остаётся выводом из геометрии, и значение уверенности на каждой TPdfTable существует потому, что вывод заслуживает оценки

Извлечение таблиц, структурированный текст и рамки слов читают из одной и той же модели страницы в Delphi, C++Builder и Lazarus; полный API, включая TPdfTableExtractionOptions и демо TableExtractionLab, поставляемое вместе с ним, описан на странице PDFium Component для Delphi