How to define the badness of a river?

Question

I've written an algorithm to try and detect rivers in paragraphs and it actually detects quite a lot when I run it. Some of them are clearly false positives, but there are others that are indeed aligned spaces on consecutive lines. Here are some, colored in green in the following picture:

When are rivers really problematic and/or ugly? Are there rivers in this example that are worth fixing?

What are the parameters (and their importance) to qualify the "badness" of a river, and how could they be calculated?

As an additional question, there doesn't seem to be a standard definition of a river. Defining a river properly would surely help to define the parameters that make it bad. How would you define a river?

Answer 1

After reading lockstep's and Lev's answers, here is my own take. It seems to me that there's 4 main factors that make a river bad:

1. Its orientation: The straighter, the worse;
2. Its width: the larger, the worse;
3. The constancy of its width: the more constant, the worse;
4. The length: the longer, the worse.

From this, I guess I could try to improve the algorithm by checking the following:

1. Find overlapping spaces (which I already do) on as many lines as possible (instead of just 3);
2. Try to approximate the river by a linear regression and retrieve a regression factor;
3. Measure the width of each node, and calculate mean μ and standard deviation σ.
4. Based on all this, calculate the badness based on:
   • the regression factor (the closest to a straight line, the worse), which might be some kind of MSE,
   • the mean width μ divided by the standard space width ω (the larger -- compared to the standard word space, the worse),
   • the standard deviation of width σ (the smaller, the worse),
   • the length (number of lines n, the longer, the worse).

The badness could be something like (with a factor α to normalize it):

where

to set the maximum badness to 10000.

I suggest to square σ and MSE since they appear to be more important factors than μ and n.

With this formula, we would have:

• b tends towards 10000 when μ tends towards infinity (maximum badness for very large spaces);
• b tends towards 10000 when n tends towards infinity (maximum badness for a lot of lines);
• b tends towards 0 when μ tends towards 0 (smaller spaces reduce badness);
• b tends towards 0 when n tends towards 0 (smaller amount of lines reduce badness);
• b tends towards 10000 when σ tends towards 0 (monospaced text increases badness);
• b tends towards 10000 when MSE tends towards 0 (perfectly aligned spaces are sure to be really bad);
• b tends towards 0 when σ tends towards infinity (different spaces tend to reduce badness);
• b tends towards 0 when MSE tends towards infinity (unaligned spaces do not lead to real rivers).

My definition of a river would then be:

an accidental series of aligned spaces of constant width on 3 or more consecutive lines.

Edit: As Bruno noted, α and ω are not really used in the calculation since we fix the maximum badness to 10000 anyway. Also the algorithm can be simplified by not calculating μ since nμ is simply the sum of all widths:

with:

Edit 2: I'm actually considering to use something like S+ σ + MSE in the denominator instead of S * (σ * MSE)^2. The reasons for that are:

• When σ is zero (perfectly identical spaces), that doesn't make the river necessarily bad, it still depends on MSE (the alignment);
• When MSE is zero (perfectly aligned spaces), that doesn't make the river necessarily bad, it still depends on the size of spaces;
• I'm not sure squares are necessary for σ and MSE (but experiments will have to tell) since they're already squared differences.

As a little progress note, here is Lev's excellent example converted to LuaTeX + fontspec:

\documentclass{article}
\usepackage{fontspec}
\setmainfont[Ligatures=TeX]{Minion Pro}
\usepackage{microtype}
\usepackage[draft,rivers]{impnattypo}
\begin{document}
\noindent\parbox{8.5cm}{\hspace{15pt}
eget niis non lobero at conseyquat lacus. Vestibulum eg
Lorem ipsum dolor sit amew jonsectetun ad PL Wilson elit
Pellentesque nec turpis nisv Ac lobortis ballacus.  Ut fringil
nis, non ipsum gravida sep `doltrices' odio dictub.  Tam id l
fermintum dolor. Pail NT cabitant morbi istiqleith  vibendi
senectus et netus erepaw dalesuada fames ic turpak  wegest
Nam ac nunc vel nique.  aliquam dictum etat magna.  Thats
risus neque. `Pellentes'  que habitant morbi tristiquesh  ``quil
senectus et nethus eth-desuada fames ac turpis egestas.}
\end{document}

and ran into my current algorithm:

It detects quite a few things... except the 2 mighty rivers, which don't actually overlap on 3 consecutive lines... There's still quite some work to do...

As for the overlapping issue, it seems to me that the bigger the interline space, the more space between spaces is possible. If lines are very close, spaces really have to overlap in order to create a river, but if lines are very loose, then spaces that are actually distant horizontally can create a diagonal river, too.

Update: I considered that rivers are below 45° (with a vertical line), and in this case, the overlap can be taken + or - the line height. So the new algorithm considers that spaces do not necessarily have to overlap strictly vertically, but the overlap can be + or - the distance between the two lines. The result with Lev's example is this:

Next step will be to analyze on more than 3 lines (as I still do) and define and apply a river badness to eliminate false positive rivers. This seems to be a bit harder since I have to define a list object in Lua to chain the nodes that are part of the river, but I'm slowly getting there.

Answer 2

I think to do it properly, you really need to take into account the shapes of the glyphs. Some glyphs, such as .,-' are very light. Others, such as ATVWvwLkbhdpq"lean" to the left or the right. I don't think the two rivers in this example could be spotted without taking into account glyph shapes:

EDIT: To respond to Raphink's comment, here is the same example, with \usepackage{microtype}. I don't think it looks significantly better (I wouldn't expect it to, since this effect does not depend on margin protrusion or font expansion):

It's also true that computer modern has especially wide interword spaces and even wider intersentence spaces, as I discussed in this answer. If I make the same example using MinionPro, which has much narrower spaces, then it does look a little less offensive, but still pretty bad:

I think the best way to find rivers has to involve rasterizing the paragraph and then doing some kind of image processing on the resulting bitmap.

Here's the source for a MinionPro based example (I didn't save the others as I was going along):

\documentclass{article}
\usepackage{MinionPro}
\usepackage{microtype}
\begin{document}
\noindent\parbox{8.2cm}{\hspace{15pt}
eget niis non lobero at conseyquat lacus. Vestibulum eg
Lorem ipsum dolor sit amew jonsectetun ad PL Wilson elit
Pellentesque nec turpis nisv Ac lobortis ballacus.  Ut fringil
nis, non ipsum gravida sep `doltrices' odio dictub.  Tam id l
fermintum dolor. Pail NT cabitant morbi istiqleith  vibendi
senectus et netus erepaw dalesuada fames ic turpak  wegest
Nam ac nunc vel nique.  aliquam dictum etat magna.  Thats
risus neque. `Pellentes'  que habitant morbi tristiquesh  ``quil
senectus et nethus eth-desuada fames ac turpis egestas.}
\end{document} 

EDIT 2

Here is a similar example, with letters that "lean" replaced by ones that do not. Replace the previous paragraph with:

\noindent\parbox{8.2cm}{\hspace{15pt}
eget niis non lobero at conseyquat lacus. Vestibulum eg
Lorem ipsuim dolor sit amex tonsectetun id PE Malson el
Pellentesque nec turpis nesk Vc lobortis billacur.  Dt fringi
nis, non ipsum gravida seq `boltrices' odio dictud.  Eam id l
fermintum dolor. Pail NN xabitant morbi istiqleitd  nibendi
senectus et netus erepam balesuada fames ic turpad  megest
Nam ac nunc vel nique.  fliquam dictum etat magna.  Khats
risus neque. `Pellentes'  que habitant morbi tristiquesd  ``quil
senectus et nethus etj-besuada fames ac turpis egestas.}

To get the following non-rivers (or at least, much less offensive):

Answer 3

I suggest to assign a "badness" value to rivers according to the following definition/formula:

• A river occurs whenever two or more successive text lines feature white space that overlaps horizontally. (It seems that Raphink's detection algorithm adheres to this definition.)

• The "badness" of a river may be calculated as

  (overlap / word space ) * (no. of text lines)^2 * 250
  

According to this formula, a three-line river with a width of 50% of a normal word space would be assigned a badness value of 1125, which is about the level where a "fussy" user should start to worry. A river with the same overlap but extending over five text lines would have a badness of 3125, i.e., would be "really problematic". (I just made up these parameters to put something forward for discussion.)

EDIT: In your example, I reckon that the leftmost river (quite small, but extending over four lines) would be assigned the highest badness according to my suggested formula. I predict a badness value of about 1500 to 2000, i.e., something that is only worth fixing if the fix doesn't break other things (e.g., leads to underfull hboxes or lots of hyphens).

Answer 4

If the routines are to be integrated with TeX or a TeX-like system optimization should preferably be done at the paragraph level to enable faster execution.

Consider the text below given by Bishop in his post.

The characteristics of the 'rivers' is an advancing front. If the x,y positions of the endings of words is known a line (not necessarily straight - snake shapes can also be integrated mathematically) can be fitted through them, say from 30-60 degrees. If the line hits a word, say on the third line then the test fails and should not be considered a river.

At its extreme at zero angle one would get a figure such as that given by Holkner and the objective function becomes easier to optimize and measure:

Holkner in his paper used a number of functions to optimize pages. For rivers he just measured the sum of the grayed areas above, which he attempted to minimize. A multipass approach using paragraphs would have been much simpler and faster. Also he did not consider rivers at angles.

A more naive algorithm can be to consider the interword space as made of two parts. A fixed part and a part that is determined randomly. Suppose TeX has calculated the space between two words to be 0.8em one could then change this size to a fixed part say 0.80 x 0.8 and the remainder to be determined using a random function. Any negative or positive remainder gets added randomly to the other interword spaces. This would tend to 'shake' the words a bit out of position and may remove most of the rivers (it is though guaranteed by definition to fail in certain cases). Such an algorithm can also be made as an "on a demand macro", i.e., only apply it manually if you spot it.

Answer 5

I doubt this is practical, but just in case... but the problem is a lot easier (conceptually, not computationally), and closer to what the eye does, if detection is performed on the page image - in pixel space, not character space. Then it would "just" require blurring the image a little, and then searching for long lines that are somewhat vertical and are lighter than a threshold value. A minimum width might be needed, but if lucky, an appropriate blur will make it unnecessary.