# How to define the badness of a river?

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?

-
There's quite a few questions labeled typography here and I've found that when I asked typography questions on Graphic Design, I hardly got constructive answers (the truth is, Graphic Design is quite dead compared to here). –  ℝaphink Sep 20 '11 at 20:12
I upvoted because detection of rivers is an essential condition for avoiding them. Such questions are helpful for developing TeX's typographic capabilities, so it's ontopic. See also here on chat. –  Stefan Kottwitz Sep 20 '11 at 20:21
While I've not an answer, I concur that this is in topic. The perception of rivers is rather subjective, in many cases, and depends on many factors. For example, the blackness of the type and the leading. –  egreg Sep 20 '11 at 20:42
@Mico: Good eye ;-) The two missing spaces in the 5-lines river is probably due to a bug in my code, probably a special node like a penalty or a kern that prevents me from properly calculating the width of the space between "Dieu" and "car". –  ℝaphink Sep 21 '11 at 13:11
I asked about an image-processing solution to river detection on the new signal processing stackexchange site here. –  Lev Bishop Oct 5 '11 at 18:16

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

-
Don't use this definition without "accidental" or sth. similar - sometimes spaces are on purpose. –  topskip Sep 21 '11 at 16:41
@Patrick: right, fixed. –  ℝaphink Sep 21 '11 at 16:42
Actually, it seems your formula gives 10000 for every river with \frenchspacing. –  Bruno Le Floch Sep 21 '11 at 19:33
I'd like to propose two slight modifications of Raphink's working definition of a river. First, I don't think the interword spaces have to be of constant width in order to be noticeable and objectionable. I'd therefore suggest the term *exceeding a threshold width, where the threshold would be something like 60% of the average interword space. Second, I'd say that the space taken up by commas and periods should also count towards the interword space, because those two glyphs are so small as to "disappear" optically when a river starts flowing. Just some thoughts to consider... –  Mico Sep 21 '11 at 21:24
I agree @Mico and I think your comment somehow reinforces Lev's answer. My plan is to add a protrusion penalty factor to σ (measuring identical spaces) and MSE (measuring alignment) which would add a penalty for special glyphs (like punctuation or characters like ATVWvwLkbhdpq as mentioned by Lev. –  ℝaphink Sep 21 '11 at 23:27

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
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):

-
Well isn't this just grand? Time to give up and cry. –  JohnJamesSmith Sep 21 '11 at 5:06
That seems right. I would say that what makes such a river problematic is also that spaces have a constant (quite large) width, which is why using microtype (such as in my example) reduces the problem (you may have rivers, but since the spaces are slightly different from one line to another, it doesn't look really bad to the eye). –  ℝaphink Sep 21 '11 at 6:03
@Raphink See edit. –  Lev Bishop Sep 21 '11 at 14:18
Thanks. Can I find the source of your examples somewhere to try and reproduce these rivers? –  ℝaphink Sep 21 '11 at 14:31
And thanks for the encouragement @JohnJamesSmith :-) –  ℝaphink Sep 21 '11 at 15:59

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.

-
Lua lets you use a hook after the paragraph is rendered and access the boxes as nodes. Types of nodes and positions can be retrieved, so the analysis can be done numerically. I'm not sure a graphical detection would be easier (and it would certainly be more time consuming). –  ℝaphink Sep 21 '11 at 14:40
Do you have access at that time to any info about letter shape? That's the only reason you might want to consider graphical. –  Ed Staub Sep 21 '11 at 14:56
What do you mean by letter shape exactly. I have access to infos about the kind of node (glyph, glue, penalty, etc.), the character of the glyph, the dimensions of the node... –  ℝaphink Sep 21 '11 at 15:03
The idea to blur the image of a paragraph is also advocated by James Felici in The Complete Manual of Typography, 2nd ed. 2011, p. 164. Upon blurring, any rivers do "jump out" at you much more easily -- although in the paragraph example he provides, the river is so crass and obvious that blurring is not even required... –  Mico Sep 21 '11 at 21:18
@EdStaub: TeX has no information on letter shapes, it only sees the bounding boxes of the letters (traditionally from the tfms). Maybe you can get information about letter shapes from OpenType fonts, but I doubt it. –  Martin Schröder Apr 5 '12 at 7:58

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.

-
Thanks for the input. As a matter of fact, my current algorithm already works at a paragraph level somehow (if I understand what you mean), since it processes the lines after the paragraph rendering and finds overlapping spaces, the goal now being to assign a badness to detected rivers (or did I misunderstood what you mean by paragraph level?). I don't think Holkner's approach is really the best way. As you mentioned it already, it doesn't address oblique rivers (LevBishop gave a great example of them) and it doesn't consider the individual badness of a river. –  ℝaphink Sep 21 '11 at 18:26
@Raphink Yes Holkner's approach does not work for rivers such as those shown by Lev Bishop. Also note I have seen rivers in my own texts that actually look like rivers, i.e., they snake around and they are very profound (sadly all gone by adding a word here and there). I personally think one should give the random algorithm a go, I don't know if I made myself very clear though! Why I am advocating the latter is that this is the most common way to "destroy" rivers, just add a bit of a kern here and there and they are gone, so effectively the random function should does this. –  Yiannis Lazarides Sep 21 '11 at 18:44
The random algorithm? –  ℝaphink Sep 21 '11 at 18:46
@Raphink This is my own idea. Think of the spaces as made of boxes that have two parts. The total width of the box is determined by TeX. You fix a portion of it and you have a variable part which you reduce or increment by a small fraction randomly. The difference from the size of the original box, you distribute again randomly over all the interword spaces of the paragraph and you iterate. Many things in nature look better if they have minor variations and I think text falls into such a category. –  Yiannis Lazarides Sep 21 '11 at 18:53
Ah, you mean to use a random algorithm to fix rivers. For now, I'm already trying to detect them and display them with a badness value (a bit like overfull lines). –  ℝaphink Sep 21 '11 at 18:55

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 hbox`es or lots of hyphens).

-
I like the idea. I could definitely print the badness in the logs as done for (under|over)full boxes. Should I then only display the rivers above a given badness? Should I change the color when the badness increases? When you say "word space", you mean the normal TeX setting for this paragraph? When you mean overlap, do you mean the mean overlap on the 3 analyzed lines (I analyze lines 3 by 3 currently)? –  ℝaphink Sep 20 '11 at 22:31
To be clear, I currently consider that rivers are problematic if they're at least on 3 lines, so I analyze from the 3rd line of a paragraph, comparing with lines n-1 and n-2. The 4 lines river you see to the left of the paragraph is the superposition of 2 detected rivers, the analysis having been done for lines 3 and 4 (or respectively lines 7 and 8 in the paragraph). –  ℝaphink Sep 20 '11 at 22:39
"Overlap" could also be overlapping whitespace of 4 or more lines. I'm aware that a "broader" river with, say, 3 lines could be part of a "smaller" river with, say, 5 lines -- in such a case, I'd be interested in the river with maximum badness (likely the one with 5 lines). –  lockstep Sep 20 '11 at 22:39
Just a note: the overlap badness doesn't really detect oblique rivers, only straight ones. –  ℝaphink Sep 20 '11 at 22:45
I'll probably have to rethink the algorithm to detect rivers on more than 3 consecutive lines. I'm afraid such an algorithm would have a potentially much greater time complexity than the current one, since it would mean analyzing the whole paragraph for each space found. –  ℝaphink Sep 20 '11 at 22:48