|
Algorithm Overview
Before talking about my specific
implementation of this paper, I'd like to summarize the
algorithm briefly so the reader does not have to refer to the
original paper directly. The goal of the
algorithm/application is to take a photograph or some other 2D
image and convert it to something that resembles a
painting. This particular algorithm does so by first
computing proposed locations of brushstrokes from the source
image. More brushstrokes are needed in areas of high
detail; less in flat areas. From all the proposed
brushstroke image sample points, a brushstroke (incld. location,
length, width, angle, and color) is computed based on a color
difference (i.e. distance from the sampled color) around the
chosen pixel some radius fixed by a "max brushstroke
size" variable. The brushstrokes are painted to the
screen in order of largest to smallest so the details appear on
top.
Implementation
I set out to implement the
algorithm described by Shiraishi and Yamaguchi using
OpenGL. My application should allow the user to open
images, press a button, and "watch the fun" so to
speak. OpenGL is probably not the best renderer to do
things like this because displaying images requires use of
textures which are limiting (size requirements, etc.).
Also, these types of algorithms are extremely pre-process,
per-pixel, CPU computationally intensive; the OpenGL pipeline
isn't exploited here by any means. One thing that was nice
about the use of OpenGL was that the actual "painting
animation" after all the brushstrokes are enumerated is fairly
fast and interesting to watch.
As somewhat hinted at above, the algorithm is
inherently broken down into nice (simple?) steps that allowed
the implementation to be a "check as you go"
process. There are two intermediate images that are
generated before the painting. Both are used in the
determination of brushstroke location. The first, a
"Stroke Area Image" is a gray scale image computed
based on the area of a particular color in a particular
region. Darker areas represent greater detail and where
more brushstrokes should be located. The second, a
"Stroke Distribution Image" is a binary halftone image
generated from the Stroke Area Image. A black dot
represents a sample location for a brushstroke.
Brushstroke characteristics are determined from the halftone
sample points, ordered based on area, and then
"painted" to the frame buffer. Using
the description from Shiraishi and Yamaguchi I was able to
generate a Stroke Area Image that looked almost identical to the
images in their paper. The Stroke Distribution Image
however, was slightly more difficult. The authors
reference a number of papers on generating a halftone image
based on a space filling curve. They discuss changes that
they made to these algorithms to suit their own purpose and to exploit
the characteristics that they wanted, but they do so loosly and
I was unable to determine the exact method they used to generate
their halftone image. The main paper they reference uses a
method based on clustering (which Shiraishi and Yamaguchi
explicity say they don't use); I was unable to find a space
filling curve algorithm that did not use clustering. As opposed
to spending a great deal of time to try to implement another
SIGGRAPH or NPAR paper for this assignment, I found a simpler
halftone paper and implemented it for this project--adjusting
for the Shiraishi and Yamaguchi modifications when possible.
Basically, I get less sample points than Shiraishi and Yamaguchi
in areas of high detail, which does affect the results, but only
subtly.
|
Original Test Image
|
Stroke Area Image
|
|
Stroke Distribution |
Result |
There was no mention of execution time in the
Shiraishi and Yamaguchi paper. My implementation is
extremely slow even for image sizes of 512x512 pixels.
This was expected as at least the Source Area Image performs on
the order of O(brush_size^2) operations per pixel (the halftone
generation is not too slow). As well, some of my results
have generated 80,000+ brushstrokes which take a while to sort
by area as well.
The Application...
One feature that is always
nice to have in applications such as this is the ability to
modify parameters to change the image. I spent a lot of
time on the usability of the application and user
interaction. That's difficult because as I've already
mentioned this isn't a speedy process. I allow the user to
modify three parameters, namely: maximum brushstroke size, a
"sample factor" that helps determine the number of
brushstrokes, and the paint opacity. All intermediate
images are saved as textures in OpenGL and may be recalled after
all have been generated. Changing any of the parameters
will only re-create the intermediate image that needs to be
modified. Re-generating the brushstrokes is also an
option. That is, the user can just generate the
intermediate images and get estimate of the number of brushstrokes that
will be required before deciding to generate them or not.
It makes experimentation much easier. Changing the opacity
of the paint doesn't modify anything about the number of
brushstrokes or their order so the image can simply be
repainted. Also since the painting animation is
interesting, there is a button to simply "replay" the
painting. The console window is used to keep the user
informed about what is being generated at a particular
time. For example, during the brushstroke generation and
sorting, the console displays how many brushstrokes have been
generated so far.
...and Its Limitations
Unfortunately, no
application is perfect and this implementation is no
exception. From an algorithm-only standpoint, the only
thing that I feel is really "wrong" with my code is
the Stroke Distribution Image which I've already mentioned. Of course, I have the same
problems that Shiraishi and Yamaguchi had too...the biggest of
those has to do with when the brushstrokes are small (which
results in a final image with greater detail) you need an
extremely large number of them to "fill-in" the entire
image. This is especially true in images where there is a
lot of flat color. The algorithm is designed to not
generate as many brushstrokes in that area, and therefore the
canvas tends to show through more. This problem is worse
for a more translucent brushstroke texture or one with many
"gaps", which Shiraishi and Yamaguchi notice too (See
sky of "Shore at Dusk" image in the 'Results' section
below). The
largest implementation issue is that I require the user to use an
image size of 512x512 pixels. I made this decision early
in the design process based on the requirements of OpenGL
textures and the obvious simplification of implementation.
That would be the first change I'd make to my application.
Shiraishi and Yamaguchi do not have this limitation (they
probably didn't use OpenGL either). Interestingly, the
particular space filling curve algorithm they use works for
non-square images as well. It seems that both of my
"problems" would be nice to fix together. The
other obvious hindrance is the speed of the application which
I've already talked about. There's not much that can be
done in this respect but I suspect that my brushstroke
generation and sorting is taking longer than it has to.
Results
I've been interested in this sort of
graphics for over a year now. As an undergraduate I wrote
a thesis on artistic image filters and wrote my own application
and some of my own filters. One of the implementations was
an "oil paint"
filter. It was very interesting
to study Shiraishi and Yamaguchi's algorithm and contrast it to
my extremely simple and naive algorithm; the images
generated for this project are much more interesting.
Below are some sample outputs:
(Enlarged Image from Above)
Brush Size = 15; Sample Factor = 75%
Apx. 82,300 Strokes
Same source image from above.
Brush Size = 40; Sample Factor = 50%
Apx. 54,900 Strokes
Original Image: Downtown Seattle at Night
Brush Size = 40; Sample Size = 50%
Apx. 103,200 Strokes
Original Image: Ocean Shore at Dusk
Brush Size = 15; Sample Size = 86%
Apx. 73,900 Strokes
Original Image: The Parthenon
Brush Size = 18; Sample Size = 90%
Apx. 117,500 Strokes
Same source image from above.
Brush Size = 50; Sample Size = 65%
Apx. 62,000 Strokes
What's Next?
I've decided for the time being
to make this sort of project my primary research interest.
Shiraishi and Yamaguchi propose enhancements such as on-thy-fly
optimal brush size determination and decision of the minimum number of brush
strokes to cover the entire image. I have a few ideas of
my own to enhance this algorithm and some additional spin-off
ideas that could prove to be interesting as well.
References
Paul Haeberli. Paint by
numbers: Abstract image representations. Computer
Graphics, 24(4):207-214, August 1990. Michio
Shiraishi and Yasushi Yamaguchi. An algorithm for
automatic painterly rendering based on local source image
approximation. Non-Photorealistic Animation and
Rendering, 53-58, June 2000. Wong
Tien-tsin and Siu-chi Hsu. Halftoning with Selective
Precipitation and Adaptive Clustering. Graphics Gems V,
Edited by Alan Paeth, AP Professional, 302-315, 1995. Luiz
Velho and Jonas de Miranda Gomes. Digital halftoning with
space filling curves. Computer Graphics,
25(4):81-90, July 1991.
Download
This application runs under Windows
9x/Me/NT/2000/XP If you don't have them already, you'll need
openGL32.dll and glut32.dll in order to run the
application. I've provided links here. Sample images
are included in the application package.
Automatic Painterly Rendering Package
application and examples
2.30 MB
OpenGL 32-bit DLL
contains opengl32.dll
269 KB
GLUT 32-but DLL
contains glut32.dll
62 KB
|
email
at jasonwaltman
dot com