"River" detection in text

Question

Over on the TeX stackexchange, we have been discussing how to detect "rivers" in paragraphs in this question.

In this context, rivers are bands of white space that result from accidental alignment of interword spaces in the text. Since this can be quite distracting to a reader bad rivers are considered to be a symptom of poor typography. An example of text with rivers is this one, where there are two rivers flowing diagonally.

There is interest in detecting these rivers automatically, so that they can be avoided (probably by manual editing of the text). Raphink is making some progress at the TeX level (which only knows of glyph positions and bounding boxes), but I feel confident that the best way to detect rivers is with some image processing (since glyph shapes are very important and not available to TeX). I have tried various ways to extract the rivers from the above image, but my simple idea of applying a small amount of ellipsoidal blurring doesn't seem to be good enough. I also tried some Radon Hough transform based filtering, but I didn't get anywhere with those either. The rivers are very visible to the feature-detection circuits of the human eye/retina/brain and somehow I would think this could be translated to some kind of filtering operation, but I am not able to make it work. Any ideas?

To be specific, I'm looking for some operation that will detect the 2 rivers in the above image, but not have too many other false positive detections.

EDIT: endolith asked why I am pursuing a image-processing-based approach given that in TeX we have access to the glyph positions, spacings, etc, and it might be much faster and more reliable to use an algorithm that examines the actual text. My reason for doing things the other way is that the shape of the glyphs can affect how noticeable a river is, and at the text level it is very difficult to consider this shape (which depends on the font, on ligaturing, etc). For an example of how the shape of the glyphs can be important, consider the following two examples, where the difference between them is that I have replaced a few glyphs with others of almost the same width, so that a text-based analysis would consider them equally good/bad. Note, however, that the rivers in the first example are much worse than in the second.

Answer 1

I have thought about this some more, and think that the following should be fairly stable. Note that I have limited myself to morphological operations, because these should be available in any standard image processing library.

(1) Open image with a nPix-by-1 mask, where nPix is about the vertical distance between letters

#% read image
img = rgb2gray('https://i.sstatic.net/4ShOW.png');

%# threshold and open with a rectangle
%# that is roughly letter sized
bwImg = img > 200; %# threshold of 200 is better than 128

opImg = imopen(bwImg,ones(13,1));

(2) Open image with a 1-by-mPix mask to eliminate whatever is too narrow to be a river.

opImg = imopen(opImg,ones(1,5));

(3) Remove horizontal "rivers and lakes" that are due to space between paragraphs, or indentation. For this, we remove all rows that are all true, and open with the nPix-by-1 mask that we know will not affect the rivers we have found previously.

To remove lakes, we can use an opening mask that is slightly larger than nPix-by-nPix.

At this step, we can also throw out everything that is too small to be a real river, i.e. everything that covers less area than (nPix+2)*(mPix+2)*4 (that will give us ~3 lines). The +2 is there because we know that all objects are at least nPix in height, and mPix in width, and we want to go a little above that.

%# horizontal river: just look for rows that are all true
opImg(all(opImg,2),:) = false;
%# open with line spacing (nPix)
opImg = imopen(opImg,ones(13,1));

%# remove lakes with nPix+2
opImg = opImg & ~imopen(opImg,ones(15,15)); 

%# remove small fry
opImg = bwareaopen(opImg,7*15*4);

(4) If we're interested in not only the length, but also the width of the river, we can combine distance transform with skeleton.

   dt = bwdist(~opImg);
   sk = bwmorph(opImg,'skel',inf);
   %# prune the skeleton a bit to remove branches
   sk = bwmorph(sk,'spur',7);

   riversWithWidth = dt.*sk;

(colors correspond to width of river (though color bar is off by a factor of 2)

Now you can get the approximate length of the rivers by counting the number of pixels in each connected component, and the average width by averaging their pixel values.

---

Here's the exact same analysis applied to the second, "no-river" image:

Answer 2

In Mathematica, using erosion and Hough transform:

(*Get Your Images*)
i = Import /@ {"https://i.sstatic.net/4ShOW.png", 
               "https://i.sstatic.net/5UQwb.png"};

(*Erode and binarize*)
i1 = Binarize /@ (Erosion[#, 2] & /@ i);

(*Hough transform*)
lines = ImageLines[#, .5, "Segmented" -> True] & /@ i1;

(*Ready, show them*)
Show[#[[1]],Graphics[{Thick,Orange, Line /@ #[[2]]}]] & /@ Transpose[{i, lines}]

Edit Answering Mr. Wizard's comment

If you want to get rid of the horizontal lines, just do something like this instead (probably someone could make it simpler):

Show[#[[1]], Graphics[{Thick, Orange, Line /@ #[[2]]}]] & /@ 
 Transpose[{i, Select[Flatten[#, 1], Chop@Last@(Subtract @@ #) != 0 &] & /@ lines}]

Answer 3

Hmmm... I guess Radon transform isn't that easy to extract from. (Radon transform basically rotates the image while "looking through it" edge-on. It's the principle behind CAT scans.) The transform of your image produces this sinogram, with the "rivers" forming bright peaks, which are circled:

The one at 70 degrees rotation can be seen pretty clearly as the peak on the left of this plot of a slice along the horizontal axis:

Especially if the text was Gaussian blurred first:

But I'm not sure how to reliably extract these peaks from the rest of the noise. The bright top and bottom ends of the sinogram represent the "rivers" between horizontal lines of text, which you obviously don't care about. Maybe a weighting function vs angle that emphasizes more vertical lines and minimizes the horizontal ones?

A simple cosine weighting function works well on this image:

finding the vertical river at 90 degrees, which is the global maxima in the sinogram:

and on this image finding the one at 104 degrees, though blurring first makes it more accurate:

(SciPy's radon() function is kind of dumb, or I'd map this peak back onto the original image as a line going through the middle of the river.)

But it doesn't find either of the two main peaks in the sinogram for your image, after blurring and weighting:

They're there, but they're overwhelmed by the stuff near the middle peak of the weighting function. With the right weighting and tweaking this method probably could work, but I'm not sure what the right tweaks are. It probably depends on the properties of the scans of the page, too. Maybe the weighting needs to be derived from the overall energy in the slice or something, like a normalization.

from pylab import *
from scipy.misc import radon
import Image

filename = 'rivers.png'
I = asarray(Image.open(filename).convert('L').rotate(90))

# Do the radon transform and display the result
a = radon(I, theta = mgrid[0:180])

# Remove offset
a = a - min(a.flat)

# Weight it to emphasize vertical lines
b = arange(shape(a)[1]) #
d = (0.5-0.5*cos(b*pi/90))*a

figure()
imshow(d.T)
gray()
show()

# Find the global maximum, plot it, print it
peak_x, peak_y = unravel_index(argmax(d),shape(d))
plot(peak_x, peak_y,'ro')
print len(d)- peak_x, 'pixels', peak_y, 'degrees'

Answer 4

I trained a discriminative classifier on the pixels using derivative features (up to 2nd order) on different scales.

My labels:

Prediction on training image:

Prediction on the other two images:

I guess this looks promising and could yield usable results given more training data and maybe smarter features. On the other hand it took me only a few minutes to get these results. You may reproduce the results yourself by using the open source software ilastik . [Disclaimer: I'm one of the main developers.]

Answer 5

(Sorry, this post doesn't come with awesome demonstrations.)

If you wanted to work with information TeX already has (letters and positions), you can manually classify letters and letter pairs as "sloping" in one direction or another. For example, "w" has SW and SE corner slopes, the "al" combo has a NW corner slope, "k" has a NE corner slope. (Don't forget punctuation - a quote followed by a letter that fills the lower half of the glyph box establishes a nice slope; quote followed by q is particularly strong.)

Then, look for occurrences of corresponding slopes on opposite sides of a space - "w al" for a SW-to-NE river or "k T" for a NW-to-SE river. When you find one on a line, see if a similar one occurs, appropriately shifted left or right, on the lines above/below; when you find a run of these, there's probably a river.

Also, obviously, just look for spaces stacked nearly vertically, for the plain vertical rivers.

You can get a little more sophisticated by measuring the "strength" of the slope: how much of the advance box is "empty" due to the slope and thus contributing to the river's width. "w" is fairly small, as it has only a small corner of its advance box to contribute to the river, but "V" is very strong. "b" is slightly stronger than "k"; the gentler curve gives a more visually-continuous river edge, making it stronger and visually wider.