Fast Generation of Various Painterly Style Images
Based on Scalable Poisson Disk Pre-SamplingTechnique
Shuhei Kodama† Junichi Sugita‡ Tomoaki Moriya† Tokiichiro Takahashi†,§†Graduate School of Science and Technology for Future Life, Tokyo Denki University,
Senjuasahi-cho 5, Adachi-ku, Tokyo, 120-8551 Japan‡Faculty of Healthcare, Tokyo Healthcare University,Setagaya 3-11-3, Setagaya-ku, Tokyo, 154-8568 Japan§UEI Research{s-kodama, sugita, moriya, toki}@vcl.jp(a) Input image(b) Watercolor painting(c) Oil painting(d) Colored paper mosaic
Fig. 1. Various painterly style images generated by our proposed system

Abstract— We present a fast system for generating various
painterly style images automatically from input images using ascalable Poisson disk pre-sampling technique. We developed apre-sampling approach for drastically fast generation of artistic
images. Watercolor painting, oil painting, colored paper mosaic
and pointillistic painting can be generated by the proposed method.
Keywords— Non-photorealistic Rendering;
Painterly Rendering:

I. INTRODUCTION
Techniques to generate non-photorealistic images such as oilpainting and illustrations from 2D image including photograph as aninput are called non-photorealistic rendering (NPR). Since Haeberli[1] has proposed its basic idea on generating painterly style images bystroke composition, many researches have been done on this area. We
have been developing NPR methods [6] [7]. Most of conventional
methods including our methods are dedicated to a specific painterly
style. A system, which generates variation of painterly style images
from an input with lower computational time, is desired. Then, theuser can convert input images into nonphotorealistic images easily.
There have been proposed a couple of methods which generated
various kinds of painterly style images [3] [4], however, they took
several tens of seconds to minutes for generating megapixel images.
Besides, their methods are not so much flexible to adjust visual effects
to painterly styles according to user’s preference.
In this paper, we propose a system for generating various painterly
style images from 2D image by integrating and unifying several NPR
methods we proposed so far. We present a drastically fast system thatgenerates multi-painterly style images according to the user’spreference.

(e) Pointillistic painting

II. PREVIOUS WORK
Hays and Essa [3] and Johan, et al. [4] proposed methods which
generate various kinds of painterly style images, but these methods are
too slow. Hays and Essa reported that the computation time of agenerated 1,000 × 1,000 pixel image is 80~300 seconds. Johan, et al.
proposed a method for generating various artistic images based on
Voronoi diagram, whose computation time of a 512 pixel image tookfor 5.6 seconds. Their method is considered to require much morecomputation time for image with rendering and a large number ofpixels. They generate variation of painterly styles only by adjusting
rendering parameters, for instances, stroke color, texture, and size.
However, they do not handle to express variation of painting materials,
as well as commonly used painting techniques such as optical mixture,
halo effect, and so on.
Considering such painting materials and techniques, we havealready developed generation methods of various kinds of painterly
style images [6] [7]. But, each of these methods was dedicated to one
specific painterly style. Fortunately, all of our methods adopted
scalable Poisson disk sampling technique (hereinafter, SPDS in short),
which is powerful to generate various kinds of painterly style images.
SPDS technique samples input images by placing disks whose radii
are the same, or different. The radii of disks are corresponding topaintbrushes. However, SPDS technique is too slow, because it
samples a canvas by placing disks randomly but avoiding overlapping
them.

III. SYSTEM DESIGN
We propose a system which consists of three processes: sampling,stroke composition and visual effects as shown in Fig. 2. In order torealize the system, we develop a fast SPDS technique. We also
integrate and unify our previous methods to generate various kinds ofpainterly style images from 2D image as an input.

disks randomly but uniformly, where the radii of all the disks are thesame. SPDS technique first places large disks, then places disks
gradually reducing their radii. Once disks are placed, their positions
and radii are not altered. Although SPDS technique is quite resemble
to HPDS but different, acceleration algorithms for HPDS techniqueare not applicable to SPDS technique. Therefore, we realize speeding
up by using pre-computational approach. This method is called
scalable Poisson disk pre-sampling (SPDpS) technique. We explain
the algorithm of SPDpS technique below.

Fig. 2. System configuration of our system

In sampling process, sampling data are determined such as disk
sampling distribution, disk attributions (size, orientation, color) andsampling order of the disks. The base of sampling data is determined
by SPDS technique. However, SPDS technique is too slow to sample acanvas uniformly and randomly, because SPDS is based on ‘darts
throwing’ algorithm. We accelerate the SPDS technique by precomputation. This technique is called as scalable Poisson disk presampling technique (SPDpS, in short). Sampling data are generated byusing the SPDpS technique and information obtained from input
image such as ETF (edge tangent flow) and edges.
In stroke composition process, both point and stroke brushes arecomposed. Point brush is a very short stroke, and its shape is quadrateor circular. Point brush is generated from a sampled disk directly.
Point brushes are used in colored paper mosaic and pointillistic
painting. Stroke brush is composed by connecting two disks which arelocated nearby and are similar colored. Stroke brushes are dominant toexpress various kinds of painterly style images such as oil painting
and watercolor painting. Our system can control which types ofbrushes will be mainly utilized according to user’s preference.
In visual effect process, we provide nine visual effects regarding
both painting materials and techniques as shown in Fig. 2. Especially,
stroke composition emphasizes visual effects. Details are described at
Section Ⅳ.C.

A disk, radius =, is sampled at random on the canvas. A
set of disks already sampled is defined as, and next sampling
point is defined as . The radii of the arbitrary point ∈that
already sampled and the point are defined as , accordingly.
Further, the distance between and is defined as . Meanwhile,
if a case is+ , it is possible to place the point , and if+, it is impossible to place the point .
the case isHowever, with above conditions, in case the value of a coefficient α islow, a small disk is completely comprehended by a larger disk. Nosmall disk is needed in large disk. And it may detract visual effect. To
avoid this artifact, we added another criterion. If the case is,no disk is placed. If this procedure continues to fail many times (thislimitation number is called ), which means that very few spaces areleft. Then, the radius of disks is reduced by ⊿ pixels (including
already placed disks). This algorithm is recurred until radius of disks
become equal to. SPDS technique varies the radii, but the radii of
already placed disks are not altered. Fig. 3 shows the difference
between HPDS and SPDS techniques.

Fig. 3. Difference between HPDS and SPDS

2) Sampling Data Generation

The sampling data are results of SPDpS technique, which consistsof distribution of disks, their attributions (color, size, orientation) andsampling order of disks. In artistic images, it is common that edges areemphasized and nearby regions with similar colors are drawn with one
stroke. Thus, we re-sample fraction of pre-sampled scalable Poissondisks to avoid edges by referring edge information obtained from input
image.

The method for stroke composition is based on Haeberli’s model,
and proposed method classified this model. The model generates
images with a hand-crafted look by placing brush stroke textures on acanvas. Proposed method consists of three processes, sampling, stroke
composition and visual effects.

First, the disks on edges are erased from the disk placement resultsof SPDpS technique. Note that disk placement by SPDpS technique iscalculated in advance without considering any edges. Next, a new disk
is sampled within the bounding rectangle of the erased disk. Here, thedisks in a square with black line in Fig. 4 are candidate disks
forre-sampling. In Fig. 4, the disk with dotted red line on the left islocated on the edge and is the target of erasing. The disks with redsolid line on the right are new resampled disks.

A. Sampling
1) Scalable Poisson Disk Pre-sampling Technique.

Distribution: Determined by re-sampling results of scalable Poissondisks mentioned above.

IV. PROPOSED METHOD

We propose a unified and fast system for generating various stylesof painting images by using pre-computed SPDS technique. SPDS
technique is an extended technique of hierarchical Poisson disk
sampling technique (HPDS, in short) [5]. HPDS technique places

Attribution:
Color: RGB color of input image that corresponds to the center ofthe coordinates of the disk of re-calculated SPDpS distribution.

Orientation: The colored paper texture is randomly rotated. The
orientation is determined by applying the ETF (edge tangent flow) forwater color, oil painting and pointillistic painting, since strokes should
flow along the edges of the motif.
Size: Determined by the radius of the each Poisson disk.
Order: The order of the rendering textures is determined by theSPDpS technique. Thus, lager textures are placed before smaller ones.
This process looks similar to actual painting process.

Fig. 4. Example of re-sampling of disks near the edge

B. Stroke Composition
1) Generation of Point Brush and Stroke BrushIn this section, we describe how to generate point brushes andstroke brushes from sampling data.
Point brush generation: Point brushes can be generated by using
sampling data as described in Section .A.2).
Stroke brush generation: Each disk is connected to its nearest
neighboring disk whose size and color is quite similar, whose distanceis smaller, and whose ETF is similar to the direction vector from one
disk to another disk. Stroke brushes are generated by following steps.
Step 1

Select one disk from all the disks arranged by SPDS
technique. Then, regard it as the target disk. Other disks arecalled as ‘listed disks’.

Step 2 Using the target disk and a disk from ‘listed disks’ (tentativedisk), calculate following five metrics: (1) the Euclidean
distance between center of both disks, (2) the radii difference,(3) the difference of center pixels colors, (4) the luminancegradient of the center pixels, and (5) the color difference
accumulated from the difference calculation between thecenter pixel of the target disk and the pixel on the line
between the target disk and a tentative disk scanned one byone. Judge if values of (1) - (5) are more than the thresholds d,∆ , t, ， respectively. Eliminate the tentative disk from‘listed disks’ if one or more values out of five metrics is morethan the threshold.
Step 3Choose a disk whose Euclidean distance is closest to thetarget disk from the ‘listed disks’ remaining after Step 2. Thecandidate disk is connected to the target disk and composed astroke brush. Map a stroke texture on it. Proceed to Step 4. In
the case of no candidate disk, judge it as a point stroke, andmap a point texture on the disk, and go back to Step 1.

Step 4 Go back to Step 1 if the number of times of drawing between
the target disk and the candidate disk exceeds a threshold m.
If it is below m, judge the candidate disk as a target disk andgo back to Step 2.
The stroke texture as shown in Fig.5 (a), (b), (d), (e) are renderedat the position determined above.

(a) Torn coloredpaper(b) Watercolor stroke(c) Noise forbumpiness of apaper(d) Stroke forpointillistic painting(e) Oil painting stroke(f) Noise forturbulent flow

Fig. 5. Stroke and noise textures2) Implementation
Generation

Issuesfor

Fast

StrokeBrush

According to the algorithm described in Section .B.1), all thesampled disks except the target disk (we call these disks as ‘listeddisks’) are tested whether they satisfy five metrics or not. Finally, thecandidate disk is determined from ‘listed disks’. This procedure isapplied to ‘listed disks’, so it is tedious, not effective.
We introduce a new search strategy to reduce the number of disks
to be evaluated by five metrics. A canvas is subdivided into smallregions. Each region is called ‘a small area’. First, we seek a disk fromall the disks in the small area where the target disk belongs to. If five
metrics are calculated, and the disk satisfies conditions, the disk isdecided as a candidate disk of the target disk. These two disks
compose a stroke. If there are no disks satisfy the conditions, searchareas are expanded to its adjacent 8 small areas. Repeat this procedure
until the candidate disk is determined.
Because the number of disks to be evaluated as candidate disks isgreatly decreased, this search strategy is very effective to composestrokes.

C. Visual Effects
In visual effects process, the composited strokes result isemphasized with effects of painting materials or techniques. We
developed nine techniques to realize these effects.

1) Effects Derived from Painting Materials(1) Bumpiness of the paper
The bumpiness of the paper effects fluid flow or visual of torncolored paper. We synthesis noise texture (Fig. 5 (c)) on thecomposed stroke image.
(2) Turbulent flow of the pigment
In wet-on-wet painting, the color of the pigment runs. In order torealize the effect of turbulent flow, the texture shown in Fig. 5 (f)is provided and synthesized.
(3) Pencil strokes remaining on a canvas
In order to represent pencil strokes remaining on a canvas, edges
are extracted from the input image by applying the Laplacian
filter, and are synthesized.

(4) Shadow casting
In case of colored paper mosaic, for example, the actual work
using thick colored paper has transparent shadow around a pieceof torn colored paper. A shadow-casting effect is expressed byplacing the texture initiated shadow of the torn colored paper,under it.
(5) Scrape of the paint pigment
Looking at an actual oil painting stroke, we notice that it is thickat the beginning and gradually scrapes. To express these effects,
we provide a texture as shown in Fig. 5 (e), adjusted its alphavalue to gradually decrease along its brush stroke.
(6) Bumpiness of the paint pigment
To express bumpiness of the paint, we applied emboss filter tothe rendered strokes.

2) Effects Derived from Painting Techniques

V. RESULTS
Figs. 1(b)~(e) show the generated different painterly style images
by our system from an input as shown in Fig. 1(a). Fig. 1(b) is awatercolor-like image, (c) oil painting, (d) colored paper mosaic, and(e) pointillistic painting, respectively. As shown in Fig. 1, our system
is able to generate various artistic style images.
We measured the computational time of both sampling and stroke
composition processes of proposed SPDpS technique andconventional SPDS technique. We tested on a standard PC with a
2.5GHz Intel Core i5 CPU and 4GB memory. The input image size
was 2048×2048 pixels. Fig. 6 shows computational time of watercolor
painting, oil painting, colored paper mosaic, and pointillistic painting.
SPDpS technique was much faster than conventional SPDS techniqueby about 164.3, 64.9, 17.6, 80.7 times, respectively.
The computational time of visual effects process by theconventional SPDS technique is almost same as proposed SPDpS
technique. It is about 2~5 seconds.

Juxtaposed vivid color dots cause similar spectra of colors
because the additive color mixtures on a retina blend these dots
into one color. We achieve the optical mixture effect by error
diffusion technique efficiently, which relies on randomly placed
Poisson disks. We use Hausner’s technique [2] with modification.
(8) Complementary color contrast

Styles of Paintings(7) Optical mixtureThis visual effect generates very brilliant color contrast byplacing two or more complementary colors side by side. It is used
to express shading. First, we generate stippling by altering theradius ri of Poisson disks depending on luminance li of input
image at the sampling point i as follows:To generate halo, we use modified unsharp mask (MUM, inshort). MUM Ui at pixel i is expressed as follows:= ∙ 1−∙ ∙−∙ −(2)√Here, A is constant for tuning effect, Di is a distance map
obtained by Canny’s method, s is kernel size of Gaussian blur, B=100, expectation =127, variance =40, Ii is a luminance at
pixel i, Gi is a low frequency component obtained by Gaussianblur.

3) Effects Derived from Painting Materials

SPDpS (Proposed)

10100

1000

VI. CONCLUSIONS
We have proposed a fast generation system for various painting
style images by using SPDpS technique. We have shown that our
proposed system has drastically shortened the time required for theprocess.

REFERENCES
[1]
[2]
[3]

Watercolor: (1) Bumpiness of the paper, (2) Turbulent flow of thepigment and (3) Pencil strokes remaining on a canvas.

[5]

Oil painting: (5) Scrape of the paint pigment, (6) Bumpiness of thepaint pigment and (9) Halo effect.

[6]

It is also possible to originate other combinations of our visualeffects according to user’s preference.

1

Computational Time (seconds)

Fig. 6. Computational time of SPDS and SPDpS techniques insampling and stroke composition process[4]

Pointillistic painting: (6) Bumpiness of the paint pigment, (7) Opticalmixture, (8) Complementary color contrast and (9) Halo effect.

Colored paper mosaic

SPDS (Conventional)

In our system, we can generate multiple painterly style images bycombining several visual effects according to each artistic style. We
provide templates to generate watercolor, oil painting, colored paper
mosaic and pointillistic painting as shown in Fig. 2.

Colored paper mosaic: (1) Bumpiness of the paper and (4) Shadow
casting.

Oil painting

Pointillistic painting=×−(1)+
Next, complementary colors of each point of stippling arecalculated by using RYB color wheel.
(9) Halo effect

Watercolor painting[7]

P. Haeberli, “Paint by Numbers: Abstract Image Representation,” Proc.
ACM SIGGRAPH 90, Vol.24, No.4, pp. 207-214, 1990.
A. Hausner, “Pointillistic Halftoning,”Proc. Computer Graphics andImaging, pp.134-139, 2005.
J. Hays, and I. Essa, “Image and Video Based Painterly Animation,”
Proc. Non-Photorealistic Animation and Rendering 04, pp.113-120,
2004.
H. Johan, et al., “A Method for Creating Region-Based and StrokeBased Artistic Images,” The IEICE Transactions on Information andSystems, Vol.88-D2, No.2, pp.358-367, 2005. (in Japanese)
M. Mccool, and E. Fiume, “Hierarchical Poisson Disk SamplingDistribution” Proc. Graphics Interface 92, pp.94-105, 1992.
Y. Shimakage, et al., “An Automatic Generation Method of Watercolorlike Images Considering Color Mixture,” Proc. International Workshop
on Image Electronics and Visual Computing (IEVC 2010), Article 4B-2,2010.
J. Sugita, et al., “Visionary Mixture Method for Generating ColoredPaper Mosaic Images,” ACM SIGGRAPH 2006 Research Posters,Article No.115, 2006.