Sửa dương tính giả bảng PDF từ text căn đều trong Delphi

PDFium Component phiên bản 3.117.0 ngừng báo các đoạn văn căn đều hai bên thành bảng theo khoảng trắng bằng cách đòi mỗi biên cột phải là một hành lang dọc không có text trên mọi dòng mà nó phân tách, bỏ qua các word đã được một lưới kẻ dòng nhận trước, và lắp text trong ô theo độ chồng dọc thay vì khoảng cách giữa tâm các glyph box. Cả ba thay đổi đều nằm trong ExtractTables và ExtractDocumentTables và không cần option nào

Báo cáo khởi đầu cho việc này thì chẳng có gì hào nhoáng. Một trang thông cáo báo chí không hề có bảng nào lại quay về từ ExtractTables với một bảng khoảng trắng 5x4, confidence cao thoải mái trên MinConfidence mặc định là 0,5, và các ô chứa những mảnh văn bản thường. Một mẫu đơn nhập học cũng y hệt với các đoạn văn tự luận của nó và cho ra một bảng 3x4 cùng một bảng 5x3. Cả hai tài liệu đều được set căn đều hai bên. Phản ứng hiển nhiên là chỉnh các ngưỡng, và bài học hữu ích từ bản phát hành này là chỉnh ngưỡng không sửa được, vì cái quy tắc đang bị chỉnh hỏi sai câu hỏi

uses
  PDFium;

// Kiểm tra hồi quy: liệt kê mọi bảng theo khoảng trắng trong một tài liệu để
// một trang bạn biết chỉ có văn xuôi có thể được xác nhận là sạch
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;

Vì sao text căn đều hai bên trông như một bảng?

Một đoạn văn căn đều hai bên trông như một bảng vì một dòng căn đều là một hàng các từ ngăn nhau bằng những khoảng mà layout engine đã kéo giãn, và một khi khoảng bị kéo giãn chạm tới MinColumnGap thì bộ phát hiện không có cách nào chỉ dựa vào hàng để phân biệt nó với một dấu phân tách cột. Chiến lược khoảng trắng trong PDFium Component gom các word box thành các hàng thị giác, cắt mỗi hàng thành các nhóm từ ở những chỗ mà khoảng cách ngang tới từ trước đó ít nhất là MinColumnGap (mặc định 12 point), và chấp nhận một bảng khi có ít nhất hai hàng liên tiếp lặp lại ít nhất MinColumns mốc nhóm căn trái trong sai số AlignmentTolerance, tức 3 point. Đó là quy tắc được mô tả trong bài tổng quan về phát hiện bảng, và với một bảng thẳng hàng thật sự thì nó hoàn toàn đúng

Giờ thử áp nó lên hai mươi dòng văn xuôi cỡ 10 point căn đều hai bên. Mọi dòng đều được kéo giãn tới cùng một lề phải, nên một dòng kết thúc bằng một từ dài sẽ kéo các khoảng bên trong nó rộng ra, và trong một đoạn có vài dòng ngắn thì một số khoảng đó vượt 12 point. Hai dòng liên tiếp chỉ cần mỗi dòng một khoảng bị kéo giãn, rơi trong 3 point quanh cùng một vị trí X, là đã thành một ứng viên hai hàng hai cột. Qua đủ nhiều dòng thì đây không phải vận may xấu; nó là một xác suất tiến dần tới chắc chắn, và bảng 5x4 trên trang thông cáo chỉ đơn giản là lần chạy mà bốn khoảng như vậy thẳng hàng trên năm dòng

Mọi ngưỡng đều đánh đổi nhóm tài liệu này lấy nhóm tài liệu khác. Nâng MinColumnGap lên 20 point sẽ mất các cột chen chúc của những báo cáo tài chính dày đặc, đúng cái ca mà giá trị mặc định vốn đã được hạ xuống để phục vụ. Nâng MinRows lên 3 sẽ vứt đi những bảng hai hàng thật và chỉ làm giảm xác suất với các đoạn văn dài. Thắt AlignmentTolerance xuống dưới 3 point sẽ phá các word box sinh từ OCR, nơi mép trái dao động hơn mức đó. Tín hiệu ở mức từng hàng thật sự mơ hồ, nên bản sửa phải đến từ một tín hiệu mà bản thân các hàng không mang theo

Điều gì khiến một biên cột là thật?

Một biên cột thật là một dải dọc của trang luôn trống trên mọi dòng mà nó phân tách. Một bảng có một dải như vậy giữa mỗi cặp cột ngay từ cách dựng, vì các ô được xếp theo những vị trí X dùng chung. Một đoạn văn căn đều hai bên kéo giãn các khoảng giữa từ ở những vị trí ngang khác nhau trên mỗi dòng, nên không dải nào sống sót qua phép giao của hơn một hai dòng. PDFium Component giờ kiểm tra đúng điều đó: sau khi các nhóm từ của ứng viên đã được gán vào các cột neo, với mỗi cặp cột kề nhau nó lấy, trên mọi dòng có nội dung ở cả hai ô, khoảng từ mép phải nhất của các từ trong ô trái tới mép trái nhất của các từ trong ô phải, giao các khoảng đó qua các dòng, và loại bỏ toàn bộ ứng viên nếu phần giao hẹp hơn MinColumnGap nhân 0,5, tức 6 point ở giá trị mặc định

Hai chi tiết đáng lưu ý. Những dòng mà một trong hai ô rỗng thì không bỏ phiếu, nên một bảng có ô trống, hay có header chỉ trải ít cột hơn phần thân, vẫn qua được. Và bề rộng hành lang được suy từ MinColumnGap chứ không phơi ra thành một option riêng, vì cả hai mô tả cùng một thứ vật lý: khoảng trống mà người thiết kế để giữa các cột. Logic này đủ nhỏ để tái tạo nếu bạn đang làm việc trên các word box thô thay vì dùng API bảng, và mẫu bên dưới phản chiếu đúng phép kiểm tra bên trong component:

uses
  Math, PDFium;

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

// Trả về False khi có một cặp cột kề nhau thiếu một hành lang dọc
// không text rộng ít nhất MinColumnGap / 2 trên các dòng dùng nó
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;                             // ô rỗng không bỏ phiếu
      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;

Vì sao bảng kẻ dòng bị trích xuất hai lần?

Bảng kẻ dòng bị trích xuất hai lần vì lượt phát hiện theo khoảng trắng trước đây nhìn thấy mọi word trên trang, kể cả những từ mà lượt kẻ dòng đã đặt vào một lưới, mà một bảng kẻ dòng sạch thì ngay từ cách dựng cũng là một bảng khoảng trắng thẳng hàng hoàn hảo. Đã có một phép kiểm tra chồng lấn loại bỏ ứng viên khoảng trắng có biên bao phủ hơn nửa một bảng đã tồn tại, nhưng một ứng viên gộp các hàng dưới của bảng với vài dòng text thẳng hàng bên dưới nó có thể nằm dưới tỉ lệ đó và sống sót thành một bảng thứ hai, to hơn một chút, tràn sang bảng bên cạnh. ExtractTables giờ loại những word đó trước khi lượt phát hiện theo khoảng trắng chạy. Một word bị bỏ khi điểm tâm của nó nằm trong biên của bất kỳ bảng nào mà lượt kẻ dòng sinh ra; người ta dùng tâm thay vì đòi nằm trọn bên trong để một từ vắt qua đường viền chỉ một phần nhỏ của point vẫn đi theo bảng mà nó trực quan thuộc về. Chiến lược khoảng trắng sau đó chỉ làm việc trên các word còn tự do, nghĩa là một bảng nhỏ không kẻ dòng nằm ngay dưới một bảng kẻ dòng cũng được phát hiện theo đúng giá trị của nó thay vì bị dính vào cái lưới phía trên

Vì sao “Purpose of Request:” lại ra thành “of Purpose Request:”?

Các từ ra sai thứ tự vì word box mà PDFium Component dựng là hợp của các bounding box của từng glyph, mà “of” không có phần đuôi chữ còn “Purpose” và “Request:” thì có. FPDFText_GetCharBox trả về hộp khít của phần mực in của glyph trong không gian trang, không phải một hộp được đệm theo ascent và descent của font, và word box là hợp các hộp của các ký tự trong nó. Một từ không có phần đuôi chữ vì thế ngắn hơn và tâm dọc của nó nằm cao hơn, khoảng 2 tới 3 point trên mẫu đơn đang nói tới. Routine xử lý text trong ô ngày trước sắp các từ theo tâm Y trước, với sai số 1 point cho “cùng dòng”, rồi theo mép trái; “of” vượt qua sai số đó, được sắp thành dòng riêng phía trên những từ kia, và được phát ra đầu tiên

Đây không hẳn là một điểm lạ của PDFium mà là hệ quả của cách PDF định vị text. ISO 32000-1 §9.2.2 và §9.4.4 định nghĩa việc đặt glyph là dịch chuyển ngang dọc theo baseline trong không gian text, còn các số đo dọc duy nhất mà tệp mang theo là theo từng font: các entry Ascent, Descent và FontBBox của font descriptor ở §9.8.1. Không có gì trong tệp nói rằng hai glyph nằm cùng một dòng; điều đó phải được suy ra từ hình học, và các glyph box khít khiến việc highlight lựa chọn trông đúng, như mô tả trong chọn dòng text bằng char box của PDFium, lại là đầu vào sai cho một phép so khoảng cách giữa các tâm

Bản sửa ở phiên bản 3.117.0 đổi câu hỏi từ “các tâm cách nhau bao xa” thành “các hộp chồng nhau theo chiều dọc bao nhiêu”. Text trong ô được lắp bằng cách trước tiên gom các từ của ô thành các dòng thị giác, trong đó một từ nhập vào một dòng khi độ chồng dọc của nó với biên đang chạy của dòng đó ít nhất bằng 25 phần trăm chiều cao nhỏ hơn trong hai chiều cao, rồi sắp xếp chèn từng dòng theo mép trái, rồi nối các dòng bằng một dấu xuống dòng. “Purpose” và “of” chồng nhau trên toàn bộ chiều cao x, tức nhiều hơn hẳn 25 phần trăm của hộp ngắn hơn, nên chúng nằm cùng dòng và được sắp theo X đúng như mong muốn

Gom dòng text theo độ chồng, không theo khoảng cách tâm

Quy tắc đáng mang theo từ con bug này là một quy tắc phổ quát: mọi code dàn trang text PDF quyết định “cùng dòng” bằng cách so các tâm dọc với một sai số cố định đều sẽ hỏng với font thật, và hỏng một cách âm thầm: không có gì báo lỗi, các từ chỉ đơn giản ra sai thứ tự. Phần đuôi chữ lẫn lộn là nguyên nhân nhẹ nhất. Một nhãn in đậm 12 point bên cạnh các giá trị 10 point, một dấu chú thích dạng superscript, một ký hiệu tiền tệ được vẽ từ font dự phòng, và các word box từ OCR với nhiễu chiều cao theo từng từ đều làm các tâm dịch chuyển nhiều hơn bất kỳ sai số nào còn tách nổi các dòng 10 point kề nhau ở leading 12 point. Tỉ lệ chồng thì không phụ thuộc kích thước: hai hộp trên cùng một baseline chồng nhau trên chiều cao x dùng chung bất kể ascender và descender của chúng ra sao, còn hai hộp ở hai dòng kề nhau thì không chồng chút nào

Cùng quy tắc đó cũng dễ áp bên ngoài việc trích xuất bảng. TPdf.PageWordBoxes trả về mọi word trên trang đang hoạt động kèm hình chữ nhật trong không gian trang, nên gom một trang thành các dòng thị giác chỉ là một vòng lặp ngắn:

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>;   // hợp đang chạy của mỗi dòng
  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;
  // sắp từng dòng theo Rect.Left trước khi đọc nó; PageWordBoxes trả về
  // các word theo thứ tự content stream, không bảo đảm là thứ tự thị giác
end;

Điều gì thay đổi với người gọi hiện có, và các giới hạn nằm ở đâu

Điểm đáng chú ý của đoạn code đó là vị từ, không phải vòng lặp; với bất cứ thứ gì vượt quá một lần dump nhanh, hãy bắt đầu từ model structured text, thứ đã mang sẵn các block, các line và một nguồn thứ tự đọc, như trình bày trong trích xuất text PDF có cấu trúc kèm thứ tự đọc. Những người gọi API bảng hiện có nhận được cả ba bản sửa mà không phải đụng vào options của họ. Ngưỡng hành lang được cố định ở một nửa MinColumnGap, chiến lược khoảng trắng giữ ngưỡng hai dòng ngay cả khi MinRows được đặt bằng 1 (giá trị mà chiến lược kẻ dòng giờ chấp nhận), và việc lọc word ưu tiên bảng kẻ dòng là vô điều kiện mỗi khi cả hai chiến lược đều được bật. Trên tập 13 tài liệu mẫu dùng cho bản phát hành, lượt phát hiện theo khoảng trắng trước đây trả về 34 mảnh vụn và dương tính giả bên cạnh 9 bảng kẻ dòng; sau bản phát hành nó không trả về cái nào, và số bảng kẻ dòng tăng lên 41, dù phần lớn mức tăng đó đến từ việc cùng bản phát hành dạy bộ phát hiện kẻ dòng đọc các viền được vẽ dưới dạng hình chữ nhật tô đầy, một câu chuyện riêng

Nói thật các giới hạn: phép kiểm tra hành lang cần ít nhất một dòng có nội dung ở cả hai phía của một biên thì mới loại được gì đó, nên một ứng viên hai dòng mà hai khoảng bị kéo giãn của nó tình cờ rơi trong 6 point của nhau vẫn qua được. Đó là một sự trùng hợp hẹp chứ không còn là gần như chắc chắn như trước, nhưng các tài liệu nặng văn xuôi không có bảng hai dòng thật có thể đóng nốt khe đó bằng cách đặt MinRows bằng 3. Text căn trái so le chưa bao giờ là vấn đề và không bị ảnh hưởng. Và PDF vẫn không có object table; ISO 32000-1 §14.8.4.3 định nghĩa một structure element Table, nhưng chỉ Tagged PDF mới mang nó, nên với mọi thứ còn lại thì cái lưới vẫn là một suy luận từ hình học, và giá trị confidence trên mỗi TPdfTable tồn tại vì suy luận thì đáng được cho điểm

Trích xuất bảng, structured text và word box đều đọc từ cùng một page model trong Delphi, C++Builder và Lazarus; toàn bộ API, gồm TPdfTableExtractionOptions và demo TableExtractionLab đi kèm, được trình bày trên trang PDFium Component cho Delphi