river detection

river detection

[Ed L Cashin]

Han The Thanh discusses in his thesis several problems that computer
typography systems face.  One problem that no current systems address
is "rivers", visual lines of blank space like this:

     XXXXXXXXX  XXXXXXXXXXXXXX XXXXXXXXX XXXXXXXX
     XXXXXXX   xxXX XXXXXXXX Xxxxx   XXXXXX XXXXX
     XX  XXX   XXXXXXX XXXXXX XXXXX XXXXXXXX XXXX
     XXXXXXX  XXXX XXXXXXX XXXX  XXXXXXXX XXXXXXX
     XXX XX   XXXXXXX XXXXXX XXXXX XXXXXXXX XXXXX
     XXXXX   xxXX XXXXXXXX Xxxxx   XXXXXX XXXXX X
     XXXX   XXX XXXXXXX XXXX  XXXXXXXX XXXXXXX XX

... where there's a river on the left.  Hans has been doing many
experiments combining MetaPost and TeX, where they share more
information about the visual appearance of the typeset text than has
traditionally been available.

Would it be possible to use MP and TeX together in order to detect
rivers?  If so, it would be a computer typesetting first, according to
Thanh's thesis.  :)

-- 
--Ed Cashin                     PGP public key:
  ecashin@coe.uga.edu           http://www.coe.uga.edu/~ecashin/pgp/

Re: river detection

[Hans Hagen]

At 01:45 PM 1/9/01 -0500, Ed L Cashin wrote:
>Han The Thanh discusses in his thesis several problems that computer
>typography systems face.  One problem that no current systems address
>is "rivers", visual lines of blank space like this:
>
>
>     XXXXXXXXX  XXXXXXXXXXXXXX XXXXXXXXX XXXXXXXX
>     XXXXXXX   xxXX XXXXXXXX Xxxxx   XXXXXX XXXXX
>     XX  XXX   XXXXXXX XXXXXX XXXXX XXXXXXXX XXXX
>     XXXXXXX  XXXX XXXXXXX XXXX  XXXXXXXX XXXXXXX
>     XXX XX   XXXXXXX XXXXXX XXXXX XXXXXXXX XXXXX
>     XXXXX   xxXX XXXXXXXX Xxxxx   XXXXXX XXXXX X
>     XXXX   XXX XXXXXXX XXXX  XXXXXXXX XXXXXXX XX
>
>... where there's a river on the left.  Hans has been doing many
>experiments combining MetaPost and TeX, where they share more
>information about the visual appearance of the typeset text than has
>traditionally been available.
>
>Would it be possible to use MP and TeX together in order to detect
>rivers?  If so, it would be a computer typesetting first, according to
>Thanh's thesis.  :)

I must say that my first thought was that you might had a point, but after
half an hour metaposting [playing a bit with picture postprocessing, of
which you can find an example in the metafun manual] i think that, given
that there was a good method, it could as well be done in tex itself, since
tex has as much knowlegde in this respect as metapost, i.e. the boundingbox. 

What i did was (1) converting text into pictures, (2) converting
boundingboxes of chars into matrix points and (3) looking at the result.
Maybe some matrix guru could program an ananalyzer but my math is to weak
for that. 

I think [but thanh may disagree] that grayness is something perceptual and
rivers are things recognized by our eyes and brain at a quite low level,
not so much analytical. So, if there was a way that tex could send an
paragraph shape in terms of boundingboxes to a file, and after that a
separate process could feed that into a neural net [optionally converted to
bitmaps so that the character shape could be taken into account], and the
net could send back a badness value to tex, so that there could be an
additional pass ... 

I think that it's not that hard to extend tex with a spawned process in the
paragraph builder and let it act upon the baddness. The main question is:
how do we convince thanh to provide that hook, and after that, how do we
trick ed in writing that analyzer. 

But this is a nice thread, 

Hans   
-------------------------------------------------------------------------
                                  Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                      Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
 tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: river detection

[Ed L Cashin]

Hans Hagen <pragma@wxs.nl> writes:

> At 01:45 PM 1/9/01 -0500, Ed L Cashin wrote:
...
> >Would it be possible to use MP and TeX together in order to detect
> >rivers?  If so, it would be a computer typesetting first, according to
> >Thanh's thesis.  :)
> 
> I must say that my first thought was that you might had a point, but after
> half an hour metaposting [playing a bit with picture postprocessing, of
> which you can find an example in the metafun manual] i think that, given
> that there was a good method, it could as well be done in tex itself, since
> tex has as much knowlegde in this respect as metapost, i.e. the boundingbox. 

I'd call that good news!  TeX knows where all the whitespace is, and
that defines whether there are rivers or not.

> What i did was (1) converting text into pictures, (2) converting
> boundingboxes of chars into matrix points and (3) looking at the result.

But you could just do a TeX macro that expands to a kind of matrix
like this:

           (5, 6) (11, 15) (35, 40)
           (7, 9) (11, 15) (26, 30)
           (2, 4) (11, 14) (24, 26)

(there's a river at position eleven).

> Maybe some matrix guru could program an ananalyzer but my math is to weak
> for that. 

In the above example, it doesn't look too hard to look for whitespace
positions that overlap over more than, say, four lines, and have a
thickness of more than some arbitrary value.  Then one could calculate
badness.  

> I think [but thanh may disagree] that grayness is something perceptual and
> rivers are things recognized by our eyes and brain at a quite low level,
> not so much analytical. So, if there was a way that tex could send an
> paragraph shape in terms of boundingboxes to a file, and after that a
> separate process could feed that into a neural net [optionally converted to
> bitmaps so that the character shape could be taken into account], and the
> net could send back a badness value to tex, so that there could be an
> additional pass ... 

I don't know, in the example above would it be hard to write a TeX
macro that recognizes when the position ranges overlap?  (e.g., 11-15
overlaps with 11-15 in a four-unit wide overlap.  11-15 overlaps with
11-14 in a three-unit wide overlap.)

> I think that it's not that hard to extend tex with a spawned process in the
> paragraph builder and let it act upon the baddness. The main question is:
> how do we convince thanh to provide that hook, and after that, how do we
> trick ed in writing that analyzer. 

-- 
--Ed Cashin                     PGP public key:
  ecashin@coe.uga.edu           http://www.coe.uga.edu/~ecashin/pgp/

Re: river detection

[Hans Hagen]

At 11:58 AM 1/10/01 -0500, Ed L Cashin wrote:

>But you could just do a TeX macro that expands to a kind of matrix
>like this:
>
>           (5, 6) (11, 15) (35, 40)
>           (7, 9) (11, 15) (26, 30)
>           (2, 4) (11, 14) (24, 26)
>
>(there's a river at position eleven).

Eh ... when tex typesets a paragraph, all input is already converted to
lists and macro expansion is gone. So, bbox info should come from the list
to dvi pass [or maybe from within the paragraph builder]. Keep in mind that
f i e t s [bicycle] is not just 5 chars, but becomes fi e t s and that at
some point the hyphenation engine pops in too. No way to hyphenate
\hbox{f}\hbox{i}...\hbox{s}.

Hans
-------------------------------------------------------------------------
                                  Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                      Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
 tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: river detection

[Ed L Cashin]

Hans Hagen <pragma@wxs.nl> writes:

> At 11:58 AM 1/10/01 -0500, Ed L Cashin wrote:
> 
> >But you could just do a TeX macro that expands to a kind of matrix
> >like this:
> >
> >           (5, 6) (11, 15) (35, 40)
> >           (7, 9) (11, 15) (26, 30)
> >           (2, 4) (11, 14) (24, 26)
> >
> >(there's a river at position eleven).
> 
> Eh ... when tex typesets a paragraph, all input is already converted to
> lists and macro expansion is gone. So, bbox info should come from the list
> to dvi pass [or maybe from within the paragraph builder]. Keep in mind that
> f i e t s [bicycle] is not just 5 chars, but becomes fi e t s and that at
> some point the hyphenation engine pops in too. No way to hyphenate
> \hbox{f}\hbox{i}...\hbox{s}.

I don't know what you mean by "the list to dvi pass".

Within the paragraph builder, though, I'm thinking that there's a time
when TeX tries a certain paragraph configuration.  At that time, you
have information about where the horizontal glue between hboxes begins
and ends.  That's the information that I was talking about in my
example.  With "I   w u v   fi e t s", TeX knows that there's a good
bit of horizontal glue after the "v" box and before the "fi" box.  It
knows the leftmost and rightmost position of that glue, right?

I was thinking that the river badness can be calculated at that time,
but are you saying that it can't be calculated at that time by a macro
because all the macro expansion is not going on at that time?

-- 
--Ed Cashin                     PGP public key:
  ecashin@coe.uga.edu           http://www.coe.uga.edu/~ecashin/pgp/

Re: river detection

[Hans Hagen]

At 01:59 PM 1/10/01 -0500, Ed L Cashin wrote:
>Hans Hagen <pragma@wxs.nl> writes:
>
>> At 11:58 AM 1/10/01 -0500, Ed L Cashin wrote:
>> 
>> >But you could just do a TeX macro that expands to a kind of matrix
>> >like this:
>> >
>> >           (5, 6) (11, 15) (35, 40)
>> >           (7, 9) (11, 15) (26, 30)
>> >           (2, 4) (11, 14) (24, 26)
>> >
>> >(there's a river at position eleven).
>> 
>> Eh ... when tex typesets a paragraph, all input is already converted to
>> lists and macro expansion is gone. So, bbox info should come from the list
>> to dvi pass [or maybe from within the paragraph builder]. Keep in mind that
>> f i e t s [bicycle] is not just 5 chars, but becomes fi e t s and that at
>> some point the hyphenation engine pops in too. No way to hyphenate
>> \hbox{f}\hbox{i}...\hbox{s}.
>
>I don't know what you mean by "the list to dvi pass".
>
>Within the paragraph builder, though, I'm thinking that there's a time
>when TeX tries a certain paragraph configuration.  At that time, you
>have information about where the horizontal glue between hboxes begins
>and ends.  That's the information that I was talking about in my
>example.  With "I   w u v   fi e t s", TeX knows that there's a good
>bit of horizontal glue after the "v" box and before the "fi" box.  It
>knows the leftmost and rightmost position of that glue, right?
>
>I was thinking that the river badness can be calculated at that time,
>but are you saying that it can't be calculated at that time by a macro
>because all the macro expansion is not going on at that time?

Right. Input (either or not expanded macros) is converted into a linked
list. This list is then broken into lines [actually a solution tree first].
Normally baddness is calculated by summarizing badness's of lines [kind
of]. A river detector should act upon the *resulting* paragraph as a whole,
since it should look 'vertical' instead of horizontal. 

I think that some heuristic method is needed then. I can even think of
wierd ones, like: 

build a bitmap from the boundingboxes of the chars [no interlinespace],
enlarge the bitmaps some 10%, then compress the bitmap. The smaller it is,
the better the grayness [guess]. Or apply jpeg/mpeg like analysis, with
those neighbouring pixel analyzation things.  

River detection could be done by tracing edges or something like that or a
neural net. 

Of course one could act upon the list directlty, but i think that a more
visual related method is easier, especially since we also need to take the
actual dimensions of the bbox into account [even better: the real shape or
composed shape]. 

Hans
-------------------------------------------------------------------------
                                  Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                      Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
 tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: river detection

[Ed L Cashin]

Hans Hagen <pragma@wxs.nl> writes:

> Right. Input (either or not expanded macros) is converted into a linked
> list. This list is then broken into lines [actually a solution tree first].
> Normally baddness is calculated by summarizing badness's of lines [kind
> of]. A river detector should act upon the *resulting* paragraph as a whole,
> since it should look 'vertical' instead of horizontal. 

Is it possible for TeX to generate a list of values showing the
positions where the interword whitespaces begin and end for all the
lines in the paragraph?

-- 
--Ed Cashin                     PGP public key:
  ecashin@coe.uga.edu           http://www.coe.uga.edu/~ecashin/pgp/

Re: river detection

[H. Ramm]

Hans Hagen wrote:
> I think [but thanh may disagree] that grayness is something perceptual and
> rivers are things recognized by our eyes and brain at a quite low level,
> not so much analytical. So, if there was a way that tex could send an
> paragraph shape in terms of boundingboxes to a file, and after that a
> separate process could feed that into a neural net [optionally converted to
> bitmaps so that the character shape could be taken into account], and the
> net could send back a badness value to tex, so that there could be an
> additional pass ...

If such a "text picture analyzer" would work, it could handle protruding
and other greyness/view related stuff as well, couldn't it?

Grüßlis vom Hraban!
---
http://www.planet-interkom.de/fiee.visuelle/formelsammlung.html

Re: river detection

[Frans Goddijn]

That would be nice, detections of the "rivers of white". A while ago I had
one perfectly vertical "river" in a short paragraph, freakish, not a river,
a steel straight canal!

But if I could make a wish or three  I'd have

1) a printed ConTeXt manual
   (with plenty explicit examples showing not only the
    "idea" of the method but full head-to-tail ready to
     cut-and-paste actually working examples...)

2) a perfectly simple single command like
    "texexec font tim" to auto-install
   all tim*.afm/.pfb files in a given directory ;=}}

3) "texexec create masterpiece mcNab "
     yielding in auto-expand a truly original nobel
     prize winning novel, that wrote itself in the style
     of Nabokov and was autoformatted, with
     protruding characters of course (I could live
     with any meandering rivers of white then... ;=}}}

----- Original Message ----- e
From: Ed L Cashin <ecashin@coe.uga.edu>
> Would it be possible to use MP and TeX together in order to detect
> rivers?  If so, it would be a computer typesetting first, according to
> Thanh's thesis.  :)

RE: river detection

[Dan Seracu]

Hi!
> 2) a perfectly simple single command like
>     "texexec font tim" to auto-install
>    all tim*.afm/.pfb files in a given directory ;=}}
>

I think this would be a very nice option. I did not succeed into installing
new fonts on ConTeXt,
especialy for using accents (i.e romanian accents)

Dan Seracu

RE: river detection

[Hans Hagen]

At 01:29 PM 1/10/01 +0200, Dan Seracu wrote:
>Hi!
>> 2) a perfectly simple single command like
>>     "texexec font tim" to auto-install
>>    all tim*.afm/.pfb files in a given directory ;=}}
>>
>
>I think this would be a very nice option. I did not succeed into installing
>new fonts on ConTeXt,
>especialy for using accents (i.e romanian accents)

That will be easier soon once we move to named glyphs. 

Hans
-------------------------------------------------------------------------
                                  Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                      Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
 tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: river detection

[Hans Hagen]

At 11:40 AM 1/10/01 +0100, Frans Goddijn wrote:
>That would be nice, detections of the "rivers of white". A while ago I had
>one perfectly vertical "river" in a short paragraph, freakish, not a river,
>a steel straight canal!

Tex can do strange things, especially when you test things like

\dorecurse{10}{Some short sentence. }

you can get rivers depending on the width of the paragraph. If this
sentence fits twice, the pre last line often is squeezed. I suppose it has
to do with some overall baddness calculation. 

BTW, thanh had implemented some switch to fool tex into continuing while
some overfull line was found, but i'm not sure if it's still there.
[something \avoid..., one of the magic secret pdf primitives]  

>But if I could make a wish or three  I'd have
>
>1) a printed ConTeXt manual
>   (with plenty explicit examples showing not only the
>    "idea" of the method but full head-to-tail ready to
>     cut-and-paste actually working examples...)

i know, currently ton is updating the beginners one, next will be the
reference, and then a design manual

>2) a perfectly simple single command like
>    "texexec font tim" to auto-install
>   all tim*.afm/.pfb files in a given directory ;=}}

would ne a separate script then, more a texutil job btw

>3) "texexec create masterpiece mcNab "
>     yielding in auto-expand a truly original nobel
>     prize winning novel, that wrote itself in the style
>     of Nabokov and was autoformatted, with
>     protruding characters of course (I could live
>     with any meandering rivers of white then... ;=}}}

Well, texexec could go to google and turn the resulting list of urls into a
random book if it would make you happy. 

Hans
-------------------------------------------------------------------------
                                  Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                      Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
 tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: river detection

[Taco Hoekwater]

> >2) a perfectly simple single command like
> >    "texexec font tim" to auto-install
> >   all tim*.afm/.pfb files in a given directory ;=}}
> 
> would ne a separate script then, more a texutil job btw

In my 'spare' time, I'm working on a font interpreter
module to be written in perl. This could be one of the
front-ends to that module eventually. In order to instaLL
a font correctly, you also need some encoding information
which requires parsing the font, so the solution is not
as trivial as it looks on first sight.

Greetings, Taco

Re: river detection

[Hans Hagen]

At 02:14 PM 1/10/01 +0100, Taco Hoekwater wrote:
>
>> >2) a perfectly simple single command like
>> >    "texexec font tim" to auto-install
>> >   all tim*.afm/.pfb files in a given directory ;=}}
>> 
>> would ne a separate script then, more a texutil job btw
>
>In my 'spare' time, I'm working on a font interpreter
>module to be written in perl. This could be one of the

Good news! 

>front-ends to that module eventually. In order to instaLL
>a font correctly, you also need some encoding information
>which requires parsing the font, so the solution is not
>as trivial as it looks on first sight.

Indeed. So, we limit ourselves to proper encodings -) 

Hans
-------------------------------------------------------------------------
                                  Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                      Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
 tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: river detection

[H. Ramm]

Frans Goddijn wrote:
> That would be nice, detections of the "rivers of white". A while ago I had
> one perfectly vertical "river" in a short paragraph, freakish, not a river,
> a steel straight canal!

In german we call such a "Wasserfall" (waterfall).

> But if I could make a wish or three  I'd have
> 1) a printed ConTeXt manual
> 2) a perfectly simple single command like
>     "texexec font tim" to auto-install
>    all tim*.afm/.pfb files in a given directory ;=}}

I subscribe!
(1) may be not printed, but I wish it were complete!

> 3) "texexec create masterpiece mcNab "
;-)

better:
3) facilities to define a layout (design grid)
4) a working PDF viewer for Linux PPC
5) ...
...

Grüßlis vom Hraban!
---
http://www.planet-interkom.de/fiee.visuelle/formelsammlung.html