bbox-align 0.2.8
A python library that reorders bounding boxes generated by OCR engines into the correct reading order
Requires Python: >=3.8
Keywords: OCR, bounding boxes, document processing, lines, reorder

# 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

```py
import bbox_align

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

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

<table>
  <tr>
    <td>
      <img src="https://raw.githubusercontent.com/doctor-entropy/bbox-align/main/images/receipt.jpg" alt="receipt" style="min-width:300px;" width="300" />
    </td>
  </tr>
  <tr>
    <td>
      <pre style="background-color:#f4f4f4; padding:10px; border:1px solid #ddd; border-radius:5px; font-family:monospace; font-size:14px; line-height:1.5;">
MOD Pizza
26902 92nd Ave NW
Suite A
Stanwood , WA 98292
Phone 360.205.9680
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
      </pre>
    </td>
  </tr>
</table>
<table>
  <tr>
    <td>
      <img src="https://raw.githubusercontent.com/doctor-entropy/bbox-align/main/images/bill.jpg" alt="bill" style="width:400px;"/>
    </td>
  </tr>
  <tr>
    <td>
      <pre style="background-color:#f4f4f4; padding:10px; border:1px solid #ddd; border-radius:5px; font-family:monospace; font-size:14px; line-height:1.5;">
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
      </pre>
* spacings computed differently
    </td>
  </tr>
</table>

## 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°`.

<img src="https://raw.githubusercontent.com/doctor-entropy/bbox-align/refs/heads/main/images/parallel.png" alt="parallel" style="width:1000px;"/>

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.

<img src="https://raw.githubusercontent.com/doctor-entropy/bbox-align/refs/heads/main/images/poi.png" alt="poi" style="width:1000px;"/>

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`

```py
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.