Repairing wrapped lines (was: Re: Nokia 8210)

Michael Schierl wrote:
[lots of stuff about a wrapped lines repair algorithm]

This discussion seems a little off topic, for it is about computer
algorithms in some way. But in the end it is about repairing wrapped
ascii art - indeed a problem that occures quite often in this newsgroup.
So I think it is not a bad idea to discuss it here.

Michael, as you already stated the greatest problem for such kind of
algorithm is that it has to 'guess'. It has to try different
combinations and find out which one's best. And with wrapped lines there
are two things unknown:

1) How many lines belong together? Usually it is sometimes 1, and then
2,3,4... with decreasing propability. I think it would be ok to have an
algorithm that can handle 1,2 and 3.

2) How many space characters have to be added between the pieces?

As you already said, a greedy algorithm could be used: You go through
the image line by line and always choose the option for the next step
that will lead to the best provisional result. 
BTW: I think dynamic programming [building a table with all possible
solutions] is better here, for with greedy making errors in the
beginning will multiply to enormous errors in the end.

Anyway, here is the problem: What is "the best (provisional) result"?
One needs a function that can tell how good/bad a result is (compared to
others).

Some time ago I have written an algorithm to rate how good two lines of
ascii art fit together.  The algorithm is the one that is included in
JavE 1.1 (Menu->Modify->Try_to_repair). It is based on a configurable
set of rules for how to rate combinations of characters in subsequent
lines. For example a character | followed by a character | in the next
line will be given a credit of 20, while it will get a negative value on
the other hand if the characters are shifted and not one below the other
(a set of those rules is defined in the file repair.txt, it can be
edited by hand).

It works quite well for ascii line art, but I have not designed it to
work with shaded ascii art like that:

BMMaXX;:          0WBZ80BWWWWBBBB0B0BZaBMMB::..;ZB@M.
0ZWMZaaa7aZSi    MMM@WWMMMMW00WMMMMM8Z2 BMW;rBMB2:XW
WW88MBaZ2SrrSS,  rMMMMMB  ,MMMMW   S27iWM8;ZMMr8Mr
WW@BZWM82Z2XSaZ.   MMMMMMM7     ;WWa7aMM2:XrZ;
BWWWW88M@ZZZS77;,   BMMMMMMMMMMMM8ZWMMM;iS7r.
BWWB@@W00@MZ2S227ri   ,MMMMMMMMMMMMM8..;rii.
WWWWWWW@WB0@MW82SX77;     ,X0BBZX.  .i;:
BBWBBBWBBW@B00MM@0ZSriii,         .
WBBWWBWWWWWWWWWB0WMMMMW8Xri,.

One idea to adopt the algorithm was to give each character a number
corresponding to its shade of gray. I already have tables for that, so
that's no problem. Then rating two subsequent lines can be done by
comparing those values.

Also for rating one should consider the dimensions of the result:
                                 4        :
  +------------------+-------------------+
  |                  |                   |
  |                  |                   |
  |                  |                   |1
  |                  |                   |
  |                  |                   |
  |                  |                   |
  |                  |                   |
  |                  |                   |
  +------------------+-------------------+
  |                  |
  |                  |
3 |                  |
  |                  |
  +------------------+
:     4

A width to height ratio of 4:1 to 4:3 seems ok. Other ratios should be
rated with decreasing values.

At the moment I am very busy with working on JavE 2.0 :-( - I want to
relase it at 13th October :-)

I think I will do some more investigation on this wrapping problem
afterwards.

Markus

Related ASCII art in the Gallery

Explore these categories from our collection of 11,000+ artworks:

   _______
  |.-----.|
  || jgs ||
  ||_   _||
  `--)-(--`
 __[=== o]___
|:::::::::::|\
`-=========-`() 

     ,sSSs
   ,SSSS_/ ,_
   sS/`))\//
  sS//|_(_/      _,
  SS\\\  `""-.-'` /
sSS` jgs-==-'`'-._\

 ___________
|  _______  |
| |       | |
| |       | |
| |       | |
| |_______| |
|___________|

//O\\

|\/\/\/|
|      |
|      |
| (o)(o)
C      _)
 | ,___|
 |   /
/____\

|HHHHH/"\"\HHHHHHH|
|HH`\|_.-)'|/'dP,H|
|Hb.`\\_/_//'.oddH|
|HHHb|`.\/\,'|HHHH|
|HHHHHb/\/\/|HHHHH|
|"""""""""""""""""|
| |"" /\ \  / |"" |
| |__/--\ \/  __| |

Make your own ASCII art

Turn images, text or 3D into ASCII, or draw your own – right in your browser.