Διόρθωση false positives πινάκων PDF από justified text

Το PDFium Component έκδοση 3.117.0 σταματά να αναφέρει justified παραγράφους ως whitespace-aligned tables απαιτώντας κάθε όριο στήλης να είναι κατακόρυφος διάδρομος χωρίς text σε καμία γραμμή που χωρίζει, προσπερνώντας λέξεις που διεκδικούνται ήδη από ruled grid, και συναρμολογώντας text κελιών με κατακόρυφη επικάλυψη αντί για απόσταση κέντρων glyph-box. Και οι τρεις αλλαγές ζουν μέσα στο ExtractTables και ExtractDocumentTables και δεν χρειάζονται καμία επιλογή

Η αναφορά που το ξεκίνησε δεν είχε λαμπρότητα. Μια σελίδα δελτίου τύπου χωρίς κανένα πίνακα γύριζε από το ExtractTables με whitespace table 5x4, confidence άνετα πάνω από το default MinConfidence του 0.5, και τα κελιά κρατούσαν τμήματα συνηθισμένου body text. Μια φόρμα εισαγωγής έκανε το ίδιο με τις παραγράφους δοκιμίων της και παρήγαγε 3x4 και 5x3. Και τα δύο έγγραφα είχαν στηθεί justified. Η προφανής απάντηση είναι να ρυθμίσεις τα κατώφλια, και το χρήσιμο μάθημα από αυτή την έκδοση είναι ότι το tuning δεν μπορεί να το διορθώσει, επειδή ο κανόνας που ρυθμιζόταν έθετε τη λάθος ερώτηση

uses
  PDFium;

// Έλεγχος regression: απαρίθμησε κάθε whitespace table σε έγγραφο ώστε σελίδα
// που ξέρεις ότι είναι μόνο πεζογραφία να επαληθευτεί καθαρή
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 text μοιάζει με πίνακα;

Μια justified παράγραφος μοιάζει με πίνακα επειδή μια justified γραμμή είναι σειρά λέξεων χωρισμένων με κενά που το layout engine τέντωσε, και μόλις ένα τεντωμένο κενό φτάσει το MinColumnGap ο detector δεν έχει κανέναν row-local τρόπο να το ξεχωρίσει από διαχωριστικό στήλης. Η στρατηγική whitespace στο PDFium Component ομαδοποιεί word boxes σε οπτικές γραμμές, σχίζει κάθε γραμμή σε ομάδες λέξεων όπου η οριζόντια απόσταση από την προηγούμενη λέξη είναι τουλάχιστον MinColumnGap (12 πόντοι από προεπιλογή), και δέχεται πίνακα όταν τουλάχιστον δύο διαδοχικές γραμμές επαναλαμβάνουν τουλάχιστον MinColumns αγκυρώσεις ομάδων left-aligned εντός AlignmentTolerance, που είναι 3 πόντοι. Εκείνος είναι ο κανόνας που περιγράφει το overview ανίχνευσης πινάκων, και για γνήσιο ευθυγραμμισμένο πίνακα είναι ακριβώς σωστός

Τώρα εφάρμοσέ το σε είκοσι γραμμές justified πεζογραφίας 10 πόντων. Κάθε γραμμή τεντώνεται ως το ίδιο δεξί περιθώριο, οπότε μια γραμμή που τελειώνει με μακριά λέξη ανοίγει τα εσωτερικά της κενά, και σε παράγραφο με λίγες κοντές γραμμές μερικά από εκείνα τα κενά διασχίζουν τους 12 πόντους. Δύο διαδοχικές γραμμές χρειάζονται μόνο ένα τεντωμένο κενό η καθεμία, προσγειωμένο εντός 3 πόντων από την ίδια θέση X, για να σχηματίσουν υποψήφιο δύο γραμμών, δύο στηλών. Σε αρκετές γραμμές αυτό δεν είναι κακή τύχη· είναι πιθανότητα που πλησιάζει τη βεβαιότητα, και το 5x4 στο δελτίο τύπου ήταν απλώς η εκτέλεση όπου τέσσερα τέτοια κενά ευθυγραμμίστηκαν πάνω σε πέντε γραμμές

Κάθε κατώφλι ανταλλάσσει μια κατηγορία εγγράφου με άλλη. Ανεβάζοντας το MinColumnGap στους 20 πόντους χάνεις τις συμπαγείς στήλες πυκνών οικονομικών reports, που είναι η ακριβής περίπτωση για την οποία το default είχε ήδη χαμηλώσει. Ανεβάζοντας το MinRows στο 3 απορρίπτεις πραγματικούς πίνακες δύο γραμμών και απλώς χαμηλώνεις τις πιθανότητες για μεγάλες παραγράφους. Σφίγγοντας το AlignmentTolerance κάτω από 3 πόντους σπάς word boxes προερχόμενα από OCR, του οποίου τα αριστερά άκρα τρέμουν περισσότερο από αυτό. Το σήμα επιπέδου γραμμών είναι πράγματι αμφίσημο, οπότε το fix πρέπει να έρθει από σήμα που οι γραμμές δεν κουβαλάνε από μόνες τους

Τι κάνει ένα όριο στήλης πραγματικό;

Πραγματικό όριο στήλης είναι μια κατακόρυφη λωρίδα της σελίδας που μένει άδεια σε κάθε γραμμή που χωρίζει. Ένας πίνακας έχει μία ανάμεσα σε κάθε ζευγάρι στηλών εκ κατασκευής, επειδή τα κελιά τοποθετήθηκαν απέναντι σε κοινές θέσεις X. Μια justified παράγραφος τεντώνει τα κενά λέξεων της σε διαφορετικές οριζόντιες θέσεις σε κάθε γραμμή, οπότε καμία λωρίδα δεν επιβιώνει από την τομή περισσότερων από μία-δυο γραμμών. Το PDFium Component τεστάρει πλέον ακριβώς αυτό: αφού οι ομάδες λέξεων του υποψηφίου έχουν ανατεθεί σε στήλες αγκυρώσεων, για κάθε ζευγάρι γειτονικών στηλών παίρνει, σε κάθε γραμμή που έχει περιεχόμενο και στα δύο κελιά, το διάστημα από το δεξιότερο άκρο των λέξεων του αριστερού κελιού έως το αριστερότερο άκρο των λέξεων του δεξιού κελιού, τέμνει εκείνα τα διαστήματα πάνω στις γραμμές, και απορρίπτει ολόκληρο τον υποψήφιο αν η τομή είναι στενότερη από MinColumnGap επί 0.5, που είναι 6 πόντοι στο default

Δύο λεπτομέρειες μετράνε. Γραμμές όπου το ένα από τα δύο κελιά είναι κενό δεν ψηφίζουν, οπότε πίνακας με κενό κελί, ή header που απλώνεται σε λιγότερες στήλες από το σώμα, εξακολουθεί να περνά. Και το πλάτος του διαδρόμου προκύπτει από το MinColumnGap αντί να εκτεθεί ως ξεχωριστή επιλογή, επειδή τα δύο περιγράφουν το ίδιο φυσικό πράγμα: το κενό που αφήνει ένας σχεδιαστής ανάμεσα στις στήλες. Η λογική είναι αρκετά μικρή για να την αναπαραγάγεις αν χτίζεις πάνω σε raw word boxes αντί για το table API, και το δείγμα παρακάτω κατοπτρίζει τον έλεγχο μέσα στο component:

uses
  Math, PDFium;

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

// Γυρνά False όταν οποιοδήποτε ζευγάρι γειτονικών στηλών στερείται κατακόρυφου
// διαδρόμου χωρίς text πλάτους τουλάχιστον 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;

Γιατί οι ruled tables εξάγονταν δύο φορές;

Οι ruled tables εξάγονταν δύο φορές επειδή το πέρασμα whitespace έβλεπε κάθε λέξη της σελίδας, συμπεριλαμβανομένων των λέξεων που το ruled πέρασμα είχε ήδη τοποθετήσει σε grid, και ένας καθαρός ruled πίνακας είναι εκ κατασκευής ταυτόχρονα και τέλεια ευθυγραμμισμένος whitespace πίνακας. Ένας έλεγχος επικάλυψης απορρίπτει ήδη whitespace υποψήφιο του οποίου τα όρια κάλυπταν πάνω από το μισό υπάρχοντος πίνακα, αλλά υποψήφιος που συνδύαζε τις κάτω γραμμές του πίνακα με μερικές ευθυγραμμισμένες γραμμές text από κάτω του μπορούσε να πέσει κάτω από εκείνη την αναλογία και να επιβιώσει ως δεύτερος, ελαφρώς μεγαλύτερος πίνακας που αιμορραγούσε στον γείτονά του. Το ExtractTables αφαιρεί πλέον εκείνες τις λέξεις πριν τρέξει το πέρασμα whitespace. Μια λέξη πετιέται όταν το σημείο κέντρο της βρίσκεται μέσα στα όρια οποιουδήποτε πίνακα παρήγαγε το ruled πέρασμα· το κέντρο χρησιμοποιείται αντί για πλήρη περιέλευση ώστε λέξη που καβαλάει border κατά κλάσμα πόντου να ακολουθεί τον πίνακα στον οποίο οπτικά ανήκει. Η στρατηγική whitespace δουλεύει μετά μόνο πάνω στις ελεύθερες λέξεις, που σημαίνει επίσης ότι μικρός unruled πίνακας καθισμένος απευθείας κάτω από ruled ανιχνεύεται με τα δικά του προσόντα αντί να λιώσει με το grid από πάνω του

Γιατί το «Purpose of Request:» βγήκε ως «of Purpose Request:»;

Οι λέξεις βγήκαν ανακατεμένες επειδή τα word boxes που χτίζει το PDFium Component είναι ενώσεις bounding boxes των glyphs, και το «of» δεν έχει descender ενώ το «Purpose» και το «Request:» έχουν. Το FPDFText_GetCharBox επιστρέφει το σφιχτό box του μελανιού του glyph στον χώρο σελίδας, όχι box πεπλατυσμένο ως την ascent και descent της γραμματοσειράς, και το word box είναι η ένωση των boxes των χαρακτήρων του. Μια λέξη χωρίς descenders είναι επομένως κοντύτερη και το κατακόρυφο κέντρο της κάθεται ψηλότερα, κατά 2 έως 3 πόντους στη φόρμα στη συγκεκριμένη περίπτωση. Η παλιά ρουτίνα text κελιών ταξινομούσε λέξεις πρώτα κατά center Y, με ανοχή 1 πόντου για «ίδια γραμμή», και μετά κατά αριστερό άκρο· το «of» πέρασε την ανοχή, ταξινομήθηκε ως δική του γραμμή πάνω από τις άλλες, και εκπέμφθηκε πρώτο

Αυτό δεν είναι ιδιομορφία του PDFium τόσο όσο συνέπεια του πώς το PDF τοποθετεί text. Το ISO 32000-1 §9.2.2 και §9.4.4 ορίζουν την τοποθέτηση glyphs ως οριζόντια μετατόπιση κατά μήκος της baseline στον χώρο text, και οι μόνοι κατακόρυφοι μετρικοί που κουβαλάει το αρχείο είναι ανά γραμματοσειρά: οι εγγραφές Ascent, Descent, και FontBBox του font descriptor στο §9.8.1. Τίποτα στο αρχείο δεν λέει ότι δύο glyphs μοιράζονται γραμμή· αυτό πρέπει να συναχθεί από τη γεωμετρία, και τα σφιχτά glyph boxes που κάνουν την επισήμανση επιλογής να δείχνει σωστή, όπως περιγράφεται στο text line selection με PDFium char boxes, είναι η λάθος είσοδος για σύγκριση απόστασης κέντρων

Το fix στην έκδοση 3.117.0 αλλάζει την ερώτηση από «πόσο μακριά είναι τα κέντρα» σε «πόσο επικαλύπτονται τα boxes κατακόρυφα». Το text κελιού συναρμολογείται πρώτα ομαδοποιώντας τις λέξεις του κελιού σε οπτικές γραμμές, όπου λέξη εντάσσεται σε γραμμή όταν η κατακόρυφη επικάλυψή της με τα τρεχούμενα όρια της γραμμής είναι τουλάχιστον 25 τοις εκατό του μικρότερου από τα δύο ύψη, μετά ταξινομώντας κάθε γραμμή με insertion sort κατά αριστερό άκρο, και μετά ενώνοντας τις γραμμές με αλλαγή γραμμής. Το «Purpose» και το «of» επικαλύπτονται σε όλο το x-height, που είναι πολύ περισσότερο από 25 τοις εκατό του κοντύτερου box, οπότε προσγειώνονται στην ίδια γραμμή και ταξινομούνται κατά X όπως πρέπει

Ομαδοποίησε text γραμμές με επικάλυψη, όχι με απόσταση κέντρων

Ο κανόνας που αξίζει να πάρεις από αυτό το bug είναι γενικός: οποιοδήποτε PDF text-layout code αποφασίζει «ίδια γραμμή» συγκρίνοντας κατακόρυφα κέντρα με σταθερή ανοχή θα αποτύχει πάνω σε πραγματικές γραμματοσειρές, και η αποτυχία είναι σιωπηλή· τίποτα δεν σφάλει, οι λέξεις απλώς βγαίνουν με λάθος σειρά. Τα μικτά descenders είναι ο ηπιότερος trigger. Ένα bold label 12 πόντων δίπλα σε τιμές 10 πόντων, ένας superscript δείκτης υποσημείωσης, ένα σύμβολο νομίσματος ζωγραφισμένο από fallback γραμματοσειρά, και word boxes OCR με θόρυβο ύψους ανά λέξη μετακινούν όλα κέντρα περισσότερο από κάθε ανοχή που εξακολουθεί να χωρίζει γειτονικές γραμμές 10 πόντων σε 12 πόντων leading. Ο λόγος επικάλυψης είναι αμετάβλητος μεγέθους: δύο boxes στην ίδια baseline επικαλύπτονται πάνω στο κοινό τους x-height ό,τι κι αν κάνουν ascenders και descenders τους, και δύο boxes σε γειτονικές γραμμές δεν επικαλύπτονται καθόλου

Ο ίδιος κανόνας εφαρμόζεται εύκολα έξω από την εξαγωγή πινάκων. Το TPdf.PageWordBoxes επιστρέφει κάθε λέξη της ενεργής σελίδας με το ορθογώνιο της στον χώρο σελίδας, οπότε η ομαδοποίηση μιας σελίδας σε οπτικές γραμμές είναι κοντός loop:

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;

Τι αλλάζει για υπάρχοντες callers, και πού είναι τα όρια

Το νόημα εκείνου του snippet είναι το κατηγόρημα, όχι το loop· για οτιδήποτε πέρα από γρήγορο dump, ξεκίνα από το structured text model, που κουβαλάει ήδη blocks, γραμμές, και πηγή reading-order, όπως καλύπτεται στο structured PDF text extraction με reading order. Οι υπάρχοντες table callers παίρνουν και τις τρεις διορθώσεις χωρίς να αγγίξουν τις επιλογές τους. Το κατώφλι διαδρόμου είναι καρφωμένο στο μισό του MinColumnGap, η στρατηγική whitespace κρατά το δάπεδο δύο γραμμών της ακόμα κι όταν το MinRows θέτεται στο 1 (που η ruled στρατηγική δέχεται πια), και το φιλτράρισμα λέξεων ruled-first είναι απεριόριστο όποτε και οι δύο στρατηγικές είναι ενεργές. Στο σύνολο 13 εγγράφων που χρησιμοποιήθηκε για την έκδοση, το πέρασμα whitespace είχε γυρίσει προηγουμένως 34 τμήματα και false positives δίπλα σε 9 ruled tables· μετά την έκδοση δεν γυρίζει κανένα, και ο αριθμός ruled tables ανέβηκε σε 41, αν και το μεγαλύτερο μέρος της ανόδου προέρχεται από την ίδια έκδοση που δίδαξε τον ruled detector να διαβάζει borders σχεδιασμένα ως γεμάτα ορθογώνια, που είναι ξεχωριστή ιστορία

Τα τίμια όρια: το corridor test χρειάζεται τουλάχιστον μία γραμμή με περιεχόμενο και από τις δύο πλευρές ενός ορίου για να απορρίψει οτιδήποτε, οπότε υποψήφιος δύο γραμμών του οποίου τα δύο τεντωμένα κενά τυχαίνουν εντός 6 πόντων μεταξύ τους εξακολουθεί να περνά. Εκείνο είναι στενή συγκυρία αντί για την σχεδόν-βεβαιότητα που ήταν πριν, αλλά πεζογραφικά βαριά έγγραφα χωρίς κανένα γνήσιο πίνακα δύο γραμμών μπορούν να το κλείσουν θέτοντας MinRows στο 3. Το left-aligned ανομοιόμορφο text δεν ήταν ποτέ το πρόβλημα και δεν επηρεάζεται. Και το PDF εξακολουθεί να μην έχει table object· το ISO 32000-1 §14.8.4.3 ορίζει element δομής Table, αλλά μόνο Tagged PDF το κουβαλάει, οπότε για όλα τα άλλα το grid παραμένει συμπέρασμα από τη γεωμετρία, και η τιμή confidence πάνω σε κάθε TPdfTable υπάρχει επειδή το συμπέρασμα αξίζει σκορ

Η εξαγωγή tables, το structured text, και τα word boxes διαβάζουν όλα από το ίδιο page model σε Delphi, C++Builder και Lazarus· το πλήρες API, συμπεριλαμβανομένου του TPdfTableExtractionOptions και του demo TableExtractionLab που κυκλοφορεί δίπλα του, περιγράφεται στη σελίδα PDFium Component for Delphi