bbox-align 0.2.5

A python library that reorders bounding boxes generated by OCR engines into the correct reading order

bbox-align

bbox-align is a Python library that reorders bounding boxes generated by OCR engines into logical lines and correct reading order for downstream document processing tasks. Even when documents have folds, irregular spacing, or distortions.

Installation

pip install bbox-align

Prereqs: Python 3.8+

Usage

import bbox_align

vertices = [
    [ (0, 15), (10, 15), (10, 25), (0, 25) ], # world
    [ (15, 15), (15, 15), (15, 25), (15, 25) ], # :)
    [ (0, 0), (10, 0), (10, 10), (0, 10) ], # hello
]
words = ['world', ':)', 'hello']
boundaries = [ (0, 0), (25, 0), (25, 50), (0, 50) ]

lines = bbox_align.process(vertices, boundaries)

for line in lines:
    sentence_list = [words[idx] for idx in line]
    print(' '.join(sentence_list))

'''
$ python3 run.py
hello
world :)
'''

Examples

MOD Pizza 26902 92nd Ave NW Suite A Stanwood , WA 98292 Phone [phone] 5/19/2019 4:06:54 PM Order Id : AABT4HN6ACCM # 77 - HERE Draft Beer ( 2 @ 4.97 ) $ 9.94 Fountain Drink ( 1602 ) $ 2.17 MOD Pizza $ 8.67 Mini MOD $ 6.67 Sub Total $ 27.45 Sales Tax $ 2.53 Order Total $ 29.98 Visa $ 29.98 Tip : $ 3.59 Card # : **** ***** 3352 819160

Orange & Rockland 390 West Route 59 Pike County Light & Power Co. Spring Valley NY 10977-5300 Page 1 of 2 Rockland Electric Company 1-877-434-4100 www.oru.com Your next Meter If you have questions JOAN SMITH Reading will be about this bill , call 24 ORCHARD LN Feb 27 toll free 1-877-434-4100 - SMALL CITY NY 19999-0000 or go to www.oru.com ELECTRIC RESIDENTIAL - DELIVERY BILLING DATE 01/29/09 Jan 29 reading ( Actual ) 61114 BILLING SUMMARY Dec 30 reading ( Actual ) -60597 ACCOUNT NUMBER Total Usage KWH 30 Days 517 67890-12345 Last Bill $ 422.80 Delivery Charges Payment - EFT Basic Service Charge $ 9.09 First 250 KWH 5.6920 each 14.23 01/12/09 -422.80 Next 267 KWH 44880 each 11.98 Service Charges Energy Cst Adj 517 KWH -0.045000 -23 € Electric 89.62 RDM Adjustment 517 KWH 0.16400 85 Gas 266.67 SBC / RP5 Cha 517 KWH 0.388970 201 Government surcharges - Delivery .76 TOTAL Total Delivery Charges $ 38.69 AMOUNT DUE $ 356.29 Avg . Temp This Period 25 F Total Supplier Charge 50.93 Same Period Last Year 33F CURRENT ELECTRIC CHARGES $ 89.62 ELECTRIC USAGE : MONTHLY 820 GAS FIRM TRANS RES SPACE HEATING - DELIVERY 615 410 Jan 29 reading ( Actual ) 5004 205 Dec 30 reading ( Actual ) -4846 0 KWH JFMAMJJASON DJ AVG Total Usage CCF 30 Days 158 2008 2009 * spacings computed differently

Workings

Two bounding boxes are considered inline if the y-coordinate of one box's vertical center lies within the top and bottom bounds of the other box. i.e d <= D/2. To prevent skewed bounding boxes from being inline, the slope difference must be within 5°.

If there are distortions, the above check fails. So we can find the Point of intersection (poi) instead and compute a harmonic mean score using

1. (d1 + d2)/2
2. absolute vertical distance between m1 and m2.

This gives a balanced vertical score. A bounding box is inline with another bounding box with lowest score.

Any overlaps within a line are resolved also using harmonic mean score of perpendicular distance and vertical distance between overlapping bounding boxes.

Debugging

To dig deeper into what bounding boxes are inline, you can use bbox_align.process_with_meta_info to get meta related informations and pretty print them using bbox_align.pprint_matrix

import bbox_align
# For the above example
lines, inlines, passthroughs, pois = bbox_align.process_with_meta_info(vertices, endpoints)

bbox_align.pprint_matrix(matrix=passthroughs, words=words, idxs=[51, 52, 57, 58])
'''
          Sales     Tax       $    2.53
  Sales    True    True   False   False
    Tax    True    True   False   False
      $   False   False    True    True
   2.53   False   False    True    True
'''
# points of intersections
bbox_align.pprint_matrix(matrix=pois, words=words, idxs=[51, 52, 57, 58])
'''
                                Sales                Tax                  $               2.53
             Sales               None      (26.9, 357.2)   (204.17, 347.35)   (200.76, 347.54)
               Tax      (26.9, 357.2)               None   (218.02, 348.89)   (215.73, 348.99)
                 $   (204.17, 347.35)   (218.02, 348.89)               None   (240.37, 351.37)
              2.53   (200.76, 347.54)   (215.73, 348.99)   (240.37, 351.37)               None
'''
bbox_align.pprint_matrix(matrix=inlines, words=words, idxs=[51, 52, 57, 58])
'''
          Sales     Tax       $    2.53
  Sales    True    True   False   False
    Tax    True    True   False    True
      $   False   False    True    True
   2.53   False    True    True    True
'''
# Using DFS, we group these idxs into a line

FAQs

1. Does this library do document layout analysis? No. Document layout analysis is an upstream task. bbox-align only groups bounding boxes within a layout into logical lines.

2. Does this library compute spacings as well? Not yet. But with enough requests and interests, I can implement it.