Segmenting page with dense input and disconnected separators

Question

I would like to segment pages of a historic book, which is printed densely and shows disconnected black column separators, see below.

What I would like to arrive at is the following segmentation.

I have been playing with ocropy so far, which makes use of scipy/ndimage. But the tool used is not important, I'm interested in methods (morphology, ...) that can solve this.

Any ideas?

Answer 1

1 Top-down approach

Your problem looks like you'd

1. want to segment horizontally,
2. shrink your segments from the left and right image border,
3. check the number of text columns in each horizontal segment, and then
4. within these segments simply look for the columns.

1.1 – segment horizontally

Laziest approach I could come up with: simply find completely white consecutive runs of lines.

To avoid detecting the whitespace between normal lines of text, have a "safe" boundary for large inter-paragraph space. Below that, check whether the non-white lines below and above roughly have the same length.

1.2 – shrink horizontally

Simply find the outmost left and right columns that contain no black. Crop these and everything beyond them out.

1.3 & 1.4 – check number of columns & vertically segment

I'd go for: find columns in the segment of pure white, approach "safety margins" just like for the horizontal segmentation. If you're left with a 1-3px wide vertical segment, check whether it roughly looks like a vertical line.

Another approach would be to directly search for vertical black lines (i.e. go through columns, count black pixels. If column more than let's say 40% black –> vertical line), or if you have to derotate the images first, anyway, start your whole process prior to 1 with a Hough transform and look for roughly vertical lines close to the center of the image – these would show up as peaks in the Houghes-typical position/angle plane.

2 Bottom-up approach based on content

Another thing I'd try is to logically:

1. Detect letters' and vertical lines' outlines
2. Detect the text lines' outlines (by grouping letter outlines and using vertical lines as boundaries)
3. Detect the paragraphs' outlines (by grouping lines)

2.1 – detect letters

Pretty much: find black pixel, find all directly connected black pixels, find the min and max x and y of these groups, draw red rectangle enclosing them. Repeat for next black pixel. (with "draw red" I pretty much mean "mark this as already processed")

2.1a – detect vertical lines

The same as 2.1, but simply filter the detected rectangles by aspect ratio. Mark as green, or however.

2.2 – detect lines' outlines

Starting from the left, take a symbol outline, find center, move right till you either

1. hit a vertical (green) line or
2. exceed the maximum sensible word distance or
3. hit the image border or
4. hit the next symbol.

In cases 1.–3., mark all found symbols as content of one line. In case 4., add found symbol to line "stack", and repeat.

2.3 Find paragraph outlines

From top left, take a line outline. Go down.

If the next outline you hit has roughly the same start and width, add to lines stack. If not, or you hit a boundary, declare all lines on stack a paragraph, mark processed, take next unprocessed line outline from top, and repeat.

3 Bottom-up approach, whitespace-based

Idea: on black and white input

1. Pick a white pixel
2. Find largest undisturbed white (or red) rectangle enclosing said pixel. If area smaller than threshold, mark green. If larger than threshold, mark red
3. Go back to 1.

The result should pretty much be a red mask, that, when inverted, gives you the segmentation you need.