Atasi False Positive Tabel PDF dari Teks Justified di Delphi

PDFium Component versi 3.117.0 berhenti melaporkan paragraf justified sebagai tabel sejajar whitespace dengan menuntut setiap batas kolom berupa koridor vertikal tanpa teks di baris mana pun yang dipisahkannya, melewati kata yang sudah diklaim grid ruled, dan merakit teks sel berdasarkan overlap vertikal alih-alih jarak pusat glyph box. Ketiga perubahan itu ada di dalam ExtractTables dan ExtractDocumentTables dan tidak butuh opsi apa pun

Laporan yang memulai ini tidak glamor. Halaman siaran pers yang tidak punya tabel sama sekali kembali dari ExtractTables dengan tabel whitespace 5x4, confidence-nya nyaman di atas MinConfidence default 0.5, dan sel-selnya berisi potongan teks body biasa. Formulir pendaftaran melakukan hal yang sama dengan paragraf esainya dan menghasilkan satu 3x4 dan satu 5x3. Kedua dokumen diset justified. Tanggapan yang jelas adalah menyetel ulang ambangnya, dan pelajaran berguna dari rilis ini adalah penyetelan tidak bisa memperbaikinya, karena aturan yang sedang disetel mengajukan pertanyaan yang keliru

uses
  PDFium;

// Pemeriksaan regresi: daftar setiap tabel whitespace di dokumen supaya halaman
// yang Anda tahu hanya berisi prosa bisa dipastikan bersih
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;

Kenapa teks justified terlihat seperti tabel?

Paragraf justified terlihat seperti tabel karena baris justified adalah deretan kata yang dipisahkan celah yang diregangkan layout engine, dan begitu celah yang diregangkan mencapai MinColumnGap, detektornya tidak punya cara lokal-per-baris untuk membedakannya dari pemisah kolom. Strategi whitespace di PDFium Component mengelompokkan word box ke baris visual, memecah setiap baris menjadi grup kata di mana pun jarak horizontal ke kata sebelumnya setidaknya MinColumnGap (12 poin default-nya), dan menerima sebuah tabel ketika setidaknya dua baris berurutan mengulang setidaknya MinColumns anchor grup yang sejajar kiri dalam AlignmentTolerance, yaitu 3 poin. Itulah aturan yang dijelaskan di ikhtisar deteksi tabel, dan untuk tabel yang benar-benar sejajar aturan itu tepat sekali

Sekarang terapkan itu pada dua puluh baris prosa justified berukuran 10 poin. Setiap barisnya diregangkan ke margin kanan yang sama, jadi baris yang diakhiri kata panjang akan menarik spasi di dalamnya terbuka, dan di paragraf dengan beberapa baris pendek sebagian spasi itu melewati 12 poin. Dua baris berurutan hanya butuh satu celah teregang masing-masing, yang jatuh dalam 3 poin dari posisi X yang sama, untuk membentuk kandidat dua baris dua kolom. Lewat cukup banyak baris ini bukan lagi nasib buruk; ini probabilitas yang mendekati kepastian, dan 5x4 di siaran pers itu sekadar rentetan ketika empat celah seperti itu sejajar pada lima baris

Setiap ambang menukar satu kelas dokumen dengan kelas lainnya. Menaikkan MinColumnGap ke 20 poin menghilangkan kolom rapat di laporan keuangan yang padat, yang justru kasus yang membuat default-nya sudah diturunkan. Menaikkan MinRows ke 3 membuang tabel dua baris yang sungguhan dan cuma menurunkan peluangnya untuk paragraf panjang. Memperketat AlignmentTolerance di bawah 3 poin merusak word box hasil OCR, yang tepi kirinya bergetar lebih dari itu. Sinyal di level baris memang ambigu, jadi perbaikannya harus datang dari sinyal yang tidak dibawa barisnya sendiri

Apa yang membuat batas kolom itu nyata?

Batas kolom yang nyata adalah jalur vertikal di halaman yang tetap kosong di setiap baris yang dipisahkannya. Tabel punya satu di antara setiap pasangan kolomnya secara konstruksi, karena sel-selnya ditata terhadap posisi X yang dipakai bersama. Paragraf justified meregangkan spasi katanya di posisi horizontal yang berbeda di setiap baris, jadi tidak ada jalur yang bertahan melewati irisan lebih dari satu dua baris. PDFium Component kini menguji persis itu: setelah grup kata milik kandidatnya diassign ke kolom anchor, untuk setiap pasangan kolom yang berdampingan ia mengambil, di setiap baris yang punya konten di kedua selnya, interval dari tepi paling kanan kata-kata sel kiri ke tepi paling kiri kata-kata sel kanan, mengiriskan interval-interval itu antar baris, dan menolak seluruh kandidatnya kalau irisannya lebih sempit dari MinColumnGap kali 0.5, yaitu 6 poin pada default-nya

Dua detail penting. Baris yang salah satu selnya kosong tidak ikut memilih, jadi tabel dengan sel kosong, atau header yang mencakup lebih sedikit kolom daripada body-nya, tetap lolos. Dan lebar koridornya diturunkan dari MinColumnGap alih-alih dipaparkan sebagai opsi terpisah, karena keduanya mendeskripsikan hal fisik yang sama: celah yang ditinggalkan desainer di antara kolom. Logikanya cukup kecil untuk direproduksi kalau Anda membangun di atas word box mentah alih-alih API tabelnya, dan contoh di bawah mencerminkan pemeriksaan di dalam komponennya:

uses
  Math, PDFium;

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

// Mengembalikan False ketika ada pasangan kolom berdampingan yang tidak punya
// koridor vertikal bebas teks selebar minimal MinColumnGap / 2 di baris yang memakainya
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;                             // sel kosong tidak ikut memilih
      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;

Kenapa tabel ruled terekstraksi dua kali?

Tabel ruled terekstraksi dua kali karena pass whitespace-nya dulu melihat setiap kata di halaman, termasuk kata yang sudah ditempatkan pass ruled ke dalam grid, dan tabel ruled yang bersih secara konstruksi juga merupakan tabel whitespace yang sejajar sempurna. Pemeriksaan tumpang tindih sudah menolak kandidat whitespace yang batasnya mencakup lebih dari separuh tabel yang ada, tapi kandidat yang menggabungkan baris bawah tabelnya dengan beberapa baris teks sejajar di bawahnya bisa jatuh di bawah rasio itu dan bertahan sebagai tabel kedua yang sedikit lebih besar yang merembes ke tetangganya. ExtractTables kini membuang kata-kata itu sebelum pass whitespace-nya berjalan. Sebuah kata dibuang ketika titik pusatnya berada di dalam batas tabel mana pun yang dihasilkan pass ruled; titik pusatnya yang dipakai alih-alih pengecekan seluruhnya di dalam, supaya kata yang menyeberangi border sepersekian poin mengikuti tabel yang secara visual ia miliki. Strategi whitespace-nya lalu hanya bekerja pada kata yang bebas, yang juga berarti tabel kecil tanpa garis yang berada tepat di bawah tabel bergaris terdeteksi atas kemampuannya sendiri alih-alih menyatu dengan grid di atasnya

Kenapa "Purpose of Request:" keluar sebagai "of Purpose Request:"?

Kata-katanya keluar dalam urutan yang salah karena word box yang dibangun PDFium Component adalah gabungan glyph bounding box, dan "of" tidak punya descender sementara "Purpose" dan "Request:" punya. FPDFText_GetCharBox mengembalikan kotak ketat dari tinta glyph-nya di ruang halaman, bukan kotak yang diberi padding sampai ascent dan descent font-nya, dan word box-nya adalah gabungan kotak karakter-karakternya. Kata tanpa descender karena itu lebih pendek dan pusat vertikalnya lebih tinggi, sebesar 2 sampai 3 poin pada formulir yang dimaksud. Rutin teks sel yang lama mengurutkan kata-kata berdasarkan pusat Y lebih dulu, dengan toleransi 1 poin untuk "baris yang sama", lalu berdasarkan tepi kirinya; "of" melewati toleransinya, terurut sebagai barisnya sendiri di atas yang lain, dan dikeluarkan lebih dulu

Ini bukan keanehan PDFium melainkan konsekuensi dari bagaimana PDF memosisikan teks. ISO 32000-1 §9.2.2 dan §9.4.4 mendefinisikan penempatan glyph sebagai perpindahan horizontal di sepanjang baseline di ruang teks, dan satu-satunya metrik vertikal yang dibawa filenya bersifat per-font: entri Ascent, Descent, dan FontBBox di font descriptor pada §9.8.1. Tidak ada apa pun di filenya yang menyatakan dua glyph berbagi satu baris; itu harus disimpulkan dari geometrinya, dan glyph box yang ketat, yang membuat penyorotan seleksi terlihat benar seperti dijelaskan di seleksi baris teks dengan char box PDFium, adalah input yang salah untuk perbandingan jarak pusat

Perbaikan di versi 3.117.0 mengubah pertanyaannya dari "seberapa jauh jarak pusatnya" menjadi "seberapa besar kotaknya bertumpang tindih secara vertikal". Teks sel dirakit dengan mengelompokkan kata-kata selnya lebih dulu menjadi baris visual, di mana sebuah kata bergabung ke sebuah baris ketika overlap vertikalnya dengan batas berjalan baris itu setidaknya 25 persen dari tinggi yang lebih kecil di antara keduanya, lalu mengurutkan setiap barisnya dengan insertion sort berdasarkan tepi kirinya, lalu menyambungkan baris-barisnya dengan line break. "Purpose" dan "of" bertumpang tindih sepanjang seluruh x-height-nya, jauh lebih dari 25 persen kotak yang lebih pendek, jadi keduanya mendarat di baris yang sama dan terurut berdasarkan X seperti yang dimaksud

Kelompokkan baris teks lewat overlap, bukan lewat jarak pusat

Aturan yang layak dibawa pulang dari bug ini bersifat umum: kode tata letak teks PDF mana pun yang memutuskan "baris yang sama" dengan membandingkan pusat vertikalnya terhadap toleransi tetap akan gagal pada font sungguhan, dan kegagalannya senyap: tidak ada yang error, kata-katanya sekadar keluar dalam urutan yang salah. Descender yang campur aduk adalah pemicu paling ringan. Label bold 12 poin di samping nilai 10 poin, penanda footnote superscript, simbol mata uang yang digambar dari font fallback, dan word box hasil OCR dengan derau tinggi per katanya semuanya menggeser pusatnya lebih dari toleransi mana pun yang masih memisahkan baris 10 poin yang berdampingan pada leading 12 poin. Rasio overlap tidak terpengaruh ukuran: dua kotak di satu baseline bertumpang tindih sepanjang x-height yang dipakai bersama tak peduli apa yang dilakukan ascender dan descendernya, dan dua kotak di baris yang berdampingan tidak bertumpang tindih sama sekali

Aturan yang sama mudah diterapkan di luar ekstraksi tabel. TPdf.PageWordBoxes mengembalikan setiap kata di halaman aktif beserta persegi di ruang halamannya, jadi mengelompokkan sebuah halaman menjadi baris visual hanyalah loop pendek:

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>;   // gabungan berjalan per baris
  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;
  // urutkan setiap barisnya berdasarkan Rect.Left sebelum dibaca; PageWordBoxes
  // mengembalikan kata dalam urutan content stream, yang belum tentu visual
end;

Apa yang berubah bagi pemanggil yang sudah ada, dan di mana batasnya

Inti dari cuplikan itu adalah predikatnya, bukan loop-nya; untuk apa pun yang lebih dari sekadar dump cepat, mulailah dari model structured text, yang sudah membawa block, line, dan sumber reading order-nya, seperti dibahas di ekstraksi teks PDF terstruktur dengan reading order. Pemanggil tabel yang sudah ada mendapat ketiga koreksinya tanpa menyentuh opsinya. Ambang koridornya tetap setengah MinColumnGap, strategi whitespace-nya tetap memakai batas dua barisnya walaupun MinRows diset ke 1 (yang kini diterima strategi ruled), dan penyaringan kata ruled-first-nya berlaku tanpa syarat kapan pun kedua strateginya aktif. Pada set sampel tiga belas dokumen yang dipakai untuk rilisnya, pass whitespace-nya sebelumnya mengembalikan 34 fragmen dan positif palsu di samping 9 tabel ruled; setelah rilisnya ia tidak mengembalikan apa pun, dan jumlah tabel ruled-nya naik ke 41, meski sebagian besar kenaikan itu berasal dari rilis yang sama yang mengajari detektor ruled membaca border yang digambar sebagai filled rectangle, dan itu cerita tersendiri

Batas yang jujur: uji koridornya butuh setidaknya satu baris dengan konten di kedua sisi batasnya untuk bisa menolak apa pun, jadi kandidat dua baris yang dua celah teregangnya kebetulan jatuh dalam 6 poin satu sama lain tetap lolos. Itu kebetulan yang sempit, bukan lagi kepastian mendekati mutlak seperti sebelumnya, tapi dokumen yang padat prosa tanpa tabel dua baris sungguhan bisa menutupnya dengan menyetel MinRows ke 3. Teks rata kiri yang bergerigi tidak pernah jadi masalah dan tidak terpengaruh. Dan PDF tetap tidak punya objek tabel; ISO 32000-1 §14.8.4.3 mendefinisikan elemen struktur Table, tapi hanya Tagged PDF yang membawanya, jadi untuk selain itu grid-nya tetap inferensi dari geometri, dan nilai confidence di setiap TPdfTable ada karena inferensi memang layak diberi skor

Ekstraksi tabel, structured text, dan word box semuanya membaca dari model halaman yang sama di Delphi, C++Builder, dan Lazarus; API lengkapnya, termasuk TPdfTableExtractionOptions dan demo TableExtractionLab yang dirilis bersamanya, dijelaskan di halaman PDFium Component for Delphi