Determine table structure in pdf using whitespace between coordinates

Question

I'm looking to see if there are any better / faster ways of identifying table structures on a page without gridlines.

The text is extracted from the file and the coordinates of each block of text are stored in a dataframe. For the sake of this snippet, this has already been generated and has yielded the dataframe below. This is ordered top to bottom, left to right in reading order.

The bounding box (x,y,x1,y1) is represented below as (left,top,left1,top1). Middle is the mid-point between left and left1 and left_diff is the gap between current rows starting x position (left) and previous rows finishing x1 position (left1.shift()). Width is the left to left1 size.

    top     top1    left    middle  left1   left_diff   width
0   78.0    126     54      62.0    70.0    NaN     16.0
1   78.0    123     71      94.0    118.0   1.0     47.0
2   78.0    126     125     136.0   147.0   7.0     22.0
3   78.0    123     147     215.0   283.0   0.0     136.0
4   167.0   199     54      130.0   206.0   -229.0  152.0
5   167.0   187     664     701.0   739.0   458.0   75.0
6   186.0   204     664     722.0   780.0   -75.0   116.0
7   202.0   220     664     751.0   838.0   -116.0  174.0
8   212.0   234     54      347.0   641.0   -784.0  587.0
9   212.0   237     664     737.0   811.0   23.0    147.0
10  232.0   254     54      347.0   641.0   -757.0  587.0
11  232.0   253     664     701.0   738.0   23.0    74.0
12  232.0   253     826     839.0   853.0   88.0    27.0
13  253.0   275     54      137.0   220.0   -799.0  166.0
14  268.0   286     664     717.0   770.0   444.0   106.0
15  285.0   310     54      347.0   641.0   -716.0  587.0
16  285.0   303     664     759.0   855.0   23.0    191.0
17  301.0   330     54      347.0   641.0   -801.0  587.0
18  301.0   319     664     684.0   704.0   23.0    40.0
19  301.0   319     826     839.0   853.0   122.0   27.0
20  328.0   350     54      347.0   641.0   -799.0  587.0

....... etc......

My method here is to group by an x coordinate (taking into account the text could be justified left, centred or to the right), search for ant other points which are close (within a tolerance of 5 pixels in this snippet). This gives me my columns.

Then, for each column identified, look to see where the rows are by looking for the points at which the gap between rows is over a certain a threshold. Here, we take the indexes of the points where the text should break and generate index pairs. By taking the max and min points, we can generate a bounding box around this cell.

Then, I look to see if there are other boxes located on the same x coordinate and store this in a table list.

Finally, form pairs from the tables and look at the index distance between each of the items in the table list. As the indexes should run sequentially, this should equal 1. If it doesn't, this indicates that the table doesn't continue.

import itertools

def pairwise(splits):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(splits, 2)
    next(b, None)
    return list(zip(a, b))

def space_sort(df):
    groups = df.groupby('page')
    pages = {i:j[['top','top1','left','middle','left1']] for i,j in groups}
    cols = ['left','middle','left1']
    boxes = {}
    for page in pages:
        rows = {}
        c_df = pages[page]
        min_x = min(c_df.left)
        gaps = c_df.loc[df.left_diff>5]
        
        #  value count on left, middle and left1 values so we can deal with text justification.
        counts = {'left':[], 'middle':[], 'left1':[]}
        [counts[col].append(gaps[col].unique()) for col in cols if (gaps[col].value_counts()>2).any()]
        
        if len(counts['left'])>0:
            counts['left'][0] = np.insert(counts['left'][0], 0, int(min_x))

        #  search c_df for other points close to these x values.
        for col in cols:
            if len(counts[col])>0:
                for x in counts[col][0]:
                    row_spaces = {}
                    matches = c_df.loc[np.isclose(c_df[col],x, atol=5)]
                    left_groups = df_coord.loc[matches.index.values].reset_index()
                    
#           find points where line diff > 5 indicating new row. Get indexes.
                    vert_gaps = left_groups.loc[(left_groups.top - left_groups.top1.shift())>5]                    
                    vert_indexes = vert_gaps.index.values
                    vert_indexes = np.insert(vert_indexes,0,0)
                    vert_indexes = np.append(vert_indexes,len(left_groups))
                    
#           form groups between rows.
                    pairs = pairwise(vert_indexes)
                    for start,end in pairs:
                        box = left_groups.loc[start:end-1]
                        coords = (page, min(box.top),min(box.left),max(box.top1),max(box.left1))
                        boxes[coords]=(list(left_groups.loc[start:end-1,('index')]))

#  Find close boxes by seeing which align on the same x value (either top, centre or bottom)
    
    table = []
    for a, b in itertools.combinations(boxes, 2):

        a_pg, a_top, a_left, a_top1, a_left1 = a
        b_pg, b_top, b_left, b_top1, b_left1 = b
        a_centre = (a_top+a_top1)//2
        b_centre = (b_top+b_top1)//2
        if (np.isclose(a_top, b_top, atol=5)) | (np.isclose(a_centre, b_centre, atol=5)) | (np.isclose(a_top1, b_top1, atol=5)):
            table.append([boxes[a],boxes[b]])
    
#  Table list contains two lists of indexes of rows which are close together. 
#  As ordered, the indexes should be sequential.
#  If difference between one pair and next is 1, sequential. If not, reset rows

    t = (pairwise(table))
    row = 0
    for i in t:
        if (i[1][0][-1] - i[0][1][-1]) == 1:
            for r in i:
                row+=1
                num = 1
                for col in r:
                    print('indexes', col, 'row',row, 'col',num)
                    num+=1
        else:
            row = 0

Answer 1

The process I would follow to improve the performance of any code would be to go through it in 3 passes,

1. Cleaning - fix those small issues of style, fix bigger issues of semantics, and make the code nice to read.
2. Understanding - find out what we actually want to tell the computer to do.
3. Improving - choosing more appropriate algorithms or data structures for the task(s).

Below I'll walk you through the steps I would take for cleaning up the code.

---

The code as it stands is decent. There are some formatting issues, but the spacing and comments are pretty nice. Good job.

The first thing that stands out is the small inconsistencies. I would suggest using an auto-formatting tool (black, yapf, etc) to find and fix those sort of problems, we really don't need to be wasting mental resources on them. As an example, the spacing between arguments in c_df.loc[np.isclose(c_df[col],x, atol=5)] is not consistent.

While we are discussing tooling, a linter (pep8, pylint, pyflakes, etc) also picks up on some quick things to clean up. I wouldn't worry too much about lint warnings (or scoring), but I would take into account any critical errors it points out. For example, a quick lint highlights unused variables row_spaces = {} and missing imports "undefined name 'np'".

One minor issue which these tools don't catch is extra characters. Often I find code to look a lot nicer if there is less of it. Python is quite good about this, as you don't need brackets around conditions in if statements, or necessarily need square brackets when the generator expression will do.

If you want, here is the code I will base the next clean up on. I've fixed lint errors like unused variables, removed extra parenthesis, and removed comments for brevity. One thing of note is that in left_groups = df_coord.loc[matches.index.values].reset_index() df_coords is undefined, and I don't know what it should actually be.

def pairwise(splits):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(splits, 2)
    next(b, None)
    return list(zip(a, b))


def space_sort(df):
    groups = df.groupby('page')
    pages = {
        i: j[['top', 'top1', 'left', 'middle', 'left1']]
        for i, j in groups
    }
    cols = ['left', 'middle', 'left1']
    boxes = {}
    for page in pages:
        c_df = pages[page]
        min_x = min(c_df.left)
        gaps = c_df.loc[df.left_diff > 5]

        #
        counts = {'left': [], 'middle': [], 'left1': []}
        [
            counts[col].append(gaps[col].unique()) for col in cols
            if (gaps[col].value_counts() > 2).any()
        ]

        if len(counts['left']) > 0:
            counts['left'][0] = np.insert(counts['left'][0], 0, int(min_x))

        #
        for col in cols:
            if len(counts[col]) > 0:
                for x in counts[col][0]:
                    matches = c_df.loc[np.isclose(c_df[col], x, atol=5)]
                    left_groups = df_coord.loc[
                        matches.index.values].reset_index()

                    #
                    vert_gaps = left_groups.loc[(left_groups.top -
                                                 left_groups.top1.shift()) > 5]
                    vert_indexes = vert_gaps.index.values
                    vert_indexes = np.insert(vert_indexes, 0, 0)
                    vert_indexes = np.append(vert_indexes, len(left_groups))

                    #
                    pairs = pairwise(vert_indexes)
                    for start, end in pairs:
                        box = left_groups.loc[start:end - 1]
                        coords = (page, min(box.top), min(box.left),
                                  max(box.top1), max(box.left1))
                        boxes[coords] = list(left_groups.loc[start:end - 1,
                                                             ('index')])

    #
    table = []
    for a, b in itertools.combinations(boxes, 2):
        a_pg, a_top, a_left, a_top1, a_left1 = a
        b_pg, b_top, b_left, b_top1, b_left1 = b
        a_centre = (a_top + a_top1) // 2
        b_centre = (b_top + b_top1) // 2
        if np.isclose(a_top, b_top, atol=5) | np.isclose(
                a_centre, b_centre, atol=5) | np.isclose(
                    a_top1, b_top1, atol=5):
            table.append([boxes[a], boxes[b]])

    #
    t = pairwise(table)
    row = 0
    for i in t:
        if (i[1][0][-1] - i[0][1][-1]) == 1:
            for r in i:
                row += 1
                num = 1
                for col in r:
                    print('indexes', col, 'row', row, 'col', num)
                    num += 1
        else:
            row = 0

---

def pairwise(splits):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."

PEP8 defers to PEP257 for docstring convention. Convention dictates even single line docstrings should have three double quotes.

---

cols = ['left', 'middle', 'left1']

It looks like cols is not modified anywhere else in the code. You can enforce its immutability by changing cols to a tuple. This is useful to prevent accidental edits. The change is rather nice to make, just drop the square brackets.

cols = 'left', 'middle', 'left1'

---

counts = {'left': [], 'middle': [], 'left1': []}
[
    counts[col].append(gaps[col].unique()) for col in cols
    if (gaps[col].value_counts() > 2).any()
]

Modifying counts inside of a list comprehension is quite unexpected. List comprehensions are usually used to construct new lists. I would suggest turning this into a loop.

There is a potential bug waiting to happen. If cols is added to, but counts is forgotten about, an exception will occur due to the missing key.

>>> cols = ['left', 'middle', 'left1', 'middle_y']
>>> counts = {'left': [], 'middle': [], 'left1': []}
>>> counts['middle_y'].append(42.0)

KeyError: 'middle_y'

I think you should link counts to cols with something like counts = {col: [] for col in cols} or make a note beside one of them reminding whoever to do the manual update.

---

counts['left'][0] = np.insert(counts['left'][0], 0, int(min_x))

The docs for np.insert have a see also section (which I find incredibly useful for when you just can't remember the name of a function, but you know a similar one). In it is np.concatentation. While searching for the difference between them, I found two results that suggest you may get better performance by changing the insert to a concatentation^1,2. I don't know how someone would figure this out by themselves, but hey, potentially a free performance win. You just need to measure it now.

---

for col in cols:
    if len(counts[col]) > 0:
        ...

I would much prefer a guard clause here, since the if statement has no else, and since the code inside continues to indent. Less indentation is a good goal. It gives you more room on each subsequent line, and a lot of indentation is an indication of (overly) complicated code³.

for col in cols:
    if len(counts[col]) == 0:
        continue
    ...

---

vert_indexes = vert_gaps.index.values
vert_indexes = np.insert(vert_indexes, 0, 0)
vert_indexes = np.append(vert_indexes, len(left_groups))

I think np.concatenate would be especially useful here, since it would make it clear you are pre-pending and appending to the indexes. It could also perform the task more efficiently as it only needs to make one copy of vert_indexes instead of the two above.

vert_indexes = np.concatenate([0], vert_gaps.index.values, [len(left_groups)])

You should double check this. Without trying it out I don't know if it fails to flatten when it should (and therefore needs axis=None or something).

---

a_pg, a_top, a_left, a_top1, a_left1 = a
b_pg, b_top, b_left, b_top1, b_left1 = b
a_centre = (a_top + a_top1) // 2
b_centre = (b_top + b_top1) // 2
if np.isclose(a_top, b_top, atol=5) | np.isclose(
        a_centre, b_centre, atol=5) | np.isclose(
            a_top1, b_top1, atol=5):

You probably want the short circuiting behaviour that the keyword or provides. I don't see a reason to use the bitwise or instead.

I don't like the unpacking that happens here. If you change the order of packing in coords, it will become outdated here (and vice versa). There is no link between them, so it may silently break. Without good tests you may not notice for a long time. I don't have a solution to this problem, so this is just a "be wary".

On a related note to the unpacking, there is a nice idiom for unused variables. As only a_top, a_top1, b_top, and b_top1, you can reduce the noise by using an underscore to indicate you know about this variable, but don't need it.

The section of code might now look something like this

_, a_top, _, a_top1, _ = a
_, b_top, _, b_top1, _ = b
a_centre = (a_top + a_top1) // 2
b_centre = (b_top + b_top1) // 2
if np.isclose(a_top, b_top, atol=5) or np.isclose(
        a_centre, b_centre, atol=5) or np.isclose(
            a_top1, b_top1, atol=5):
    table.append([boxes[a], boxes[b]])

There is some incongruence in this code. There is a mismatch between using np.isclose (which I would expect to be used for floating point numbers) and // 2 (which I would expect for integers). So, are the variables expected to be floats or integers? Should the integer division (// 2) be floating point division (/ 2), or is np.isclose overkill when abs(a_top - b_top) <= 5 would do?

---

for i in t:
    if (i[1][0][-1] - i[0][1][-1]) == 1:
        for r in i:

This code is not easy to understand at a glance, mostly due to the variable names. Do you have more descriptive names you could use? What are i[1][0] and i[0][1]? Is this just debugging code and can be left out?