ביטול זיהויים שגויים של טבלאות PDF מטקסט מיושר בדלפי

‏רכיב PDFium גרסה 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 מקבצת תיבות מילים לשורות חזותיות, מפצלת כל שורה לקבוצות מילים בכל מקום שהמרחק האופקי למילה הקודמת הוא לפחות MinColumnGap (12 נקודות כברירת מחדל), ומקבלת טבלה כששני שורות עוקבות לפחות חוזרות על לפחות MinColumns עוגני קבוצה מיושרים לשמאל בתוך AlignmentTolerance, שזה 3 נקודות. זה הכלל שמתואר בסקירת זיהוי הטבלאות, ולטבלה מיושרת אמיתית הוא בדיוק נכון

עכשיו החילו אותו על עשרים שורות של פרוזה מיושרת בגודל 10 נקודות. כל שורה נמתחת לאותו שול ימני, כך ששורה שנגמרת במילה ארוכה מושכת את הרווחים הפנימיים שלה לרווחה, ובפסקה עם כמה שורות קצרות חלק מהרווחים האלה חוצים 12 נקודות. שתי שורות עוקבות צריכות רק רווח מתוח אחד כל אחת, שנוחת בתוך 3 נקודות מאותו מיקום X, כדי ליצור מועמד בן שתי שורות ושתי עמודות. על מספיק שורות זה לא מזל רע; זו הסתברות שמתקרבת לודאות, וה-5x4 בהודעה לעיתונות היה פשוט הרצף שבו ארבעה רווחים כאלה התיישרו על חמש שורות

כל סף מחליף סוג אחד של מסמך בסוג אחר. העלאת MinColumnGap ל-20 נקודות מאבדת את העמודות הקומפקטיות של דוחות כספיים צפופים, וזה בדיוק המקרה שבשבילו ברירת המחדל כבר הונמכה. העלאת MinRows ל-3 פוסלת טבלאות אמיתיות בנות שתי שורות ורק מקטינה את הסיכויים לפסקאות ארוכות. הידוק AlignmentTolerance מתחת ל-3 נקודות שובר תיבות מילים שמגיעות מ-OCR, שקצוותיהן השמאליים רועדים ביותר מזה. האות ברמת השורה הוא אמביוולנטי באמת, ולכן התיקון חייב לבוא מאות שאות שמשורה לא נושאת בעצמה

מה הופך גבול עמודה לאמיתי?

גבול עמודה אמיתי הוא רצועה אנכית של העמוד שנשארת ריקה על פני כל שורה שהוא מפריד. לטבלה יש אחד כזה בין כל זוג עמודות מעצם בנייתה, כי התאים נפרסו מול מיקומי X משותפים. פסקה מיושרת מותחת את רווחי המילים שלה במיקומים אופקיים שונים בכל שורה, כך ששום רצועה לא שורדת את החיתוך של יותר משורה או שתיים. רכיב PDFium בודקת בדיוק את זה כעת: אחרי שקבוצות המילים של המועמד הוקצו לעמודות העוגן, לכל זוג עמודות סמוכות היא לוקחת, בכל שורה שיש בה תוכן בשני התאים, את הקטע מהקצה הימני ביותר של מילות התא השמאלי ועד הקצה השמאלי ביותר של מילות התא הימני, מצטלבת בין הקטעים האלה על פני השורות, ודוחה את כל המועמד אם החיתוך צר מ-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 בונה הן איחודים של תיבות חוסמות של גליפים, ול-"of" אין יורד מתחת לשורה בעוד של-"Purpose" ושל-"Request:" יש. FPDFText_GetCharBox מחזירה את התיבה ההדוקה של הדיו של הגליף במרחב העמוד, לא תיבה מרופדת לגובה העליון והתחתון של הגופן, ותיבת המילה היא איחוד התיבות של התווים שלה. מילה בלי יורדים קצרה לכן יותר והמרכז האנכי שלה גבוה יותר, ב-2 עד 3 נקודות בטופס המדובר. שגרת טקסט התא הישנה מיינה מילים לפי מרכז Y תחילה, עם סבילות של נקודה אחת ל"אותה שורה", ואחר כך לפי הקצה השמאלי; "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, שזה הרבה יותר מ-25 אחוז מהתיבה הקצרה יותר, כך שהן נוחתות על אותה שורה וממוינות לפי X כמתוכנן

לקבץ שורות טקסט לפי חפיפה, לא לפי מרחק בין מרכזים

הכלל ששווה לקחת מהבאג הזה הוא כללי: כל קוד פריסת טקסט ב-PDF שמחליט "אותה שורה" על ידי השוואת מרכזים אנכיים מול סבילות קבועה ייכשל בגופנים אמיתיים, והכשל שקט: שום דבר לא נכשל, המילים פשוט יוצאות בסדר שגוי. יורדים מעורבים הם הגורם הקל ביותר. תווית מודגשת בגודל 12 נקודות לצד ערכים בגודל 10, סימן הערת שוליים בכתיב עילי, סמל מטבע שנלקח מגופן חלופי, ותיבות מילים מ-OCR עם רעש גובה לכל מילה — כולם מזיזים מרכזים ביותר מכל סבילות שעוד מפרידה בין שורות סמוכות של טקסט בגודל 10 נקודות בריווח של 12. יחס החפיפה אינו תלוי בגודל: שתי תיבות על קו בסיס אחד חופפות על גובה ה-x המשותף שלהן לא משנה מה עושים החלקים העליונים והתחתונים, ושתי תיבות על שורות סמוכות לא חופפות בכלל

קל להחיל את אותו כלל גם מחוץ לחילוץ הטבלאות. 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 ל-Delphi