image2ascii - state of the art overview (was: Re: Metallica)

Gereon Bartel wrote:

> I tried Jave4 for the same Picture and there wasnt a too big difference in the end.
> Very cool how much Options there are at Jave4 and i tried al lot to find the optimal one for this Picture.
> It looks a bit better in the Distance but isnt as clear as i hoped.

So you can see that even with this rather simple image the limits of all
known automatical conversion algorithms have been reached :-)

> Is it a good or a bad Sign?
> Is this the final Frontier for Ascii-Generators?
> Or is my Picture-Calculation almost as good as Jave4s ???

I think for every algorithm there is an image it works better with than
any other algorithm.

 - - - - - - - - 8< - - - - - - -  - - - - - - - - - - - - - - - - - - -

                       Image2Ascii conversion
                    State of the art - Overview
               V0.1 (c) Copyright Markus Gebhard Mai 2002

Well, here is an overview of the knowledge I have gathered during the
last two years or so of work on JavE [0]:

As far as I know there are 3 kinds of i2a (image2ascii) algorithms:

1. Black/white-algorithms.
==========================
IMHO they were the first ones developed. Explanation by example:

  ##### ####   ## #####    88888 8888  d8b 88888
    #   #     #     #        8   8    ]b     8
    #   ##    #     #        8   88    Yb    8
    #   #      #    #        8   8    o d8   8
    #   #### ##     #        8   8888  YP    8
     low resolution         higher resolution

There is also a tutorial about how they (and some simple greyscale
algorithms) work in the www at [1].
I have not focused on b/w conversion, so the algorithms in JavE are not
the best ones for it. Well, ok, I will explain a very simple b/w
algorithm: 2by2 (JFL..). It takes 4 pixels from the original image and
converts them to black and white.
The 16 patterns are converted as shown here:

    ..  .X  X.  ..  ..  XX  ..  X.  .X  .X  X.  XX  XX  XX
    ..  ..  ..  X.  .X  ..  XX  X.  .X  XX  XX  .X  X.  XX

 =>      `   '   .   ,   "   _  (    )   J   L   7   P   8

The problem here are '(' and ')' for they do not look that good. One
could also use '[' and ']'.

2. Greyscale-algorithms.
========================
They try to find a character that has a brightness that is very close to
the original pixel in the image. Most algorithms use 1 pixel to convert
it to 1 character:

##@H@@@ku=;^^?:^;;;;:^...`````;p#Ny=HHH
NHHgH#fr;^;^.:lrrt?:^^^....``.;p#M@;m@H
NNHHHz?:.^:=uyZyybfyl?;^..^=Zbbk@NH=yH@                           `.^.`
gHN@r:^..?kH@@Hb?pqzvl?^`?mHkuH##NHtZ@@                          .^
NMqr;^.;rvtZyZZ;^;tzvt?``rvulz@H##@zrkH                        ..`
Mpt:.;Zut=????=?;;?ttr=.`:?lvyyg#H@Z?mH     `.    `      ``..^.`
yt^^fgZvt=?::^^::;?=ttt^ ^;?trzkHH@p;mN     .?fr?^..^.^;;:` ``
t.;HHkurtl?;;::::;=ltrt; .;?ltu@#HHg?ZN ``?yp@@@@b=.?yVfppZ^^lvrt?.
:vMNmqZrtl=??;;;;?trtvr?``??lrpNHgHH?tN .@#@NHNNNV`.=pg@gfrtyVVyyyu=`
fNNNpkZvrtl=???;?=rruuut^^==tyHNH@HNr=@ :NMMNHfrl.       ?yZyyy?.^^^.
#H##yfuvrtl===??;??=l??^^;=lZHNH@mH#p=b  ?kHp.  `       .Zyfyfr.
                                                          ^=;.
"state of the art"-algorithms use more than 1 pixel per character and
the result shows more details:

##@H@@@ku=;^^?:^;;;;:^...`````;p#Ny=HHH
NHHgH#fr;^;^.:lrrt?:^^^....``.;p#M@;m@H
NNHHHz?:.^:=uyZyybfyl?;^..^=Zbbk@NH=yH@                            .?!
gHN@r:^..?kH@@Hb?pqzvl?^`?mHkuH##NHtZ@@                          .`
NMqr;^.;rvtZyZZ;^;tzvt?``rvulz@H##@zrkH                        ..`
Mpt:.;Zut=????=?;;?ttr=.`:?lvyyg#H@Z?mH      .            ....``
yt^^fgZvt=?::^^::;?=ttt^ ^;?trzkHH@p;mN     ..Q+.,...``+..
t.;HHkurtl?;;::::;=ltrt; .;?ltu@#HHg?ZN   .JWHHHHR+..dXXkWk,.Juu&..
:vMNmqZrtl=??;;;;?trtvr?``??lrpNHgHH?tN  dNHMMMMM@ `"BHHHB6JXWWXXXX&.
fNNNpkZvrtl=???;?=rruuut^^==tyHNH@HNr=@ .MMMMMB"7!       .XXXWX|`??!`
#H##yfuvrtl===??;??=l??^^;=lZHNH@mH#p=b  7WMY^           XWWXWY'
                                                          ?7=!
For converting to a bigger result (>100 characters wide) it is a good
idea to use features like error diffusion (with 1-pixel algos) and to
combine both of the above algorithms (and maybe to use some other
tricks) - but that kind of algorithm will not be available before I
release JavE5.0 ;)

For greyscale algorithms you can either use a gradient by defining the
characters for different steps of brightness (e.g. " .:oO8@" or "
.:OI#M"), or you can create a greyscale table containing the brightness
values for each character.
JavE4.0 only contains that table for Courier New (in 4-pixel algo), but
at the moment I am building greyscale tables for many other fonts.
I believe that the limit with pure greyscale algorithms will be reached
by then.

3. Edge-tracing or edge-detection algorithms.
=============================================
There are not many of them yet. In fact I only know about two...
Most people here seem to believe that those algos could be the solution
to all our conversion problems. I do not think so.
There is a very simple one for edge tracing - this one is more like
cheating than a _real_ algorithm:
                   ______                         ______
    ________     _/      \_        ________     ,'      `.
  _/        \___/          \     ,'        `-._/          \
 /__  __                  __\   /__  __                  __\
//  \/ _|                |     /'  \/ _|                |
     _/       _           \         ,'       _           \
    /        / |      _   |        /        / |      _   |
   /   __   |  \     | \_ /       /   __   |  \     | `. /
   |__/  |  /   \__  |   \        |,-'  |  /   `-.  |   \
   \     | |       \_/            \     | |       \_/
        /  /                           /  /
       /  |                           /  |
       |  /  original                 |  /  result when
       | |  algorithm                 | |  running some
      /  |   result                  /  |  optimizing
      |  |                           |  |  algorithm afterwards
      |  |                           |  |
      |  |                           |  |
      |  |_                          |  |_
     /_ ___\                        /_ ___\
       \                              \

(The basic algorithm can be found here: [3] The pseudocode is available
in the google groups archive at [4]) 

And there is a very complicated _real_ edge detection algorithm:
                   ,--.---.
    / -'''''-._ .-'        -\
   '|    _     L'       ../--
 <'' `'' '|             '-.
       ,-'     U    :\_    |
     v-       /`.    ``.   |
    /    ,'| |  |     |'`|./
    /_,,' /  |   `._  |   -
    '    |  |       `'|
        .-  |
           |
       .'  |   It works as described in many books about image
       |  |    processing and uses JavE's capabilities for 
       |  |    converting lines to Ascii
       |  |
       |  |
       |  |
      .'  |
     _ _  ]_,

(read more about edge detection algorithms and combination with
grayscale algorithms in the google groups archive at [2])

That's it.

As you can see by the examples above, it always takes a bit of work by
hand to improve the result. BTW: There is a nice tutorial that explains
how to use the autmatical conversion to start from to creating _real_
art at [5].

I think (for beginners) it is a good idea to convert an image trying to
find a good algorithm. Then paste the result into your favorite text
editor and make changes by hand until it looks best.
Maybe with some images it is a good idea to also use the plastic bag
technique: The original image is placed in the background of your text
editor (as kind of watermark) and you can draw the Ascii image by hand.
  
There have been some investigations on combining edge detection and
greyscale algorithms. But this does not seem to work well. Look at this
simple example:

  ::::d88  ::::/88
  :::d888  :::/888  The diagonal lines from the edge detection 
  ::d8888  ::/8888  also generate empty triangles...

This effect becomes even worse when dealing with details like eyes for
example. There is an idea for solving this problem: One could define
rules for mixing the characters from both conversions. There is this
kind of mixing algorithm in JavE:
  o + d = d
  - + | = +
  / + \ = X
   ...
But this algorithm is only defined for about 200 combinations and there
are about 90x90=8100.
Also first tests have shown that it does not work that well [4]...

BTW: More often than once I have considered creating a very simple
plugin architecture for JavE, so that everybody with basic Java
programming skills can easily write his/her own conversion algorithm,
w/o having to care about loading, scaling and preprocessing images etc.
Is there any
need for this or is implementing it just wasted time?

[0] http://www.jave.de
[1] http://www.sci.fi/~iltzu/ascii/ada/aaatechnical.txt
    (have a look at the last third of that text)
[2]
http://groups.google.com/groups?selm=3C59AF2E.92AC8B89%40rz.uni-karlsruhe.de&oe=utf-8&output=gplain
[3] http://www.ai.mit.edu/~jsd/Projects/ImagesToText/
[4]
http://groups.google.com/groups?selm=3C5318B5.80F13461%40rz.uni-karlsruhe.de&oe=utf-8&output=gplain
[5] http://www.jave.de/docs/tutorial2/index.html
 - - - - - - - - 8< - - - - - - -  - - - - - - - - - - - - - - - - - - -

> I fear it's some kind of Frontier in Quality but i won't give up so fast.
> I got some little Ideas remaining an maybe the Group-history gives me more.

During my work on JavE I have found out that sometimes a very simply
algorithm creates a much better result than a complex high tech overkill
algorithm :-)

So have fun creating your very own algorithm (maybe the
"metallica"-algorithm?).

Regards,
Markus
-- 
 \-/        http://www.jave.de     O_< Get JavE4.0 now!    \-/
J|a|v|E                           /|                      J|a|v|E
 /-\      Ascii-Art for eyeryone  / \    - for free!       /-\

Related ASCII art in the Gallery

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

Make your own ASCII art

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