Коридор без тексту: хибні таблиці за пробілами в PDFium

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. Ніщо у файлі не каже, що два глифи на одному рядку; це треба виводити з геометрії, і щільні глифові прямокутники, які роблять підсвічування виділення правильним, як описано в статті про виділення рядків тексту через прямокутники символів PDFium, — це хибний вхід для порівняння відстані між центрами

Виправлення у версії 3.117.0 міняє питання з «наскільки далеко центри» на «наскільки прямокутники перекриваються вертикально». Текст клітинки збирається так: спершу слова клітинки групуються у візуальні рядки, де слово приєднується до рядка, коли його вертикальне перекриття з поточними межами рядка становить щонайменше 25 відсотків від меншої з двох висот, потім кожен рядок сортується вставкою за лівим краєм, потім рядки з'єднуються розривом рядка. «Purpose» і «of» перекриваються на всю висоту x-height, що куди більше за 25 відсотків від коротшого прямокутника, тож вони потрапляють на той самий рядок і сортуються за X, як і задумано

Групуйте рядки тексту за перекриттям, а не за відстанню між центрами

Правило, яке варто винести з цього бага, загальне: будь-який код верстки тексту в PDF, що вирішує «той самий рядок» порівнянням вертикальних центрів із фіксованим допуском, зламається на справжніх шрифтах, і збій буде тихим: ніщо не дає помилки, слова просто виходять у неправильному порядку. Найм'якший тригер — змішані виносні елементи. Жирний напис кеглем 12 пунктів поряд зі значеннями кеглем 10, позначка виноски у верхньому індексі, символ валюти, намальований fallback-шрифтом, і прямокутники слів з OCR із похибкою висоти на кожне слово — усе це зсуває центри більше, ніж будь-який допуск, який ще розділяє сусідні рядки тексту кеглем 10 пунктів при інтерліньяжі 12 пунктів. Коефіцієнт перекриття інваріантний до розміру: два прямокутники на одній базовій лінії перекриваються на спільній висоті x-height, хоч би що робили їхні виносні елементи, а два прямокутники на сусідніх рядках не перекриваються нічим

Те саме правило легко застосувати поза вилученням таблиць. 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 for Delphi