แก้ false positive ตาราง PDF จากข้อความ justified ใน Delphi

PDFium Component เวอร์ชัน 3.117.0 เลิกรายงานย่อหน้าแบบ justified เป็นตารางที่เรียงตรงแนวด้วย whitespace ด้วยการกำหนดให้ขอบคอลัมน์ทุกแห่งต้องเป็นทางเดินแนวตั้งที่ไม่มีข้อความบนทุกแถวที่มันคั่น ด้วยการข้ามคำที่กริดแบบมีเส้นตารางจับไปแล้ว และด้วยการประกอบข้อความในเซลล์จากการซ้อนทับในแนวตั้งแทนระยะห่างระหว่างจุดศูนย์กลางของกล่อง glyph การเปลี่ยนแปลงทั้งสามอย่างอยู่ใน ExtractTables กับ ExtractDocumentTables และไม่ต้องตั้งออปชันใด

รายงานที่จุดเรื่องนี้ขึ้นมานั้นไม่หวือหวาอะไร หน้าข่าวประชาสัมพันธ์ที่ไม่มีตารางอยู่เลยถูก ExtractTables ตอบกลับมาพร้อมตาราง whitespace ขนาด 5x4 โดย confidence สูงกว่าค่าเริ่มต้นของ MinConfidence ที่ 0.5 อย่างสบาย ๆ และในเซลล์ก็มีเศษของข้อความเนื้อความธรรมดา ใบสมัครเข้าศึกษาก็ทำแบบเดียวกันกับย่อหน้าความเรียงของมัน แล้วให้ผลออกมาเป็น 3x4 กับ 5x3 เอกสารทั้งสองตั้งค่าเป็น justified ปฏิกิริยาที่เห็นชัดคือไปจูน threshold และบทเรียนที่มีประโยชน์จากรุ่นนี้คือการจูนแก้เรื่องนี้ไม่ได้ เพราะกฎที่กำลังถูกจูนนั้นถามคำถามผิด

uses
  PDFium;

// การตรวจ regression: ลิสต์ตาราง whitespace ทุกตัวในเอกสาร เพื่อยืนยันว่าหน้า
// ที่คุณรู้ว่าเป็นร้อยแก้วล้วนสะอาดจริง
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;

ทำไมข้อความ justified ถึงดูเหมือนตาราง

ย่อหน้าแบบ justified ดูเหมือนตารางเพราะบรรทัดที่ justify แล้วคือแถวของคำที่คั่นด้วยช่องว่างที่ layout engine ยืดออก และเมื่อช่องว่างที่ถูกยืดไปถึง MinColumnGap ตัวตรวจจับก็ไม่มีวิธีดูแค่ภายในแถวที่จะแยกมันออกจากตัวคั่นคอลัมน์ กลยุทธ์ whitespace ใน PDFium Component จัดกลุ่ม word box เป็นแถวเชิงสายตา แยกแต่ละแถวออกเป็นกลุ่มคำตรงจุดที่ระยะห่างแนวนอนจากคำก่อนหน้าอย่างน้อย MinColumnGap (12 point ตามค่าเริ่มต้น) และยอมรับว่าเป็นตารางเมื่อมีอย่างน้อยสองแถวติดกันที่ทวนซ้ำ group anchor ที่ชิดซ้ายอย่างน้อย MinColumns ตำแหน่งภายใน AlignmentTolerance ซึ่งคือ 3 point นั่นคือกฎที่อธิบายไว้ในภาพรวมของการตรวจจับตาราง และสำหรับตารางที่เรียงตรงแนวจริง ๆ มันถูกต้องเป๊ะ

ทีนี้ลองเอามันไปใช้กับร้อยแก้ว 10 point แบบ justified ยี่สิบบรรทัด ทุกบรรทัดถูกยืดไปถึงขอบขวาเดียวกัน บรรทัดที่จบด้วยคำยาวจึงดึงช่องว่างภายในของมันให้กว้างออก และในย่อหน้าที่มีบรรทัดสั้นอยู่สองสามบรรทัด ช่องว่างบางตัวก็ข้าม 12 point ไป สองแถวติดกันต้องการแค่ช่องว่างที่ถูกยืดอย่างละหนึ่งช่อง โดยตกภายใน 3 point ของตำแหน่ง X เดียวกัน ก็พอจะสร้าง candidate ขนาดสองแถวสองคอลัมน์ได้ พอมีบรรทัดมากพอนี่ไม่ใช่ความโชคร้าย แต่เป็นความน่าจะเป็นที่เข้าใกล้ความแน่นอน และ 5x4 บนหน้าข่าวประชาสัมพันธ์ก็แค่ช่วงที่ช่องว่างสี่ช่องเรียงตรงกันบนห้าบรรทัด

ทุก threshold แลกเอกสารประเภทหนึ่งกับอีกประเภทหนึ่ง การขึ้น MinColumnGap ไปเป็น 20 point ทำให้คอลัมน์ที่บีบแน่นของรายงานการเงินที่ข้อมูลหนาแน่นหายไป ซึ่งก็คือเคสที่ค่าเริ่มต้นถูกลดลงมาแล้วเพื่อมันโดยเฉพาะ การขึ้น MinRows เป็น 3 ทิ้งตารางสองแถวจริง ๆ และแค่ลดโอกาสสำหรับย่อหน้ายาว การรัด AlignmentTolerance ให้ต่ำกว่า 3 point ทำให้ word box ที่ได้จาก OCR พัง เพราะขอบซ้ายของมันแกว่งเกินกว่านั้น สัญญาณระดับแถวมันกำกวมจริง ๆ การแก้จึงต้องมาจากสัญญาณที่แถวพกมาเองไม่ได้

อะไรทำให้ขอบคอลัมน์เป็นของจริง

ขอบคอลัมน์จริง ๆ คือแถบแนวตั้งของหน้าที่ว่างอยู่ตลอดทุกแถวที่มันคั่น ตารางมีมันอยู่ระหว่างคอลัมน์ทุกคู่โดยโครงสร้าง เพราะเซลล์ถูกจัดวางเทียบกับตำแหน่ง X ที่ใช้ร่วมกัน ย่อหน้าแบบ justified ยืดช่องว่างระหว่างคำที่ตำแหน่งแนวนอนต่างกันในแต่ละบรรทัด จึงไม่มีแถบใดรอดจากการ intersect เกินหนึ่งหรือสองบรรทัด ตอนนี้ PDFium Component ทดสอบสิ่งนั้นเป๊ะ ๆ: หลังจากกลุ่มคำของ candidate ถูกจับเข้า anchor column แล้ว สำหรับคอลัมน์ที่ติดกันทุกคู่ มันจะเอาช่วงจากขอบขวาสุดของคำในเซลล์ซ้ายถึงขอบซ้ายสุดของคำในเซลล์ขวา บนทุกแถวที่มีเนื้อหาทั้งสองเซลล์ แล้ว intersect ช่วงเหล่านั้นข้ามแถว และปฏิเสธ candidate ทั้งตัวถ้าการ intersect แคบกว่า MinColumnGap คูณ 0.5 ซึ่งคือ 6 point ที่ค่าเริ่มต้น

มีสองรายละเอียดที่สำคัญ แถวที่เซลล์ใดเซลล์หนึ่งว่างไม่มีการออกเสียง ตารางที่มีเซลล์ว่าง หรือที่มี header คร่อมคอลัมน์น้อยกว่าตัวเนื้อหา จึงยังผ่านได้ และความกว้างของทางเดินนั้นอนุมานจาก MinColumnGap แทนที่จะเปิดเป็นออปชันแยก เพราะทั้งสองบรรยายสิ่งทางกายภาพเดียวกัน คือช่องว่างที่ผู้ออกแบบเว้นไว้ระหว่างคอลัมน์ ตรรกะนี้สั้นพอจะทำซ้ำได้ถ้าคุณสร้างบน word box ดิบแทนที่จะใช้ 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;

ทำไมตารางแบบมีเส้นตารางถึงถูกดึงสองครั้ง

ตารางแบบมีเส้นตารางถูกดึงสองครั้งเพราะรอบ whitespace เคยมองเห็นทุกคำบนหน้า รวมถึงคำที่รอบแบบมีเส้นตารางจัดเข้าไปในกริดแล้ว และตารางที่มีเส้นตารางซึ่งสะอาดก็เป็นตาราง whitespace ที่เรียงตรงแนวสมบูรณ์แบบโดยโครงสร้างอยู่แล้ว การตรวจจับการทับซ้อนที่มีอยู่แล้วปฏิเสธ candidate ของ whitespace ที่ขอบเขตของมันครอบตารางที่มีอยู่เกินครึ่ง แต่ candidate ที่รวมแถวล่าง ๆ ของตารางเข้ากับบรรทัดข้อความที่เรียงตรงกันสองสามบรรทัดใต้ลงมาอาจต่ำกว่าอัตราส่วนนั้นแล้วรอดไปเป็นตารางที่สองซึ่งใหญ่กว่าเล็กน้อยและลามเข้าไปในเพื่อนบ้าน ExtractTables ตอนนี้ลบคำเหล่านั้นออกก่อนที่รอบ whitespace จะรัน คำจะถูกลบเมื่อจุดศูนย์กลางของมันอยู่ในขอบเขตของตารางใดก็ตามที่รอบแบบมีเส้นตารางผลิตออกมา; ใช้จุดศูนย์กลางแทนการครอบคลุมทั้งคำ เพื่อให้คำที่คร่อมเส้นขอบไปเสี้ยว point ตามตารางที่มันเป็นส่วนหนึ่งในเชิงสายตาไป กลยุทธ์ whitespace จึงทำงานเฉพาะกับคำที่ว่างอยู่ ซึ่งหมายความด้วยว่าตารางเล็ก ๆ ที่ไม่มีเส้นตารางซึ่งอยู่ใต้ตารางที่มีเส้นตารางโดยตรงจะถูกตรวจจับด้วยคุณสมบัติของตัวเอง แทนที่จะถูกหลอมรวมกับกริดข้างบน

ทำไม "Purpose of Request:" ออกมาเป็น "of Purpose Request:"

คำออกมาสลับลำดับกันเพราะ word box ที่ PDFium Component สร้างเป็นยูเนียนของ bounding box ของ glyph และ "of" ไม่มีหางตัวอักษรล่าง (descender) ขณะที่ "Purpose" กับ "Request:" มี FPDFText_GetCharBox คืนกล่องที่แนบชิดกับหมึกของ glyph ใน page space ไม่ใช่กล่องที่เติมระยะ ascent และ descent ของฟอนต์เข้ามา และ word box ก็เป็นยูเนียนของกล่องตัวอักษรของมัน คำที่ไม่มี descender จึงสั้นกว่าและจุดศูนย์กลางแนวตั้งของมันอยู่สูงกว่า ประมาณ 2 ถึง 3 point บนฟอร์มที่ว่านี้ รูทีนข้อความในเซลล์ตัวเก่าเรียงคำด้วย center Y ก่อน โดยมี tolerance 1 point สำหรับ "บรรทัดเดียวกัน" แล้วจึงเรียงด้วยขอบซ้าย "of" หลุด tolerance จึงถูกเรียงเป็นบรรทัดของตัวเองอยู่เหนือตัวอื่น และถูก emit ออกมาก่อน

นี่ไม่ใช่ความประหลาดของ PDFium เท่าไร แต่เป็นผลจากวิธีที่ PDF วางตำแหน่งข้อความ ISO 32000-1 §9.2.2 และ §9.4.4 นิยามการวาง glyph ว่าเป็นการเลื่อนในแนวนอนไปตาม baseline ใน text space และเมตริกแนวตั้งเดียวที่ไฟล์พกมาคือระดับฟอนต์: รายการ Ascent, Descent และ FontBBox ของ font descriptor ใน §9.8.1 ไม่มีอะไรในไฟล์บอกว่า glyph สองตัวอยู่บรรทัดเดียวกัน นั่นต้องอนุมานจากเรขาคณิต และกล่อง glyph ที่แนบชิดซึ่งทำให้การไฮไลต์ตอนเลือกดูถูกต้อง อย่างที่บรรยายไว้ในการเลือกลายข้อความด้วย char box ของ PDFium เป็น input ที่ผิดสำหรับการเทียบระยะห่างระหว่างจุดศูนย์กลาง

การแก้ในเวอร์ชัน 3.117.0 เปลี่ยนคำถามจาก "จุดศูนย์กลางห่างกันแค่ไหน" เป็น "กล่องซ้อนทับกันในแนวตั้งมากแค่ไหน" ข้อความในเซลล์ถูกประกอบโดยจัดกลุ่มคำในเซลล์เป็นบรรทัดเชิงสายตาก่อน โดยคำจะเข้าร่วมบรรทัดเมื่อการซ้อนทับในแนวตั้งของมันกับขอบเขตที่วิ่งอยู่ของบรรทัดนั้นมีอย่างน้อย 25 เปอร์เซ็นต์ของความสูงที่น้อยกว่าระหว่างสองค่า จากนั้น insertion sort แต่ละบรรทัดด้วยขอบซ้าย แล้วเชื่อมบรรทัดด้วยการขึ้นบรรทัดใหม่ "Purpose" กับ "of" ซ้อนทับกันตลอดความสูง x เต็ม ซึ่งมากกว่า 25 เปอร์เซ็นต์ของกล่องที่สั้นกว่าอยู่ไกล พวกมันจึงลงบรรทัดเดียวกันและเรียงตาม X อย่างที่ตั้งใจ

จับกลุ่มบรรทัดข้อความด้วยการซ้อนทับ ไม่ใช่ด้วยระยะจุดศูนย์กลาง

กฎที่คุ้มจะเก็บจาก bug นี้เป็นเรื่องทั่วไป: โค้ดจัดวางข้อความ PDF ตัวใดก็ตามที่ตัดสิน "บรรทัดเดียวกัน" ด้วยการเทียบจุดศูนย์กลางแนวตั้งกับ tolerance ตายตัวจะพังกับฟอนต์จริง และความล้มเหลวนั้นเงียบ: ไม่มีอะไร error คำก็แค่ออกมาผิดลำดับ descender ที่ปนกันเป็นตัวกระตุ้นที่อ่อนที่สุด ป้ายตัวหนา 12 point ข้างค่าตัวเลข 10 point, เครื่องหมายอ้างอิงเชิงอรรถแบบยกกำลัง, สัญลักษณ์สกุลเงินที่วาดด้วยฟอนต์สำรอง และ word box จาก OCR ที่มีความสูงแกว่งเป็นรายคำ ล้วนขยับจุดศูนย์กลางเกินกว่า tolerance ใดก็ตามที่ยังแยกบรรทัด 10 point ที่ระยะห่างบรรทัด 12 point ออกจากกันได้ อัตราส่วนการซ้อนทับไม่ขึ้นกับขนาด: กล่องสองกล่องบน baseline เดียวกันซ้อนทับกันตลอดความสูง x ที่ใช้ร่วมกันไม่ว่า ascent กับ descender ของมันจะเป็นอย่างไร และกล่องสองกล่องบนบรรทัดที่ติดกันก็ไม่ซ้อนทับกันเลย

กฎเดียวกันนี้เอาไปใช้บอกการดึงตารางได้ง่าย ๆ TPdf.PageWordBoxes คืนทุกคำบนหน้าที่ใช้งานอยู่พร้อมสี่เหลี่ยมใน page space ของมัน การจัดกลุ่มหน้าให้เป็นบรรทัดเชิงสายตาจึงเป็นลูปสั้น ๆ:

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 คืนคำ
  // ตามลำดับใน content stream ซึ่งไม่ได้รับประกันว่าเป็นลำดับเชิงสายตา
end;

อะไรเปลี่ยนไปสำหรับผู้เรียกเดิม และขอบเขตอยู่ตรงไหน

ประเด็นของ snippet นั้นอยู่ที่ predicate ไม่ใช่ที่ลูป; สำหรับอะไรที่เกินกว่าการ dump เร็ว ๆ ให้เริ่มจาก model ของ structured text ซึ่งพก block, บรรทัด และแหล่งลำดับการอ่านไว้อยู่แล้ว อย่างที่ครอบคลุมอยู่ในการดึงข้อความ PDF แบบมีโครงสร้างพร้อมลำดับการอ่าน ผู้เรียกตารางเดิมได้การแก้ทั้งสามข้อโดยไม่ต้องแตะออปชันของตัวเอง threshold ของทางเดินถูกตรึงไว้ที่ครึ่งหนึ่งของ MinColumnGap กลยุทธ์ whitespace ยังคงพื้นขั้นต่ำสองแถวแม้ตั้ง MinRows เป็น 1 (ซึ่งกลยุทธ์แบบมีเส้นตารางตอนนี้รับได้) และการกรองคำก่อนรอบแบบมีเส้นตารางก็เป็นแบบไม่มีเงื่อนไขทุกครั้งที่เปิดทั้งสองกลยุทธ์ บนชุดตัวอย่าง 13 ฉบับที่ใช้สำหรับรุ่นนี้ รอบ whitespace เคยคืน 34 ชิ้นส่วนและ false positive เคียงกับตารางแบบมีเส้นตาราง 9 ตัว; หลังรุ่นนี้มันคืนศูนย์ และจำนวนตารางแบบมีเส้นตารางขึ้นไปเป็น 41 แม้ว่าการเพิ่มขึ้นส่วนใหญ่มาจากการที่รุ่นเดียวกันสอนตัวตรวจจับแบบมีเส้นตารางให้อ่านขอบที่วาดเป็น filled rectangle ซึ่งเป็นเรื่องแยกกัน

ขอบเขตที่พูดตรง ๆ: การทดสอบทางเดินต้องมีอย่างน้อยหนึ่งแถวที่มีเนื้อหาทั้งสองฝั่งของขอบเขตจึงจะปฏิเสธอะไรได้ candidate สองแถวที่ช่องว่างถูกยืดสองช่องของมันบังเอิญตกภายใน 6 point ของกันและกันจึงยังผ่านอยู่ นั่นเป็นความบังเอิญที่แคบ ไม่ใช่ความเกือบแน่นอนแบบที่เคยเป็น แต่เอกสารที่เน้นร้อยแก้วและไม่มีตารางสองแถวจริง ๆ ปิดช่องนั้นได้ด้วยการตั้ง MinRows เป็น 3 ข้อความที่ชิดซ้ายแบบขอบไม่เรียบไม่เคยเป็นปัญหาและไม่ได้รับผลกระทบ และ PDF ก็ยังไม่มีออบเจ็กต์ตาราง; ISO 32000-1 §14.8.4.3 นิยาม structure element Table ไว้ แต่มีแค่ Tagged PDF ที่พกมันมา นอกนั้นกริดก็ยังเป็นการอนุมานจากเรขาคณิต และค่า confidence บน TPdfTable แต่ละตัวมีอยู่ก็เพราะการอนุมานสมควรมีคะแนนกำกับ

การดึงตาราง, structured text และ word box ล้วนอ่านจาก page model ตัวเดียวกันใน Delphi, C++Builder และ Lazarus; API แบบเต็ม รวมถึง TPdfTableExtractionOptions และ TableExtractionLab demo ที่ออกมาพร้อมกัน บรรยายไว้ที่หน้า PDFium Component for Delphi