رفع مثبت‌های کاذب جدول در PDF از متن justified در Delphi

کامپوننت PDFium نسخهٔ 3.117.0 دست از گزارش دادن پاراگراف‌های justified به‌عنوان جدول‌های هم‌ترازشده با فضای سفید برمی‌دارد، با الزامی کردن این‌که هر مرز ستون یک کریدور عمودی بدون متن در هر سطری که جدا می‌کند باشد، با رد کردن کلمه‌هایی که یک شبکهٔ خط‌دار از قبل ادعایشان را کرده، و با سرهم کردن متن سلول بر پایهٔ هم‌پوشانی عمودی به‌جای فاصلهٔ مرکز جعبه‌های گلیف. هر سه تغییر داخل ExtractTables و ExtractDocumentTables زندگی می‌کنند و هیچ optionی نمی‌خواهند

گزارشی که این کار را شروع کرد هیچ جلوهٔ خاصی نداشت. یک صفحهٔ اطلاعیهٔ مطبوعاتی که هیچ جدولی نداشت از ExtractTables با یک جدول فضای سفید 5x4 برمی‌گشت، با اطمینانی راحت بالای MinConfidence پیش‌فرض برابر 0.5، و سلول‌هایش تکه‌هایی از متن اصلی معمولی بودند. یک فرم پذیرش همین کار را با پاراگراف‌های مقاله‌ای‌اش کرد و یک 3x4 و یک 5x3 تولید کرد. هر دو سند justified چیده شده بودند. واکنش بدیهی تنظیم آستانه‌هاست، و درس مفید این انتشار این است که تنظیم نمی‌تواند درستش کند، چون قاعده‌ای که تنظیم می‌شد داشت سؤال غلطی می‌پرسید

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;

چرا متن justified شبیه یک جدول به نظر می‌رسد؟

یک پاراگراف justified شبیه جدول به نظر می‌رسد چون یک سطر justified ردیفی از کلمه‌هاست که با گاترهایی جدا شده‌اند که layout engine کشیده‌شان داده، و وقتی یک گاتر کشیده‌شده به MinColumnGap برسد، آشکارساز هیچ راه سطر-محلی‌ای ندارد تا آن را از یک جداکنندهٔ ستون تشخیص بدهد. استراتژی فضای سفید در کامپوننت PDFium جعبه‌های کلمه را به سطرهای دیداری گروه می‌کند، هر سطر را به گروه‌های کلمه می‌شکند هر جا که فاصلهٔ افقی تا کلمهٔ قبلی حداقل MinColumnGap باشد (پیش‌فرض 12 پوینت)، و یک جدول را وقتی می‌پذیرد که حداقل دو سطر پشت سر هم حداقل MinColumns لنگر گروه چپ-تراز را در محدودهٔ AlignmentTolerance که 3 پوینت است تکرار کنند. همین قاعده‌ای است که در مرور کلی تشخیص جدول توصیف شده، و برای یک جدول واقعاً هم‌ترازشده دقیقاً درست است

حالا آن را روی بیست سطر نثر justified ده-پوینتی اعمال کن. هر سطر به همان حاشیهٔ راست کشیده می‌شود، پس سطری که با یک کلمهٔ بلند تمام می‌شود فاصله‌های داخلی‌اش را باز می‌کند، و در پاراگرافی با چند سطر کوتاه بعضی از آن فاصله‌ها از 12 پوینت می‌گذرند. دو سطر پشت سر هم فقط به یک گاتر کشیده‌شده هر کدام نیاز دارند که در فاصلهٔ 3 پوینتی همان موقعیت X بیفتد تا یک نامزد دو-سطر و دو-ستون بسازند. در تعداد سطر کافی این بدشانسی نیست؛ احتمالی است که به قطعیت نزدیک می‌شود، و آن 5x4 روی اطلاعیهٔ مطبوعاتی صرفاً همان رشته‌ای بود که چهار گاتر از این نوع در پنج سطر هم‌تراز شدند

هر آستانه یک دستهٔ سند را با دستهٔ دیگری معامله می‌کند. بالا بردن MinColumnGap به 20 پوینت ستون‌های فشردهٔ گزارش‌های مالی متراکم را از دست می‌دهد، که دقیقاً همان حالتی است که پیش‌فرض از قبل برایش پایین آورده شده بود. بالا بردن MinRows به 3 جدول‌های واقعی دو-سطری را دور می‌اندازد و فقط شانس پاراگراف‌های بلند را کم می‌کند. سخت‌تر کردن AlignmentTolerance زیر 3 پوینت جعبه‌های کلمهٔ برآمده از OCR را می‌شکند، که لبه‌های چپشان بیش از آن لرزش دارند. سیگنال سطح-سطر واقعاً مبهم است، پس fix باید از سیگنالی بیاید که سطرها خودشان حملش نمی‌کنند

چه چیزی یک مرز ستون را واقعی می‌کند؟

یک مرز ستون واقعی یک نوار عمودی از صفحه است که در هر سطری که جدا می‌کند خالی می‌ماند. یک جدول طبق ساختارش بین هر جفت ستون یکی دارد، چون سلول‌ها در برابر موقعیت‌های X مشترک چیده شده‌اند. یک پاراگراف justified فاصله‌های کلمه‌اش را در هر سطر در موقعیت‌های افقی متفاوتی می‌کشد، پس هیچ نواری از اشتراک بیش از یک یا دو سطر جان سالم به در نمی‌برد. کامپوننت PDFium حالا دقیقاً همین را می‌آزماید: بعد از این‌که گروه‌های کلمهٔ نامزد به ستون‌های لنگر نسبت داده شدند، برای هر جفت ستون مجاور، در هر سطری که در هر دو سلول محتوا دارد، بازهٔ میان راست‌ترین لبهٔ کلمه‌های سلول چپ تا چپ‌ترین لبهٔ کلمه‌های سلول راست را می‌گیرد، آن بازه‌ها را در طول سطرها اشتراک می‌گیرد، و کل نامزد را اگر آن اشتراک از MinColumnGap ضربدر 0.5 که پیش‌فرضش 6 پوینت است باریک‌تر باشد رد می‌کند

دو جزئیات مهم‌اند. سطرهایی که یکی از دو سلولشان خالی است رأی نمی‌دهند، پس جدولی با یک سلول خالی، یا سرصفحه‌ای که ستون‌های کمتری از بدنه پوشش می‌دهد، باز هم پاس می‌شود. و پهنای کریدور از MinColumnGap مشتق می‌شود نه این‌که به‌عنوان یک option جداگانه عرضه شود، چون این دو یک چیز فیزیکی را توصیف می‌کنند: همان گاتری که یک طراح بین ستون‌ها می‌گذارد. این منطق آن‌قدر کوچک است که اگر روی جعبه‌های کلمهٔ خام بسازی نه روی API جدول، بازتولیدش کنی، و نمونهٔ زیر همان بررسی داخل کامپوننت را بازتاب می‌دهد:

uses
  Math, PDFium;

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

// وقتی هر جفت ستون مجاور یک کریدور عمودی بدون متن به عرض
// حداقل MinColumnGap / 2 در سطرهایی که از آن استفاده می‌کنند نداشته باشد False برمی‌گرداند
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 مرتب می‌کرد، با یک تلورانس 1 پوینتی برای «همان سطر»، و بعد با لبهٔ چپ؛ "of" از آن تلورانس بیرون افتاد، به‌عنوان سطر خودش بالای بقیه مرتب شد، و اول بیرون داده شد

این بیشتر نتیجهٔ نحوهٔ قرار دادن متن توسط PDF است تا یک عجیب بودن PDFium. ISO 32000-1 §9.2.2 و §9.4.4 قرار دادن گلیف را به‌عنوان جابه‌جایی افقی در طول خط پایه در فضای متن تعریف می‌کنند، و تنها متریک‌های عمودی که فایل حمل می‌کند به ازای هر فونت‌اند: ورودی‌های Ascent و Descent و FontBBox در توصیفگر فونت در §9.8.1. هیچ‌چیز در فایل نمی‌گوید که دو گلیف یک سطر را شریک‌اند؛ این باید از هندسه استنتاج شود، و همان جعبه‌های چسبان گلیف که برجسته‌سازی انتخاب را درست نشان می‌دهند، چنان‌که در انتخاب سطر متنی با جعبه‌های char در PDFium توصیف شده، ورودی غلطی برای مقایسهٔ فاصلهٔ مرکزهاست

fix در نسخهٔ 3.117.0 سؤال را از «مرکزها چقدر از هم دورند» به «جعبه‌ها چقدر عمودی هم‌پوشانی دارند» عوض می‌کند. متن سلول با این ترتیب سرهم می‌شود: اول کلمه‌های سلول را به سطرهای دیداری گروه کن، جایی که یک کلمه به سطری می‌پیوندد وقتی هم‌پوشانی عمودی‌اش با مرزهای جاری آن سطر حداقل 25 درصد کوچک‌ترِ آن دو ارتفاع باشد؛ بعد هر سطر را با لبهٔ چپ به‌صورت درجی مرتب کن؛ بعد سطرها را با یک شکست خط به هم بچسبان. "Purpose" و "of" در تمام ارتفاع x هم‌پوشانی دارند، که بسیار بیشتر از 25 درصد جعبهٔ کوتاه‌تر است، پس روی همان سطر می‌افتند و همان‌طور که باید با X مرتب می‌شوند

سطرهای متن را با هم‌پوشانی گروه کن، نه با فاصلهٔ مرکز

قاعده‌ای که ارزش دارد از این باگ بگیری کلی است: هر کد چیدمان متن PDF که «همان سطر» را با مقایسهٔ مرکزهای عمودی در برابر یک تلورانس ثابت تصمیم بگیرد روی فونت‌های واقعی می‌شکند، و شکست بی‌صدا است: هیچ‌چیز خطا نمی‌دهد، کلمه‌ها فقط با ترتیب غلط بیرون می‌آیند. دنباله‌های مخلوط ملایم‌ترین محرک است. یک برچسب توپر 12 پوینتی کنار مقدارهای 10 پوینتی، یک نشانگر پانویس بالانویس، یک نماد ارز که از یک فونت جایگزین کشیده شده، و جعبه‌های کلمهٔ OCR با نویز ارتفاع در هر کلمه، همه مرکزها را بیش از هر تلورانسی جابه‌جا می‌کنند که باز هم سطرهای مجاور متن 10 پوینتی با leading 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
  // کلمه‌ها را به ترتیب content stream برمی‌گرداند، که تضمین‌شده دیداری نیست
end;

برای فراخوان‌های موجود چه عوض می‌شود، و مرزها کجاست

نکتهٔ آن قطعهٔ کد همان predicate است، نه حلقه؛ برای هر چیزی بیش از یک dump سریع، از مدل متن ساخت‌یافته شروع کن، که از قبل بلوک‌ها و سطرها و یک منبع ترتیب خواندن را حمل می‌کند، همان‌طور که در استخراج متن ساخت‌یافتهٔ PDF با ترتیب خواندن پوشش داده شده. فراخوان‌های موجود جدول هر سه تصحیح را بدون دست زدن به optionهایشان می‌گیرند. آستانهٔ کریدور روی نصف MinColumnGap ثابت است، استراتژی فضای سفید کف دوستری‌اش را حتی وقتی MinRows روی 1 گذاشته شود نگه می‌دارد (که استراتژی خط‌دار حالا می‌پذیردش)، و فیلتر کردن کلمه‌های خط‌دار-اول هر وقت هر دو استراتژی فعال باشند بی‌قیدوشرط است. در مجموعهٔ نمونهٔ 13 سندی که برای این انتشار استفاده شد، پاس فضای سفید قبلاً 34 قطعه و مثبت کاذب کنار 9 جدول خط‌دار برمی‌گرداند؛ بعد از انتشار هیچ‌کدام را برنمی‌گرداند، و شمار جدول‌های خط‌دار به 41 رسید، هرچند بیشتر آن رشد از همان انتشاری می‌آید که به آشکارساز خط‌دار یاد داد حاشیه‌های کشیده‌شده به‌صورت مستطیل پرشده را بخواند، که داستان جدایی است

مرزهای صادقانه: آزمون کریدور برای رد کردن هر چیزی حداقل به یک سطر با محتوا در دو طرف یک مرز نیاز دارد، پس یک نامزد دوستری که دو گاتر کشیده‌شده‌اش تصادفاً در فاصلهٔ 6 پوینتی هم بیفتند باز هم پاس می‌شود. این یک تصادف باریک است نه آن نزدیکی-به-قطعیتی که قبلاً بود، ولی سندهای پرنثر که هیچ جدول واقعی دوستری ندارند می‌توانند با گذاشتن MinRows روی 3 این را ببندند. متن چپ-تراز نامرتب هرگز مشکل نبود و تحت تأثیر نیست. و PDF همچنان هیچ شیء جدولی ندارد؛ ISO 32000-1 §14.8.4.3 یک عنصر ساختاری Table تعریف می‌کند، ولی فقط Tagged PDF آن را حمل می‌کند، پس برای هر چیز دیگری شبکه یک استنتاج از هندسه می‌ماند، و مقدار confidence روی هر TPdfTable وجود دارد چون استنتاج لایق یک امتیاز است

استخراج جدول و متن ساخت‌یافته و جعبه‌های کلمه همه از همان مدل صفحه در Delphi و C++Builder و Lazarus می‌خوانند؛ API کامل، شامل TPdfTableExtractionOptions و دموی TableExtractionLab که کنارش عرضه می‌شود، در صفحهٔ کامپوننت PDFium برای Delphi توصیف شده