Extract glyphs and sort by reading order

Extract glyphs and sort by reading order

The PDF format is designed to be a finished document after all the editing is done. It is intended for printing, viewing and interacting (such as clicking links or filling fields), but not for further editing. However the extraction of text is possible, although with a few caveats, which this article will address.

Text extraction: default ordering

The primary purpose of PDF is the presentation of information to humans and not to provide computer readable information. Most PDF documents do not contain layout information such as columns, tables and paragraphs. The textual content is basically just a collection of glyphs, each with its own X and Y coordinates. To extract text this collection must be ordered somehow, usually by sorting the glyphs on their X and Y position. This assumes that the glyphs on the top-left are the first and on the bottom right are the last in the reading order. This is how PDFKit.NET orders the glyphs as returned by page.Glyphs by default:

Document document = new Document(fileIn);
Page page = document.Pages[0];
GlyphCollection glyphs = page.Glyphs;
glyphs.Sort();
foreach (Glyph glyph in glyphs)
{
   // glyphs sorted from top-left to bottom right here...
}
Dim document As New Document(fileIn)
Dim page As Page = document.Pages(0)
Dim glyphs As GlyphCollection = page.Glyphs
glyphs.Sort()
		' glyphs sorted from top-left to bottom right here...
For Each glyph As Glyph In glyphs
Next

In most cases, this gives the expected result. This fails however in case of superscript text like this:

Superscript1

The problem here is that in both the text ‘abc’ and ‘xyz’ are sorted first on their vertical position. So what we get as result is:

Superscript2

Although ‘abc’ comes after ‘superscript’ in the reading order, it is returned first.

Text extraction: custom ordering

To address this problem we can write a custom sorter that is used this way:

Document document = new Document(fileIn);
Page page = document.Pages[0];
GlyphCollection glyphs = page.Glyphs;
var glyphSorter = new SortGlyphs();
glyphs.Sort(glyphSorter, true);
…
            Dim document As New Document(fileIn)
            Dim page As Page = document.Pages(0)
            Dim glyphs As GlyphCollection = page.Glyphs
            Dim glyphSorter = New SortGlyphs()
            glyphs.Sort(glyphSorter, True)

The implementation of SortGlyphs:

internal class SortGlyphs : IGlyphComparer
{
  private int minimalPercentageForGlyphsToOverlapVertically = 40; // in percents

  public struct glyphArea
  {
    public float X;
    public float Y;
    public float Width;
    public float Height;
    public bool  HasIllegalValue;
  }

  // Find out whether glayp A or B should come first in the output
  public int Compare(Glyph glyphA, Glyph glyphB)
  {
    var areaA = getGlyphArea(glyphA);
    var areaB = getGlyphArea(glyphB);

    // default compare result:
    // If nothing special and not about on the same Y position, return:
    //   1 if glyph A is positioned higher than glyph B, meaning A is first
    //  -1 if glyph A is below glyph B
    var compare = (areaA.Y < areaB.Y) ? 1 : -1; // default: -1 = a < b, 1 = a > b 

    // Below, we account for characters with a negative height. Usually, this 
    // means that the characters are upside down. Just make sure that these characters
    // are considered smaller than the rest, and equal amongst themselves.
    if (areaA.HasIllegalValue)
    {
      compare = (areaB.HasIllegalValue) ? 0 : -1;
    }
    else if (areaA.HasIllegalValue)
    {
      compare = 1;
    }
    else 
    {
      // If here, the glyphs can be compared by their X and Y position,
      // First look if the glyphs are about on the same height
      // by checking if there is any overlap...
      var yOverlapTop = Math.Min(areaA.Y + areaA.Height, areaB.Y + areaB.Height);
      var yOverlapBottom = Math.Max(areaA.Y, areaB.Y);
      if (yOverlapTop > yOverlapBottom)
      {
        // Found that A and B have at least a bit of a vertical overlap: 
        // Now check if there is a a minimal amount to overlap or that they are just 
        // touching each other.
        // Calculate the overlap in percents of the shortest one, in this way it is
        // more likely to match the sub- and superscript glyphs with the rest of the line 
        var yOverlap = yOverlapTop - yOverlapBottom;
        var yOverlapPercent = 100.00 * (yOverlap / Math.Min(areaA.Height, areaB.Height));
        if (yOverlapPercent > this.minimalPercentageForGlyphsToOverlapVertically)
        {
          // Overlapping enough: take a look at the x-position and mark the most
          // left sided first
          compare = (areaA.X > areaB.X)         ?  1 : // a > b
                    (areaA.X < areaB.X)         ? -1 : // a < b
                    (areaA.Width > areaB.Width) ?  1 : // a > b
                    (areaA.Width < areaB.Width) ? -1 : // a < b
                                                   0 ; // a == b
        }
      }
    }
    return compare;
  }

  // Get the area around the glyph, possibly changed for special characters
  private static glyphArea getGlyphArea(Glyph glyph)
  {
    var area = new glyphArea()
    {
      X = glyph.BottomLeft.X,
      Y = glyph.BottomLeft.Y,
      Width = glyph.TopRight.X - glyph.TopLeft.X,
      Height = glyph.TopRight.Y - glyph.BottomRight.Y,
      HasIllegalValue = false
    };
    area.HasIllegalValue = (area.Height < 0) || (area.Width < 0);

    // This gives a possibily to tweak the dimensions of some special characters
    // like the underscore '_'. 
    if (glyph.Characters.Length == 1)
    {
      switch (glyph.Characters[0])
      {
        case '_': //underscore
          float dY = (float)(glyph.TopLeft.Y - glyph.BottomLeft.Y);
          dY *= 0.4f; //the correction will be 40%, so 60% (height) will be left.
          break;
      }
    }
    return area;
  }
}
Friend Class SortGlyphs
        Implements IGlyphComparer
        Private minimalPercentageForGlyphsToOverlapVertically As Integer = 40
        ' in percents
        Public Structure glyphArea
            Public X As Single
            Public Y As Single
            Public Width As Single
            Public Height As Single
            Public HasIllegalValue As Boolean
        End Structure

        ' Find out whether glayp A or B should come first in the output
        Public Function Compare(glyphA As Glyph, glyphB As Glyph) As Integer Implements IGlyphComparer.Compare
            Dim areaA = getGlyphArea(glyphA)
            Dim areaB = getGlyphArea(glyphB)

            ' default compare result:
            ' If nothing special and not about on the same Y position, return:
            '   1 if glyph A is positioned higher than glyph B, meaning A is first
            '  -1 if glyph A is below glyph B
            Dim compare__1 = If((areaA.Y < areaB.Y), 1, -1)
            ' default: -1 = a < b, 1 = a > b 
            ' Below, we account for characters with a negative height. Usually, this 
            ' means that the characters are upside down. Just make sure that these characters
            ' are considered smaller than the rest, and equal amongst themselves.
            If areaA.HasIllegalValue Then
                compare__1 = If((areaB.HasIllegalValue), 0, -1)
            ElseIf areaA.HasIllegalValue Then
                compare__1 = 1
            Else
                ' If here, the glyphs can be compared by their X and Y position,
                ' First look if the glyphs are about on the same height
                ' by checking if there is any overlap...
                Dim yOverlapTop = Math.Min(areaA.Y + areaA.Height, areaB.Y + areaB.Height)
                Dim yOverlapBottom = Math.Max(areaA.Y, areaB.Y)
                If yOverlapTop > yOverlapBottom Then
                    ' Found that A and B have at least a bit of a vertical overlap: 
                    ' Now check if there is a a minimal amount to overlap or that they are just 
                    ' touching each other.
                    ' Calculate the overlap in percents of the shortest one, in this way it is
                    ' more likely to match the sub- and superscript glyphs with the rest of the line 
                    Dim yOverlap = yOverlapTop - yOverlapBottom
                    Dim yOverlapPercent = 100.0 * (yOverlap / Math.Min(areaA.Height, areaB.Height))
                    If yOverlapPercent > Me.minimalPercentageForGlyphsToOverlapVertically Then
                        ' Overlapping enough: take a look at the x-position and mark the most
                        ' left sided first
                        ' a > b
                        ' a < b
                        ' a > b
                        ' a < b
                        ' a == b
                        compare__1 = If((areaA.X > areaB.X), 1, If((areaA.X < areaB.X), -1, If((areaA.Width > areaB.Width), 1, If((areaA.Width < areaB.Width), -1, 0))))
                    End If
                End If
            End If
            Return compare__1
        End Function

        ' Get the area around the glyph, possibly changed for special characters
        Private Shared Function getGlyphArea(glyph As Glyph) As glyphArea
            Dim area = New glyphArea() With {
            .X = glyph.BottomLeft.X,
            .Y = glyph.BottomLeft.Y,
            .Width = glyph.TopRight.X - glyph.TopLeft.X,
            .Height = glyph.TopRight.Y - glyph.BottomRight.Y,
            .HasIllegalValue = False
        }
            area.HasIllegalValue = (area.Height < 0) OrElse (area.Width < 0)

            ' This gives a possibily to tweak the dimensions of some special characters
            ' like the underscore '_'. 
            If glyph.Characters.Length = 1 Then
                Select Case glyph.Characters(0)
                    Case "_"c
                        'underscore
                        Dim dY As Single = CSng(glyph.TopLeft.Y - glyph.BottomLeft.Y)
                        dY *= 0.4F
                        'the correction will be 40%, so 60% (height) will be left.
                        Exit Select
                End Select
            End If
            Return area
        End Function
    End Class

This sorter considers glyphs to be on the same line if they overlap 40% or more.

Multiple columns

As stated beFore, the text in a PDF document is just an unordered collection of glyphs. Extracting the text becomes much more difficult if the layout of the PDF is not ordered in a very simple way, e.g. the PDF can have multi columns. We do not try to solve these kind of problems, but we help how to recognize columns.