Merging angled text OCR into lines

user_2781958 0
Viewed 532

I have a text box detection algorithm that outputs word-level detections. Here's an example: enter image description here

So the output is a list of boxes in the form (x1_i,y1_i,x2_i,y2_i) indicating the bottom-left and top-right coordinates. I'd like to find a simple decent baseline algorithm to merge these boxes into lines. So the desired output would be:

["Hey how are you?" , "I'm great!"]

I've seen a few questions similar to this, but they are primarily about straight (uni-directional) text, e.g.: Merge the Bounding boxes near by into one

My thoughts on this are to calculate vectors from the centroid of each box, and then doing merging of boxes, based on closeness and near-same direction. I'm wondering if there are any such algorithms already out there? The corner cases that I'd like to try and address are:

  1. Multiple angles of text.

  2. Non-overlapping boxes (like the [I'm] [great!] ones).

  3. Crossing texts at different angles (like the two lines above).

I'd like to find a such a quick-and-easy baseline algorithm using python.

ocr text algorithm
1 Answers

This is the simplest algorithm meeting your criteria that I can think of.

Define a function score(b1, b2) that reflects how likely it is that the word in b1 precedes the word in b2, with lower scores being better (e.g., 0 means that the right edge of b1 is the same as the left edge of b2). For each box b, define pred(b) to be the box b' minimizing score(b', b), and define succ(b) to be the box b' minimizing score(b, b'). Form a graph on the bounding boxes with arcs b->b' such that succ(b) = b' and pred(b') = b. This graph is the disjoint union of some number of simple paths. These are your lines.

I don't know the best way to define score, but one possibility is to define score(b1, b2) = f(distance(midpoint of b1's right side, midpoint of b2's right side) / max(b1's height, b2's height)) + g(angular distance(b1's angle, b2's angle)), where f and g are increasing functions (I'd start the experiments with f and g being linear).

Edit: it occurs that the word bounding box algorithm may only give you a reliable orientation modulo a half rotation. In this case, define score so that it's lower when the two boxes are likelier to precede/succeed one another, form a directed graph where each box has an arc to each of the two boxes with which it has the lowest scores, throw away arcs with no reciprocal arc, form an undirected graph with an edge for each arc pair. The latter graph consists of a disjoint union of paths and cycles. You'll have to figure out what to do with the cycles and how to orient the paths.

user_21446690
Related